基于不相交路径的域内路由保护方案
|
摘要
目前的路由保护方案备份路径与默认路径交叉度较高,为寻找交叉度较低的两条路径,默认路径可能不利用最短路径。为此,提出一种新的域内路由保护方案。将问题描述为整数规划模型,利用遗传算法计算近似最优解,并在大量拓扑结构上对算法进行模拟。实验结果表明,该方案降低了默认路径和备份路径的交叉度,可有效提高网络的可靠性,提升用户体验。
The backup path of current routeing protection scheme has a high degree of crossover with the default path. To find two paths with low crossover,the default path may not utilize the shortest path. Therefore,a new intra-domain routing protection scheme is proposed. The problem is described as an integer programming model. The Genetic Algorithm( GA) is used to calculate the approximate optimal solution. The algorithm is simulated on a large number of topologies. Experimental results show that the scheme greatly reduces the crossover between the default path and the backup path,and improves the reliability of the network,and the user experience has improvement.
The backup path of current routeing protection scheme has a high degree of crossover with the default path. To find two paths with low crossover,the default path may not utilize the shortest path. Therefore,a new intra-domain routing protection scheme is proposed. The problem is described as an integer programming model. The Genetic Algorithm( GA) is used to calculate the approximate optimal solution. The algorithm is simulated on a large number of topologies. Experimental results show that the scheme greatly reduces the crossover between the default path and the backup path,and improves the reliability of the network,and the user experience has improvement.
引文
[1]CLARK D.The design philosophy of the DARPA internet protocols[J].ACM SIGCOMM Computer Communication Review,1988,18(4):106-114.
[2]耿海军.基于路由度量的域内多路径路由研究[D].北京:清华大学,2015.
[3]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.
[4]GOODE B.Voice over internet protocol[J].Proceedings of the IEEE,2002,90(9):1495-1517.
[5]KRIST P.Scalable and efficient multipath routing:complexity and algorithms[C]//Proceedings of the 23rd IEEE International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,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]//Proceedings of the 24th International Conference on Network Protocols.Washington D.C.,USA:IEEEPress,2016:1-10.
[7]HARTERT R,VISSICCHIO S,SCHAUS P,et al.Adeclarative and expressive approach to control forwarding paths in carrier-grade networks[J].ACM SIGCOMMComputer Communication Review,2015,45(5):15-28.
[8]MARKOPOULOU A,IANNACCONE G.Characterization of failures in an operational IP backbone network[J].IEEE/ACM Transactions on Networking,2008,16(4):749-762.
[9]徐明伟,李琦,潘凌涛,等.网络故障及自愈路由模型和算法[J].中国科学:信息科学,2010,40(7):943-953.
[10]GENG Haijun,SHI Xingang,YIN Xia,et al.Algebra and algorithms for multipath Qo S 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]//Proceedingsof the 24th International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,2016:1-10.
[12]李清.基于弱转发的互联网路由可用性和扩展性研究[D].北京:清华大学,2013.
[13]SRIDHARAN A,GUERIN R,DIOT C.Achieving nearoptimal traffic engineering solutions for current OSPF/IS-ISnetworks[J].IEEE/ACM Transactions on Networking,2005,13(2):234-247.
[14]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[C]//Proceedings of ACM SIGCOMM’06.New York,USA:ACM Press,2006:159-170.
[15]ATLAS A,ZININ A.Basic specification for IP fast reroute:loop-free alternates[Z].RFC5286,2008.
[16]ATLAS A.U-turn alternates for IP/LDP fast-reroute[Z].RFC 5286,2006.
[17]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.
[18]薛华威,王宝生,邓文平.基于SDN架构的网络故障检测与修复系统[J].计算机工程,2017,43(11):40-44.
[19]WHITLEY D.A genetic algorithm tutorial[J].Statistics and Computing,1994,4(2):65-85.
[20]Advanced networking for research and education.[EB/OL].[2017-06-21].https://www.internet2.edu/products-services/advanced-networking.
[21]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring ISP topologies with rocketfuel[J].IEEE/ACMTransactions on Networking,2004,12(1):2-16.
[2]耿海军.基于路由度量的域内多路径路由研究[D].北京:清华大学,2015.
[3]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.
[4]GOODE B.Voice over internet protocol[J].Proceedings of the IEEE,2002,90(9):1495-1517.
[5]KRIST P.Scalable and efficient multipath routing:complexity and algorithms[C]//Proceedings of the 23rd IEEE International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,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]//Proceedings of the 24th International Conference on Network Protocols.Washington D.C.,USA:IEEEPress,2016:1-10.
[7]HARTERT R,VISSICCHIO S,SCHAUS P,et al.Adeclarative and expressive approach to control forwarding paths in carrier-grade networks[J].ACM SIGCOMMComputer Communication Review,2015,45(5):15-28.
[8]MARKOPOULOU A,IANNACCONE G.Characterization of failures in an operational IP backbone network[J].IEEE/ACM Transactions on Networking,2008,16(4):749-762.
[9]徐明伟,李琦,潘凌涛,等.网络故障及自愈路由模型和算法[J].中国科学:信息科学,2010,40(7):943-953.
[10]GENG Haijun,SHI Xingang,YIN Xia,et al.Algebra and algorithms for multipath Qo S 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]//Proceedingsof the 24th International Conference on Network Protocols.Washington D.C.,USA:IEEE Press,2016:1-10.
[12]李清.基于弱转发的互联网路由可用性和扩展性研究[D].北京:清华大学,2013.
[13]SRIDHARAN A,GUERIN R,DIOT C.Achieving nearoptimal traffic engineering solutions for current OSPF/IS-ISnetworks[J].IEEE/ACM Transactions on Networking,2005,13(2):234-247.
[14]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[C]//Proceedings of ACM SIGCOMM’06.New York,USA:ACM Press,2006:159-170.
[15]ATLAS A,ZININ A.Basic specification for IP fast reroute:loop-free alternates[Z].RFC5286,2008.
[16]ATLAS A.U-turn alternates for IP/LDP fast-reroute[Z].RFC 5286,2006.
[17]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.
[18]薛华威,王宝生,邓文平.基于SDN架构的网络故障检测与修复系统[J].计算机工程,2017,43(11):40-44.
[19]WHITLEY D.A genetic algorithm tutorial[J].Statistics and Computing,1994,4(2):65-85.
[20]Advanced networking for research and education.[EB/OL].[2017-06-21].https://www.internet2.edu/products-services/advanced-networking.
[21]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring ISP topologies with rocketfuel[J].IEEE/ACMTransactions on Networking,2004,12(1):2-16.