基于优化链路权值的域内路由保护方案
|
摘要
目前,互联网部署的域内链路状态路由协议,如开放最短路径优先(Open Shortest Path First,OSPF)和中间系统到中间系统(Intermediate System-to-Intermediate System,IS-IS),采用被动恢复方案应对网络故障。随着网络的发展,大量的实时应用部署在互联网上,OSPF的收敛时间无法满足这些实时应用对收敛时间的需求。因此,学术界和工业界提出采用路由保护方案来应对网路中出现的故障。然而,已有的路由保护方案存在两个方面的问题:1)默认路径和备份路径的交叉度较高,如LFA;2)为了计算两条交叉度低的路径,对默认路径加以限制,即默认路径不采用最短路径,如Color Tree。为了解决上述两个问题,首先将上述问题归结为整数规划模型,接着利用启发式方法计算近似最优解,最后在实际网络和模拟网络中对所提算法进行了大量实验。实验结果表明,所提算法可以降低默认路径和备份路径的交叉度,极大地提高网络的可用性。
The current deployed intra-domain link state routing protocols on the Internet,such as Open Shortest Path First(OSPF)and Intermediate System-to-Intermediate System(IS-IS),generally adopt proactive recovery schemes to cope with network failures.In addition,with the emergence of real-time and mission-critical applications,stringent reliability and high availability are required.However,the deployed intra-domain link-state routing protocols need a global link-state advertisement and need to recalculate routing tables when link failures occur,inevitably causing network outage.As a result,academics and industry proposed to employ reactive routing protection solutions to deal with network failures in the network.The proactive schemes compute backup paths in advance,so that packets can be forwarded over those precomputing paths after the detection of network failures.However,the existing routing protection algorithms are facing two problems:1)the disjointness of the default path with respect to the backup path is very low,i.e.,ECMP and LFA,2)in order to compute two paths which have high disjointness,some restrictions must be impressed on default path,i.e.,the default path is not the shortest path.This paper first introduced the problem of constructing disjoint paths into integer programming problems,and then proposed to use the heuristic algorithm to calculate the approximate optimal solution.Finally,the algorithms were carried out in the real,measured and generated networks.The experimental results show that the proposed algorithms can greatly enhance the disjointness of the shortest path and the backup path,and improve the network availability.
The current deployed intra-domain link state routing protocols on the Internet,such as Open Shortest Path First(OSPF)and Intermediate System-to-Intermediate System(IS-IS),generally adopt proactive recovery schemes to cope with network failures.In addition,with the emergence of real-time and mission-critical applications,stringent reliability and high availability are required.However,the deployed intra-domain link-state routing protocols need a global link-state advertisement and need to recalculate routing tables when link failures occur,inevitably causing network outage.As a result,academics and industry proposed to employ reactive routing protection solutions to deal with network failures in the network.The proactive schemes compute backup paths in advance,so that packets can be forwarded over those precomputing paths after the detection of network failures.However,the existing routing protection algorithms are facing two problems:1)the disjointness of the default path with respect to the backup path is very low,i.e.,ECMP and LFA,2)in order to compute two paths which have high disjointness,some restrictions must be impressed on default path,i.e.,the default path is not the shortest path.This paper first introduced the problem of constructing disjoint paths into integer programming problems,and then proposed to use the heuristic algorithm to calculate the approximate optimal solution.Finally,the algorithms were carried out in the real,measured and generated networks.The experimental results show that the proposed algorithms can greatly enhance the disjointness of the shortest path and the backup path,and improve the network availability.
引文
[1]CLARK D.The design philosophy of the DARPA internet protocols[J].Acm Sigcomm Computer Communication Review,1988,18(4):106-114.
[2]BLACK U.Voice over IP[M].Prentice-Hall,Inc.,1999.
[3]DREW P,GALLON C.Next-generation voip network architecture:MSF Technical Report:MSF-TR-ARCH-001-FINALIRI[R].Multiservice Switching Forum,2003.
[4]GOODE B.Voice over internet protocol(voip)[J].Proceedings of the IEEE,2002,90(9):1495-1517.
[5]KRIST P.Scalable and Efficient Multipath Routing:Complexity and Algorithms[C]∥2015IEEE 23rd International Conference on Network Protocols(ICNP).IEEE,2015:376-385.
[6]ZHENG J,XU H,ZHU X,et al.We’ve Got You Covered:Failure Recovery with Backup Tunnels in Traffic Engineering[C]∥2016IEEE 24rd International Conference on Network Protocols(ICNP).IEEE,2016.
[7]HARTERT R,VISSICCHIO S,SCHAUS P,et al.A Declarative and Expressive Approach to Control Forwarding Paths in Carrier-Grade Networks[J].Acm Sigcomm Computer Communication Review,2015,45(5):15-28.
[8]MARKOPOULOU A,IANNACCONE G,BHATTACHARY-YA S,et al.Characterization of failures in an operational ip backbone network[J].IEEE/ACM Transactions on Networking,2008,16(4):749-762.
[9]HOU M,WANG D,XU M,et al.Selective protection:a cost-efficient backup scheme for link state routing[C]∥29th IEEE International Conference on Distributed Computing Systems.IEEE,2009:68-75.
[10]GENG H J,SHI X G,YIN X,et al.Algebra and algorithms for multipath QoS routing in link state networks[J].Journal of Communications and Networks,2017,19(2):189-200.
[11]YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal Link-Disjoint Node-“Somewhat Disjoint”Paths[C]∥2016IEEE 24rd International Conference on Network Protocols(IC-NP).IEEE,2016:1-10.
[12]KWONG K W,GAO L,ZHANG Z L.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACMTransactions on Networking,2011,19(5):1543-1556.
[13]SRIDHARAN A,GUERIN R,DIOTC.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks[J].IEEE/ACM Transactions on Networking,2005,13(2):234-247.
[14]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[J].ACM SIGCOMM Computer Communication Review,2006,36(4):159-170.
[15]ATLAS A,ZININ A.Basic specification for ip fast reroute:Loop-free alternates:RFC 5286[S].New York,NY,USA:A.Atlas,Ed.,2008.
[16]FRANCOIS P,BONAVENTURE O.An evaluation of IP-based fast reroute techniques[C]∥ACM Conference on Emerging Network Experiment and Technology.ACM,2005:244-245.
[17]HARTMANN M,HOCK D,MENTH M.Routing optimization for IP networks with loop-free alternates[J].Computer Networks,2016,95:35-50.
[18]LI A,FRANCOIS P,YANG X.On improving the efficiency and manageability of NotVia[C]∥ACM Conference on Emerging Network Experiment and Technology(CONEXT).ACM,2007:1-12.
[19]JAYAVELU G,RAMASUBRAMANIAN S,YOUNIS O.Maintaining colored trees for disjoint multipath routing under node failures[J].IEEE/ACM Transactions on Networking,2009,17(1):346-359.
[20]KINI S,RAMASUBRAMANIAN S,KVALBEIN A,et al.Fast recovery from dual link failures in IP networks[C]∥Proc.IN-FOCOM.IEEE,2009.
[21]MEDARD M,FINN S,BARRY R,et al.Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs[J].IEEE/ACM Transactions on Networking,1999,7(5):641-652.
[22]SUURBALLE J W.A quick method for finding shortest pairs of disjoint paths[J].Networks,2006,14(2):325-336.
[23]NETWORK A B.Advanced networking for research and education[OL].http://abilene.internet2.edu.
[24]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring isp topologies with rocketfuel[J].IEEE/ACM Transactions on Networking,2004,12(1):2-16.
[25]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.IEEE,2001:346-353.
[26]GJOKA M,RAM V,YANG X.Evaluation of ip fast reroute proposals[C]∥International Conference on Communication Systems Software and Middleware.IEEE,2007:1-8.
[2]BLACK U.Voice over IP[M].Prentice-Hall,Inc.,1999.
[3]DREW P,GALLON C.Next-generation voip network architecture:MSF Technical Report:MSF-TR-ARCH-001-FINALIRI[R].Multiservice Switching Forum,2003.
[4]GOODE B.Voice over internet protocol(voip)[J].Proceedings of the IEEE,2002,90(9):1495-1517.
[5]KRIST P.Scalable and Efficient Multipath Routing:Complexity and Algorithms[C]∥2015IEEE 23rd International Conference on Network Protocols(ICNP).IEEE,2015:376-385.
[6]ZHENG J,XU H,ZHU X,et al.We’ve Got You Covered:Failure Recovery with Backup Tunnels in Traffic Engineering[C]∥2016IEEE 24rd International Conference on Network Protocols(ICNP).IEEE,2016.
[7]HARTERT R,VISSICCHIO S,SCHAUS P,et al.A Declarative and Expressive Approach to Control Forwarding Paths in Carrier-Grade Networks[J].Acm Sigcomm Computer Communication Review,2015,45(5):15-28.
[8]MARKOPOULOU A,IANNACCONE G,BHATTACHARY-YA S,et al.Characterization of failures in an operational ip backbone network[J].IEEE/ACM Transactions on Networking,2008,16(4):749-762.
[9]HOU M,WANG D,XU M,et al.Selective protection:a cost-efficient backup scheme for link state routing[C]∥29th IEEE International Conference on Distributed Computing Systems.IEEE,2009:68-75.
[10]GENG H J,SHI X G,YIN X,et al.Algebra and algorithms for multipath QoS routing in link state networks[J].Journal of Communications and Networks,2017,19(2):189-200.
[11]YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal Link-Disjoint Node-“Somewhat Disjoint”Paths[C]∥2016IEEE 24rd International Conference on Network Protocols(IC-NP).IEEE,2016:1-10.
[12]KWONG K W,GAO L,ZHANG Z L.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACMTransactions on Networking,2011,19(5):1543-1556.
[13]SRIDHARAN A,GUERIN R,DIOTC.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks[J].IEEE/ACM Transactions on Networking,2005,13(2):234-247.
[14]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[J].ACM SIGCOMM Computer Communication Review,2006,36(4):159-170.
[15]ATLAS A,ZININ A.Basic specification for ip fast reroute:Loop-free alternates:RFC 5286[S].New York,NY,USA:A.Atlas,Ed.,2008.
[16]FRANCOIS P,BONAVENTURE O.An evaluation of IP-based fast reroute techniques[C]∥ACM Conference on Emerging Network Experiment and Technology.ACM,2005:244-245.
[17]HARTMANN M,HOCK D,MENTH M.Routing optimization for IP networks with loop-free alternates[J].Computer Networks,2016,95:35-50.
[18]LI A,FRANCOIS P,YANG X.On improving the efficiency and manageability of NotVia[C]∥ACM Conference on Emerging Network Experiment and Technology(CONEXT).ACM,2007:1-12.
[19]JAYAVELU G,RAMASUBRAMANIAN S,YOUNIS O.Maintaining colored trees for disjoint multipath routing under node failures[J].IEEE/ACM Transactions on Networking,2009,17(1):346-359.
[20]KINI S,RAMASUBRAMANIAN S,KVALBEIN A,et al.Fast recovery from dual link failures in IP networks[C]∥Proc.IN-FOCOM.IEEE,2009.
[21]MEDARD M,FINN S,BARRY R,et al.Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs[J].IEEE/ACM Transactions on Networking,1999,7(5):641-652.
[22]SUURBALLE J W.A quick method for finding shortest pairs of disjoint paths[J].Networks,2006,14(2):325-336.
[23]NETWORK A B.Advanced networking for research and education[OL].http://abilene.internet2.edu.
[24]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring isp topologies with rocketfuel[J].IEEE/ACM Transactions on Networking,2004,12(1):2-16.
[25]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.IEEE,2001:346-353.
[26]GJOKA M,RAM V,YANG X.Evaluation of ip fast reroute proposals[C]∥International Conference on Communication Systems Software and Middleware.IEEE,2007:1-8.