ES2933264T3

ES2933264T3 - Minimización de inundaciones con protocolo de pasarela interior

Info

Publication number: ES2933264T3
Application number: ES18899925T
Authority: ES
Inventors: Huaimo Chen; Dean Cheng
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2018-01-12
Filing date: 2018-12-05
Publication date: 2023-02-03
Anticipated expiration: 2038-12-05
Also published as: CN114629846A; US20230017665A1; KR102606598B1; EP4181528B1; KR20230022265A; EP4075755C0; CN114615198A; KR102496586B1; EP4181528A1; EP3732894A4; EP3732894A1; BR112020014010A2; CN111587580B; KR102397956B1; US11489766B2; KR20200106184A; MX2020007474A; CN111587580A; CN114615198B; EP3732894B1

Abstract

Se divulga un mecanismo para implementar la reducción de inundación de estado de enlace (LSFR) en una red de Protocolo de Pasarela Interior (IGP). El mecanismo incluye recibir datos que indican la conectividad de una pluralidad de nodos en la red. Se construye una topología de inundación basada en la conectividad. Esto incluye seleccionar uno de los nodos como nodo raíz y construir un árbol de enlaces que conectan el nodo raíz con los nodos de la red. La topología de inundación se almacena en una memoria. La topología de inundación puede no ser para los nodos restantes de la red. Los mensajes de estado de enlace pueden luego inundarse sobre la topología de inundación. (Traducción automática con Google Translate, sin valor legal)

Description

DESCRIPCIÓN

Minimización de inundaciones con protocolo de pasarela interior

Campo técnico

La presente divulgación generalmente está relacionada con las redes basadas en el Protocolo de pasarela interior (IGP), y está específicamente relacionada con un mecanismo para crear una topología de inundación separada para soportar la minimización de la inundación de paquetes en una red basada en IGP.

Antecedentes

Ciertas redes emplean información de estado de enlace para enrutar paquetes. En tales redes, cada nodo difunde la información del estado del enlace del nodo a través de la red en mensajes de estado del enlace como parte de un proceso de sincronización. La información del estado del enlace de un nodo incluye datos que identifican el nodo, que indican los vecinos del nodo y que indican la distancia y/o los costos de enrutamiento para ponerse en contacto con dichos vecinos. Cada nodo recibe los mensajes de estado de enlace de los otros nodos y utiliza la información de estado de enlace para llenar una base de datos de estado de enlace. Luego, cada nodo puede usar una base de datos de estado de enlace correspondiente para determinar las rutas más cortas para comunicar paquetes de datos con otros nodos. Tales redes sufren ciertos problemas de escalabilidad. Específicamente, cada nodo difunde periódicamente un mensaje de estado del enlace a todos los demás nodos de la red. A medida que se agregan más nodos a la red, se difunden más mensajes de estado de enlace, lo que da como resultado una sobrecarga de señalización cada vez mayor que compite con el tráfico de datos por el ancho de banda.

LI ARISTA NETWORKS T: "An Architecture for Dynamic Flooding on Dense Graphs; draft-li-dynamic-flooding-00.txt", Borrador de Internet: Grupo de trabajo de ingeniería de Internet IETF; STANDARDWo Rk INGDRAFT, Internet Society (ISOC) 4, RUE DES FALAISES CH - 1205, 3 de enero de 2018, páginas 1-8, XP015125002, divulga que se elige un nodo para calcular la topología de inundación para el subgrafo denso. La topología de inundación se codifica y distribuye como parte de la base de datos de estado de enlace normal. Los nodos dentro de la topología densa solo se inundarían en la topología de inundación. En enlaces fuera de la topología de inundación normal, se aplicaría el mecanismo normal de sincronización de la base de datos, pero no la inundación.

Resumen

La presente invención se define en el conjunto adjunto de las reivindicaciones.

Breve descripción de los dibujos

Para una comprensión más completa de esta divulgación, ahora se hace referencia a la siguiente breve descripción, tomada en relación con los dibujos adjuntos y la descripción detallada, en donde los mismos números de referencia representan partes similares.

La Figura 1 es un diagrama esquemático de una red IGP de ejemplo.

La Figura 2 es un diagrama esquemático de una red IGP de ejemplo con una topología de inundación para soportar la reducción de inundación de estado de enlace distribuido (LSFR).

La Figura 3 es un diagrama esquemático de una red IGP de ejemplo con una topología de inundación que emplea una hoja.

La Figura 4 es un diagrama esquemático de un nodo de red de ejemplo para operar en una red IGP.

La Figura 5 es un diagrama de flujo de un método de ejemplo para construir una topología de inundación.

La Figura 6 es un diagrama de flujo de otro método de ejemplo para construir una topología de inundación. La Figura 7 es un diagrama de flujo de otro método de ejemplo para construir una topología de inundación. La Figura 8 es un diagrama esquemático de un mecanismo de inundación de ejemplo.

La Figura 9 es un diagrama esquemático de un mecanismo de inundación de ejemplo empleado al descubrir un nuevo nodo.

La Figura 10 es un diagrama esquemático de un mecanismo de inundación de ejemplo empleado al descubrir que un nodo se ha caído.

La Figura 11 es un diagrama esquemático de otro mecanismo de inundación de ejemplo empleado al descubrir que un nodo se ha caído.

La Figura 12 es un diagrama esquemático de un mecanismo de inundación de ejemplo empleado al descubrir que un enlace se ha caído.

La Figura 13 es un diagrama esquemático de una red IGP de ejemplo con una interfaz crítica en la topología de inundación.

La Figura 14 es un diagrama esquemático de una codificación Abrir primero el camino más corto (OSPF) versión dos (v2) de ejemplo para indicar soporte de nodo para LSFR.

La Figura 15 es un diagrama esquemático de una codificación OSPF versión tres (v3) de ejemplo para indicar soporte de nodo para LSFR.

La Figura 16 es un diagrama esquemático de una codificación de Sistema Intermedio-Sistema Intermedio (IS-IS) de ejemplo para indicar el soporte de nodo para LSFR.

La Figura 17 es un diagrama esquemático de una codificación de valor de longitud de tipo de control (TLV) de LSFR para gestionar LSFR en una red IGP.

La Figura 18 es un diagrama esquemático de un ejemplo de codificación TLV de ejemplo para integrar LSFR centralizado con LSFR distribuida.

La Figura 19 es un diagrama de flujo de un método de ejemplo para operar mecanismos LSFR en una red IGP. La Figura 20 es una modalidad de un dispositivo para operar mecanismos LSFR en una red IGP.

Descripción detallada

Debe entenderse desde el principio que, aunque a continuación se proporciona una implementación ilustrativa de una o más modalidades, los sistemas y/o métodos divulgados pueden implementarse mediante el uso de cualquier número de técnicas, ya sea actualmente conocidas o en existencia. La divulgación no debe limitarse de ninguna manera a las implementaciones ilustrativas, dibujos y técnicas ilustrados a continuación, incluidos los diseños ilustrativos e implementaciones ilustrados y descritos en el presente documento, pero puede modificarse dentro del alcance de las reivindicaciones adjuntas junto con su alcance completo de equivalentes.

En la presente descripción se divulgan varios mecanismos para reducir la sobrecarga de señalización relacionada con los mensajes de estado de enlace en las redes IGP, como las redes OSPF y/o IS-IS. La comunicación de mensajes de estado de enlace desde un nodo a todos los demás nodos en un dominio de red se denomina como inundación. Los mecanismos divulgados, denominados colectivamente como LSFR, reducen el impacto de la inundación de mensajes de estado de enlace al generar una topología de inundación que es un subconjunto de la topología de red real. En general, cada nodo inunda la red transmitiendo mensajes de estado de enlace sobre la topología de inundación sin transmitir dichos mensajes a través de enlaces de red que están excluidos de la topología de inundación. Esto permite que el mensaje llegue a todos los demás nodos de la red, al tiempo que minimiza el número de copias redundantes del mensaje recibido en cada nodo. Por ejemplo, la topología de inundación puede generarse como un árbol de enlaces (por ejemplo, un árbol de expansión) que conecta los nodos. Tal árbol de enlaces permite que un mensaje de estado de enlace se inunde en todos los nodos mientras garantiza que cada nodo reciba una sola copia del mensaje inundado. Para una mayor confiabilidad, se pueden agregar hojas al árbol de enlaces según lo indique un administrador de red. Esto agrega algo de redundancia de mensajes, pero aumenta la confiabilidad de la red al proporcionar rutas de mensajes alternativas a través de la topología de inundación en caso de que un enlace o nodo funcione mal. En modo distribuido, cada nodo determina el árbol de inundación empleando un algoritmo común, que puede ser seleccionado por el administrador. Esto permite que cada nodo mantenga una copia de la topología de inundación sin inundar una copia de la topología de inundación en la red, lo que aumentaría la congestión de la red. También se divulga un indicador de reducción de inundaciones (F). El indicador F permite que cada nodo comunique la compatibilidad con LSFR y, por lo tanto, permite que los nodos empleen la topología de inundación mientras mantienen la compatibilidad con versiones anteriores con nodos que no admiten LSFR. El indicador F también permite que los nodos que no son LSFR se conecten más lejos de la raíz del árbol de topología de inundación. También se divulgan mecanismos para gestionar la inundación de mensajes de estado de enlace en caso de cambios en la red. Por ejemplo, cuando un nuevo nodo ingresa a la red y se comunica con un nodo vecino que ya está en la topología de inundación, el nodo vecino puede agregar el nuevo nodo a la topología de inundación hasta que se vuelva a calcular la topología de inundación y se construya una nueva topología de inundación. Además, cuando un enlace o nodo funciona mal, un nodo adyacente al que funciona mal puede comunicar mensajes de estado del enlace a otros nodos que están adyacentes a los que funcionan mal a través de enlaces que están excluidos de la topología de inundación para garantizar que dichos nodos continúen recibiendo mensajes de estado del enlace hasta que se soluciona el mal funcionamiento. Además, cada uno de los nodos puede conservar el conocimiento de los elementos críticos. Un elemento crítico es un enlace/interfaz o nodo de topología de inundación que, en caso de falla, divide la topología de inundación en dos o más partes separadas. Tras la notificación de la falla de un elemento crítico, los nodos pueden volver a enviar mensajes de estado de enlace de inundación en todos los enlaces para mantener la funcionalidad de la red hasta que se repare el enlace/nodo o hasta que se pueda calcular una nueva topología de inundación que no incluya el elemento con fallas. Cuando un elemento crítico es un enlace de topología de inundación (o interfaz), el elemento crítico se denomina interfaz crítica o enlace crítico. Cuando un elemento crítico es un nodo de topología de inundación, el elemento crítico se denomina nodo crítico.

La Figura 1 es un diagrama esquemático de una red IGP de ejemplo 100. Una red IGP 100 es una red configurada para intercambiar información de enrutamiento y/o conmutación con base en un protocolo IGP, tal como OSPF y/o IS-IS. La red IGP 100 incluye una pluralidad de nodos 111 interconectados por enlaces 115. Un nodo 111 es un dispositivo de red capaz de recibir un paquete de datos de una fuente en una primera interfaz, determinar el destino del paquete de datos al que se puede llegar a través de una segunda interfaz y reenviar el paquete de datos hacia el destino a través de la segunda interfaz. Para mayor claridad de la descripción, el término paquete de datos como se usa en la presente descripción incluye tanto paquetes de datos como tramas de datos. Un enlace 115 es un medio capaz de propagar una señal desde una interfaz de un primer nodo 111 a una interfaz de un segundo nodo 111.

Los nodos 111 están interconectados para formar un dominio de red 110. Como se usa en la presente descripción, un dominio de red 110 es un grupo de nodos interconectados 111 que comparten esquemas, políticas y/o protocolos de direccionamiento de red. Específicamente, los nodos 111 del dominio de red 110 emplean un protocolo de enrutamiento de estado de enlace. Cuando se emplea un protocolo de enrutamiento de estado de enlace, cada nodo 111 en el dominio de red 110 mantiene una topología de red completa (por ejemplo, una tabla de enrutamiento) y determina de forma independiente los siguientes saltos para paquetes de datos empleando información almacenada localmente relacionada con la topología de red. La topología de red incluye datos que indican la estructura de la red IGP 100, como conexiones de nodo 111 y enlace 115, adyacencias de nodo 111, información de interfaz de nodo 111 y/u otra información de relación de enlace 115/nodo 111.

