Study Of Fast Packet Classification Algorithm And Its Application In Firewall

With the rapid development of network technology and the emergence of various new services, packet classification is widely used in high-speed network, and becomes the basis for many network technologies. The speed and performance of packet classification algorithm directly affect the performance of network. So it is very important to research a better method with high speed. In this paper, we analyse some kinds of algorithms, and propose an new method which based on Recursive Flow Classification and hash tree, then apply it to the firewall. The research of the paper is as follows:(1) With the description and analysis of several typical packet classification algorithms in the world, the performance and applications are compared.(2) The main idea and the performance of RFC are described and analyzed. The algorithm takes a lot of memory. So, the rule set merger and the CBM compression are used in this article.(3) Based on the structure of the rule base and the statistical properties of IP address prefix length and other fields, a new method based on RFC and hash tree is proposed. The method processes two IP address fields and other fields separately, using hash tree to process the address fields, while other fileds are handled by RFC. The simulation result shows that the algorithm can maintain the search speed, but the memory requirement is lower than RFC.(4) The algorithm is applied to the packet filtering module to improve the performance of the firewall. The results show that the performace of the firewall is better than that based on linear search in the complex rule base and network environment.