计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 329-335.doi: 10.11896/jsjkx.210100051

• 计算机网络 • 上一篇    下一篇

基于混合软件定义网络的单节点故障保护方法

耿海军1,2, 王威1, 尹霞3   

  1. 1 山西大学计算机与信息技术学院 太原030006
    2 山西大学自动化与软件学院 太原030006
    3 清华大学计算机科学与技术系 北京100084
  • 收稿日期:2021-01-06 修回日期:2021-05-07 出版日期:2022-02-15 发布日期:2022-02-23
  • 通讯作者: 耿海军(ghj123025449@163.com)
  • 基金资助:
    山西省应用基础研究计划(20210302123444);国家自然科学基金(61702315);山西省重点研发计划(201903D421003);国家高技术研究发展计划(863)(2018YFB1800401)

Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks

GENG Hai-jun1,2, WANG Wei1, YIN Xia3   

  1. 1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
    2 School of Automation and Software Engineering,Shanxi University,Taiyuan 030006,China
    3 Department of Computer Science & Technology,Tsinghua University,Beijing 100084,China
  • Received:2021-01-06 Revised:2021-05-07 Online:2022-02-15 Published:2022-02-23
  • About author:GENG Hai-jun,born in 1983,Ph.D,lecturer,is a member of China Computer Federation. His main research interests include future Internet architecture and routing algorithm.
  • Supported by:
    Applied Basic Research Plan of Shanxi Province(20210302123444),National Natural Science Foundation of China(61702315),Key R & D Program of Shanxi Province China(201903D421003) and National High Technology Research and Development Program of China(863)(2018YFB1800401).

摘要: 软件定义网络(Software Defined Network,SDN)是由美国斯坦福大学Clean Slate课题组提出的一种新型网络体系架构,该架构通过解耦控制平面和转发平面的功能来实现网络流量的灵活转发。但是,由于经济开销和技术条件的限制,互联网服务提供商的骨干网必定长期处于传统设备和SDN设备共存的混合SDN状态。因此,在混合SDN网络中研究应对单节点故障情形的路由保护方法是一个关键的科学问题。文中首先描述了混合SDN网络中应对单节点故障情形时需要解决的问题,然后通过两种启发式方法来解决该问题,最后在真实拓扑结构和模拟拓扑结构中对提出的启发式算法进行测试。实验结果表明,在传统骨干网中,仅需要将一小部分传统设备升级为SDN设备,所提算法就可以应对网络中所有可能的单节点故障情形。

关键词: 单节点故障, 混合软件定义网络, 路由保护算法, 启发式算法, 实时应用

Abstract: Software defined network (SDN) is a new network architecture proposed by the clean slate research group of Stanford University.The significant feature of this architecture is to decouple the functions of control plane and forwarding plane,and to flexibly forward the network traffic.Based on this,Internet service providers have deployed SDN technology in their backbone network to maximize the utilization of network resources.However,due to the limitation of economic cost and technical conditions,the backbone network of internet service providers must be in the hybrid SDN network for a long time.The studies have shown that single network node failure is inevitable and occurs frequently.Therefore,it is a key scientific problem to study the routing protection me-thod for single network component failure in hybrid SDN networks.In this paper,the route protection method for single network component failure in hybrid SDN network is described,and then two heuristic methods are used to solve the problem.Finally,the proposed heuristic algorithms are tested in real and simulated topologies.The experimental results show that in the traditional backbone network,only a part of the traditional devices need to be upgraded to SDN devices,and the algorithms proposed in this paper can deal with all possible single network node failure cases in the network.

Key words: Heuristic algorithm, Hybrid software defined network, Real-time application, Routing protection algorithm, Single node failure

中图分类号: 

  • TP311
