计算机科学 ›› 2019, Vol. 46 ›› Issue (8): 116-120.doi: 10.11896/j.issn.1002-137X.2019.08.019
耿海军1, 尹霞2
GENG Hai-jun1, YIN Xia2
摘要: 学术界提出利用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拥有相同的故障保护率。
中图分类号:
[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. |
|