摘要
为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型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.
出处
《电子设计工程》
2010年第3期4-5,8,共3页
Electronic Design Engineering
基金
国家自然科学基金项目(60573145)
教育部博士点基金项目(200805610019)
广州市科技计划项目(2007J1-C0401)
