Research On Packet Classification Algorithms For Packet Filter Firewall

Firewall is a common method on advanced router to prevent network attacks.Firewall is a basic security technology on network layer. But with the network technology fast developing, the firewall is become a more complicated and advanced application gateway. On the router, firewall acts a role as a packet filter. The filter has many rules which contain the value of IP source address, IP destination address, protocol number, source port number, destination port number. These rules recorded by the access control list.In general, the filter use liner search to find the matched rule for target packet. When the number of the rule becomes larger, the liner search will lead to a low efficiency for the system and make the match time longer. As we know, the internet is geting larger and the demond for security is improving increasingly. So as a result, the number of the rules in firewall is also become more an more. Thus change a search algorithm to accelerate the system is neccessry.Firstly it is makes an explanation on the importance of network security for an enterprise and introduces the practical value of the packet filter firewall in this paper. Then the concept of packet filter and access control list is introduced. The bad performance of liner search match algorithm is also under a detail analysis.Secondly, some useful classification algorithms were listed and all the classification algorithms have its’ own detail analysis. Then it compares the different algorithms on space complexity, time complexity and updating complexity. Because of the rules in packet filter firewall has more then two property, the performance of all the algorithms on multiple fields is shown and the RFC algorithms and HiCuts algorithms is find better for the ACL firewall.Thirdly, deep study on the design of RFC and HiCuts algorithms for the packet filter firewall is taken. The struct of the data and the work process is designs and display. After simulating the two algorithms, their performance on lookup time, memory cost and preprocessing time is display in some figure. The experimental data tell a fact that these two algorithms have a great advantage on lookup times and then this article compares the the memory cost and preprocessing time of the two algorithms. Besides it also take a test on Linux firewall system. The comparison shows the two algorithms have a higher throughput than liner search. At last, summary of the work, the areas for improvement and the next direction of the research is point out. The designed data struct and work process of two algorithms have reference and guidance value for the algorithms applying on the router firewall.