Método y aparato para seleccionar entre múltiples trayectos de igual coste.

Un aparato para seleccionar entre múltiples trayectos de igual coste en una red de comunicación (10),

el aparato que incluye uno o más procesadores y una o más memorias, la una o más memorias que contienen datos e instrucciones que, cuando se cargan en el uno o más procesadores configuran el aparato para realizar un método de selección entre los múltiples trayectos de igual coste, el método que incluye los pasos de:

determinar un conjunto de trayectos de igual coste entre un par de nodos (11-18) en una red de comunicación, cada trayecto que incluye una pluralidad de enlaces;

caracterizado por que el método además incluye los pasos de:

construir unos primeros ID de enlace para cada enlace en cada uno de los trayectos de igual coste, cada uno de los primeros ID de enlace que se crea concatenando los ID de nodo ordenados de nodos que conectan con el enlace en la red;

construir unos primeros ID de trayecto para cada uno de los trayectos de igual coste, cada uno de los primeros ID de trayecto que se crea concatenando los primeros ID de enlace de la pluralidad de enlaces que forman ese trayecto a través de la red de comunicación;

clasificar los primeros ID de trayecto para seleccionar un primer conjunto de trayectos diversos a través de la red de comunicación;

construir unos segundos ID de enlace para cada enlace en los trayectos de igual coste, cada uno de los segundos ID de enlace que se crea concatenando un ID de nodo de uno de los nodos que conecta con el enlace en la red con un ID de nodo invertido del otro de los nodos que conecta con ese enlace en la red, los ID de nodo que se concatenan para formar los segundos ID de enlace en el mismo orden que se determinó cuando se construyeron los primeros ID de enlace;

construir unos segundos ID de trayecto para cada uno de los trayectos de igual coste, cada uno de los segundos ID de trayecto que se crea concatenando los segundos ID de enlace de la pluralidad de enlaces que forman ese trayecto a través de la red de comunicación; y

clasificar los segundos ID de trayecto para seleccionar un segundo conjunto de trayectos diversos a través de la red de comunicación.

Método y aparato para seleccionar entre múltiples trayectos de Igual coste Campo técnico

La presente invención se refiere a redes de comunicación y, más particularmente, a un método y aparato para seleccionar entre múltiples trayectos de igual coste.

Antecedentes

Las redes de comunicación de datos pueden incluir diversos ordenadores, servidores, nodos, encaminadores, conmutadores, puentes, concentradores, intermediarios y otros dispositivos de red acoplados juntos y configurados para pasar datos unos a otros. Estos dispositivos se conocerán en la presente memoria como "elementos de red". Los datos se comunican a través de la red de comunicación de datos pasando unidades de datos de protocolo, tales como tramas de datos, paquetes, celdas o segmentos, entre los elementos de red utilizando uno o más enlaces de comunicación. Una unidad de datos de protocolo particular se puede manejar por múltiples elementos de red y puede cruzar múltiples enlaces de comunicación según viaja entre su origen y su destino sobre la red.

Los diversos elementos de red en la red de comunicación comunican unos con otros usando conjuntos de reglas predefinidas, conocidas en la presente memoria como protocolos. Se usan diferentes protocolos para gobernar diferentes aspectos de la comunicación, tales como cómo se deberían formar las señales para transmisión entre elementos de red, diversos aspectos de qué unidades de datos de protocolo deberían ser similares, cómo se deberían manejar o encaminar los paquetes a través de la red por los elementos de red y cómo se debería intercambiar información asociada con información de encaminamiento entre los elementos de red. Redes que usan diferentes protocolos operan de manera diferente y se consideran que son diferentes tipos de redes de comunicación. Una red de comunicación dada puede usar múltiples protocolos en diferentes capas de red para permitir a los elementos de red comunicar unos con otros a través de la red.

En redes de comunicación de reenvío de paquetes, un nodo puede aprender acerca de la topología de la red y puede decidir, sobre la base del conocimiento que adquiere de la topología, cómo encaminará el tráfico a cada uno de los otros nodos de red. Frecuentemente, la base principal para seleccionar un trayecto es el coste del trayecto, que se puede especificar en términos de un número de saltos entre nodos o por alguna otra métrica tal como el ancho de banda de enlaces que conectan nodos o ambos. El Trayecto Más Corto Abierto Primero (OSPF) y Sistema Intermedio a Sistema Intermedio (IS-IS) son protocolos de estado de enlace ampliamente usados que establecen los trayectos más cortos en base a cada anuncio del nodo del coste de trayecto.

