METODO GENERAL PARA EL DISEÑO DE ESQUEMAS SIN PERDIDAS EN REDES OBS.

Método general para el diseño de esquemas sin pérdidas en redes OBS.

Se propone una estrategia general de transmisión sin pérdidas para redes de conmutación óptica de ráfagas que combina un esquema de asignación de longitudes de onda y caminos con mecanismos simples de resolución de contiendas. La solución propuesta cumple la restricción de continuidad en longitud de onda, es aplicable en entornos de transmisión síncronos y asíncronos, y es independiente de la estadística de generación y de la longitud de las ráfagas. El patrón de transmisión que se define para cada longitud de onda asegura que toda contienda se puede resolver retardando de forma adecuada la transmisión de las ráfagas que compiten por el uso simultáneo de recursos en un enlace intermedio. Dicho retardo adicional (independiente de la longitud de los enlaces) se puede introducir en la programación de las ráfagas en el nodo origen (solución estática) o bien añadirse en un nodo intermedio cuando se produce contienda (solución dinámica)

Método general para el diseño de esquemas sin pérdidas en redes OBS.

Sector de la técnica

La invención se engloba dentro de las nuevas tecnologías de redes ópticas de gran capacidad, más específicamente las redes OBS. El objetivo es diseñar un esquema general de asignación de recursos libre de pérdidas en redes OBS independiente de la topología de red considerada.

Estado de la técnica

El rápido crecimiento del tráfico en Internet en los últimos años ha potenciado la investigación y el desarrollo de nuevas redes ultra-rápidas basadas en tecnologías rentables que permitan aprovechar la potencial capacidad de transmisión de las fibras ópticas. Para soportar los crecientes requerimientos de ancho de banda, en muchas redes troncales ya se han instalado sistemas ópticos basados en la tecnología de Multiplexado por División de Longitud de Onda Densa ("Dense Wavelength Division Multiplexing", D-WDM), que asigna los trenes de información a las distintas componentes de longitud de onda (colores) de la luz blanca.

La tecnología D-WDM además de incrementar la capacidad de transmisión de las fibras ópticas en varios órdenes de magnitud, plantea el reto de desarrollar tecnologías ópticas de conmutación capaces de manejar el elevado número de canales que D-WDM habilita, abriendo el debate entorno a la definición de mecanismos eficientes de provisión de recursos (caminos y longitudes de onda).

Del mismo modo que en el dominio electrónico, existen dos grandes grupos de tecnologías de conmutación ópticas. El primer grupo engloba las técnicas de conmutación óptica de circuitos ("Optical Circuit Switching, OCS") que se basan en establecer caminos de luz ("lightpaths") a través de la red. A pesar de garantizar un ancho de banda constante y un retardo acotado, proporcionan una utilización relativamente pobre de la red debido al uso dedicado de las longitudes de onda. No obstante, ofrecen una gran sencillez de implementación. El segundo grupo incluye todas las técnicas basadas en la conmutación óptica de paquetes ("Optical Packet Switching, OPS") que resultan más adecuadas para tráfico a ráfagas ("bursty") permitiendo una mayor utilización de los recursos de la red mediante el multiplexado estadístico del tráfico de los usuarios. Sin embargo, la tecnología óptica actual no permite realizar el procedo de las cabeceras ópticas a las velocidades requeridas. Además, dado que no existe un equivalente real a las memorias de acceso aleatorias (RAMs) en el dominio óptico, es decir, la luz no se puede guardar, requieren el desarrollo de mecanismos que puedan resolver las contiendas que se producen cuando dos paquetes pretenden utilizar simultáneamente una misma longitud de onda en un enlace intermedio de la red.

Para relajar los requisitos tecnológicos que requieren las implementaciones de OPS pero manteniendo un cierto grado de multiplexado estadístico, se definió la tecnología de conmutación óptica de ráfagas ("Optical Burst Switching, OBS"). En los nodos frontera ("edge nodes") de una red OBS las unidades de datos de los usuarios se agrupan formando unidades de datos de longitud superior denominadas ráfagas. Antes de la transmisión de cada ráfaga, se transmite un paquete de control que es procesado en el dominio electrónico en cada nodo intermedio ("core nodes") con el objetivo de establecer la configuración adecuada de la matriz de conmutación para que la posterior transmisión de la ráfaga se pueda realizar de forma transparente en el dominio óptico.

