IP分类技术研究

网络应用的发展要求路由器必须有能力支持防火墙、QoS、流量计费等一系列功能.这就要求路由器对IP包进行分类,根据分类结果完成对数据包的不同处理.本文全面地介绍了IP分类技术研究的最新成果,以及IP分类的典型算法.最后本文对其中三种典型算法在虚拟环境下做了评测,比较了它们的优缺点.     

最长前缀匹配查找的索引分离trie树结构及其算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。索引分离trie树结构建立了具有k比特的一级索引,m比特的二级索引和步宽为s、最大深度为m/s的多分支trie树结构。在这种数据结构中进行最长前缀匹配查找的算法复杂度为:O(m/s+2)。它具有算法简单、查找速度快、易于更新、便于向IPv6过渡等特点,是一种综合性能较好的快速最长前缀匹配查找算法。