DOI:

https://doi.org/10.14483/23448393.2158

Published:

2006-11-30

Issue:

Vol. 12 No. 2 (2007): July - December

Section:

Science, research, academia and development

Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio

Computational Intelligence Applied To Based Quality Of Service Evaluation

Authors

  • Octavio José Salcedo Parra Universidad Distrital Francisco José de Caldas
  • Héctor Cristyan Manta Caro Universidad Distrital Francisco José de Caldas
  • Lilia Edith Aparicio Pico Universidad Distrital Francisco José de Caldas

Keywords:

Calidad de ser vicio, encaminamiento inter-dominio, inteligencia computacional, lógica difusa (es).

References

F. Kuipers. "Quality of Service Routing in the Internet: Theory, Complexity and Algorithms". PhD thesis, Delft University, 2004.

F. Kuipers; Piet F. Van Mieghem, "Conditions that Impact the Complexity of QoS Routing", IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.717-730, 2005.

R. Braden; D. Clark; S. Shenker, "Integrated services in the Internet Architecture: an Overview". IETF Internet Engineering Task Force, RFC 1633, 1994. http:// www.ietf.org/rfc/rfc1633.txt

S. Blake; D. Black; M. Carlson; E. Davies; Z. Wang; W. Weiss, "An Architecture for Differentiated Services ", IETF Internet Engineering Task Force, RFC 2475, 1998. http:/ /www.ietf.org/rfc/rfc2475.txt

D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus. "Requirements for Traffic Engineering Over MPLS". IETF Internet Engineering Task Force, RFC 2702, 1999. http://www.ietf.org/rfc/rfc2702.txt

A. Alkahtani; M.E. Woodward; K. Al-Begain, "An Overview of Quality of Service and QoS Routing in Communication Networks, Department of Computing at the University of Brandford, UK, PGNet, ISBN: 1-9025-6009-4, 2003.

Ilmari Juva. "Analysis of Quality of Service Routing Approaches and Algorithms", Master Thesis, Department of Engineering Physics and Mathematics, Helsinki University of Technology, 2003.

Andrzej Beben, "EQ-BGP: An Efficient Inter-Domain QoS Routing Protocol", 20th International Conference on Advanced Information Networking and Applications, Volume 2, pp. 560-564, 2006.

