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

doi:10.11896/j.issn.1002-137X.2019.08.019

Abstract

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

CLC Number:

TP393

GENG Hai-jun, YIN Xia. Efficient Intra-domain Routing Protection Algorithm Based on i-SPF[J].Computer Science, 2019, 46(8): 116-120.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

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

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 8

Metrics

Comments

Recommended 0

[1]	GENG Hai-jun, WANG Wei, YIN Xia. Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks [J]. Computer Science, 2022, 49(2): 329-335.
[2]	GENG Hai-jun,ZHANG Shuang,YIN Xia. Overview of Routing Availability in Intra-domain Routing Networks [J]. Computer Science, 2019, 46(7): 1-6.
[3]	GENG Hai-jun. Intra-domain Routing Protection Scheme by Optimizing Link Weight [J]. Computer Science, 2019, 46(1): 143-147.
[4]	GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Intra-domain Routing Protection Algorithm Based on Critical Nodes [J]. Computer Science, 2018, 45(1): 183-187.
[5]	GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Single-link Failure Protection Algorithm Based on Hop-by-Hop Routing [J]. Computer Science, 2017, 44(7): 68-73.
[6]	LIU Dai-bo,HOU Meng-shu,WU Ze-xu,QU Hong. Efficient Dynamic Algorithm for Computation of Shortest Path Tree [J]. Computer Science, 2011, 38(7): 96-99.
[7]	. [J]. Computer Science, 2007, 34(8): 266-270.
[8]	DONG Bin, LI Quan-Long ,XU Xiao-Fei ,SU Lu （Dept. of Computer Science ＆ Engineering, Harbin Institute of Technology, Harbin 150001）. [J]. Computer Science, 2006, 33(11): 222-224.