算法(Hierarchical Tries)分层查找树算法就是将分类字段的每一个维分成一层构造一个分层查找树,实际上就是对一维查找树的简单扩展,使用递归方式来生成分层查找树。基本思想是:设一个分类器C＝｛Rj)有k个域,如果k＞1,开始构建第一维的查找树,将其称之为F1.trie,它所对应的是分类器中每一条规则第一个域的前缀集｛Rjl)。F1.trie中的每个结点表示一个前缀front,然后在front处进行递归构建一个(k—1)维的分层查找树T口¨町。前缀节点1jront使用“下一级查找树的指针next＂指向下一级分层树Tp。由表2.1的规则库得出的分层查找树如图2.3所示。假设D是树中一个结点,如果D’是D的前缀,一般称D’是D的祖先。如果D’是D的最长前缀,则称D’是D的最小祖先。分类过程:进入分类算法的IP报文D(Dl,D2,…,Dd),分层树查找算法首先根12 据Dl在F1.trie树上进行遍历,从而找到Dl的一条最佳匹配前缀,记下最后一个匹配结点为Z,然后沿着“下一级查找树的指针next”继续遍历(Z—1)维的分层查找树,记录下这条路径上所有匹配的规则。接着要回溯到Z的最小祖先Z’,所谓的最小祖先就是指设Z是树中一个结点,如果Z’是Z的最长前缀,则称Z’是Z的最小祖先。继续沿着Z’的“下一个查找树的指针next’’进行遍历,直到Z节点的所有祖先都被遍历一次为止。
IP(Internet Protocol)报文分类在虚拟专用网络、基于策略的路由、区分服务、流量计费等领域得到了广泛的应用。IP报文分类是路由器根据IP报文的多个域，从分类器数据库中匹配每个输入报文，确定报文转发规则的技术。IP报文分类是因特网提供一切有差别服务和其他新业务的基础，高速IP报文分类问题是具有重要现实意义和理论价值的研究课题。 本文研究旨在总结IP报文分类技术的研究背景；系统地分析比较原有的IP报文分类技术；在此基础上，提出高效无冲突的IP报文分类算法：利用IP报文查找与分类模拟器，对本文的相关研究进行验证。具体内容包括： 1.系统地总结和评述了IP报文分类的相关技术，然后通过对现有主要的IP报文分类算法进行分析和性能比较，论述了报文分类在网络技术领域中的应用和一些还需解决的其它相关问题。 2.针对IP报文分类中的规则冲突问题、哈希构造问题和多维问题，提出了解决办法。在此理论基础上设计一种新的无冲突的多维快速IP报文分类算法，该算法通过删除冗余、压缩操作、建立等价类降维、解决规则冲突。 3.为了验证改进算法的正确性和有效性，使用报文查找与分类模拟器PALAC(Packet Lookup And Classification simulator)对主要的几种IP报文分类算法和改进算法进行模拟仿真。 IP报文分类技术是路由器研究与发展中一项新兴的、活跃的研究技术，许多问题仍未解决，相信本文的工作对从事计算机网络研究和网络工程方面的相关人员具有较大参考价值和指导意义。
Gocheck论文检测系统文章欢迎转载，转载请以链接形式标明本文地址。
