| With the development of Internet, People pay more and more attention to network security. Firewall, which is a bridge of the interaction between internal network and external network, plays an important role in network times. However, due to the sufficient IP address and so much weakness of IPv4 network system, it is destined for network system to transform from IPv4 to IPv6. Thus, a high performance rule mathcing algorithm based on IPv6 has become a key research point in network security field. Aiming to being implemented high performance IPv6 firewall in linux kernel, this paper details in analiysing high speed rule matching in packet classification and the key point in implementing this algorithm. My main working is as follows:Firstly, the paper details introduction of the architecture of linux firewall and packet flow. Through elaborating packet processing flow of linux kernel, management of hook in Netfilter, data structure of the rule in Iptables and debugging on real system, we can have a detailed knowledge on linux firewall, which is necessary for implementing an intact linux IPv6 firewall in the next step.Secondly, the papaer has a in-depth analysis on the current research status of packet classification of firewall. As is known to all, linux implemented firewall based on linear searching algorithm. With the increasing of the number of rules, especially in the scenes of enterprise firewall or a core router, the performance of this algorithm will dramatically decrease. Even so, there are lots of optimized algorithms, one of which is the HiPAC(High Performance Packet Classification for Netfilter), based on range location. Through splitting a match range into umpty parts, HiPAC algorithm converted rule matching problem into range location problem. Its performance show a greate advantage over algorithms based on linear searching in the case of large number of rules. Besides this, the search performance of HiPAC have nothing to do with increasing of the number of rules. However, HiPAC will consume lots of memory, and its space complexity will grow exponentially with the increase of the number of rules.Having analyzed existing IPv4 firewall packet classification algorithm, We analyzed the characteristic of IPv6 firewall, finding that those high performance rule matching algorithm based on IPv4 are not suitable for IPv6. The main cause of this situation is that the range of IPv6 address is much bigger than the range of IPv4 address, which will dramatically augment IP address range, consequently augment space complexity. Considering factors referred above, we come up with a high performance rule matching algorithm suitable for IPv6, named HiPACv6. This algorithm colligated the advantage of range location matching algorithm and the advantage of linear searching algorithm, compromised time complexity and space complexity. By classifying the whole rules into 20 parts according to protocol field and destinatin port field, this algorithm then select bits from connection between source IPv6 address and destination IPv6 address, constructing binary trees. And finally these 20 rule sets are splitted into umpty small rule sets. When a packet matches one of these rule sets, we then exploit linear searching algotithm to match all rules in this small rule set. Through these policies, we gain a high boost to IPv6 firewall performance. As well as this, the utilizing of memory is under control.Eventually, we implemented HiPACv6 in linux kernel. And we analyzed the key points of this algorithm, including processing of UDP fragments, processing of encrypted packets and Bit Selection. The result of experiment shows that the communication bandwidth between two hosts equipped with 1000M-NIC can reach 700Mbps under large number of rules, while Ip6tables can only reach 100M bandwidth under the same condition. As a IPv6 firewall, we can see HiPACv6 has a good performance. It can meet the demands of enterprise firewall. |
PDF Full Text Request