CAMPO DE APLICACIÓN

La presente invención se relaciona al campo de las redes ópticas, más particularmente al campo de las redes ópticas dinámicas con restricciones de continuidad de longitudes de onda y en específico proporciona un método de enrutamiento para redes ópticas dinámicas con restricciones de continuidad de longitudes de onda.

ANTECEDENTES DE LA INVENCIÓN

El enrutamiento es un componente básico de la operación de la red: las conexiones están definidas por un par de nodos en la red: el nodo de origen y el nodo de destino, y para cada comunicación, el diseñador debe asignar una ruta a seguir por los datos a transmitir. Luego, el problema de enrutamiento consiste en asignar a cada conexión una ruta específica. Este problema se puede evaluar en dos formatos de operación de red diferentes. Estas son operaciones de red estáticas y dinámicas. Actualmente, el las redes ópticas son ineficientes, ya que funcionan de forma estática, es decir, los recursos se asignan permanentemente a cada usuario desde el origen hasta el destino, independientemente del porcentaje de tiempo que se utilicen. Esta operación es claramente subóptima; por lo tanto, una posible solución es migrar a una operación dinámica. Esto es, asignar los recursos a cada usuario solo cuando se solicita una comunicación. En consecuencia, el objetivo de esta invención es resolver el problema de enrutamiento en redes ópticas dinámicas.

El problema de enrutamiento se ha estudiado ampliamente en la literatura, debido a su gran impacto en el costo de la red (CapEx) y en el rendimiento de la red. Esta tarea generalmente se resuelve con el objetivo de minimizar simultáneamente el costo de la red, al tiempo que se garantiza que el rendimiento de la red cumple con el nivel establecido en el Acuerdo de nivel de servicio (SLA). Para resolver el problema de enrutamiento, se han propuesto varios enfoques, tales como: enrutamiento fijo, enrutamiento alternativo fijo y enrutamiento adaptativo. En“A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks” por Zang et al. publicado en revista Optical Networks Magazine, 1 (1 ): 47-60, 2000, hay una revisión exhaustiva sobre estas estrategias de enrutamiento.

El problema de enrutamiento se ve afectado en gran medida por si existe o no una capacidad de conversión de longitud de onda en los nodos ópticos. La capacidad de conversión de longitud de onda significa que, si un nodo recibe una señal entrante en una longitud de onda determinada, entonces el nodo puede transmitir la señal en cualquier canal de salida, pero utilizando una longitud de onda diferente. La tecnología de conversión de longitud de onda no está completamente disponible, por lo tanto, las redes ópticas actuales tienen una restricción de continuidad de longitud de onda, es decir, cuando se realiza una comunicación de extremo a extremo entre cualquier par de nodos, la ruta que los conecta debe usar la misma longitud de onda en cada enlace de la ruta. Sin embargo, en el contexto de las redes ópticas dinámicas, diferentes transmisiones del mismo usuario pueden transmitirse en diferentes longitudes de onda.

A continuación, se presentan las principales patentes existentes relacionadas con el problema de enrutamiento en redes ópticas WDM dinámicas con restricciones de continuidad de longitud de onda.

La patente US 9,060,215 B2 de fecha 16.06.2015, titulada "NetWork specific routing and wavelength assignment for optical Communications networks"; por Miedema et. al., perteneciente a Cieña Corporation, describe un algoritmo genético para resolver el enrutamiento y la asignación de longitud de onda en redes ópticas con enrutamiento de longitud de onda dinámica. El método propone un método iterativo, basado en algoritmos genéticos. El operador de la red puede elegir la función de adecuación para encontrar una buena solución basada en cualquier criterio definido por el operador de la red.

La patente US 8,693,871 B2 de fecha 08.04.2014, titulada "System for routing and wavelength assignment in wavelength división multiplexing optical networks"; por Resende et. al., perteneciente a AT&T Intelectual Property I, L.P., describe un método para resolver el enrutamiento y la asignación de longitud de onda. Este método busca minimizar el número de longitudes de onda utilizadas, en función de una solución de problema de empaquetado de contenedores, buscando resolver el número mínimo de contenedores, donde las longitudes de onda son contenedores. Este método asigna las longitudes de onda con las nuevas versiones de las técnicas First-Fit, Best-Fit, First-Fit Decrementing y Best- Fit Decringing, utilizando bandejas.