[1]GENG H J,ZHANG H,SHI X G,et al.Efficient computation of loop-free alternates[J].Journal of Network and Computer Applications,2020,151(5):1-12.
[2]KUN Q,JIN Z,XIN W,et al.Efficient Recovery Path Computa-tion for Fast Reroute in Large-scale Software Defined Networks[J].IEEE Journal on Selected Areas in Communications,2019,37(8):1755-1768.
[3]GENG H J,SHI X G,WANG Z L.Intra-domain Routing Protection Scheme Based on Minimum Intersection Paths[J].Journal of Software,2020,31(5):1536-1548.
[4]DONG S.Survey on Software Defined Networks Security[J].Computer Science,2021,48(3):295-306.
[5]ZHANG J,WANG H,LUO S T,et al.Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm[J].Computer Science,2020,47(6):236-241.
[6]YANG Y,XU M,LI Q.Fast Rerouting Against Multi-LinkFailures Without Topology Constraint[J].IEEE/ACM Tran-sactions on Networking,2018,26(1):384-397.
[7]GENG H,SHI X,WANG Z,et al.A hop-by-hop dynamic distributed multipath routing mechanism for link state network[J].Computer Communications,2018,116:225-239.
[8]KWONG K W,GAO L,ZHANG Z L.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556.
[9]ATLAS A,ZININ A.RFC 5286,Basic specification for ip fast reroute:Loop-free alternates[S].IETF,2008.
[10]ENYEDI G,RÉTVÑRI G,SZILÑGYI P,et al.IP Fast Re-Route:Lightweight Not-Via without Additional Addresses[C]//International Conference on Computer Communications (INFOCOM).IEEE Computer Society,2009:2771-2775.
[11]ZHENG J,XU H,ZHU X,et al.We've Got You Covered:Fai-lure Recovery with Backup Tunnels in Traffic Engineering[C]//International Conference on Network Protocols (ICNP).IEEE Computer Society,2016:1-10.
[12]RÉTVÑRI G,CSIKOR L,TAPOLCAI J,et al.Optimizing IGP link costs for improving IP-level resilience[C]//International Conference on the Design of Reliable Communication Networks (DRCN).IEEE Computer Society,2011:62-69.
[13]RÉTVÑRI G,TAPOLCAI J,ENYEDI G,et al.Ip fast reroute:Loop free alternates revisited[C]//International Conference on Computer Communications (INFOCOM).IEEE Computer So-ciety,2011:2948-2956.
[14]BRAUN W,MENTH M.Loop-Free Alternates with Loop Detection for Fast Reroute in Software-Defined Carrier and Data Center Networks[J].Journal of Network and Systems Management,2016,24(3):470-490.
[15]HE L,LIN R,YU S,et al.Congestion-Aware Local Reroute for Fast Failure Recovery in Software-Defined Networks[J].IEEE/OSA Journal of Optical Communications & Networking,2017,9(11):934-944.
[16]ZHANG X,CHENG Z,LIN R P,et al.Local Fast Reroute With Flow Aggregation in Software Defined Networks[J].IEEE Communications Letters,2017,21(4):785-788.
[17]ZHU Z,LI Q,XIA S,et al.CAFFE:Congestion-Aware FastFailure Recovery in Software Defined Networks[C]//International Conference on Computer Communication and Networks (ICCCN).IEEE Computer Society,2018:1-9.
[18]ZHENG J,XU H,ZHU X,et al.Sentinel:Failure Recovery in Centralized Traffic Engineering[J].IEEE/ACM Transactions on Networking,2019,27(5):1859-1872.
[19]GENG H J,ZHANG W,YIN X.Routing Protection Algorithm Based on Hybrid Software Defined Network[J].Computer Engineering,2020,46(6):209-215.
[20]GENG H J,SHI X G,WANG Z L,et al.Intra-domain Routing Protection Scheme Based on Minimum Intersection Paths[J].Journal of Software,2020,31(5):1536-1548.
[21]YANG Z,YEUNG K L.SDN Candidate Selection in HybridIP/SDN Networks for Single Link Failure Protection[J].IEEE/ACM Transactions on Networking,2020,28(1):312-321.
[22]NETWORK A B.Advanced networking for research and education[OL].http://abilene.internet2.edu,2003.
[23]ANTONAKOPOULOS S,BEJERANO Y,KOPPOL P.FullProtection Made Easy:The DisPath IP Fast Reroute Scheme[J].IEEE/ACM Transactions on Networking,2015,23(4):1229-1242.
[24]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] 刘忠慧, 赵琦, 邹璐, 闵帆.
三元概念的启发式构建及其在社会化推荐中的应用
Heuristic Construction of Triadic Concept and Its Application in Social Recommendation
计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136
[2] 郭启程, 杜晓玉, 张延宇, 周毅.
基于改进鲸鱼算法的无人机三维路径规划
Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm
计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[3] 郭飞雁, 唐兵.
基于用户延迟感知的移动边缘服务器放置方法
Mobile Edge Server Placement Method Based on User Latency-aware
计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[4] 张举, 王浩, 罗舒婷, 耿海军, 尹霞.
基于遗传算法的混合软件定义网络路由节能算法
Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm
计算机科学, 2020, 47(6): 236-241. https://doi.org/10.11896/jsjkx.191000139
[5] 张旭, 王莉莉, 杨博韬.
带有一刀切约束的二维非规则装箱算法
Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints
计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078
[6] 杨婷, 罗飞, 丁炜超, 卢海峰.
一种自适应优化松弛量的装箱算法
Bin Packing Algorithm Based on Adaptive Optimization of Slack
计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132
[7] 罗飞, 任强, 丁炜超, 卢海峰.
基于最小松弛量的启发式一维装箱算法
Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack
计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048
[8] 耿海军, 尹霞.
基于增量最短路径优先的域内高效路由保护算法
Efficient Intra-domain Routing Protection Algorithm Based on i-SPF
计算机科学, 2019, 46(8): 116-120. https://doi.org/10.11896/j.issn.1002-137X.2019.08.019
[9] 张澍裕, 宫达, 谢兵, 刘开贵.
基于实时GPS的公交短时动态调度算法
Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS
计算机科学, 2019, 46(6A): 497-501.
[10] 史雯隽,武继刚,罗裕春.
针对移动云计算任务迁移的快速高效调度算法
Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading
计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014
[11] 单天羽, 管煜旸.
基于种群多样性的可变种群缩减差分进化算法
Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity
计算机科学, 2018, 45(11A): 160-166.
[12] 李美争,李磊军,米据生,解滨.
概念格中基于粗糙熵的属性约简方法
Rough Entropy Based Algorithm for Attribute Reduction in Concept Lattice
计算机科学, 2018, 45(1): 84-89. https://doi.org/10.11896/j.issn.1002-137X.2018.01.013
[13] 殷晓波,罗恩.
一种松弛的优化均衡流式图划分算法研究
Relaxed Optimal Balanced Streaming Graph Partitioning Algorithm
计算机科学, 2016, 43(4): 231-234. https://doi.org/10.11896/j.issn.1002-137X.2016.04.047
[14] 陈小潘,孔云峰,郑泰皓,郑珊珊.
需求可拆分校车路径问题的元启发式算法
Metaheuristic Algorithm for Split Demand School Bus Routing Problem
计算机科学, 2016, 43(10): 234-241. https://doi.org/10.11896/j.issn.1002-137X.2016.10.045
[15] 杨光,曾斌.
一种面向可靠传输的数据链中继策略研究
Research on Reliability-aware Relay Strategy in Data Link
计算机科学, 2015, 42(Z11): 253-257.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!