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

Research of multi-branch trie routing lookup algorithm

作　　者：陈蹊[1] 赵跃龙[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510006

出　　处：《电子设计工程》2010年第3期4-5,8,共3页Electronic Design Engineering

基　　金：国家自然科学基金项目(60573145);教育部博士点基金项目(200805610019);广州市科技计划项目(2007J1-C0401)

摘　　要：为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP路由算法的基础上,提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找,组成一个大的中间结点。在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示。仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用。In order to address the bottleneck of transfer packets road in router,after analysing varieties of typical IP muting algorithms in router, this paper presents an improved muhi-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 IPv4 both IPv6 addresses can be applied.

关 键 词：因特网 路由查找 最长前缀匹配 TRIE树 

分 类 号：TP393.2[自动化与计算机技术—计算机应用技术]