主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
梁志勇,徐恪,吴建平,徐明伟.支持压缩和多下一跳查找的路由查找方案.软件学报,2004,15(4):550-560
支持压缩和多下一跳查找的路由查找方案
An IP Lookup Scheme Supporting Routing Compaction and Multi Next Hops
投稿时间:2003-04-01  修订日期:2003-08-12
DOI:
中文关键词:  路由查找  路由更新  路由压缩  多下一跳  TCAM
英文关键词:routing lookup  routing update  routing compaction  multi next hops  TCAM (ternary content addressable memory)
基金项目: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
作者单位
梁志勇 清华大学,计算机科学与技术系,北京,100084 
徐恪 清华大学,计算机科学与技术系,北京,100084 
吴建平 清华大学,计算机科学与技术系,北京,100084 
徐明伟 清华大学,计算机科学与技术系,北京,100084 
摘要点击次数: 3134
全文下载次数: 3902
中文摘要:
      TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利