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

第18卷第3期 电子设计工程 2010年3月 Electronic Mar．2010 V01．18 No．3 DesignEngineering 多分枝trie树路由查找算法研究 陈蹊．赵跃龙 (华南理工大学计算机科学与工程学院，广东广州510006) 摘要：为了解决路由器报文转发中路由查找速度慢的瓶颈问题．在分析了路由器中广泛使用的各种典型m路由算法 的基础上，提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀壹找。组成一个大的中间结 点。在中间结点之间采用多分支步长查询，中间结点的内部使用二进制trie树来表示。仿真结果表明。改进的多分支 trie树具有访存次数少，查询速度快，占用存储空问少。更新开销小等特点，并且对IPv4和IPv6地址都可以适用。 关键词：因特网；路由查找；最长前缀匹配；trie树 中围分类号：TP393．2 文献标识码：A 文章编号：167舢-6236(2010)03-4)004—02 Researchof multi-branchtrie routinglookupalgorithm CHEN Xi，ZHAO Yue-long (School Scienceond China 510006，China) ofComputer Engineering，SouthUnivers蚵ofTechnology，Guang：hou Abstract：Inordertoaddressthebottleneckoftransfer roadinrouter,after varietiesof IP packets analysing typicalmuting inrouter,this an multi—branchedtriesearch eliminatedthe algorithms paperpresentsimproved muting algorithm．It prefix searchtrietoforma middlenodes．Betweenmiddlenodesuseda branchof internalofthe large multi·step inquiry,the middlenodeusedthe tileto simulationresultsshowthatthe multi·branchtreehassome binary represent．The improved suchaslittletimestovisit less and overhead，etc．，and advantages memory,fastqueryspeed，takesup storagespaceupdates IPv4bothIPv6addressescanbe applied． Keywords：Internet；routinglookup；thelongestp陀敝match；trie 当前。因特网的规模、链路速度、带宽、流量等都呈指数 个表项的空间。因此，CAM存储空间