四-二分搜索高性能IPv4路由查找算法与实现

传统二分算法完成一次IPv4最长前缀匹配需5步搜索,且因存在回溯问题难以硬件实现,而单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,影响表项的更新速度和路由查找流程的连续性。该文提出并以TCAM流水线硬件实现了一种独特的对前缀范围的四．二分搜索算法。仅用3步搜索完成一次IPv4路由查找、转发表不需排序、查找速率高、表项更新快、查表连续性好。满足了IPv4核心路由器的双OC-768(40Gbps)端口、48B包的线速转发。     

快速更新IPv4/IPv6双栈路由查找算法与实现

IPv4/IPv6双栈核心路由器需要一体化高效路由查找．但常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列，这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性．提出并实现了一种独特的对前缀范围对分搜索的IPv4／IPv6双栈一体化多步TCAM流水查找方法．突出特点是转发表不需排序、查找速率高、表项更新快、查表连续性好．可满足IPv4／IPv6双协议栈核心路由器OC-768（40Gbps）端口、48B包的线速转发．     

基于前缀范围对分搜索的高性能路由查找

高端路由器路由查找大多采用单步TCAM方案．要求转发表的存储必须按前缀长度相对地址降序排列，这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性．与已有对前缀长度的搜索不同，该文提出一种独特的基于前缀范围对分搜索的路由查找算法．并以多步TCAM实现流水查找．突出特点是转发表无需排序，表项更新快，查找速率高且连续性好。可满足IPv4／IPv6核心路由器OC-768(40Gbps)端口的线速率转发．     

TCAM路由更新的硬件优化

现代核心路由器对查找速率、表项更新速度、查找表容量等提出越来越高的要求。目前工业厂商大多采用基于TCAM(三态内容关联存储器)的解决方案。TCAM最大特点是查找速度快,但其更新算法会浪费很大的存储空间。针对这个问题该文提出一种利用FPGA提供硬件支持的路由更新方法,增加新表项时,只需对新增表项进行一次预处理,转发表无需按前缀长度排序,消除了预留空闲表项造成的存储空间浪费。     

基于TCAM的二级转发表管理方案

目前高性能路由器的查找方案采用基于三重内容可寻址存储器(TCAM)的硬件查找。路由查找的最长前缀匹配要求使得TCAM的表项更新复杂。该文针对当前转发表管理方案在带突发情况下的不足,提出一种基于TCAM二级转发表管理方案,并对该方案进行了计算机仿真研究,仿真结果表明该方案在突发的情况下仍能保证转发系统稳定工作。     

TCAM表项管理算法研究

为了克服传统的软件路由查找机制的瓶颈,高速路由器目前的查表方案是基于TCAM的硬件路由查找.由于路由查找的最长前缀匹配要求,TCAM要解决路由表项的高效存储和管理问题.本文讨论了目前的基于TCAM的表项管理算法,对当前研究的新进展进行了重点分析和比较,为进一步的研究提出了新的思路.在863重大课题"可扩展到T比特的高性能IPv4/v6路由器基础平台及实验系统"中,得到很好的应用.     

TCAM表项管理算法研究

为了克服传统的软件路由查找机制的瓶颈,高速路由器目前的查表方案是基于TCAM的硬件路由查找。由于路由查找的最长前缀匹配要求,TCAM要解决路由表项的高效存储和管理问题。本文讨论了目前的基于TCAM的表项管理算法,对当前研究的新进展进行了重点分析和比较,为进一步的研究提出了新的思路。在863重大课题“可扩展到T比特的高性能IPv4/v6路由器基础平台及实验系统"中,得到很好的应用。     

TCAM路由表项管理算法优化研究

TCAM(Ternary Content-Addressable Memory)能够很好的完成最长前缀匹配,实现快速路由查找和分组转发,但是其对路由表项的有序性要求使得表项管理比较复杂.在讨论已有TCAM表项管理算法的基础上,通过分析前缀表项的统计分布特性,对路由表的空间分配进行了优化,同时引入新的基于前缀块指针管理策略,提出了一种改进的表项管理方法,提高了路由表更新效率.     

IPv6的快速路由查找算法研究

TCAM被广泛用于执行快速路由查找,不管前缀的数量和长度,它能在极短时间内解决最佳前缀问题。与基于软件解决方法相比较,TCAM能提供持续吞吐量和简单系统体系,这对IPv6路由查找来说是很有吸引力的。然而,它也有一些缺点,例如入口数量有限,价格昂贵和能源消耗。因此,本文提出一种有效、能减少所需TCAM的算法,该算法通过增加微DRAM来消除98％的TCAM入口。实验证明,该算法效果良好,可以大大提高IPv6路由查找性能。     

