LFA算法的一种高效实现方法
|
摘要
研究表明,网络中的故障不可避免而且频繁出现.当故障发生时,目前互联网部署的域内路由协议需要经历收敛过程.在此过程中,路由信息可能不一致,从而导致报文丢失,降低了路由可用性.因此,业界提出了利用LFA(loop free alternates)应对网络中发生的单故障情形,从而提高路由可用性.然而,已有的LFA实现方式算法时间复杂度大,需要消耗大量的路由器CPU资源.针对该问题严格证明了当网络中出现单故障时,只需要为特定的节点计算备份下一跳,其余受该故障影响节点的备份下一跳和该特定节点的备份下一跳是相同的.基于上述性质,分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法.实验结果表明:与LFA相比较,该算法的执行时间降低了90%以上,路径拉伸度降低了15%以上,并且与LFA具有同样的故障保护率.
Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur, the currently deployed intra-domain routing protocol need to re-convergent. During the process of re-convergence, the packets may be lost due to inconsistent routing information, thus greatly reducing the Internet routing availability. LFA was proposed to cope with all the single failure scenarios. However, the existing LFA implementation algorithms are time-consuming and require a large amount of router CPU resources. This paper proves that when a single fault occurs in a network, it only needs to calculate the backup next hop for a specific node. The backup next hop of all the other affected nodes by the fault is the same as that of the specific node. Based on the above property, the paper proposes two routing protection algorithms to provide protection for networks with symmetric and asymmetric. The results show that these approaches reduce more than 90% computation overhead compared to LFA, and achieve less than 15% path stretch. Moreover, they can provide comparable protection ratio with LFA.
Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur, the currently deployed intra-domain routing protocol need to re-convergent. During the process of re-convergence, the packets may be lost due to inconsistent routing information, thus greatly reducing the Internet routing availability. LFA was proposed to cope with all the single failure scenarios. However, the existing LFA implementation algorithms are time-consuming and require a large amount of router CPU resources. This paper proves that when a single fault occurs in a network, it only needs to calculate the backup next hop for a specific node. The backup next hop of all the other affected nodes by the fault is the same as that of the specific node. Based on the above property, the paper proposes two routing protection algorithms to provide protection for networks with symmetric and asymmetric. The results show that these approaches reduce more than 90% computation overhead compared to LFA, and achieve less than 15% path stretch. Moreover, they can provide comparable protection ratio with LFA.
引文
[1]Internet users.http://www.internetworldstats.com/top20.htm
[2]Reaching 50 million users.http://visual.ly/reaching-50-million-users
[3]Chabarek J,Sommers J,Barford P,et al.Power awareness in network design and routing.In:Proc.of the IEEE Conf.on Computer Communications.IEEE INFOCOM,2008.457-465.
[4]Varshney U,Snow A,Mcgivern M,et al.Voice over IP.Communications of the ACM,2002,45(1):89-96.
[5]Goode B.Voice over internet protocol(voip).Proc.of the IEEE,2002,90(9):1495-1517.
[6]Drew P,Gallon C.Next-Generation voip network architecture.In:Proc.of the Multiservice Switching Forum.2003.1-19.
[7]Tapolcai J,Retvari G,Babarczi P,Berczi-Kovacsy ER,Kristofy P,Enyediz G.Scalable and efficient multipath routing:Complexity and algorithms.In:Proc.of the 2015 IEEE 23rd Int’l Conf.on Network Protocols(ICNP).IEEE,2015.376-385.
[8]Zheng JQ,Xu H,Zhu XJ,Chen GH,Geng YH.We’ve got you covered:Failure recovery with backup tunnels in traffic engineering.In:Proc.of the 2016 IEEE 24th Int’l Conf.on Network Protocols(ICNP).IEEE,2016.1-10.
[9]Markopoulou A,Iannaccone G,Bhattacharyya S,Chuah CN,Ganjali Y,Diot C.Characterization of failures in an operational IPbackbone network.IEEE/ACM Trans.on Networking,2008,16(4):749-762.
[10]Hou MJ,Wang D,Xu MW,Yang JH.Selective protection:A cost-efficient backup scheme for link state routing.In:Proc.of the IEEE Int’l Conf.on Distributed Computing Systems(ICDCS)2009.68-75.
[11]Francois P,Bonaventure O.Avoiding transient loops during the convergence of link-state routing protocols.IEEE/ACM Trans.on Networking,2007,15(6):1280-1292.
[12]Yang B,Liu J,Shenker S,et al.Keep forwarding:Towards k-link failure resilient routing.In:Proc.of the IEEE Conf.on Computer Communications.IEEE INFOCOM,2014.1617-1625.
[13]Xu MW,Hou MJ,Wang D,Yang JH.An efficient critical protection scheme for intra-domain routing using link characteristics.Computer Networks,2013,57(1):117-133.
[14]Kos A,Klepec B,Tomasic S.Challenges for voip technologies in corporate environments.In:Proc.of the ICN.2004.1-4.
[15]Pal S,Gadde R,Latchman HA.On the reliability of voice over ip(voip)telephony.In:Proc.of the SPRING 9th Int’l Conf.on Computing,Communications and Control Technologies.Orlando,2011.1-6.
[16]Xu A,Bi J,Zhang BB,Wang SH,Wu JP.Failure inference for shortening traffic detours.In:Proc.of the IEEE/ACM Int’l Symp.on Quality of Service(IWQoS).2017.1-10.
[17]Kwong KW,Gao L,Zhang ZL.On the feasibility and efficacy of protection routing in IP networks.IEEE/ACM Trans.on Networking,2011,19(5):1543-1556.
[18]Peng Q,Walid A,Low SH.Multipath TCP algorithms:Theory and design.In:Proc.of the ACM SIGMETRICS Int’l Conf.on Measurement and Modeling of Computer Systems.2013.305-316.
[19]Gran EG,Dreibholz T,Kvalbein A.NorNet core-A multihomed research testbed.Computer Networks,2014,61(C):75-87.
[20]Atlas A,Kebler R,Konstantynowicz M,et al.An architecture for IP/LDP fast-reroute using maximally redundant trees.Standards Track,2015.1-41.
[21]Enyedi G,Csaszar A,Atlas A,Bowers C,Gopalan A.Algorithms for computing maximally redundant trees for IP/LDP fast-reroute.Informational,2013.1-56.
[22]Lee S,Yu Y,Nelakuditi S,Zhang ZL,Chuah CN.Proactive vs reactive approaches to failure resilient routing.In:Proc.of the IEEEINFOCOM.Hong Kong,2004.1-11.
[23]Cho S,Elhourani T,Ramasubramanian S.Independent directed acyclic graphs for resilient multipath routing.IEEE/ACM Trans.on Networking(TON),2012,20(1):153-162.
[24]Enyedi G,Rétvári G,Szilágyi P,Császár A.IP fast ReRoute:Lightweight not-via without additional addresses.In:Proc.of the INFOCOM.2009.2771-2775.
[25]Xu M,Yang Y,Li Q.Selecting shorter alternate paths for tunnel-based IP fast ReRoute in linear time.Computer Networks,2012,56(2):845-857.
[26]Banerjee G,Sidhu D.Comparative analysis of path computation techniques for MPLS traffic engineering.Computer Networks,2002,40(1):149-165.
[27]Atlas AK,Zinin A.Basic specification for IP fast reroute:Loop-free alternates.RFC 5286,2008.1-32.
[28]Shaikh A,Greenberg A.Experience in black-box OSPF measurement.In:Proc.of the ACM SIGCOMM Workshop on Internet Measurement.ACM Press,2001.113-125.
[29]Alaettinoglu C,Jacobson V,Yu H.Towards milli-second IGP convergence.IETF Draft,2000.1-8.
[30]Francois P,Filsfils C,Evans J,Bonaventure O.Achieving sub-second IGP convergence in large IP networks.Computer Communication Review,2005,35(3):35-44.
[31]Mérindol P,Francois P,Bonaventure O,Cateloin BS,Pansiot JJ.An efficient algorithm to enable path diversity in link state routing networks.Computer Networks,2011,55(5):1132-1149.
[32]Gjoka M,Ram V,Yang X.Evaluation of IP fast reroute proposals.In:Proc.of the Int’l Conf.on Communication Systems Software and MIDDLEWARE.IEEE,2007.1-8.
[33]Rétvári G,Csikor L,Tapolcai J,et al.Optimizing IGP link costs for improving IP-level resilience.In:Proc.of the Design of Reliable Communication Networks(DRCN).2011.62-69.
[34]Rétvári G,Tapolcai J,Enyedi G,et al.Ip fast reroute:Loop free alternates revisited.In:Proc.of the INFOCOM.2011.2948-2956.
[35]Narvaez P,Siu K,Tzeng H.New dynamic SPT algorithm based on a ball-and-string model.IEEE/ACM Trans.on Networking(TON),2001,9(6):706-718.
[36]Francois P,Bonaventure O.Avoiding transient loops during the convergence of link-state routing protocols.IEEE/ACM Trans.on Networking,2007,15(6):1280-1292.
[37]Moy J.Ospf version 2.RFC 2328,1998.1-244.
[38]Sridharan A,Guerin R,Diot C.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks.IEEE/ACMTrans.on Networking(TON),2005,13(2):234-247.
[39]Yang X,Wetherall D.Source selectable path diversity via routing deflections.In:Proc.of the SIGCOMM.2006.159-170.
[40]Kvalbein A,Hansen AF,Gjessing S,Cicic T,Gjessing S,Lysne O.Fast IP network recovery using multiple routing configurations.In:Proc.of the IEEE Int’l Conf.on Computer Communications.2007.1-11.
[41]Lakshminarayanan K,Caesar M,Rangan M,Anderson T,Shenker S,Stoica I.Achieving convergence-free routing using failurecarrying packets.ACM SIGCOMM Computer Communication Review,2007,37(4):241-252.
[42]Sommers J,Barford P,Eriksson B.On the prevalence and characteristics of MPLS deployments in the open Internet.In:Proc.of the 2011 ACM SIGCOMM Conf.on Internet Measurement Conf.2011.445-462.
[43]https://www.internet2.edu/products-services/advanced-networking
[44]Spring N,Mahajan R,Wetherall D,Anderson T.Measuring ISP topologies with rocketfuel.IEEE/ACM Trans.on Networking,2004,12(1):2-16.
[45]http://www.cs.bu.edu/brite/
[2]Reaching 50 million users.http://visual.ly/reaching-50-million-users
[3]Chabarek J,Sommers J,Barford P,et al.Power awareness in network design and routing.In:Proc.of the IEEE Conf.on Computer Communications.IEEE INFOCOM,2008.457-465.
[4]Varshney U,Snow A,Mcgivern M,et al.Voice over IP.Communications of the ACM,2002,45(1):89-96.
[5]Goode B.Voice over internet protocol(voip).Proc.of the IEEE,2002,90(9):1495-1517.
[6]Drew P,Gallon C.Next-Generation voip network architecture.In:Proc.of the Multiservice Switching Forum.2003.1-19.
[7]Tapolcai J,Retvari G,Babarczi P,Berczi-Kovacsy ER,Kristofy P,Enyediz G.Scalable and efficient multipath routing:Complexity and algorithms.In:Proc.of the 2015 IEEE 23rd Int’l Conf.on Network Protocols(ICNP).IEEE,2015.376-385.
[8]Zheng JQ,Xu H,Zhu XJ,Chen GH,Geng YH.We’ve got you covered:Failure recovery with backup tunnels in traffic engineering.In:Proc.of the 2016 IEEE 24th Int’l Conf.on Network Protocols(ICNP).IEEE,2016.1-10.
[9]Markopoulou A,Iannaccone G,Bhattacharyya S,Chuah CN,Ganjali Y,Diot C.Characterization of failures in an operational IPbackbone network.IEEE/ACM Trans.on Networking,2008,16(4):749-762.
[10]Hou MJ,Wang D,Xu MW,Yang JH.Selective protection:A cost-efficient backup scheme for link state routing.In:Proc.of the IEEE Int’l Conf.on Distributed Computing Systems(ICDCS)2009.68-75.
[11]Francois P,Bonaventure O.Avoiding transient loops during the convergence of link-state routing protocols.IEEE/ACM Trans.on Networking,2007,15(6):1280-1292.
[12]Yang B,Liu J,Shenker S,et al.Keep forwarding:Towards k-link failure resilient routing.In:Proc.of the IEEE Conf.on Computer Communications.IEEE INFOCOM,2014.1617-1625.
[13]Xu MW,Hou MJ,Wang D,Yang JH.An efficient critical protection scheme for intra-domain routing using link characteristics.Computer Networks,2013,57(1):117-133.
[14]Kos A,Klepec B,Tomasic S.Challenges for voip technologies in corporate environments.In:Proc.of the ICN.2004.1-4.
[15]Pal S,Gadde R,Latchman HA.On the reliability of voice over ip(voip)telephony.In:Proc.of the SPRING 9th Int’l Conf.on Computing,Communications and Control Technologies.Orlando,2011.1-6.
[16]Xu A,Bi J,Zhang BB,Wang SH,Wu JP.Failure inference for shortening traffic detours.In:Proc.of the IEEE/ACM Int’l Symp.on Quality of Service(IWQoS).2017.1-10.
[17]Kwong KW,Gao L,Zhang ZL.On the feasibility and efficacy of protection routing in IP networks.IEEE/ACM Trans.on Networking,2011,19(5):1543-1556.
[18]Peng Q,Walid A,Low SH.Multipath TCP algorithms:Theory and design.In:Proc.of the ACM SIGMETRICS Int’l Conf.on Measurement and Modeling of Computer Systems.2013.305-316.
[19]Gran EG,Dreibholz T,Kvalbein A.NorNet core-A multihomed research testbed.Computer Networks,2014,61(C):75-87.
[20]Atlas A,Kebler R,Konstantynowicz M,et al.An architecture for IP/LDP fast-reroute using maximally redundant trees.Standards Track,2015.1-41.
[21]Enyedi G,Csaszar A,Atlas A,Bowers C,Gopalan A.Algorithms for computing maximally redundant trees for IP/LDP fast-reroute.Informational,2013.1-56.
[22]Lee S,Yu Y,Nelakuditi S,Zhang ZL,Chuah CN.Proactive vs reactive approaches to failure resilient routing.In:Proc.of the IEEEINFOCOM.Hong Kong,2004.1-11.
[23]Cho S,Elhourani T,Ramasubramanian S.Independent directed acyclic graphs for resilient multipath routing.IEEE/ACM Trans.on Networking(TON),2012,20(1):153-162.
[24]Enyedi G,Rétvári G,Szilágyi P,Császár A.IP fast ReRoute:Lightweight not-via without additional addresses.In:Proc.of the INFOCOM.2009.2771-2775.
[25]Xu M,Yang Y,Li Q.Selecting shorter alternate paths for tunnel-based IP fast ReRoute in linear time.Computer Networks,2012,56(2):845-857.
[26]Banerjee G,Sidhu D.Comparative analysis of path computation techniques for MPLS traffic engineering.Computer Networks,2002,40(1):149-165.
[27]Atlas AK,Zinin A.Basic specification for IP fast reroute:Loop-free alternates.RFC 5286,2008.1-32.
[28]Shaikh A,Greenberg A.Experience in black-box OSPF measurement.In:Proc.of the ACM SIGCOMM Workshop on Internet Measurement.ACM Press,2001.113-125.
[29]Alaettinoglu C,Jacobson V,Yu H.Towards milli-second IGP convergence.IETF Draft,2000.1-8.
[30]Francois P,Filsfils C,Evans J,Bonaventure O.Achieving sub-second IGP convergence in large IP networks.Computer Communication Review,2005,35(3):35-44.
[31]Mérindol P,Francois P,Bonaventure O,Cateloin BS,Pansiot JJ.An efficient algorithm to enable path diversity in link state routing networks.Computer Networks,2011,55(5):1132-1149.
[32]Gjoka M,Ram V,Yang X.Evaluation of IP fast reroute proposals.In:Proc.of the Int’l Conf.on Communication Systems Software and MIDDLEWARE.IEEE,2007.1-8.
[33]Rétvári G,Csikor L,Tapolcai J,et al.Optimizing IGP link costs for improving IP-level resilience.In:Proc.of the Design of Reliable Communication Networks(DRCN).2011.62-69.
[34]Rétvári G,Tapolcai J,Enyedi G,et al.Ip fast reroute:Loop free alternates revisited.In:Proc.of the INFOCOM.2011.2948-2956.
[35]Narvaez P,Siu K,Tzeng H.New dynamic SPT algorithm based on a ball-and-string model.IEEE/ACM Trans.on Networking(TON),2001,9(6):706-718.
[36]Francois P,Bonaventure O.Avoiding transient loops during the convergence of link-state routing protocols.IEEE/ACM Trans.on Networking,2007,15(6):1280-1292.
[37]Moy J.Ospf version 2.RFC 2328,1998.1-244.
[38]Sridharan A,Guerin R,Diot C.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks.IEEE/ACMTrans.on Networking(TON),2005,13(2):234-247.
[39]Yang X,Wetherall D.Source selectable path diversity via routing deflections.In:Proc.of the SIGCOMM.2006.159-170.
[40]Kvalbein A,Hansen AF,Gjessing S,Cicic T,Gjessing S,Lysne O.Fast IP network recovery using multiple routing configurations.In:Proc.of the IEEE Int’l Conf.on Computer Communications.2007.1-11.
[41]Lakshminarayanan K,Caesar M,Rangan M,Anderson T,Shenker S,Stoica I.Achieving convergence-free routing using failurecarrying packets.ACM SIGCOMM Computer Communication Review,2007,37(4):241-252.
[42]Sommers J,Barford P,Eriksson B.On the prevalence and characteristics of MPLS deployments in the open Internet.In:Proc.of the 2011 ACM SIGCOMM Conf.on Internet Measurement Conf.2011.445-462.
[43]https://www.internet2.edu/products-services/advanced-networking
[44]Spring N,Mahajan R,Wetherall D,Anderson T.Measuring ISP topologies with rocketfuel.IEEE/ACM Trans.on Networking,2004,12(1):2-16.
[45]http://www.cs.bu.edu/brite/