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

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

双TCAM高性能IPv4路由查找算法与实现

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

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

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

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

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

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

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

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

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

一种兼容IPv4和IPv6的快速路由查找算法

文中提出了一种基于DAG(Directed Acyclic Graph)的路由查找算法，兼容IPv4和IPv6，单层使用基于前缀长度的二分查找，可以用流水线方式硬件实现，最坏情况下支持OC768线速。     

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

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

一种新的二分路由查找方法

分析路由表前缀间的覆盖关系特征,证明了前缀覆盖级别集合符合二分查找特性,提出一种基于前缀覆盖级别的二分路由查找算法,和传统基于前缀长度或者前缀值的线性或者二分查找算法相比,在查找性能、路由更新和存储空间方面具有优势,本方法可以在O(log2max_level+1)个TCAM时钟周期内完成1次路由查找,其中max_level为最大的前缀覆盖级别,目前max_level不超过7;本方法无需前缀扩展和排序,支持路由增量更新;另外,传统TCAM路由查找相比,可以节省功耗约50%.     

一种快速IPv6路由查找方案

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

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

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

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

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

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

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

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

WSN中改进的IPv6路由查找算法

针对无线传感器网络(WSN)中的全局单播地址,提出一种IPv6快速路由查找机制。利用布鲁姆过滤器作为存储结构,以合适的存储方法降低错误率,采用最长前缀匹配算法合理分配前缀,以减少静态随机存取存储器的数量,降低成本。实验结果表明,利用该算法可以减少每一次查找的散列探头,从而提高路由表的查找速度,改善WSN的性能。     

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

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

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

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