|
|||||
|
|
| 双TCAM高性能IPv4路由查找算法与实现 | |
| 引用本文： | 王振兴,张彦肖,邬江兴,孙亚民.双TCAM高性能IPv4路由查找算法与实现[J].计算机工程与应用,2004,40(30):124-127. |
| 作者姓名： | 王振兴 张彦肖 邬江兴 孙亚民 |
| 作者单位： | 1. 信息工程大学信息工程学院,郑州,450002;国家数字交换系统工程技术研究中心,郑州,450002;南京理工大学计算机系,南京,210094 2. 信息工程大学信息工程学院,郑州,450002 3. 国家数字交换系统工程技术研究中心,郑州,450002 4. 南京理工大学计算机系,南京,210094 |
| 基金项目： | 国家863高技术研究发展计划重点项目(编号:2001AA121011，2003AA103510)资助课题 |
| 摘 要： | 传统二分算法完成一次IPv4最长前缀匹配需5步搜索,且因存在回溯问题难以硬件实现,而单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,影响表项的更新速度和路由查找流程的连续性。该文提出并以TCAM流水线硬件实现了一种独特对扩展前缀范围的四分搜索算法。仅用2步搜索完成一次IPv4路由查找、转发表不需排序、查找速率高、表项更新快、查表连续性好。满足IPv4核心路由器的双OC-768(40Gbps)端口、48B包的线速转发。 |
| 关 键 词： | IPv4路由查找 四分搜索 快速更新 查表连续性 TCAM流水处理 |
| 文章编号： | 1002-8331-(2004)30-0124-04 |
Dual-TCAM High Performance IPv4 Routing Lookup Algorithm and Implementation |
|
| Wang Zhenxing, Zhang Yanxiao Wu Jiangxing Sun Yamin.Dual-TCAM High Performance IPv4 Routing Lookup Algorithm and Implementation[J].Computer Engineering and Applications,2004,40(30):124-127. | |
| Authors: | Wang Zhenxing Zhang Yanxiao Wu Jiangxing Sun Yamin |
| Affiliation: | Wang Zhenxing1,2,3 Zhang Yanxiao1 Wu Jiangxing2 Sun Yamin31 |
| Abstract: | It needs as more as 5 stages of searches to do once IPv4 routing lookup using traditional bi-search algorithm on prefix length,which is difficult to be implemented with hardware because of retrospect problem.While single-step TCAM schemes demand entries being sorted according to prefix lengths in descending order relative to TCAM addresses.The sorting operations have disadvantageous affections to the entry updating speed and lookup continuity.A novel routing lookup method based on QSPE(Quaternary-Search on Prefix with expansion)algorithm is provided and implemented with TCAM pipeline hardware in this paper.Its outstanding advantages include that only 2 stages of searches needed for once IPv4 routing lookup,no entry sorting is needed,lookup speed is high,entry updating completes fast with pipelining,and lookup continuity is enhanced.It satisfies wire-speed(48B-packet)forwarding of double OC-768(40Gbps)interfaces of IPv4 core routers. |
| Keywords: | IPv4 routing lookup quaternary-search fast update lookup continuity TCAM pipelining |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |