论文部分内容阅读
由于互联网中存在虚假和不健康信息,Web防火墙作为一种安全技术,其重要性也在不断增加。在Web防火墙中,由于网络动态性增强,其IP安全规则的更新愈加频繁的发生。与传统的IP匹配算法不同,Web防火墙中的IP地址匹配算法不但需要具备高的查找效率,而且注重更新的效率。同时,IPv6地址的启用也使得原有的匹配算法表现效果欠佳。本文从这两点出发,围绕IP匹配算法的更新效率和对IPv6的支持性展开研究。IPv4和IPv6的地址格式不同,更重要的是,为了增大IPv6的地址空间,使得IPv4的地址长度仅为IPv6的1/4。在两种IP协议中分别表现优异的算法在另外一种协议中并不十分适宜。因此,本文对IPv4和IPv6进行区分,分别设计了适用的算法。优先级Trie树通过利用普通Trie结构中的空结点,将高层次前缀存储其中,在空间利用率和查找速度上表现良好。但是,由于空结点中前缀的存储需要符合一定的规则,所以一个结点的更新可能会引发多个结点变化,更新性能较差。从改善优先级Trie树更新性能的角度出发,本文提出了B*Index Priority Trie(BIPT)结构。该结构分为两层,上层为B*树,存储索引值,下层为优先级Trie树,存储索引后缀。在更新和查找时,首先通过B*树找到对应的分支优先级Trie树,然后在分支优先级Trie树中进行进一步操作。通过减小优先级Trie树的影响区间以及使用多路查找,提高了算法的更新和查找效率。针对IPv6地址长度增加,本文提出基于流水并行模型的匹配算法,该算法可以应用于基于Trie的算法结构中。将IPv6地址分割并分别生成Trie树,从而使得每个Trie树中的地址长度减小而且可以并行执行。该算法由基于TCAM的并行算法演化而来,并对其做出了两点改进:一是利用流水技术替换TCAM的硬件并行,使该算法能够在软件环境中得以应用;二是对前缀的分割方法做出了优化,提高了两部分结果集的合并速度。基于流水并行的匹配技术可以保证匹配和更新操作被并行执行,从而减少了操作时间,提高了速度。