Los nodos 111 comparten información de estado de enlace a través del dominio de red 110. La información de estado de enlace para un nodo 111 incluye datos que identifican el nodo 111 (por ejemplo, la dirección del nodo 111), una lista de los de los nodos 111 vecinos y costos/retrasos entre el nodo 111 y los nodos 111 vecinos. Los nodos 111 son vecinos cuando están separados por un solo enlace 115. Para compartir información de estado de enlace, los mensajes de estado de enlace de inundación de los nodos 111 a través del dominio de red 110. En OSPF, los mensajes de estado de enlace se conocen como anuncios de estado de enlace (LSA). En IS-IS, los mensajes de estado de enlace se conocen como unidades de datos de protocolo de estado de enlace (LSP). En algunos ejemplos, cada nodo 111 inunda mensajes de estado de enlace en todas las interfaces. Como se usa en la presente descripción, la inundación indica la transmisión simultánea de un paquete/trama en un conjunto predefinido de interfaces de red. Tal enfoque puede crear problemas a medida que aumenta el tamaño de la red IGP 100. Por ejemplo, cuando cada nodo 111 envía periódicamente un mensaje de estado de enlace a todos los demás nodos 111 a través de todas las interfaces, el tráfico de red relacionado con los datos de estado de enlace puede aumentar drásticamente a medida que se agregan más nodos 111 a la red IGP 100. Además, cada nodo 111 puede recibir un mensaje de estado de enlace para cada uno de los demás nodos 111 en todas las interfaces. Esto puede dar como resultado que cada nodo 111 reciba múltiples mensajes de estado de enlace redundantes. La presente divulgación modifica los protocolos empleados por los nodos 111 en el dominio de red 110 para reducir los mensajes de estado de enlace redundantes. El proceso de reducción de la comunicación de mensajes de estado de enlace redundantes se denomina en la presente descripción reducción de inundación de estado de lista (LSFR). Específicamente, los nodos 111 se modifican para generar y mantener una topología de inundación que es un subconjunto de la topología de red IGP 100. Los mensajes de estado de enlace se inundan sobre la topología de inundación en lugar de sobre toda la topología de la red IGP 100. Este enfoque reduce la comunicación de mensajes de estado de enlace redundantes, lo que aumenta la escalabilidad de la red IGP 100. Además, la reducción del tráfico de mensajes de estado de enlace reduce la señalización de mantenimiento de red general y, por lo tanto, aumenta la capacidad de comunicación de los nodos 111 para el tráfico de datos. La Figura 2 es un diagrama esquemático de una red IGP 200 de ejemplo con una topología de inundación 219 para admitir la LSFR distribuida. Por ejemplo, la red IGP 200 puede emplearse para implementar LSFR en una red IGP 100. La red IGP 200 incluye nodos 211, un nodo raíz 212 y un primer nodo 213, que puede ser sustancialmente similar a los nodos 111 en la red IGP 100. Un nodo raíz 212 es un nodo 211 seleccionado como raíz para un árbol de expansión empleado como topología de inundación 219. Un primer nodo 213 es un nodo 211 y está diferenciado para apoyar la claridad de la descripción cuando se describe el esquema LSFR descrito en la presente descripción. La red iGp 200 incluye enlaces de topología de inundación 216 y enlaces 217, que son sustancialmente similares a los enlaces 115. Los enlaces de topología de inundación 216, representados en negrita, son enlaces incluidos en la topología de inundación 219 y, por lo tanto, se emplean para transmitir mensajes de estado de enlace. Los enlaces 217, representados sin negrita, no están incluidos en la topología de inundación 219, y solo conducen mensajes de estado de enlace en ciertos casos particulares como se describe con respecto a las Figuras a continuación.

La red IGP 200 puede operar en un modo distribuido. En modo distribuido, cada nodo 211, 212 y 213 genera una topología de inundación 219 después de que se detecta un cambio en la red. La topología de inundación 219 es un árbol de enlaces de topología de inundación 216 empleados para transmitir mensajes de estado de enlace. Los nodos 211, 212 y 213 emplean el mismo algoritmo para generar la topología de inundación 219. En consecuencia, cada nodo 211, 212 y 213 almacena la topología de inundación 219 en la memoria local sin transmitir los datos de inundación que indican la topología de inundación 219 a los nodos restantes en la red IGP 200. De esta manera, los datos que indican la topología de inundación 219 no se envían a todos los nodos 211. La topología de inundación 219 se puede generar de acuerdo con varios algoritmos como se describe con respecto a las Figuras a continuación.

Cada nodo 211, 212 y 213 puede generar una topología de inundación 219 después de recibir datos que indican la conectividad de los nodos 212, 211 y/o 213 en la red IGP 200 en cada nodo 211, 212 y 213. La recepción/envío de datos puede producirse sobre una topología de inundación preexistente 219 y/o mediante inundación general si no existe una topología de inundación preexistente 219. Cada nodo 211, 212 y 213 puede construir una copia de la topología de inundación 219 empleando un algoritmo seleccionado. Por ejemplo, uno de los nodos de la red IGP 200 se selecciona como nodo raíz 212. Se puede seleccionar un nodo raíz 212 de los nodos 211/213 mediante muchos mecanismos. Por ejemplo, el nodo raíz 212 se puede seleccionar de los nodos 211/213 como el nodo con el identificador (ID) más grande o más pequeño, la dirección de protocolo de Internet (IP), la dirección de control de acceso al medio (MAC), etc. Una vez seleccionado el nodo raíz 212, se construye un árbol de enlaces de topología de inundación 216 de modo que el árbol de enlaces de topología de inundación 216 conecta el nodo raíz 212 con los nodos en la red. Por ejemplo, la topología de inundación 219 puede construirse como un árbol de expansión y/o un árbol de expansión de peso mínimo. Un árbol de expansión es un subconjunto de un gráfico, donde todos los vértices (nodos 211, 212 y 213) están conectados a través de un número mínimo de bordes (enlaces 216). Un árbol de expansión de peso mínimo es un subconjunto de un gráfico, donde todos los vértices (nodos 211, 212 y 213) están conectados mediante un peso de borde mínimo (por ejemplo, costo de enlace en términos de latencia). Un árbol de topología de inundación 219 con un nodo raíz 212 se puede calcular en O(N), donde O(N) es una notación O grande que indica un tiempo de cálculo lineal basado en la entrada (por ejemplo, número de nodos).

Una topología de inundación 219 es una topología de subred de la topología de red IGP 200 que cumple varios criterios. Primero, la topología de inundación 219 proporciona una accesibilidad equivalente a todos los nodos en la subred como en la red real (por ejemplo, la red IGP 200). Segundo, cuando fallan n (n>0) enlaces 216, la accesibilidad a todos los nodos (por ejemplo, los nodos 211, 212 y 213) en la subred debe ser la misma que en la red real. Tercero, cuando fallan m (m>0) nodos, la accesibilidad a todos los nodos activos en la subred debe ser la misma que en la red real. Cuarto, el número de enlaces de topología de inundación 216 en la topología de inundación 219 debe minimizarse para reducir la inundación de estado de lista.

Una vez que se genera la topología de inundación 219, los nodos 211, 212 y 213 pueden inundar mensajes de estado de enlace, como OSPF LSA y/o IS-IS LSP, sobre la topología de inundación 219. La topología de inundación 219 está diseñada para interactuar con la red IGP 200 empleando varios criterios cuando se inundan mensajes de estado de enlace. Por ejemplo, los mensajes de estado de enlace utilizan tanto la topología de inundación 219 como la topología de red IGP 200 real. Además, la topología de inundación 219 y los mecanismos de inundación asociados deberían admitir mensajes de estado de enlace de inundación (por ejemplo, mensaje de estado de enlace 221) a cada nodo 211, 212 y/o 213 en la red IGP 200 en muchos casos, que se describen en mayor detalle con respecto a las figuras a continuación. Por ejemplo, los mecanismos de inundación deberían permitir que los mensajes de estado del enlace lleguen a todos los nodos 211, 212 y/o 213 cuando n (n > 1) nodos están inactivos (por ejemplo, falla de nodo). Como otro ejemplo, los mecanismos de inundación deberían permitir que los mensajes de estado del enlace lleguen a todos los nodos 211, 212 y/o 213 cuando m (m > 1) enlaces están inactivos (por ejemplo, fallo de enlace/interfaz). Los mecanismos de inundación deberían cumplir tales criterios al mismo tiempo que reducen (por ejemplo, casi minimizan) la inundación de mensajes de estado de enlace. Además, los mecanismos de inundación deben ser compatibles con versiones anteriores para operar con una topología de inundación 219 que comprende los nodos 211,212 y/o 213 que admiten LSFR y nodos que no son compatibles con LSFR. La compatibilidad se describe con más detalle con respecto a las figuras a continuación. Generalmente, los nodos incapaces se posicionan en la topología de inundación 219, pero lejos del nodo raíz 212. Los nodos incapaces pueden entonces recibir mensajes de estado de enlace desde la topología de inundación 219 e inundarlos a través de todas las interfaces.

Para fines de ilustración, se describe un mecanismo de inundación de mensajes de estado de enlace sobre la topología de inundación 219 desde la perspectiva del primer nodo 213. Como se usa en la presente descripción, el término primer nodo 213 denota un nodo 211 seleccionado arbitrariamente de la red IGP 200 para mayor claridad de la descripción. Un primer nodo 213 puede recibir un mensaje de estado de enlace 221, por ejemplo, desde el nodo raíz 212 a través de uno o más enlaces 216. El mensaje de estado de enlace 221 puede ser un LSA, un LSP u otro paquete/trama que transporte información de estado de enlace. El mensaje de estado del enlace 221 puede contener datos de conectividad, como el ID del nodo de origen 211/212, la adyacencia del nodo 211/212, los ID del enlace 216/217, información de la interfaz (por ejemplo, datos del puerto) y/o información del estado del enlace/nodo, como costo del enlace 216/217 (por ejemplo, latencia). El primer nodo 213 recibe el mensaje de estado del enlace 221 a través de un enlace de topología de inundación 216. El primer nodo 213 describe y almacena datos del mensaje de estado de enlace 221 cuando dicha información es más nueva que los datos almacenados localmente. El primer nodo 213 luego reenvía el mensaje de estado de enlace 221 sobre los enlaces de topología de inundación 216 de la topología de inundación 219 hacia los nodos vecinos 211. El mensaje de estado de enlace 221 no se inunda de nuevo a través de la interfaz desde la que se recibió el mensaje de estado de enlace 221 (por ejemplo, de vuelta hacia el nodo raíz 212). Como se muestra, el mensaje de estado del enlace 221 generalmente no se inunda a través de los enlaces 217 que están fuera de la topología de inundación 219 en ausencia de casos particulares como se describe con más detalle con respecto a las Figuras a continuación. Por lo tanto, la inundación del estado del enlace se logra de acuerdo con la topología de inundación 219. Como la topología de inundación 219 conecta todos los nodos 211, 212 y 213, cada nodo en la red IGP 200 recibe una copia del mensaje de estado de enlace 221 y actualiza la información de estado de enlace local (por ejemplo, en una tabla de enrutamiento). Sin embargo, debido a que el mensaje de estado del enlace 221 generalmente no se inunda a través de los enlaces 217, los nodos 211, 212 y 213 generalmente no reciben copias redundantes del mensaje de estado del enlace 221. Como tal, la inundación del mensaje de estado de enlace 221 se reduce de manera que cada nodo 211, 212 y 213 recibe una única copia del mensaje de estado de enlace 221 en lugar de una copia en cada interfaz.

En general, limitar la inundación del mensaje de estado del enlace 221 a la topología de inundación 219 da como resultado varias ventajas. Por ejemplo, los mecanismos de inundación descritos en la presente descripción reducen el tráfico total de la red y, por lo tanto, mejoran el rendimiento de la red. Además, los mecanismos de inundación descritos en la presente descripción mejoran la convergencia de la red, ya que la topología de inundación 219 se calcula en cada nodo en modo distribuido. Además, los mecanismos de inundación descritos en la presente descripción pueden reducir los requisitos de configuración en comparación con otros mecanismos de inundación de estado de enlace.

Cabe señalar que se puede diseñar cierta redundancia en la red IGP 200 para proteger contra fallos del equipo. Específicamente, se pueden agregar enlaces adicionales 216 a la topología de inundación 219 para mitigar los posibles problemas de comunicación de la red IGP 200. En tal caso, algunos nodos 211, 212, 213 pueden recibir más de un mensaje de estado de enlace 221. En consecuencia, LSFR se puede equilibrar con más confiabilidad con base en los mensajes de estado de enlace redundantes. A continuación, se describe un mecanismo para aumentar la fiabilidad de la topología de inundación 219.

La Figura 3 es un diagrama esquemático de una red IGP 300 de ejemplo con una topología de inundación 319 que emplea un enlace de hoja 318, que puede emplearse para aumentar la confiabilidad de la red. La red IGP 300 es sustancialmente similar a la red IGP 200, pero contiene un enlace de hoja adicional 318 en la topología de inundación 319. Como tal, la red IGP 300 contiene un nodo raíz 312, nodos 311, enlaces 317 y una topología de inundación 319 que contiene enlaces de topología de inundación 316, que son sustancialmente similares al nodo raíz 212, nodos 211/213, enlaces 217, topología de inundación 219, y enlaces de topología de inundación 216, respectivamente.

Un enlace de hoja 318 es un enlace añadido a la topología de inundación 319 para admitir la fiabilidad de la red IGP 300. El enlace de hoja 318 se muestra como una línea discontinua en negrita. Con el enlace de hoja 318 agregado a la topología de inundación 319 (por ejemplo, creando un círculo), algunos de los enlaces 316/317 a los nodos 311/312 podrían funcionar mal sin causar que otros nodos 311/312 se separen del árbol de enlaces de topología de inundación 316. Sin embargo, agregar el enlace de hoja 318 puede hacer que uno de los nodos de punto final 311/312 del enlace de hoja 318 reciba un mensaje de estado de enlace redundante. Como tal, la fiabilidad de la red IGP 300 aumenta a costa de una sobrecarga de señal ligeramente mayor.

