A Lagrangean Relaxation Algorithm for Flow Optimization in Survivable MPLS Networks

• Autorzy: Walkowiak K.
• Języki publikacji: EN

Abstrakty

EN

The problem that this paper investigates, namely, the working route assignment (WRA) problem, is one that arises naturally from problems of survivable network design that have recently received significant attention in data networking community. We consider an existing MPLS backbone transport network, which is in an operational phase and augmenting its resources is not possible. To address the issue of network survivability we apply restoration, i.e. after a network failure broken connections are dynamically restored. The main goal of our work is twofold. First, we want to develop an effective objective function for optimization of working routes in order to scale network flows and prepare the network for future failures and restoration. Second, we plan to find an efficient method to solve the WRA problem with this new objective function. Therefore, a function called RCL (Residual Capacity and Lost Flow in Link) facilitating the function LFL (Lost Flow in Link) developed previously by the author is formulated. Next, we present an approximation approach, called Lagrangean relaxation with heuristics (LRH) aimed to solve WRA with RCL as objective function. We further draw comparisons between LRH and an existing heuristic based on Flow Deviation algorithm. We also examine the performance of RCL against other functions in the context of network survivability. The results of simulation tests demonstrate that the new algorithm provides sub-optimal results, which are significantly better than other heuristic and the new function RCL can be effectively applied for assignment of working routes in survivable MPLS networks.

Słowa kluczowe

EN

optimization; Lagrangean relaxation; MPLS; survivability

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2010
• Tom: Vol. 22, No. 1
• Strony: 19--47
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Walkowiak K.

• Chair of Systems and Computer Networks, Faculty of Electronics Wroclaw University of Technology Wybrzeże Wyspiańskiego 27, 50-370 Wroclaw, Poland,

Bibliografia

• 1. W. Bigos, B. Cousin, S. Gosselin, M. Le Foll, H. Nakajima: “Survivable MPLS Over Optical Transport Networks: Cost and Resource Usage Analysis”, IEEE Journal on Selected Areas in Communications, Vol. 25, No. 5, 2007, pp. 949-962.
• 2. J. Burns, T. Ott, A. Krzesinski, K. Muller: “Path selection and bandwidth allocation in MPLS networks”, Performance Evaluation, 52 (2003) pp. 133-152.
• 3. R. Cohen, G. Nakibly: “Maximizing Restorable Throughput in MPLS Networks”,IEEE/ACM Transactions on Networking, Accepted for publication, 2009.
• 4. R. Cottera and D. Medhi: Survivable Design of Reconfigurable MPLS VPN Networks,in Proceedings of the 7th International Workshop on Design of Reliable Communication Networks DRCN 2009, pp. 78-85, 2009.
• 5. R. A. Dias, E. Camponogara, J. M. Farines, R. Willrich, A. Campestrini: “Implementing traffic engineering in MPLS-based IP networks with Lagrangean relaxation”, in Proceedings of Computers and Communication, 2003 (ISCC 2003), pp. 373-378 vol.1, 2003.
• 6. L. Fratta, M. Gerla and L. Kleinrock: “The Flow Deviation Method: An Approach to Store-and-Forward Communication Network Design”, Networks, vol. 3, pp. 97-133, 1973.
• 7. B. Gavish, S. Huntler: “An Algorithm for Optimal Route Selection in SNA Networks”, IEEE Trans. Commun., Vol. COM-31, No. 10, pp. 1154-1160, October 1983.
• 8. B. Gavish, I. Neuman: “A System for Routing and Capacity Assignment in Computer Communication Networks”, IEEE Trans. Commun., Vol. 37, pp. 360-366, 1989.
• 9. B. Gavish, I. Neuman: “Routing in a Network with Unreliable Components”, IEEE Trans. Commun., Vol. 40, pp. 1248-1258, July 1992.
• 10. W. Grover: “Mesh-based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking”, Prentice Hall PTR, Upper Saddle River, New Jersey 2004.
• 11. R. Guerin, M. Ahmadi and M. Nagshineh: “Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks”, IEEE Journal on Selected Areas in Communications, Vol. 9, No. 4, pp. 968-981, 1991.
• 12. K. Holmberg, “Lagrangean Heuristics for Linear Cost Multicommodity Network Flow Problems”, Working Paper LiTH-MAT-OPT/WP-1995-01, Department of Mathematics, Linkoping Institute of Technology, Sweden, 1995.
• 13. K. Holmberg, D. Yuan: “A Lagrangean Approach to Network Design Problems”. International Transactions in Operational Research, Vol. 5, No. 6, pp. 529-539, 1998.
• 14. K. Holmberg, D. Yuan: “A Lagrangean Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem”, Operations Research Vol. 48, No. 3, pp. 461-481, 2000.
• 15. J. Hui, M. Gursoy, N. Moayeri and R. Yates: “A Layered Broadband Switching Architecture with Physical and Virtual Path Configurations”, IEEE Journal on Selected Areas in Communications, Vol. 9, No. 12, pp. 1416
• 16. A. Kasprzak: “Designing of Wide Area Networks”, Wroclaw University of Technology Press, 2001.
• 17. D. Medhi, D. Tipper: “Some Approaches to Solving a Multi-Hour Broadband Network Capacity Design Problem with Single-Path Routing”, Technical Report, CST/UMKC July 1996.
• 18. K. Murakami and H. Kim: “Virtual Path Routing for Survivable ATM Networks”, IEEE/ACM Transactions on Networking, Vol. 4, No. 2, pp. 22-39, 1996.
• 19. P. Nilsson, M. Pióro and Z. Dziong: “Link Protection within an Existing Backbone Network”, In Proceedings Of International Network Optimization Conference (INOC), 2003.
• 20. M. Pióro and D. Medhi: “Routing, Flow, and Capacity Design in Communication and Computer Networks” Morgan Kaufman Publishers 2004.