基于前缀分组表的位向量流分类算法及应用研究

发布时间：2018-05-25 02:07

本文选题：流分类 + 前缀分组表　；参考：《合肥工业大学》2014年硕士论文

【摘要】：随着计算机网络的高速发展,对网络设备的数据处理能力要求也越来越高。流分类技术将数据包按照指定的规则分类,从而提高网络设备的处理和转发速度,是防火墙和UTM网关等网络设备的关键技术。目前,流分类研究主要集中在多维、大规模规则库下如何提高流分类的时空效率。本文介绍了流分类技术的研究背景和现状,以及经典的流分类算法,包括BV算法、ABV算法、AFBV算法、RFC算法等,并分析和比较了这些算法的时间和空间性能。针对ABV算法空间开销大,AFBV算法时间效率低,本文提出基于前缀分组表的位向量流分类算法——BV。PBV算法采用分步查找,首先在前缀分组表和位向量图中进行查找,并将两次匹配结果取交集；然后将数据包的协议字段与交集中的规则逐一匹配,得到最终分类结果。通常规则库中可能存在多个规则对应相同的IP地址前缀。PBV算法首先按源／目的IP地址前缀,将规则库所有规则划分成若干个前缀分组,使得规则库中的多个规则映射为前缀分组表中的一个分组,从而使前缀分组表的规模远小于规则库的规模,用前缀分组表取代原来的规则库,提高了匹配效率。对源／目的端口号字段进行值域划分,建立位向量图,无需进行位向量聚合,减少了内存开销。最后,基于Linux系统Netfilter框架,设计并实现了基于PBV算法的流分类器,并应用于UTM网关。对PBV算法的性能进行了测试,实验结果表明,PBV算法在大规模规则库下具有良好的时间和空间性能。
[Abstract]:With the rapid development of computer network, the data processing ability of network equipment is higher and higher. Stream classification technology classifies packets according to the specified rules, thus improving the processing and forwarding speed of network devices, which is the key technology of network devices such as firewalls and UTM gateways. At present, the research of stream classification mainly focuses on how to improve the spatio-temporal efficiency of stream classification under the multi-dimensional and large-scale rule base. This paper introduces the research background and present situation of flow classification technology, as well as classical flow classification algorithms, including BV algorithm, ABV algorithm, AFBV algorithm and RFC algorithm, and analyzes and compares the time and space performance of these algorithms. In view of the low time efficiency of ABV algorithm with large space overhead, this paper proposes a bit-vector flow classification algorithm based on prefix grouping table BV.PBV algorithm uses step by step lookup, which is first found in prefix grouping table and bit-vector graph. Then the protocol fields of the packets are matched with the rules of the intersection set one by one to obtain the final classification results. Usually there may be several rules corresponding to the same IP address prefix. PBV algorithm first divides all rules of the rule base into several prefixes according to the source / destination IP address prefix. The rules in the rule base are mapped to one group in the prefix grouping table, so that the scale of the prefix grouping table is much smaller than the size of the rule base, and the matching efficiency is improved by replacing the original rule base with the prefix grouping table. The source / destination port number field is divided and the bitvector graph is established without the need for bit vector aggregation, thus reducing the memory cost. Finally, based on the Netfilter framework of Linux system, a stream classifier based on PBV algorithm is designed and implemented, and it is applied to UTM gateway. The performance of the PBV algorithm is tested. The experimental results show that the algorithm has good performance in time and space under the large-scale rule base.
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.08

【相似文献】