|
|||||
|
|
| 基于无冲突哈希表和多比特树的两级IPv6路由查找算法 | |
| 引用本文： | 杜飞 董治国 苗琳 庹宇鹏. 基于无冲突哈希表和多比特树的两级IPv6路由查找算法[J]. 计算机应用, 2013, 33(5): 1194-1202. DOI: 10.3724/SP.J.1087.2013.01194 |
| 作者姓名： | 杜飞 董治国 苗琳 庹宇鹏 |
| 作者单位： | 1. 中国科学院 信息工程研究所，北京 1000932. 中国核工业集团公司 中国核电工程有限公司，北京 1008403. 国家计算机网络应急技术处理协调中心，北京 100027 |
| 基金项目： | 国家863计划项目(2012AA012803，2013AA014703);中国科学院战略性科技先导专项(XDA06030200) |
| 摘 要： | 为了提高IPv6的路由查找效率，根据IPv6路由前缀分布规律和前缀层次关系，提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中，剩下不足的前缀比特由多比特树存储，IPv6路由查找时在无冲突哈希表和多比特树中两级查找。实验表明，该查找算法的平均查找路径数为1.0~1.7，适用于高速的IPv6路由查找。 |
| 关 键 词： | IPv6 路由前缀 无冲突哈希表 多比特树 |
| 收稿时间： | 2012-11-06 |
| 修稿时间： | 2012-12-18 |
Two-stage IPv6 route search algorithm based on perfect-Hash table and multibit-trie |
|
| Du Fei DONG Zhiguo MIAO Lin TUO YupengYupeng. Two-stage IPv6 route search algorithm based on perfect-Hash table and multibit-trie[J]. Journal of Computer Applications, 2013, 33(5): 1194-1202. DOI: 10.3724/SP.J.1087.2013.01194 | |
| Authors: | Du Fei DONG Zhiguo MIAO Lin TUO YupengYupeng |
| Affiliation: | 1. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China 2. China Nuclear Power Engineering Corporation Limited, China National Nuclear Corporation, Beijing 100840, China 3. National Computer Network Emergency Response Technical Team Coordination Center of China, Beijing 100027, China 4. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China |
| Abstract: | 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 multibit-tries. IPv6 routing adopted a two-stage search. The first stage was in the perfect-Hash table and the second in the multibit-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. |
| Keywords: | IPv6 routing prefix perfect-Hash table multibit-trie |
| 点击此处可从《计算机应用》浏览原始摘要信息 | |
| 点击此处可从《计算机应用》下载全文 | |