期刊文献+

基于前缀扩展的快速路由查找算法 被引量:1

Fast IP-Routing Lookup Algorithm Based on Prefix Expansion
下载PDF
导出
摘要 该文对路由器中的快速路由查找算法进行了研究 .针对路由查找算法在查找速度、算法空间复杂度以及插入和删除表项的难度等方面存在的问题 ,提出了一种快速路由查找算法 .该算法通过构造两级索引表结构来减小路由查找的访存次数以提高查找速度 ;利用前缀扩展的特性并采用特殊的数据结构来构建索引表 ,能支持动态插入、删除和更新路由 ;采用压缩技术对二级索引表进行压缩 ,从而大大减小了路由所需的存储空间 .该算法最多四次访存 ,最少两次访存就完成一次路由查找 .由于采用了压缩方法 ,所需存储空间很小 ,该算法不仅适合于软件实现 ,也适合于硬件实现 .查找速度快、存储空间小并支持动态插入和删除是该算法的主要特点 . This paper proposes a fast IP-routing lookup algorithm based on prefix expansion, which can reduce the memory access times by constructing two levels of index tables. For the index tables, if the length of the prefix is more than sixteen, the first sixteen bits of the prefix is used to construct the first level index table, and the remaining bits of the prefix is used to construct the second index table, otherwise expands the prefix to sixteen bits and constructs the first level index table. Constructing the index tables is based on the characteristics of the prefix expansion, and these characteristics enable this algorithm to add and delete entries dynamically. In order to reduce the memory size of the index tables, this algorithm applies a special technique to compress the second index table, which makes the space of the forwarding table smaller. Special data structures are designed for the index tables, which make it easy to implement this algorithm. Most lookups need only two memory accesses to get the routing information, and a lookup requires no more than four memory accesses. Because this algorithm employs compression to reduce memory size and the process of lookup for the best match address is very simple, it can be implemented not only in software but also in hardware. This algorithm is characterized by fast IP-routing lookup, small memory needs, adding and deleting entries dynamically.
出处 《计算机学报》 EI CSCD 北大核心 2001年第12期1272-1278,共7页 Chinese Journal of Computers
基金 高等学校重点实验室访问学者基金资助
关键词 索引表 INTERNET 快速路由查找算法 路由器 数据结构 Algorithms Internet Network protocols Table lookup
  • 相关文献

参考文献2

  • 1Henry Hong Yi Tzeng,IEEE J Select Areas Commun,1999年,17卷,6期,1067页 被引量:1
  • 2Huang NenFu,IEEE J Select Areas Commun,1999年,17卷,6期,1093页 被引量:1

同被引文献8

引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部