Research And Application Of Bit Vector Flow Classification Algorithm Based On The Prefix Grouping Table

With the rapid development of computer networks, the higher data processing ability is required in the network device. The flow classification can increase the speed of processing and forwarding of network device which can classify the data packet in accordance with the specified rules and it is the key technology of firewalls and UTM gateway and other network devices. Currently, the research of traffic classification is mainly focused on how to improve the efficiency of flow classification under multi-dimensional and large-scale rule base.This dissertation describes the background and present research situation of the flow classification, and the classic flow classification algorithms, such as BV algorithm, ABV algorithm, AFBV algorithm, RFC algorithm, and analyzes the time and space performance of these algorithms.For ABV algorithm’s large space costs and AFBV algorithm’s low time efficiency, a bit vector flow classification algorithm based on prefix grouping table - PBV algorithm is proposed. PBV algorithm uses the step-query. Firstly, it searches in the prefix table and bit vector diagram, and take the intersection set of the two matches. Then, it matches packet protocol field with the rules of the set to get the final classification result.There may be multiple rules corresponding to the same IP address prefix in the rule base. In order to improve the matching efficiency, PBV divides all rules into a number of prefixes grouping by source/destination IP address prefix, making multiple rules in the rule base be mapped to a subgroup of the prefix table,so that the size of the prefix grouping table is much smaller than that of the rule base. the original rule base is replaced by the prefix grouping table to improve the matching efficiency.The source/destination port number fields are partitioned and a bit vector diagram is created without making bit vector1 aggregation,which reduces memory costs.Finally, based on the Linux Netfilter framework, a flow classifier based on PBV is designed and implemented, which is embed in the UTM gateways. The function of the PBV algorithm is tested and analyzed. The experimental results show that PBV algorithm has excellent performance in time and space under the large rule base.