动态快速路由查找算法

2002年第4卷第7期

摘要

关键词

图片

参考文献

相关研究

回顶部

《中国工程科学》 >> 2002年第4卷第7期

动态快速路由查找算法

电信科学技术研究院，北京 100083

收稿日期： 2001-10-11 修回日期： 2002-01-15 发布日期： 2002-07-20

HTML78 PDF 6 收藏 0

摘要

给出了动态快速路由查找算法（DFR）的原理和实现。该算法采用特殊的数据结构来构建索引表，能支持动态插入、删除和更新路由；DFR算法最多4次访存，最少2次访存，就能找到完整的路由信息。该算法不仅适用于软件实现，而且由于查找简单，也适合于硬件实现。

关键词

前缀扩展 ; DFR ; 路由 ; 路由查找

图片

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献

[ 1 ] NilssonS , KarlssonG .IP addresslookupusingLC Tries[J].IEEEJournalonSelectedAreasinCommunications, 1999, 17 (6) :1083～1092

[ 2 ] HenryHongyi, Tzeng.Onfastaddress lookupalgorithms[J].IEEEJournalonSelectedAreasinCommunications, 1999, 17 (6) :1067～1082

[ 3 ] HuangNenfu, ZhaoShiming.AnovelIP routinglookupschemeandhardwarearchitectureformultigigabitswitchingrouters[J].IEEEJournalonSeletedAreasinCommunications, 1999, 17 (6) :1093～1104

[ 4 ] GuptaP , LinS , McKeownM .Routinglookupsinhardwareatmemoryaccessspeeds[A ].ProcIEEEINFOCOM’98[C], Session10B 1, SanFrancisco, CA , 1998.1240～1247