基于无冲突哈希表和多比特树的两级IPv6路由查找算法

doi:10.3724/SP.J.1087.2013.01194

计算机应用 ›› 2013, Vol. 33 ›› Issue (05): 1194-1202.DOI: 10.3724/SP.J.1087.2013.01194

基于无冲突哈希表和多比特树的两级IPv6路由查找算法

杜飞¹,董治国²,苗琳³,庹宇鹏¹

1. 中国科学院信息工程研究所，北京 100093
2. 中国核工业集团公司中国核电工程有限公司，北京 100840
3. 国家计算机网络应急技术处理协调中心，北京 100027

收稿日期:2012-11-06 修回日期:2012-12-18 出版日期:2013-05-01 发布日期:2013-05-08
通讯作者: 庹宇鹏
作者简介:杜飞(1982-)，男，山西太原人，工程师，硕士，CCF会员，主要研究方向：网络与信息安全；董治国(1972-)，男，吉林农安人，高级工程师，主要研究方向：核电DCS系统级设备；苗琳(1983-)，女，北京人，工程师，硕士，主要研究方向：网络与信息安全；庹宇鹏(1984-)，男，河北廊坊人，助理研究员，博士研究生，CCF会员，主要研究方向：网络协议识别与异常检测
基金资助:
国家863计划项目(2012AA012803，2013AA014703);中国科学院战略性科技先导专项(XDA06030200)

Two-stage IPv6 route search algorithm based on perfect-Hash table and multibit-trie

Du Fei¹,⁴,DONG Zhiguo²,MIAO Lin³,TUO YupengYupeng¹,⁴

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

Received:2012-11-06 Revised:2012-12-18 Online:2013-05-08 Published:2013-05-01
Contact: TUO YupengYupeng
Supported by:
Strategic Priority Research Program

摘要/Abstract

摘要： 为了提高IPv6的路由查找效率，根据IPv6路由前缀分布规律和前缀层次关系，提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中，剩下不足的前缀比特由多比特树存储，IPv6路由查找时在无冲突哈希表和多比特树中两级查找。实验表明，该查找算法的平均查找路径数为1.0~1.7，适用于高速的IPv6路由查找。

关键词: IPv6, 路由前缀, 无冲突哈希表, 多比特树

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.

Key words: IPv6, routing prefix, perfect-Hash table, multibit-trie

中图分类号:

TP393.03

杜飞董治国苗琳庹宇鹏. 基于无冲突哈希表和多比特树的两级IPv6路由查找算法[J]. 计算机应用, 2013, 33(05): 1194-1202.

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(05): 1194-1202.

[1]	孔亚洲, 张连成, 王振兴. 基于滑动时间窗口的IPv6地址跳变主动防御模型[J]. 计算机应用, 2018, 38(7): 1936-1940.
[2]	仵惠婷, 王振兴, 张连成, 孔亚洲. IMTP——一种MIPv6身份与移动轨迹隐私保护机制[J]. 计算机应用, 2016, 36(8): 2236-2240.
[3]	韩国梁, 盛茂家, 包丛笑, 李星. IPv4网络与IPv6互联网的无状态通信机制[J]. 计算机应用, 2015, 35(8): 2113-2117.
[4]	陈旖, 许力, 张美平. 适用于大规模无线传感器网的流量优化系统设计[J]. 计算机应用, 2015, 35(4): 905-909.
[5]	孙晓林张建洋贾晓. 层次移动IPv6域内切换优化方案[J]. 计算机应用, 2014, 34(2): 338-340.
[6]	李振军柳兴. 基于Delaunay三角剖分的FMIPv6快速切换机制[J]. 计算机应用, 2013, 33(10): 2707-2710.
[7]	孔繁杰张奇支饶亮陈源. NEMO网络在PMIPv6中的实现及快速切换方案[J]. 计算机应用, 2013, 33(06): 1495-1504.
[8]	朱田田野马迪毛伟. 基于包验证的面向IPv6翻译机制的IP追溯方法[J]. 计算机应用, 2013, 33(04): 926-930.
[9]	邓亚平周美红. 基于多层混合结构的IPv6路由表查找算法[J]. 计算机应用, 2013, 33(02): 385-389.
[10]	周莲英王亮. 基于路由优化分组通信技术的改进型层次移动IPv6[J]. 计算机应用, 2012, 32(06): 1491-1494.
[11]	邓亚平陈中元. 快速层次移动IPv6的域间移动管理[J]. 计算机应用, 2012, 32(05): 1236-1239.
[12]	张一芳张奇支. 基于快速切换的代理移动IPv6路由优化方案[J]. 计算机应用, 2012, 32(02): 335-339.
[13]	吕莎莎孙建伟贾军营于波. 基于群集移动节点的切换算法[J]. 计算机应用, 2011, 31(12): 3219-3222.
[14]	闫巧宁土文. 基于确定线性网络编码的IPv6追踪[J]. 计算机应用, 2011, 31(09): 2352-2355.
[15]	陈俊陈孝威. 移动IPv4/IPv6的虚拟机迁移过渡框架[J]. 计算机应用, 2011, 31(05): 1180-1183.

基于无冲突哈希表和多比特树的两级IPv6路由查找算法

Two-stage IPv6 route search algorithm based on perfect-Hash table and multibit-trie

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics