|本期目录/Table of Contents|

 多分枝trie树路由查找算法研究 (PDF)

《电子设计工程》[ISSN:1674-6236/CN:61-1477/TN]

期数:
 2010年03期
页码:
 4-6
栏目:
 计算机技术应用
出版日期:
 2010-03-05

文章信息/Info

Title:
 Research of multi－branch trie routing lookup algorithm
作者:
 陈 蹊 ; 赵跃龙
 华南理工大学计算机科学与工程学院，广东广州510006
Author(s):
 CHEN Xi; ZHAO Yue-long
 School of Computer Science and Engineering，South China University of Technology，Guangzhou510006，China
关键词:
 因特网; 路由查找; 最长前缀匹配; trie树
Keywords:
 Internet; routing lookup; the longest prefix match; trie
分类号:
 TP393.2
DOI:
 -
文献标识码:
 A
摘要:
 为了解决路由器报文转发中路由查找速度慢的瓶颈问题，在分析了路由器中广泛使用的各种典型IP路由算法的基础上，提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找，组成一个大的中间结点。在中间结点之间采用多分支步长查询，中间结点的内部使用二进制trie树来表示。仿真结果表明，改进的多分支trie树具有访存次数少，查询速度快，占用存储空间少，更新开销小等特点，并且对IPv4和IPv6地址都可以适用。
Abstract:
 In order to address the bottleneck of transfer packets road in router,after analysing varieties of typical IP routing algorithms in router,this paper presents an improved multi-branchedtrie routing search algorithm.It eliminated the prefix search trie to form a large middle nodes.Between middle nodes used a multi-step branch of inquiry,the internal of the middle node used the binary trie to represent.The simulation results show that the improved multi-branch tree has some advantages such as little times to visit memory,fast query speed,takes up less storage space and updates overhead,etc.,and IPv4both IPv6addresses can be applied.

参考文献/References

 [1]Marc Friedman，AlonLevy，Todd Millstein.Navigational plans for data integration[C].Proc of the16th National Confon Ar-tificial Intelligence（AAAI’99），1999:72-73.
[2]Mcauley A，Francis P.Fast routing table lookup using CAMs[J].Proc.IEEE INFOCOM,1993（3）：1382-1391.
[3]吴彤，杨嗣超，诸鸿文.路由表快速查找算法[J].通信技术，2000（4）：52-59.
[4]刘永锋，杨宗凯.高速路由器中基于树型结构路由查找算法的研究与实现[J].计算机工程与科学，2004，26（1）：77-80.
[5]徐格，吴建平，徐明伟，等.高等计算机网络—体系结构、协议机制、算法设计与路由器技术[M].北京：机械工业出版社，2006.
[6]谭明锋，高蕾，龚正虎.IP路由查找算法研究概述[J].计算机工程与科学，2006，28（6）：87-91.
[7]徐宇锋，李乐民.快速路由查找算法及其实现[J].通信技术，2001（7）：48-52.

备注/Memo

备注/Memo:
 收稿日期：2009-09-16稿件编号：200909054基金项目：国家自然科学基金项目（60573145）；教育部博士点基金项目（200805610019）；广州市科技计划项目（2007J1-C0401）作者简介：陈蹊（1985—），男，广西桂林人，硕士研究生。研究方向：计算机网络与通信，网络存储。
更新日期/Last Update:  2010-03-05