La patente estadounidense US 2014/086576 A1 , fechada el 27.03.2014, titulada "Determining Least-latency paths across a provider network utilizing available capacity" de Campbell et al., Perteneciente a Verizon Patent and Licensing, INC., Describe un sistema para calcular una o más Las rutas alternativas para cada usuario de la red. Los objetivos de este método son minimizar la latencia de cada usuario y disminuir la cantidad de procedimientos de conversión de longitud de onda necesarios. Sin embargo, esta técnica resuelve este problema en una operación de red estática; esto significa que los recursos son asignados a cada usuario de forma permanente. Por el contrario, nuestra invención resuelve el problema de enrutamiento en una operación de red dinámica, por lo que los recursos se asignan a cada usuario a pedido, solo cuando el usuario desea transmitir al destino.

SUMARIO DE LA INVENCIÓN

La presente invención proporciona un método de enrutamiento para una red óptica de multiplexación por división de longitud de onda (WDM) dinámica que tiene restricciones de continuidad de longitud de onda, que se caracteriza porque comprende los pasos de:

obtener, mediante un procesador, la topología de dicha red óptica WDM dinámica que tiene restricciones de continuidad de onda almacenadas en una base de datos de topología, dicha red óptica WDM dinámica que está representada por N nodos de red y L enlaces que conectan dichos N nodos; obtener, mediante dicho procesador, una pluralidad de usuarios de dicha red, en donde un usuario de dicha pluralidad se encuentra definido como un nodo de origen, un nodo destino y una carga de tráfico asociada a dicho usuario;

obtener, mediante dicho procesador, una pluralidad de rutas no operativas, dicha pluralidad de rutas no operativas que corresponde a dicha pluralidad de usuarios; y almacenar dicha pluralidad de rutas no operativas en una base de datos de rutas no operativas, en donde dichas rutas no operativas se almacenan en dicha base de datos de rutas no operativas ordenadas de menor a mayor longitud y, para aquellas de igual longitud, de menor a mayor carga de tráfico; almacenar, en una base de datos de rutas operativas, las rutas que posean longitud igual a 1 y eliminar dicha ruta de dicha base de datos de rutas no operativas;

calcular, mediante dicho procesador, el costo de cada enlace de dicha red utilizando la información de dicha base de datos de rutas operativas;

calcular, mediante dicho procesador, una ruta de menor costo correspondiente al usuario de la primera ruta no operativa de dicha base de datos de rutas no operativas, utilizando la información correspondiente al costo de cada enlace; almacenar dicha ruta de menor costo en dicha base de datos de rutas operativas y eliminar dicha ruta no operativa correspondiente a dicho usuario de dicha base de datos de rutas no operativas;

repetir los dos pasos anteriores hasta que no existan rutas no operativas en dicha base de datos de rutas no operativas; y transmitir información a través de dicha red utilizando dichas rutas almacenadas en dicha base de datos de rutas operativas.

En una realización preferida, el método se caracteriza porque dichas rutas no operativas se obtienen mediante el algoritmo Dijkstra. En otra realización preferida, el método se caracteriza porque dichas rutas de menor costo se obtienen mediante el algoritmo Dijkstra ponderado por el costo de cada enlace.

