Hierarchical Multiobjective Routing in MPLS Networks with Two Service Classes - A Meta-Heuristic Solution

• Autorzy: Girao-Silva R. , Craveirinha J. , Clímaco J.
• Języki publikacji: EN

Abstrakty

EN

The paper begins by reviewing a two-level hierarchical multicriteria routing model for MPLS networks with two service classes (QoS and BE services) and alternative routing, as well as the foundations of a heuristic resolution approach, previously proposed by the authors. Afterwards a new approach, of meta-heuristic nature, based on the introduction of simulated annealing and tabu search techniques, in the structure of the dedicated heuristic, is described. The application of the developed procedures to a benchmarking case study will show that, in certain initial conditions, this approach provides improvements in the final results especially in more "difficult" situations detected through sensitivity analysis.

Słowa kluczowe

EN

multiobjective optimization; MPLS-Internet; routing models; simulated annealing; tabu search

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2009
• Tom: nr 3
• Strony: 20--37
• Opis fizyczny: Bibliogr. 47 poz., tab.

Twórcy

autor

Girao-Silva R.

autor

Craveirinha J.

autor

Clímaco J.

• Department of Electrical Engineering Science and Computers, University of Coimbra, Pólo II, Pinhal de Marrocos, P-3030-290 Coimbra, Portugal; Institute of Computers and Systems Engineering, of Coimbra (INESC-Coimbra), Rua Antero de Quental, 199, P-3000-0

Bibliografia

