Optimización y planificación de redes ópticas transparentes WDM

Abstract

[SPA] Esta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientos Esta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientosEsta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientosEsta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientosEsta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientosEsta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientosEsta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientosEsta tesis contribuye en el campo de la optimización y planificación de redes ópticas transparentes WDM. Las redes ópticas transparentes basadas en multiplexación por división de onda (wavelength division multiplexing, WDM) son las solución tecnológica de las redes troncales de comunicaciones de alta velocidad. En redes transparentes, el tráfico es cursado por medio de conexiones todo-ópticas, llamadas lightpaths. Un lightpath se origina en un transmisor óptico y termina en un receptor óptico, ocupando un único canal de longitud de onda en cada enlace atravesado. Al ser procesado electrónicamente en los nodos intermedios el tráfico cargado por el lighpath, se pueden conseguir ahorros con respecto al uso de equipamiento de conmutación electrónica. El conjunto concreto de lighpaths establecidos sobre la topología física constituye la denominada topología virtual. La planificación de red en estas redes implica resolver un problema multicapa de optimización, al que nos referimos como Diseño de Topología Virtuales (Virtual Topology Design, VTD): en la capa superior, las demandas de tráfico electrónico son encaminadas a través de la topología virtual, mientras que, en la capa inferior, cada lightpath en la topología virtual lo es sobre la topología de red física, al tiempo que se le asigna a una longitud de onda. El problema de la capa inferior es generalmente denominado Problema de Enrutamiento y Asignación de Longitud de Onda (Routing and Wavelength Assignment, RWA). El problema completo VTD y el problema RWA pueden ser modelados exactamente como programas matemáticos, en concreto, como programas de optimización lineal entera mixta (Mixed Integer Linear Programming, MILP) o programas de optimización lineal entera (Integer Linear Programming, ILP), respectivamente. En estos modelos matemáticos, algún tipo de coste de la red es minimizado sujeto a restricciones matemáticas que representan la configuración de red. Un diseño factible de red corresponde a una solución que satisfaga todas estas restricciones, es decir, una solución contenida en el interior del conjunto definido por estas restricciones. Si la solución es también óptima (p.ej. mínimo coste), el diseño de la red encontrado es el "más barato" posible. Por desgracia, se ha demostrado que los problemas VTD y RWA son de tipo NP-hard, es decir, todavía no se ha encontrado un algoritmo de optimización matemática que sea capaz de resolver el problema en tiempo polinomial. Como consecuencia, problemas de tamaño moderado ya resultan computacionalmente intratables, motivando la necesidad de desarrollar procedimientos heurísticos subóptimos para proporcionar soluciones aproximadas a las óptimas del problema de planificación. Dado que, para muchos tamaños de red, la solución del modelo exacto no es posible, el planificador de red debe calcular cotas inferiores a los costes mínimos a partir de fórmulas analíticas para estimar la calidad de las soluciones heurísticas subóptimas. Una vez evaluada la "bondad" de los algoritmos heurísticos desarrollados, estos métodos, junto con formulaciones exactas ILP o MILP, o las mencionadas cotas analíticas pueden ser aplicados a la exploración de compensaciones en los costes de red entre configuraciones alternativas. En la presente tesis, tres problemas en redes ópticas transparentes son investigados mediante la metodología previamente mencionada: (a) Planificación Estática Multifibra (Static Multifiber Planning), (b) Planificación Estática bajo Degradaciones de Capa Física (Static Physical Layer Impairment Aware, PLIA, Planning), y (c) Planificación Multihora (Multihour Planning). Algunas conclusiones interesantes se extraen acerca de las mejores configuraciones de red, en términos de costes, y sobre las ventajas y desventajas entre ellas. En los párrafos siguientes se resume el contenido de los capítulos de tesis.

[ENG] The present thesis contributes in the field of the optimization and planning of WDM transparent optical networks. Transparent optical networks based on wavelength division multiplexing (WDM) are the enabling technology for high-speed backbone networks. In transparent networks, traffic is carried over all-optical connections, called lightpaths. A lightpath originates at an optical transmitter and terminates at an optical receiver, occupying a single wavelength channel in each traversed link. Since the traffic carried over a lightpath is not processed electronically at intermediate nodes, savings with respect to electronic switching equipment can be achieved. The particular set of lightpaths established over the physical topology constitutes the so-called virtual topology. The network planning in these networks implies solving a multilayer optimization problem named Virtual Topology Design (VTD): in the upper layer, electronic traffic demands are routed over the virtual topology; whereas, in the lower layer, each lightpath in the virtual topology is routed over the physical network topology and assigned to a wavelength. The lower layer problem is generally called Routing and Wavelength Assignment (RWA) problem. The overall VTD and the RWA problem can be modeled exactly as Mixed Integer Linear Programming (MILP) or Integer Linear Programming (ILP) formulations, respectively. In these mathematic models, some kind of network cost is minimized subject to the constraints representing the network configuration. A feasible network design corresponds to a solution meeting all the constraints, that is, a solution contained inside the feasible set defined by these constraints. If the solution is also optimal (e.g. minimal cost), the network design found is the “cheapest” possible. Unfortunately, VTD and RWA problems have been proved as NP-Hard, that is, a mathematical optimization algorithm able to solve the problem in a polynomial time has still not been found. As a consequence, moderate-sized problems are computationally intractable, motivating the need of developing suboptimal heuristic procedure to provide approximate solutions to the optimal ones of the planning problem. Since, for many network sizes, solving the exact model is not possible, the network planner must devise lower bounds on the minimal costs from analytical formulae to estimate the quality of the suboptimal heuristic solutions. Once assessed the “goodness” of the developed heuristic algorithms, these methods along with exact ILP or MILP formulations or the referred analytical bounds can be applied to explore tradeoffs on network costs among different network configurations.