El objetivo de la tecnología OBS es mejorar el caudal ("throughput") y, a su vez, aumentar la velocidad de aprovisionamiento de la red. Así pues, la mayoría de implementaciones consideran mecanismos de señalización unidirecionales en los cuales la transmisión de la ráfaga se inicia un intervalo de tiempo (denominado "offset") después de la transmisión del paquete de control sin tener confirmación sobre la disponibilidad de los recursos solicitados en todos los enlaces intermedios del camino. Así que, de forma análoga a lo que ocurre en OPS, se pueden producir contiendas entre ráfagas que solicitan el uso simultáneo de una longitud de onda en un enlace intermedio de la red. Si no se resuelven, las contiendas pueden desembocar en la pérdida de datos y es por este motivo que la resolución de contiendas es un problema clave para favorecer y potenciar el desarrollo comercial de OBS.

Los esquemas de resolución de contiendas más conocidos, tanto en OPS como en OBS, son la conversión de longitud de onda en el dominio de la frecuencia, la desviación en el encaminamiento ("deflection routing") en el dominio del espacio y el almacenaje mediante líneas de retardo en el dominio temporal. Estos esquemas no son excluyentes, se pueden combinar para obtener mejores resultados y han dado lugar al desarrollo de múltiples variantes que tienen como objetivo reducir la probabilidad de contienda o reducir el porcentaje de paquetes perdidos. Sin embargo, en general, estas técnicas no garantizan la ausencia absoluta de pérdidas.

