基于混合软件定义网络的路由保护算法

doi:10.19678/j.issn.1000-3428.0054783

计算机工程 ›› 2020, Vol. 46 ›› Issue (6): 209-215. doi: 10.19678/j.issn.1000-3428.0054783

基于混合软件定义网络的路由保护算法

耿海军¹, 张伟², 尹霞³

1. 山西大学软件学院, 太原 030006;
2. 中国劳动关系学院计算机应用教研室, 北京 100048;
3. 清华大学计算机科学与技术系, 北京 100084

收稿日期:2019-04-30 修回日期:2019-06-03 发布日期:2020-06-10
作者简介:耿海军(1983-),男,讲师、博士,主研方向为网络体系结构、路由算法;张伟,副教授;尹霞,教授、博士。
基金资助:
国家自然科学基金（61702315）；山西省高等学校科技创新项目（201802013）。

Routing Protection Algorithm Based on Hybrid Software Defined Network

GENG Haijun¹, ZHANG Wei², YIN Xia³

1. School of Software Engineering, Shanxi University, Taiyuan 030006, China;
2. Computer Application Teaching and Research Section, China University of Labor Relations, Beijing 100048, China;
3. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Received:2019-04-30 Revised:2019-06-03 Published:2020-06-10

摘要/Abstract

摘要： 为使混合软件定义网络（SDN）体系架构能够应对网络中的单链路故障情形，提出一种基于混合软件定义网络的路由保护算法。在混合SDN网络中部署应对单链路故障的路由保护算法，将其归结为一个0-1整数规划问题，并利用启发式算法计算该问题对应的近似最优解。通过实例介绍算法的执行过程，分析算法对应的时间复杂度。实验结果表明，该算法仅需将传统网络中的少部分节点升级为SDN节点，即可应对网络中可能出现的单链路故障情形，且对应的路径拉伸度在1.4以内。

关键词: 混合软件定义网络, 单链路故障, 启发式算法, 整数规划模型, 故障保护率

Abstract: In order to enable the Software Defined Network(SDN) to cope with the possible situations of single link failure in network,this paper proposes a routing protection algorithm based on hybrid SDN.The routing protection algorithm coping with the single link failure is deployed in the hybrid SDN,which is reduced to a 0-1 integer programming problem and a heuristic algorithm is used to calculate the approximate optimal solution to the problem.The execution process of the algorithm is introduced through an example and the corresponding time complexity of the algorithm is analyzed.Experimental results show that the proposed algorithm can cope with all possible situations of single link failure only by upgrading a small number of nodes in the traditional network to SDN nodes,and the corresponding path stretch is within 1.4.

Key words: hybrid Software Defined Network(SDN), single link failure, heuristic algorithm, integer programming model, failure protection ratio

中图分类号:

TP309.7

耿海军, 张伟, 尹霞. 基于混合软件定义网络的路由保护算法[J]. 计算机工程, 2020, 46(6): 209-215.

GENG Haijun, ZHANG Wei, YIN Xia. Routing Protection Algorithm Based on Hybrid Software Defined Network[J]. Computer Engineering, 2020, 46(6): 209-215.

https://www.ecice06.com/CN/Y2020/V46/I6/209

图/表 7

20200617090950

20200617090953

20200617090956

20200617090959

20200617091002

20200617091005

20200617091008

参考文献