Se pueden usar diversos algoritmos de trayecto más corto para determinar si un nodo dado está en el trayecto más corto entre un par de puentes dados. Un algoritmo de trayecto más corto de todos los pares tal como el algoritmo de Floyd o el algoritmo de trayecto más corto de origen único de Dijkstra se puede implementar por los nodos para calcular el trayecto más corto entre pares de nodos. Se debería entender que también se podría utilizar cualquier otro algoritmo de trayecto más corto adecuado. La métrica de enlace usada por el algoritmo de trayecto más corto puede ser modificada estática o dinámicamente para tener en cuenta la información de ingeniería de tráfico. Por ejemplo, la métrica de enlace puede incluir una medida del coste tal como la capacidad, velocidad, uso y disponibilidad.

Hay situaciones donde existen múltiples trayectos de igual coste a través de una red entre un par de nodos dados. ISIS y OSPF usan un proceso de desempate unidireccional simplista para seleccionar entre estos múltiples trayectos de igual coste o solo extender tráfico a través de los trayectos de igual coste. Los algoritmos de extensión no están especificados y pueden variar de encaminador a encaminador. Alternativamente, cada encaminador puede hacer una selección local de un único trayecto, pero sin consideración de la coherencia con la selección hecha por otros encaminadores. Consecuentemente, en cualquiera de los casos, la dirección inversa de un flujo no está garantizada usando el trayecto usado por la dirección directa. Esto es suficiente para reenvío unidifusión donde cada dispositivo tendrá una tabla de reenvío completa para todos los destinos y acepta promiscuamente paquetes a todos los destinos en todas las interfaces. No obstante, esto no funciona bien en otras situaciones tales como encaminamiento multidifusión, cuando se deben tomar decisiones coherentes y cuando se requiere simetría bidireccional para permitir a los trayectos de reenvío reales en una red estable presentar propiedades orientadas a conexión.

Los protocolos de encaminamiento multidifusión tales como Trayecto Más Corto Abierto Mutidifusión Primero (MOSPF) dependen de cada encaminador en una red que construye el mismo árbol de trayecto más corto. Por esta razón, MOSPF implementa un esquema de desempate basado en el tipo de enlace, LAN frente a punto a punto e identificador del encaminador, para asegurar que se producen árboles idénticos. No obstante, basar la decisión de desempate en el padre con el identificador más grande implica que los trayectos usados por los flujos inversos no pueden ser los mismos que los trayectos usados por los flujos directos.

Hay un requisito en algunos protocolos emergentes, tales como Puenteo de Estado de Enlace de Proveedor (PLSB) que está siendo definido por el Instituto de Ingenieros Eléctricos y Electrónicos (IEEE) como el estándar propuesto 82.1 aq, para conservar la congruencia bidireccional de reenvío a través de la red tanto para tráfico unidifusión

como multidifusión, de manera que el tráfico usará un trayecto común tanto en las direcciones de flujo directo como inverso. Por consiguiente, es importante que los nodos lleguen coherentemente a la misma decisión cuando hay un desempate entre trayectos de igual coste y que el proceso de desempate sea independiente de cuyo nodo es la raíz para un cálculo dado. Además, es deseable que un nodo pueda realizar el desempate con una cantidad mínima de esfuerzo de procesamiento.

Generalmente, cualquier algoritmo de desempate debería ser completo, lo cual significa que debe ser capaz siempre de elegir entre dos trayectos. Adicionalmente, el algoritmo de desempate debería ser asociativo conmutativo, simétrico y local. Estas propiedades se exponen más adelante en la Tabla I:

TABLA I

