一种IPV6环境下的高性能规则匹配算法研究

Research on High Performance Rule Matching Algorithm in IPV6 Networks

防火墙是确保网络安全的关键设施,而规则匹配又是防火墙的核心技术。随着网络技术的发展,互联网体系结构正逐渐从IPV4向IPV6结构发展,原有的IPV4防火墙规则匹配算法很难直接应用于IPV6网络环境,因为IPV6协议所能表示的地址范围远远超过IPV4协议对应的地址范围。因此提出了一种适用于IPV6环境的高性能规则匹配算法HiPRM(High Performance Rule Matching)。HiPRM算法的核心思想是依据规则的协议和目的端口分布特征,先把整个规则集划分成多个子规则集,再利用位选取算法对规则的源和目的IPV6地址组合的特定位进行选取,然后据此构建二叉查找规则树,最后利用规则树把多个规则子集划分成若干个更小的规则集合。而当报文匹配到某个更小的规则集合时,在小规则集中利用线性匹配法确定具体匹配的对应规则。分析和测试表明,HiPRM算法可以在时间复杂度和空间复杂度较低的情况下实现报文的高速匹配,且具有较好的规则集适应性。

As is known to all,firewall is the core device to guarantee network security,and rule matching is one of the most important technologies to firewall. However, those high performance rule matching algorithms based on IPV4 are not suitable for IPV6 with the network derivation from IPV4 to IPV6. The main cause of this situation is that the range of IPV6 address is much bigger than the range of IPV4 address. Thus we suggested a high performance rule matching algorithm suitable for IPV6, named HiPRM （High Performance Rule Matching）. HiPRM algorithm classifies the whole rule set into several parts with the protocol and destination port field of rules, and it selects special bits from the combi- nation of source and destination IPV6 address of rules to construct binary trees. After the construction of binary trees, those rule sets are split into smaller rule sets. When a packet matches one of these smaller rule sets, the linear searching algorithm is used to find the matching rules in this small rule set. Analysis and experiment results show that HiPRM al- gorithm not only has good time and space performance, but also has better scalability with different rule sets.