• [1] A. P. Wierzbicki, “Telecommunications, multiple criteria analysis and knowledge theory”, J. Telecommun. Inform. Technol., vol. 3, pp. 3–13, 2005.
• [2] J. Cl´ımaco and J. Craveirinha, “Multicriteria analysis in telecommunication network planning and design – problems and issues”, in Multiple Criteria Decision Analysis – State of the Art Surveys, J. Figueira, S. Greco, and M. Ehrgott, Eds., Int. Ser. Oper. Res. & Manage. Sci., vol. 78. New York: Springer, 2005, pp. 899–951.
• [3] J. C. N. Cl´ımaco, J. M. F. Craveirinha, and M. M. B. Pascoal, “Multicriteria routing models in telecommunication networks – overview and a case study”, in Advances in Multiple Criteria Decision Making and Human Systems Management: Knowledge and Wisdom, Y. Shi, D. L. Olson, and A. Stam, Eds. Amsterdam: IOS Press, 2007, pp. 17–46.
• [4] J. Craveirinha, R. Gir˜ao-Silva, and J. Cl´ımaco, “A meta-model for multiobjective routing in MPLS networks”, Cent. Eur. J. Oper. Res., vol. 16, no. 1, pp. 79–105, 2008.
• [5] J. Craveirinha, R. Gir˜ao-Silva, J. Cl´ımaco, and L. Martins, “A hierarchical multiobjective routing model for MPLS networks with two service classes – analysis and resolution approach”, Res. Rep. 5/2007, INESC-Coimbra, Oct. 2007.
• [6] D. Mitra, J. A. Morrison, and K. G. Ramakrishnan, “Optimization and design of network routing using refined asymptotic approximations”, Perform. Eval., vol. 36–37, pp. 267–288, 1999.
• [7] L. Martins, J. Craveirinha, and J. Cl´ımaco, “A new multiobjective dynamic routing method for multiservice networks: modelling and performance”, Comp. Manage. Sci., vol. 3, no. 3, pp. 225–244, 2006.
• [8] R. Gir˜ao-Silva, J. Craveirinha, and J. Cl´ımaco, “Hierarchical multiobjective routing in MPLS networks with two service classes – a heuristic solution” (accepted for publication in Int. Trans. Oper. Res., 2009).
• [9] S. Kirkpatrick, C. D. Gellat Jr, and M. P. Vecchi, “Optimization by simulated annealing”, Science, vol. 220, no. 4598, pp. 671–680, 1983.
• [10] F. Glover and M. Laguna, “Tabu search”, in Modern Heuristic Techniques for Combinatorial Problems, Adv. Top. Comp. Sci. Oxford: Blackwell Sci. Publ., 1993, pp. 70–150.
• [11] Model-Based Decision Support Methodology with Environmental Applications, A. P. Wierzbicki, M. Makowski, and J. Wessels, Eds. Dordrecht: Kluwer, 2000.
• [12] F. Kelly, “Notes on effective bandwidths”, in Stochastic Networks: Theory and Applications, F. P. Kelly, S. Zachary, and I. Ziedins, Eds. Roy. Stat. Soc. Lect. Notes, vol. 4. Oxford: Oxford University Press, 1996, pp. 141–168.
• [13] L. Martins, J. Craveirinha, and J. Cl´ımaco, “A new multiobjective dynamic routing method for multiservice networks – modelling, resolution and performance”, Res. Rep. 2/2005, INESC-Coimbra, Feb. 2005.
• [14] H. M. Elsayed, M. S. Mahmoud, A. Y. Bilal, and J. Bernussou, “Adaptive alternate-routing in telephone networks: optimal and equilibrium solutions”, Inform. Decis. Technol., vol. 14, pp. 65–74, 1988.
• [15] J. Craveirinha, L. Martins, T. Gomes, C. H. Antunes, and J. N. Cl´ımaco, “A new multiple objective dynamic routing method using implied costs”, J. Telecommun. Inform. Technol., vol. 3, pp. 50–59, 2003.
• [16] L. Martins, J. Craveirinha, J. N. Cl´ımaco, and T. Gomes, “Implementation and performance of a new multiple objective dynamic routing method for multiexchange networks”, J. Telecommun. Inform. Technol., vol. 3, pp. 60–66, 2003.
• [17] F. P. Kelly, “Routing in circuit-switched networks: Optimization, shadow prices and decentralization”, Adv. Appl. Probab., vol. 20, no. 1, pp. 112–144, 1988.
• [18] A. Faragó, S. Blaabjerg, L. Ast, G. Gordos, and T. Henk, “A new degree of freedom in ATM network dimensioning: optimizing the logical configuration”, IEEE J. Selec. Areas Commun., vol. 13, no. 7, pp. 1199–1206, 1995.
• [19] J. Craveirinha, L. Martins, and J. N. Cl´ımaco, “Dealing with complexity in a multiobjective dynamic routing model for multiservice networks – a heuristic approach”, in Proc. 15th Mini-EURO Conf. MUDSM 2004, Coimbra, Portugal, 2004.
• [20] L.Martins, J. Craveirinha, J. Cl´ımaco, and T. Gomes, “Modeling and performance analysis of a new multiple objective dynamic routing method for multiexchange networks”, Res. Rep. ET-N8-5 – 11/2002, INESC-Coimbra, July 2002.
• [21] R. Gir˜ao-Silva, J. Craveirinha, and J. Cl´ımaco, “Hierarchical multiobjective routing in MPLS networks with two service classes – a heuristic resolution approach”, Res. Rep. 8/2008, INESC-Coimbra, July 2008.
• [22] K. A. Dowsland, “Simulated annealing”, in Modern Heuristic Techniques for Combinatorial Problems, Adv. Top. Comp. Sci. Oxford: Blackwell Sci. Publ., 1993, pp. 20–69.
• [23] E. I. Oyman and C. Ersoy, “Multicast routing using simulated annealing”, in Proc. COMCON’5, Crete, Greece, 1995, pp. 419–424.
• [24] E. I. Oyman and C. Ersoy, “Multipoint communication using simulated annealing”, in Proc. Birinci Bilgisayar Aglari Symp. BAS’96, Istanbul, Turkey, 1996, pp. 136–143.
• [25] Z. Kun, W. Heng, and L. Feng-Yu, “Distributed multicast routing for delay and delay variation-bounded Steiner tree using simulated annealing”, Comput. Commun., vol. 28, no. 11, pp. 1356–1370, 2005.
• [26] S. Shimizu, T. Miyoshi, and Y. Tanaka, “Multicast network design by the use of heuristic algorithms”, in Proc. APSITT’99, Ulaanbaatar, Mongolia, 1999.
• [27] T. Miyoshi, S. Shimizu, and Y. Tanaka, “Fast topological design with simulated annealing for multicast networks”, in Proc. ISCC’02, Taormina, Italy, 2002, pp. 959–966.
• [28] M. Randall, G. McMahon, and S. Sugden, “A simulated annealing approach to communication network design”, J. Comb. Optim., vol. 6, no. 1, pp. 55–65, 2002.
• [29] T. Thomadsen and J. Clausen, “Hierarchical network design using simulated annealing”, Tech. Rep. IMM-2002-14, DTU, Sept. 2002.
• [30] M. Rios, V. Marianov, and C. Abaroa, “Design of heterogeneous traffic networks using simulated annealing algorithms”, in Proc. ICOIN 2005, C. Kim, Ed., LNCS, vol. 339. Heidelberg: Springer- Verlag, 2005, pp. 520–530.
• [31] J. M. de Kock and A. E. Krzesinski, “Computing an optimal virtual path connection network by simulated annealing”, in Proc. SATNAC’98, Cape Town, South Africa, 1998, pp. 611–617.
• [32] Y. Cui, K. Xu, J. Wu, Z. Yu, and Y. Zhao, “Multi-constrained routing based on simulated annealing”, in Proc. IEEE ICC’03, Anchorage, USA, 2003, vol. 3, pp. 1718–1722.
• [33] B. Zhang, C. Huang, and M. Devetsikiotis, “Simulated annealing based bandwidth reservation for QoS routing”, in Proc. IEEE ICC 2006, Istanbul, Turkey, 2006.
• [34] X. Yao, “Call routing by simulated annealing”, Int. J. Electron., vol. 79, no. 4, pp. 379–387, 1995.
• [35] R. Gir˜ao-Silva, J. Craveirinha, and J. Cl´ımaco, “Hierarchical multiobjective routing in MPLS networks with two service classes – a meta-heuristic resolution approach”, Res. Rep. 13/2008, INESCCoimbra, Sept. 2008.
• [36] F. Glover and M. Laguna, “Tabu search”, http://www.dei.unipd.it/ ~fisch/ricop/tabu search glover laguna.pdf
• [37] A. Hertz, E. Taillard, and D. de Werra, “A tutorial on tabu search”, http://www.dei.unipd.it/∼fisch/ricop/tabu search tutorial.pdf
• [38] J. Xu, S. Y. Chiu, and F. Glover, “Probabilistic tabu search for telecommunications network design”, Comb. Optim., vol. 1, no. 1, pp. 69–94, 1996.
• [39] J. Xu, S. Y. Chiu, and F. Glover, “Tabu search for dynamic routing communications network design”, Telecommun. Syst., vol. 8, pp. 55–77, 1997.
• [40] M. Laguna and F. Glover, “Bandwidth packing: a tabu search approach”, Manage. Sci., vol. 39, no. 4, pp. 492–500, 1993.
• [41] M. Gendreau, J.-F. Larochelle, and B. Sans`o, “A tabu search heuristic for the Steiner tree problem”, Networks, vol. 34, no. 2, pp. 162–172, 1999.
• [42] J. Shen, F. Xu, and P. Zheng, “A tabu search algorithm for the routing and capacity assignment problem in computer networks”, Comput. Oper. Res., vol. 32, no. 11, pp. 2785–2800, 2005.
• [43] T. F. Noronha and C. C. Ribeiro, “Routing and wavelength assignment by partition colouring”, Eur. J. Oper. Res., vol. 171, no. 3, pp. 797–810, 2006.
• [44] S. Routray, A. M. Sherry, and B. V. R. Reddy, “Bandwidth optimization through dynamic routing in ATM networks: genetic algorithm & tabu search approach”, T. Eng. Comput. Technol., vol. 12, pp. 171–175, Mar. 2006.
• [45] D. Mitra and K. G. Ramakrishnan, “Techniques for traffic engineering of multiservice, multipriority networks”, Bell Labs Tech. J., vol. 6, no. 1, pp. 139–151, 2001.
• [46] A. M. Law and W. D. Kelton, Simulation Modeling and Analysis, Ind. Eng. Manage. Sci. 2nd ed. New York: McGraw-Hill, 1991.
• [47] J. Craveirinha, T. Gomes, S. Esteves, and L. Martins, “A method for calculating marginal variances in teletraffic networks with multiple overflows”, in Proc. First Euro-Japanese Worksh. Stoch. Risk Model. Finan. Insur. Product. Reliab., J. Janssen and S. Osaki, Eds., Brussels, Belgium, 1998, vol. II.