En una realización preferida adicional, el método se caracteriza porque el costo de cada enlace, se obtiene mediante la fórmula: = _e Pt ^~ P en donde p _{ es la carga de tráfico del enlace £ y p es la carga de tráfico promedio de dicha red. En una realización más preferida, el método se caracteriza porque la carga de tráfico de cada enlace £, p _{ , se obtiene mediante la fórmula: en donde u _{ es el conjunto de usuarios cuyas rutas operativas utilizan el enlace £ y p _u es la carga de tráfico de un usuario u. En otra realización más preferida, el método se caracteriza porque dicha carga de tráfico promedio, p, se obtiene mediante la fórmula

BREVE DESCRIPCIÓN DE LAS FIGURAS

FIG. 1 es un diagrama que describe, de manera general, el tipo de entorno en el que se implementa la invención, identificando los principales subsistemas involucrados en su operación.

FIG. 2 es un diagrama que describe la topología de la red del proveedor en la

FIG. 1.

FIG. 3A es un diagrama que describe la estructura del sistema de información de topología de red en la FIG. 1.

FIG. 3B es un diagrama que describe una tabla para almacenar la información de los nodos en la FIG. 2. FIG. 3C es un diagrama que describe una tabla para almacenar la información de los enlaces en la FIG. 2.

FIG. 4A es un diagrama que describe la estructura del sistema de información de usuarios en la FIG. 1.

FIG. 4B es un diagrama que describe una tabla para almacenar la información de los usuarios de la red que pertenece a la base de datos de usuarios en la FIG. 4A.

FIG. 5A es un diagrama que describe la estructura y los componentes funcionales del sistema de cálculo de ruta de menor costo por capas en la FIG. 1.

FIG. 5B es un diagrama que describe la tabla de rutas no operativas calculadas y almacenadas en la base de datos de rutas no operativas en la FIG. 5A.

FIG. 5C es un diagrama que describe la tabla de rutas operativas calculadas y almacenadas en la base de datos de rutas operativas en la FIG. 5A.

FIG. 5D es un diagrama que describe la tabla de rutas calculadas y almacenadas en la base de datos de rutas en la FIG. 5A.

DESCRIPCIÓN DETALLADA DE LA INVENCIÓN

Los esquemas presentados en las figuras adjuntas describen el entorno de la invención.

El método que es objeto de la presente invención implementa un algoritmo de rutas de menor costo por capas (de ahora en adelante en el texto como CPL por sus siglas en inglés Cheapest Paths by Layers) que se basa en la ruta de menor costo que conecta un nodo de origen 210 a un nodo de destino 210 en la red del proveedor 1 10, mientras que, simultáneamente, la carga de tráfico en los enlaces en la red es lo más equilibrado posible. Cada par de nodos 210 representa un usuario u, que se comunica por medio de una ruta r _u . Se supone que el costo C _Tu de la ruta r _u es igual al costo del usuario u, y está dado por la suma del costo de cada enlace, , asignado a cada enlace i que pertenece a la ruta del usuario. Específicamente, se calcula mediante la ecuación (1 ) y C _Tu se calcula mediante la ecuación (2).

En la ecuación (1 ), es la carga de tráfico del enlace i 220, que es igual a la suma de la carga de tráfico p _u aportada por cada usuario u, que pertenece al conjunto de usuarios U _{ , que utilizan el enlace i en su ruta, como se describe en la ecuación (3):

Debe notarse que la carga de tráfico de cada usuario se almacena en la base de datos de usuarios 430 en el sistema de información de usuarios 130.

Por otro lado, haciendo referencia nuevamente a la ecuación (1 ), p es el promedio de la carga de tráfico de todos los enlaces 220 de la red del proveedor 1 10, como se presenta en la ecuación (4), donde L es el conjunto de los enlaces 220 en la red del proveedor 1 10, y L el número de enlaces en L.

La operación del método CPL se puede ejecutar en el entorno 100 como se ilustra en la FIG. 1. La configuración puede estar compuesta por una red del proveedor 1 10 y por un sistema de información de topología de red 120, que contiene la estructura de la topología de la red del proveedor 1 10. También puede contener un sistema de información de usuarios 130, que contiene el conjunto de usuarios (par de nodos de origen y destino) que utilizan la red del proveedor 1 10 y la carga de tráfico de cada usuario. Además, el entorno 100 posee un sistema de cálculo de ruta de menor costo por capas 150, encargado de calcular la ruta de menor costo para cada usuario, que se encuentra conectado al sistema de información de topología de red 120 y al sistema de información de usuarios 130, a través del sistema de comunicación 140. La red del proveedor 1 10 es una red óptica, que se puede modelar como un grato g = compuesta por un conjunto JNT de nodos 210 interconectados por un conjunto £ de enlaces de fibra óptica 220. Un nodo de red 210 puede ser cualquier tipo de red óptica (es decir, una conexión cruzada óptica - OXC) sin capacidades de conversión de longitud de onda.

El sistema de información de topología de red 120 puede ser un servidor o un dispositivo de red dentro o fuera de la red del proveedor 1 10. El sistema de información de topología de red 120 se almacena en una base de datos de topología 330 y puede estar constituido por una interfaz de entrada 310 que recibe una solicitud o datos del sistema de comunicación 140 que son procesados por un procesador 320. La base de datos de topología 330 incluye la información de nodos 210 y la información de enlaces 220 en la red del proveedor 110, utilizando una tabla de nodos 350 para almacenar los nodos 210 y otra tabla de enlaces 360 para almacenar los enlaces 220, como se describe en las Figuras 3B y 3C respectivamente. Para comunicarse con otros sistemas o dispositivos, el sistema de información de topología de red 120 puede enviar mensajes utilizando la interfaz de salida 340.

El sistema de información de usuarios 130 puede ser un servidor o un dispositivo de red fuera de la red del proveedor 110 y puede estar compuesto por una interfaz de entrada 410 que recibe solicitudes de información del sistema de comunicación 140. Esta información es procesada por el procesador 420 y puede almacenarse en la base de datos de usuarios 430. La base de datos de usuarios 430 contiene todos los datos de los usuarios (pares de nodos) en la red del proveedor 1 10, y la carga de tráfico asociada a cada uno de ellos, como se presenta en la tabla de usuarios 450 que se muestra en la Fig. 4B. Para interactuar con otros sistemas y dispositivos, el sistema de información de usuarios 130 usuarios puede enviar mensajes utilizando la interfaz de salida 440.

El sistema de cálculo de ruta de menor costo por capas 150 puede ser un servidor o un dispositivo de computadora con la capacidad de comunicarse con otros dispositivos, por ejemplo, una computadora de escritorio o una computadora portátil, fuera de la red del proveedor 1 10. El sistema de cálculo de ruta de menor costo por capas puede componerse por una interfaz de entrada 510, que acepta solicitudes o información del sistema de comunicación 140. Durante la ejecución del algoritmo CPL, el sistema de cálculo de ruta de menor costo por capas 150 puede solicitar datos relativos a la topología de la red y los usuarios, al sistema de información de topología de red 120 y sistema de información de usuarios 130, respectivamente. Dicha información se almacena en las bases de datos propias del dispositivo, ya sea en la base de datos de topología 520 con la información de la topología, o en la base de datos de usuarios 530 con los datos de los usuarios. El calculador de costo de enlace 540 y el calculador de ruta 550 utilizan la información almacenada en la base de datos de rutas no operativas 560 y la base de datos de rutas operativas 570 para calcular los costos de cada enlace y de cada de ruta, respectivamente. La base de datos de rutas operativas 570 contiene todos aquellos usuarios y sus rutas, que tienen sus rutas definitivas calculadas durante la ejecución del algoritmo CPL. Por otra parte, la base de datos de rutas no operativas 560 contiene los otros usuarios, es decir, aquellos quienes no poseen una ruta definitiva definida durante la ejecución del algoritmo CPL. El calculador de costo de enlace 540 utiliza la información de la base de datos de topología 520, de la base de datos de usuarios 530, y de la base de datos de rutas operativas para calcular el costo asociado a cada enlace 220. A la vez, el calculador de rutas 550 está a cargo de calcular la ruta para cada usuario. Para su entrega, los resultados de la ejecución del algoritmo CPL pueden almacenarse en la base de datos de rutas 580, o ser enviadas a otro sistema o dispositivo utilizando la interfaz de salida 590, como una tabla de rutas 630, tal como se describe en la Fig. 5D.

La estructura de la tabla de rutas no operativas 610, la tabla de rutas operativas 620 y la tabla de rutas 630 se muestran en las FIG. 5B, 5C y 5D, respectivamente.

El sistema de comunicación 140 puede ser cualquier sistema de red que permita conectar dos o más dispositivos, como la red celular, la red móvil pública terrestre (PLMN), una red de segunda generación (2G), una red de tercera generación (3G), una cuarta generación (4G), una red de evolución a largo plazo (LTE), una quinta generación (5G), una red de acceso múltiple por división de código (CDMA), un sistema global para redes de comunicaciones móviles (GSM), un paquete general de servicios de radio (GPRS) ), una red de área local (LAN), una red de área amplia (WAN), una red de área metropolitana (MAN), una red ad hoc, una intranet, Internet, una red basada en fibra óptica, una red satelital, red de televisión, o una mezcla de uno o más de estos sistemas.

El método CPL se ejecuta en el sistema de cálculo de ruta de menor costo por capas 150 y su funcionamiento se describe a continuación:

1. El sistema de cálculo de ruta de menor costo por capas 150 solicita la información de topología de red al sistema de información de topología de red 120 y la almacena en su propia base de datos de topología 520.

2. El sistema de cálculo de ruta de menor costo por capas 150 solicita la información de los usuarios y sus cargas de tráfico al sistema de información de usuarios 130, almacenándolos en la base de datos de rutas no operativas 560.

3. El calculador de costo de enlace 540 define todos los costos de enlace iguales a 1.

4. El calculador de ruta 550 calcula el conjunto inicial de rutas (para cada usuario de la red), utilizando cualquier algoritmo de ruta más corto (por ejemplo, Dijkstra), basado en la topología de la red y en el costo de los enlaces almacenados previamente en el paso 3.

5. El calculador de ruta 550 almacena el conjunto inicial de la ruta de los usuarios en la base de datos de rutas no operativas 560.

6. El calculador de rutas 550 clasifica las rutas de la base de datos de rutas no operativas 560 según su longitud (es decir, la cantidad de enlaces que comprenden la ruta), de más corta a más larga. Las rutas con la misma longitud están ordenadas por su carga de tráfico (de menor a mayor). En caso de empate, el orden se elige arbitrariamente.

7. El calculador de rutas 550 mueve a todos los usuarios con una longitud de ruta igual a 1 , desde la base de datos de rutas no operativas 560 a la base de datos de rutas operativas 570. 8. El calculador de costos de enlace 540 calcula el costo en cada enlace, utilizando el algoritmo de costo (CA) (descrito a continuación), considerando solo las rutas de todos los usuarios almacenados en la base de datos de rutas operativas 570.

9. El calculador de rutas 550 calcula la ruta de menor costo utilizando

Dijkstra, considerando el costo del enlace evaluado en el paso 8.

10. El calculador de rutas 550 mueve al usuario (solo uno) asociado a la ruta seleccionada en el paso 9, desde la base de datos de rutas no operativas 560 a la base de datos de rutas operativas 570.

1 1. Los pasos 9, 10 y 11 se repiten hasta que no haya ningún usuario almacenado en la base de datos de rutas no operativas 560.

12. Finalmente, cuando todos los usuarios se trasladaron a la base de datos de rutas operativas 570, esta base de datos se envía a la base de datos de rutas 580.

Un administrador de red puede usar esta tabla de enrutamiento (llamada R) para transferirla y copiarla de manera centralizada o distribuida en los nodos 210 de la red del proveedor 1 10.

CA: algoritmo de costo:

El calculador de costos de enlace 530 ejecuta las siguientes operaciones para cada enlace almacenado en la base de datos de topología 520:

Se calcula la carga de tráfico p _t del enlace £, usando la ecuación (3) (El conjunto U _{ considerado en este paso está compuesto por todos los usuarios almacenados en la base de datos de rutas operativas 570)

Se establece un costo a £, usando la ecuación (1 ).

El calculador de costos de enlace 530 calcula la carga de tráfico media de los enlaces mediante la ecuación (4).

El método de enrutamiento de menor costo se puede utilizar de dos maneras diferentes: a) Puede utilizarse para generar una ruta por usuario, válida para todas las longitudes de onda de la red

b) Alternativamente, se puede usar para generar una ruta por usuario, por cada longitud de onda diferente (o un conjunto de longitudes de onda consecutivas). En este caso, la carga de tráfico ofrecida por cada usuario en cada longitud de onda se puede evaluar utilizando el método publicado en "Evaluación de bloqueo y dimensionamiento de longitud de onda de redes WDM dinámicas sin conversión de longitud de onda" por Jara et.al. en el Diario de Comunicaciones Ópticas y Redes, vol. 9, no. 8, pp. 625-634, 2017., o cualquier otro método disponible en la literatura.