Research On Packet Classification Algorithm And Its Application In Linux Firewall

With the rapid development of Internet, various network traffics are emerging,this requires the network device to provide wider bandwidth and quicker process ability. Packet classification is essential for policy-based firewall,intrusion detection, Qos, Virtual Private Network, traffic billing and so others, and is widely deployed within network devices such as routers and high-level switches.The thesis firstly introduces the research background, present study of the classification techniques, describes the main idea and characteristic of some typical algorithms. Further more, the thesis makes deep research on the RFC algorithm and finds out that it may run into memory explosion in some cases,such as large classifier, multiple fields and IPv6 environment. Then it proposes an enhanced algorithm called ERFC which processes two address fields and other fields differently and applies address fields with a geometry point location matching scheme.Moreover,the thesis gives analysis on implementation details of the current Linux netfilter/iptables firewall which adopts a low-performance linear rule matching policy. And as a significant real application of the classification techniques , the thesis design and implement a fast filtering module based on the ERFC algorithm to improve the Linux firewall.Finally, the thesis tests the related algorithms and the effect of filtering module on an integrated experiment platform which is based on Linux operating system. The result indicates that, compared with RFC and linear search algorithm, ERFC algorithm makes a good trade-off between speed and storage, and it is also proved that the ERFC-based filtering module makes a great improvement on linux firewall.