摘要
为了提高IPv6的路由查找效率,根据IPv6路由前缀分布规律和前缀层次关系,提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中,剩下不足的前缀比特由多比特树存储,IPv6路由查找时在无冲突哈希表和多比特树中两级查找。实验表明,该查找算法的平均查找路径数为1.0～1.7,适用于高速的IPv6路由查找。
Based on the analysis of the prefix length distribution and prefix level relationships of the routing table, a new IPv6 route search algorithm based on perfect-Hash table and multibit-trie was proposed to improve the efficiency of the IPv6 address search. The prefixes of the addresses divided into intervals were stored in three Hash tables according to the length of 32, 40 and 48, and the rest bits were stored in muhibit-tries. IPv6 routing adopted a two-stage search. The first stage was in the perfect-Hash table and the second in the muhibit-trie. The experimental results demonstrate that the average search path of the algorithm is 1.0 - 1.7, and it can be applied to the high performance IPv6 route search.
出处
《计算机应用》
CSCD
北大核心
2013年第5期1194-1196,1202,共4页
journal of Computer Applications
基金
国家863计划项目(2012AA012803
2013AA014703)
中国科学院战略性科技先导专项(XDA06030200)