La adición de un enlace de hoja 318 puede producirse durante el proceso de construcción de la topología de inundación 319. Por ejemplo, un administrador del sistema puede seleccionar un número de enlaces de hoja 318 para agregar a la topología de inundación 319. Tal selección puede transmitirse a todos los nodos 311/312 en la red IGP 300. En consecuencia, cada nodo 311/312 recibe la solicitud, que especifica el número de enlaces de hoja 318 para agregar al árbol de enlaces de topología de inundación 316 en la topología de inundación 319. Cada nodo 311/312 puede construir la topología de inundación 319 con base en la información de conectividad como se describió anteriormente. Antes de agregar los enlaces de hoja 318, el árbol de enlaces 316 en la topología de inundación 319 puede contener un número mínimo de enlaces para conectar todos los nodos 311 en la red IGP 300 al nodo raíz 312. Después de generar la topología de inundación 319, los nodos 311/312 agregan a la topología de inundación 319 un número de enlaces de hoja 318 k (k> = 0) como se especifica en la solicitud del administrador del sistema. Los enlaces de hoja 318 se añaden entre los nodos 311/312 en la red IGP 300 para aumentar la fiabilidad. Los enlaces de hoja 318 se pueden colocar con base en varios mecanismos. Por ejemplo, cualquier enlace de topología de inundación 316 o nodo 311/312 que dividiría la topología de inundación 319 en múltiples árboles/partes en caso de falla puede designarse como un elemento crítico. Los enlaces de hoja 318 pueden colocarse en posiciones seleccionadas para minimizar el número de elementos críticos en la red IGP 300. Los mecanismos adicionales de colocación del enlace de hoja 318 se describen a continuación.

Por ejemplo, la topología de inundación 319, designada Ft, puede construirse mediante uno de los mecanismos descritos con respecto a las Figuras 5-7. En tal caso, la topología de inundación 319 puede adoptar la forma de un árbol. A continuación, se puede añadir al árbol un número entero de enlaces de hoja 318 k (k>=0) para crear una topología de inundación mejorada 319 con mayor conectividad. Por ejemplo, puede haber m (m > 0) enlaces 317 conectados directamente a un nodo X en la topología de inundación 319. Se puede seleccionar un número k de enlaces de hoja 318, donde k <= m, por ejemplo, usando un algoritmo o regla determinista. Un algoritmo o regla puede incluir la selección de k enlaces de hoja 318 que tengan los ID más pequeños o más grandes de los enlaces 317 que no están actualmente conectados a la topología de inundación 319. (por ejemplo, los ID de los extremos que no son hojas de estos enlaces k son más pequeños o más grandes que los ID de los otros enlaces conectados directamente al nodo X). Cada nodo puede tener un ID único. Por lo tanto, seleccionar k enlaces de hoja con ID más pequeños o más grandes de estos extremos que no son de hoja de enlaces es determinista. Como ejemplo específico, si k = 1 bajo este algoritmo, el enlace de hoja 318 seleccionado tiene el ID más pequeño/más grande entre los ID de todos los extremos que no son de hoja de los enlaces conectados directamente al nodo X.

En otro mecanismo de ejemplo, un primer nodo L puede conectarse directamente a un segundo nodo N en la topología de inundación 319 Ft. Se puede seleccionar una conexión/adyacencia a un tercer nodo desde el primer nodo L como un enlace de hoja 318 en Ft usando una regla o algoritmo determinista. Por ejemplo, un primer nodo L puede conectarse directamente a terceros nodos Ni (i = 1,2,...,s) en la topología de inundación 319 Ft a través de adyacencias. Además, los terceros nodos Ni no son el segundo nodo N, IDi es el ID de los terceros nodos Ni y Hi (i = 1,2,...,s) es el número de saltos desde el primer nodo L hasta los terceros nodos Ni en la topología de inundación 319 Ft. Un algoritmo o regla es seleccionar la conexión al tercer nodo Nj (1 <= j <= s) como un enlace de hoja 318 de manera que Hj sea el mayor entre HI, H2,..., Hs. Si hay otro tercer nodo Na (1 <= a <= s) y Hj = Ha, entonces seleccionar el tercer nodo con el ID de nodo más pequeño (o más grande). Específicamente, si Hj es igual a Ha e IDj <IDa, entonces seleccionar la conexión al tercer nodo Nj seleccionando el enlace con ID más pequeño (o si Hj == Ha e IDj <IDa entonces seleccionar la conexión a Na para seleccionar el un ID con ID de nodo más grande).

Con fines ilustrativos, el número de conexiones en total entre los nodos L seleccionados y los nodos en la topología de inundación 319 Ft que se agregarán como enlaces de hoja 318 se puede denotar como NLc. El número de enlaces de hoja 318 NLc se puede limitar programáticamente. En un ejemplo, NLc está configurado en un número específico, como diez, lo que indica que se pueden seleccionar como máximo diez conexiones entre un nodo hoja L y nodos en la topología de inundación 319 Ft y agregarse a la topología de inundación 319 Ft para generar una mejora de topología de inundación 319 Ft. En otro ejemplo, NLc se configura en un porcentaje específico del número de nodos 311/312 en la red (por ejemplo, cinco por ciento), lo que indica que el número de conexiones entre los nodos hoja y los nodos en Ft a seleccionar y agregar a la Ft es como máximo el cinco por ciento del número de nodos 311/312 en la red IGP 300. Por ejemplo, para una red con mil nodos 311/31, el cinco por ciento de mil es cincuenta. Por lo tanto, como máximo cincuenta enlaces de hoja 318 entre los nodos hoja L y los nodos en la topología de inundación 319 Ft se seleccionan y se agregan a la topología de inundación 319 Ft.

La Figura 4 es un diagrama esquemático de un nodo de red de ejemplo 400 para operar en una red IGP, como un nodo en la red IGP 100, 200 y/o 300. Por ejemplo, el nodo de red 400 puede emplearse para implementar los nodos 111, 211, 212, 213, 311 y/o 312. Además, el nodo de red 400 puede emplearse para calcular una topología de red 219 y/o 319. El nodo de red 400 también puede recibir, procesar y reenviar mensajes de estado de enlace, como LSA o LSP (por ejemplo, mensajes de estado de enlace 221), sobre tales topologías de inundación para implementar la LSFR. Por lo tanto, el nodo de red 400 es adecuado para implementar los ejemplos/modalidades descritos en la presente descripción. El nodo de red 400 comprende puertos de recepción 420, puertos de envío 450 y/o unidades transceptoras (Tx/Rx) 410, incluidos transmisores y/o receptores para comunicar datos de subida y/o bajada a través de una red. El nodo de red 400 también incluye un procesador 430 que incluye una unidad lógica y/o una unidad central de procesamiento (CPU) para procesar los datos y una memoria 432 para almacenar los datos. El nodo de red 400 también puede comprender componentes de óptico a eléctrico (OE), componentes de eléctrico a óptico (EO) y/o componentes de comunicación inalámbrica acoplados a los puertos de envío 450 y/o puertos de recepción 420 para la comunicación de datos a través de Redes de comunicaciones ópticas o inalámbricas. El nodo de red 400 también puede incluir dispositivos de entrada y/o salida (E/S) para comunicar datos hacia y desde un usuario en algunos casos.

El procesador 430 está implementado por hardware y software. El procesador 430 puede implementarse como uno o más chips de CPU, núcleos (por ejemplo, como un procesador multinúcleo), matrices de puertas programables en campo (FPGA), circuitos integrados de aplicación específica (ASIC) y procesadores de señales digitales (DSP). El procesador 430 está en comunicación con los puertos de flujo descendente 420, Tx/Rx 410, los puertos de flujo ascendente 450 y la memoria 432. El procesador 430 comprende un módulo LSFR 414. El módulo LSFR 414 implementa las modalidades divulgadas descritas en la presente descripción. Específicamente, el módulo LSFR 414 puede construir una topología de inundación con base en información de conectividad. El módulo LSFR 414 puede construir la topología de inundación empleando varios mecanismos, tales como los métodos 500, 600 y/o 700 como se describe a continuación. El módulo LSFR 414 también puede agregar varios enlaces de hoja a la topología de inundación según lo indique un usuario/administrador del sistema. El módulo LSFR 414 puede almacenar la topología de inundación en la memoria 432. El módulo LSFR 414 puede recibir y/o inundar mensajes de estado de enlace, como OSPF LSA y/o IS-IS LSP, a través de una red IGP a través de la topología de inundación empleando los puertos de recepción 420, Tx/Rx 410 y/o puertos ascendentes 450. El módulo LSFR 414 también puede emplear el manejo específico del caso de los mensajes de estado del enlace como se describe con respecto a las Figuras abajo. Por ejemplo, el módulo LSFR 414 puede agregar nuevos nodos a la topología de inundación al iniciarse, así como enviar mensajes de estado de enlace fuera de la topología de inundación en caso de fallas de enlace/nodo. El módulo LSFR 414 también puede mantener el conocimiento de los elementos críticos y volver a la inundación general de mensajes de estado del enlace en caso de falla de un elemento crítico. Estos y otros mecanismos implementados por el módulo LSFR 414 se describen con más detalle con respecto a las Figuras abajo. Además, el módulo LSFR 414 efectúa una transformación del nodo de red 400 a un estado diferente. Alternativamente, el módulo LSFR 414 puede implementarse como instrucciones almacenadas en la memoria 432 y ejecutadas por el procesador 430 (por ejemplo, como un producto de programa de ordenador almacenado en un medio no transitorio).

La memoria 432 comprende uno o más tipos de memoria tales como discos, unidades de cinta, unidades de estado sólido, memoria de solo lectura (ROM), memoria de acceso aleatorio (RAM), memoria flash, memoria ternaria de contenido direccionable (TCAM), memoria estática de acceso aleatorio (SRAM), etc. La memoria 432 puede usarse como un dispositivo de almacenamiento de datos de desbordamiento, para almacenar programas cuando tales programas se seleccionan para su ejecución, y para almacenar instrucciones y datos que se leen durante la ejecución del programa. Las Figuras 5, 6 y 7 representan métodos de ejemplo para construir una topología de inundación. Generalmente, construir una topología de inundación incluye 1) seleccionar un nodo R de acuerdo con una regla, tal como el nodo con el ID de nodo más grande/más pequeño; 2) construir un árbol usando R como la raíz del árbol; y 3) conectar k (k>=0) hojas al árbol según se desee para agregar mitigación de fallas del equipo a la topología de inundación. En el modo distribuido, cada uno de los nodos de la red utiliza el algoritmo para generar una topología de inundación y, por lo tanto, la topología de inundación no se distribuye/inunda en la red IGP. A continuación, se describen dos tipos de mecanismos de ejemplo. Un tipo de mecanismo crea un árbol para la topología de inundación sin verificar si los nodos admiten LSFR. Este mecanismo supone que todos los enrutadores del dominio admiten LSFR. Un segundo tipo de mecanismo considera si cada nodo admite LSFR mientras construye un árbol para la topología de inundación. Dichos mecanismos colocan los nodos que admiten LSFR más cerca del nodo raíz para permitir que los nodos que admiten LSFR estén continuamente conectados a la topología de inundación. El soporte para LSFR se puede señalar en un indicador F, que se puede incluir en un valor de longitud de tipo de capacidad de enrutador IS-IS (TLV) y/o un OSPF LSA. Por ejemplo, el indicador F puede establecerse en uno para indicar que el nodo/enrutador admite LSFR y establecerse en cero para indicar que el nodo/enrutador no admite LSFR. Luego, el nodo raíz se puede seleccionar de acuerdo con la regla correspondiente, por ejemplo, como el nodo con el ID de nodo más grande/más pequeño que también admite LSFR (por ejemplo, entre los nodos con un indicador F establecido en uno).

La Figura 5 es un diagrama de flujo de un método de ejemplo 500 para construir una topología de inundación, como la topología de inundación 219 y/o 319. En consecuencia, el método 500 puede emplearse por un nodo 111, 211, 212, 213, 311, 312 y/o 400. El método 500 es un mecanismo para construir un árbol a partir de un nodo raíz R con una cola de candidatos (Cq) que inicialmente contiene el nodo R e inicialmente una topología de inundación vacía Ft.

En el bloque 501, se inicia la generación de topología de inundación. Por ejemplo, la topología de inundación se puede volver a calcular cuando hay cambios en la red. Como otro ejemplo, una topología de inundación se puede volver a calcular tras la ocurrencia de un evento. Específicamente, una topología de inundación se puede volver a calcular ante la falla de un elemento crítico. Como otro ejemplo, una topología de inundación se puede volver a calcular al recibir un mensaje de un usuario/administrador del sistema que solicita un nuevo cálculo. Como se indicó anteriormente, en el modo distribuido, el método 500 se inicia sustancialmente de forma simultánea en cada nodo de la red que sea compatible con LSFR.

En el bloque 503, se selecciona un nodo raíz para la topología de inundación, por ejemplo, con base en el número de ID. El nodo raíz seleccionado se agrega a una cola de candidatos vacía. Además, una topología de inundación puede inicializarse como vacía en el bloque 503. El método 500 continúa luego con el bloque 505, que forma un ciclo iterativo con los bloques 507, 511 y 513.

El bloque 505 varía dependiendo de si el método 500 considera qué nodos admiten LSFR. Si el método 500 no considera qué nodos admiten LSFR, el bloque 505 elimina el primer nodo de la cola de candidatos y agrega el nodo eliminado a la topología de inundación. Si el nodo eliminado no es el nodo raíz (por ejemplo, la topología de inundación no se vacía antes de agregar el nodo eliminado), también se incluye en la topología de inundación un enlace entre el nodo eliminado y el último nodo agregado a la topología de inundación. Como tal, el bloque 505 itera a través de la cola de candidatos en orden desde el nodo raíz y posiciona los nodos en la topología de inundación. Si el método 500 considera qué nodos admiten LSFR, el bloque 505 elimina el primer nodo de la cola de candidatos que también admite LSFR. Cuando ningún nodo de la cola de candidatos admite LSFR, el primer nodo de la cola de candidatos (que no admite LSFR) se elimina de la cola de candidatos. El nodo eliminado y el enlace correspondiente al nodo anterior en la topología de inundación, si corresponde, se agregan a la topología de inundación. De esta manera, el bloque 505 puede posicionar nodos que admiten LSFR en posiciones sobre la topología de inundación que están más cerca del nodo raíz. Esto da como resultado el posicionamiento de nodos que no admiten LSFR más lejos del nodo raíz y, por lo tanto, reduce la dependencia de dichos nodos para comunicar datos de estado de enlace a través de la topología de inundación.

