Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (9): 337-346.doi: 10.11896/jsjkx.220900220

• Computer Network • Previous Articles     Next Articles

Routing Protection Scheme with High Failure Protection Ratio Based on Software-defined Network

GENG Haijun1,2,3, WANG Wei1,3, ZHANG Han4, WANG Ling2   

  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 Institute of Big Data Science and Industry,Shanxi University,Taiyuan 030006,China
    4 Department of Computer Science Technology,Tsinghua University,Beijing 100084,China
  • Received:2022-09-23 Revised:2023-03-05 Online:2023-09-15 Published:2023-09-01
  • About author:GENG Haijun,born in 1983,Ph.D,associate professor.His main research intere-sts include software defined network,Internet routing algorithm and network architecture.
  • Supported by:
    Shanxi Applied Basic Research Program(20210302123444),Scientific and Technological Innovation Programs of Higher Education Institutions in Shanxi(2022L002),Industry-University-Research Innovation Fund of Chinese Universities(2021FNA02009),National Natural Science Foundation of China(61702315),Key R&D Program of Shanxi Province,China(201903D421003,202202020101004) and National High Technology Research and Development Program of China(2018YFB1800401).

PDF (PC)

1709

Abstract: SDN has attracted extensive attention from academia for its advantages of strong programmability and centralized control.Existing SDN devices still use the shortest path protocol when performing packet forwarding.When a node in the shortest path fails,the network re-convergence is still required.During this period,packets may be discarded and thus cannot be delivered to the destination node,which has an impact on the flow of real-time applications and affects the user experience.The academia generally adopts the routing protection schemes to deal with network failures.The existing routing protection schemes have the following two problems:(1)the failure protection ratio is low;(2)when the network fails,the backup path may have routing loops.In order to solve the above two problems,a backup next hop calculation rule is proposed.Then,based on this rule,a routing protection algorithm with high hailure protection ratio(RPAHFPR) is designed,which combines the path generation algorithm(PGA),side branch first algorithm(SBF) and loop avoidance algorithm(LAA).It can simultaneously solve the low failure protection rate and routing loop problems faced by existing routing protection methods.Finally,the performance of RPAHFPR scheme is verified in a large number of real network topologies and simulated network topologies.Compared with the classic NPC and U-TURN,the failure protection rate of RPAHFPR is increased by 20.85% and 11.88% respectively,and it can achieve 100% fai-lure protection rate in 86.3% topology,and more than 99% failure protection rate in all topology.The path stretching degree of RPAHFPR is basically close to 1,without introducing too much time delay.

Key words: Software-defined network, Route protection algorithm, Reverse shortest path tree, LFA rule, Backup path, Network single failure

CLC Number: 

  • TP311
