Título: Algoritmos basados en programación lineal entera para el Survivable Routing and Spectrum Assignment Problem

Director: Dr. Javier Marenco

Jurados: Dra. Isabel Méndez Díaz y Dra. Paula Zabala

Resumen:

Las redes de fibra óptica utilizan la luz, transportada por un cable, como un medio de comunicación entre dos nodos de la red. En respuesta al crecimiento sostenido del tráfico en este tipo de redes, en los últimos años se ha propuesto una nueva generación de redes de fibra óptica, llamada flexgrid elastic optical networks (EONs) con el objetivo de mejorar la eficiencia en el uso del espectro electromagnético y aumentar así la capacidad de las redes.

En las EONs, el espectro de frecuencias de una fibra óptica se divide en slots de frecuencias relativamente pequeños, cada uno con un ancho de banda fijo. Se puede utilizar cualquier secuencia de slots consecutivos para formar un canal, que a su vez puede ser ruteado por la red para crear lo que se conoce como un lightpath.

Dada la estructura de una red y un conjunto de demandas, el routing and spectrum assignment (RSA) problem consiste en establecer los lightpaths para un conjunto de demandas de tráfico, cada una de las cuales está expresada en términos de un nodo de origen, un nodo de destino y una cantidad de slots. Dado que cada lightpath está determinado por una ruta y un canal, el RSA consiste en encontrar una ruta y asignar un intervalo de slots para cada demanda.

El survivable RSA with path protection es una variante de RSA, que corresponde a solicitar dos lightpaths para cada demanda: un camino titular y un camino de backup, y ambos deben respetar las restricciones de RSA. Este problema es NP-hard y ha recibido atención por parte de la comunidad especializada en los últimos años.

En este trabajo se proponen distintos modelos de programación lineal entera para este problema, y se estudia su performance en la práctica sobre topologías reales. Se presentan además heurísticas para optimizar los modelos, buscando acelerar la obtención de soluciones factibles iniciales. Notando que el problema se puede descomponer en una fase de ruteo y una fase de asignación, se estudian esquemas de descomposición basados en la descomposición combinatoria de Benders para obtener soluciones a estos modelos mucho más rápidamente.