基于前缀扩展的快速路由查找算法

该文对路由器中的快速路由查找算法进行了研究。针对路由查找算法在查找速度、算法空间复杂度以及插入和删除表项的难度算方法存在的问题,提出了一种快速路由查找算法。该算法通过构造两级索引表结构来减小路由查找的访存次数以提高查找速度;利用前缀扩展的特性并采用特殊的数据结构来构建索引表,能支持动态插入、删除和更新路由;采用压缩技术对二级索引表进行压缩,从而大大减小了路由所需的存储空间。该算法最多四次访存,最少两次访存就完成一次路由查找。由于采用了压缩方法,所需存储空间很小,该算法不仅适合于软件实现,也适合于硬件实现。查找速度快、存储空间小并支持动态插入和删除是该算法的主要特点。     

一种改进的IPV6最长前缀匹配路由查找算法

本文就是在研究已有算法的基础上,结合IPv6地址的特征以及路由表中前缀的分布规律,提出了一种改进的、基于索引表和Trie树的查找算法,该算法在时间复杂度和空间复杂度上表现出了较好的性能。     

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

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

高速路由器中基于树型结构路由查找算法的研究与实现

本文在比较各种基于树型结构查找算法的基础上提出了一种改进的路由查找算法,该算法具有查找速度快、所需存储空间小、更新速度快、硬件实现简单等特点,能够满足10Gbps核心路由器环境的要求。     

基于分段地址结构的快速路由查找算法

根据IPV6地址结构和骨干路由表特点,分析了原有路由查找算法,基于IPV6的掩码长度和分段地址,采用Hash表和多分支Trie树结构,提出了一种快速的IPV6路由查找算法。根据分段地址和掩码将最常用到的路由前缀按前缀长度设置Hash表,并将前缀值有序存放在表结点中。不仅可以进行前缀长度的二分查找,同时又是其它前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。实践证明该算法具有较好的时空效率,可以较好地提高路由查找速度。     

基于索引和压缩的超高速路由查找及更新算法

在下一代核心路由器的研究中．需要在规定的硬件成本和功耗限制下同时实现超高速路由表的查找和更新是目前研究的难点．论文提出了一个全新的超高速路由表查找及更新算法．该算法采用了基于索引和路由表隐式压缩的方案，不仅实现了可以在每一个SRAM的访问延时周期内输出一个路由查找结果．而且能够在两次SRAM的读写访问延时下完成路由更新．该算法功耗小，存储效率高，整个路由表的信息都可存放在容量接近于1M字节的SRAM中．     

一种前缀长度二分查找的改进算法

在研究路由表地址前缀分布特点的基础上,提出了前缀长度二分查找方案。该方案采用前缀扩展技术,将前缀数量相对稀少的若干种前缀合并成一种,降低了查找树的高度,减少了存储器访问次数,提高了查找速度,分析了一种实用的Marker存储算法,探讨了IPv6的路由查找问题。     

支持压缩和多下一跳查找的路由查找方案

TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中.     

一种新的快速IPv6路由查找算法

在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。     

路由查找算法研究综述

随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps～10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向.     

对路由表结构和查找算法的研究

随着网络流量的指数性增长,每秒能够传输10G以上比特的光纤骨干网络大量投入使用,但是大部分骨干路由器无法相应达到每秒转发百万个分组的高速,成为网络瓶颈。分组转发性能由多种因素决定,其中路由查找算法是关键。综述了近年来在路由表数据结构和查找算法的研究方面的最新进展,并对一种较先进的转发表结构进行了重点分析。     

基于LFT和DAG方式的IPv6路由查找算法

随着网络的不断发展,路由表的信息量也在不断增加,这势必会影响路由转发的效率,影响网络速度.在分析了衡量路由算法优劣的标准后,又通过对现有IPv4和IPv6各种路由算法的分析,尤其是LFT和DAG结构的说明,综合了二者以及LC Trie的优点,提出了算法改进的思想,给出了算法的主要数据结构以及算法执行的流程图,此算法提高了路由查找效率.     

IP路由缓存技术研究

针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性,分析了骨干网路由表前缀重叠特征,提出了一种基于阈值的IP路由缓存方法,该方法结合了地址缓存和前缀缓存技术,无需进行前缀扩展,克服了地址缓存技术缓存空间要求过大、前缀缓存技术无法缓存内部前缀节点的问题,在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势;仿真实验表明对于路由条目超过260 000的路由表,缓存空间大小为30 000,选择阈值K=4时97%以上的节点可实现1∶1缓存,其余节点采用地址缓存,缓存失效率小于0.02,可以用小的缓存空间实现高速线速转发.     

基于多分支优先级树的IP路由查找算法

针对现有路由表查找方法效率低的问题,提出了一种基于多分支优先级树的数据查找算法。该算法将优先级较高的前缀依次存储在原多分支树的虚节点上,将需要进行扩展的前缀存储在辅助存储结构中,从而在路由查找时,该方法可在内部节点找到最长前缀匹配而无需查找到叶子节点,同时避免了在路由表更新时对路由表的重建。仿真结果表明,提出的查找算法能够有效减少在对路由表查找、插入和删除操作所需的内存访问次数,并大幅度地提高路由查找及其更新速率。     

一种基于哈希编码的内容路由查询匹配机制

基于名字的路由查找是命名数据网络(NDN)的一个关键技术,但由于NDN名字层次化的结构以及无限制的长度,使得查询匹配的实现具有很大的挑战性.提出一种有效的元素哈希编码机制,首先利用哈希函数压缩数据名字,然后采用改进的状态转换阵列实现名称最长前缀的快速匹配,最后设计一种快速的增量更新机制,满足NDN转发过程中频繁地插入、修改与删除等操作.仿真结果表明,提出的方法使路由条目压缩率达到40％以上,匹配速率提高约10％.     

B-树和Bloom filter相结合的IPv6路由查找算法

为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和Bloom filter相结合的IPv6路由查找算法（BTBF）。BTBF分为B-树和Bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到Bloom filter,再利用Bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和Bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。     

基于RAM和TCAM存储结构的高速路由查找算法

由于因特网速度的不断提高,网络流量的不断增加和路由表规模的不断扩大,IP路由查找已经成为制约核心路由器性能的主要瓶颈。文章分析了两种常用的基于硬件存储器的路由查找算法,并结合它们各自优点,提出了一种基于RAM和TCAM存储结构的路由查找算法,该算法克服了上述两种算法的不足,具有查找速率高、更新时间快、存储代价低、易于实现等特点,是一种理想的适合于高速核心路由器环境的查找机制。     

基于多层混合结构的IPv6路由表查找算法

针对现有的大多IPv6路由表查找算法采用各种优化手段提高查找性能,却使得路由更新需要重构整个路由表的问题,提出基于多层混合结构的IPv6路由表查找算法。该算法在第一层借鉴最优查找树的优点,把前缀1~16位的不同取值按其在路由表中出现的概率降序存储在线性表中,在第二、三层把前缀的17~32位和33~48位分别用二叉平衡树组织,在第四层把49~64位使用线性表组织。实验结果表明,该算法查找速度快,占用内存少,动态增量更新速度快。