计算机科学 ›› 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
  • 通讯作者: 耿海军,男,博士,讲师,主要研究方向为软件定义网络、路由算法和网络体系结构,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 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: Real-time applications, Routing protection, Shortest path Tree, i-SPF, LFC rule, Network failures, Network availability

中图分类号: 

  • 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] 耿海军,张爽,尹霞. 互联网域内路由可用性综述[J]. 计算机科学, 2019, 46(7): 1-6.
[2] 耿海军. 基于优化链路权值的域内路由保护方案[J]. 计算机科学, 2019, 46(1): 143-147.
[3] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于关键节点的域内路由保护算法[J]. 计算机科学, 2018, 45(1): 183-187.
[4] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于逐跳方式的单链路故障保护算法[J]. 计算机科学, 2017, 44(7): 68-73.
[5] 周帆帆. 校园网络故障用户自助排查技术的探讨[J]. 计算机科学, 2014, 41(Z11): 461-462,470.
[6] 刘代波,侯孟书,武泽旭,屈鸿. 一种高效的最短路径树动态更新算法[J]. 计算机科学, 2011, 38(7): 96-99.
[7] . 最短路径树的马尔可夫有限阶段决策算法[J]. 计算机科学, 2007, 34(8): 266-270.
[8] . 反射式集成框架的规约描述方法研究[J]. 计算机科学, 2007, 34(8): 254-257.
[9] 黄靖 卢炎生 徐丽萍. 面向特征的反射式实时应用系统领域模型研究[J]. 计算机科学, 2006, 33(9): 245-249.
[10] 董彬 李全龙 徐晓飞 宿陆. 移动目标单源最短路径树更新的近似算法[J]. 计算机科学, 2006, 33(11): 222-224.
[11] 施笑安 周兴社 林奕. 支持服务质量的Linux内核设计与实现[J]. 计算机科学, 2005, 32(8): 216-218.
[12] 罗琼 张立臣. 针对实时数据库中隐蔽通道问题采取的安全策略[J]. 计算机科学, 2005, 32(7): 76-77.
[13] 夏梦芹 易发胜 曾家智. 互联网区域路由QoS机制研究[J]. 计算机科学, 2004, 31(11): 38-39.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[2] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[3] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .
[4] 李珊,饶文碧. 基于视频的矿井中人体运动区域检测[J]. 计算机科学, 2018, 45(4): 291 -295 .
[5] 韩奎奎,谢在鹏,吕鑫. 一种基于改进遗传算法的雾计算任务调度策略[J]. 计算机科学, 2018, 45(4): 137 -142 .
[6] 郑秀林,宋海燕,付伊鹏. MORUS-1280-128算法的区分分析[J]. 计算机科学, 2018, 45(4): 152 -156 .
[7] 朱淑芹,王文宏,李俊青. 针对基于感知器模型的混沌图像加密算法的选择明文攻击[J]. 计算机科学, 2018, 45(4): 178 -181, 189 .
[8] 郭帅,刘亮,秦小麟. 用户偏好约束的空间关键词范围查询处理方法[J]. 计算机科学, 2018, 45(4): 182 -189 .
[9] 童泽平,李涛,李立杰,任亮. 基于随机需求与产能限制的供应链协同优化研究[J]. 计算机科学, 2018, 45(4): 260 -265 .
[10] 梁俊斌,周翔,王田,李陶深. 移动低占空比无线传感网中数据收集的研究进展[J]. 计算机科学, 2018, 45(4): 19 -24, 52 .