On the performance analysis of a heuristic approach dedicated to a multiobjective dynamic routing model

• Autorzy: Craveirinha J. , Martins L. , Climaco J. N. , Jorge L.
• Języki publikacji: EN

Abstrakty

EN

In previous works the features and a complete formulation for circuit-switched networks of a multiple objective dynamic routing method (MODR) of periodic state dependent routing type were presented. The aim of the model is to resolve a very complex network bi-objective dynamic routing problem, by recurring to a heuristic for synchronous path selection enabling to obtain a good compromise solution in terms of two network performance measures. In this paper we present a study on the performance of variants of the MODR heuristic of synchronous path selection by using relaxations of the values previously calculated for the two network objective functions. This study permitted the development of an improved version of the initial heuristic. Also a comparison of the analytical values of the network objective functions obtained with selected variants of the initial heuristic with the corresponding results from a known reference method, the real time network routing (RTNR) method, given by a discrete-event simulator for single-service networks, is presented.

Słowa kluczowe

EN

multiple criteria analysis; routing; heuristics; telecommunications

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

Twórcy

autor

Craveirinha J.

• Departamento de Engenharia Electrotécnica e Computadores Universidade de Coimbra Pinhal de Marrocos, 3030-290 Coimbra, Portugal

autor

Martins L.

• Departamento de Engenharia Electrotécnica e Computadores Universidade de Coimbra Pinhal de Marrocos, 3030-290 Coimbra, Portugal

autor

Climaco J. N.

• Faculdade de Economia Universidade de Coimbra Av. Dias da Silva 3000 Coimbra, Portugal

autor

Jorge L.

• INESC Coimbra Rua Antero de Quental, 199 3000-033 Coimbra, Portugal

Bibliografia

• [1] G. R. Ash, Dynamic Routing in Telecommunications Networks. New York: McGraw-Hill, 1998.
• [2] G. R. Ash, R. H. Cardwell, and R. P. Murray, “Design and optimization of networks with dynamic routing”, Bell Syst. Tech. J., vol. 60, no. 8, pp. 1787–1820, 1981.
• [3] D. Bertsekas and R. Gallager, Data Networks. Upper Saddle River: Prentice-Hall, 1992.
• [4] J. Cl´ımaco and J. Craveirinha, “Multicriteria analysis in telecommunication planning and design – problems and issues”, in Multiple Criteria Decision Analysis: State of the Art Surveys, J. Figueira, S. Greco, and M. Ehrgott, Eds., International Series in Operations Research & Management Science. New York: Springer Science, 2005, vol. 78, pp. 899–951.
• [5] J. Cl´ımaco, J. Craveirinha, and M. Pascoal, “A bicriterion approach for routing problems in multimedia networks”, Networks, vol. 41, no. 4, pp. 206–219, 2003.
• [6] J. Craveirinha, L. Martins, T. Gomes, C. H. Antunes, and J. Cl´ımaco, “A new multiple objective dynamic routing method using implied costs”, J. Telecommun. Inform. Technol., no. 3, pp. 50–59, 2003.
• [7] 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., no. 14, pp. 65–74, 1988.
• [8] S. C. Erbas and C. Erbas, “A multiobjective off-line routing model for MPLS networks”, in Proceedings of the 18th International Teletraffic Congress, J. Charzinki, R. Lehert, and P. Tra-Gia, Eds. 2003.
• [9] J. S. Kaufman, “Blocking in a shared resource environment”, IEEE Trans. Commun., vol. 29, no. 10, pp. 1474–1481, 1981.
• [10] F. P. Kelly, “Routing in circuit-switched networks: optimization, shadow prices and decentralization”, Adv. Appl. Probab., no. 20, pp. 112–144, 1988.
• [11] F. Kuipers, T. Korkmaz, M. Krunz, and P. Mieghem, “A review of constraint-based routing algorithms”. Tech. Rep., Delft University of Technology, June 2002, http://wwwtvs.et.tudelft.nl/people/fernando/papers/TRreviewqosalg.pdf.
• [12] E. Q. V. Martins, M. M. B. Pascoal, and J. L. E. Santos, “Deviation algorithms for ranking shortest paths”, Int. J. Found. Comput. Sci., no. 10, pp. 247–263, 1999.
• [13] L. Martins, J. Craveirinha, and J. Cl´ımaco, “A new multiobjective dynamic routing method for multiservice netwoks – modelling and performance”, in Proceedings of the International Network Optimization Conference, W. Ben-Ameur and A. Petrowski, Eds. Paris-Evry: Institut National des T´el´ecommunications, 2003, pp. 404–409.
• [14] L. Martins, J. Craveirinha, and J. Cl´ımaco, “A new multiobjective dynamic routing method for multiservice networks – modelling, resolution and performance”. Tech. Rep., INESC-Coimbra, May 2003.
• [15] L. Martins, J. Craveirinha, J. Cl´ımaco, and T. Gomes, “Modelling and performance analysis of a new multiple objective dynamic routing method for multiexchange networks”. Tech. Rep., INESCCoimbra, July 2002.
• [16] L. Martins, J. Craveirinha, J. Cl´ımaco, and T. Gomes, “Implementation and performance of a new multiple objective dynamic routing method for multiexchange networks”, J. Telecommun. Inform. Technol., no. 3, pp. 60–66, 2003.
• [17] L. Martins, J. Craveirinha, J. Cl´ımaco, and T. Gomes, “On a bidimensional dynamic alternative routing method”, Eur. J. Oper. Res. (special issue on advances in complex systems modeling), vol. 166, no. 3, 2005 (to appear).
• [18] D. Mitra, J. A. Morrison, and K. G. Ramakrishnan, “Optimization and design of network routing using refined asymptotic approximations”, Perfor. Eval. Int. J., vol. 36-37, pp. 267–288, 1999.
• [19] D. Mitra and J. B. Seery, “Comparative evaluation of randomized and dynamic routing strategies for circuit-switched networks”, IEEE Trans. Commun., vol. 39, no. 1, pp. 102–116, 1991.
• [20] C. Pornavalai, G. Chakraborty, and N. Shiratori, “Routing with multiple QoS requirements for supporting multimedia applications”, Telecommun. Syst., no. 9, pp. 357–373, 1998.
• [21] J. W. Roberts, “Teletraffic models for the telecom 1 integrated services network”, in Proc. 10th Int. Teletraff. Congr., Montreal, Canada, 1983.
• [22] R. Vogel, R. G. Herrtwich, W. Kalfa, H. Wittig, and L. C. Wolf, “QoS – based routing of multimedia streams in computer networks”, IEEE J. Selec. Areas Commun., vol. 14, no. 7, pp. 1235–1244, 1996.
• [23] Z. Wang and J. Crowcroft, “Quality-of-service routing for supporting multimedia appications”, IEEE J. Selec. Areas Commun., vol. 14, no. 7, pp. 1228–1234, 1996.