On the performance analysis of a heuristic approach dedicated to a multiobjective dynamic routing model
DOI:
https://doi.org/10.26636/jtit.2005.3.330Keywords:
multiple criteria analysis, routing, heuristics, telecommunicationsAbstract
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.
Downloads
References
[1] G. R. Ash, Dynamic Routing in Telecommunications Networks. New York: McGraw-Hill, 1998.
View in Google Scholar
[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.
View in Google Scholar
[3] D. Bertsekas and R. Gallager, Data Networks. Upper Saddle River: Prentice-Hall, 1992.
View in Google Scholar
[4] J. Climaco 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.
View in Google Scholar
[5] J. Climaco, J. Craveirinha, and M. Pascoal, „A bicriterion approach for routing problems in multimedia networks”, Networks, vol. 41, no. 4, pp. 206-219, 2003.
View in Google Scholar
[6] J. Craveirinha, L. Martins, T. Gomes, C. H. Antunes, and J. Climaco, „A new multiple objective dynamic routing method using implied costs”, J. Telecommun. Inform. Technol., no. 3, pp. 50-59, 2003.
View in Google Scholar
[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.
View in Google Scholar
[8] S. C. Erbas and C. Erbas, „A multi-objective off-line routing model for MPLS networks”, in Proceedings of the 18th International Teletraffic Congress, J. Charzinski, R. Lehnert, and P. Tran-Gia, Eds. 2003.
View in Google Scholar
[9] J. S. Kaufman, „Blocking in a shared resource environment”, IEEE Trans. Commun., vol. 29, no. 10, pp. 1474-1481, 1981.
View in Google Scholar
[10] F. P. Kelly, „Routing in circuit-switched networks: optimization, shadow prices and decentralization”, Adv. Appl. Probab., no. 20, pp. 112-144, 1988.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[13] L. Martins, J. Craveirinha, and J. Climaco, „A new multi-objective dynamic routing method for multiservice networks - modelling and performance”, in Proceedings of the International Network Optimization Conference, W. Ben-Ameur and A. Petrowski, Eds. Paris-Evry: Institut National des Telecommunications, 2003, pp. 404-409.
View in Google Scholar
[14] L. Martins, J. Craveirinha, and J. Climaco, „A new multi-objective dynamic routing method for multiservice networks - modelling, resolution and performance”. Tech. Rep., INESC-Coimbra, May 2003.
View in Google Scholar
[15] L. Martins, J. Craveirinha, J. Climaco, and T. Gomes, „Modelling and performance analysis of a new multiple objective dynamic routing method for multiexchange networks”. Tech. Rep., INESC Coimbra, July 2002.
View in Google Scholar
[16] L. Martins, J. Craveirinha, J. Climaco, 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.
View in Google Scholar
[17] L. Martins, J. Craveirinha, J. Climaco, 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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[21] J. W. Roberts, „Teletraffic models for the telecom integrated services network”, in Proc. 10th Int. Teletraff. Congr., Montreal, Canada, 1983.
View in Google Scholar
[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.
View in Google Scholar
[23] Z. Wang and J. Crowcroft, „Quality-of-service routing for supporting multimedia applications”, IEEE J. Selec. Areas Commun., vol. 14, no. 7, pp. 1228-1234, 1996.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2005 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
