基于三级索引和Trie的IPv6路由查找算法研究  

The Study on IPv6 Routing Lookup Algorithm Based on Three-level Index and Multi-bit Trie

作　　者：刘阳[1] 

机构地区：[1]滨州学院信息工程系,山东滨州256603

出　　处：《山东农业大学学报（自然科学版）》2015年第4期607-612,共6页Journal of Shandong Agricultural University：Natural Science Edition

基　　金：滨州学院"青年人才创新工程"科研基金(BZXYQNLG200903);滨州市软科学研究计划项目(2014RKX18)

摘　　要：Internet的迅速发展使得骨干网核心路由器转发分组的数量呈指数级增长,快速的IP路由查找算法是实现高速分组转发的关键。IPv6的应用,使得路由查找算法要适应IPv6地址的特点。本文分析了典型的基于Trie的路由查找算法,总结各种算法的优缺点。结合IPv6地址特征和骨干路由器路由表地址前缀的分布规律,提出了一种基于三级索引表和多比特Trie的快速IPv6路由查找算法。与其他同类算法相比较,该算法易于实现,并且具有较快的查找和更新速度,较低的存储空间。The rapid development of Internet facilitates the exponential growth in the number of forwarded packets of core router for backbone network and the rapid IP routing lookup algorithm is a key for achieving the high-speed packet forwarding. The application of IPv6 requires the routing lookup algorithm to adapt to the characteristics of IPv6 address. This paper analyzed the typical routing lookup algorithm based on Trie and summarized the advantages and disadvantages of various algorithms. Combining the characteristics of IPv6 address and the distribution laws of address prefixes in the routing table of backbone router, this paper proposed a rapid IPv6 routing lookup algorithm based on the three-level index table and the multi-bit Trie. It was easier to be achieved a faster speed in lookup and updating and required a smaller storage space comparing with other similar algorithms.

关 键 词：索引表 多比特Trie 路由查找 IPV6 

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