En el bloque 507, la lista de nodos de la red se compara con la lista de nodos de la topología de inundación. Cuando se han agregado todos los nodos a la topología de inundación, el método 500 pasa al bloque 509 y devuelve una topología de inundación FT completa. Cuando al menos un nodo no está incluido en la topología de inundación FT, el método 500 pasa al bloque 511.

El bloque 511 varía dependiendo de si el método 500 considera qué nodos admiten LSFR. Si el método 500 no considera qué nodos admiten LSFR, el bloque 511 determina una lista de nodos Xi (i= 1,2,3,... n) conectados al último nodo agregado a la topología de inundación, donde dichos nodos no están ya en la topología de inundación. Dichos nodos Xi pueden clasificarse luego por costo de enlace y/o ID de enlace/nodo/interfaz. El costo del enlace puede indicar la latencia, la longitud del enlace o el ancho de banda máximo del enlace y/u otras capacidades del enlace. Además, el costo del enlace puede indicar un costo entre el último nodo agregado a la topología de inundación y un nodo Xi correspondiente. Tal enfoque puede emplearse para posicionar los nodos Xi con enlaces de menor costo más arriba en la cola de candidatos. Por lo tanto, es más probable que estos enlaces de menor costo se agreguen más cerca del nodo raíz y se utilicen más en la topología de inundación. Cuando el costo es idéntico, puede emplearse el ID de enlace/nodo/interfaz para determinar el orden. Si el método 500 considera qué nodos admiten LSFR, el bloque 511 puede considerar el soporte de LSFR al determinar el costo. Por ejemplo, se pueden emplear métricas reales para determinar los costos de los nodos que admiten LSFR. Además, las métricas reales para los nodos que no admiten LSFR se pueden escalar por un factor de manera que las métricas no LSFR de menor costo sean más altas que las métricas LSFR de mayor costo. Al emplear costos de esta manera, los nodos que no admiten LSFR se posicionan al final de la cola de candidatos. Esto admite aún más la colocación de nodos que no admiten LSFR lo más lejos posible del nodo raíz.

En el bloque 513, los nodos Xi del bloque 511 se agregan al final de la cola de candidatos en el orden clasificado en el bloque 511. El método 500 puede luego volver al bloque 505 para agregar el siguiente nodo de la cola de candidatos a la topología de inundación.

Al emplear el enfoque mencionado anteriormente, la topología de inundación crece como un árbol equilibrado que comienza en el nodo raíz. El nodo raíz se agrega primero a la topología de inundación. Luego, cada uno de los nodos conectados al nodo raíz (por ejemplo, nodos de primer grado) se agregan al árbol de inundación. Luego, cada nodo conectado a los nodos conectados al nodo raíz (por ejemplo, nodos de segundo grado conectados a un nodo de primer grado) se agrega al árbol de inundación. Este proceso continúa hasta que se agregan todos los nodos a la topología de inundación junto con los enlaces correspondientes.

La Figura 6 es un diagrama de flujo de otro método de ejemplo 600 para construir una topología de inundación, como la topología de inundación 219 y/o 319. En consecuencia, el método 600 puede emplearse por un nodo 111, 211,212, 213, 311, 312 y/o 400. El método 600 es un mecanismo para construir un árbol a partir de un nodo raíz R con una cola de candidatos que inicialmente contiene el nodo R e inicialmente una topología de inundación vacía Ft. El método 600 emplea los bloques 601, 603, 605, 607, 609 y 611, que son sustancialmente similares a los bloques 501, 503, 505, 507, 509 y 511, respectivamente. El método 600 también emplea el bloque 613, que es similar al bloque 513. Sin embargo, el bloque 613 añade nodos Xi del bloque 611 al final de la cola de candidatos en lugar de al principio de la cola de candidatos. El método 600 puede considerar si dichos nodos son compatibles con LSFR al clasificar los nodos Xi, o el método 600 puede operar sin considerar la capacidad LSFR (por ejemplo, de una manera sustancialmente similar al método 500).

En consecuencia, el método 600 es sustancialmente similar al método 500, pero el árbol de inundación crece de manera diferente. Específicamente, el árbol crece a lo largo de la primera rama desde el nodo raíz hasta que todos los nodos conectados a la primera rama se agreguen a la topología de inundación. Luego, los nodos unidos a la segunda rama desde el nodo raíz (que aún no se han agregado) se agregan a la topología de inundación, etc. Si se tiene en cuenta la capacidad LSFR, los nodos que no son compatibles con LSFR aún pueden colocarse más adelante en la secuencia debido a la clasificación en el bloque 611.

La Figura 7 es un diagrama de flujo de otro método de ejemplo 700 para construir una topología de inundación como la topología de inundación 219 y/o 319. En consecuencia, el método 700 puede emplearse por un nodo 111, 211, 212, 213, 311, 312 y/o 400. El método 700 es un mecanismo para construir un árbol a partir de un nodo raíz R con una cola de candidatos que inicialmente contiene el nodo R e inicialmente una topología de inundación vacía Ft. El método 700 emplea los bloques 701, 703, 705, 707 y 709, que son sustancialmente similares a los bloques 501, 503, 505, 507 y 509, respectivamente. El método 700 también incluye los bloques 711 y 713, que son similares a los bloques 511 y 513, respectivamente. Sin embargo, los bloques 711 y 713 ordenan los nodos Xi en la cola de candidatos con base en el costo de regreso al nodo raíz en lugar de basarse en el ID o el costo de regreso al nodo anterior en la topología de inundación.

Específicamente, el bloque 711 determina el costo más bajo para el nodo raíz por cada nodo Xi acoplado al último nodo agregado a la topología de inundación en el bloque 705. En ejemplos que consideran la capacidad LSFR, las rutas que atraviesan nodos que no admiten LSFR pueden tener mayores costos asignados para garantizar que dichas rutas se excluyan y/o solo se empleen en la topología de inundación cuando no se disponga de una ruta compatible con LSFR completa. Los nodos Xi acoplados al último nodo agregado a la topología de inundación se agregan a la cola de candidatos junto con los costos más cortos asociados al nodo raíz. En el caso de que un nodo Xi se incluyera previamente en la cola de candidatos durante una iteración anterior debido a la conexión a otro nodo que ya estaba en la topología de inundación, el nuevo costo para el nodo raíz se compara con el costo anterior para el nodo raíz. Luego, el costo se actualiza si el nuevo costo es menor que el costo anterior. Este enfoque hace que cada nodo se considere en la cola de candidatos con base en el costo más bajo hasta el nodo raíz durante cada iteración. Luego, la cola de candidatos se clasifica por costos hasta el nodo raíz y/o con base en el ID de interfaz/nodo/enlace.

En consecuencia, el método 700 es sustancialmente similar al método 500, pero el árbol de inundación crece de manera diferente. Por ejemplo, la topología de inundación del método 700 crece al agregar nodos en orden de costo más bajo hasta el nodo raíz. Este enfoque hace que la topología de inundación se complete principalmente con las rutas de menor costo. Además, las rutas de menor costo se posicionan en la topología de inundación para que dichas rutas se empleen con la mayor cantidad de tráfico de estado de enlace. En consecuencia, las rutas de mayor costo se excluyen o solo se incluyen en la topología de inundación como último recurso para garantizar una conectividad total. Por lo tanto, el uso de dichas rutas de mayor costo y/o el uso de rutas que atraviesan un dispositivo no compatible con LSFR se emplean para la menor cantidad de tráfico de estado de enlace. Emplear una topología de inundación, por ejemplo, la generada de acuerdo con los métodos 500, 600 y 700, puede generar ciertos problemas. Por ejemplo, se pueden emplear ciertos mecanismos para asegurar que cada nodo en la red obtenga una topología de inundación completa en un corto tiempo cuando ocurren cambios en la red, particularmente cuando ocurren fallas de múltiples enlaces o nodos. Un enfoque para mitigar estos problemas es hacer que los nodos mantengan/calculen una topología de inundación redundante. Tal topología de inundación redundante puede incluir una topología de inundación básica para cambios de inundación que excluyen enlaces o nodos descendentes. Además, la topología de inundación redundante puede comprender la información (como rutas de inundación) para un enlace o falla de nodo, así como para múltiples fallas de enlace o nodo. Otro mecanismo que puede emplearse es un mecanismo para dar cuenta de los cambios en el nodo raíz. Por ejemplo, cuando un nodo X descubre que el nodo raíz R utilizado para calcular un árbol de inundación está inactivo o no es accesible, el nodo X selecciona un nuevo nodo raíz R de acuerdo con alguna regla, tal como el nodo con el ID de nodo más grande o más pequeño. El nodo X luego calcula un árbol de inundación como se describió anteriormente y construye la topología de inundación con base en el árbol de inundación (por ejemplo, inmediatamente). Además, cuando se agrega un nuevo nodo a la topología existente y es accesible, el nodo X puede verificar para determinar si el nuevo nodo es una nueva raíz para un árbol de inundación de acuerdo con una regla de selección de nodo raíz, como el ID de nuevos nodos es el nuevo ID de nodo más pequeño/más grande. Si el nuevo nodo es el nuevo nodo raíz, el nodo X calcula un árbol de inundación utilizando el nuevo nodo R como la raíz y construye la topología de inundación con base en el árbol de inundación después de un intervalo de tiempo predefinido, como cinco segundos.

La Figura 8 es un diagrama esquemático de un mecanismo de inundación de ejemplo 800, que puede emplearse en una red IGP, como la red IGP 100, 200 y/o 300. El mecanismo de inundación 800 se emplea con respecto a un primer nodo 813, que puede ser cualquier nodo en una red IGP (por ejemplo, nodo 111, 211, 212, 213, 311, 312 y/o 400) que emplea una topología de inundación, como la topología de inundación 219 y/o 319. Dicha topología de inundación se puede generar, por ejemplo, de acuerdo con el método 500, 600 y/o 700.

Como se muestra con fines de ilustración, el nodo 813 está acoplado a enlaces 817 que están excluidos de la topología de inundación y enlaces 816 que están incluidos en la topología de inundación. Como se indicó anteriormente, un nodo 813 generalmente recibe información de estado de enlace desde una topología de inundación e inunda tal información de estado de enlace sobre otras interfaces acopladas a la topología de inundación. Sin embargo, pueden producirse ciertos casos en los que un nodo 813 recibe información del estado del enlace desde un enlace 817 que no está incluido en la topología de inundación. Por ejemplo, un nodo 813 puede recibir un mensaje de estado de enlace 821 de un nodo que no es compatible con LSFR y, por lo tanto, ha inundado el mensaje de estado de enlace 821 en todas las interfaces. Como otro ejemplo, el nodo 813 puede recibir un mensaje de estado de enlace 821 desde fuera de la topología de inundación cuando un nodo/enlace ha funcionado mal. En consecuencia, el nodo 813 puede realizar varias acciones, según el ejemplo. En un ejemplo, si el mensaje de estado de enlace 821 se recibe a partir de un enlace 817 que no está en la topología de inundación, el nodo 813 envía un mensaje de estado de enlace 823 y 822 a los nodos 813 vecinos sobre todos los demás enlaces 816 y 817 que están unidos al nodo 813 excluyendo el enlace 817 desde el cual se recibe el mensaje de estado del enlace 821 (por ejemplo, la inundación del estado del enlace sigue la topología real de la red). Tenga en cuenta que los mensajes 822 y 823 son copias del mensaje 821. En otro ejemplo, si el mensaje de estado del enlace 821 se recibe de un enlace 817 que no está en la topología de inundación, el nodo 813 envía un mensaje de estado del enlace 823 a los nodos 813 vecinos sobre todos los enlaces 816 que están unidos al nodo 813 y se incluyen en la topología de inundación. Por lo tanto, el nodo 813 puede configurarse para recibir un mensaje de estado de enlace 821 a través de un enlace 817 que está excluido de la topología de inundación e inundar el mensaje de estado de enlace 822 fuera de la topología de inundación.

La Figura 9 es un diagrama esquemático de un mecanismo de inundación de ejemplo 900 empleado por un primer nodo 913 al descubrir un segundo nuevo nodo 914. El mecanismo de inundación 900 puede emplearse en una red IGP, como la red IGP 100, 200 y/o 300. El mecanismo de inundación 900 se emplea con respecto a un nodo 913, que puede ser cualquier nodo en una red IGP (por ejemplo, nodo 111, 211, 212, 213, 311, 312 y/o 400) que emplea una topología de inundación, como topología de inundación 219 y/o 319. Dicha topología de inundación se puede generar, por ejemplo, de acuerdo con el método 500, 600 y/o 700. El mecanismo de inundación 900 puede emplearse con un mecanismo de inundación 800 cuando se descubre el nuevo nodo 914.

