Método y dispositivo de determinación de ruta.

Un método para determinar una ruta, que comprende:

preajustar el número N de rutas,

realizar un algoritmo K de los itinerarios más cortos después de que se haya recibido una demanda de solicitud de ruta, calcular las rutas por grupo en conformidad con el número N de las rutas, cuando se calculen N rutas, proporcionando, a la salida, el número de rutas calculadas como un grupo y asignando recursos al grupo de rutas y

detener el cálculo de las rutas si una ruta en donde la puesta en correspondencia de los recursos se obtiene con éxito operativo desde el grupo de rutas y utilizar la ruta en la que es satisfactoria la puesta en correspondencia de los recursos como la ruta determinada; de no ser así, realizar la puesta en correspondencia de los recursos en el grupo siguiente de las rutas de salida para determinar una ruta;

en donde N es un número entero positivo y 1

Método y dispositivo de determinación de ruta

CAMPO TÉCNICO

La presente invención se refiere a una tecnología de enrutamiento en el campo de la comunicación y en particular, a un método y dispositivo para determinar una ruta.

ANTECEDENTES DE LA TÉCNICA RELACIONADA

La red óptica conmutada automática (ASON) es una tecnología de transmisión óptica con características inteligentes. Utiliza protocolos estándar, tales como señalización, encaminamiento, descubrimiento automático, etc., para poner en práctica funciones, tales como cálculo automático del encaminamiento, establecimiento automático de conexiones, descubrimiento automático de fuentes de red, etc., para mejorar la capacidad de control automático de la red de transmisión óptica, de modo que la red de transmisión óptica tenga características inteligentes tales como la red IP de protocolo de Internet. Un controlador de rutas, que actúa con un módulo encargado del cálculo automático de rutas, es un módulo componente importante de un plan de control de la red ASON y es también una forma de realización importante de su intelectualización.

El controlador de rutas en la red ASON suele obtener un itinerario más corto utilizando el protocolo tradicional de ‘El itinerario más corto primero’ (OSPF) . Sin embargo, en algunos casos, no es suficiente proporcionar solamente una ruta. A modo de ejemplo, el problema de puesta en correspondencia de recursos puede implicarse en algunas aplicaciones. Si la puesta en correspondencia no es operativamente satisfactoria, lo que indica que este itinerario está obstruido, en tal caso, fallará el cálculo de las rutas desde un nodo origen a un nodo destino. Por lo tanto, en algunas aplicaciones de la red ASON, el algoritmo de los K itinerarios más cortos (KSP) se utiliza para resolver el problema de puesta en correspondencia de recursos. Es decir, los K itinerarios alternativos más cortos se calcularán por el controlador de rutas para proporcionar una condición de que la puesta en correspondencia de recursos pueda determinar un itinerario más corto, con restricciones en origen, entre todas las K rutas alternativas. Por lo tanto, en donde se requiera calcular los K itinerarios más cortos alternativos, el algoritmo de KSP es una función importante en el controlador de rutas.

Un método similar se da a conocer, a modo de ejemplo, en la patente de Estados Unidos US 2004/153492 A1.

Según se ilustra en la Figura 1, existen dos módulos de procesamiento en el controlador de rutas de la red ASON, siendo uno de ellos un módulo de puesta en correspondencia de recursos (RM) que proporciona principalmente la función de puesta en correspondencia de recursos, el otro módulo es un módulo de KSP configurado para recibir una demanda de solicitud de ruta, para calcular rutas y para enviar las rutas calculadas al módulo RM, que procesa la puesta en correspondencia de los recursos. El procedimiento de trabajo del módulo de procesamiento en el controlador de rutas de la red ASON se ilustra en la Figura 2 y comprende las etapas siguientes. En la etapa 10, el módulo de KSP recibe una demanda de solicitud de ruta desde un nodo origen a un nodo destino. En la etapa 11, el módulo de KSP calcula las K rutas y las reenvía al módulo RM. En la etapa 12, el módulo RM realiza la puesta en correspondencia de recursos en las K rutas recibidas. En la etapa 13, el módulo RM reenvía el resultado de la puesta en correspondencia a un iniciador de demanda. Según dicho modo de trabajo, el módulo KSP interrumpe el cálculo solamente si se han calculado completamente los K itinerarios más cortos alternativos o no existe ninguna otra ruta alternativa disponible en la red aún cuando no se hayan calculado todavía completamente los K itinerarios más cortos alternativos. En tal caso, el módulo KSP envía todas las rutas calculadas al módulo RM para la puesta en correspondencia de recursos.

Actualmente, existen numerosas referencias de investigación sobre el algoritmo de KSP y el algoritmo de KSP utilizado para calcular K rutas es relativamente maduro. Sea cual fuere el sistema que utiliza el algoritmo KSP, la complejidad temporal del algoritmo de KSP completo es directamente proporcionar al valor de K. El valor de K, que es un parámetro principal del algoritmo de KSP, está preestablecido. Si el valor de K se establece para ser demasiado pequeño, en tal caso, el número de las rutas alternativas obtenidas es relativamente pequeño y es posible que una ruta, que cumple el requisito de puesta en correspondencia de recursos, pueda no encontrarse en las rutas; si el valor de K se establece para ser demasiado grande, en tal caso, el algoritmo de KSP consume un tiempo más largo. Puede deducirse de lo que antecede que existe una contradicción entre la reducción del tiempo consumido del algoritmo de KSP y la satisfacción del requisito de puesta en correspondencia de recursos cuando se determina la ruta.

