A new multiple objective dynamic routing method using implied costs

• Autorzy: Craveirinha J. , Martins L. , Gomes T. , Antunes C.H. , Climaco J.N.
• Języki publikacji: EN

Abstrakty

EN

There are advantages in considering the routing problem in integrated communication networks as a multiobjective shortest path problem, having in mind to grasp eventual conflicts and trade-offs among distinct objectives and quality of services (QoS) constraints. On the other hand the utilisation of dynamic routing methods in various types of networks is well known to have significant impact on network performance and cost, namely in overload and failure conditions. This paper presents the detailed formulation of a proposal of a multiple objective dynamic routing method (MODR) of periodic state dependent routing type, enabling to represent distinct QoS related metrics and requirements in a consistent manner. The MODR method present formulation is based on a multiple objective shortest path model with constraints and is prepared to use implied costs as one of the metrics. Alternative paths tor each traffic flow are changed as a function of periodic updates of certain QoS related parameters estimated from real time measurements on the routes and trunks of the network. Such paths are computed by a specialised and efficient variant of a bi-objective shortest path constrained algorithm, developed for the MODR, enabling to incorporate flexible requirements on the QoS metrics. The architecture of the routing system is discussed together with the features of its main modules. An illustrative example of application of the MODR path calculation module to a circuit-switched type network using blocking probability and implied cost as metrics, is also presented, considering different overload conditions.

Słowa kluczowe

EN

dynamic routing; multicriteria decision support systems; traffic management

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

Twórcy

autor

Craveirinha J.

• Departamento de Engenharia Electrotecnica e Computadores, Universidade de Coimbra, Coimbra, Portugal

autor

Martins L.

• Departamento de Engenharia Electrotécnica e Computadores Universidade de Coimbra Pinhal de Marrocos, 3030-290 Coimbra, Portugal INESC Coimbra Rua Antero de Quental, 199, 3000-033 Coimbra, Portugal

autor

Gomes T.

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

autor

Antunes C.H.

• Departamento de Engenharia Electrotécnica e Computadores Universidade de Coimbra Pinhal de Marrocos, 3030-290 Coimbra, Portugal INESC Coimbra Rua Antero de Quental, 199, 3000-033 Coimbra, Portugal

autor

Climaco J.N.

• Departamento de Engenharia Electrotécnica e Computadores Universidade de Coimbra Pinhal de Marrocos, 3030-290 Coimbra, Portugal INESC Coimbra Rua Antero de Quental, 199, 3000-033 Coimbra, Portugal

Bibliografia

• [1] W. C. Lee, M. G. Hluchyj, and P. A. Humblet, “Routing subject to quality of service constraints in integrated communication net- works”, IEEE Network, pp. 46–55, July/Aug. 1995.
• [2] 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.
• [3] 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.
• [4] C. Pornavalai, G. Chakraborty, and N. Shiratori, “Routing with multiple QoS requirements for supporting multimedia applications”, Telecommun. Syst., no. 9, pp. 357–373, 1998.
• [5] C. H. Antunes, J. Craveirinha, J. Clímaco, and C. Barrico, “A multiple objective routing algorithm for integrated communication networks” in ITC-16 Teletraffic Engineering in a Competitive World, P. Key and D. Smith, Eds., Elsevier Science B.V., June 1999, vol. 3b, pp. 1291–1300.
• [6] A. Girard, Routing and Dimensioning in Circuit-Switched Networks. Addison-Wesley, 1990.
• [7] G. R. Ash, Dynamic Routing in Telecommunications Networks. McGraw-Hill, 1998.
• [8] F. P. Kelly, “Routing in circuit-switched networks: optimization, shadow prices and decentralization”, Adv. Appl. Probab., vol. 20, pp. 112–144, 1988.
• [9] E. Q. V. Martins, M. M. B. Pascoal, and J. L. E. Santos, “Deviation algorithms for ranking shortest paths”, Int. J. Foundat. Comput. Sci., no. 10, pp. 247–263, 1999.
• [10] ITU-T Group 2, “Dynamic routing interworking”. Draft text for Rec. E.1XX, 1997.
• [11] T. Gomes, L. Martins, and J. F. Craveirinha, “An efficient algorithm for calculating k shortest paths with a maximum number of arcs”, Investig. Oper., no. 21, pp. 235–244, 2001.
• [12] J. Craveirinha, L. Martins, T. Gomes, C. H. Antunes, and J. Clímaco, “Formulation of a multiple objective dynamic routing method Rusing implied costs – architecture and algorithms”, Tech. Rep. ET-N8-3, INESC-Coimbra, Feb. 2001.
• [13] 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.
• [14] G. R. Ash, “An analytical model for adaptative routing networks”, IEEE Trans. Commun., vol. 41, no. 11, pp. 1748–1759, 1993.