基于不相交路径的域内路由保护方案

doi:10.19678/j.issn.1000-3428.0048862

计算机工程 ›› 2018, Vol. 44 ›› Issue (12): 140-144,149. doi: 10.19678/j.issn.1000-3428.0048862

基于不相交路径的域内路由保护方案

耿海军,刘洁琦,张举

山西大学软件学院,太原 030006

收稿日期:2017-10-09 出版日期:2018-12-15 发布日期:2018-12-15
作者简介:耿海军(1983—),男,讲师、博士,主研方向为网络体系结构、路由算法;刘洁琦,本科生;张举,讲师、硕士
基金资助:
国家自然科学基金(61702315)

Intra-domain Routing Protection Scheme Based on Disjoint Path

GENG Haijun,LIU Jieqi,ZHANG Ju

School of Software Engineering,Shanxi University,Taiyuan 030006,China

Received:2017-10-09 Online:2018-12-15 Published:2018-12-15

摘要/Abstract

摘要：

目前的路由保护方案备份路径与默认路径交叉度较高,为寻找交叉度较低的两条路径,默认路径可能不利用最短路径。为此,提出一种新的域内路由保护方案。将问题描述为整数规划模型,利用遗传算法计算近似最优解,并在大量拓扑结构上对算法进行模拟。实验结果表明,该方案降低了默认路径和备份路径的交叉度,可有效提高网络的可靠性,提升用户体验。

关键词: 默认路径, 备份路径, 网络故障, 整数线性规划, 遗传算法

Abstract:

The backup path of current routeing protection scheme has a high degree of crossover with the default path.To find two paths with low crossover,the default path may not utilize the shortest path.Therefore,a new intra-domain routing protection scheme is proposed.The problem is described as an integer programming model.The Genetic Algorithm(GA) is used to calculate the approximate optimal solution.The algorithm is simulated on a large number of topologies.Experimental results show that the scheme greatly reduces the crossover between the default path and the backup path,and improves the reliability of the network,and the user experience has improvement.

Key words: default path, backup path, network failure, integer linear programming, Genetic Algorithm(GA)

中图分类号:

TP309.7

耿海军,刘洁琦,张举. 基于不相交路径的域内路由保护方案[J]. 计算机工程, 2018, 44(12): 140-144,149.

GENG Haijun,LIU Jieqi,ZHANG Ju. Intra-domain Routing Protection Scheme Based on Disjoint Path[J]. Computer Engineering, 2018, 44(12): 140-144,149.

http://www.ecice06.com/CN/Y2018/V44/I12/140

参考文献

［1］CLARK D.The design philosophy of the DARPA internet protocols ［J］.ACM SIGCOMM Computer Communication Review,1988,18(4):106-114.
［2］耿海军.基于路由度量的域内多路径路由研究［D］.北京:清华大学,2015.
［3］ANTONAKOPOULOS S,BEJERANO Y,KOPPOL P.Full protection made easy:the dispath IP fast reroute scheme［J］.IEEE/ACM Transactions on Networking,2015,23(4):1229-1242.
［4］GOODE B.Voice over internet protocol［J］.Proceedings of the IEEE,2002,90(9):1495-1517.
［5］KRIST P.Scalable and efficient multipath routing:complexity and algorithms［C］//Proceedings of the 23rd IEEE International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,2015:376-385.
［6］ZHENG J,XU H,ZHU X,et al.We’ve got you covered:failure recovery with backup tunnels in traffic engineering［C］//Proceedings of the 24th International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,2016:1-10.
［7］HARTERT R,VISSICCHIO S,SCHAUS P,et al.A declarative and expressive approach to control forwarding paths in carrier-grade networks［J］.ACM SIGCOMM Computer Communication Review,2015,45(5):15-28.
［8］MARKOPOULOU A,IANNACCONE G.Characterization of failures in an operational IP backbone network［J］.IEEE/ACM Transactions on Networking,2008,16(4):749-762.
［9］徐明伟,李琦,潘凌涛,等.网络故障及自愈路由模型和算法［J］.中国科学:信息科学,2010,40(7):943-953.
［10］GENG Haijun,SHI Xingang,YIN Xia,et al.Algebra and algorithms for multipath QoS routing in link state networks［J］.Journal of Communications and Networks 2017,19(2):189-200.
［11］YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal link-disjoint node-"somewhat disjoint" paths［C］//Proceedingsof the 24th International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,2016:1-10.
(下转第149页)
(上接第144页)
［12］李清.基于弱转发的互联网路由可用性和扩展性研究［D］.北京:清华大学,2013.
［13］SRIDHARAN A,GUERIN R,DIOT C.Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks［J］.IEEE/ACM Transactions on Networking,2005,13(2):234-247.
［14］YANG X,WETHERALL D.Source selectable path diversity via routing deflections［C］//Proceedings of ACM SIGCOMM’06.New York,USA:ACM Press,2006:159-170.
［15］ATLAS A,ZININ A.Basic specification for IP fast reroute:loop-free alternates［Z］.RFC5286,2008.
［16］ATLAS A.U-turn alternates for IP/LDP fast-reroute［Z］.RFC 5286,2006.
［17］JAYAVELU G,RAMASUBRAMANIAN S,YOUNIS O.Maintaining colored trees for disjoint multipath routing under node failures［J］.IEEE/ACM Transactions on Networking,2009,17(1):346-359.
［18］薛华威,王宝生,邓文平.基于SDN架构的网络故障检测与修复系统［J］.计算机工程,2017,43(11) :40-44.
［19］WHITLEY D.A genetic algorithm tutorial［J］.Statistics and Computing,1994,4(2):65-85.
［20］Advanced networking for research and education.［EB/OL］.［2017-06-21］.https://www.internet2.edu/products-services/advanced-networking.
［21］SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring ISP topologies with rocketfuel［J］.IEEE/ACM Transactions on Networking,2004,12(1):2-16.

