一种逐跳方式的域内单节点故障保护算法
|
摘要
研究表明,网络中的故障频繁发生.当网络出现故障时,目前互联网部署的域内路由协议需要经历收敛过程,在此期间将有大量报文丢失,导致用户体验下降,严重影响了因特网服务提供商(ISP,Internet Service Provider)的服务质量.因此,提高域内路由可用性成为亟待解决的一个科学问题.为了提升路由可用性,业界提出了快速重路由的基本框架(IP Fast Re-Route,IPFRR),基于该框架的解决方案可以减少路由协议收敛过程中报文丢失情况,然而该方案并不能100%保护网络中所有可能的单节点故障.因此,本文提出了一种基于逐跳方式的针对单节点故障的全保护方案,该算法具有如下特点:1)实现简单; 2)支持逐跳转发方式; 3)支持增量部署,因此适合在实际中部署.实验结果表明,该方案不仅可以100%保护网络中所有单节点故障情形的路由保护算法,并且具有较小的路径拉伸度.
Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur,the current deployed intra-domain routing protocol need to re-convergence. During the process of re-convergence,the packets may be lost due to inconsistent routing information,greatly reducing the Internet routing availability,seriously affecting the ISP's service quality and reputation. Therefore,improving the Internet routing availability has become an urgent problem. Therefore,improving the Internet routing availability has become an urgent problem. A framework which is called IPFRR( IP Fast ReRoute) has been proposed to enhance the Internet routing availability,which can effectively reduce packet loss when failures occur. However,the scheme cannot supply complete protection against all single-node failure scenarios. In this work,we aim for hop-by-hop routing algorithm which can provide complete protection against all such a single-node failure scenarios. The algorithm has the following characteristics: 1) simple; 2) hop by hop routing; 3) incremental deployment,so it is suitable for deployment on today's Internet. The experimental results showthat the scheme can not only provide complete protection against all such a single-node failure scenarios,but also have smaller path stretch.
Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur,the current deployed intra-domain routing protocol need to re-convergence. During the process of re-convergence,the packets may be lost due to inconsistent routing information,greatly reducing the Internet routing availability,seriously affecting the ISP's service quality and reputation. Therefore,improving the Internet routing availability has become an urgent problem. Therefore,improving the Internet routing availability has become an urgent problem. A framework which is called IPFRR( IP Fast ReRoute) has been proposed to enhance the Internet routing availability,which can effectively reduce packet loss when failures occur. However,the scheme cannot supply complete protection against all single-node failure scenarios. In this work,we aim for hop-by-hop routing algorithm which can provide complete protection against all such a single-node failure scenarios. The algorithm has the following characteristics: 1) simple; 2) hop by hop routing; 3) incremental deployment,so it is suitable for deployment on today's Internet. The experimental results showthat the scheme can not only provide complete protection against all such a single-node failure scenarios,but also have smaller path stretch.
引文
[1]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(2):225-239.
[2]Xu M,Li Q,Pan L,et al.Minimum protection cost tree:a tunnelbased IP fast reroute scheme[J].Computer Communications,2012,35(17):2082-2092.
[3]Antonakopoulos S,Bejerano Y,Koppol P.Full protection made easy:the DisPath IP fast reroute scheme[J].IEEE/ACMTransactions on Networking,2015,23(4):1229-1242.
[4]Xu A,Bi J,Zhang B,et al.Failure inference for shortening traffic detours[C].IEEE/ACMInternational Symposium on Quality of Service,2017:1-10.
[5]Markopoulou A,Iannaccone G,Bhattacharyya S,et al.Characterization of failures in an operational IP backbone network[J].IEEE/ACMTransactions on Networking,2008,16(4):749-762.
[6]Jose Yallouz,Ori Rottenstreich,Péter Babarczi.Optimal link-disjoint node-"somewhat disjoint"paths[C].IEEE International Conference on Network Protocols,2016:1-10.
[7]Yang B,Liu J,Shenker S,et al.Keep Forwarding:towards k-link failure resilient routing[C].IEEE International Conference on Computer Communications,2014:1617-1625.
[8]Goode B.Voice over internet protocol(voip)[C].Proceedings of the IEEE,2002,90(9):1495-1517.
[9]Vo H Q,Lysne O,Kvalbein A.Routing with joker links for maximized robustness[C].IFIP Networking Conference,2013:1-9.
[10]Geng H,Shi X,Yin X,et al.Algebra and algorithms for multipath QoS routing in link state networks[J].Journal of Communications&Networks,2017,19(2):189-200.
[11]Kwong K W,Gao L,Guerin R,et al.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACMTransactions on Networking,2011,19(5):1543-1556.
[12]He J,Rexford J.Toward internet-wide multipath routing[J].IEEENetwork,2008,22(2):16-21.
[13]Li Qing.Availability and scalability issues in Internet routing:a weak forwarding correctness approach[D].Beijing:Tsinghua University,2013.
[14]Yang Yuan.Path constraint-based intra-domain routing for Internet availability and energy-efficiency[D].Beijing:Tsinghua University,2015.
[15]Tapolcai J,Retvari G,Babarczi P,et al.Scalable and efficient multipath routing:complexity and algorithms[C].International Conference on Network Protocols,2016:376-385.
[16]Moy J.RFC 2328:Ospf version 2[Z].Reston:IETF,1998.
[17]Sridharan A,Guerin R,Diot C.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks[J].IEEE/ACMTransactions on Networking,2005,13(2):234-247.
[18]Atlas A K,Zinin A.Basic specification for IP fast reroute:loop-free alternates[R].RFC 5286,2008.
[19]Retvari G,Tapolcai J,Enyedi G,et al.Ip fast reroute:loop free alternates revisited[C].IEEE International Conference on Computer Communications,2011:2948-2956.
[20]Francois P,Bonaventure O.An evaluation of ip-based fast reroute techniques[C].Proceedings of the ACMConference on Emerging Network Experiment and Technology,2005:244-245.
[21]Geng H,Shi X,Yin X,et al.Algebra and algorithms for efficient and correct multipath QoS routing in link state networks[C].IEEEInternational Symposium on Quality of Service,2016:261-266.
[22]Geng Hai-jun,Shi Xin-gang,Yin Xia,et al.Dynamic distributed algorithm for computing multiple next-hops on a tree[C].Proceedings of the 21st IEEE International Conference on Network Protocols,2013:1-10.
[23]Geng Hai-jun,Shi Xin-gang,Yin Xia,et al.MLSA:a link-state multipath routing algorithm[C].Proceedings of the 18th IEEESymposium on Computers and Communications,2013:330-335.
[24]Atlas A.U-turn alternates for Ip/LDp fast-reroute[Z].IETF Draft,2006.
[25]Enyedi G,Szilagyi P,Retvari G,et al.Ip fast reroute:Lightweight not-via without additional addresses[C].IEEE International Conference on Computer Communications,2009:2771-2775.
[26]Menth M,Hartmann M,Martin R,et al.Loop-free alternates and not-via addresses:a proper combination for IP fast reroute[J].Computer Networks,2010,54(8):1300-1315.
[27]Geng H,Shi X,Yin X,et al.An efficient link protection scheme for link-state routing networks[C].IEEE International Conference on Communications,2015:6024-6029.
[28]Schollmeier G,Charzinski J,Kirstadter A,et al.Improving the resilience in ip networks[C].High Performance Switching and Routing,2003:91-96.
[29]Yang X,Wetherall D.Source selectable path diversity via routing deflections[J].Acm Sigcomm Computer Communication Review,2006,36(4):159-170.
[30]Spring N,Mahajan R,Wetherall D,et al.Measuring isp topologies with rocketfuel[J].Acm Sigcomm Computer Communication Review,2002,32(4):133-145.
[31]Medina A,Lakhina A,Matta I,et al.Brite:an approach to universal topology generation[C].IEEE International Workshop on Modeling,Analysis,and Simulation of Computer and Telecommunication Systems,2001:346-353.
[13]李清.基于弱转发的互联网路由可用性和扩展性研究[D].北京;清华大学,2013.
[14]杨芫.基于路径约束的互联网域内路由可用性与节能研究[D].北京:清华大学,2015.
[2]Xu M,Li Q,Pan L,et al.Minimum protection cost tree:a tunnelbased IP fast reroute scheme[J].Computer Communications,2012,35(17):2082-2092.
[3]Antonakopoulos S,Bejerano Y,Koppol P.Full protection made easy:the DisPath IP fast reroute scheme[J].IEEE/ACMTransactions on Networking,2015,23(4):1229-1242.
[4]Xu A,Bi J,Zhang B,et al.Failure inference for shortening traffic detours[C].IEEE/ACMInternational Symposium on Quality of Service,2017:1-10.
[5]Markopoulou A,Iannaccone G,Bhattacharyya S,et al.Characterization of failures in an operational IP backbone network[J].IEEE/ACMTransactions on Networking,2008,16(4):749-762.
[6]Jose Yallouz,Ori Rottenstreich,Péter Babarczi.Optimal link-disjoint node-"somewhat disjoint"paths[C].IEEE International Conference on Network Protocols,2016:1-10.
[7]Yang B,Liu J,Shenker S,et al.Keep Forwarding:towards k-link failure resilient routing[C].IEEE International Conference on Computer Communications,2014:1617-1625.
[8]Goode B.Voice over internet protocol(voip)[C].Proceedings of the IEEE,2002,90(9):1495-1517.
[9]Vo H Q,Lysne O,Kvalbein A.Routing with joker links for maximized robustness[C].IFIP Networking Conference,2013:1-9.
[10]Geng H,Shi X,Yin X,et al.Algebra and algorithms for multipath QoS routing in link state networks[J].Journal of Communications&Networks,2017,19(2):189-200.
[11]Kwong K W,Gao L,Guerin R,et al.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACMTransactions on Networking,2011,19(5):1543-1556.
[12]He J,Rexford J.Toward internet-wide multipath routing[J].IEEENetwork,2008,22(2):16-21.
[13]Li Qing.Availability and scalability issues in Internet routing:a weak forwarding correctness approach[D].Beijing:Tsinghua University,2013.
[14]Yang Yuan.Path constraint-based intra-domain routing for Internet availability and energy-efficiency[D].Beijing:Tsinghua University,2015.
[15]Tapolcai J,Retvari G,Babarczi P,et al.Scalable and efficient multipath routing:complexity and algorithms[C].International Conference on Network Protocols,2016:376-385.
[16]Moy J.RFC 2328:Ospf version 2[Z].Reston:IETF,1998.
[17]Sridharan A,Guerin R,Diot C.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks[J].IEEE/ACMTransactions on Networking,2005,13(2):234-247.
[18]Atlas A K,Zinin A.Basic specification for IP fast reroute:loop-free alternates[R].RFC 5286,2008.
[19]Retvari G,Tapolcai J,Enyedi G,et al.Ip fast reroute:loop free alternates revisited[C].IEEE International Conference on Computer Communications,2011:2948-2956.
[20]Francois P,Bonaventure O.An evaluation of ip-based fast reroute techniques[C].Proceedings of the ACMConference on Emerging Network Experiment and Technology,2005:244-245.
[21]Geng H,Shi X,Yin X,et al.Algebra and algorithms for efficient and correct multipath QoS routing in link state networks[C].IEEEInternational Symposium on Quality of Service,2016:261-266.
[22]Geng Hai-jun,Shi Xin-gang,Yin Xia,et al.Dynamic distributed algorithm for computing multiple next-hops on a tree[C].Proceedings of the 21st IEEE International Conference on Network Protocols,2013:1-10.
[23]Geng Hai-jun,Shi Xin-gang,Yin Xia,et al.MLSA:a link-state multipath routing algorithm[C].Proceedings of the 18th IEEESymposium on Computers and Communications,2013:330-335.
[24]Atlas A.U-turn alternates for Ip/LDp fast-reroute[Z].IETF Draft,2006.
[25]Enyedi G,Szilagyi P,Retvari G,et al.Ip fast reroute:Lightweight not-via without additional addresses[C].IEEE International Conference on Computer Communications,2009:2771-2775.
[26]Menth M,Hartmann M,Martin R,et al.Loop-free alternates and not-via addresses:a proper combination for IP fast reroute[J].Computer Networks,2010,54(8):1300-1315.
[27]Geng H,Shi X,Yin X,et al.An efficient link protection scheme for link-state routing networks[C].IEEE International Conference on Communications,2015:6024-6029.
[28]Schollmeier G,Charzinski J,Kirstadter A,et al.Improving the resilience in ip networks[C].High Performance Switching and Routing,2003:91-96.
[29]Yang X,Wetherall D.Source selectable path diversity via routing deflections[J].Acm Sigcomm Computer Communication Review,2006,36(4):159-170.
[30]Spring N,Mahajan R,Wetherall D,et al.Measuring isp topologies with rocketfuel[J].Acm Sigcomm Computer Communication Review,2002,32(4):133-145.
[31]Medina A,Lakhina A,Matta I,et al.Brite:an approach to universal topology generation[C].IEEE International Workshop on Modeling,Analysis,and Simulation of Computer and Telecommunication Systems,2001:346-353.
[13]李清.基于弱转发的互联网路由可用性和扩展性研究[D].北京;清华大学,2013.
[14]杨芫.基于路径约束的互联网域内路由可用性与节能研究[D].北京:清华大学,2015.