La esencia del algoritmo de desempate es que `funcione siempre. No importa con qué conjunto de trayectos se presente el algoritmo, el algoritmo debería ser capaz siempre de elegir uno y solamente un trayecto. Primero y ante todo, el algoritmo de desempate por lo tanto debería ser completo. Para un desempate coherente, el algoritmo debe producir los mismos resultados con independencia del orden en el que se descubren los trayectos de igual coste y se realiza el desempate. Es decir, el algoritmo de desempate debería ser conmutativo y asociativo. El requisito de que el desempate entre tres trayectos deba producirlos mismos resultados con independencia del orden en que se consideran los pares de trayectos no es tan obvio y aún es absolutamente necesario para resultados coherentes según se descubren trayectos de igual coste en órdenes diferentes dependiendo de la dirección del cálculo a través de la red. El algoritmo de desempate también debe ser simétrico, es decir, el algoritmo de desempate debe producir el mismo resultado con independencia de la dirección del trayecto: el trayecto más corto entre dos nodos A y B debe ser el inverso del trayecto más corto entre B y A.

Finalmente, la localidad es una propiedad muy importante de los trayectos más cortos que se explota por los sistemas de encaminamiento. La propiedad de localidad simplemente dice que: un subtrayecto de un trayecto más corto también es un trayecto más corto. Esta propiedad aparentemente trivial de los trayectos más cortos tiene una importante aplicación en redes por paquetes... [Seguir leyendo]

1. Un aparato para seleccionar entre múltiples trayectos de igual coste en una red de comunicación (1), el aparato que incluye uno o más procesadores y una o más memorias, la una o más memorias que contienen datos e instrucciones que, cuando se cargan en el uno o más procesadores configuran el aparato para realizar un método de selección entre los múltiples trayectos de igual coste, el método que incluye los pasos de:

determinar un conjunto de trayectos de igual coste entre un par de nodos (11-18) en una red de comunicación, cada trayecto que incluye una pluralidad de enlaces;

caracterizado por que el método además incluye los pasos de:

construir unos primeros ID de enlace para cada enlace en cada uno de los trayectos de igual coste, cada uno de los primeros ID de enlace que se crea concatenando los ID de nodo ordenados de nodos que conectan con el enlace en

la red;

construir unos primeros ID de trayecto para cada uno de los trayectos de igual coste, cada uno de los primeros ID de trayecto que se crea concatenando los primeros ID de enlace de la pluralidad de enlaces que forman ese trayecto a través de la red de comunicación;

clasificar los primeros ID de trayecto para seleccionar un primer conjunto de trayectos diversos a través de la red de

comunicación;

construir unos segundos ID de enlace para cada enlace en los trayectos de igual coste, cada uno de los segundos ID de enlace que se crea concatenando un ID de nodo de uno de los nodos que conecta con el enlace en la red con un ID de nodo invertido del otro de los nodos que conecta con ese enlace en la red, los ID de nodo que se concatenan para formar los segundos ID de enlace en el mismo orden que se determinó cuando se construyeron los primeros ID de enlace;

construir unos segundos ID de trayecto para cada uno de los trayectos de igual coste, cada uno de los segundos ID de trayecto que se crea concatenando los segundos ID de enlace de la pluralidad de enlaces que forman ese trayecto a través de la red de comunicación; y

clasificar los segundos ID de trayecto para seleccionar un segundo conjunto de trayectos diversos a través de la red de comunicación.

2. El aparato de la reivindicación 1, en donde los ID de nodo ordenados concatenados usados para formar los primeros ID de enlace se ordenan de manera que el ID de nodo bajo forma los bits más significativos del ID de enlace y el ID de nodo alto forma los bits menos significativos del ID de enlace.

3. El aparato de la reivindicación 1, en donde el paso de construir los primeros ID de trayecto comprende ordenar los primeros ID de enlace de manera que el orden en el que aparecen los primeros ID de enlace dentro de los primeros ID de trayecto es independiente del trayecto.

4. El aparato de la reivindicación 1, en donde el paso de construir los primeros ID de trayecto para cada uno de los trayectos de igual coste comprende clasificar los ID de enlace desde el más bajo al más alto.

5. El aparato de la reivindicación 1, en donde el paso de clasificar los primeros ID de trayecto comprende ordenar los primeros ID de trayecto desde el más bajo al más alto.

6. El aparato de la reivindicación 5, en donde el primer conjunto de trayectos diversos a través de la red de comunicación son el trayecto con el primer ID de trayecto clasificado más bajo y el trayecto con el primer ID de trayecto clasificado más alto.

7. El aparato de la reivindicación 1, en donde el paso de construir los segundos ID de enlace comprende el paso de aplicar una función de inversión idéntica a uno de los ID de nodo de cada uno de los enlaces para crear los ID de nodo invertidos.

8. El aparato de la reivindicación 7, en donde la función de inversión es una función XOR.

9. El aparato de la reivindicación 7, en donde los ID de nodo ordenados concatenados usados para formar los segundos ID de enlace se ordenan de manera que el ID de nodo bajo forma los bits más significativos del ID de enlace y el ID de nodo alto forma los bits menos significativos del ID de enlace y en donde la función de inversión se aplica al ID de nodo alto.

1. El aparato de la reivindicación 1, en donde el paso de construir los segundos ID de trayecto comprende ordenar los segundos ID de enlace de manera que el orden en el que aparecen los segundos ID de enlace dentro de los segundos ID de trayecto es independiente del orden de los enlaces en el trayecto.

11. El aparato de la reivindicación 1, en donde los segundos ID de enlace se ordenan desde el más bajo al más alto anterior a una concatenación cuando se forman los segundos ID de trayecto.

12. El aparato de la reivindicación 1, en donde el paso de clasificar los segundos ID de trayecto comprende ordenar los segundos ID de trayecto desde el más bajo al más alto.

13. El aparato de la reivindicación 12, en donde el segundo conjunto de trayectos diversos a través de la red de comunicación son los trayectos con el segundo ID de trayecto clasificado más bajo y el segundo ID de trayecto clasificado más alto.

14. El aparato de la reivindicación 1, que además comprende el paso de aplicar una primera función de inversión a todos los ID de nodo antes de crear los primeros y segundos ID de enlace, la primera función de inversión que se selecciona para seleccionar preferentemente un nodo de tránsito en la red a través del cual pasará el primer conjunto de trayectos haciendo el ID de nodo del nodo de tránsito un valor de ID de nodo mínimo.

15. El aparato de la reivindicación 14, en donde el paso de construir los segundos ID de enlace comprende el paso de aplicar una segunda función de inversión a uno de los ID de nodo de cada uno de los enlaces para crear los ID de nodo invertidos para permitir al segundo conjunto de trayectos ser seleccionado que pasa a través del nodo de tránsito y divergen lejos del nodo de tránsito.

16. Una red de comunicación (1), que comprende:

una pluralidad de nodos (11-18) interconectados por enlaces, cada nodo que tiene un ID de nodo y que incluye al menos un procesador y una memoria asociada, la memoria de cada nodo que además contiene datos e instrucciones que, cuando se cargan en el procesador, hacen al nodo implementar un proceso de protocolo de encaminamiento de estado de enlace para permitir al nodo intercambiar información de configuración de la red con los otros nodos en la red y calcular trayectos a través de la red, la memoria de cada nodo que además contiene datos e instrucciones que, cuando se cargan en el procesador, hacen al nodo realizar un método que incluye los pasos de:

determinar un conjunto de trayectos de igual coste entre un par de nodos en una red de comunicación, cada trayecto que incluye una pluralidad de enlaces;

caracterizado por que el método además incluye los pasos de:

construir unos primeros ID de enlace para cada enlace en cada uno de los trayectos de igual coste, cada uno de los primeros ID de enlace que se crea concatenando los ID de nodo ordenados de nodos que conectan con el enlace en la red;

construir unos primeros ID de trayecto para cada uno de los trayectos de igual coste, cada uno de los primeros ID de trayecto que se crea concatenando los primeros ID de enlace de la pluralidad de enlaces que forman ese trayecto a través de la red de comunicación;

clasificar los primeros ID de trayecto para seleccionar un primer conjunto de trayectos diversos a través de la red de comunicación;

construir unos segundos ID de enlace para cada enlace en los trayectos de igual coste, cada uno de los segundos ID de enlace que se crea concatenando un ID de nodo de uno de los nodos que conecta con el enlace en la red con un ID de nodo invertido del otro de los nodos que conecta con ese enlace en la red, los ID de nodo que se concatenan en el mismo orden que se determinó cuando se construyeron los primeros ID de enlace;

construir los segundos ID de trayecto para cada uno de los trayectos de igual coste, cada uno de los segundos ID de trayecto que se crea concatenando los segundos ID de enlace de la pluralidad de enlaces que forman ese trayecto a través de la red de comunicación; y

clasificar los segundos ID de trayecto para seleccionar un segundo conjunto de trayectos diversos a través de la red de comunicación.

17. La red de la reivindicación 16, en donde cada uno de los ID de nodo se asignan administrativamente desde intervalos separados de los ID de nodo según una clasificación de nodo para permitir al primer y segundo conjunto de trayectos diversos divergir en ubicaciones seleccionadas de la red.

18. La red de la reivindicación 17, en donde se asignan los ID de nodo a nodos en un borde de la red a partir de un intervalo bajo y se asignan los ID de nodo a nodos en el interior de la red a partir de un intervalo alto, para hacer al primer y segundo conjunto de trayectos diversos ser un enlace diverso en el borde de la red.

19. La red de la reivindicación 16, en donde el paso de construirlos segundos ID de enlace comprende el paso de aplicar una función de inversión idéntica a uno de los ID de nodo de cada uno de los enlaces para crear los ID de nodo invertidos.

2. La red de la reivindicación 19, en donde los ID de nodo ordenados concatenados usados para formar los segundos ID de enlace se ordenan de manera que el ID de nodo bajo forma los bits más significativos del ID de enlace y el ID de nodo alto forma los bits menos significativos del ID de enlace y en donde la función de inversión se aplica al ID de nodo alto.

21. La red de la reivindicación 16, en donde los ID de nodo de nodos de tránsito se asignan administrativamente de

manera que los nodos de tránsito llegan a ser a su vez puntos de tránsito durante repeticiones sucesivas de la construcción de los primeros y segundos ID de enlace.

22. La red de la reivindicación 21, en donde las funciones de inversión selectivas elegidas para hacer coincidir los ID de nodo asignados administrativamente de los nodos de tránsito se aplica en serie a todos los ID de nodo durante

las iteraciones de los pasos de creación de los primeros y segundos ID de enlace, creando los primeros y segundos ID de trayecto y clasificando los primeros y segundos ID de trayecto, para hacer diferentes trayectos a ser seleccionados a través de cada nodo de tránsito asignado en la red a su vez durante las iteraciones.

23. La red de la reivindicación 22, en donde la función de inversión es una función XOR.