Título: Modelos de programación lineal entera para el problema de enrutamiento y asignación de espectro manycast
Director: Javier Marenco
Jurados: Gabriela Di Piazza y Federico Pousa

Resumen:
La creciente demanda de servicios de alta velocidad en redes de comunicaciones ha puesto en el centro de atención la optimización del uso de las redes de fibra óptica. Una tecnología prometedora para abordar este desafío es la arquitectura “flexgrid”, que divide el ancho de banda de la fibra óptica en slots, los slots consecutivos se pueden unir en lo que se llama “canal” y los canales permiten crear una conexión entre nodos de una red. Si bien flexgrid posibilita una asignación mucho más eficiente de la red, plantea un problema de optimización conocido como “routing and spectrum allocation” (RSA). En este trabajo se abordará una generalización de este problema llamada “manycast-RSA (MRSA)”, que surge en escenarios en los que el envío de información es de un origen a muchos destinos.

Ambos problemas suelen ser modelados sobre grafos dirigidos. Dados un digrafo, la cantidad de slots en la fibra, y un conjunto de demandas (donde cada demanda requiere una cantidad de slots contiguos, tiene un nodo origen y un conjunto de nodos de destino), se quiere satisfacer todas las demandas sin ocupar el mismo slot por dos demandas y sin exceder la capacidad de la red. Mientras que en RSA se busca un camino para cada par origen-destino, en MRSA se busca una arborescencia entre el origen y los destinos.

RSA fue demostrado NP-hard (Christodoulopoulos et al. 2011) y, si bien se han propuesto diversas soluciones, los modelos basados en programación entera demostraron ser particularmente prometedores. El objetivo de este trabajo es encontrar soluciones exactas para el problema MRSA, tomando modelos planteados para RSA. A partir de ellos, se propone una serie de formulaciones de programación lineal entera para resolver MRSA y se comparan sobre instancias generadas a partir de diferentes topologías de la literatura.