LPR-Trie: A Fast IPv6 Routing Lookup Algorithm with Virtual Nodes

The number of IPv6 routes in todays backbone routers has grown rapidly,which has put tremendous pressure on route lookup and storage.Based on the analysis of IPv6 address prefix length and distribution characteristics,this paper proposes an IPv6 route lookup architecture called LPR-Trie.The core idea of the algorithm is to utilize more spaces and accelerate routing lookup.Moreover,we put forward the concept of virtual nodes,and leverage the link between virtual nodes and ordinary nodes to accelerate routing lookup.We provide the longest prefix routing entry(LPR)calculation algorithm to achieve the longest prefix match.The experimental results show that the virtual node mechanism increases the search speed up to 244%,and the virtual nodes have better stability by setting an appropriate keep-alive time according to the characteristics of actual traffic.This paper shows that our design improves the routing lookup speed and have better memory utilization.

Trie树路由查找算法在网络处理器中的实现

Trie树数据结构的实现方法灵活,所需存储器空间小,是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s线速度网络处理器中微引擎的设计要求,提出一种基于最优平衡、多层存储的Trie树路由查找算法。建立一种平衡的压缩树结构,将该树中相邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度,以空间换取时间,从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现Trie路由查找算法,实验结果表明,单个微引擎的查找速度为4.4 Mb/s,能达到节省存储空间、提高查找效率的效果。

一种基于哈希表和Trie树的快速IP路由查找算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。

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

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

一种基于Trie的快速IP路由查找算法

Internet的飞速发展要求核心路由器能够实现快速的分组转发和路由更新功能,实现这一功能的关键是路由表的组织结构和快速的路由查找算法.提出了带有转发域信息树的多分支Trie结构路由查找算法,它由固定步长的多分支Trie结构的路由表和转发域信息树两部分组成.对于一个长度为w的路由前缀,其查找、插入、删除路由的时间复杂度均为O((w-m)/n+1),其中m、n为Trie树的步长.它解决路由查找过程中快速更新的问题,具有算法简单、查找速度快、易于更新、空间利用率高、便于向IPv6过渡等优点.

多分枝trie树路由查找算法研究

为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP路由算法的基础上,提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找,组成一个大的中间结点。在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示。仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用。

基于Trie的快速路由查找算法

随着互联网络光链路速率不断提高,路由查找已成为路由器报文转发的瓶颈。本文主要介绍近年来基于Trie的各种路由查找方法,同时对各种方法的性能进行了比较,最后介绍了一种性能优良的基于Trie的路由查找算法———压缩树算法。

散列索引多分支Trie树快速路由查找算法

路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进行IP路由查找,其存储器访问次数最多为7次,而且还具有易于更新、易于扩展等特点。

基于多分支Trie的路由查找算法设计与实现

基于多分支Trie数据结构的查找算法在路由查找中有着广泛的应用。文章对基于多分支Trie的路由查找算法进行了介绍,并对其特点进行了分析。在此基础上,设计实现了便于高速动态路由查找的多分支Trie数据结构,公开了一个使用多分支Trie数据结构的基于前缀值的动态最长前缀匹配算法,提高了路由查找速度。

大容量高带宽路由查找算法设计与FPGA实现

为了解决目前IP路由查表大容量和高吞吐需求的同时,实现低硬件资源成本,提出一种大容量高带宽IP路由查表算法,并完成FPGA实现。算法将FIB表项的存储映射为字典树的数据结构,进行路径压缩和级别压缩以节省存储资源。将字典树根节点信息存储在片内SRAM,子树节点存储于片外DRAM。查找时,在芯片硬件内采用流水线方式优化资源负载均衡,实现片外DRAM的一次访问即可得到结果,实现了单周期线速查表,并支持增量更新。该算法通过FPGA设计实现,并进行仿真和实机验证。结果表明,该方案可同时支持大容量IPv4和IPv6 FIB表项并行查找,与现有方案相比,做到了更大容量、更高带宽和更低成本。

基于哈希表与多比特树的路由查找算法

网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求。为此，将哈希表和多比特树相结合，提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层Tree中，采用哈希表存储路由下一跳的信息，根据目的IP地址在三层Tree结构中按最长前缀匹配的原则进行快速路由表项定位，并通过表项的信息在对应的哈希表中读取下一跳信息，进行数据转发。在多核平台上的测试结果表明，该算法在百万条路由环境下可达到双向10GB／s的速度，平均查找次数介于1～2次之间，平均延时小于30μs。

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

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

众核网络处理器下高速包转发系统设计与实现

互联网的快速发展要求网络设备能够支持每秒几百万以上分组的转发能力,实现这一功能的关键是路由表的组织结构、快速的路由查找算法和高性能的硬件平台支持。设计并实现基于众核网络处理器的高速IP包转发系统,使用Tile-Gx36众核网络处理器作为硬件平台,采用基于Hash的前缀长度和多分支Trie树的路由查找算法,借鉴基于Hash的前缀长度路由表查找算法在存储和检索上的优势,并结合基于多分支Trie树路由表查找算法的查询效率,将路由表存储于L2层缓存中,进一步提高了路由表的访问速度和查询命中率。实验结果表明,对于不同大小负载的数据包系统均能满足40 Gbps的转发速度。

采用分段哈希方法的IPv6路由查找算法研究

分析了现有IPv4路由表查找算法和IPv6地址的特性以及主干网路由表的前缀分布特点,借鉴LFT哈希表结构简单、查找快速的特点,提出了以32bits为查找路由前缀起点的分段哈希表和多分支Trie树相结合的IPv6路由查找算法。该算法结构简单、查找效率高、易于更新,多数情况下只需一次内存访问就可查找到路由信息,提高了IPv6主干网路由器转发速度,以满足下一代互联网IPv6发展的需求。

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

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

IPv4下路由查表及算法分析

查找路由表以给出下一跳地址是路由器中分组转发的核心步骤,因此快速的路由查表算法是实现高速分组转发的关键。该文分析了IPv4下路由查表问题及其难点,详细介绍了现有的各种查找算法并对它们进行了分析和比较,给出了在不同情况下应用适当查表算法的结论。

分组IP路由最长前缀匹配查找算法研究

介绍了几种常见的IP路由查找算法,并简单分析其优点与不足。二进制Trie树结构虽占用空间较小,但因其查找时间太长而很少运用于实际生活中,目前常见的算法都是在查找时间与存储空间上寻找折衷点.本文在此基础之上提出了一种基于分组IP路由最长前缀匹配查找算法,通过将IP前缀按其长度进行分组,并在各组内采用Trie树结构进行存储,最长只需4次存储器访问,且因利用了公共前缀,固能节约存储空间,实验结果表明,本算法在查找时间上取得了非常理想的效果。