Thesis:

Optimization methods applied to network planning problems

This thesis focuses on the feasibility of solving network planning problems that include non-linear aspects by means of integer linear programming (ILP). In the specialized literature, most network planning problems solved by applying ILP models do not include non-linear expressions in a direct way. However, non-linear expressions are very common when including constraints related to key network performance metrics as the blocking rate or the availability. To circumvent the difficulties of solving such problems, researchers have usually resorted to not including non-linear aspects or using meta-heuristics and heuristics, which do not guarantee an optimal solution. Such sub-optimal solutions lead to higher budget requirements or under performing networks and thus, as long as the optimal solution can be found in acceptable running times, it is preferred to other alternatives. The use of logarithm functions (to linearize some expressions) and mixed zero-one models have also be used, but not for the problems addressed in this thesis. In this thesis 3 network planning problems including non-linear expressions were solved by means of ILP. The first problem was the dimensioning of network nodes and links in a dynamic wavelength division multiplexed (WDM) network equipped with reconfigurable optical add-drop multiplexers (ROADM) as switching nodes. The network had to be dimensioned in such a way that the maximum blocking probability experienced by point-to-point connections would not exceed a maximum threshold. To date, no ILP works have addressed the problem of dimensioning for a specific blocking value. The second problem consisted on dimensioning and configuring the backup resources of a static WDM network using shared-path protection as survivability mechanism. The network had to be dimensioned guaranteeing that the availability of every connection would not decrease under a given target value. A new way of dealing with the non-linear expression for the availability target, the inclusion of an availability based priority scheme for the access to the shared resources and the equations to consider the wavelength continuity constraint are the main contributions of this work. Finally, the dimensioning of working and backup wavelengths of the dynamic WDM network operating as the physical substrate of a network virtualization system was solved. In this system, virtual networks must be guaranteed a maximum blocking and minimum availability. No previous work has dealt with these constraints. The strategies used in this thesis to solve non-linear network planning problems could be used as a starting point to solve problems in different network contexts that include important non-linear aspects.

Esta tesis se centra en la viabilidad de resolver problemas de planificación de redes que incluyen aspectos no lineales mediante programación lineal entera (ILP). En la literatura especializada, la mayoría de los problemas de planificación de redes resueltos mediante modelos ILP no incluyen expresiones no lineales de forma directa. Sin embargo, las expresiones no lineales son muy comunes cuando se incluyen restricciones relacionadas con métricas clave de rendimiento de la red, como la tasa de bloqueo o la disponibilidad. Para sortear las dificultades de resolución de estos problemas, los investigadores suelen optar por no incluir aspectos no lineales o utilizar metaheurísticas y heurísticas, que no garantizan una solución óptima. Estas soluciones subóptimas conllevan mayores requisitos presupuestarios o redes de bajo rendimiento y, por lo tanto, siempre que se pueda encontrar la solución óptima en tiempos de ejecución aceptables, se prefiere esta alternativa a otras. También se han empleado funciones logarítmicas (para linealizar algunas expresiones) y modelos mixtos cero-uno, pero no para los problemas abordados en esta tesis. En esta tesis, se resolvieron tres problemas de planificación de redes que incluían expresiones no lineales mediante ILP. El primer problema fue el dimensionamiento de los nodos y enlaces de red en una red multiplexada por división de longitud de onda (WDM) dinámica, equipada con multiplexores ópticos reconfigurables de inserción y extracción (ROADM) como nodos de conmutación. La red debía dimensionarse de forma que la probabilidad máxima de bloqueo experimentada por las conexiones punto a punto no superara un umbral máximo. Hasta la fecha, ningún trabajo de ILP ha abordado el problema del dimensionamiento para un valor de bloqueo específico. El segundo problema consistió en dimensionar y configurar los recursos de respaldo de una red WDM estática utilizando la protección de ruta compartida como mecanismo de supervivencia. La red debía dimensionarse garantizando que la disponibilidad de cada conexión no disminuyera por debajo de un valor objetivo determinado. Las principales contribuciones de este trabajo son una nueva forma de abordar la expresión no lineal del objetivo de disponibilidad, la inclusión de un esquema de prioridad basado en la disponibilidad para el acceso a los recursos compartidos y las ecuaciones para considerar la restricción de continuidad de la longitud de onda. Finalmente, se resolvió el dimensionamiento de las longitudes de onda de trabajo y de respaldo de la red WDM dinámica que opera como sustrato físico de un sistema de virtualización de red. En este sistema, las redes virtuales deben tener garantizado un bloqueo máximo y una disponibilidad mínima. Ningún trabajo previo ha abordado estas restricciones. Las estrategias empleadas en esta tesis para resolver problemas de planificación de redes no lineales podrían servir como punto de partida para resolver problemas en diferentes contextos de red que incluyan importantes aspectos no lineales.