Enrutamiento multicast utilizando optimización multiobjetivo

Enrutamiento Multicast Utilizando Optimización Multiobjetivo
Jorge Crichigno+*, Francisco Talavera+, Joel Prieto, Benjamín Barán+* Ciencias y Tecnología - Universidad Católica Nuestra Señora de la Asunción+
Centro Nacional de Computación - Universidad Nacional de Asunción*
jcrichigno@cnc.una.py, ftalavera@yahoo.com.ar, jprieto@telesurf.com.py, bbaran@cnc.una.py

Resumen
Este trabajopresenta un nuevo algoritmo multi-objetivo, inspirado en un trabajo mono-objetivo anterior, proponiendo la utilización de un algoritmo basado en el SPEA. El algoritmo propuesto optimiza de manera simultánea el costo del árbol, el retardo promedio y el retardo máximo de extremo a extremo. De este modo, un conjunto de soluciones Pareto óptimas es calculado en una sola ejecución del algoritmo sin considerardecisiones a priori. Resultados experimentales fueron comparados con los conseguidos por otro algoritmo multi-objetivo propuesto anteriormente por algunos autores de este trabajo, mostrándose que para problemas pequeños se llega a las soluciones óptimas en un tiempo menor y para problemas más grandes se puede obtener una mayor cantidad de soluciones con un menor tiempo de procesamiento. Además sepresentan simulaciones para el problema dinámico de enrutamiento multicast, donde las solicitudes de tráfico arriban una después de otra. Se compara el rendimiento con el algoritmo SK, el cual encara el problema de enrutamiento multicast monoobjetivo. Palabras clave: Redes, Algoritmo Evolutivo, Multicast, Multi-objetivo, Pareto.

1

Introducción

Multicast consiste en la transmisiónsimultánea de datos desde un nodo fuente a un subconjunto de nodos destinos en una red de computadoras [1]. Recientemente, se ha incrementado el interés en los algoritmos de enrutamiento multicast debido a las nuevas aplicaciones punto a multipunto en redes de datos, como transmisiones de radio y TV, video bajo demanda, teleconferencias y aprendizaje a distancia. Dichas aplicaciones generalmente requierende algunos parámetros de calidad de servicio tales como retardo máximo de extremo a extremo y recursos mínimos de ancho de banda. Cuando el problema de enrutamiento dinámico considera varias solicitudes de tráfico de distintos nodos, además de los parámetros de calidad de servicio, también se debe tener en cuenta el balanceo de carga y el uso adecuado de los recursos de la red. El enfoquetradicional utilizado para el balanceo de la carga es la minimización de la utilización del enlace más sobrecargado, o minimización de la utilización máxima de los enlaces de la red (α) [2]. Este trabajo propone un algoritmo de enrutamiento multicast multiobjetivo, basado en un Algoritmo Evolutivo de Optimización Multiobjetivo (MOEA) con una población externa de soluciones Pareto óptimas, llamadoStrength Pareto Evolutionary Algorithm (SPEA) [3]. Dicho algoritmo halla un árbol multicast optimizando varias funciones objetivo simultáneamente. El presente artículo está organizado de la siguiente manera: en la Sección 2 se describen brevemente los trabajos relacionados. En la Sección 3 se da la definición general de un problema de optimización multiobjetivo. La formulación del problema y lasfunciones objetivo son dadas en la Sección 4. El algoritmo propuesto es explicado en la Sección 5. Los resultados experimentales son mostrados en la Sección 6. Por último, las conclusiones y los trabajos futuros son presentados en la Sección 7.

2

Trabajos Relacionados

Kompella et al. [5] publican un trabajo interesante sobre el problema de enrutamiento multicast sujeto a retardo máximo de extremoa extremo proponiendo un algoritmo basado en

programación dinámica (algoritmo KPP). Este algoritmo optimiza el costo del árbol multicast y restringe el retardo máximo a un valor dado a priori. Para el mismo problema planteado por Kompella et al., recientemente han sido propuestos algoritmos evolutivos, una técnica global de búsqueda que emula la evolución natural [6]. Ravikumar et al. [1]...