En esta invención se presenta un método general de asignación de recursos (caminos, longitudes de onda y, en caso necesario, ventanas de offset) para redes OBS. La estrategia propuesta asegura una transmisión libre de pérdidas bajo condiciones de tráfico dinámico independientemente de la topología de red considerada. Así, mediante una adecuada asignación de longitudes de onda a los distintos caminos se define el patrón de transmisión de cada longitud de onda, es decir, el conjunto de caminos a los que les es permitido compartir una misma longitud de onda. Todas las posibles contiendas que se producen entre caminos que comparten una misma longitud de onda se puede resolver retardando de forma adecuada la transmisión de las ráfagas que compiten por el uso simultáneo de recursos. Dicho retardo adicional (que es independiente de la longitud de los enlaces) se puede introducir en el instante de programación de las ráfagas en el nodo origen (solución estática) o bien añadirse en un nodo intermedio sólo en el caso que se produzca contienda (solución dinámica). En el primer caso, es necesario preasignar a cada comunicación una ventana de offset (o de compensación) que define un rango de valores de offset adecuados para la transmisión de las ráfagas sobre un determinado camino [Anna Agustí-Torra, Cristina Cervelló-Pastor y Miquel A. Fiol, "Wavelength and Offset Window Assignment Schemes to Avoid Contention in OBS Rings", Third International Conference on Broadband Communications, Networks and Systems, Octubre 2006]. En el segundo caso, cada nodo intermedio debe disponer, en cada puerto de salida, de una única fibra de retardo que se encarga de retardar la transmisión de las ráfagas en tránsito (es decir, generadas por los nodos precedentes de la red) cuando dichas ráfagas compiten por el uso simultáneo de recursos con ráfagas locales (es decir, generadas por el propio nodo) [Anna Agustí-Torra, Cristina Cervelló-Pastor y Miquel A. Fiol, "A New Approach to Loss-Free Packet/Burst Transmission in All-Optical Networks", Sixth IEEE/CreateNet International Workshop on Optical Burst/Packet Switching (WOBS '06), Octubre 2006].

Descripción breve de las figuras

Para facilitar la comprensión de la descripción detallada de la invención, se incluyen referencias a las figuras siguientes:

• La Figura 1 ilustra el diagrama de bloques del método de asignación de recursos propuesto.

• La Figura 2 ejemplifica dos casos de interferencia entre comunicaciones, denotados como colisión y solapamiento.

• La Figura 3 ilustra el diagrama de bloques del algoritmo que, dado un digrafo D y un ciclo orientado del digrafo C, proporciona un ?-digrafo con raíz el ciclo C.

• La Figura 4 ilustra el diagrama de bloques del algoritmo que, dado un ?-digrafo acíclico, proporciona la asignación de ventanas de offset a las comunicaciones descritas por el ?-digrafo.

• La Figura 5 ejemplifica la aplicación del mecanismo basado en el digrafo línea para la definición del conjunto de ?-digrafos arco-disjuntos para una longitud de onda dada.

• La Figura 6 ejemplifica la aplicación del algoritmo voraz ("greedy") para la asignación de ventanas de offset sobre un ?-digrafo acíclico.

Descripción detallada de la invención

La invención consiste en un método general de asignación de recursos en una red de conmutación óptica de ráfagas (OBS) para la transmisión libre de pérdidas. Así, la asignación de longitudes de onda se realiza con el fin de limitar los...

1. Método de asignación de recursos en una red OBS (con independencia de su topología) para la transmisión de información sin pérdidas basado en la consecución de las etapas siguientes:

        Etapa 1. Asignación de longitudes de onda distintas a caminos que colisionan mediante la definición de ?-digrafos (cada uno de los cuáles representa el patrón de transmisión de una longitud de onda) en los que todos los vértices tienen un grado de entrada inferior o igual a 1.

        Etapa 2. Resolución de las contiendas que se pueden producir por solapamiento de caminos que comparten la misma longitud de onda (por pertenecer a un mismo ?-digrafo) mediante la introducción de un retardo de transmisión adicional (pero independiente de la longitud de los enlaces).

2. Método de asignación de recursos en una red OBS según la reivindicación 1, caracterizado por definir un par de ?-digrafos asociados a una misma longitud de onda a partir del grafo G que modela la red mediante la consecución de los pasos siguientes:

        a.        Definir una orientación G⁺ de G y su complementario G^- = G⁺. En cada orientación, elegir un ciclo orientado, C⁺ y C^-, respectivamente (que en particular pueden tener longitud 0).

        b.        Para cada orientación (G⁺ y G^-), denotado como D en general, definir el ?-digrafo con raíz el ciclo orientado (C⁺ y C^-), denotado como C en general, mediante la consecución de los pasos siguientes:

-        vtcortaunaDefinir el digrafo línea LD del digrafo D, cuyos vértices representan los arcos de D y cuyos arcos se definen en función de las arco-adyacencias en D.

-        vtcortaunaRepresentar un vértice adicional v en LD con un arco incidente a todos los vértices de LD que representan aristas de salida de los vértices de C en D.

-        vtcortaunaDefinir un árbol de encaminamiento en LD con raíz en el vértice v (utilizando cualquier algoritmo de encaminamiento).

-        vtcortaunaDefinir el ?-digrafo recorriendo el árbol de encaminamiento definido en LD identificando los vértices que cubre el árbol en LD como las aristas que se recurren en D. Para evitar que ningún vértice del ?-digrafo tenga grado de entrada superior a 1, repetir tantos vértices como sea necesario en la definición del ?-digrafo.

3. Método de asignación de recursos en una red OBS según la reivindicación 1, caracterizado por introducir el retardo adicional en el momento de la programación de la ráfaga (solución estática) utilizando un tiempo de offset adecuado para resolver todas las contiendas por solapamiento de caminos que pueden producirse dentro de los patrones de transmisión (representados mediante ?-digrafos). El rango de valores de offset asociado a cada camino depende de la ventana asignada a dicho camino, cuya asignación se realiza mediante el algoritmo voraz siguiente:

        a.        Seleccionar todos los nodos del ?-digrafo con grado de salida 0 y eliminarlos.

        b.        Inicializar el valor de la ventana de offset a 1.

        c.        Seleccionar todos los nodos del ?-digrafo con grado de salida 0 y asignarles el valor en curso de la ventana de offset.

        d.        Eliminar todos los nodos seleccionados en el paso c.

        e.        Si quedan nodos en el ?-digrafo sin ventana asignada, incrementar el valor de la ventana de offset en 1 y volver al paso c.

El mínimo offset de la ventana n+1 (con n=0) debe ser superior al máximo offset de la ventana n, más el tiempo de transmisión de la ráfaga más larga, más el tiempo de procesado del paquete de control asociado a una ráfaga.

4. Método de asignación de recursos en una red OBS según la reivindicación 1, caracterizado por introducir el retardo adicional en un nodo intermedio sólo en el caso que se produzca contienda (solución dinámica) mediante el uso de una fibra de retardo que retarda la transmisión de la ráfaga durante un tiempo superior al tiempo de transmisión de la ráfaga más larga más el mayor tiempo de offset asignable por parte del nodo.