El mecanismo 900 ilustra un enfoque para ajustar la inundación del estado del enlace cuando un nuevo nodo 914 está conectado a un nodo 913, indicado como un primer nodo 913, que ya está funcionando en la red. El mecanismo 900 puede activarse cuando el primer nodo 913 establece una adyacencia con el nuevo nodo 914 recién conectado. Como se muestra, el nuevo nodo 914 recién conectado está conectado directamente al primer nodo 913 a través de un enlace 919. El primer nodo 913 asume que el nuevo nodo 914 está acoplado a la topología de inundación a través del enlace correspondiente 919 hasta que se pueda reconstruir la topología de inundación (por ejemplo, después de que haya un cambio en la red). Como tal, el enlace 919 se etiqueta temporalmente como un enlace de topología de inundación en la memoria del primer nodo 913. En consecuencia, el enlace 919 se emplea para agregar el nuevo nodo 914 recién conectado al árbol de enlaces en la topología de inundación hasta que se vuelve a calcular la topología de inundación. Después de agregar el nuevo nodo 914 a la topología de inundación, el primer nodo 913 puede recibir un mensaje de estado de enlace 921 sobre un enlace 916 en la topología de inundación. El primer nodo 913 puede luego reenviar el mensaje de estado del enlace 922 (una copia del mensaje 921) a través de los enlaces de topología de inundación 916 y el enlace 919 al nuevo nodo 914. El mensaje de estado del enlace 921 no se puede reenviar a los enlaces 917 que, de lo contrario, están excluidos de la topología de inundación.

La Figura 10 es un diagrama esquemático de un mecanismo de inundación de ejemplo 1000 empleado al descubrir que un nodo ha funcionado mal (por ejemplo, ha fallado). El mecanismo de inundación 1000 opera en una red IGP, tal como la red IGP 100, 200 y/o 300. El mecanismo de inundación 1000 se ilustra con respecto a un primer nodo 1013, que puede ser cualquier nodo en una red IGP (por ejemplo, nodo 111, 211, 212, 213, 311, 312 y/o 400) que emplea una topología de inundación, como la topología de inundación 219 y/o 319. Dicha topología de inundación se puede generar, por ejemplo, de acuerdo con el método 500, 600 y/o 700. El mecanismo de inundación 1000 puede emplearse con los mecanismos de inundación 800 y/o 900 cuando un nodo inactivo 1031 funciona mal.

Como se muestra, el mecanismo 1000 opera en una red IGP con nodos 1011, un nodo raíz 1012 y un primer nodo 1013 conectados por enlaces 1017 y enlaces de topología de inundación 1016, que son sustancialmente similares a los nodos 211, nodo raíz 212, primer nodo 213, enlaces 217 y enlaces de topología de inundación 216, respectivamente. El mecanismo 1000 puede operar en cualquier nodo y se ilustra desde la perspectiva del primer nodo 1013 para mayor claridad de la descripción. El mecanismo 1000 puede iniciarse cuando el primer nodo 1013 recibe un nuevo mensaje de estado de enlace 1021 de un nodo vecino 1033 a través de un enlace de topología de inundación 1016. El mensaje de estado del enlace 1021 indica que el nodo inactivo 1031 no está funcionando. El nodo inactivo 1031 es vecino de los nodos 1033, que también son vecinos del primer nodo 1013. El nodo inactivo 1031 es vecino del nodo 1034, que no es vecino del primer nodo 1013.

Cuando se recibe el mensaje de estado de enlace 1021 desde un enlace de topología de inundación 1016, el primer nodo 1013 envía el mensaje de estado de enlace 1022 (una copia del mensaje 1021) a los vecinos del primer nodo 1013 a través de los enlaces de topología de inundación 1016, que excluye los enlaces de topología de inundación 1016 desde el que se recibió el mensaje de estado de enlace 1021. Esto asegura que el nuevo mensaje de estado de enlace 1021 se reenvía correctamente sobre la topología de inundación. El primer nodo 1013 también envía el mensaje de estado del enlace 1023 (otra copia del mensaje 1021) a los nodos 1033 que son vecinos tanto del primer nodo 1013 como del nodo inactivo 1031. Dichos mensajes de estado de enlace 1023 se envían a través de los enlaces 1017 que conectan el primer nodo 1013 a los nodos 1033, aunque dichos enlaces 1017 no están incluidos en la topología de inundación. Este mecanismo 1000 considera que los nodos vecinos 1033 pueden confiar en el nodo inactivo 1031 para los mensajes de estado del enlace 1021. Por lo tanto, el primer nodo 1013 notifica a los nodos vecinos 1033 del nodo inactivo 1031 para garantizar que el mensaje de estado del enlace 1021 se propague a tales nodos 1033. El primer nodo 1013 puede no reenviar el mensaje de estado del enlace 1021 al nodo vecino restante 1034 del nodo inactivo 1031, debido a que el nodo 1034 no es vecino del primer nodo 1013. El mecanismo se basa en un vecino del nodo 1034 para informar al nodo 1034 que el nodo inactivo 1031 no está operativo. Este enfoque evita que todos los nodos de la red se pongan en contacto con todos los demás nodos cuando un nodo inactivo 1031 funciona mal.

Como tal, el primer nodo 1013 puede recibir un mensaje de estado de enlace 1021 (por ejemplo, un tercer mensaje de estado de enlace para distinguirlo de otros mensajes de estado de enlace descritos en la presente descripción) que indica que un segundo nodo inactivo 1031 en la red está inactivo. El primer nodo 1013 puede entonces inundar el mensaje de estado del enlace 1021 a los enlaces 1017 que están excluidos de la topología de inundación y conectarse entre el primer nodo 1013 y los nodos vecinos 1033 del nodo inactivo 1031.

La Figura 11 es un diagrama esquemático de otro ejemplo de mecanismo de inundación 1100 empleado al descubrir que un nodo ha funcionado mal (por ejemplo, ha fallado). El mecanismo de inundación 1100 opera en una red IGP, como la red IGP 100, 200 y/o 300. El mecanismo de inundación 1100 se ilustra con respecto a un primer nodo 1113, que puede ser cualquier nodo en una red IGP (por ejemplo, nodo 111, 211, 212, 213, 311, 312 y/o 400) que emplea una topología de inundación, como la topología de inundación 219 y/o 319. Dicha topología de inundación se puede generar, por ejemplo, de acuerdo con el método 500, 600 y/o 700. El mecanismo de inundación 1100 puede emplearse con los mecanismos de inundación 800 y/o 900 cuando un nodo inactivo 1131 funciona mal.

Como se muestra, el mecanismo 1100 opera en una red IGP con nodos 1111, un nodo raíz 1112 y un primer nodo 1113 conectados por enlaces 1117 y enlaces de topología de inundación 1116, que son sustancialmente similares a los nodos 1011, nodo raíz 1012, primer nodo 1013, enlaces 1017 y enlaces de topología de inundación 1016, respectivamente. Además, un nodo inactivo 1131 funciona mal, que es similar al nodo inactivo 1031. Además, la red contiene nodos 1133 que son vecinos del primer nodo 1113 y el nodo inactivo 1131, y un nodo 1134 que es vecino del nodo inactivo 1031 y no vecino del primer nodo 1113.

El mecanismo 1100 es similar al mecanismo 1000, pero se emplea cuando un primer nodo 1113 recibe un nuevo mensaje de estado de enlace 1121 de un nodo vecino a través de un enlace 1117 que no está en la topología de inundación. El mensaje de estado del enlace 1121 contiene información que indica que el nodo inactivo 1131 está inactivo/no funciona bien. En un ejemplo, el primer nodo 1113 envía el mensaje de estado del enlace 1121 a todos los nodos vecinos sobre todos los enlaces 1116 y 1117 que están conectados al primer nodo 1113 que excluye el enlace 1117 del que se recibió el mensaje de estado del enlace 1121. Tal respuesta es sustancialmente similar al mecanismo 800 y permite que el mensaje de estado del enlace 1121 fluya siguiendo la topología real de la red. Tal ejemplo supone que el primer nodo 1113 no recibe correctamente los mensajes de estado del enlace sobre la topología de inundación y toma medidas para garantizar que el mensaje de estado del enlace 1121 se transmita lo más ampliamente posible.

En otro ejemplo, el primer nodo 1113 inunda el mensaje de estado de enlace 1122 (una copia del mensaje 1121) sobre los enlaces de topología de inundación 1116. El primer nodo 1113 también inunda el mensaje de estado del enlace 1122 a los nodos 1133 que son vecinos tanto del primer nodo 1113 como del nodo inactivo 1131 sobre los enlaces 1117 que no están en la topología de inundación. No es necesario reenviar el mensaje de estado del enlace 1122 por el enlace 1117 desde el que se recibió el mensaje de estado del enlace 1121. Además, el primer nodo 1113 puede no reenviar el mensaje de estado del enlace 1121 al nodo vecino restante 1134 del nodo inactivo 1131, debido a que el nodo 1134 no es vecino del primer nodo 1113. Tal ejemplo se enfoca en reenviar información de estado de enlace a lo largo de la topología de inundación e informar a los vecinos del nodo inactivo 1131 del mal funcionamiento.

En cualquier ejemplo, el primer nodo 1113 recibe un mensaje de estado de enlace 1121 (por ejemplo, un tercer mensaje de estado de enlace para distinguirlo de otros mensajes de estado de enlace descritos en la presente descripción) que indica que un segundo nodo inactivo 1131 en la red está inactivo. El primer nodo 1113 luego inunda el mensaje de estado del enlace 1122 a los enlaces 1117 que están excluidos de la topología de inundación y se conectan entre el primer nodo 1113 y los nodos vecinos 1133 del nodo inactivo 1131.

La Figura 12 es un diagrama esquemático de un ejemplo de mecanismo de inundación 1200 empleado al descubrir que un enlace 1231 ha funcionado mal (por ejemplo, ha fallado). El mecanismo de inundación 1200 opera en una red IGP, como la red IGP 100, 200 y/o 300. El mecanismo de inundación 1200 se ilustra con respecto a un primer nodo 1213, que puede ser cualquier nodo en una red IGP (por ejemplo, nodo 111,211, 212, 213, 311, 312 y/o 400) que emplea una topología de inundación, como la topología de inundación 219 y/o 319. Dicha topología de inundación se puede generar, por ejemplo, de acuerdo con el método 500, 600 y/o 700. El mecanismo de inundación 1200 puede emplearse con los mecanismos de inundación 800, 900, 1000 y/o 1100 cuando un enlace 1231 está inactivo/funciona mal.

Como se muestra, el mecanismo 1200 opera en una red IGP con nodos 1211, un nodo raíz 1212 y un primer nodo 1213 conectados por enlaces 1217 y enlaces de topología de inundación 1216, que son sustancialmente similares a los nodos 1011, nodo raíz 1012, primer nodo 1013, enlaces 1017 y enlaces de topología de inundación 1016, respectivamente. Además, un enlace descendente 1231 funciona mal. Un nodo 1232 está acoplado al primer nodo 1213 a través del enlace descendente 1231. Los nodos 1233 son vecinos tanto del primer nodo 1213 como del nodo 1232 adyacente al enlace descendente 1231. El nodo 1234 es vecino del nodo 1232 (adyacente al enlace descendente), pero no es vecino del primer nodo 1213.

El primer nodo 1213 descubre que un enlace 1231 está inactivo al recibir un mensaje de estado de enlace más nuevo 1221 de un nodo vecino, en este caso el nodo raíz 1212, a través de un enlace, en este caso un enlace de topología de inundación 1216. El primer nodo 1213 primero verifica para determinar si el enlace descendente 1231 está en la topología de inundación. Si el enlace descendente 1231 no está en la topología de inundación, el enlace descendente 1231 no afecta la inundación del estado del enlace y no se necesita tomar ninguna acción más allá de reenviar el mensaje de estado del enlace 1222 (una copia del mensaje 1221) a través de la topología de inundación. En el ejemplo que se muestra, el enlace descendente 1231 está en la topología de inundación, por lo que el primer nodo 1213 procede a verificar si el enlace descendente 1231 está en una interfaz vecina al primer nodo 1213. Si el enlace descendente 1231 no está en una interfaz vecina, el primer nodo 1213 puede permitir que los nodos adyacentes al enlace descendente 1231 manejen cualquier señalización y, por lo tanto, no puede realizar ninguna acción más allá de reenviar el mensaje de estado del enlace 1222 a través de la topología de inundación. Este enfoque evita que todos los nodos de la red emitan señales al descubrir un enlace descendente 1231. En el ejemplo que se muestra, el enlace descendente 1231 es adyacente al primer nodo 1213, por lo que el primer nodo 1213 asume la razonabilidad de la señalización para garantizar que los nodos que podrían depender del enlace descendente 1231 continúen recibiendo información del estado del enlace hasta que se pueda volver a calcular la topología de inundación. En este caso, el primer nodo 1213 envía el mensaje de estado de enlace 1222 a través de la topología de inundación a cada enlace de topología de inundación 1216 excepto el enlace de topología de inundación 1216 desde el cual se recibió el mensaje de estado de enlace 1221. Además, el primer nodo 1213 envía el mensaje de estado del enlace 1223 (otra copia del mensaje 1221) sobre los enlaces 1217 que están excluidos de la topología de inundación según sea necesario para contactar a los nodos 1233 que son vecinos tanto del primer nodo 1213 como del nodo 1232 adyacente al enlace descendente 1231. Además, el primer nodo 1213 puede no reenviar el mensaje de estado del enlace 1221 al nodo vecino restante 1234 del nodo 1232, debido a que el nodo 1234 no es vecino del primer nodo 1213. Este enfoque permite que los nodos 1233 que potencialmente dependen del enlace descendente 1231 para recibir información del estado del enlace continúen recibiendo dicha información del estado del enlace a pesar de la topología de inundación interrumpida.

