首页 | 官方网站   微博 | 高级检索  
     

一种基于范围表示B树的大容量IPv6路由查表算法
引用本文:谭明锋,龚正虎,孙志刚.一种基于范围表示B树的大容量IPv6路由查表算法[J].国防科技大学学报,2005,27(5):18-24.
作者姓名:谭明锋  龚正虎  孙志刚
作者单位:国防科技大学,计算机学院,湖南,长沙,410073
基金项目:国家自然科学基金项目(90104001),国家重点基础研究发展计划项目(2003CB314802),国家863高技术研究发展计划基金项目(2003AA115130)
摘    要:IPv6具有巨大的地址空间,未来要面对的将会是海量IPv6路由表,而且128位的IPv6地址比IPv4需要更多的访存数。算法针对IPv6路由查找问题中的这两个难点,提出利用B树高度较低的优良性质,将前缀转化为范围表保存在B树中,并在结点内部利用分段范围比较树算法来减少访存次数和空间耗费。理论分析和实验表明,该算法能够以很好的性能支持IPv6海量路由表的查找。

关 键 词:IPv6  路由查表  B树  大容量路由表  范围表示
文章编号:1001-2486(2005)05-0018-07
收稿时间:2005/5/20 0:00:00
修稿时间:2005年5月20日

An IPv6 Routing Lookup Algorithm for Large Route Tables Based on Range Representation B-tree
TAN Mingfeng,GONG Zhenghu and SUN Zhigang.An IPv6 Routing Lookup Algorithm for Large Route Tables Based on Range Representation B-tree[J].Journal of National University of Defense Technology,2005,27(5):18-24.
Authors:TAN Mingfeng  GONG Zhenghu and SUN Zhigang
Affiliation:College of Computer, National Univ. of Defense Technology, Changsha 410073, China;College of Computer, National Univ. of Defense Technology, Changsha 410073, China;College of Computer, National Univ. of Defense Technology, Changsha 410073, China
Abstract:The IPv6 routing lookup algorithms need to process huge route tables in the future owing to the huge address space of IPv6,and each lookup needs more memory accesses than IPv4 algorithms because of the 128 bits address.To solve these two difficult problems,this algorithm converts the prefix into ranges and stores them in a B-tree,then uses range fragment tree in the nodes to reduce the memory access and the storage requirement.Theoretical analysis and the experimental results indicate that the algorithm can support the high performance lookup for huge IPv6 route tables.
Keywords:IPv6  routing lookup  B-tree  large route table  range representation
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《国防科技大学学报》浏览原始摘要信息
点击此处可从《国防科技大学学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号