文档介绍：第卷第期电子设计工程年月
18 3 2010 3
Electronic Design Engineering Mar. 2010
多分枝 trie 树路由查找算法研究
陈蹊赵跃龙
,
华南理工大学计算机科学与工程学院广东广州
( , 510006)
摘要为了解决路由器报文转发中路由查找速度慢的瓶颈问题在分析了路由器中广泛使用的各种典型路由算法
: , IP
的基础上提出一种基于多分枝树的改进路由查找算法在多分枝树中取消前缀查找组成一个大的中间结
, trie 。 trie ,
点在中间结点之间采用多分支步长查询中间结点的内部使用二进制树来表示仿真结果表明改进的多分支
。, trie 。,
树具有访存次数少查询速度快占用存储空间少更新开销小等特点并且对和地址都可以适用
trie , , , , IPv4 IPv6 。
关键词因特网路由查找最长前缀匹配树
: ; ; ; trie
中图分类号文献标识码文章编号:
: :A 1674-6236(2010)03-0004-02
Research of multi-branch trie routing lookup algorithm
CHEN Xi, ZHAO Yue-long
(School puter Science and Engineering, South China University of Technology, Guangzhou 510006, China)
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 eliminated the prefix
search trie to form a large middle middle nodes used a multi-step branch of inquiry,the internal of the
middle node used the binary trie to 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
IPv4 both IPv6 addresses can be applied.
Key words:; routing lookup; the longest prefix ma