Research And Implementation On Optimization Technology Of Packet Classification Based On Netfilter

With the wide and deep application of network technology nowadays, the problem of network security is becoming more and more urgent, and people's requirement for better performance and function of firewall is coming forth. From kernel 2.4, Linux used Netfilter/IPtables as firewall, which can provide mighty function of filter and capacity of being extended, and it is easy for user to define and extend new modules of filter. As the scale of firewall rule set is becoming larger and larger, and at the same time, the extended modules included in rules are more and more complicated the performance of Netfilter/IPtables firewall decline fast. To meet this practical requirement, the thesis gives a deep research on the optimization technology of firewall's performance.The thesis firstly gets a deep analysis of the Netfilter/IPtables, and finds that rules are stored by sequence, and the matching process is linearly implemented in Netfilter/IPtables system. So as the rule number becomes larger, the performance decline fast. This thesis designed and implemented a Two-Level Packet Classification Algorithm based on protocol and port. According to the principle of"divide and conquer", the rule set is divided into four classes: TCP rule set, UDP rule set, ICMP rule set and no protocol related rule set based on transport layer protocol. The TCP, UDP and no protocol related rule sets are divided into second-level classes based on source port or destination port. The hash key of rule's source port or destination port is used to classify the rule sets, and hash collision is solved by using chains. Packets will by classified through two levels when passing through firewall, and only need to be matched with rules in the corresponding second-level rule chain, which can reduce the matching times effectively.Analysis of network traffic shows that, IP flows have a characteristic of locality, that is an active IP flow is likely to be active in recent time. According to this statistics, the thesis put forth a dynamic rule order adjusting algorithm. When a rule is matched with a packet in an IP flow, moving the rule to the head position of the rule chain can reduce the match time when the successive packets of the same flow is coming, which can improve the efficiency of rule matching. Practical tests show that new packet classification technology with dynamic adjusting order algorithm can increase the firewall's throughput by 110% in case of 400 rules. At the same time, this new packet classification algorithm's demand for memory is less than the other algorithms of the same kind, and the space complexity is relatively weak.As the diversity and complexity of modern network applications growing, more and more types of protocols have the demand of filtering, and match modules are applied more and more widely. All these conditions will reduce the performance also. In case of large-scale rule set of firewall, an optimization algorithm named"Once Decoding, More Matching"("ODMM"in short ) is put forward, which is used for the same match modules in different rules, and can improve the performance of firewall further. Tests show that optimization algorithm can increase the firewall's throughput by 30% in case of 200 rules.Finally, a software prototype system is designed and implemented based on the optimization algorithms above. System tests show not only the optimization algorithm's rightness in function, but also the effectiveness in improving system's throughput and reducing system's delay.