计算机科学 ›› 2019, Vol. 46 ›› Issue (8): 116-120.doi: 10.11896/j.issn.1002-137X.2019.08.019

• 网络与通信 • 上一篇    下一篇

基于增量最短路径优先的域内高效路由保护算法

耿海军1, 尹霞2   

  1. (山西大学软件学院 太原030006)1
    (清华大学信息科学技术学院计算机科学与技术系 北京100084)2
  • 收稿日期:2018-02-20 出版日期:2019-08-15 发布日期:2019-08-15
  • 通讯作者: 耿海军,男,博士,讲师,主要研究方向为软件定义网络、路由算法和网络体系结构,E-mail:ghj123025449@163.com
  • 作者简介:尹霞女,博士,教授,主要研究方向为网络体系结构、路由算法、SDN、协议测试
  • 基金资助:
    国家自然科学基金(61702315),网络与交换技术国家重点实验室(北京邮电大学)开放课题(SKLNST-2018-1-19)

Efficient Intra-domain Routing Protection Algorithm Based on i-SPF

GENG Hai-jun1, YIN Xia2   

  1. (School of Software Engineering,Shanxi University,Taiyuan 030006,China)1
    (Department of Computer Science & Technology,School of Information Science and Technology,Tsinghua University,Beijing 100084,China)2
  • Received:2018-02-20 Online:2019-08-15 Published:2019-08-15

摘要: 学术界提出利用LFC(Loop-Free Criterion,LFC)规则来解决网络中所有可能出现的单链路故障情形,但是已有的针对LFC的实现方式的计算开销随着网络节点平均度的增加而增加,给路由器带来了大量的额外负担。针对该问题,文中研究如何降低LFC实现方式的计算开销,提出了一种基于增量最短路径优先(Incremental Shortest Path First,i-SPF)的域内高效路由保护算法(Efficient Intra-domain Routing Protection Algorithm Based on i-SPF,ERPISPF)。理论证明ERPISPF的计算开销远远小于构造一棵最短路径树的计算开销,并且可以为任意源-目的对计算出所有符合LFC规则的下一跳集合。实验结果表明,与LFC方案相比,ERPISPF的计算开销降低了93%左右,并且与LFC拥有相同的故障保护率。

关键词: LFC规则, 路由保护, 路由可用性, 实时应用, 网络故障, 增量最短路径优先, 最短路径树

Abstract: LFC(Loop-Free Criterion)has been proposed to cope with all the single link failure scenarios.However,the existing LFC implementation algorithms are time-consuming and require a large amount of router CPU resources.Therefore,this paper studied how to reduce the computational overhead of the LFC implementation,and proposed an efficient Intra-domain routing protection algorithm based on i-SPF (ERPISPF).Theoretical analysis indicates that the time complexity of ERPISPF is less than that of constructing a shortest path tree,and ERPISPF can compute all the valid LFC next-hop sets for any source-destination pairs.The experiment results show that ERPISPF reduce more than 93% computation overhead compared with the LFC,and can provide the same protection ratio with LFC

Key words: i-SPF, LFC rule, Network availability, Network failures, Real-time applications, Routing protection, Shortest path Tree

中图分类号: 

  • TP393