Por lo tanto, el primer nodo 1213, empleando el mecanismo 1200, puede recibir un mensaje de estado de enlace 1221 (por ejemplo, un cuarto mensaje de estado de enlace para distinguirlo de otros mensajes de estado de enlace descritos en la presente descripción) que indica un enlace 1231 (por ejemplo, un primer enlace) en la red esta abajo. El primer nodo 1213 puede determinar que el primer enlace 1213 está en la topología de inundación y que el primer enlace 1231 está conectado al primer nodo 1213. Con base en la determinación, el primer nodo 1213 puede enviar el mensaje de estado del enlace 1221 a los enlaces 1216 y/o 1217 que se conectan a vecinos que también se conectan a un nodo 1232 adyacente al primer enlace.

Cabe señalar que cuando un enlace 1231 en una topología de inundación existente/antigua está inactivo o un nodo está inactivo (por ejemplo, como se describe en los mecanismos 1000 y 1100), se genera una nueva topología de inundación poco después. Los mecanismos 1000, 1100 y/o 1200 permiten que la topología de inundación existente continúe funcionando hasta que los nodos puedan calcular y emplear la nueva topología de inundación. Los mecanismos 1000, 1100 y 1200 mencionados anteriormente permiten que la red continúe funcionando cuando un enlace o un nodo está inactivo, siempre que la topología de la red no se divida en múltiples topologías de inundación aisladas por el mal funcionamiento. Las interfaces críticas se pueden guardar en la memoria para hacer frente a tales escenarios, como se describe a continuación.

La Figura 13 es un diagrama esquemático de una red IGP 1300 de ejemplo con una interfaz crítica 1335 en la topología de inundación 1319. La red IGP 1300 es sustancialmente similar a la red IGP 100, 200 y/o 300. La red IGP 1300 incluye nodos 1311 y un nodo raíz 1312, que pueden ser similares a los nodos 111, 211, 212, 213, 311, 312 y/o 400. La topología de inundación 1319 de la red IGP 1300 puede ser similar a la topología de inundación 219 y/o 319. Dicha topología de inundación 1319 se puede generar, por ejemplo, de acuerdo con el método 500, 600 y/o 700. Los nodos 1311 y el nodo raíz 1312 pueden emplear mecanismos de inundación 800, 900, 1000, 1100 y/o 1200.

Al calcular la topología de inundación 1319, los nodos 1311 y el nodo raíz 1312 mantienen el conocimiento de cualquier interfaz crítica 1335 en la topología de inundación 1319. Una interfaz crítica 1335 es cualquier interfaz (por ejemplo, enlace o nodo) en la topología de inundación 1319 que, si se elimina, dividiría la topología de inundación 1319 en dos o más topologías de enlaces no conectadas. En el ejemplo que se muestra, la topología de inundación 1319 contiene múltiples bucles de enlaces de topología de inundación. Cuando se elimina un enlace de topología de inundación en un bucle, la topología de inundación 1319 todavía puede enviar información de estado de enlace a todos los nodos en el bucle a través de la parte no dañada del bucle. Por lo tanto, dichos enlaces no son interfaces críticas. Sin embargo, si la interfaz crítica 1335 se elimina de la topología de inundación 1319, la topología de inundación 1319 se divide en un primer árbol 1341 y un segundo árbol 1342. En ausencia de la interfaz crítica 1335, el primer árbol 1341 y el segundo árbol 1342 no pueden comunicar información de estado de enlace ya que ningún enlace de topología de inundación 1319 conectaría los dos árboles.

Las interfaces críticas 1335 pueden determinarse en cada nodo 1311/1312 durante/después de calcular la topología de inundación 1319 y guardarse en la memoria. El número de interfaces críticas 1335 se puede reducir agregando más enlaces de hoja como se describió anteriormente. Cuando un enlace o nodo asociado con una interfaz crítica 1335 funciona mal, los nodos 1311/1312 (tras la notificación del mal funcionamiento a través de mensajes de estado de enlace) pueden volver a mensajes de estado de enlace de inundación en todas las interfaces hasta que se pueda generar una nueva topología de inundación 1319 para abordar el fallo de la interfaz crítica y volver a conectar todos los nodos 1311/1312.

Por lo tanto, los nodos 1312/1311 pueden determinar las interfaces críticas 1335, donde una interfaz crítica 1335 es un enlace o nodo cuyo fallo divide la topología de inundación 1319. Los nodos 1312/1311 pueden interrumpir el uso de la topología de inundación 1319 cuando falla una interfaz crítica 1335.

La Figura 14 es un diagrama esquemático de un ejemplo de codificación OSPF v2 1400 para indicar soporte de nodo para LSFR. Por ejemplo, un nodo, como los nodos 111, 211, 212, 213, 311, 312, 400, 1311, 1312 y/o 1333, en una red IGP, como la red IGP 100, 200, 300 y/o 1300, puede emplear la codificación 1400 para indicar si el nodo admite LSFR. Esta información puede ser empleada por otros nodos al construir una topología de inundación, por ejemplo, con base en los métodos 500, 600 y/o 700. Los nodos OSPF v2 que emplean LSFR y, por lo tanto, emplean la codificación 1400, también pueden emplear los mecanismos de inundación 800, 900, 1000, 1100 y/o 1200.

La codificación 1400 puede emplearse para incorporar LSFR en una red IGP que sea compatible con OSPF v2. Específicamente, la codificación 1400 se puede incluir en un OSPF v2 LSA. La codificación 1400 incluye un campo de envejecimiento de LS 1401 establecido para indicar un tiempo (por ejemplo, en segundos) desde que se originó el LSA. El campo de envejecimiento LSA 1401 puede tener una longitud de dieciséis bits y puede extenderse desde el bit cero al bit quince. La codificación 1400 también incluye un campo de opciones 1402 que puede contener datos que indican capacidades opcionales admitidas en una parte de un dominio de enrutamiento en una red IGP como se describe en el LSA. El campo de opciones 1402 puede tener una longitud de ocho bits y puede extenderse desde el bit dieciséis hasta el bit veintitrés. La codificación 1400 también incluye un campo de tipo LS 1403 que se puede configurar para indicar el tipo de LSA. Por ejemplo, el campo de tipo de LS 1403 se puede establecer en uno para indicar que el LSA es un enrutador (por ejemplo, un nodo) LSA. El campo de tipo LS 1403 puede tener una longitud de ocho bits y puede extenderse desde el bit veinticuatro al bit treinta y uno. La codificación 1400 también incluye un campo de ID de estado de enlace 1404 que incluye datos que identifican la parte del entorno de Internet que está describiendo el LSA. Por ejemplo, el campo de ID de estado de enlace 1404 se puede configurar para indicar que el LSA describe los estados recopilados de las interfaces de un enrutador. El campo de ID de estado de enlace 1404 puede tener una longitud de treinta y dos bits y puede extenderse desde el bit cero hasta el bit treinta y uno. La codificación 1400 también incluye un campo de enrutador publicitario 1405 que contiene el ID del enrutador que origina el LSA. El campo del enrutador de anuncios 1405 puede tener una longitud de treinta y dos bits y puede extenderse desde el bit cero hasta el bit treinta y uno. La codificación 1400 también incluye un campo de número de secuencia LS 1406 que contiene datos para identificar el LSA. Los datos del campo de número de secuencia LS 1406 pueden emplearse para detectar LSA antiguos o duplicados. El campo de número de secuencia LS 1406 puede tener una longitud de treinta y dos bits y puede extenderse desde el bit cero hasta el bit treinta y uno. La codificación 1400 también incluye un campo de suma de verificación LS 1407 que contiene datos de suma de verificación para soportar la verificación de errores. El campo de suma de verificación LS 1407 puede tener una longitud de dieciséis bits y puede extenderse desde el bit cero al bit quince. La codificación 1400 también incluye un campo de longitud de LS 1408 que contiene datos que indican la longitud del LSA en bytes. El campo de longitud LS 1408 puede tener una longitud de dieciséis bits y puede extenderse desde el bit dieciséis hasta el bit treinta y uno. La codificación 1400 también incluye varias indicaciones empleadas para indicar varias características para el enrutador que inicia el LSA. La codificación puede incluir un indicador virtual (V) 1421 en la posición de bit cinco, que se puede configurar para indicar cuándo el enrutador es un punto final para uno o más enlaces virtuales adyacentes. La codificación también puede incluir un indicador externo (E) 1422 en la posición de bit seis, que se puede configurar para indicar cuándo el enrutador es un enrutador de límite de sistema autónomo. La codificación también puede incluir un indicador de borde (B) 1423 en la posición de bit siete, que se puede configurar para indicar cuándo el enrutador es un enrutador de área de borde.

La codificación 1400 también incluye un indicador F 1431. El indicador F 1431 puede ser de un bit y puede posicionarse en la posición de bit ocho. El indicador F 1431 se puede establecer (por ejemplo, establecer en uno) para indicar que el enrutador que inicia el LSA admite la reducción de inundación (por ejemplo, de acuerdo con los mecanismos LSFR descritos en la presente descripción). La posición de bit del indicador F 1431 también puede establecerse (por ejemplo, establecerse en cero) de forma predeterminada para que los enrutadores que no admiten LSFR puedan ser identificados por los enrutadores que reciben el LSA. Como tal, la codificación 1400 permite que los mensajes de estado de enlace contengan indicadores F establecidos para indicar los nodos en la red que admiten la reducción de inundación de estado de enlace a través de una topología de inundación.

La codificación 1400 también incluye un campo de número de enlaces 1409 que indica el número de enlaces descritos por el LSA. El campo de número de enlaces 1409 puede tener una longitud de dieciséis bits y puede extenderse desde la posición de bit dieciséis hasta la posición de bit treinta y uno. La codificación 1400 también incluye un campo de ID de enlace 1410 para cada enlace descrito por el lSa . El campo de ID de enlace 1410 incluye un ID que identifica el objeto (por ejemplo, un nodo) al que está conectado el enlace correspondiente. El campo de ID de enlace 1410 puede tener una longitud de treinta y dos bits y puede extenderse desde el bit cero hasta el bit treinta y uno. La codificación 1400 también incluye un campo de datos de enlace 1411 para cada enlace descrito por el LSA. El campo de datos de enlace 1411 incluye información de dirección (por ejemplo, información de dirección IP) relacionada con el enlace/interfaz correspondiente. El campo de datos de enlace 1411 puede tener una longitud de treinta y dos bits y puede extenderse desde el bit cero hasta el bit treinta y uno.

La codificación 1400 también incluye un campo de tipo 1412 para cada enlace descrito por el LSA. El campo de tipo 1412 contiene datos que describen el enlace del enrutador. El campo de tipo 1412 puede tener una longitud de ocho bits y puede extenderse desde el bit cero al bit siete. La codificación 1400 también incluye varios campos de tipo de servicio (ToS) 1413 para cada enlace descrito por el LSA. El número del campo ToS 1413 indica un número de métricas ToS para los enlaces correspondientes que se incluyen en el LSA. El número del campo ToS 1413 puede tener una longitud de ocho bits y puede extenderse desde el bit ocho hasta el bit quince. La codificación 1400 también incluye un campo métrico 1414 que incluye el costo (por ejemplo, costo de enrutamiento/latencia, etc.) de usar el enlace correspondiente. El campo métrico 1414 puede tener una longitud de dieciséis bits y puede extenderse desde el bit dieciséis hasta el bit treinta y uno. La codificación 1400 también puede incluir campos ToS 1415 y campos métricos ToS 1416 que indican información ToS asociada con el enlace correspondiente. El campo ToS 1415 indica el tipo de servicio al que hace referencia el campo métrico ToS 1416, puede tener una longitud de ocho bits y puede extenderse desde la posición de bit cero hasta la posición de bit siete. El campo de métrica Tos 1416 puede indicar información específica de ToS para el enlace, puede tener una longitud de dieciséis bits y puede extenderse desde el bit dieciséis hasta el bit treinta y uno.

La Figura 15 es un diagrama esquemático de un ejemplo de codificación OSPF v3 1500 para indicar soporte de nodo para LSFR. Por ejemplo, un nodo, como los nodos 111, 211, 212, 213, 311, 312, 400, 1311, 1312 y/o 1333, en una red IGP, como la red IGP 100, 200, 300 y/o 1300, puede emplear la codificación 1500 para indicar si el nodo admite LSFR. Esta información puede ser empleada por otros nodos al construir una topología de inundación, por ejemplo, con base en los métodos 500, 600 y/o 700. Los nodos OSPF v3 que emplean LSFR y, por lo tanto, emplean la codificación 1500, también pueden emplear los mecanismos de inundación 800, 900, 1000, 1100 y/o 1200.