[1] ZHANG Yuan,CUI Lin,WANG Wei,et al.A survey on software defined networking with multiple controllers[J].Journal of Network and Computer Applications,2018,103:101-118.
[2] VISSICCHIO S,VANBEVER L,CITTADINI L,et al.Safe update of hybrid SDN networks[J].IEEE/ACM Transactions on Networking,2017,25(3):1649-1662.
[3] HU Yanan.Research on key technologies and related problems of software defined network[D].Beijing:Beijing University of Posts and Telecommunications,2015.(in Chinese)胡延楠.软件定义网络关键技术及相关问题的研究[D].北京:北京邮电大学,2015.
[4] SCOTTHAYWARD S,NATARAJAN S,SEZER A S.A survey of security in software defined networks[J].IEEE Communications Surveys and Tutorials,2016,18(1):623-654.
[5] SEZER S,SCOTT-HAYWARD S,CHOUHAN P K,et al.Are we ready for SDN? implementation challenges for software-defined networks[J].IEEE Communications Magazine,2013,51(7):36-43.
[6] YUAN Tingting.Research on node migration and optimization methods for SDN transition[D].Beijing:Beijing University of Posts and Telecommunications,2018.(in Chinese)苑婷婷.面向SDN过渡的节点迁移及优化方法的研究[D].北京:北京邮电大学,2018.
[7] SALSANO S,VENTRE P L,LOMBARDO F,et al.Hybrid IP/SDN networking:open implementation and experiment management tools[J].IEEE Transactions on Network and Service Management,2016,13(1):138-153.
[8] AMIN R,RESSLEIN M,SHAH N.Hybrid SDN networks:a survey of existing approaches[J].IEEE Communications Surveys and Tutorials,2018,20(4):3259-3306.
[9] CHU C,XI K,LUO M,et al.Congestion-aware single link failure recovery in hybrid SDN networks[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C.,USA:IEEE Press,2015:1086-1094.
[10] GENG Haijun,SHI Xingang,WANG Zhiliang,et al.A hop-by-hop dynamic distributed multipath routing mechanism for link state network[J].Computer Communications,2018,116:225-239
[11] 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.
[12] HUANG Jianyang.Research on SDN traffic engineering technology based on segment routing[D].Zhengzhou:PLA Information Engineering University,2017.(in Chinese)黄建洋.基于分段路由的SDN流量工程技术研究[D].郑州:解放军信息工程大学,2017.
[13] GENG Haijun,LIU Jieqi,ZHANG Ju.Intra-domain routing protection scheme based on disjoint path[J].Computer Engineering,2018,44(12):140-144,149.(in Chinese)耿海军,刘洁琦,张举.基于不相交路径的域内路由保护方案[J].计算机工程,2018,44(12):140-144,149.
[14] YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal link-disjoint node-somewhat disjoint paths[C]//Proceedings of IEEE International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,2016:1-10.
[15] YANG X,WETHERALL D.Source selectable path diversity via routing deflections[C]//Proceedings of ACM Special Interest Group on Data Communication.New York,USA:ACM Press,2006:159-170.
[16] KVALBEIN A,HANSEN A F,GJESSING S,et al.Fast IP network recovery using multiple routing configurations[C]//Proceedings of the 25th IEEE International Conference on Computer Communications.Washington D.C.,USA:IEEE Press,2006:22-31
[17] LAKSHMINARAYANAN K,CAESAR M,RANGAN M,et al.Achieving convergence-free routing using failure-carrying packets[C]//Proceedings of International Conference on Computer Communications.Kyoto,Japan:[s.n.],2007:241-252.
[18] ATLAS A,ZININ A.Basic specification for IP fast reroute:loop-free alternates[M].[S.1.]:Heise Zeitschriften Verlag,2008.
[19] ENYEDI G,RETVARI G,SZILAGYI P,et al.IP fast ReRoute:lightweight not-via without additional addresses[C]//Proceedings of IEEE INFOCOM'09.Washington D.C.,USA:IEEE Press,2009:2771-2775.
[20] ZHANG Ju,GENG Haijun.Research on intra-domain routing protection scheme based on software defined network[J].Application Research of Computers,2019,36(3):921-924.(in Chinese)张举,耿海军.基于软件定义网络的域内路由保护方案研究[J].计算机应用研究,2019,36(3):921-924.
[21] GENG Haijun,LIU Jieqi,YIN Xia.Single node failure routing protection algorithm based on segment routing[J].Journal of Tsinghua University(Science and Technology),2018,58(8):710-714.(in Chinese)耿海军,刘洁琦,尹霞.基于段路由的单节点故障路由保护算法[J].清华大学学报(自然科学版),2018,58(8):710-714.
[22] NETWORK A B.Advanced networking for research and education[EB/OL].[2019-03-20].http://abilene.internet2.edu.
[23] 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.
[24] SPING N,MAHAJAN R,WETHERALL D,et al.Measuring ISP topologies with rocketfuel[J].IEEE/ACM Transactions on Networking,2004,12(1):2-16.

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

选择包含的内容

基于混合软件定义网络的路由保护算法

Routing Protection Algorithm Based on Hybrid Software Defined Network

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	周春雷, 宋继勐, 沈子奇, 余晗, 雷杰, 林兵. 数联网标识解析系统中的标识数据布局策略[J]. 计算机工程, 2024, 50(6): 311-320.
[2]	林丹, 郑梓烨, 付齐双, 吴嘉婧, 郑子彬. 基于DeFi消息传递机制的跨链交易关联方法[J]. 计算机工程, 2024, 50(10): 61-68.
[3]	刘博宇, 梁承姬, 王钰. 特大型城市地下物流多层级网络优化研究[J]. 计算机工程, 2023, 49(12): 311-320.
[4]	黄金瑶, 刘同来, 吴嘉鑫, 武继刚. 多周期家庭护理的路径规划与调度算法[J]. 计算机工程, 2022, 48(7): 292-299.
[5]	龙恳, 钱美伶, 余翔, 陈侃. 一种基于网络切片的带宽资源编排算法[J]. 计算机工程, 2019, 45(10): 78-83.
[6]	张祯,樊兴悦,郭禹田,吴国华. 基于Topic Signature的动态文摘更新方法[J]. 计算机工程, 2018, 44(6): 169-175.
[7]	许磊,顾进广,何亨. 基于SDN架构的网络能耗与性能动态调节机制[J]. 计算机工程, 2018, 44(4): 108-114.
[8]	郭羽含,杨晓翠. 绿色供应链网络构建的双阶段综合优化方法[J]. 计算机工程, 2016, 42(10): 192-200.
[9]	刘文锋. 一种基于最小能耗的手机传感调度算法[J]. 计算机工程, 2015, 41(6): 83-89.
[10]	徐超,曾学文,郭志川. 基于资源预测的智能终端资源缓存算法[J]. 计算机工程, 2015, 41(3): 59-63.
[11]	凌权,李枚毅. 无线Mesh网络中骨干节点部署算法研究[J]. 计算机工程, 2015, 41(11): 147-152.
[12]	高圣巍,彭超. 一种改进的邻接关系可查询压缩算法[J]. 计算机工程, 2015, 41(1): 61-64.
[13]	李静梅,王雪,韩启龙. 一种异构多核处理器启发式综合任务调度算法[J]. 计算机工程, 2014, 40(8): 242-245,252.
[14]	秦天保，彭嘉瑶，沙梅. 基于约束规划的岸桥与集卡集成调度[J]. 计算机工程, 2014, 40(5): 196-202.
[15]	赖河蒗, 陈红英, 赖博先, 柯万添. 基于回答集编程的Banks选举求解方法[J]. 计算机工程, 2013, 39(8): 266-269.

模态框（Modal）标题

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

选择包含的内容

基于混合软件定义网络的路由保护算法

Routing Protection Algorithm Based on Hybrid Software Defined Network

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价