随着计算机网络的高速发展,对网络设备的数据处理能力要求也越来越高。流分类技术将数据包按照指定的规则分类,从而提高网络设备的处理和转发速度,是防火墙和UTM网关等网络设备的关键技术。目前,流分类研究主要集中在多维、大规模规则库下如何提高流分类的时空效率。本文介绍了流分类技术的研究背景和现状,以及经典的流分类算法,包括BV算法、ABV算法、AFBV算法、RFC算法等,并分析和比较了这些算法的时间和空间性能。针对ABV算法空间开销大,AFBV算法时间效率低,本文提出基于前缀分组表的位向量流分类算法——BV。PBV算法采用分步查找,首先在前缀分组表和位向量图中进行查找,并将两次匹配结果取交集；然后将数据包的协议字段与交集中的规则逐一匹配,得到最终分类结果。通常规则库中可能存在多个规则对应相同的IP地址前缀。PBV算法首先按源／目的IP地址前缀,将规则库所有规则划分成若干个前缀分组,使得规则库中的多个规则映射为前缀分组表中的一个分组,从而使前缀分组表的规模远小于规则库的规模,用前缀分组表取代原来的规则库,提高了匹配效率。对源／目的端口号字段进行值域划分,建立位向量图,无需进行位向量聚合,减少了内存开销。最后,基于Linux系统Netfilter框架,设计并实现了基于PBV算法的流分类器,并应用于UTM网关。对PBV算法的性能进行了测试,实验结果表明,PBV算法在大规模规则库下具有良好的时间和空间性能。