基于前缀区间集合的IPv6路由查找算法

doi:10.3969/j.issn.1000-436X.2013.06.004

通信学报 ›› 2013, Vol. 34 ›› Issue (6): 29-37.doi: 10.3969/j.issn.1000-436X.2013.06.004

基于前缀区间集合的IPv6路由查找算法

崔宇,田志宏,张宏莉,方滨兴

哈尔滨工业大学网络与信息安全技术研究中心，黑龙江哈尔滨 150001

出版日期:2013-06-25 发布日期:2017-07-20
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家自然科学基金资助项目;）国家科技支撑计划基金资助项目

Binary search on range of IPv6 prefix sets

Yu CUI,Zhi-hong TIAN,GHong-li ZHAN,Bin-xing FANG

School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China

Online:2013-06-25 Published:2017-07-20
Supported by:
The National Basic Research Program of China (973 Program);The National High TechnologyResearch and Development Program of China (863 Program) (;The National High TechnologyResearch and Development Program of China (863 Program) (;The National High TechnologyResearch and Development Program of China (863 Program);The NationalNatural Science Foundation of China;The National Key Technology R＆D Program of China

摘要/Abstract

摘要：

对IPv6相关的通用型与特定型路由算法进行了分析，重点研究了以BSR为基础的IPv6路由算法在查找和更新时的不平衡问题，提出了基于前缀区间集合的IPv6路由算法。通过对路由前缀（N）进行范围（K）、集合（M）划分以及更新节点自修复提高查询速度、降低不平衡性的影响，具有O(log2N/K)和O(log2N/K+2M)的查询与更新时间复杂度，空间复杂度为O(K+2N)。实验表明，该算法具有良好的查询性能，降低了更新不平衡性的影响。

关键词: 路由, IPv6, 前缀区间集合, 自修复

Abstract:

The general and special types of IPv6 routing algorithms were studied.Focusing on the imbalance problems in lookup and update process in routing algorithm,a novel method called BSRPS (binary search on range of prefix sets) was presented.By range-partition (K) and set-partition (M) on routing table (N),and self-recovery after updating,this method enhanced the lookup speed and reduced the impact of imbalance in updating.Time complexity in lookup and update process is O(log2N/K) and O(log2N/K+2M),and space complexity is O(K+2N) where N is the size of routing table.Experiment re-sults show that this method is efficient in lookup and reduces the impact of imbalance after updating effectively.

Key words: route, IPv6, range of prefix sets, self-recovery

崔宇,田志宏,张宏莉,方滨兴. 基于前缀区间集合的IPv6路由查找算法[J]. 通信学报, 2013, 34(6): 29-37.

Yu CUI,Zhi-hong TIAN,GHong-li ZHAN,Bin-xing FANG. Binary search on range of IPv6 prefix sets[J]. Journal on Communications, 2013, 34(6): 29-37.

图/表 14

表1

图1

图2

图3

表2

图4

表3

图5

图6

图7

表4

表5

表6

表7

参考文献 15

[1]	[EB/OL]. 2010.
[2]	SUN Q , HUANG X H , ZHOU X J . A dynamic binary hash scheme for IPv6 lookup[A]. Proceedings of IEEE GLOBECOM[C]. New Orleans,USA, 2008. 1-5.
[3]	RUIZ-SANCHEX M A , BIERSACK E W , DABBOUS W . Survey and taxonomy of IP address lookup algorithms[J]. IEEE Network, 2001,15(2): 8-23.
[4]	SAHNI S , KIM K S . Efficient construction of multibit tries for IP address lookup[J]. IEEE/ACM Trans Networking, 2003,11(4): 650-662.
[5]	LIM H , YIM C H . SWARTZLANDER E.Priority tries for IP address lookup[J]. IEEE Transactions on Computers, 2010,6(59): 784-794.
[6]	WALDVOGEL M , VARGHESE G , TURNER J . Scalable high speed IP routing lookups[A]. Proceeding of ACM SIGCOMM[C]. Cannes,France, 1997. 25-36.
[7]	Kim K S , SAHNI S . IP lookup by binary search on prefix length[A]. ISCC '03 Proceedings,of the Eighth IEEE International Symposium on Computers and Communications[C]. Antalya,Turkey, 2003. 77-82.
[8]	LIM H , KIM W , LEE B . Binary search in a balanced tree for IP address lookup[A]. IEEE Workshop High Performance Switching and Routing[C]. HongKong,China, 2005. 490-494.
[9]	LIM H , KIM H , YIM C . IP address lookup for internet routers using balanced binary search with prefix vectord[J]. IEEE Transactions on Communication, 2009,7(3): 618-821.
[10]	LAMPSON B , SRINIVASAN V , VARGHESE G . IP lookups using multiway and multicolumn search[J]. IEEE/ACM Trans Networking, 1999,7(3): 324-334.
[11]	WARKHEDE P , SURI S , VARGHESE G . Multiway range trees: scalable IP lookup with fast updates[J]. Computer Networks, 2004,44: 289-303.
[12]	SAHNI S , KIM K S . An O(logN) dynamic router-table design[J]. IEEE Transactions on Computers, 2004,53(3): 351-363.
[13]	ZHONG P F . An IPv6 address lookup algorithm based on recursive balanced multi-way range trees with efficient search and update[A]. Computer Science and Service System (CSSS)[C]. Paris,France, 2011. 2059-2063.
[1]	李振强, 郑东去, 马严 . TSB：一种多阶段 IPv6 路由表查找算法[J]. 电子学报, 2007,35(10):1859-1864. LI Z Q , ZHENG D Q , MA Y . TSB:a multi-stage algorithm for IPv6 routing table lookup[J]. Chinese Journal of Electronics, 2007,35(10):1859-1864.
[15]	[EB/OL]. 2012.

节点名	前缀	长度	范围
P₁	0001	4	[2,3]
P₂	0010	4	[4,5]
P₃	0011	4	[6,7]
P₄	0100	4	[8,9]
P₅	0101	4	[10,11]
P₆	0110	4	[12,13]
P₇	0111	4	[14,15]
P₈	11	2	[24,31]

节点名	前缀	长度	范围
P₉	00001	5	[1,1]
P₁₀	00010	5	[2,2]
P₁₁	00011	5	[3,3]
P₁₂	1100	4	[26,27]
P₁₃	1101	4	[24,25]
P₁₄	111	3	[28,31]
P₁₅	11101	5	[29,29]

Num	Count.	Percent	Acc-Rate
1+	13	0.36%	9.87
10+	6	4.83%	1.89
100+	17	63.02%	1.48
1 000+	1	30.43%	1.06

Name	Count.	Patricia/kB	BSR/kB	RBMRTs/kB	BSRPS/kB	Max-L	L1	SEG
Potaroo	7 843	604	429	502	499	5	5 570	28
Tokyo	8 019	618	449	513	508	5	6 129	28
Atlanta	8 140	626	456	521	515	5	6 136	29

前缀个数	Patricia	BSR	RBMRTs	BSRPS
1 000+	0.391	0.124	0.119	0.110
100+	0.293	0.135	0.106	0.097
10+	0.277	0.141	0.101	0.077
1+	0.081	0.128	0.092	0.032

基于前缀区间集合的IPv6路由查找算法

Binary search on range of IPv6 prefix sets

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 15

相关文章 15

Metrics

推荐阅读 0

Case	Patricia	RBMRTs	BSRPS
D-a	1.268	1.185	1.389
D-b	1.211	1.107	1.211
D-c	1.178	1.083	1.012
D-d	1.210	1.146	1.262
D-e	1.216	1.077	0.906
D-f	1.063	1.218	1.367
F-a	0.932	1.151	0.936
F-b	0.915	0.911	0.894
F-c	0.892	1.083	0.821
F-d	0.885	1.097	0.835
F-e	0.901	0.882	0.812
F-f	0.863	1.153	0.945

[1]	李竟博, 马礼, 李阳, 傅颖勋, 马东超. 感传算协同工业互联网优化设计[J]. 通信学报, 2023, 44(6): 12-22.
[2]	赵仕祺, 黄小红, 钟志港. 基于信誉的域间路由选择机制的研究与实现[J]. 通信学报, 2023, 44(6): 47-56.
[3]	张进, 葛强, 徐伟海, 江逸茗, 马海龙, 于洪涛. 拟态路由器BGP代理的设计实现与形式化验证[J]. 通信学报, 2023, 44(3): 33-44.
[4]	杨思锦, 庄雷, 宋玉, 王家兴, 阳鑫宇. 多模态网络中时间敏感网络模态的智能调度机制[J]. 通信学报, 2022, 43(5): 82-91.
[5]	陈全, 杨磊, 郭剑鸣, 李星辰, 赵勇, 陈小前. 低轨巨型星座网络：组网技术与研究现状[J]. 通信学报, 2022, 43(5): 177-189.
[6]	李传煌, 陈泱婷, 唐晶晶, 楼佳丽, 谢仁华, 方春涛, 王伟明, 陈超. QL-STCT：一种SDN链路故障智能路由收敛方法[J]. 通信学报, 2022, 43(2): 131-142.
[7]	裴金川, 胡宇翔, 田乐, 胡涛, 李子勇. 联合路由规划的时间敏感网络流量调度方法[J]. 通信学报, 2022, 43(12): 54-65.
[8]	王鹏, 张修社, 索龙, 史可懿. 基于随机时变图的时间确定性网络路由算法[J]. 通信学报, 2021, 42(9): 21-30.
[9]	朱立东, 张勇, 贾高一. 卫星互联网路由技术现状及展望[J]. 通信学报, 2021, 42(8): 33-42.
[10]	杨明川, 薛冠昌, 李清毅. 基于邻居卫星负载状态的低轨卫星分布式路由算法[J]. 通信学报, 2021, 42(8): 43-51.
[11]	霍如, 倪东, 卢华, 夏云峰, 汪硕, 黄韬, 刘韵洁. 区块链PCN的高效路由策略[J]. 通信学报, 2021, 42(6): 30-40.
[12]	徐潇雨, 胡浩, 张红旗, 刘玉岭. 基于深度确定性策略梯度的随机路由防御方法[J]. 通信学报, 2021, 42(6): 41-51.
[13]	陈迪, 邱菡, 张万里, 朱会虎, 朱俊虎, 王清贤. 基于路由状态因果链的域间路由不稳定溯源检测方法[J]. 通信学报, 2021, 42(12): 76-87.
[14]	吴家皋, 郭亚航, 蔡沈磊, 刘林峰. 基于多时间段优化贝叶斯网络的车载容迟网络路由算法[J]. 通信学报, 2021, 42(12): 109-120.
[15]	李硕朋, 方娟, 陈肯. 基于SRv6的确定性网络服务共享保护方案[J]. 通信学报, 2021, 42(10): 32-42.

Case	Patricia	RBMRTs	BSRPS
Du	2.356	2.157	2.414
Fu	1.331	1.809	1.465
Du-L	0.409	0.441	0.141
Fu-L	0.264	0.400	0.116