Estudio inicial de un politopo para el problema de ruteo y asignación de espectro (RSA)

BIANCHETTI, MARCELO

Conferencia; 47 JAIIO - Simposio Argentino de Investigación Operativa; 2018

La soluci ́on m ́as prometedora para la creciente demanda de tr ́afico en redes de comunicaciones consiste en la aplicacio ́n de t ́ecnicas de uso flexible de cableado de fibra ́optica, en particular la tecnolog ́ıa de grilla flexible (flexgrid) especificada en el estandar ITU-T G.694.1. En esta especificaci ́on, el espectro de frecuencias de un enlace de fibra ́optica se divide en slots pequen ̃os, y cualquier secuencia de slots consecutivos se puede utilizar como un u ́nico canal. Un canal puede ser ruteado a trav ́es de la red de fibra ́optica, formando as ́ı un lightpath.En este tipo de redes, el problema de establecer lightpaths que satisfagan la demanda se denomina Routing and Spectrum Allocation Problem (RSA), y ha recibido mucho inter ́es en los u ́ltimos an ̃os. Formalmente, dado un grafo G = (V,E) que representa la red de fibra ́optica, un conjunto de demandas D = {(si, ti, vi)}ki=1 -de modo tal que cada demanda i ∈ {1, . . . , k} tieneunorigensi ∈V,undestinoti ∈V yunvolumenvi ∈Z+-yunacantidads∈Z+ de slots disponibles, el RSA consiste en asignar un lightpath a cada demanda, de modo tal que los lightpaths no se superpongan. En otras palabras, a cada demanda i ∈ {1, . . . , k} se le debe asignar un camino entre si y ti en G y un intervalo de vi slots consecutivos en [0,s], de modo tal que si dos demandas utilizan una misma arista para sus caminos, entonces los intervalos de slots que recibieron deben ser disjuntos.En trabajos anteriores se ha demostrado que el problema de decisi ́on asociado es NP-dif ́ıcil y se han propuesto varios modelos de programaci ́on lineal entera que lo resuelven por optimalidad. Con dichos modelos instancias grandes aun son intratables, por lo que en el presente trabajo se comienza un estudio poliedral de una familia particular de los mismos con el objetivo final de llegar a resolver en forma exacta instancias reales.