计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (9): 337-346.doi: 10.11896/jsjkx.220900220

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

基于软件定义网络的高故障保护率的路由保护方案

耿海军1,2,3, 王威1,3, 张晗4, 王玲2   

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

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)

1706

摘要： 软件定义网络(Software Defined Network,SDN)以其强大的可编程性和集中控制的优势得到了学术界的广泛关注。现有的SDN设备在执行报文转发时仍然使用最短路径协议,当最短路径中的结点发生故障时,网络仍然需要重新收敛,在此期间报文可能会被丢弃,进而无法传递至目的结点,给实时性应用的流畅性造成了冲击,影响用户体验。学术界普遍采用路由保护的方案来应对网络故障,现有的路由保护方案存在以下两个方面的问题:(1)故障保护率低;(2)当网络出现故障时,备份路径可能会出现路由环路。为了解决上述两个问题,首先提出了备份下一跳计算规则;然后基于此规则设计了一种软件定义网络下的高故障保护率的路由保护算法(Routing Protection Algorithm with High Failure Protection Ratio,RPAHFPR),该算法融合了路径生成算法(Path Generation Algorithm,PGA)、旁支优先算法(Side Branch First Algorithm,SBF)和环路规避算法(Loop Avoidance Algorithm,LAA),可以同时解决已有路由保护方法面临的故障保护率低和路由环路问题;最后在大量的真实网络拓扑和模拟网络拓扑中验证了RPAHFPR方案的性能。与经典的NPC和U-TURN相比,RPAHFPR的故障保护率分别提高了20.85%和11.88%,并且在86.3%的拓扑中可以达到100%的故障保护率,在所有拓扑中可以达到99%以上的故障保护率。RPAHFPR的路径拉伸度基本接近1,不会引入过多的时间延迟。

关键词: 软件定义网络, 路由保护算法, 反向最短路径树, LFA规则, 备份路径, 网络单故障

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发