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

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

中图分类号:

TP309.7

耿海军,张爽,尹霞. 互联网域内路由可用性综述[J]. 计算机科学, 2019, 46(7): 1-6. https://doi.org/10.11896/j.issn.1002-137X.2019.07.001

GENG Hai-jun,ZHANG Shuang,YIN Xia. Overview of Routing Availability in Intra-domain Routing Networks[J]. Computer Science, 2019, 46(7): 1-6. https://doi.org/10.11896/j.issn.1002-137X.2019.07.001

参考文献

[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