Tielei Zhang, Yong Cui, Youjian Zhao, Lizheng Fu, Turgay Korkmaz, "Scalable BGP QoS Extension with Multiple Metrics," ICNS, p. 80, International conference on Networking and Services (ICNS'06), 2006.

A. Sahoo. "An OSPF based load sensitive QoS routing Algorithm using Alternate Paths", Proceedings of International Conference on Computer Communications and Networks, 2002.

S. Norden; J. Turner, "New Inter-domain QoS Routing Algorithms", Technical Report WUCS-02-03, Department of Computer Science, Washington University, 2002.

Li Xiao; King-Shan Lui; Jun Wang; K. Nahrstedt, "QoS extension to BGP". Proceedings 10th IEEE International Conference on Networks Protocols, 2002.

Venkatesh Sarangan; Donna Ghosh; Raj Ghosh. "Capacity-Aware State Aggregation for Inter-Domain QoS Routing", IEEE Transactions on Multimedia, vol. 1, No. 4, 2006.

G. Cristallo and C. Jacquenet, "Providing Quality of Service Indication by the BGP-4 Protocol: the QOS_NLRI attribute", IETF draft-jacquenet-qos-nlri-05.txt, 2003.

K.H. Ho, N. Wang, P. Trimintzios and G. Pavlou, "Traffic Engineering for Inter-domain Quality of Service," Proc. London Communications Symposium (LCS), London, UK, September 2003.

Uhlig Steve, "A Multiple-objectives Evolutionary Perspective to Interdomain Traffic Engineering", International Journal of Computational Intelligence and Applications, 5, 2, 2005, p. 215-230.

X. Masip-Bruin, M. Yannuzzi, J. Domingo-Pascual, A. Fonte, M. Curado, E. Monteiro, F. Kuipers, P. Van Mieghem, S. Avallone, G. Ventre, P. Aranda-Gutierrez, M. Hollick, R. Steinmetz, L. Iannone, and K. Salamatian. "Research Challenges in QoS Routing". Computer Communications, 29(5):563­581, March 2006.

M. Yannuzzi, A. Fonte, X. Masip, E. Monteiro, S. Sánchez, M. Curado, J. Domingo, "A proposal for inter-domain QoS Routing based on distributed overlay entities and QBGP", Proceedings of the First International Workshop on QoS Routing (WQoSR), LNCS 3266, Barcelona, 2004.

L. Subramanian, I. Stoica, R. H. Katz, H. Balakrishnan, "OverQoS: An Overlay Based Architecture for Enhancing Internet QoS," USENIX/ACM Symposium on Networked System Design and Implementation, San Francisco, CA, 2004.

ITU-T Recommendation E.800, "Terms and Definitions Related to Quality of Service and Network Performance Including Dependability".

E. Crawley, R. Nair, B. Rajagopalan, H. Sandick, "A Framework for QoS-based Routing in the Internet", IETF Internet Engineering Task Force, RFC 2386, 1998. http://www.ietf.org/rfc/rfc2386.txt

G. Cristallo and C. Jacquenet, "An Approach to Interdomain Traffic Engineering", in Proceedings of XVIII World Telecommunications Congress (WTC2002), Paris, France, September 2002.

Steve Uhlig, Bruno Quoitin, "Tweak-it: BGP-based interdomain traffic engineering for transit ASes", Next generation Internet networks traffic engineering 2005 (NGI2005), Roma, Italy, April 18-20, 2005, IEEE, 2005, p. 75-82.

Bruno Quoitin, Steve Uhlig, Cristel Pelsser, Louis Swinnen, Olivier Bonaventure, "Interdomain traffic engineering with BGP", IEEE Communications Magazine, 41, 5, 2003, p. 1-9.

Jun-Hong Cui; Swapna S. Gokhale; Li Lao, "Distributed QoS Routing for Backbone Overlay Networks", In Proceedings of IFIP Networking, Coimbra, Portugal, 2006.

R. Guerin, A. Orda ,"QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms", IEEE INFOCOM'97, Kobe, Japan

A. Vasilakos; C. Ricudis; K. Anagnostakis; W. Pedryca; A. Pitsillides. "Evolutionary-fuzzy prediction for strategic QoS routing in broadband networks". IEEE World Congress on Computational Intelligence, IEEE International Conference on Fuzzy Systems Volume 2, Issue, 4-9 May 1998 Page(s):1488 - 1493 vol.2

Ahmed Shawky Moussa. "The Implementation of Intelligent QoS Networking by the Development and Utilization of Novel Cross-Disciplinary Soft Computing Theories and Techniques", Ph.D Dissertation at the Florida State University, 2003.

ITU-T Recommendation Y.1540, "IP packet transfer and availability performance parameters".

ITU-T Recommendation Y.1541, "Network Performance Objectives for IP-based Services".

How to Cite

APA

Salcedo Parra, O. J., Manta Caro, H. C., and Aparicio Pico, L. E. (2006). Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio. Ingeniería, 12(2), 4–14. https://doi.org/10.14483/23448393.2158

ACM

[1]
Salcedo Parra, O.J. et al. 2006. Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio. Ingeniería. 12, 2 (Nov. 2006), 4–14. DOI:https://doi.org/10.14483/23448393.2158.

ACS

(1)
Salcedo Parra, O. J.; Manta Caro, H. C.; Aparicio Pico, L. E. Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio. Ing. 2006, 12, 4-14.

ABNT

SALCEDO PARRA, Octavio José; MANTA CARO, Héctor Cristyan; APARICIO PICO, Lilia Edith. Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio. Ingeniería, [S. l.], v. 12, n. 2, p. 4–14, 2006. DOI: 10.14483/23448393.2158. Disponível em: https://revistas.udistrital.edu.co/index.php/reving/article/view/2158. Acesso em: 19 mar. 2024.

Chicago

Salcedo Parra, Octavio José, Héctor Cristyan Manta Caro, and Lilia Edith Aparicio Pico. 2006. “Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio”. Ingeniería 12 (2):4-14. https://doi.org/10.14483/23448393.2158.

Harvard

Salcedo Parra, O. J., Manta Caro, H. C. and Aparicio Pico, L. E. (2006) “Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio”, Ingeniería, 12(2), pp. 4–14. doi: 10.14483/23448393.2158.

IEEE

[1]
O. J. Salcedo Parra, H. C. Manta Caro, and L. E. Aparicio Pico, “Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio”, Ing., vol. 12, no. 2, pp. 4–14, Nov. 2006.

MLA

Salcedo Parra, Octavio José, et al. “Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio”. Ingeniería, vol. 12, no. 2, Nov. 2006, pp. 4-14, doi:10.14483/23448393.2158.

Turabian

Salcedo Parra, Octavio José, Héctor Cristyan Manta Caro, and Lilia Edith Aparicio Pico. “Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio”. Ingeniería 12, no. 2 (November 30, 2006): 4–14. Accessed March 19, 2024. https://revistas.udistrital.edu.co/index.php/reving/article/view/2158.

Vancouver

1.
Salcedo Parra OJ, Manta Caro HC, Aparicio Pico LE. Inteligencia Computacional Aplicada a la Evaluación de Calidad de Servicio. Ing. [Internet]. 2006 Nov. 30 [cited 2024 Mar. 19];12(2):4-14. Available from: https://revistas.udistrital.edu.co/index.php/reving/article/view/2158

Download Citation

Visitas

390

Dimensions


PlumX


Downloads

Download data is not yet available.

Ingeniería, 2007-00-00 vol:12 nro:2 pág:4-14

Inteligencia computacional aplicada a la evaluación de calidad de servicio

Computational intelligence applied to based quality of service evaluation

Cristyan Manta Caro
Investigador del grupo de investigación
en Resonancia Magnética RM-UD.
Edith Aparicio Pico
Directora del grupo de investigación GITEM,
Universidad Distrital
Octavio J.Salcedo Parra
Director del grupo de investigación Internet Inteligente,
Universidad Distrital.

Resumen

La evaluación de la calidad de servicio específicamente en el encaminamiento de paquetes satisface requerimientos de desempeño y maximiza la utilización de los recursos de la red por medio de la selección de caminos con base en los recursos que se requieran. Muchas de las investigaciones acerca del soporte de la calidad de servicio en el encaminamiento se enfocan en el encaminamiento de un solo dominio. BGP, el estándar de facto para el encaminamiento inter-dominio no provee mecanismo para soportar la calidad de servicio y tomando en consideración que la calidad de servicio experimentada por los usuarios esta influenciada por todos los dominios a través del camino, es necesario el desarrollo de esquemas de encaminamiento inter-dominio que evalúen eficientemente la calidad de servicio.

La investigación propuesta busca la aplicación de la inteligencia computacional en la evaluación de la calidad de servicio en un prototipo de encaminamiento inter-dominio con base en políticas de encaminamiento inter-dominio. Se presenta un acercamiento basado en lógica difusa para la evaluación de la calidad de servicio, a fin de seleccionar caminos en función de múltiples criterios heterogéneos.

Palabras clave:
Calidad de servicio, encaminamiento inter-dominio, inteligencia computacional, lógica difusa.

Abstract

The quality of service QoS evaluation specifically in the packet routing satisfies requirements of performance and maximizes the resources utilization of the network by means of paths selection based on the resources that are needed. More of the investigations about the quality of service support in the routing are focused in the one-domain routing. BGP, the standard for the inter-domain routing does not provide mechanism to evaluate the quality of service and taking in consideration that the quality of service experienced by the users, it is influenced by all the domains through the endto-end path, it is necessary the development of schemes of inter-domain routing that evaluate efficiently the quality of service. The proposed research is focused in the computational intelligence application in a prototype of interdomain routing based in policies. We present a fuzzy logic approach to evaluate the quality of service, in this way select paths depending multiple heterogeneous criteria.

Key words:
Quality of service, inter-domain routing, computational intelligence, fuzzy logic.


1. Introducción

Las redes de telecomunicaciones se han convertido en parte esencial en el desarrollo económico de grandes industrias y de la sociedad en general, esto ha ocasionado un crecimiento exponencial de la red Internet, en cuanto al número de equipos terminales, nodos intermedios, puertas de enlace y por supuesto un aumento en la demanda de mejores características de servicio en el uso de aplicaciones multimedia de tiempo real. Por tanto, durante los últimos años se han realizado numerosos esfuerzos hacia el mejoramiento de la calidad de servicio QoS Quality of Service, esto con el fin de alcanzar mayor satisfacción del cliente, lo que conduce a un mayor beneficio a los proveedores de servicios de telecomunicaciones. En últimas en búsqueda de la eficacia y eficiencia en la utilización de los recursos con que cuenta la red.

Dos de los temas claves en el soporte de la calidad de servicio en las redes de comunicaciones son las especificaciones de la calidad de servicio y su evaluación en el encaminamiento. Las especificaciones de la calidad de servicio apuntan hacia la investigación de cuales son los requerimientos de los usuarios de la red y cuantificarlos con exactitud. La evaluación de la calidad de servicio en el encaminamiento no sólo involucra seleccionar un camino para transmitir los datos de la fuente hacia el destino, sino que además se deben satisfacer restricciones u optimizar requerimientos. Debido a los diversos requerimientos a cumplir, el encaminamiento basado en calidad de servicio se considera un problema NP-completo [1], [2] y no puede ser resuelto por un simple y eficiente algoritmo. Todo lo anterior ha dado inicio a la investigación del problema de la calidad de servicio, resultando en propuestas de arquitecturas basadas en calidad de servicio como: servicios integrados IntServ [3], servicios diferenciados DiffServ [4], MPLS basado en restricciones e ingeniería de tráfico [5], [6], [7]; propuestas en protocolos de encaminamiento como: EQ-BGP [8], [9], QOSPF [10], PNNI Private Network-to-Network Interface y algoritmos de encaminamiento con evaluación calidad de servicio [11], [12], [13].

En la actualidad, la evaluación de la calidad de servicio en redes IP multi-dominio es un área ampliamente investigada, tomando en consideración que la calidad de servicio experimentada por los usuarios esta influenciada por todos los dominios a través del camino, es necesario el desarrollo de esquemas de encaminamiento inter-dominio que evalúen eficientemente la calidad de servicio.

Mientras existe un número considerable de propuestas para el desarrollo de encaminamiento intra-dominio evaluando la calidad de servicio, donde se destacan los acercamientos de Q-OSPF QoS Routing Mechanisms and OSPF Extensions [10], las soluciones para el desarrollo de acercamientos en el encaminamiento inter-dominio están aún bajo investigaciones. Muchas de los acercamientos en este aspecto involucran el mejoramiento del protocolo usado normalmente, BGP-4 [8], [12]; pero no se han planteado acercamientos basados en inteligencia computacional. Este tipo de acercamientos involucra la realización de extensiones a BGP, modificando sus mensajes de intercambio de información de encaminamiento, el manejo de las tablas de encaminamiento y por supuesto el algoritmo de selección del mejor camino.

Otro tipo de propuestas, involucra la aplicación de técnicas de ingeniería de tráfico [14]-[16] y en recientes propuestas se propone la utilización de entidades sobrepuestas que realicen el intercambio de información con los pares BGP [17]-[19]. La investigación propuesta busca, basados en los conceptos y desarrollos en inteligencia computacional desarrollar un prototipo de encaminamiento inter-dominio con evaluación de la calidad de servicio.

2. Fundamentos de calidad de servicio

La evaluación de la calidad de servicio en el encaminamiento es un área de investigación activa y de gran interés, debido a la necesidad de proveer funcionalidades especiales de calidad de servicio a los servicios de red emergentes, en aplicaciones sensibles al tiempo, al retardo y a su variación, funcionalidades que no pueden ser proporcionados por los protocolos de encaminamiento convencionales que no evalúan parámetros de calidad de servicio para seleccionar el mejor camino.

El aprovisionamiento de servicios basados en calidad de servicio es en términos generales un problema extremadamente complejo, y una parte significativa de esta complejidad se encuentra en la capa de encaminamiento. El problema de la evaluación de la calidad de servicio con múltiples restricciones aditivas es considerado NP-hard [2]. Así, el amplio desarrollo de servicios de red novedosos demanda el entendimiento de la esencia de la evaluación de la calidad de servicio, y de la factibilidad y accesibilidad de las propuestas a este problema.

2.1. Concepto de calidad de servicio

Uno de los pasos más importantes en el manejo de la calidad de servicio en redes de telecomunicaciones es especificar cuales son los requerimientos y cuantificarlos con exactitud. Estos parámetros de calidad de servicio tienen que ser definidos para cada una de las capas de la arquitectura de la red de telecomunicaciones.

En telecomunicaciones, la calidad de servicio es definida por la UIT-T Unión Internacional de Telecomunicaciones como: "Un efecto colectivo del desempeño del servicio el cual determina el grado de satisfacción de un usuario del servicio" [20]. En [21] la IETF Internet Engineeing Task Force la define como: "el conjunto de requerimientos ha ser provisto por la red mientras se transporta un flujo de información". Algunos otros autores la definen como: "la capacidad de una red para proveer mejores servicios a tráfico de red selectivo sobre tecnologías heterogéneas".

2.2. Métricas de calidad de servicio

El tráfico transmitido a través de las redes de comunicaciones se caracteriza en forma muy general, por cuatro parámetros primarios [6]:

  • La probabilidad de pérdida de paquetes,packet loss probability.
  • El retardo extremo a extremo, end-to-end delay.
  • La variación de retardo, jitter.
  • El ancho de banda disponible, available bandwidth.

El valor de la métrica sobre un camino puede ser una de las siguientes composiciones:

· Métricas aditivas: este puede ser representado matemáticamente como:

Donde m(p) es la métrica total sobre el camino (p), lki es un enlace en el camino (p), LK es el número de enlaces en el camino ( p) ei = 1,...,LK. El retardo, la variación del retardo, y el costo son ejemplos de este tipo de métrica.

· Métricas cóncavas: pueden ser representadas matemáticamente como:

El ancho de banda es un ejemplo de este tipo de composición. El ancho de banda al que se refiere esta métrica es el ancho de banda residual disponible para nuevo tráfico. Este puede definirse como el mínimo de los ancho de banda residuales de todos los enlaces en el camino o también se conoce como el ancho de banda de embotellamiento.

·Métricas multiplicativas: estas pueden ser representadas matemáticamente de la siguiente manera:

La probabilidad de pérdida (l), indirectamente, es un ejemplo de este tipo de composición. La métrica de probabilidad de pérdida puede transformarse en una métrica equivalente que sigue la regla de composición multiplicativa. La probabilidad de transmisión exitosa puede ser expresada como:

Existe un significativo número de factores que han de tenerse en cuenta para la selección de métricas de calidad de servicio. Las métricas tienen que estar en capacidad de modelar con exactitud la fuente de información, la aplicación, reflejando las características básicas de la red.

3.Estado del arte de la evaluación de calidad de servicio

En años recientes, los investigadores en el área han realizado diferentes propuestas a fin de mejorar las características de BGP, por medio de la adición de nuevas capacidades tales como: las extensiones de Calidad de Servicio y la Ingeniería de Tráfico, motivados principalmente por la gran importancia de BGP y la necesidad de soporte a la Calidad de Servicio.

3.1. Calidad de servicio en el encaminamiento

3.1.1. Extensiones de calidad de servicio

Con el objetivo de habilitar las garantías de Calidad de Servicio extremo a extremo, con base al protocolo de encaminamiento BGP-4 se han desarrollado propuestas de extensión de este protocolo, a fin de publicar y encaminar con base a parámetros de Calidad de Servicio. Sin embargo, dos de los principios fundamentales de diseño de BGP: escalabilidad y heterogeneidad hacen que la extensión de este protocolo sea una labor difícil [2]. Los primeros acercamientos al respecto, Encaminamiento de Capacidad de Enlace LCR Link Capacity Routing, y el encaminamiento de Ancho de Banda Disponible ABR Available Bandwidth Routing [12], realizan la publicación y encaminamiento de Calidad de Servicio en BGP en función al Ancho de Banda, sin embargo ninguno de estos acercamientos resuelve en su totalidad los dos tópicos esenciales de diseño.

En la propuesta de Xiao-Lui et al. [12], se extienden las capacidades de BGP a fin de publicar la información de ancho de banda. Pero en lugar de emplear la capacidad del enlace o el valor instantáneo del ancho de banda disponible, se introduce una nueva métrica de Calidad de Servicio: el índice de ancho de banda disponible ABI Available Bandwidth Index. Las principales ventajas de emplear esta nueva métrica es el establecimiento de un mapeo probabilístico dinámico del ancho de banda disponible, además de proporcionar flexibilidad de representar valores de ancho de banda de carácter dinámico y heterogéneo.

En el acercamiento de Beben [8], se propone una extensión de Calidad de Servicio al protocolo BGP, denominado EQ-BGP Enhanced QoS BGP. El objetivo principal es el establecimiento de caminos de extremo a extremo que ofrezcan las garantías más adecuadas en Calidad de Servicio tomando en consideración tanto las capacidades de Calidad de Servicio de los dominios en particular como también los enlaces inter-dominio.

3.1.2. Publicación de métricas múltiples

La propuesta de Zhang-Cui et al. [9], posee un elemento innovador y es la extensión del protocolo BGP para soportar métricas múltiples de Calidad de Servicio. La posibilidad de soportar métricas múltiples involucra que un par BGP tiene que publicar a otro par BGP caminos múltiples hacia un destino, traduciéndose en una sobre carga de información adicional de encaminamiento y por consiguiente en una escasa escalabilidad de la evaluación de Calidad de Servicio en redes extensas.

3.1.3. Ingeniería de tráfico

Adicional a las extensiones se han establecidos mecanismos para el uso de técnicas de ingeniería de tráfico para la manipulación del tráfico entrante y saliente con base en parámetros de calidad de servicio sobre BGP. En la propuesta de Cristallo-Jacquenet [22], se establece un acercamiento vía la utilización de un atributo adicional de BGP-4, denominado QOS_NLRI [14], el cual portará explícitamente la información de calidad de servicio relacionada al alcance de un conjunto de direcciones IP, prefijo IP. De esta forma es posible la influencia sobre el proceso de selección de camino de BGP, mediante la utilización de la ingeniería de tráfico, la cual se enfoca en la optimización del desempeño de la red, con el objetivo de alcanzar la utilización eficiente de los recursos de red y el balance de carga.

En el acercamiento de Uhlig-Quoitin [16], [23], [24], se establece una aplicación de técnicas de optimización evolutivas de múltiples objetivos a la ingeniería de tráfico inter-dominio, el cual puede solucionar problemas relacionados con la manipulación del tráfico entrante y saliente a un sistema autónomo, para aplicaciones tales como la minimización del costo del tráfico saliente de un sistema autónomo sobre múltiple conexiones con balanceo de carga, que podría tomarse como base para establecer acercamientos para el manejo de calidad de servicio.

3.1.4. Superposición de Capa

En contraposición con los acercamientos de extensión e ingeniería de tráfico, una alternativa para la evaluación de Calidad de Servicio en el encaminamiento, es un acercamiento basado en superposición de capa, Overlay-based. Acercamiento que se perfila como fuerte candidato para la solución a este tópico.

En el acercamiento de Yannuzzi-Fonte et al. [17], [18], se propone un esquema de encaminamiento inter-dominio con evaluación de la calidad de servicio, mediante una arquitectura de superposición de capa para la provisión dinámica de calidad de servicio, y la utilización de extensiones e ingeniería de tráfico en la capa de encaminamiento BGP para aprovisionamiento estático de la calidad de servicio.

En la propuesta de Subramanian-Stoica et al. [Sub04], se describe otra arquitectura de superposición de capa, mediante la utilización de un enlace virtual de pérdida controlada, OverQoS. De esta forma, puede proveer una variedad de servicios basados en la probabilidad de pérdida de paquetes y de garantías del ancho de banda. En la propuesta de CuiGokhale et al. [25], se presenta un acercamiento a fin de determinar eficientemente caminos con base en parámetros de calidad de servicio mediante superposición de capa distribuida.

4. Inteligencia computacional aplicada a la evaluación de calidad de servicio

La evaluación de la calidad de servicio en el encaminamiento es una de las funciones clave para la transmisión y distribución de tráfico de audio y video a través de las redes de alta velocidad de próxima generación. La complejidad que involucra el tratamiento de restricciones múltiples en la evaluación de calidad de servicio en el encaminamiento se considera un problema NP-completo [1], [2] y no puede ser resuelto por un simple y eficiente algoritmo. De esta manera, heurísticas como las descritas en [26], o técnicas de inteligencia computacional pueden ser empleadas para encontrar una solución cercana a la óptima [27].

Normalmente, las métricas de calidad de servicio en consideración son las capacidades de almacenamiento de nodo, capacidades residuales de enlace, número de saltos en el camino, entre otros. Muchos de los algoritmos de encaminamiento requieren que esos factores se expresen en conjunto, de forma analítica para su evaluación. Con frecuencia, la combinación de múltiples factores en una forma matemática puede resultar computacionalmente intensa, en evaluación y en desarrollo.

4.1.Características difusas de las métricas de calidad de servicio

4.1.1. Parámetros de calidad de servicio

Existen un conjunto de parámetros para la evaluación de la calidad de servicio que pueden ser llevados a universos difusos, para así ser tenidos en consideración en los procesos de encaminamiento inter-dominio. De tal forma, en la presente investigación se propone la aplicación de la teoría de los conjuntos difusos para la evaluación de la calidad de servicio en el encaminamiento. Así, un primer paso es la definición de las variables de entrada y de las variables de control. Y su cuantificación mediante una función de membresía.

Es de agregar que los parámetros de calidad de servicio y el término calidad de servicio corresponden por su naturaleza a términos difusos [28], y la medición de estos parámetros desde la vista de los usuarios de los recursos de la red se establece en mediciones difusas de carácter lingüístico. De tal forma, la lógica difusa se establece como herramienta de modelado de las características de calidad de servicio y por supuesto también pueden emplearse para la evaluación en ambientes de encaminamiento.

4.1.2. Rec. Y.1540: Parámetros de desempeño en la transferencia de paquetes IP

Esta recomendación define los parámetros a usar para la especificación de velocidad, exactitud, dependencia, y disponibilidad de la transferencia de paquetes IP en redes de telecomunicaciones internacionales, esto es, escenarios inter-dominio. Los usuarios de esta recomendación son proveedores de servicios de Internet, fabricantes de equipos de telecomunicaciones y usuarios finales de servicios de red. Los parámetros de desempeño para la transferencia de paquetes IP se han definido en la recomendación Y.1540 [29] como:

IPTD IP Packet Transfer Delay: Retardo en la transferencia del paquete IP: es el retardo de transmisión total extremo a extremo para una conexión IP.

IPDV IP Packet Delay Variation: Es la variación del retardo en paquetes consecutivos, los cuales fluyen entre dos puntos de medición sobre un camino IP. Este básicamente caracteriza el denominado Jitter.

IPLR IP Packet Loss Ratio: Es la relación de número total de paquetes perdidos al número total de paquetes transmitidos. Ocasionados por la presencia de congestión en los nodos intermedios.

IPER IP Packet Error Rate: Es la relación del número total de paquetes erróneos al número total de paquetes.

SIPR Spurious IP Packet Rate: Es el número total de paquetes IP espurios observados en un punto de medición en un intervalo de tiempo especificado.

4.1.3. Rec. Y.1541: Objetivos de desempeño en la transferencia de paquetes IP

Esta recomendación especifica valores numéricos a ser alcanzados, sobre caminos IP en redes internacionales, para cada uno de los parámetros de desempeño definidos en la recomendación Y.1540 [30]. Los valores que se especifican se agrupan en un conjunto de clases de servicio para establecer una base práctica para la evaluación de parámetros de calidad de servicio en redes IP. Los objetivos de desempeño definidos en la recomendación Y.1541 y las clases de servicio se muestran en la Tabla I, existen diferentes tipos de aplicaciones que pueden ser soportadas por estas clases de servicio especificadas. Cada clase de servicio especifica una combinación de objetivos sobre un subconjunto de los parámetros de desempeño establecidos en [29], las clases y los parámetros asociados aplican a flujos de paquetes IP entre puntos de medición que delimitan una red IP extremo a extremo.

4.2. Descripción del acercamiento con base en inteligencia computacional

4.2.1. Diseño del prototipo: entradas/salidas

Las variables de entrada y salida del control difuso para la evaluación de calidad de servicio se muestran en la Figura 1 junto con la arquitectura del controlador difuso.

Entradas: Número de sistemas autónomos en el camino, Porcentaje de Ancho de banda disponible, índice de utilización del camino, Retardo de tiempo en el camino, Variación de retardo en el camino, Probabilidad de pérdida en el camino, Probabilidad de error en el camino, en la propuesta se decide emplear solo algunas de las entradas.

Salidas: Grado de preferencia del camino, Destino del paquete.

4.2.2. Difusificación de las variables de controlador difuso

La difusificación es el proceso por la cual una variable de entrada o salida del controlador di fuso es convertida en un conjunto de certezas Esto se realiza a través de la construcción de funciones de membresía para cada variable Estas son representaciones gráficas del interva lo de confianza que el diseñador ajusta a cada variable difusa. Los valores lingüísticos que to man las variables son: BA Bajo, MB Medio Bajo MA Medio Alto y AT Alto. En las Figuras 2 y 3 se muestran las funciones de membresía selec cionadas para cada una de las variables lingüísticas de entrada y salida a emplear.

4.2.3. Base de reglas difusas

La base de reglas contiene un conjunto de sentencias condicionales que son base del proceso de toma de decisiones de evaluación de calidad de servicio y encaminamiento interdominio en el mecanismo de inferencia. Este conjunto de reglas es dependiente del diseñador y puede modificarse a fin de proveer un mejor desempeño, Figura 4.

4.2.4. Difuso

El mecanismo de inferencia difusa es un proceso de dos pasos en el cual las certezas debido a cada una de las reglas activas se evalúan. El primer paso en el proceso de inferencia difusa es la determinación de activación de las reglas que aplican a una situación dada. Así de tal forma se considera que una regla se activa si todos sus componentes tienen > 0 . El segundo paso en el proceso de inferencia difusa es determinar las conclusiones provistas por cada una de las reglas. Ya que cada una de las reglas tiene su propia conclusión, la salida del mecanismo de inferencia es una combinación de conclusiones de todas las reglas activas. Estos resultados ingresan al proceso de dedifusificación para convertirse en una respuesta simple en valor cuantitativo. Para los experimentos se decide limitar el número de variables difusas de entrada a:

  • IPTD
  • IPDV
  • IPLR

Existen un amplio número de algoritmos que pueden emplearse en el componente de de-difusificación, que varía en complejidad de almacenamiento y procesamiento. Uno de los métodos de de-difusificación más empleados por su reducción en costo computacional es el método del centroide, también conocido por el nombre de centro de gravedad. De tal forma, el proceso de de-difusificación produce una respuesta cuantitativa a fin de evaluar la calidad de servicio en el encaminamiento, el mecanismo y modelo de controlador difuso se muestra en la Figura 5.

5. Simulaciones y discusión de resultados

En esta sección se describen las simulaciones de la propuesta de evaluación de calidad de servicio mediante aplicación de técnicas de inteligencia computacional en un escenario interdominio, en primera instancia se determina el valor umbral de la función grado de preferencia para las clases definidas en [30]. Posteriormente, se muestran los escenarios de simulación seleccionados, se introduce el mecanismo de evaluación de calidad de servicio empleando el controlador difuso diseñado y a partir de estos datos se construyen políticas de encaminamiento, las cuales se implementan con base en mapas de encaminamiento, en la parte posterior de la sección se muestran los resultados y discusión de las simulaciones.

En la Figura 6 se muestran las superficies de la maquina de inferencia difusa para el método bisector y mom respectivamente. En las siguientes simulaciones se emplean los valores umbrales proporcionados por el método bisector en tanto se establece con nivel de exigencia en cumplimiento de los criterios de calidad de servicio en comparación con los métodos centroide y mom.

5.1.1. Determinación de umbral de la función grado de preferencia DoP

Con la finalidad de establecer los valores umbrales que toma la variable lingüística de salida grado de preferencia DoP en función de los valores que toman los requerimientos de calidad de servicio de entrada, se inicializan vectores de prueba que toman los valores propuestos para las diferentes clases de servicio propuestas por la UIT-T en la recomendación Y.1541 [30] tabla I, los correspondientes ensayos se realizan empleando herramientas de computacionales de lenguaje científico.

De tal forma se establece el rango de grados de preferencia de los caminos que pueden ser tomados por cada uno de los tráficos en relación con dicha normatividad internacional. Por razones de simplicidad en el número de reglas a evaluar se elige, como vector de prueba los valores umbrales limitados a las entradas difusas, IPTD, IPDV e IPLR, obteniéndose de tal forma los valores umbrales de la función grado de preferencia de la Figura 7, con el método de de-difusificación del centroide, bisector, mom: mean of maximum, lom: largest of maximum y som: smallest of maximum.

5.1.2. Simulaciones en modelos de red

En la Figura 8 se muestran los modelos de red empleados para la simulación de evaluación de la calidad de ser vicio en el encaminamiento; el primer modelo esta compuesto por cinco nodos interconectados en una topología en anillo, con interconexiones PPP-DS3. Las redes A y B actúan como sistemas autónomos en configuración stub, los sistemas autónomos 1100, 2200, 3300, 4400 y 5500 se establecen como sistemas autónomos de transito. Se emplean para el modelo de red interconexiones seriales PPP, con capacidades DS1 (2048 Kbps) y DS3 (44736 Kbps), como se muestra.

Con relación al encaminamiento BGP se requieren de un intercambio de información de caminos inicial, este se realiza dentro de los tres primeros minutos de tal forma, la gráfica muestra el tiempo de convergencia BGP, Figura 9. Se propone la evaluación de las métricas de calidad de servicio de tipo estática y proveer un mecanismo estable de aprovisionamiento de calidad de servicio en la capa de encaminamiento mediante construcción de políticas de encaminamiento con base en mapas, Tabla II. Las siguientes gráficas muestran el efecto de la introducción de las políticas de encaminamiento con base en los niveles umbrales decididos en el mecanismo de inferencia. En la figura 9 se muestra el tráfico promedio sobre los enlaces punto a punto entre el sistema autónomo AS1100 y los sistemas autónomos AS3300 y AS4400, se observa que dado el comportamiento de BGP todo el tráfico generado por el AS1100 correspondiente a los diferentes clases de servicio definidas en [29], [30] es enviado por medio del sistemas autónomo AS3300, debido a que el atributo de camino AS_PATH tiene menor número de sistemas autónomos que hacia el AS4400, evidenciándose el comportamiento vector-camino inherente de BGP, y su incapacidad de evaluación de la calidad de servicio.

En la Figura 10 se muestran los resultados de la aplicación de la política de encaminamiento con base en los valores umbrales determinados en el mecanismo de inferencia difusa. De tal manera, acorde a los parámetros de desempeño de los caminos en el escenario de red A listados en la Tabla III y la correspondiente política, el mejor camino para las clases de servicio 0 y 1 es el identificado como número 2. Así en la Figura 10 se muestra que el tráfico marcado con ToS correspondiente a clases 0 y 1 se envía a través del sistema autónomo 3300. Es de notar que se mejoran algunos de los parámetros de desempeño IP en comparación con el camino que tomaría los datos en el modelo de encaminamiento convencional proporcionado por BGP, sin embargo el mecanismo de inferencia no garantiza por si sólo el cumplimiento estricto de los niveles mínimos que identifican a cada clase, sino que más bien selecciona el camino que mejor cumpla en conjunto todas las condiciones, esto es, aprovisionamiento de calidad de servicio suave.

6. Conclusiones

Se observan diferencias en los resultados de los valores umbrales de la función de grado de presencia de camino en relación al método de de-difusificación a emplear, de tal modo se observa uniformidad en los valores de umbral para las clases de servicio 3 y 4, que corresponden con tráfico de tipo datos interactivos y de tipo video respectivamente.

En relación al resultado de los umbrales, proporcionados por cada uno de los diferentes métodos, es evidente que los umbrales proporcionados por el método lom y som no son adecuados en tanto el valor para la clase de servicio 0 están establecidos en el valor máximo y en un valor por debajo del valor medio. En cuanto al método mom, bisector y centroide, pueden emplearse para la determinación de los umbrales de la función grado de preferencia.

Las políticas de encaminamiento empleadas para la determinación de los caminos con base en los valores de grado de preferencia pueden configurarse por medio de mapas de encaminamiento.

Los mapas de encaminamiento tienen usos múltiples para la asociación y modificación de caminos en diferentes escenarios.

A fin de no afectar las características y principales criterios de diseño de BGP: estabilidad y escalabilidad, se propone la evaluación de las métricas de calidad de servicio de tipo estática y proveer un mecanismo estable de aprovisionamiento de calidad de servicio en la capa de encaminamiento mediante construcción de políticas de encaminamiento con base en mapas. En la propuesta de investigación se mejoran los parámetros de desempeño IP en comparación con el camino que tomaría los datos en el modelo de encaminamiento convencional proporcionado por BGP, sin embargo el mecanismo de inferencia no garantiza por si sólo el cumplimiento estricto de los niveles mínimos que identifican a cada clase, sino que más bien selecciona el camino que mejor cumpla en conjunto todas las condiciones, esto es, aprovisionamiento de calidad de servicio suave.

En el caso específico de esta investigación se limita el número de entradas al controlador difuso a tres: IPTD, IPDV e IPLR, sin embargo queda abierta a investigaciones futuras el estudio y análisis de escenarios de encaminamiento con mayor número de restricciones.

Referencias bibliográficas

[1] F. Kuipers. "Quality of Service Routing in the Internet:Theory, Complexity and Algorithms". PhD thesis, Delft University, 2004.

[2] F. Kuipers; Piet F. Van Mieghem, "Conditions that Impact the Complexity of QoS Routing", IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.717-730, 2005.

[3] R. Braden; D. Clark; S. Shenker, "Integrated services in the Internet Architecture: an Overview". IETF Internet Engineering Task Force, RFC 1633, 1994. http://www.ietf.org/rfc/rfc1633.txt

[4] S. Blake; D. Black; M. Carlson; E. Davies; Z. Wang; W. Weiss, "An Architecture for Differentiated Services ", IETF Internet Engineering Task Force, RFC 2475, 1998. http://www.ietf.org/rfc/rfc2475.txt

[5] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus. "Requirements for Traffic Engineering Over MPLS". IETF Internet Engineering Task Force, RFC 2702,1999. http://www.ietf.org/rfc/rfc2702.txt

[6] A. Alkahtani; M.E. Woodward; K. Al-Begain, "An Overview of Quality of Service and QoS Routing in Communication Networks", Department of Computing at the University of Brandford, UK, PGNet, ISBN: 1-9025-6009-4, 2003.

[7] Ilmari Juva. "Analysis of Quality of Service Routing Approaches and Algorithms", Master Thesis, Department of Engineering Physics and Mathematics, Helsinki University of Technology, 2003.

[8] Andrzej Beben, "EQ-BGP: An Efficient Inter-Domain QoS Routing Protocol", 20th International Conference on Advanced Information Networking and Applications, Volume 2, pp. 560-564, 2006.

[9] Tielei Zhang, Yong Cui, Youjian Zhao, Lizheng Fu, Turgay Korkmaz, "Scalable BGP QoS Extension with Multiple Metrics," ICNS, p. 80, International conference on Networking and Services (ICNS'06), 2006.

[10] A. Sahoo. "An OSPF based load sensitive QoS routing Algorithm using Alternate Paths", Proceedings of International Conference on Computer Communications and Networks, 2002.

[11] S. Norden; J. Turner, "New Inter-domain QoS Routing Algorithms", Technical Report WUCS-02-03, Department of Computer Science, Washington University, 2002.

[12] Li Xiao; King-Shan Lui; Jun Wang; K. Nahrstedt, "QoS extension to BGP". Proceedings 10th IEEE International Conference on Networks Protocols, 2002.

[13] Venkatesh Sarangan; Donna Ghosh; Raj Ghosh. "Capacity-Aware State Aggregation for Inter-Domain QoS Routing", IEEE Transactions on Multimedia, vol. 1, No. 4, 2006.

[14] G. Cristallo and C. Jacquenet, "Providing Quality of Service Indication by the BGP-4 Protocol: the QOS_NLRI attribute", IETF draft-jacquenet-qos-nlri-05.txt, 2003.

[15] K.H. Ho, N. Wang, P. Trimintzios and G. Pavlou, "Traffic Engineering for Inter-domain Quality of Service," Proc. London Communications Symposium (LCS), London, UK, September 2003.

[16] Uhlig Steve, "A Multiple-objectives Evolutionary Perspective to Interdomain Traffic Engineering", International Journal of Computational Intelligence and Applications, 5, 2, 2005, p. 215-230.

[17] X. Masip-Bruin, M. Yannuzzi, J. Domingo-Pascual, A. Fonte, M. Curado, E. Monteiro, F. Kuipers, P. Van Mieghem, S. Avallone, G. Ventre, P. Aranda-Gutierrez, M. Hollick, R. Steinmetz, L. Iannone, and K. Salamatian. "Research Challenges in QoS Routing". Computer Communications, 29(5):563­581, March 2006.

[18] M. Yannuzzi, A. Fonte, X. Masip, E. Monteiro, S. Sánchez, M. Curado, J. Domingo, "A proposal for inter-domain QoS Routing based on distributed overlay entities and QBGP", Proceedings of the First International Workshop on QoS Routing (WQoSR), LNCS 3266, Barcelona, 2004.

[19] L. Subramanian, I. Stoica, R. H. Katz, H. Balakrishnan, "OverQoS: An Overlay Based Architecture for Enhancing Internet QoS," USENIX/ACM Symposium on Networked System Design and Implementation, San Francisco, CA,2004.

[20] ITU-T Recommendation E.800, "Terms and Definitions Related to Quality of Service and Network Performance Including Dependability".

[21] E. Crawley, R. Nair, B. Rajagopalan, H. Sandick, "A Framework for QoS-based Routing in the Internet", IETF Internet Engineering Task Force, RFC 2386, 1998. http://www.ietf.org/rfc/rfc2386.txt

[22] G. Cristallo and C. Jacquenet, "An Approach to Interdomain Traffic Engineering", in Proceedings of XVIII World Telecommunications Congress (WTC2002), Paris, France, September 2002.

[23] Steve Uhlig, Bruno Quoitin, "Tweak-it: BGP-based interdomain traffic engineering for transit ASes", Next generation Internet networks traffic engineering 2005 (NGI2005), Roma, Italy, April 18-20, 2005, IEEE, 2005, p. 75-82.

[24] Bruno Quoitin, Steve Uhlig, Cristel Pelsser, Louis Swinnen,Olivier Bonaventure, "Interdomain traffic engineering with BGP", IEEE Communications Magazine, 41, 5, 2003, p. 1-9.

[25] Jun-Hong Cui; Swapna S. Gokhale; Li Lao, "Distributed QoS Routing for Backbone Overlay Networks", In Proceedings of IFIP Networking, Coimbra, Portugal, 2006.

[26] R. Guerin, A. Orda ,"QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms", IEEE INFOCOM'97, Kobe, Japan

[27] A. Vasilakos; C. Ricudis; K. Anagnostakis; W. Pedryca; A. Pitsillides. "Evolutionary-fuzzy prediction for strategic QoS routing in broadband networks". IEEE World Congress on Computational Intelligence, IEEE International Conference on Fuzzy Systems Volume 2, Issue, 4-9 May 1998 Page(s):1488 - 1493 vol.2

[28] Ahmed Shawky Moussa. "The Implementation of Intelligent QoS Networking by the Development and Utilization of Novel Cross-Disciplinary Soft Computing Theories and Techniques", Ph.D Dissertation at the Florida State University, 2003.

[29] ITU-T Recommendation Y.1540, "IP packet transfer and availability performance parameters".

[30] ITU-T Recommendation Y.1541, "Network Performance Objectives for IP-based Services".

Héctor Cristyan Manta Caro

Ingeniero electrónico, Universidad Distrital Francisco José de Caldas. Magíster en Ciencias de la Información y las Comunicaciones énfasis en Teleinformática, Universidad Distrital. Integrante del Grupo de Investigación en Internet Inteligente, y del Grupo de Investigación en Resonancia Magnética RM-UD. sus áreas de interés en investigación se relacionan con encaminamiento avanzado, aprovisionamiento de calidad de servicio en redes de próxima generación y procesamiento digital de señales e imágenes. Se desempeña como instructor certificado Cisco, CCSI, CCNP, CCNA. hcmantac@udistrital.edu.co

Lilia Edith Aparicio

Especialista en Gerencia de Proyectos de Educativos Universidad Distrital Francisco José de Caldas, Magíster en Teleinformática Universidad Distrital Francisco José de Caldas, Doctora en Ciencias Técnicas de la Universidad Central de las Villas (Cuba), Actualmente se desempeña como Decana de la Facultad de Ingeniería de la Universidad Distrital Francisco José de Calda, docente tiempo completo y Directora de la Maestría en Teleinformática, pertenece al grupo de investigación GITEM.

Octavio José Salcedo Parra

Ingeniero de sistemas de la Universidad Autónoma de Colombia en 1994, Magíster en Teleinformática de la Universidad Distrital Francisco José de Caldas. Magíster en Economía de la Universidad de los Andes.Actualmente se encuentra adelantando estudios de Doctorado en Informática con énfasis en Sociedad del Conocimiento en la Universidad Pontificia de Salamanca. Director y fundador del Grupo de Investigación en Internet Inteligente. Es director de la revista Ingeniería y docente de la Universidad Distrital. ojsalcedop@unal.edu.co


Creation date:

Most read articles by the same author(s)

1 2 3 > >> 
Loading...