[1]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.
[2]XU A,BI J,ZHANG B.Failure Inference for shortening traffic Detours[C]∥Proceedings of the International Symposium on Quality of Service.Beijing,China,2016:1-10.
[3]KRIST P.Scalable and Efficient Multipath Routing:Complexity and Algorithms[C]∥Proceedings of the IEEE International Conference on Network Protocols.San Francisco,CA,2015:376-385.
[4]YANG Y,XU M,LI Q.Tunneling on demand:A lightweight approach for IP fast rerouting against multi-link failures[C]∥Proceedings of the International Symposium on Quality of Ser-vice.Beijing,China,2016:1-10.
[5]ELHOURANI T,GOPALAN A,RAMASUBRAMANIAN S. IP fast rerouting for multi-link failures[C]∥Proceedings of the Conference on Computer Communications.Toronto,Canada,2014:2148-2156.
[6]MARKOPOULOU A,IANNACCONE G,BHATTACHAR- YYA S.Characterization of failures in an operational ip backbone network[J].IEEE/ACM Transactions on Networking,2008,16(4):749-762.
[7]GOPALAN A,RAMASUBRAMANIAN S.IP Fast Rerouting and Disjoint Multipath Routing With Three Edge-Independent Spanning Trees[J].IEEE/ACM Transactions on Networking,2016,24(3):1336-1349.
[8]XU M,HOU M,WANG D,et al.An efficient critical protection scheme for intra-domain routing using link characteristics[J].Computer Networks,2013,57(1):117-133.
[9]FRANCOIS P,BONAVENTURE O.Avoiding transient loops during the convergence of link-state routing protocols[J].IEEE/ACM Transactions on Networking,2007,15(6):1280-1292.
[10]NELAKUDITI S,LEE S,YU Y,et al.Fast local rerouting for handling transient link failures[J].IEEE/ACM Transactions on Networking,2007,15(2):359-372.
[11]YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal Link-Disjoint Node-“Somewhat Disjoint” Paths[C]∥Proceedings of the IEEE International Conference on Network Protocols.Singapore,2016:1-10.
[12]KWONG K,GAO L,GUERIN R,et al.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556.
[13]LEE S,YU Y,NELAKUDITI S,et al.Proactive vs Reactive Approaches to Failure Resilient Routing[C]∥Proceedings of the IEEE International Conference on Computer Communications.Hong Kong,China,2004:1-9.
[14]FRANCOIS P,BONAVENTURE O.Avoiding transient loops during the convergence of link-state routing protocols[J].IEEE/ACM Transactions on Networking,2007,15(6):1280-1292.
[15]FRANCOIS P,FILSFILS C,EVANS J,et al.Achieving sub-se- cond igp convergence in large ip networks[J].Computer Communication Review,2005,35(3):35-44.
[16]CLAD F,MERINDOL P,VISSICCHIO S,et al.Graceful Router Updates for Link-State Protocols[C]∥Proceedings of the IEEE International Conference on Network Protocols.Göttingen,Germany,2013:1-10.
[17]ZHANG B,WU J,BI J.RPFP:IP fast reroute with providing complete protection and without using tunnels[C]∥Proceedings of the International Symposium on Quality of Service.Mon-treal,Canada,2013:1-10.
[18]XU M,YANG Y,LI Q.Selecting Shorter Alternate Paths for Tunnel-based IP Fast ReRoute in Linear Time[J].Computer Networks,2012,56(2):845-857.
[19]ENYEDI G,RÉTVÁRI G,SZILÁGYI P,et al.IP Fast Re- Route:Lightweight Not-Via without Additional Addresses[C]∥Proceedings of the Conference on Computer Communications.Rio de Janeiro,Brazil,2009:157-168.
[20]ZHANG M,LIU B,ZHANG B.Multi-Commodity Flow Traffic Engineering with Hybrid MPLS/OSPF Routing[C]∥Procee-dings of the Global communications Conference.Honolulu,USA,2009:1-6.
[21]ATLAS A K,ZININ A.Basic Specification for IP Fast Reroute:Loop-Free Alternates[S].RFC 5286,2008:1-31.
[22]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[C]∥Proceedings of the ACM Special Inte-rest Group on Data Communication.Pisa,Italy,2006:159-170.
[23]GENG H J,SHI X G,WANG Z L,et al.Efficient implementation method for LFA[J].Journal of Software,2018,29(12):3904-3920.(in Chinese) 耿海军,施新刚,王之梁,等.LFA算法的一种高效实现方法[J].软件学报,2018,29(12):3904-3920.
[24]Junos OS Routing Protocols Configuration Guide[OL].ht- tps://www.juniper.net/documentation/en_US/junos12.3/information-products/topic-collections/release-notes/12.3/junos-release-notes-12.3.pdf.
[25]MARKOPOULOU M P,FRANCOIS P,BONAVENTURE O,et al.An efficient algorithm to enable path diversity in link state routing networks [J].Computer Networks,2011,55(5):1132-1149.
[26]GENG H,SHI X,YIN X,et al.Dynamic distributed algorithm for computing multiple next-hops on a tree[C]∥Proceedings of the IEEE International Conference on Network Protocols.Göttingen,Germany,2013:1-10.
[27]ENYEDI G,RÉTVÁRI G,SZILÁGYI P,et al. IP Fast Re-Route:Lightweight Not-Via∥Proceedings of the IEEE International Conference on Computer Communications.Rio De Janeiro,Brazil,2009:1-9.
[28]RÉTVÁRI G,et al.IP fast ReRoute:Loop Free Alternates revisited[C]∥Proceedings of the IEEE Conference on Computer Communications.Shanghai,China,2011:2948-2956.
[29]RETVARI G,CSIKOR L,TAPOLCAI J,et al.Optimizing IGP link costs for improving IP-level resilience[J].Computer Communications,2013,36(6):645-655.
[30]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring isp topologies with rocketfuel[C]∥IEEE/ACM Transactions on Networking.2004:2-16.
[1] 耿海军, 王威, 尹霞.
基于混合软件定义网络的单节点故障保护方法
Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks
计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[2] 耿海军,张爽,尹霞.
互联网域内路由可用性综述
Overview of Routing Availability in Intra-domain Routing Networks
计算机科学, 2019, 46(7): 1-6. https://doi.org/10.11896/j.issn.1002-137X.2019.07.001
[3] 耿海军.
基于优化链路权值的域内路由保护方案
Intra-domain Routing Protection Scheme by Optimizing Link Weight
计算机科学, 2019, 46(1): 143-147. https://doi.org/10.11896/j.issn.1002-137X.2019.01.022
[4] 耿海军,施新刚,王之梁,尹霞,尹少平.
基于关键节点的域内路由保护算法
Intra-domain Routing Protection Algorithm Based on Critical Nodes
计算机科学, 2018, 45(1): 183-187. https://doi.org/10.11896/j.issn.1002-137X.2018.01.032
[5] 耿海军,施新刚,王之梁,尹霞,尹少平.
基于逐跳方式的单链路故障保护算法
Single-link Failure Protection Algorithm Based on Hop-by-Hop Routing
计算机科学, 2017, 44(7): 68-73. https://doi.org/10.11896/j.issn.1002-137X.2017.07.012
[6] 周帆帆.
校园网络故障用户自助排查技术的探讨
Study on Campus Network Faults for Investigation Technology of User Self-service
计算机科学, 2014, 41(Z11): 461-462.
[7] 刘代波,侯孟书,武泽旭,屈鸿.
一种高效的最短路径树动态更新算法
Efficient Dynamic Algorithm for Computation of Shortest Path Tree
计算机科学, 2011, 38(7): 96-99.
[8] .
最短路径树的马尔可夫有限阶段决策算法

计算机科学, 2007, 34(8): 266-270.
[9] .
反射式集成框架的规约描述方法研究

计算机科学, 2007, 34(8): 254-257.
[10] 黄靖 卢炎生 徐丽萍.
面向特征的反射式实时应用系统领域模型研究

计算机科学, 2006, 33(9): 245-249.
[11] 董彬 李全龙 徐晓飞 宿陆.
移动目标单源最短路径树更新的近似算法

计算机科学, 2006, 33(11): 222-224.
[12] 施笑安 周兴社 林奕.
支持服务质量的Linux内核设计与实现

计算机科学, 2005, 32(8): 216-218.
[13] 罗琼 张立臣.
针对实时数据库中隐蔽通道问题采取的安全策略

计算机科学, 2005, 32(7): 76-77.
[14] 夏梦芹 易发胜 曾家智.
互联网区域路由QoS机制研究

计算机科学, 2004, 31(11): 38-39.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!