[1]ANTONAKOPOULOS S,KOPPOL P,et al.Full protectionmade easy:the dispath ip fast reroute schemep[J].IEEE/ACM Transactions on Networking:A Joint Publication of the IEEE Communications Soceity,the IEEE Computer Society,and the ACM with Its Special Interest Group on Data Communication,2015,23(4):1229-1242.
[2]ANBIAH A,SIVALINGAM K M.Efficient failure recoverytechniques for segment-routed networks[J].Computer Communications,2022,182:1-12.
[3]TAPOLCAI J,RETVARI G,BABARCZI P,et al.Scalable and efficient multipath routing:complexity and algorithms[C]// 2015 IEEE 23rd International Conference on Network Protocols(ICNP).2016:376-385.
[4]XU M W,LI Q,PAN L T,et al.Network Failure and Self-hea-ling Routing Model and Algorithm[J].SCIENTIA SINICA Informationis,2010,40(7):943-953.
[5]YUAN Y,XU M,QI L.Tunneling on demand:a lightweight ap-proach for ip fast rerouting against multi-link failures[C]// 2016 IEEE/ACM 24th International Symposium on Quality of Service(IWQoS).Beijing:IEEE,2016:1-6.
[6]GOPALAN A,RAMASUBRAMANIAN S.IP fast reroutingand disjoint multipath routing with three edge-independent spanning trees[J].IEEE/ACM Transactions on Networking,2016,24(3):1336-1349.
[7]LABOVITZ C,AHUJA A,BOSE A,et al.Delayed internet routing convergence[J].IEEE/ACM Transactions on Networking,2001,9(3):293-306.
[8]FORTZ B,THORUP M.Optimizing ospf/is-is weights in achanging world[J].IEEE Journal on Selected Areas in Communications,2002,20(4):756-767.
[9]CLAD F,MERINDOL P,VISSICCHIO S,et al.Graceful router updates in link-state protocols [C]// 21st IEEE International Conference on Network Protocols.Goettingen:IEEE,2013:1-10.
[10]ASTUTO B N,CA M M,XUAN N N,et al.A survey of software-defined networking:past,present,and future of programmable Networks[J].IEEE Communications Surveys & Tuto-rials,2014,16(3):1617-1634.
[11]AMIN R,REISSLEIN M,SHAH N.Hybrid sdn networks:asurvey of existing approaches[J].IEEE Communications Surveys & Tutorials,2018,20(4):3259-3306.
[12]YANG Y,XU M,LI Q.Fast rerouting against multi-link fai-lures without topology constraint[J].IEEE/ACM Transactions on Networking,2018,26(1):384-397.
[13]LEE S,YU Y,NELAKUDITI S,et al.Proactive vs reactive approaches to failure resilient routing[C]// Joint Conference of the IEEE Computer & Communications Societies.Hong Kong:IEEE,2004:176-186.
[14]KWONG K W,GAO L,GUERIN R,et al.On the Feasibilityand Efficacy of Protection Routing in IP Networks[J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556.
[15]ATLAS A,ZININ A.Basic specification for ip fast reroute:Loop-free alternates[R].Heise zeitschriften verlag,2008.
[16]BRYANT S.Ip fast reroute framework.LoopFree Alternatesn[S].USA:The Internet Engineering Task Force,2010.
[17]BRYANT S,PREVIDI S,SHAND M.A framework for ip and mpls fast reroute using not-via addresses[S].USA:Internet Requests for Comments,RFC,2013.
[18]RÉTVÁRI G,TAPOLCAI J,ENYEDI G,et al.Ip fast reroute:loop free alternates revisited[C]//2011 Proceedings IEEE INFOCOM.Shanghai:IEEE,2011:2948-2956.
[19]CSIKOR L,NAGY M,RÉTVÁRI G.Network optimizationtechniques for improving fast ip-level resilience with loop-free alternates[J].Infocommunications Journal,2011,III(4):2-10.
[20]RÉTVÁRI G,CSIKOR L,TAPOLCAI J,et al.Optimizing igp link costs for improving ip-level resilience[C]// 8th Interna-tional Workshop on the Design of Reliable Communication Networks.Krakow:DRCN,2011:62-69.
[21]CSIKOR L,RÉTVÁRI G.On providing fast protection with remote loop-free alternates[J].Telecommunication Systems,2015,60(4):1-18.
[22]BRYANT S,FILSFILS C,PREVIDI S,et al.Remote loop-free alternate(lfa) fast reroute(fpr)[S].USA:The Internet Engineering Task Force,2015.
[23]GENG H J,ZHANG H,SHI X G,et al.Efficient computation ofloop-free alternates[J].Journal of Network and Computer Applications,2020,151(102501):1-12.
[24]KAMISINSKI A.Evolution of ip fast-reroute strategies[C]// 2018 10th International Workshop on Resilient Networks Design and Modeling.Longyearbyen:RNDM,2018:1-6.
[25]TAVERNIER W,PAPADIMITRIOU D,COLLE D,et al.Self-configuring loop-free alternates with high link failure coverage[J].Telecommunication Systems,2014,56(1):85-101.
[26]DECRAENE B,FRANCOIS P,BASHANDY A,et al.Topology independent fast reroute using segment routin[S].USA:The Internet Engineering Task Force,2014.
[27]CIANFRANI A,LISTANTI M,POLVERINI M.IncrementalDeployment of Segment Routing Into an ISP Network:a Traffic Engineering Perspective[J].IEEE/ACM Transactions on Networking,2017,25(5):3146-3160.
[28]ATLAS A et al.U-turn alternates for ip/ldp fast-reroute[S].USA:The Internet Engineering Task Force,2006.
[29]ENYEDI G,SZILAGYI P,RETVARI G,et al.Ip fast reroute:lightweight not-via without additional addresses[C]//IEEE INFOCOM 2009.Rio de Janeiro:IEEE,2009:2771-2775.
[30]ZHANG H L,XIAO G,YAN J Y,et al.Sdn-based ecmp algorithm for data center networks[C]// 2014 IEEE Computing,Communications and IT Applications Conference(ComComAp).Beijing:IEEE,2014:13-18.
[31]BRAUN W,MENTH M,et al.Loop-free alternates with loop detection for fast reroute in software-defined carrier and data center networks[J].Journal of Network & Systems Management,2016,24(3):470-490.
[32]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.
[33]QIU K,ZHAO J,WANG X,et al.Efficient recovery path computation for fast reroute in large-scale software defined networks[J].IEEE Journal on Selected Areas in Communications,2019,37(8):1755-1768.
[34]THORAT P,CHALLA R,RAZA S M,et al.Proactive failure recovery scheme for data traffic in software defined networks[C]// 2016 IEEE Netsoft Conference & Workshops.Seoul:IEEE,2016:219-225.
[35]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.
[36]GENG H J,ZHANG W,YIN X.Routing protection algorithm based on hybrid software defined network[J].Computer Engineering,2020,46(6):209-215.
[37]GENG H J,WANG W,YIN X.Single-node fault protectionmethod based on hybrid software-defined network[J].Computer Science,2022,49(2):329-335.
[38]GP RÉDEI.Abilene(advanced networking for leading-edge research and education)[M].Berlin:Springer Netherlands,2008.
[1] CHEN Ziqiang, XIA Zhengyou. Failure Recovery Model for Single Link with Congestion-Avoidance in SDN [J]. Computer Science, 2023, 50(4): 212-219.
[2] CHEN Gang, MENG Xiang-ru, KANG Qiao-yan, ZHAI Dong. vSDN Fault Recovery Algorithm Based on Minimum Spanning Tree [J]. Computer Science, 2022, 49(11A): 211200034-7.
[3] ZHOU Jian-xin, ZHANG Zhi-peng, ZHOU Ning. Load Balancing Technology of Segment Routing Based on CKSP [J]. Computer Science, 2020, 47(4): 256-261.
[4] ZHAO Jin-long, ZHANG Guo-min, XING Chang-you, SONG Li-hua, ZONG Yi-ben. Self-adaptive Deception Defense Mechanism Against Network Reconnaissance [J]. Computer Science, 2020, 47(12): 304-310.
[5] ZHANG Zhao, LI Hai-long, HU Lei, DONG Si-qi. Service Function Load Balancing Based on SDN-SFC [J]. Computer Science, 2019, 46(9): 130-136.
[6] GENG Hai-jun. Intra-domain Routing Protection Scheme by Optimizing Link Weight [J]. Computer Science, 2019, 46(1): 143-147.
[7] ZHANG Fang, DENG Chang-lin, WANG Zhi and GUO Wei. Link Failure Detection and Fast Recovery in Software-defined Satellite Network [J]. Computer Science, 2017, 44(6): 63-67.
[8] LIU Lin and ZHOU Jian-tao. Review for Research of Control Plane in Software-defined Network [J]. Computer Science, 2017, 44(2): 75-81.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.