SUMARIO DE LA INVENCIÓN

La presente invención da a conocer un método y dispositivo para determinar una ruta con el fin de resolver el problema de que existe una contradicción entre reducción de tiempo consumido del algoritmo de KSP y satisfacción del requisito de puesta en correspondencia de recursos en la técnica anterior.

Para poder resolver el problema anterior, la presente invención da a conocer el sistema técnico siguiente.

La presente invención da a conocer un método para determinar una ruta que comprende:

preajustar el número N de rutas, realizar un algoritmo de K itinerarios más cortos después de que se reciba una demanda de solicitud de ruta, calcular las rutas por grupo en función del número N de las rutas, siempre que se calculen N rutas, proporcionar a la salida, las N rutas calculadas como un grupo y asignar recursos al grupo de rutas; y

interrumpir el cálculo de las rutas si una ruta, en la que la puesta en correspondencia de recursos se realiza de forma operativamente satisfactoria, se obtiene a partir del grupo de rutas y utilizar la ruta en la que la puesta en correspondencia de recursos es operativamente satisfactoria como la ruta determinada; si no es así, realizar la puesta en correspondencia de recursos en el siguiente grupo de rutas de salida para determinar una ruta;

en donde N es un número entero positivo y 1<N<K.

El método comprende, además, la determinación de si todas las rutas han sido calculadas completamente y la interrupción del procedimiento de cálculo de los K itinerarios más cortos cuando todas las rutas hayan sido calculadas completamente.

El método comprende, además: la determinación de si todas las rutas han sido calculadas y puestas en correspondencia completamente cuando la puesta en correspondencia de recursos no es operativamente satisfactoria y terminar el procedimiento de determinación de rutas cuando todas las rutas se hayan calculado y puestas en correspondencia completamente.

Las rutas se calculan en un orden de calidad de itinerario desde bueno a deficiente y la puesta en correspondencia de recursos se realiza en un orden de calidad de itinerario desde bueno a deficiente en el grupo de rutas.

N tiene un valor de 2, 3, 4 o 5.

La presente invención da a conocer, además, un dispositivo para determinar una ruta, que comprende:

un módulo de cálculo de rutas configurado para preestablecer el número N de rutas, para realizar un algoritmo de los K itinerarios más cortos después de que se reciba una demanda de solicitud de ruta, calcular las rutas por grupo en función del número N de las rutas, siempre que se calculen N rutas, proporcionar, a la salida, las N rutas calculadas como un grupo a un módulo de puesta en correspondencia de recursos y realizar la puesta en correspondencia de recursos en el grupo de rutas; y

el módulo de puesta en correspondencia de recursos está configurado para realizar la puesta en correspondencia de recursos en el grupo de rutas recibidas, si se obtiene una ruta en la que la puesta en correspondencia de recursos es operativamente satisfactoria, utilizar la ruta como la ruta determinada y notificar al módulo de cálculo de rutas que interrumpa el cálculo de las rutas; de no ser así, realizar la puesta en correspondencia de recursos en el siguiente grupo de rutas recibidas para determinar una ruta;

en donde N es un número entero positivo y 1<N<K.

El módulo de cálculo de rutas está configurado, además, para determinar si todas las rutas han sido calculadas completamente y para interrumpir el procedimiento de cálculo de los K itinerarios más cortos cuando todas las rutas se hayan calculado completamente.

El módulo de puesta en correspondencia de recursos está configurado,... [Seguir leyendo]

1. Un método para determinar una ruta, que comprende:

preajustar el número N de rutas, realizar un algoritmo K de los itinerarios más cortos después de que se haya recibido una demanda de solicitud de ruta, calcular las rutas por grupo en conformidad con el número N de las rutas, cuando se calculen N rutas, proporcionando, a la salida, el número de rutas calculadas como un grupo y asignando recursos al grupo de rutas y

detener el cálculo de las rutas si una ruta en donde la puesta en correspondencia de los recursos se obtiene con éxito operativo desde el grupo de rutas y utilizar la ruta en la que es satisfactoria la puesta en correspondencia de los recursos como la ruta determinada; de no ser así, realizar la puesta en correspondencia de los recursos en el grupo siguiente de las rutas de salida para determinar una ruta;

en donde N es un número entero positivo y 1<N<K.

2. El método según la reivindicación 1 que comprende, además:

determinar si todas las rutas han sido calculadas completamente y

detener el procedimiento de cálculo K de los itinerarios más cortos cuando todas las rutas han sido calculadas completamente.

3. El método según la reivindicación 1 que comprende, además:

determinar si todas las rutas se han calculado y puestas en correspondencia completamente cuando la puesta en correspondencia de los recursos no ha sido operativamente satisfactoria y terminar el procedimiento de determinación de ruta cuando todas las rutas han sido calculadas y puestas en correspondencia completamente.

4. El método según una cualquiera de las reivindicaciones 1 a 3, en donde la ruta se calcula en un orden de la calidad de los itinerarios de buena a deficiente y

la puesta en correspondencia de los recursos se realiza según un orden de la calidad de los itinerarios de bueno a deficiente en el grupo de rutas.

5. El método según la reivindicación 4, en donde N es 2, 3, 4 o 5.

6. Un dispositivo para la determinación de una ruta que comprende:

un módulo de cálculo de rutas configurado para preestablecer el número N de rutas, realizar un algoritmo de los K itinerarios más cortos después de que se haya recibido una demanda de solicitud de ruta, calcular las rutas por grupo en función del número N de las rutas, siempre que se calculen N rutas, proporcionar, a la salida, las N rutas calculadas como un grupo a un módulo de puesta en correspondencia de los recursos y realizar una puesta en correspondencia de los recursos en el grupo de rutas y

el módulo de puesta en correspondencia de los recursos está configurado para realizar la puesta en correspondencia de los recursos en el grupo de rutas recibidas, si una ruta, en donde la puesta en correspondencia de los recursos se obtiene con éxito operativo, utilizar la ruta como ruta determinada y notificar al módulo de cálculo de rutas que interrumpa el cálculo de las rutas; si no es así, realizar la puesta en correspondencia de los recursos en el siguiente grupo de rutas recibidas para determinar una ruta;

en donde N es un número entero positivo y 1<N<K.

7. El dispositivo según la reivindicación 6, en donde el módulo de cálculo de rutas está configurado, además, para 55 determinar si todas las rutas han sido calculadas completamente e interrumpir el procedimiento de cálculo de los K itinerarios más cortos cuando todas las rutas han sido calculadas completamente.

8. El dispositivo según la reivindicación 6, en donde el módulo de puesta en correspondencia de los recursos está configurado, además, para determinar si todas las rutas han sido calculadas y puestas en correspondencia completamente cuando no ha tenido éxito operativo la puesta en correspondencia de los recursos y terminar el procedimiento de determinación de ruta cuando todas las rutas hayan sido calculadas y puestas en correspondencia completamente.

9. El dispositivo según una cualquiera de las reivindicaciones 6 a 8, en donde el módulo de cálculo de rutas 65 calcula la ruta según un orden de la calidad del itinerario de buena a deficiente y el módulo de puesta en correspondencia de los recursos está configurado, además, para realizar la puesta en correspondencia de los recursos en las rutas objeto de salida por el módulo de cálculo de rutas según un orden de la calidad del itinerario de buena a deficiente.

10. El dispositivo según la reivindicación 9, en donde N es 2, 3, 4 o 5.

Módulo RM Módulo KSP

El módulo KSP recibe una demanda de solicitud de ruta desde un nodo origen a un nodo destino El módulo KSP calcula K rutas y las reenvía al módulo RM

El módulo RM realiza la puesta en correspondencia de recursos para las K rutas recibidas

El módulo RM reenvía el resultado de la puesta en correspondencia a un iniciador de demanda Preajuste del número N de rutas, realización del algoritmo de los K itinerarios más cortos después de que se reciba una demanda desolicitud de ruta, cálculo de las rutas por grupo en función del número Nde las rutas, siempre que se calculen N rutas, suministro de las N rutascalculadas como un grupo y asignación de recursos al grupo de rutas, en donde N es un número entero positivo y 1<N<K

Se obtiene desde el grupo de rutas unaruta en la que la correspondencia de los recursos es satisfactoria?

Interrupción del cálculo de rutas y utilización de la ruta en la que lacorrespondencia de recursos es satisfactoria como la ruta determinada y finalización del procedimiento de determinación de ruta Realización de la puesta en correspondencia de recursos en el siguiente grupo de rutas de salida para determinar una ruta

Preajustar el número N de rutas y un identificador global

Recepción de una demanda de solicitud de ruta que contiene un nodo origen y un nodo destino e iniciación del procedimiento de cálculo de KSP para las rutas en función de la demanda de solicitud de ruta

Lectura del identificador global para determinar si el estado del identificador global es “éxito” o “fallo” Fallo Éxito Interrumpir el cálculo de ruta y usar una ruta en la que la correspondencia de recursos es un éxito operativo como la ruta determinada final y finalizar el procedimiento de determinación de ruta

Realizar el algoritmo de los K itinerarios más cortos y calcular y suministrar N rutas en función del número N de rutas

Se han calculado completamente todas las rutas? Interrumpir elprocedimiento de cálculo de KSP

Se realiza la correspondencia de recursos en N rutas de salida y se determina si la correspondencia de recursos es satisfactoria Modificar del estado del identificador global como “éxito” Se han calculado y puesto en correspondenciacompletamente todas las rutas? Sí

Finalizar el procedimiento dedeterminación de rutas

FIG. 6