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

Research on High Performance Rule Matching Algorithm in IPV6 Networks

作　　者：庞立会[1] 江峰[1] PANG Li-hui JIANG Feng(School of Computer,National University of Defense Teehnology,Changsha 410073,China)

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机科学》2017年第3期158-162,共5页Computer Science

基　　金：国家863项目:QoS服务质量保证设计(2012AA01A50606);国家自然科学基金项目:高级持续威胁网络行为建模与检测方法研究(61303264)资助

摘　　要：防火墙是确保网络安全的关键设施,而规则匹配又是防火墙的核心技术。随着网络技术的发展,互联网体系结构正逐渐从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.

关 键 词：防火墙 规则匹配 IPV6 二叉树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]