Tesis "Evaluación de Metaheurísticas para el Problema de Incrustación de Nuevas Redes Virtuales en Redes Operativas"
Alumno: Christian Aguilar Fuster
Asesor: Dr. Javier Rubio Loyola
Sinodales: Dr. Alejandro Galaviz Mosqueda, Dr. Eduardo Rodríguez Tello
Resumen:
La tecnología de virtualización de redes (NV por sus siglas en inglés Network Virtualization) permite que múltiples redes coexistan en una misma red física, obteniendo como resultado un mayor aprovechamiento de los recursos de la infraestructura física. La virtualización de redes se considera de vital importancia para el Internet del futuro debido a que hace posible el despliegue de nuevos modelos de negocios en los que se ofrecen servicios independientes de una infraestructura subyacente. El mapeo de redes virtuales (VN por sus siglas en inglés Virtual Network) en una red física tiene como reto principal optimizar la manera en que serán asignados los recursos (CPU y ancho de banda) de una infraestructura física, de tal forma que cumplan con los requerimientos demandados por las VNs y a su vez, incruste la mayor cantidad de éstas. A este problema se le conoce como “Incrustación de redes virtuales” (VNE por sus siglas en inglés Virtual Network Embedding) y se encuentra catalogado como un problema NP-Completo cuando se toman en consideración las restricciones de nodos y enlaces.
Este trabajo de tesis está enfocado en evaluar y analizar el comportamiento de cinco metaheurísticas para el problema de incrustación de nuevas redes virtuales en redes operativas (VNEON por sus siglas en inglés Virtual Network Embedding in Operational Networks). Se evaluaron y analizaron cuantitativamente las metaheurísticas: optimización de cúmulo de partículas (PSO por sus siglas en inglés Particle Swarm Optimization), optimización por colonia de hormigas (ACO por sus siglas en inglés Ant Colony Optimization), algoritmo genético (GA por sus siglas en inglés Genetic Algorithm), búsqueda armónica (HS por sus siglas en inglés Harmony Search) y el algoritmo de luciérnagas (FA por sus siglas en inglés Firefly Algorithm) en la solución del problema VNEON. Además de la evaluación, se propone el uso del algoritmo de ordenación estocástica (SR por sus siglas en inglés Stochastic Ranking) para el manejo de la restricciones en cada una de las metaheurísticas. Este trabajo de tesis avanza el estado del arte al determinar qué metaheurística tiene mejor desempeño dada una métrica de evaluación, donde las métricas evaluadas en el problema VNEON son: costo, ingreso, tasa ingreso/costo, tasa de aceptación y tiempo de ejecución. La evaluación propuesta se llevó a cabo mediante la implementación de un banco de pruebas que permite la realización de simulaciones bajo diferentes escenarios de validación. Los escenarios de validación sobrepasan en dimensión a todos los trabajos encontrados en la literatura para tal fin y por ende, los hallazgos realizados como producto del análisis de los resultados de este trabajo de investigación también avanzan el estado del arte en el problema de incrustación de redes virtuales en redes operativas.