IP网络链路权重优化方法研究
|
摘要
随着Internet从单一地支持点到点的尽力而为的通信服务向支持多业务转换,能够安排业务路由、从而优化网络资源的traffic engineering越来越受到网络服务商的重视。传统的MPLS-TE建立支持显示路由的LSP,从而控制不同业务的路由。研究表明,MPLS-TE规划出的无环LSP可以转换为IP网络中对应于一组链路权重集合的最短路。根据业务需求进行链路权重优化的IP-TE能够避免MPLS-TE的复杂性,是本文研究的重点。
针对当今IP网络大业务量、多QoS要求的特点,本文首先讨论多约束条件下IP网络链路权重的全量规划问题,提出一种业务量确定情况下的IP网络链路权重全量规划算法。算法支持多种业务约束约束,包括业务的路径约束(跳数约束,时延约束),链路约束(服务级别约束),节点约束(ECMP个数约束)。同时,算法运用了大量的动态更新思想,具有效率高,优化性能好的特点。
在IP网络中,业务的改变可能造成网络性能下降,这时需要对网络进行增量规划。在IP网络的增量规划中,链路权重的调整会造成路由需要重新收敛,从而可能导致路由震荡、环路由的出现。
为了减小对网络进行增量配置时需要调整权重的链路数目,从而达到降低出现路由震荡、环路由的可能性的目的,本文介绍一种在保证业务的QoS和网络负载均衡的前提下,使得需要调整权重的链路数目尽量少的算法。
当IP网络链路权重需要调整时,调整可能是分批进行的,即并不同时将所有需要调整的链路权重进行重新设置,而是采用每次调整一部分链路权重的方式,分批完成对所有需要调整的链路权重的重新设置。
为了使得在分批调整链路权重的过程中网络不发生拥塞,让业务能够平滑的迁移,本文提出一种在需要调整的链路权重已知的情况下,决定链路权重的调整顺序的算法。
The Internet was transited from providing only peer to peer best-effort service to supporting different types of demands. Therefore, the ISPs paid more attention on traffic engineering which can optimize the using of network resources by arrange the traffic routes. In MPLS network, the network is optimally engineered through a set of loop-free explicit LSPs. And, some researches proved that by setting appropriate link weights, the loop-free explicit LSPs which created by MPLS-TE, can be transformed into shortest paths according to this set of link weights in IP networks. In this paper, we focus on IP-TE which reduced the complexity of MPLS-TE by optimizing link weights under given traffic demand.
Considering large traffic and multi-QoS requirements in IP network, this article first discusses the GreenField planning with multi-constrains condition. And then a heuristic algorithm is proposed for GreenField planning under given traffic demand. A variety of constraints, including the path constraints (hop constraint, delay constraint), the link constraints (service-level constraints), the node constraints (ECMP number constraints), are considered in this algorithm. Meanwhile, the algorithm has excellent optimization performance and high efficiency by adopting dynamic updating. Since the demand changes may result in a decline in network performance, it’s necessary to introduce the incremental planning in IP networks. In the incremental planning of IP networks, the link weight adjustment will cause the routing convergence and even routing oscillation and loops.
In order to reduce the possibility of the routing oscillation and loops’occurrence, this paper proposes an algorithm that aims at minimizing the adjusting number of link weights on the premise of QoS Guarantee and load balancing.
In IP networks, when some link weights needs to be adjusted, the adjustment may be a bath process. That is to say, all the adjustable link weights aren’t tuned simultaneously, but some links are chosen to be adjusted each time.
This paper proposes an algorithm that can determine the order of adjusting link with given link weight values to avoid network congestion in adjustment process and make traffic redistribute smoothly.
针对当今IP网络大业务量、多QoS要求的特点,本文首先讨论多约束条件下IP网络链路权重的全量规划问题,提出一种业务量确定情况下的IP网络链路权重全量规划算法。算法支持多种业务约束约束,包括业务的路径约束(跳数约束,时延约束),链路约束(服务级别约束),节点约束(ECMP个数约束)。同时,算法运用了大量的动态更新思想,具有效率高,优化性能好的特点。
在IP网络中,业务的改变可能造成网络性能下降,这时需要对网络进行增量规划。在IP网络的增量规划中,链路权重的调整会造成路由需要重新收敛,从而可能导致路由震荡、环路由的出现。
为了减小对网络进行增量配置时需要调整权重的链路数目,从而达到降低出现路由震荡、环路由的可能性的目的,本文介绍一种在保证业务的QoS和网络负载均衡的前提下,使得需要调整权重的链路数目尽量少的算法。
当IP网络链路权重需要调整时,调整可能是分批进行的,即并不同时将所有需要调整的链路权重进行重新设置,而是采用每次调整一部分链路权重的方式,分批完成对所有需要调整的链路权重的重新设置。
为了使得在分批调整链路权重的过程中网络不发生拥塞,让业务能够平滑的迁移,本文提出一种在需要调整的链路权重已知的情况下,决定链路权重的调整顺序的算法。
The Internet was transited from providing only peer to peer best-effort service to supporting different types of demands. Therefore, the ISPs paid more attention on traffic engineering which can optimize the using of network resources by arrange the traffic routes. In MPLS network, the network is optimally engineered through a set of loop-free explicit LSPs. And, some researches proved that by setting appropriate link weights, the loop-free explicit LSPs which created by MPLS-TE, can be transformed into shortest paths according to this set of link weights in IP networks. In this paper, we focus on IP-TE which reduced the complexity of MPLS-TE by optimizing link weights under given traffic demand.
Considering large traffic and multi-QoS requirements in IP network, this article first discusses the GreenField planning with multi-constrains condition. And then a heuristic algorithm is proposed for GreenField planning under given traffic demand. A variety of constraints, including the path constraints (hop constraint, delay constraint), the link constraints (service-level constraints), the node constraints (ECMP number constraints), are considered in this algorithm. Meanwhile, the algorithm has excellent optimization performance and high efficiency by adopting dynamic updating. Since the demand changes may result in a decline in network performance, it’s necessary to introduce the incremental planning in IP networks. In the incremental planning of IP networks, the link weight adjustment will cause the routing convergence and even routing oscillation and loops.
In order to reduce the possibility of the routing oscillation and loops’occurrence, this paper proposes an algorithm that aims at minimizing the adjusting number of link weights on the premise of QoS Guarantee and load balancing.
In IP networks, when some link weights needs to be adjusted, the adjustment may be a bath process. That is to say, all the adjustable link weights aren’t tuned simultaneously, but some links are chosen to be adjusted each time.
This paper proposes an algorithm that can determine the order of adjusting link with given link weight values to avoid network congestion in adjustment process and make traffic redistribute smoothly.
引文
[1] Xipeng Xiao. Ni, L.M. s. Internet QoS: a big picture Network. Mar/Apr 1999. vol.13, no.2, pp.8-18.
[2] Cisco systems Inc. Cisco IOS switching services configuration guide: Multi-protocol label switching overview. http://www.cisco.com 2001-02.
[3] Rosen E. Multi-protocol label switching architecture. IETF RFC 30-31(2001).
[4] Ning Wang, Kin Ho, Pavlou, G., Howarth, M., Surrey Univ., Guildford, An overview of routing optimization for internet traffic engineering. Communications Surveys & Tutorials. April 2008. pp.33-56.
[5] Menasce, D.A. QoS issues in Web services. Internet Computing. Nov/Dec 2002. vol.6 no.6. pp.72-75.
[6] Fortz, B. Rexford, J. Thorup, M. Traffic engineering with traditional IP routing protocols. Communications Magazine. Oct 2002. vol.40. no.10. pp.118-124.
[7] K. Kompella et al. OSPF Extensions in Support of MPLS, Internet Draft, draft-kompella-ospf-gmpls-extensions-00.txt, November, 2000.
[8] K.Kompella et al., IS-IS Extensions in Support of MPLS, Internet Draft, draft-kompella-isis-gmpls-extensions-txt, November, 2000.
[9] Henrik Abrahamsson. Bengt Ahlgren. Juan Alonso. Anders Andersson. Per Kreuger. A Multi-path routing algorithm for IP networks based on flow optimization. Lecture Notes in Computer Science. 2002. vol.2511/2002. pp.135-144.
[10] Kuipers, F. Van Mieghem, P. Korkmaz, T. Krunz, M. An overview of constraint-based path selection algorithms for QoS routing. Communications Magazine. Dec 2002. vol.40. no. 12. pp.50-55.
[11] M. Dzida M. Zagozdzon, M. Pioro, A. Tomaszewski. Optimization of The Shortest-Path Routing with Equal-Cost Multi-Path Load Balancing, ICTON, 2006. pp.9-12.
[12] CT Chou. Traffic engineering for MPLS-based virtual private networks. Computer Networks, 2004. pp.110-115.
[13] Ekkehard K?hler, Rolf H. M?hring, Klaus N?kel and Gregor Wünsch. Optimization of signalized traffic networks. MATHEMATICS. 2008. Part.5. pp.179-188.
[14] Z. Wang, Y. Wang, and L. Zhang, Internet Traffic Engineering Without Full-mesh Overlaying, IEEE Infocom 2001. vol.1. pp.565-571.
[15] H. Umit. B. Fortz. Fast Heuristic Techniques for Intra-Domain Routing Metric Optimization. In proceedings of International Network Optimization. 2007.
[16] A. Bley. Inapproximability Results For The Inverse Shortest Paths Problem With Integer Lengths and Unique Shortest Paths. Networks.2007. vol.50. no.1. pp.29–36.
[17] G. Retvari, J. J. Biro, T. Cinkler. On Shortest Path Representation, IEEE/ACM Transactions on Networking. vol.15. no.6. pp.1293-1305.
[18] Ericsson, M., Resende, M.G.C., Pardalos, P.M. A genetic algorithm for the weight setting problem in OSPF routing. Technical report, ATT Shannon Laboratory, 2001. vol.6. no.3. pp.299-333.
[19] Buriol L.S., Resende, M.G.C., Ribeiro C., Thorup M. A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks. 2005. vol.46.no.1. pp.36-56.
[20] Riedl A. A hybrid genetic algorithm for routing optimization in IP networks utilizing bandwidth and delay metrics. IEEE IPOM02. 2002. pp.166-170.
[21] B. Fortz and M. Thorup. Internet Traffic Engineering by Optimizing OSPF Weights, IEEE INFOCOM 2000. vol.2. pp.519–528.
[22] M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, 2004.
[23] S. M. Sait, M. H. Sqalli, S. Asadulah. Parallel Tabu Search for Optimizing the OSPF Weight Setting Problem, WSEAS Transactions on Communications, vol.8, no.3. pp. 311-320.
[24] IBM ILOG CPLEX Optimizer http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[25] Xin Wang. Schulzrinne, H. Pricing network resources for adaptive applications in a differentiated services network. INFOCOM 2001. vol.2. pp.943-952.
[26] Narvaez, P. Kai-Yeung Siu. Hong-Yi Tzeng. New dynamic algorithms for shortest path tree computation. Networking. Dec 2000. vol.8. no.6. pp.734-746.
[27] G. Ramalingam and T.W. Reps, An Incremental Algorithm for a Generalization of the Shortest-Path Problem, J. Algorithms, 1996. vol.21, no.2, pp.267-305.
[28] V. King and M. Thorup. A space saving trick for directed dynamic transitive closure and shortest path algorithms. In Proceedings of the 7th Annual International Computing and Combinatorial Conference COCOON in LNCS 2108. Springer-Verlag, 2001. pp.268–277.
[29] Edward P.F. Chan and Yaya Yang. Shortest Path Tree Computation in Dynamic Graphs, IEEE Computer Society,2009. vol.58. no.4. pp.541-557.
[30] A. M. Frieze. G. R. Grimmett. The shortest-path problem for graphs with random arc-lengths. Elsevier Science.1985. vol.10. no.1 pp.57-77.
[31] Donald B. Johnson. A Note on Dijkstra's Shortest Path Algorithm. Journal of the ACM. July 1973.
[32] Opnet IT Guru http://www.opnet.com
[33] Charzinski, Joachim. Optimized Incremental Network Planning. 13th GI/ITG Conference Measuring, Modelling and Evaluation of Computer and Communication Systems. 2006.
[34] Shiwei Chen. Hongfang Yu. Lemin Li. Dan Liao. Hongbin Luo. An effective upgrading algorithm in incremental planning for optical networks. Communication Technology, 2008. pp.390-393.
[35] D. Allen, I. Ismail, J. Kennington and E. Olinick. An Incremental Procedure for Improving Path Assignment in a Telecommunications Network. Journal Of Heuristic. 2003. vol.9. no.5. pp.375-399.
[36] B. Fortz, M. Thorup. Optimizing OSPF/IS-IS weights in a changing world, IEEE JSAC,vol.2, no.4, 2002. pp.756-767.
[2] Cisco systems Inc. Cisco IOS switching services configuration guide: Multi-protocol label switching overview. http://www.cisco.com 2001-02.
[3] Rosen E. Multi-protocol label switching architecture. IETF RFC 30-31(2001).
[4] Ning Wang, Kin Ho, Pavlou, G., Howarth, M., Surrey Univ., Guildford, An overview of routing optimization for internet traffic engineering. Communications Surveys & Tutorials. April 2008. pp.33-56.
[5] Menasce, D.A. QoS issues in Web services. Internet Computing. Nov/Dec 2002. vol.6 no.6. pp.72-75.
[6] Fortz, B. Rexford, J. Thorup, M. Traffic engineering with traditional IP routing protocols. Communications Magazine. Oct 2002. vol.40. no.10. pp.118-124.
[7] K. Kompella et al. OSPF Extensions in Support of MPLS, Internet Draft, draft-kompella-ospf-gmpls-extensions-00.txt, November, 2000.
[8] K.Kompella et al., IS-IS Extensions in Support of MPLS, Internet Draft, draft-kompella-isis-gmpls-extensions-txt, November, 2000.
[9] Henrik Abrahamsson. Bengt Ahlgren. Juan Alonso. Anders Andersson. Per Kreuger. A Multi-path routing algorithm for IP networks based on flow optimization. Lecture Notes in Computer Science. 2002. vol.2511/2002. pp.135-144.
[10] Kuipers, F. Van Mieghem, P. Korkmaz, T. Krunz, M. An overview of constraint-based path selection algorithms for QoS routing. Communications Magazine. Dec 2002. vol.40. no. 12. pp.50-55.
[11] M. Dzida M. Zagozdzon, M. Pioro, A. Tomaszewski. Optimization of The Shortest-Path Routing with Equal-Cost Multi-Path Load Balancing, ICTON, 2006. pp.9-12.
[12] CT Chou. Traffic engineering for MPLS-based virtual private networks. Computer Networks, 2004. pp.110-115.
[13] Ekkehard K?hler, Rolf H. M?hring, Klaus N?kel and Gregor Wünsch. Optimization of signalized traffic networks. MATHEMATICS. 2008. Part.5. pp.179-188.
[14] Z. Wang, Y. Wang, and L. Zhang, Internet Traffic Engineering Without Full-mesh Overlaying, IEEE Infocom 2001. vol.1. pp.565-571.
[15] H. Umit. B. Fortz. Fast Heuristic Techniques for Intra-Domain Routing Metric Optimization. In proceedings of International Network Optimization. 2007.
[16] A. Bley. Inapproximability Results For The Inverse Shortest Paths Problem With Integer Lengths and Unique Shortest Paths. Networks.2007. vol.50. no.1. pp.29–36.
[17] G. Retvari, J. J. Biro, T. Cinkler. On Shortest Path Representation, IEEE/ACM Transactions on Networking. vol.15. no.6. pp.1293-1305.
[18] Ericsson, M., Resende, M.G.C., Pardalos, P.M. A genetic algorithm for the weight setting problem in OSPF routing. Technical report, ATT Shannon Laboratory, 2001. vol.6. no.3. pp.299-333.
[19] Buriol L.S., Resende, M.G.C., Ribeiro C., Thorup M. A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks. 2005. vol.46.no.1. pp.36-56.
[20] Riedl A. A hybrid genetic algorithm for routing optimization in IP networks utilizing bandwidth and delay metrics. IEEE IPOM02. 2002. pp.166-170.
[21] B. Fortz and M. Thorup. Internet Traffic Engineering by Optimizing OSPF Weights, IEEE INFOCOM 2000. vol.2. pp.519–528.
[22] M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, 2004.
[23] S. M. Sait, M. H. Sqalli, S. Asadulah. Parallel Tabu Search for Optimizing the OSPF Weight Setting Problem, WSEAS Transactions on Communications, vol.8, no.3. pp. 311-320.
[24] IBM ILOG CPLEX Optimizer http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[25] Xin Wang. Schulzrinne, H. Pricing network resources for adaptive applications in a differentiated services network. INFOCOM 2001. vol.2. pp.943-952.
[26] Narvaez, P. Kai-Yeung Siu. Hong-Yi Tzeng. New dynamic algorithms for shortest path tree computation. Networking. Dec 2000. vol.8. no.6. pp.734-746.
[27] G. Ramalingam and T.W. Reps, An Incremental Algorithm for a Generalization of the Shortest-Path Problem, J. Algorithms, 1996. vol.21, no.2, pp.267-305.
[28] V. King and M. Thorup. A space saving trick for directed dynamic transitive closure and shortest path algorithms. In Proceedings of the 7th Annual International Computing and Combinatorial Conference COCOON in LNCS 2108. Springer-Verlag, 2001. pp.268–277.
[29] Edward P.F. Chan and Yaya Yang. Shortest Path Tree Computation in Dynamic Graphs, IEEE Computer Society,2009. vol.58. no.4. pp.541-557.
[30] A. M. Frieze. G. R. Grimmett. The shortest-path problem for graphs with random arc-lengths. Elsevier Science.1985. vol.10. no.1 pp.57-77.
[31] Donald B. Johnson. A Note on Dijkstra's Shortest Path Algorithm. Journal of the ACM. July 1973.
[32] Opnet IT Guru http://www.opnet.com
[33] Charzinski, Joachim. Optimized Incremental Network Planning. 13th GI/ITG Conference Measuring, Modelling and Evaluation of Computer and Communication Systems. 2006.
[34] Shiwei Chen. Hongfang Yu. Lemin Li. Dan Liao. Hongbin Luo. An effective upgrading algorithm in incremental planning for optical networks. Communication Technology, 2008. pp.390-393.
[35] D. Allen, I. Ismail, J. Kennington and E. Olinick. An Incremental Procedure for Improving Path Assignment in a Telecommunications Network. Journal Of Heuristic. 2003. vol.9. no.5. pp.375-399.
[36] B. Fortz, M. Thorup. Optimizing OSPF/IS-IS weights in a changing world, IEEE JSAC,vol.2, no.4, 2002. pp.756-767.