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

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

基于TCAM技术的高速路由查找方案

基于TCAM技术提出一个高速路由查找方案。该方案可以达到每秒钟100M次的查找速度，满足OC48和OC192接口的线速转发要求。方案使用了索引表和映射表的二级结构存储路由的下一跳信息，大大减小了存储空间，同时对IPv6具有很好的扩展性。对TCAM的路由更新问题进行了讨论，提出一个最坏情况下O(W／2)的更新算法(形为前缀长度集合的数目)，有效地提高了TCAM的更新性能。     

一种基于Trie的IPv6路由查找方案

随着Internet的迅猛发展,IPv6技术必将成为主流.于是,如何高效地在路由表中查找匹配128位IPv6地址,成为了IPv6 技术发展的一大制约因素.经大量研究表明,Trie数据结构是实现高速路由查找和报文转发的关键.结合IPv6的地址结构特点,设计出基于Trie数据结构的查找算法,提高了路由查找效率以及报文转发速度.     

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

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

IPv6无线传感器网络低功耗路由算法

为满足IPv6无线传感器网络低功耗的要求,采用适配层路由,在LOAD路由协议基础上提出一种简化的按需式路由算法。本算法采用精简的路由控制报文、路由表和路由请求表,简化了路由发现过程,优化了路由维护机制。仿真实验表明,该算法能有效的降低IPv6无线传感器网络的功耗。     

AdpCAM：基于TCAM的低功耗IP查表算法*

非对称前缀分布算法（AdpCAM）是一个新颖的降低TCAM功耗的解决方案。该算法在保证TCAM有较高利用率的前提下,有效地降低了功率消耗,并将其限制在可预知的范围内。这种算法支持路由表的快速更新。仿真和应用证明了该算法的可行性和实用性。     

实现IPv6数据包分类的算法研究

三重可寻址内存（Ternary Content Addressable Memory,TCAM）能提供持续吞吐量和单一系统结构,这非常有利于实现包分类,特别是对将来基于IPv6的网络尤其如此。但是它也有缺点,比如路径有限、价格昂贵和电源消耗。为此提出了一种有效算法,对可寻址端口地址加密来减少需要的TCAM。该新方案能够将现实世界IPv6路由表的128位前缀加密成11位,并且仍然保留无类域间路由的属性。     

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

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

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

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

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

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

四-二分搜索高性能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包的线速转发．     

基于双优先级的IPv4单播查表解决方法

针对大规模接入汇聚路由器IPv4单播报文的多表查找问题,结合对TCAM＋SRAM查表技术特点的分析,提出了一种基于双优先级的IPv4单播查表解决方法,并对其中的最长匹配表项快速更新需求设计了一种预留表项空间的改进型选择移动算法。测试结果表明该方法能有效地解决IPv4单播报文的多表查找难题,提高表项的更新速度,节省FPGA资源,提高转发引擎的效率。     

IPv4与IPv6头部之比较

传统的互联网协议IPv4协议存在地址空间匮乏、路由效率不高、安全性差、对移动性支持不好等缺点,严重阻碍了Internet的发展,下一代互联网协议IPv6彻底解决IPv4上述难题。     

基于IPv4网络的两种IPv6隧道传输方法

配置型隧道传输方法及自动型隧道传输方法是实现ＩＰｖ４基础网络设施向ＩＰｖ６网络迁移的两种有效方法。讨论了隧道位置、两类ＩＰｖ６地址,以及配置型隧道和自动型隧道的传输机制。此外,还详细提供了使用上述隧道传输技术的ＩＰｖ６数据报转发算法。     

IPv6相关路由算法技术的研究

随着Internet的普及,IPv4技术已经不能适应这种高速发展的要求,相应的路由器技术也需要进行改进。为了更好地适应全球一体化进程的发展,推进Internet技术在世界范围内的广泛传播与应用,路由器所使用路由算法的性能必须得到提高。文中阐述了现有常用的路由算法并对其进行分析和对比,介绍了IPv6协议的优势,并分析了现阶段IPv6路由器的关键技术及其实现方案。通过分析表明,IPv6路由器相关技术更好地促进了未来Internet的发展,使得Internet更加安全、快速与可靠。     

A high-throughput and high-capacity IPv6 routing lookup system

With the growing number of routing entries, IP routing lookup has become the major performance bottleneck in backbone routers. In this paper, a complete hardware-based routing lookup system is proposed to achieve high-throughput and high-capacity for IPv6. The proposed system is a cache-centric, hash-based architecture that contains a routing lookup application specific integrated circuit (ASIC) and a memory set. A hash function is used to reduce lookup time for the routing table and ternary content addressable memory (TCAM) effectively resolves the collision problem. The gate count of the ASIC, excluding the binary content addressable memory (BCAM), is about 5306 gates, using an in-house 0.18 μm CMOS single-poly six-metal standard cell library. The results of post-layout simulations show that the ASIC operates in 3.6 ns so that the routing lookup system approaches 260 Mega lookups per second (Mlps), which is sufficient for 100 Gbps networks. The memory density is good, with each routing entry requiring only 64 bits. Moreover, the routing table only needs 10.24 KB on-chip BCAM, 20.04 KB off-chip TCAM and 29.29 MB DRAM for 3.6 M routing entries in the proposed system.     

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