| 摘要: |
| TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中. |
| 关键词: 路由查找 路由更新 路由压缩 多下一跳 TCAM |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.90104002 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant Nos.2001AA121013, 2001AA112132 (国家高技术研究发展计划(863)); the Key Science and Technology P |
|
| An IP Lookup Scheme Supporting Routing Compaction and Multi Next Hops |
|
LIANG Zhi-Yong,XU Ke,WU Jian-Ping,XU Ming-Wei
|
| Abstract: |
| TCAM (ternary content addressable memory) is a popular device for fast routing lookup. The advantages of TCAM are high lookup speed and simple operation. However, TCAM still has three explicit disadvantages: high cost, high power consumption and complex update. For load balancing and policy routing, routers have to hold considerable routes with multi next hops. This paper proposes a fast IP lookup scheme that is based on TCAM and supports routing lookup for multi next hops. With two index tables, the scheme can store and retrieve the routes with multi next hops. To improve the TCAM update, a fast update algorithm—N-subspace algorithm that can approximately reach the O(1) complexity for current Internet routing tables is also proposed. To decrease cost and power consumption, an efficient routing compaction method is also applied, which is based on the Trie structure and can reduce 20% routes for Internet routing tables. Also, the scheme can scale to IPv6 easily. |
| Key words: routing lookup routing update routing compaction multi next hops TCAM (ternary content addressable memory) |
