摘要: |
常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性。本文提出并实现了一种独特的对前缀范围对分搜索的IPv4五步TCAM流水查找方法。突出特点是转发表不需排序,查找速率高,表覆更新快,查表连续性好,可满足IPv4核心路由器双OC-768(40Gbps)端口、48B包的线速转发。 |
关键词: 核心路由器 IP路由查找 对分搜索 快速更新 查表连续性 TCAM流水处理 |
DOI:10.3969/j.issn.1001-893X. |
投稿时间:2004-10-14修订日期:2005-03-22 |
基金项目:国家高技术研究发展计划(863计划) |
|
TCAM Fast-Update High-Speed Routing Lookup Algorithm and its Implementation |
|
() |
Abstract: |
Single-step TCAM schemes used in core routers demand entries must be sorted according to prefix lengths in descending order relative to TCAM addresses.The sorting operations related to addresses have disadvantageous effects on the entry updating speed and lookup continuity.A novel routing lookup method based on BSPR(Bi-search on Prefix Range) is provided and implemented in this paper,which uses 5-step TCAMs pipelining based on bi-search on prefix range.Its outstanding advantages include that 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 dual OC-768(40Gbps) interfaces of IPv4 core routers. |
Key words: core router IP routing lookup bi - search fast update lookup continuity TCAM - pipelining |