La codificación 1500 puede emplearse para incorporar LSFR en una red IGP que sea compatible con OSPF v3. Específicamente, la codificación 1500 se puede incluir en un OSPF v3 LSA. La codificación 1500 puede incluir un campo de envejecimiento de LS 1501, un campo de tipo de LS 1503, un campo de ID de estado de enlace 1504, un campo de enrutador de publicidad 1505, un campo de número de secuencia de LS 1506, un campo de suma de verificación de LS 1507 y un campo de longitud de LS 1508, que puede ser sustancialmente similar al campo de envejecimiento de LS 1401, campo de tipo de LS 1403, campo de ID de estado de enlace 1404, campo de enrutador de anuncios 1405, campo de número de secuencia de LS 1406, campo de suma de verificación de LS 1407 y campo de longitud de LS 1408, respectivamente. A diferencia del campo de tipo LS 1403, el campo de tipo LS 1503 tiene una longitud de dieciséis bits y se extiende desde la posición de bit dieciséis hasta la posición de bit treinta y uno. La codificación 1500 también incluye un campo de opciones 1509 que se puede configurar para indicar capacidades opcionales admitidas por el enrutador que inició el LSA. El campo de opciones 1509 puede tener una longitud de treinta y dos bits y puede extenderse desde el bit cero hasta el bit treinta y uno. El campo de opciones 1509 incluye varias indicaciones empleadas para indicar varias características para el enrutador que inicia el LSA. El campo de opciones 1509 puede incluir un indicador V 1521, un indicador E 1522 y un indicador B 1523, que pueden ser sustancialmente similares al indicador V 1421, indicador E 1422 e indicador B 1423, respectivamente. El campo de opciones 1509 también puede incluir un indicador de comodín (W) 1524 que puede configurarse para indicar que el enrutador que inicia el LSA es un receptor de multidifusión comodín. El indicador W 1524 puede tener una longitud de un bit y puede posicionarse en la posición de bit cuatro.

El campo de opciones 1509 también incluye un indicador F 1531. El indicador F 1531 puede ser de un bit y puede colocarse en la posición de bit ocho. El indicador F 1531 se puede establecer (por ejemplo, establecer en uno) para indicar que el enrutador que inicia el LSA admite la reducción de inundación (por ejemplo, de acuerdo con los mecanismos LSFR descritos en la presente descripción). La posición de bit del indicador F 1531 también puede establecerse (por ejemplo, establecerse en cero) de forma predeterminada para que los enrutadores que no admiten LSFR puedan ser identificados por los enrutadores que reciben el LSA. Como tal, la codificación 1500 permite que los mensajes de estado de enlace contengan indicadores F establecidos para indicar los nodos en la red que admiten la reducción de inundación de estado de enlace a través de una topología de inundación.

La codificación 1500 también puede incluir un campo de tipo 1512 y un campo de métrica 1514 para cada enlace descrito por el LSA. El campo de tipo 1512 y el campo métrico 1514 pueden ser sustancialmente similares al campo de tipo 1412 y al campo métrico 1414, respectivamente. La codificación 1500 también puede incluir un campo de ID de interfaz 1510, un campo de ID de interfaz vecina 1515 y un campo de ID de enrutador vecino 1516 para cada enlace descrito en el LSA. El campo de ID de interfaz 1510, el campo de ID de interfaz vecina 1515 y el campo de ID de enrutador vecino 1516 pueden tener cada uno treinta y dos bits de longitud y extenderse desde la posición de bit cero hasta la posición de bit treinta y uno. El campo de ID de interfaz 1510 indica un ID asignado a la interfaz (por ejemplo, enlace) que se está describiendo. El campo de ID de interfaz vecina 1515 indica un ID de interfaz del enrutador vecino acoplado al enlace que se está describiendo. El campo de ID de enrutador vecino 1516 indica el ID de enrutador del enrutador vecino acoplado al enlace que se describe. La Figura 16 es un diagrama esquemático de un ejemplo de codificación IS-IS 1600 para indicar soporte de nodo para LSFR. Por ejemplo, un nodo, como los nodos 111, 211, 212, 213, 311, 312, 400, 1311, 1312 y/o 1333, en una red IGP, como la red IGP 100, 200, 300 y/o 1300, puede emplear la codificación IS-IS 1600 para indicar si el nodo admite LSFR. Esta información puede ser empleada por otros nodos al construir una topología de inundación, por ejemplo, con base en los métodos 500, 600 y/o 700. Los nodos IS-IS que emplean LSFR y, por lo tanto, emplean la codificación 1600, también pueden emplear los mecanismos de inundación 800, 900, 1000, 1100 y/o 1200.

La codificación 1600 puede emplearse para incorporar LSFR en una red IGP que sea compatible con IS-IS. Específicamente, la codificación 1600 se puede incluir como TLV en un IS-IS LSP. La codificación 1600 incluye un campo de tipo 1601 establecido para indicar que la codificación es un TLV con capacidad de enrutador IS-IS. Por ejemplo, el campo de tipo 1601 puede tener una longitud de ocho bits, puede extenderse desde la posición de bit cero hasta la posición de bit siete y puede establecerse en doscientos cuarenta y dos. La codificación 1600 incluye un campo de longitud 1602, que puede tener una longitud de ocho bits, puede extenderse desde la posición de bit ocho a la posición de bit quince, y puede configurarse para indicar la longitud del TLV. El campo de longitud 1602 se puede establecer en un valor de entre cinco y doscientos cincuenta y cinco inclusive. La codificación 1600 también incluye un campo de ID de enrutador 1603, que tiene una longitud de treinta y dos o cuarenta y ocho bits, puede extenderse desde la posición de bit dieciséis hasta la posición de bit quince o treinta y uno, y contiene un ID del enrutador que inicia el mensaje de estado del enlace. La codificación 1600 también incluye un conjunto de indicadores 1605 que indican las capacidades del enrutador que inicia el mensaje de estado del enlace. Los indicadores 1605 pueden tener una longitud de ocho bits y pueden extenderse desde el bit dieciséis hasta el bit veintitrés. Los indicadores 1605 incluyen un indicador de eliminación de bucle (D) 1621 que se puede posicionar en la posición de bit veintidós y se puede configurar para indicar si el TLV se puede filtrar entre niveles en el sistema IS IS. Los indicadores 1605 también incluyen un indicador de conjunto (S) 1622 que se puede posicionar en la posición de bit veintitrés, y se puede configurar para indicar si el TLV está inundando todo el dominio de la red IS-IS o está contenido en un nivel de red IS-IS particular.

Los indicadores 1605 también incluyen un indicador F 1631, que puede posicionarse en la posición de bit veintiuno. El indicador F 1631 se puede establecer (por ejemplo, establecer en uno) para indicar que el enrutador que inicia el LSP admite la reducción de inundación (por ejemplo, de acuerdo con los mecanismos LSFR descritos en la presente descripción). La posición de bit del indicador F 1631 también puede establecerse (por ejemplo, establecerse en cero) de forma predeterminada para que los enrutadores que no admiten LSFR puedan ser identificados por los enrutadores que reciben el LSP. Como tal, la codificación 1600 permite que los mensajes de estado de enlace contengan indicadores F establecidos para indicar los nodos en la red que admiten la reducción de inundación de estado de enlace a través de una topología de inundación.

La codificación 1600 también puede incluir uno o más sub-TLV opcionales 1606 que contienen información adicional relevante para el LSP.

La Figura 17 es un diagrama esquemático de un ejemplo de codificación TLV de control LSFR 1700 para gestionar LSFR en una red IGP. Por ejemplo, un nodo, como los nodos 111, 211, 212, 213, 311, 312, 400, 1311, 1312 y/o 1333, en una red IGP, como la red IGP 100, 200, 300 y/o 1300, puede recibir la codificación TLV de control LSFR 1700 para controlar la implementación de LSFR en la red. Específicamente, la codificación TLV de control LSFR 1700 puede permitir que un usuario/administrador del sistema seleccione y/o cambie los modos operativos para LSFR y las topologías de inundación asociadas. La codificación TLV de control LSFR 1700 puede emplearse como parte de un mensaje de estado de enlace, como la codificación 1400, 1500 y/o 1600. Los nodos pueden emplear dicha información al construir una topología de inundación, por ejemplo, con base en los métodos 500, 600 y/o 700. La codificación TLV de control LSFR 1700 también puede indicar a los nodos cuándo emplear los mecanismos de inundación LSFR 800, 900, 1000, 1100 y/o 1200.

La codificación TLV de control LSFR 1700 emplea un campo de tipo TLV de información 1701 que puede incluir datos que identifican el TLV como un TLV de control LSFR. El campo de tipo TLV 1701 puede tener una longitud de dieciséis bits y puede extenderse desde la posición de bit cero hasta la posición de bit quince. La codificación TLV de control de LSFR 1700 también emplea un campo de longitud de TLV 1702 que incluye datos que indican la longitud del TLV de control de LSFR. El campo de longitud de TLV 1702 puede tener una longitud de dieciséis bits y puede extenderse desde la posición de bit dieciséis hasta la posición de bit treinta y uno.

La codificación TLV de control LSFR 1700 también emplea un campo de operación (OP) 1731, que puede tener una longitud de tres bits y puede extenderse desde la posición de bit cero a la posición de bit dos. El campo OP 1731 puede emplearse para seleccionar y/o cambiar el modo operativo LSFR para nodos que son compatibles con LSFR. El campo OP 1731 puede contener datos para indicar que los nodos deben realizar una reducción de inundación o puede contener datos para indicar que los nodos deben retroceder a la inundación normal sin usar una topología de inundación. Por lo tanto, la codificación TLV de control LSFR 1700 permite que los mensajes de estado del enlace contengan un campo OP establecido para cambiar a la reducción de inundación del estado del enlace desde la inundación total de la red. Por ejemplo, un usuario/administrador del sistema puede emplear el campo OP 1731 para activar y/o desactivar LSFR según lo desee.

La codificación TLV de control LSFR 1700 también emplea un campo de modo (MOD) 1732, que puede tener una longitud de tres bits y puede extenderse desde la posición de bit tres hasta la posición de bit cinco. LSFR puede incluir tres modos, incluido el modo central, el modo distribuido y el modo de configuración estática, y el campo MOD 1732 puede emplearse para señalar un cambio entre modos. Por ejemplo, el campo MOD 1732 se puede configurar en modo central, lo que dirige la red IGP para seleccionar un líder y/o un líder de respaldo. Luego, el líder calcula la topología de inundación e inunda la topología de inundación a los otros nodos. Cada nodo recibe y usa la topología de inundación del líder. El campo MOD 1732 también se puede configurar en modo distribuido, lo que dirige a todos los nodos en la red IGP para calcular una topología de inundación empleando un algoritmo común como se describió anteriormente. El campo MOD 1732 también se puede establecer en el modo de configuración estática, que dirige los nodos en la red IGP para emplear una topología de inundación configurada. Por lo tanto, la codificación TLV de control LSFR 1700 permite que los mensajes de estado de enlace contengan un campo MOD 1732 establecido para indicar una reducción de inundación de estado de enlace centralizada, reducción de inundación de estado de enlace distribuido o reducción de inundación de estado de enlace configurada estáticamente.

La codificación TLV de control LSFR 1700 también emplea un campo de algoritmo 1733, que puede tener una longitud de ocho bits y puede extenderse desde la posición de bit seis hasta la posición de bit trece. El campo de algoritmo 1733 puede contener datos que indican un algoritmo para calcular una topología de inundación (por ejemplo, método 500, 600 y/o 700) que deberían utilizar los nodos en modo central y/o distribuido. Por lo tanto, la codificación TLV de control LSFR 1700 permite que los mensajes de estado de enlace contengan un campo de algoritmo 1733 establecido para indicar un algoritmo para construir el árbol de enlaces en la topología de inundación. La codificación 1700 también puede incluir uno o más sub-TLV opcionales 1706 que contienen información adicional relevante para la implementación de LSFR.

La Figura 18 es un diagrama esquemático de un ejemplo de codificación TLV 1800 para integrar LSFR centralizado con LSFR distribuida. Específicamente, la codificación TLV 1800 puede usarse junto con la codificación TLV de control LSFR 1700, por ejemplo, cuando el campo MOD 1732 se establece en modo central. La codificación TLV 1800 incluye un campo de tipo TLV de información 1801 y un campo de longitud de TLV 1802 que son sustancialmente similares al campo de tipo de información TLV 1701 y al campo de longitud de TLV 1702, respectivamente. La codificación TLV 1800 también incluye un campo de prioridad 1803, que puede tener una longitud de ocho bits y puede extenderse desde la posición de bit cero hasta la posición de bit siete. El campo de prioridad 1803 puede emplearse para indicar una prioridad de un nodo que origina un TLV para convertirse en un líder en modo central. La codificación 1800 también puede incluir uno o más sub-TLV opcionales 1806 que contienen información adicional relevante para la implementación de LSFR. Tales sub-TLV 1806 pueden incluir un sub-TLV líder y/o un sub-TLV líder de respaldo, que incluyen un método/algoritmo para seleccionar el líder y/o el líder de respaldo, respectivamente.

La Figura 19 es un diagrama de flujo de un método de ejemplo 1900 de operar mecanismos LSFR en una red IGP. Por ejemplo, el método 1900 puede emplearse por un nodo, como los nodos 111, 211, 212, 213, 311, 312, 400, 1311, 1312 y/o 1333, en una red IGP, como la red IGP 100, 200, 300 y/o 1300. El método 1900 puede emplearse en redes OSPF y/o IGP y, por lo tanto, puede emplearse junto con la codificación 1400, 1500 y/o 1600. El método 1900 puede emplearse para construir una topología de inundación, por ejemplo, empleando los métodos 500, 600 y/o 700. El método 1900 también puede emplear mecanismos de inundación, como los mecanismos de inundación 800, 900, 1000, 1100 y/o 1200. El método 1800 también puede iniciarse al recibir una codificación TLV de control LSFR 1700. El método 1900 se puede implementar en cualquier nodo de una red IGP, que se indica como primer nodo con el fin de aclarar la descripción. En el bloque 1901, se reciben datos en el primer nodo que indican la conectividad de una pluralidad de nodos en la red. Dichos datos incluyen datos de estado de enlace y se pueden recibir, por ejemplo, de acuerdo con la inundación general de mensajes de estado de enlace, como OSPF LSA o IS-IS LSP.