一种快速IPv6路由查找方案

提出了一个可硬件实现的基于分段的快速IPv6路由查找方案.该方案支持快速的IP地址查找,并能有效地对路由前缀进行插入和删除操作.方案采用基于比特位置区分的压缩算法,与其它的 IPv6 路由查找方案相比较,所需存储器空间小,路由查找的平均时间少.如果采用SRAM流水线查找,可实现 125×106次/秒的查找速度.由于缺少实际的 IPv6路由前缀,该文生成了模拟路由前缀数据库.仿真试验结果表明:文章提出的方案具有合理的查找时间、空间和更新复杂度,容易硬件实现.     

An efficient IP address lookup algorithm based on a small balanced tree using entry reduction

Due to a tremendous increase in internet traffic, backbone routers must have the capability to forward massive incoming packets at several gigabits per second. IP address lookup is one of the most challenging tasks for high-speed packet forwarding. Some high-end routers have been implemented with hardware parallelism using ternary content addressable memory (TCAM). However, TCAM is much more expensive in terms of circuit complexity as well as power consumption. Therefore, efficient algorithmic solutions are essentially required to be implemented using network processors as low cost solutions.Among the state-of-the-art algorithms for IP address lookup, a binary search based on a balanced tree is effective in providing a low-cost solution. In order to construct a balanced search tree, the prefixes with the nesting relationship should be converted into completely disjointed prefixes. A leaf-pushing technique is very useful to eliminate the nesting relationship among prefixes [V. Srinivasan, G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems 17 (1) (1999) 1-40]. However, it creates duplicate prefixes, thus expanding the search tree.This paper proposes an efficient IP address lookup algorithm based on a small balanced tree using entry reduction. The leaf-pushing technique is used for creating the completely disjointed entries. In the leaf-pushed prefixes, there are numerous pairs of adjacent prefixes with similarities in prefix strings and output ports. The number of entries can be significantly reduced by the use of a new entry reduction method which merges pairs with these similar prefixes. After sorting the reduced disjointed entries, a small balanced tree is constructed with a very small node size. Based on this small balanced tree, a native binary search can be effectively used in address lookup issue. In addition, we propose a new multi-way search algorithm to improve a binary search for IPv4 address lookup. As a result, the proposed algorithms offer excellent lookup performance along with reduced memory requirements. Besides, these provide good scalability for large amounts of routing data and for the address migration toward IPv6. Using both various IPv4 and IPv6 routing data, the performance evaluation results demonstrate that the proposed algorithms have better performance in terms of lookup speed, memory requirement and scalability for the growth of entries and IPv6, as compared with other algorithms based on a binary search.     

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

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

快速IPv6分段查找及其硬件实现

提出一种可硬件实现的快速IPv6查找算法,采用基于内容可寻址存储器CAM的分段查找机制,用流水线实现,每个周期可输出一次查找结果,所需存储开销较小。在Xilinx Virtex-6 FPGA开发板用150×1 024项IPv6前缀测试表明,查找速度可达597 Mp/s（Million packet/s）,最坏需要2次存储器访问,更新最坏需要50 μs,仅需20.07 MB的RAM和258 KB的CAM存储开销。     

基于Hash和CAM的IPv6路由查找算法

分析实际网络中的IPv6前缀分布规律与增长趋势,提出一种基于Hash和内容可寻址存储器(CAM)的IPv6路由查找算法。将长度能被8整除的前缀存储在8个Hash表中,发生Hash冲突的前缀存储在CAM中,长度不能被8整除的前缀按照一定的组织方式存储在随机存取存储器中。分析结果表明,该算法具有较高的存储利用率、查找速率及更新速率,并且易于扩展和硬件实现。     

兼容IPv4和IPv6的高速路由设计

提出一种兼容IPv4和IPv6报文高速路由查找方案，方案基于TCAM技术，同时对TCAM路由表更新算法进行比较，最后采用松散前缀顺序约束算法实现TCAM路由表的更新，并在网络处理器原型设计中得到应用。方案可以满足10Gbps速率IP报文线速转发的要求。     

Leaf-TCAM:一种并行IP路由查找方法及性能分析

分析了互联网路由表和路由更新的特征,提出了一种基于叶子节点进行路由表分区的并行IP路由查找方法Leaf-TCAM,分区子表按照流量特征在K个TCAM芯片中进行均衡分布。分析表明,该路由查找方法在引入0.1*(K-1)冗余的前提下具有K-1倍加速因子。该方法无需进行前缀扩展,90%以上的路由前缀无需排序,可以采用随机更新;同时还具有分区均匀、分区溢出代价小等特点,而功耗只有传统单片方案的12%。     

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

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

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