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

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

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

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

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类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。     

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

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

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

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

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

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

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

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

使用Hash表和树位图的两级IPv6地址查找算法

为了提高IPv6地址查找效率,在分析IPv6路由前缀长度分布规律的基础上,提出了基于哈希表及树位图(Tree-bitmap)的两级IPv6地址查找算法.算法将长度为16,32,48和64比特的前缀分别存储在4个Hash表中,其余前缀的前16,32和48比特利用已有的Hash表存储,剩余的不足16比特的部分前缀利用树位图存储,并将树位图的入口地址保存在Hash表中.IP地址查找时在Hash表和树位图中进行两级查找.实验表明,该查找算法的平均内存访问次数为1～2,最坏情况下为7,适用于高速IPv6地址查找.     

基于无冲突哈希表和多比特树的两级IPv6路由查找算法

为了提高IPv6的路由查找效率,根据IPv6路由前缀分布规律和前缀层次关系,提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中,剩下不足的前缀比特由多比特树存储,IPv6路由查找时在无冲突哈希表和多比特树中两级查找。实验表明,该查找算法的平均查找路径数为1.0~1.7,适用于高速的IPv6路由查找。     

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

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

Fast binary and multiway prefix searches for packet forwarding

Backbone routers with tens-of-gigabits-per-second links are indispensable communication devices to deploy on the Internet. The IP lookup operation is the most critical task that must be improved in routers. In this paper, we first present a systematic method to compare prefixes of different lengths. The list of prefixes can then be sorted and stored in a sequential array, which is contrary to the linked lists used in most of trie-based structures. Next, fast binary and multiway prefix searches assisted by auxiliary prefixes are proposed. We also developed a 32-bit representation to encode the prefixes of different lengths. For the large routing tables currently available on the Internet, the proposed multiway prefix search can achieve the worst-case number of memory accesses of three and four if the sizes of the CPU cache lines are 64 bytes and 32 bytes, respectively. The IPv4 simulation results show that the proposed prefix searches outperform the existing IP lookup schemes in terms of lookup times and memory consumption. The simulations using IPv6 routing tables also show the performance advantages of the proposed binary prefix searches. We also analyze the performance of the existing lookup schemes by concurrently considering the lookup speed, the update speed, and the memory consumption. Although the update speed of the proposed prefix search is worse than the dynamic routing table schemes with log(N) complexity for a table of N prefixes, our analysis shows that the overall performance of the proposed binary prefix search outperforms all the existing schemes.     

A longest prefix first search tree for IP lookup

The IP lookup mechanism is a key issue, in the design of IP routers. IP lookup is an important action in a router, which finds the next hop of each incoming packet with a longest-prefix-match address in the routing table. This work places the routing table on a longest prefix first search tree, which is constructed as a heap-like structure by the prefix length. A router using this scheme has fewer memory accesses when executing IP lookup than a router designed according to the Trie [E. Fredkin, Trie Memory, Communication of the ACM 3 (1960) 490–500], Patricia [K. Sklower, A tree-based routing table for Berkeley Unix, in: Proceedings of the USENIX Conference, 1991, pp. 93–99] or Prefix tree [M. Berger, IP lookup with low memory requirement and fast update, in: Proceedings of IEEE High Performance Switching and Routing, 2003, pp. 287–291]. Some nodes of the proposed tree can include two entries of the routing table to decrease the number of tree nodes. For instance, a routing table with 163,695 entries can be held in the proposed tree with 156,191 nodes. Furthermore, an improved scheme is presented to partition a tree into several smaller trees. The simulation reveals that the scheme not only lowers the tree height effectively but also scales well to IPv6 addresses.     

基于二分搜索Trie的IPv4/IPv6路由快速查找算法

提出了一种独特的基于前缀长度二分搜索Trie的IP路由查找算法,融合了基于前缀长度的二分查找算法和基于Trie的查找算法的优点,采用部分IP地址作为索引,避免了使用Hash函数,提高了路由查找速度和表项更新速度;支持路由表的动态更新;算法扩展性好,可满足IPV4和IPV6两种协议栈的OC-48(25Gbps)、OC-192(10Gbps)接口的线速路由查找。     

基于多处理机结构的IP路由搜索技术

随着因特网的飞速发展以及128位地址的IPV6的出现,路由表变得日益庞大,这给IP目标地址的查找速度提出了更高的要求。IP地址查询使用的不是精确匹配,而是最长前缀匹配,因查询极其复杂。论文针对现有的IP查询技术的缺点和不足,提出了一种基于多处理器结构的搜索技术,这种技术减少了查找的比较次数和存储空间。     

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

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

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

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

基于LSOT的高速IP路由查找算法

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大，IP路由查找已经成为制约路由器性能的重要原因，因而受到广泛重视。目前人们已经提出几种算法用于解决IP路由查找问题，但均不能完全满足核心路由器的要求。该文提出一种基于LSOT的IP路由查找方法，它使用可变大小段表和偏移量表，能适应SRAM和FPGA芯片内存储器容量的变化，具有查找速度高、更新时间快、存储代价低、易于实现等特点，使用FPGA设计能满足10Gbps端口速率核心路由器环境的要求，使用ASIC设计能满足40Gbps端口速率核心路由器环境的要求。     

基于前驱查找的快速IP路由查找和更新方案

路由器的转发速率通常受限于选择路由的速度,因此路由查找和更新的方法在路由器设计中至关重要。文章提出了一种可硬件实现的快速IP路由查找和更新方法,将IP前缀匹配等价为地址范围搜索,采用B-树结构存储路由表。这种方案对存储要求较低,仅由小容量的片上SRAM和片外DRAM构成。实验表明,该方案在简单硬件支持下就能够达到OC-48的转发要求。     

A cache-based internet protocol address lookup architecture

This paper proposes a novel Internet Protocol (IP) packet forwarding architecture for IP routers. This architecture is comprised of a non-blocking Multizone Pipelined Cache (MPC) and of a hardware-supported IP routing lookup method. The paper also describes a method for expansion-free software lookups. The MPC achieves lower miss rates than those reported in the literature. The MPC uses a two-stage pipeline for a half-prefix/half-full address IP cache that results in lower activity than conventional caches. MPC’s updating technique allows the IP routing lookup mechanism to freely decide when and how to issue update requests. The effective miss penalty of the MPC is reduced by using a small non-blocking buffer. This design caches prefixes but requires significantly less expansion of the routing table than conventional prefix caches. The hardware-based IP lookup mechanism uses a Ternary Content Addressable Memory (TCAM) with a novel Hardware-based Longest Prefix Matching (HLPM) method. HLPM has lower signaling activity in order to process short matching prefixes as compared to alternative designs. HLPM has a simple solution to determine the longest matching prefix and requires a single write for table updates.