En el bloque 1903, el primer nodo (y todos los nodos de la red) construye una topología de inundación con base en la conectividad. La topología de inundación se puede construir seleccionando uno de los nodos de la red como nodo raíz y construir un árbol de enlaces de topología de inundación que conectan el nodo raíz con los otros nodos de la red. Por ejemplo, el bloque 1903 puede construir una topología de inundación empleando los métodos 500, 600 y/o 700. La construcción de una topología de inundación puede producirse periódicamente y/o tras la ocurrencia de una condición, como un mal funcionamiento de enlace/nodo, el mal funcionamiento de una interfaz crítica, etc. nodos, por ejemplo, como se anuncia en los mensajes de estado de enlace que emplean un indicador F. Además, el primer nodo (y todos los nodos) puede construir la topología de inundación de acuerdo con un algoritmo indicado en una codificación TLV de control LSFR 1700 (por ejemplo, en un mensaje de estado de enlace).

En el bloque opcional 1905, el primer nodo puede recibir una solicitud que especifica un número de enlaces de hoja para agregar al árbol. La solicitud puede ser un TLV incluido en un mensaje de estado de enlace, por ejemplo, iniciado por un usuario/administrador de red. Si se recibe una solicitud, el primer nodo (y todos los nodos de la red) agrega el número de enlaces de hoja a la topología de inundación como se especifica en la solicitud. Dichos enlaces de hoja se agregan entre los nodos de la red, por ejemplo, como se describe con respecto a la Figura 3 arriba. Por ejemplo, se pueden agregar enlaces de hoja para reducir el número de interfaces críticas, se pueden agregar con base en el ID de enlace/ID de interfaz/ID de nodo, etc. Antes de agregar dichos enlaces de hoja, el árbol de enlaces en la topología de inundación puede contener un número mínimo de enlaces para conectar todos los nodos de la red al nodo raíz. Los enlaces de hoja pueden aumentar la fiabilidad de la topología de inundación a expensas de aumentar ligeramente la comunicación de mensajes de estado de enlace redundante.

En el bloque 1907, el primer nodo almacena la topología de inundación en una memoria sin transmitir la topología de inundación a los otros nodos de la red. Este enfoque garantiza que la topología de inundación se cree en cada nodo de acuerdo con un algoritmo preseleccionado, lo que a su vez reduce la inundación de mensajes de estado de enlace relacionada con la topología de inundación.

En el bloque 1909, el primer nodo inunda mensajes de estado de enlace sobre la topología de inundación. Además, el primer nodo no inunda mensajes de estado de enlace fuera de la topología de inundación.

En el bloque opcional 1911, el primer nodo puede alterar el procedimiento de inundación con base en los cambios en el estado del enlace/nodo. Por ejemplo, el primer nodo puede emplear mecanismos de inundación 800, 900, 1000, 1100 y/o 1200 según el tipo de cambios que se produzcan en la red. Como ejemplos específicos, el primer nodo puede recibir un primer mensaje de estado de enlace desde un nodo recién conectado, donde el nodo recién conectado está conectado directamente al primer nodo a través de un enlace. El primer nodo puede agregar el nodo recién conectado al árbol de enlaces en la topología de inundación hasta que se vuelva a calcular la topología de inundación. Como otro ejemplo, el primer nodo puede recibir un segundo mensaje de estado de enlace a través de un enlace que está excluido de la topología de inundación. El primer nodo puede inundar el segundo mensaje de estado de enlace fuera de la topología de inundación. Como otro ejemplo, el primer nodo puede recibir un tercer mensaje de estado de enlace que indica que un segundo nodo en la red está inactivo. Luego, el primer nodo puede inundar el mensaje de estado del tercer enlace a los enlaces que están excluidos de la topología de inundación y conectarse entre el primer nodo y los vecinos del segundo nodo. Como otro ejemplo, el primer nodo puede recibir un cuarto mensaje de estado de enlace que indica que un primer enlace en la red está inactivo. El primer nodo puede determinar que el primer enlace está en la topología de inundación y el primer enlace está conectado al primer nodo. Con base en la determinación, el primer nodo puede enviar el cuarto mensaje de estado del enlace a los enlaces que se conectan a los vecinos que también conectan los nodos adyacentes al primer enlace. Como otro ejemplo, el primer nodo puede determinar interfaces críticas en la red, donde una interfaz crítica es un enlace o nodo cuyo fallo divide la topología de inundación. El primer nodo puede interrumpir el uso de la topología de inundación cuando falla una interfaz crítica.

La Figura 20 es una modalidad de un dispositivo 2000 para operar mecanismos LSFR en una red IGP. Por ejemplo, el dispositivo 2000 puede emplearse para implementar el método 1900. Además, el dispositivo 2000 puede emplearse como un nodo, como los nodos 111, 211, 212, 213, 311, 312, 400, 1311, 1312 y/o 1333, en una red IGP, como la red IGP 100, 200, 300 y/o 1300. El dispositivo 2000 puede emplearse en redes OSPF y/o IGP y, por lo tanto, puede emplearse junto con la codificación 1400, 1500 y/o 1600. El dispositivo 2000 puede emplearse para construir una topología de inundación, por ejemplo, empleando los métodos 500, 600 y/o 700. El dispositivo 2000 también puede emplear mecanismos de inundación, como los mecanismos de inundación 800, 900, 1000, 1100 y/o 1200. El dispositivo 2000 también puede controlarse mediante la recepción de una codificación TLV de control LSFR 1700.

El dispositivo 2000 incluye un módulo de recepción 2001, que es un medio para recibir datos que indican la conectividad de una pluralidad de nodos en la red, incluido el primer nodo. El dispositivo 2000 incluye un módulo de construcción de topología de inundación 2003, que es un medio para construir una topología de inundación con base en la conectividad seleccionando uno de los nodos como nodo raíz y construir un árbol de enlaces que conectan el nodo raíz con los nodos en la red. El dispositivo 2000 incluye un módulo de almacenamiento 2005, que es un medio para almacenar la topología de inundación sin transmitir la topología de inundación a la pluralidad de nodos en la red. El dispositivo 2000 también incluye un módulo de inundación 2007, que es un medio para transmitir mensajes de estado de enlace sobre la topología de inundación.

En una modalidad, un primer nodo en una red incluye medios de recepción para recibir datos que indican la conectividad de una pluralidad de nodos en la red que incluye el primer nodo. El primer nodo incluye además medios de construcción para construir, mediante un procesador del primer nodo, una topología de inundación con base en la conectividad seleccionando uno de los nodos como nodo raíz, construyendo un árbol de enlaces que conectan el nodo raíz con los nodos en la red, almacenando la topología de inundación en una memoria sin transmitir la topología de inundación a la pluralidad de nodos en la red e inundando con mensajes de estado de enlace sobre la topología de inundación.

Un primer componente se acopla directamente a un segundo componente cuando no hay componentes intermedios, a excepción de una línea, un trazo u otro medio entre el primer componente y el segundo componente. El primer componente se acopla indirectamente al segundo componente cuando hay componentes intermedios distintos de una línea, un trazo u otro medio entre el primer componente y el segundo componente. El término "acoplado" y sus variantes incluyen tanto los acoplados directamente como los acoplados indirectamente. El uso del término "aproximadamente" significa un rango que incluye ±10 % del número subsiguiente a menos que se indique lo contrario.

Si bien se han proporcionado varias modalidades en la presente divulgación, puede entenderse que los sistemas y métodos divulgados podrían incorporarse de muchas otras formas específicas sin apartarse del espíritu o alcance de la presente divulgación. Los presentes ejemplos deben considerarse ilustrativos y no restrictivos, y la intención no se limita a los detalles ofrecidos en el presente documento. Por ejemplo, los diversos elementos o componentes se pueden combinar o integrar en otro sistema o se pueden omitir o no implementarse determinadas características.

Claims

REIVINDICACIONES

1. Un método implementado en un primer nodo en una red, el método que comprende:

recibir, en un receptor del primer nodo, datos que indican la conectividad de una pluralidad de nodos en la red que incluye el primer nodo;

construir, por parte de un procesador del primer nodo, una topología de inundación con base en la conectividad al:

seleccionar uno de los nodos como nodo raíz, y

construir un árbol de enlaces que conectan el nodo raíz con los nodos de la red de acuerdo con un algoritmo, en donde el algoritmo está contenido en un campo de algoritmo de un mensaje de estado de enlace recibido;

almacenar la topología de inundación en una memoria; y

inundar, por parte de un transmisor del primer nodo, mensajes de estado de enlace sobre la topología de inundación.

2. El método de acuerdo con la reivindicación 1 que comprende, además:

recibir, en el receptor, una solicitud que especifica un número de enlaces de hoja para agregar al árbol; y agregar a la topología de inundación, por parte del procesador, el número de enlaces de hoja entre los nodos de la red.

3. El método de cualquiera de las reivindicaciones 1-2, en donde, antes de agregar enlaces de hoja, el árbol de enlaces en la topología de inundación contiene un número mínimo de enlaces para conectar todos los nodos en la red al nodo raíz.

4. El método de cualquiera de las reivindicaciones 1-3, que comprende, además:

establecer, por parte del procesador, una adyacencia con un nodo recién conectado, en donde el nodo recién conectado está directamente conectado al primer nodo a través de un enlace; y

agregar, por parte del procesador, el nodo recién conectado al árbol de enlaces en la topología de inundación hasta que se vuelve a calcular la topología de inundación.

5. El método de cualquiera de las reivindicaciones 1-4, que comprende, además:

recibir, en el receptor, un primer mensaje de estado de enlace a través de un enlace que está excluido de la topología de inundación; y

inundar, por parte del transmisor, el primer mensaje de estado de enlace a través de enlaces en la topología de inundación.

6. El método de cualquiera de las reivindicaciones 1-5, que comprende, además:

recibir, en el receptor, un segundo mensaje de estado de enlace que indica que un segundo nodo en la red está inactivo; e

inundar, por parte del transmisor, el segundo mensaje de estado de enlace a enlaces que se conectan entre el primer nodo y los vecinos del segundo nodo.

7. El método de cualquiera de las reivindicaciones 1-6, que comprende, además:

recibir, en el receptor, un tercer mensaje de estado de enlace que indica que un primer enlace en la red está inactivo;

determinar que el primer enlace es un elemento crítico; y

con base en la determinación, enviar el mensaje de estado del tercer enlace a enlaces que se conectan a vecinos que también conectan nodos adyacentes a un nodo unido al primer enlace.

8. El método de cualquiera de las reivindicaciones 1-7, que comprende, además:

determinar, por parte del procesador, elementos críticos, en donde un elemento crítico es un enlace o nodo cuyo fallo divide la topología de inundación; y

suspender el uso de la topología de inundación cuando falla una interfaz crítica.

9. El método de cualquiera de las reivindicaciones 1-8, en donde los mensajes de estado de enlace contienen indicaciones de reducción de inundación (F) establecidas para indicar los nodos en la red que admiten la reducción de inundación de estado de enlace a través de la topología de inundación.

10. El método de cualquiera de las reivindicaciones 1-9, en donde los mensajes de estado de enlace contienen un campo de modo establecido para indicar reducción de inundación de estado de enlace centralizada, reducción de inundación de estado de enlace distribuida o reducción de inundación de estado de enlace configurada estáticamente.

11. El método de cualquiera de las reivindicaciones 1-10, en donde los mensajes de estado de enlace contienen un conjunto de campos de algoritmo para indicar un algoritmo para construir el árbol de enlaces en la topología de inundación.

12. El método de cualquiera de las reivindicaciones 1-11, en donde los mensajes de estado de enlace contienen un campo de operación (OP) establecido para cambiar a reducción de inundación de estado de enlace desde inundación de red completa.

13. Un primer nodo en una red, el primer nodo que comprende:

un receptor configurado para recibir datos que indican la conectividad de una pluralidad de nodos en la red que incluye el primer nodo;

un procesador acoplado al receptor, el procesador configurado para:

construir una topología de inundación con base en la conectividad al:

seleccionar uno de los nodos como nodo raíz, y

construir un árbol de enlaces que conectan el nodo raíz con los nodos de la red de acuerdo con un algoritmo, en donde el algoritmo está contenido en un

campo de algoritmo de un mensaje de estado de enlace recibido;

una memoria acoplada al procesador, la memoria configurada para almacenar la topología de inundación; y un transmisor acoplado al procesador, el transmisor configurado para inundar mensajes de estado de enlace sobre la topología de inundación.

14. El primer nodo de la reivindicación 13, en donde el receptor está además configurado para recibir una solicitud que especifica un número de enlaces de hoja para agregar al árbol, y en donde el procesador está configurado además para agregar a la topología de inundación el número de enlaces de hoja entre los nodos en la red.

15. El primer nodo de la reivindicación 13 o 14, en donde, antes de agregar enlaces de hoja, el árbol de enlaces en la topología de inundación contiene un número mínimo de enlaces para conectar todos los nodos de la red al nodo raíz.

16. Un medio legible por ordenador no transitorio que comprende un producto de programa de ordenador para uso del primer nodo en la red, el producto de programa de ordenador que comprende instrucciones ejecutables por ordenador almacenadas en el medio legible por ordenador no transitorio de manera que cuando se ejecuta por un procesador hace que el primer nodo realice el método de cualquiera de las reivindicaciones 1-12.