[1]	白祉旭, 王衡军. 基于改进遗传算法的对抗样本生成方法[J]. 计算机工程, 2023, 49(5): 139-149.
[2]	桑永宣, 魏江坡, 王博, 宋莹. 具有边缘缓存机制的混合启发式任务卸载算法[J]. 计算机工程, 2023, 49(4): 149-158.
[3]	马华伟, 马凯, 郭君. 考虑多投递的带无人机车辆路径规划问题研究[J]. 计算机工程, 2022, 48(8): 299-305.
[4]	宋勇春, 王茜竹, 高正念. 基于HAGA的D2D-NOMA资源分配优化算法[J]. 计算机工程, 2022, 48(2): 275-280,290.
[5]	缪欣, 陈璇, 鲍红莹, 张静轩, 余炜. 移动传感器网络中路径扫描覆盖问题研究[J]. 计算机工程, 2022, 48(12): 150-155,164.
[6]	吴铁洲, 邹智, 姜奔, 张晓星. 基于TLBGA-GRU神经网络的短期负荷预测[J]. 计算机工程, 2022, 48(11): 69-76.
[7]	曾蓉晖, 林兵, 王明芬, 林凯, 卢宇. 超密集边缘计算网络中面向能耗优化的任务卸载方法[J]. 计算机工程, 2022, 48(11): 39-48.
[8]	杜秀丽, 周敏, 吕亚娜, 邱少明. 基于RBF神经网络优化的装备保障系统效能评估[J]. 计算机工程, 2021, 47(9): 282-287,296.
[9]	魏秀然, 王峰. 基于协调器与遗传算法的云存储数据复制策略[J]. 计算机工程, 2021, 47(8): 124-130,139.
[10]	刘丹, 耿娜. 基于两阶段随机仿真优化算法的体检顾客预约调度[J]. 计算机工程, 2021, 47(7): 281-288.
[11]	郑娟毅, 崔卓, 苏海龙, 殷帅帅, 刘遥遥. 基于改进GA-Elman的无线智能传播损耗预测方法[J]. 计算机工程, 2021, 47(7): 155-160,167.
[12]	曹志鹏, 刘勤让, 刘冬培, 张霞. 面向时间敏感网络的流量调度方法[J]. 计算机工程, 2021, 47(7): 168-175,182.
[13]	杨天, 杨军. 移动边缘计算中的卸载决策与资源分配策略[J]. 计算机工程, 2021, 47(2): 19-25.
[14]	倪水平, 戚海涛, 李慧芳. 基于多种群遗传与思维进化的混合算法[J]. 计算机工程, 2021, 47(12): 62-70.
[15]	陆荣秀, 何权恒, 杨辉, 朱建勇. 基于GA-ELM的稀土混合溶液多组分含量预测[J]. 计算机工程, 2021, 47(1): 284-290,297.

选择文件类型/文献管理软件名称

选择包含的内容

基于不相交路径的域内路由保护方案

Intra-domain Routing Protection Scheme Based on Disjoint Path

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于不相交路径的域内路由保护方案

Intra-domain Routing Protection Scheme Based on Disjoint Path

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价