Optimization of optical interconnection and comunnication networks

Resumo

Esta tesis ha sido desarrollada en el área de investigación de ¿optimización de redes ópticas de interconexión y comunicación¿. Esta tesis se estructura en tres líneas principales: (i) la planificación multihora de redes con especial atención a las redes ópticas WDM, (ii) la planificación bajo degradaciones de la capa física de redes ópticas WDM, y (iii) el diseño de interconexión óptica en routers de altas prestaciones. En el capítulo 1 se presenta una introducción sobre las redes ópticas WDM como la alternativa tecnológica más atractiva para redes de comunicación de alta capacidad. Además, se introducen los principales escenarios de planificación de redes que son estudiados en esta tesis. Por otro lado, también se presenta el diseño de redes de interconexión óptica como una elección viable para reemplazar la estructura electrónica de conmutación en routers de altas prestaciones. Por último, se incluye un resumen de los objetivos y las contribuciones de esta tesis. El capítulo 2 se centra en la planificación de redes de comunicación cuando el tráfico varía a lo largo del tiempo siguiendo un patrón multihora. En nuestro caso, esto quiere decir que el tráfico ofrecido está compuesto por una secuencia de matrices de tráfico que representan el tráfico en las diferentes horas del día o bien la semana. El objetivo de la planificación es tomar ventaja del hecho de que los instantes con picos de tráfico en diferentes puntos de la red no coinciden en el tiempo, con lo que es posible reutilizar los recursos desocupados para reducir el coste de la red. Dos problemas multihora son estudiados según el encaminamiento de los flujos: problemas con encaminamiento de flujos estático (Multihour Static Routing (MHSR)) y dinámico (Multihour Dynamic Routing (MHDR)), que son adecuados para una amplia variedad de problemas de planificación de redes. Los parámetros de entrada de estos problemas son una serie de matrices de tráfico y un conjunto de enlaces formando una red, y el objetivo será calcular las capacidades necesarias de los enlaces y el patrón de encaminamiento que permite satisfacer por completo la demanda de tráfico en todos los instantes. En ambos problemas, supondremos que las capacidades de los enlaces son fijas, mientras que el encaminamiento del tráfico es obtenido de forma diferente en cada caso. En el caso del problema MHSR, una restricción extra debe ser considerada: el enrutamiento de los flujos es estático, es decir, éste permanece constante a lo largo del tiempo. Sin embargo, esta restricción no es incluida en el caso dinámico (MHDR). Por tanto, si la red no permite cambiar el encaminamiento de los flujos de tráfico a lo largo del tiempo, debemos considerar el problema MHSR. Por el contrario, cuando se trata de una red ágil capaz de adaptarse a las variaciones del tráfico, debemos asumir el caso MHDR. En las primeras secciones de este capítulo, presentamos la base de la llamada relación de dominación del tráfico (traffic domination). Primero, presentamos un conjunto de definiciones y proposiciones derivadas de dicha relación entre dos matrices de tráfico individuales. A continuación, estas relaciones son extendidas a la relación entre dos conjuntos de matrices. Después de esta introducción teórica, exploramos la aplicación de la relación de dominación del tráfico para reducir la complejidad de los problemas de planificación multihora. Según el tipo de problema, consideramos dos subtipos de dominación entre matrices de tráfico: la llamada relación de dominación (sin más adjetivos) es empleada para el problema MHDR, mientras que la relación de dominación total se aplica al problema MHSR. Estas relaciones se emplean para calcular, dada una demanda de tráfico compuesta potencialmente por cientos o miles de matrices, una serie más simple con un tamaño arbitrario que o bien (i) domina o bien (ii) es dominada por la serie original. La serie de tráfico dominante puede ser utilizada como un límite superior de la demanda de tráfico (Upper Bound Traffic Demand (UBTD)): el UBTD es una serie de matrices de tráfico que domina a la original, por lo que la red puede ser diseñada usando el UBTD y la solución sería válida también para el tráfico original. Además, las demandas multihora dominadas pueden ser usadas como límites inferiores (Lower Bound Traffic Demand (LBTD)) del coste de la red. Si calculamos diseños óptimos usando como demanda el LBTD, estos nos darán límites inferiores del coste de la red cuando ésta soporta la demanda original. Por último, obtenemos la llamada demanda de tráfico multihora en exceso (Excess Multihour Traffic Demand (ETD)) que nos permite obtener un margen acerca de cuánto se aleja del óptimo el diseño de la red cuando empleamos el UBTD en vez de la serie original. Las últimas secciones del capítulo 2 presentan el trabajo llevado a cabo sobre la planificación multihora cuando consideramos redes ópticas WDM transparentes. Este tipo de problemas al que nos referimos como MH-VTD (Multihour Virtual Topology Design) obtienen la topología virtual y el encaminamiento del tráfico en una red óptica alimentada por tráfico multihora. El principal objetivo de estos problemas es minimizar el coste de la red medido como el número de enlaces virtuales (lightpaths) establecidos en la red, es decir, el número de transmisores y receptores necesarios en el diseño. Esta función objetivo se emplea para medir el coste de la red en la amplia mayoría de estudios de planificación publicados. El problema MH-VTD presenta diferentes variantes. En esta tesis estudiamos el problema NR-VTD (Non-reconfigurable Virtual Topology) en el que la topología virtual no se puede cambiar de un instante de tiempo a otro. Asumimos que la capa óptica no es ágil y, por tanto, el conjunto de lightpaths establecidos permanece invariable en el tiempo. Si nos fijamos ahora en el enrutamiento del tráfico tenemos cuatro variantes del problema: (i) enrutamiento de los flujos fijo (FR) ó adaptable dinámicamente (variable, VR), (ii) los flujos pueden ser divisibles (splittable) o no (unsplittable) (MH-VTD-FRs, MH-VTD-FRu, MH-VTD-VRs, y MH-VTD-VRu). En el caso MH-VTD-FR, el enrutamiento de los flujos sobre la topología virtual es fijo, es decir, el tráfico desde el nodo origen al nodo destino es siempre transmitido usando el mismo conjunto de lightpaths. Por el contrario, el enrutamiento variable (VR) no impone estas restricciones, pero sí implica un coste extra de señalización y una gestión de la red más compleja. Según el segundo criterio de clasificación, podemos considerar que los flujos sean divisibles o no divisibles. La variante FRu (unsplittable Flow Routing) indica que todo el tráfico entre cierto par de nodos debe atravesar la misma ruta, es decir, la misma secuencia de nodos independientemente del instante de tiempo en el que nos encontremos. Teniendo en cuenta esta restricción, cuando el tráfico entre un par de nodos es mayor que la capacidad de un único lightpath, un conjunto de varios lightpaths es necesario para enrutar el tráfico no divisible y todos estos lightpaths pertenecientes al conjunto deben ser enrutados de forma completamente óptica a través de la misma secuencia de nodos. Por otro lado, cuando el problema del tipo FRs (splittable Flow Routing) es considerado, el tráfico entre un par de nodos puede ser dividido en diferentes fracciones de tráfico que se pueden enrutar sobre lightpaths que no necesariamente deben atravesar la misma secuencia de nodos. Parece claro que este último caso ofrece una ventaja destacable respecto a la otra variante (unsplittable / no divisible), y es que el enrutamiento divisible nos permite un mejor balance del tráfico, aunque esta flexibilidad trae consigo el coste que conlleva un gasto mayor en señalización. El capítulo 3 presenta las contribuciones de esta tesis en la planificación de redes ópticas WDM considerando degradaciones de la capa física (Physical Layer Aware Planning (PLIA)). Estudiamos el problema tradicional de enrutamiento y asignación de longitudes de onda de los lightpaths (Routing and Wavelength Assignment (RWA)) teniendo en cuenta la degradación de las señales en el proceso de cálculo de los lightpaths (PLIA-RWA). En lo que respecta a la demanda del tráfico, consideramos que éste ya es conocido al menos parcialmente y, por tanto, las decisiones pueden ser tomadas previamente usando algoritmos PLIA-RWA estáticos. En las primeras secciones del capítulo 3, se presentan el problema de planificación PLIA y sus variantes estudiadas en esta tesis. También introducimos cómo la degradación de la señal es estimada y que efectos físicos son incluidos en el cálculo de dicha degradación. Se describen dos tipos de problemas PLIA-RWA. En ambos casos, los parámetros de entrada son la topología virtual compuesta por el número de lightpaths demandados entre cada par de nodos, y la topología física de la red. El problema PLIA-RWA obtiene el enrutamiento de los lightpaths válido teniendo en cuenta las degradaciones físicas, es decir, la secuencia de enlaces y longitudes de onda empleados en cada salto físico que satisfacen un umbral mínimo de calidad de transmisión. La otra variante del problema que estudiamos es PLIA-RWA-Regenerator Placement (PLIA-RWA-RP) donde además se usa la regeneración para evitar los efectos de la capa física. En este caso el problema, además de obtener el enrutamiento de los lightpaths sobre la topología física, calcula la posible secuencia de regeneradores que deben ser empleados en los nodos intermedios de cada lightpath cursado. Estos regeneradores se utilizan para garantizar que el nivel de la calidad de señal en el nodo destino sea mayor que un umbral de calidad de transmisión (Quality of Transmission (QoT)). En ambos casos, PLIA-RWA y PLIA-RWA-RP, es necesario el cálculo de la QoT de la señal y, por tanto, debemos emplear un estimador que calcula los efectos de la capa física a lo largo de cada camino. El resultado que obtiene dicho estimador depende de los efectos físicos que tengamos en cuenta y de algunas propiedades de la red como la tasa de bit o el formato de modulación. Por esta razón, estos datos así como la metodología empleada son descritos en más detalle en una de la secciones del capítulo 3. En el capítulo 4 se motiva la importancia de la interconexión óptica como un campo de investigación abierto y prometedor. Debemos notar que el interés por la interconexión óptica se ha enmarcado en el área de los routers de altas prestaciones donde nuevos componentes ópticos han sido desarrollados para esta aplicación. Como ya es conocido, los conmutadores de paquetes de gran capacidad son costosos, necesitan grandes espacios, tienen un consumo de energía elevado y además su escalabilidad está limitada por las restricciones de la tecnología electrónica a altas tasas binarias. Por estas razones, estudiamos en esta tesis los posibles beneficios de la introducción de la tecnología óptica en la arquitectura de conmutación de estos routers con el objetivo de superar el cuello de botella electrónico. Con este fin nos centramos en mostrar que las estructuras de conmutación empleadas en los routers comerciales pueden ser reemplazadas por estructuras ópticas sin cambios mayores en el router y alcanzando importantes ventajas tales como escalabilidad y bajo consumo de potencia. Seleccionamos routers VOQ (Virtual Output Queuing) cuyas estructuras de conmutación son claramente identificables y no emplean memoria intermedia permitiendo una sustitución que no da lugar a cambios en el resto de la estructura o el funcionamiento del router. La estructura electrónica de conmutación se reemplaza por una arquitectura basada en módulos ¿Array Wavelength Gratings¿ (AWG), ya que estos elementos están disponibles en el Mercado, y, además, son un componente pasivo prometedor por su escalabilidad para muy altas capacidades manteniendo un consumo bajo de energía. Por último, se obtienen resultados para dos routers comerciales (Cisco 12816 y Juniper TX Matrix) y éstos ilustran los beneficios en términos de escalabilidad de consumo y rendimiento que pueden ser alcanzados introduciendo una estructura óptica de conmutación. Para concluir esta tesis, el capítulo 5 recoge las principales conclusiones alcanzadas en las diferentes líneas de investigación desarrolladas.