互联网域内路由可用性综述

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

Abstract

Abstract: Route availability refers to the probability that a user can get the requested service.With the development of the Internet,a large number of real-time services have emerged,and the requirements for the timeliness of the network is becoming higher and higher,and high demands have been placed on the “self-repairing ability” of the Internet.However,network faults occur frequently,and routing loops and long convergence times may occur during the process of repairing network failures.The repair time is usually between several seconds and tens of seconds,which cannot meet the real-time requirements of the Internet.Therefore,improving routing availability has become an urgent problem to be solved.This paper summarized and analyzed the existing schemes to improve routing availability,and divided these schemes into two major categories,namely passive protection scheme and route protection scheme.The research results at home and abroad were introduced in detail,the advantages and disadvantages of each program were compared,the main contributions and shortcomings of these programs were summarized and analyzed,and the research directions were proposed for further research.

Key words: Network failure, Routing availability, Routing loop, Routing protection scheme

CLC Number:

TP309.7

GENG Hai-jun,ZHANG Shuang,YIN Xia. Overview of Routing Availability in Intra-domain Routing Networks[J].Computer Science, 2019, 46(7): 1-6.

References

[1]CLARK D.The design philosophy of the DARPA internet protocols[J].Acm Sigcomm Computer Communication Review,1988,18(4):106-114.
[2]ALBERT R,JEONG H,BARAB SI A L.Internet:Diameter of the World-Wide Web[J].Nature,1999,401(6):130-131.
[3]TURKLE S.Life on the Screen:Identity in the Age of the Internet[J].Science,1997,23(2):123-149.
[4]VARSHNEY U,SNOW A,MCGIVERN M,et al.Voice over IP [J].Communications of the Acm,2002,45(1):89-96.
[5]GOODE B.Voice over internet protocol (voip) [J].Proceedings of the IEEE,2002,90(9):1495-1517.
[6]DREW P,GALLON C.Next-generation voip network architecture [C]∥Proceedings of Multiservice Switching Forum.New York:IEEE Press,2003:1-19.
[7]YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal Link-Disjoint Node-“Somewhat Disjoint” Paths [C]∥Proceedings of International Conference on Network Protocols (ICNP).New York:IEEE Press,2016:1-10.
[8]KWONG K W,GAO L,ZHANG Z L.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556.
[9]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.
[10]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.
[11]XU A,BI J,ZHANG B.Failure Inference for shortening traffic Detours[C]∥Proceedings of IEEE/ACM International Symposium on Quality of Service (IWQoS).New York:IEEE Press,2016:1-10.
[12]TAPOLCAI J,RETVARI G,BABARCZI P,et al.Scalable and Efficient Multipath Routing:Complexity and Algorithms[C]∥Proceedings of International Conference on Network Protocols (ICNP).New York:IEEE Press,2015:376-385.
[13]ZHENG J Q,XU H,ZHU X J,et al.We’ve Got You Covered:Failure Recovery with Backup Tunnels in Traffic Engineering[C]∥Proceedings of International Conference on Network Protocols (ICNP).New York:IEEE Press,2016:1-10.
[14]YANG Y,XU M,LI Q.Tunneling on demand:A lightweight approach for IP fast rerouting against multi-link failures [C]∥Proceedings of IEEE/ACM International Symposium on Quality of Service (IWQoS).New York:IEEE Press,2016:1-6.
[15]ANTONAKOPOULOS S,BEJERANO Y,KOPPOL P.Full Protection Made Easy:The DisPath IP Fast Reroute Scheme [J].IEEE/ACM Transactions on Networking,2016,23(4):1229-1242.
[16]MARKOPOULOU A,IANNACCONE G,BHATTACHARYYA S,et al.Characterization of failures in an operational ip backbone network[J].IEEE/ACM Transactions on Networking,2008,16(4):749-762.
[17]HOU M J,WANG D,XU M W,et al.Selective protection:A Cost-Efficient Backup Scheme for Link State Routing[C]∥Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS).New York:IEEE Press,2009:68-75.
[18]MOY J.RFC 2328:OSPF Version 2.USA:Soc Internet Society,1998.
[19]BASU A,RIECKE J.Stability issues in OSPF routing[J].Acm Sigcomm Computer Communication Review,2001,31(4):225-236.
[20]CLAD F,MERINDOL P,VISSICCHIO S,et al.Graceful router updates in link-state protocols[C]∥Proceedings of International Conference on Network Protocols (ICNP).New York:IEEE Press,2013:1-10.
[21]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.
[22]PAL S,GADDE R,LATCHMAN H A.On the reliability of voice over ip (VoIP) telephony [C]∥Proceedings of International Conference on Computing,Communications and Control Technologies.New York:IEEE Press,2011:1-8.
[23]XU M W,HOU M J,WANG D,et al.An efficient critical protection scheme for intra-domain routing using link characteristics[J].Computer Networks,2013,57(1):117-133.
[24]XU A,BI J,ZHANG B B,et al.Failure Inference for shortening traffic Detours[C]∥Proceedings of IEEE/ACM International Symposium on Quality of Service (IWQoS).New York:IEEE Press,2017:1-10.
[25]KWONG K W,GAO L,ZHANG Z L.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556.
[26]PENG Q,WALID A,LOW S H.Multipath TCP algorithms: theory and design[C]∥Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems.2013:305-316.
[27]GRAN E G,DREIBHOLZ T,KVALBEIN A.NorNet Core-A multihomed research testbed[J].Computer Networks,2014,61(C):75-87.
[28]ATLAS A,KEBLER R,KONSTANTYNOWICZ M,et al.An Architecture for IP/LDP Fast-Reroute Using Maximally Redundant Trees[S].USA:ISOC Internet Society,2015.
[29]ENYEDI G,CSASZAR A,ATLAS A,et al.Algorithms for computing Maximally Redundant Trees for IP/LDP Fast-Reroute[S].USA:ISOC Internet Society,2013.
[30]XU M W,LI Q,PANG L T,et al.The model and algorithm on network failure and self-healing Routing[J].Scientia Sinica,2010,40(7):943-953.(in Chinese)
徐明伟,李琦,潘凌涛,等.网络故障及自愈路由模型和算法[J].中国科学:信息科学,2010,40(7):943-953.
[31]XU M W,YANG Y,LI Q.Survey of Intra-Domain Self-Healing Routing[J].Acta Electronica Sinica,2009,37(12):2753-2761.(in Chinese)
徐明伟,杨芫,李琦.域内自愈路由研究综述[J].电子学报,2009,37(12):2753-2761.
[32]LI Q.Availability and Scalability Issues in Internet Routing:A Weak Forwarding Correctness Approach [D].Beijing:Tsinghua University,2013.(in Chinese)
李清.基于弱转发的互联网路由可用性和扩展性研究[D].北京:清华大学,2013.
[33]LEE S,YU Y,NELAKUDITI S,et al.Proactive vs Reactive Approaches to Failure Resilient Routing[C]∥Proceedings of IEEE International Conference on Computer Communication (INFOCOM).New York:IEEE Press,2004:1-11.
[34]GENG H J.Research on Routing Metric based Intra-Domain Multipath Routing [D].Beijing:Tsinghua University,2015.(in Chinese)
耿海军.基于路由度量的域内多路径路由研究[D].北京:清华大学,2015.
[35]NARVAEZ P.Routing Reconfiguration in IP Networks[D].Massachusetts:Massachusetts Institute of Technology,2000.
[36]NARVAEZ P,SIU K,TZENG H.New dynamic algorithms for shortest path tree computation[J].IEEE/ACM Transactions on Networking (TON),2000,8(6):734-746.
[37]NARVAEZ P,SIU K,TZENG H.New dynamic spt algorithm based on a ball-and-string model[J].IEEE/ACM Transactions on Networking (TON),2001,9(6):706-718.
[38]FRANCOIS P,SHAND M,BONAVENTURE O.Disruption free topology reconfiguration in OSPF networks[C]∥Procee-dings of IEEE International Conference on Computer Communication (INFOCOM).New York:IEEE Press,2007:89-97.
[39]FORTZ B,THORUP M.Optimizing OSPF/IS-IS weights in a changing world[J].IEEE Journal on Selected Areas in Communications,2002,20(4):756-767.
[40]NUCCI A,SCHROEDER B,BHATTACHARYYA S,et al.IGP Link Weight Assignment for Transient Link Failures[C]∥Proceedings of the International Teletraffic Congress.New York:IEEE Press,2003:321-330.
[41]FERGUSON D,MOY J,COLTUN R.RFC 2740:OSPF for IPv6[S].USA:ISOC Internet Society,1999.
[42]ATLAS A,ZININ A.Basic specification for ip fast reroute: Loop-free alternates[S].USA:ISOC Internet Society,2008.
[43]ATLAS A.U-turn alternates for IP/LDP fast-reroute[S]. USA:ISOC Internet Society,2006.
[44]GENG H,SHI X,WANG Z,et al.A hop-by-hop dynamic distributed multipath routing mechanism for link state network[J].Computer Communications,2018,116:225-239.
[45]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[C]∥Proceedings of ACM Special Interest Group on Data Communication (SIGCOMM).2006:159-170.
[46]SCHOLLMEIERS G,CHARZINSKI J,KIRSTADTER A,et al. Improving the resilience in IP networks[C]∥Proceedings of IEEE HPSR.New York:IEEE Press,2003:91-96.
[47]KVALBEIN A,HANSEN A F,GJESSING S,et al.Fast ip network recovery using multiple routing configurations[C]∥Proceedings of IEEE International Conference on Computer Communication (INFOCOM).New York:IEEE Press,2007:1-11.
[48]LAKSHMINARAYANAN K,CAESAR M,RANGAN M,et al. Achieving convergence-free routing using failure-carrying packets[J].Acm Sigcomm Computer Communication Review,2007,37(4):241-252.
[49]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.
[50]ZHANG B,WU J,BI J.RPFP:IP fast reroute with providing complete protection and without using tunnels[C]∥Proceedings of IEEE/ACM International Symposium on Quality of Service (IWQoS).New York:IEEE Press,2013:1-10.
[51]YANG B,LIU J,SHENKER S,et al.Keep forwarding:Towards k-link failure resilient routing[C]∥Proceedings of IEEE International Conference on Computer Communication (INFOCOM).New York:IEEE Press,2014:1617-1625.
[52]ENYEDI G,R TV RI G,SZIL GYI P,et al.IP Fast Re-Route:Lightweight Not-Via without Additional Addresses[C]∥Proceedings of IEEE International Conference on Computer Communication (INFOCOM).New York:IEEE Press,2009:2771-2775.
[53]GENG H,SHI X,YIN X,et al.An efficient link protection scheme for link-state routing networks[C]∥Proceedings of IEEE International Conference on Communications (ICC).New York:IEEE Press,2015:6024-6029.
[54]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.
[55]BANERJEE G,SIDHU D.Comparative analysis of path computation techniques for MPLS traffic engineering[J].Computer Networks,2002,40(1):149-165.
[56]SOMMERS J,ERIKSSON B,BARFORD P.On the prevalence and characteristics of MPLS deployments in the open Internet[C]∥Proceedings of ACM Special Interest Group on Data Communication (SIGCOMM).New York:ACM Press,2011:445-462.
[57]CHRIS B,GAURAV A,ANIL N,et al.Maximally Redundant Trees in Segment Routing[J].Chinese Journal of Engineering Design,2016,94(1):33-42.
[58]CIANFRANI A,LISTANTI M,POLVERINI M.Incremental Deployment of Segment Routing Into an ISP Network:a Traffic Engineering Perspective[J].IEEE/ACM Transactions on Networking,2017,25(5):3146-3160.
[59]HARTERT R,VISSICCHIO S,SCHAUS P,et al.A Declarative and Expressive Approach to Control Forwarding Paths inCar-rier-Grade Networks[J].Acm Sigcomm Computer Communication Review,2015,45(5):15-28.
[60]GENG H J,LIU J Q,YIN X.Single Node Failure Routing Protection Algorithm Based on Segment Routing[J].Journal of Tsinghua University(Science and Technology),2018,58(8):710-714.(in Chinese)
耿海军,刘洁琦,尹霞.基于段路由的单节点故障路由保护算法[J].清华大学学报(自然科学版),2018,58(8):710-714.
[61]HOU M J.Research on Internet Routing Protection[D].Bei- jing:Tsinghua University,2015.(in Chinese)
侯美佳.互联网路由保护研究[D].北京:清华大学,2015.
[62]GENG H J,SHI X G,WANG Z L,et al.Intra-domain Routing Protection Algorithm Based on Critical Nodes[J].Computer Science,2018,45 (1):183-187.(in Chinese)
耿海军,施新刚,王之梁,等.基于关键节点的域内路由保护算法[J].计算机科学,2018,45(1):183-187.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Overview of Routing Availability in Intra-domain Routing Networks

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 0

[1]	GENG Hai-jun, YIN Xia. Efficient Intra-domain Routing Protection Algorithm Based on i-SPF [J]. Computer Science, 2019, 46(8): 116-120.
[2]	GENG Hai-jun. Intra-domain Routing Protection Scheme by Optimizing Link Weight [J]. Computer Science, 2019, 46(1): 143-147.
[3]	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.
[4]	LI Dan,WANG Bin-qiang,LIU Qiang,MA Hai-long. Analysis for Loop-freeness of Multipath Inter-domain Routing Based on Locator/ID Decoupling Architecture [J]. Computer Science, 2011, 38(1): 130-135.