Optimización y planificación de redes ópticas transparentes WDM
[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.
Redes ópticas, Ondas, Multifibra, Wavelength Division Multiplexing(WDM), Lightpaths, Programación lineal
Networked Digital Library of Theses and Dissertations