###
DOI:
Journal of Software:2004.15(4):550-560

支持压缩和多下一跳查找的路由查找方案
梁志勇,徐恪,吴建平,徐明伟
(清华大学,计算机科学与技术系,北京,100084)
An IP Lookup Scheme Supporting Routing Compaction and Multi Next Hops
LIANG Zhi-Yong,XU Ke,WU Jian-Ping,XU Ming-Wei
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2971   Download 3824
Received:April 01, 2003    Revised:August 12, 2003
> 中文摘要: TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中.
中文关键词: 路由查找  路由更新  路由压缩  多下一跳  TCAM
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.
文章编号:     中图分类号:    文献标志码:
基金项目: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 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
Foundation items:
Reference text:

梁志勇,徐恪,吴建平,徐明伟.支持压缩和多下一跳查找的路由查找方案.软件学报,2004,15(4):550-560

LIANG Zhi-Yong,XU Ke,WU Jian-Ping,XU Ming-Wei.An IP Lookup Scheme Supporting Routing Compaction and Multi Next Hops.Journal of Software,2004,15(4):550-560