Algoritmo de actualización por difusión

El algoritmo de actualización difusa ( DUAL ) es el algoritmo utilizado por el protocolo de enrutamiento EIGRP de Cisco ^{[ 1 ]} para garantizar que una ruta determinada se recalcule globalmente siempre que pueda causar un bucle de enrutamiento . Fue desarrollado por JJ Garcia-Luna-Aceves en SRI International . El nombre completo del algoritmo es máquina de estados finitos DUAL (DUAL FSM). EIGRP es responsable del enrutamiento dentro de un sistema autónomo , y DUAL responde a los cambios en la topología de enrutamiento y ajusta dinámicamente las tablas de enrutamiento del enrutador automáticamente.

EIGRP utiliza una condición de viabilidad para garantizar que solo se seleccionen rutas libres de bucles. Esta condición es conservadora: cuando se cumple, no pueden producirse bucles, pero en determinadas circunstancias podría rechazar todas las rutas hacia un destino, aunque algunas estén libres de bucles.

Cuando no existe una ruta factible hacia un destino, el algoritmo DUAL ^{[ 2 ]} invoca un cálculo de difusión ^{[ 3 ]} para asegurar que se eliminen de la red todos los rastros de la ruta problemática. En ese momento, se utiliza el algoritmo Bellman-Ford convencional para recuperar una nueva ruta.

DUAL utiliza tres tablas independientes para el cálculo de rutas. Estas tablas se crean a partir de la información intercambiada entre los routers EIGRP. Dicha información difiere de la que intercambian los protocolos de enrutamiento de estado de enlace . En EIGRP, la información intercambiada incluye las rutas, la métrica o coste de cada ruta y la información necesaria para establecer una relación de vecindad (como el número de sistema autónomo, los temporizadores y los valores K). Las tres tablas y sus funciones se describen en detalle a continuación:

• La tabla de vecinos contiene información sobre todos los demás enrutadores conectados directamente. Existe una tabla independiente para cada protocolo compatible (IP, IPX, etc.). Cada entrada corresponde a un vecino con la descripción de la interfaz de red y la dirección. Además, se inicializa un temporizador para comprobar periódicamente si la conexión está activa. Esto se logra mediante paquetes "Hello" . Si no se recibe un paquete "Hello" de un vecino durante un período de tiempo determinado, se asume que el enrutador está inactivo y se elimina de la tabla de vecinos.
• La tabla de topología contiene la métrica (información de costo) de todas las rutas a cualquier destino dentro del sistema autónomo. Esta información se recibe de los enrutadores vecinos que se encuentran en la tabla de vecinos. Las rutas primaria (sucesor) y secundaria (sucesor factible) a un destino se determinarán con la información de la tabla de topología. Entre otras cosas, cada entrada en la tabla de topología contiene lo siguiente:

"FD (Distancia Factible)": La métrica calculada de una ruta a un destino dentro del sistema autónomo.

"RD (Distancia Informada)": La métrica a un destino según lo anunciado por un enrutador vecino. La RD se utiliza para calcular la FD y para determinar si la ruta cumple con la "condición de viabilidad".

Estado de la ruta : Una ruta se marca como "activa" o "pasiva". Las rutas "pasivas" son estables y se pueden usar para la transmisión de datos. Las rutas "activas" se están recalculando o no están disponibles.

• La tabla de enrutamiento contiene la(s) mejor(es) ruta(s) hacia un destino (en términos de la "métrica" ​​más baja). Estas rutas son las sucesoras de la tabla de topología.

DUAL evalúa los datos recibidos de otros enrutadores en la tabla de topología y calcula las rutas primaria (sucesora) y secundaria (sucesora factible). La ruta primaria suele ser la que tiene la métrica más baja para llegar al destino, y la ruta redundante es la que tiene el segundo costo más bajo (si cumple la condición de factibilidad). Puede haber múltiples sucesores y múltiples sucesores factibles. Tanto los sucesores como los sucesores factibles se mantienen en la tabla de topología, pero solo los sucesores se agregan a la tabla de enrutamiento y se utilizan para enrutar paquetes.

Para que una ruta sea considerada sucesora viable, su RD debe ser menor que el FD de la ruta sucesora. Si se cumple esta condición de viabilidad, añadir esta ruta a la tabla de enrutamiento no provocará un bucle.

Si todas las rutas sucesoras hacia un destino fallan, la ruta sucesora factible se convierte en la ruta sucesora y se agrega inmediatamente a la tabla de enrutamiento. Si no hay ninguna ruta sucesora factible en la tabla de topología, se inicia un proceso de consulta para buscar una nueva ruta.

Leyenda:

+ = Enrutador

− o | = Enlace

(X) = Métrica del enlace

 A (2) B (1) C + - - - - + - - - - - + | | (2) | | (3) | | + - - - - - + D (1) E

Ahora, un cliente en el enrutador E quiere comunicarse con un cliente en el enrutador A. Esto significa que debe existir una ruta entre el enrutador A y el enrutador E. Esta ruta se calcula de la siguiente manera:

Los vecinos inmediatos del enrutador E son el enrutador C y el enrutador D. El comando DUAL en el enrutador E solicita la distancia reportada (RD) desde los enrutadores C y D, respectivamente, hasta el enrutador A. Los resultados son los siguientes:

Destino: Enrutador A

vía D: RD(4)

vía C: RD(3)

Por lo tanto, la ruta a través de C es la de menor coste. En el siguiente paso, se añade la distancia desde el router E a los vecinos a la distancia informada para obtener la distancia factible (FD):

Destino: Enrutador A

vía D: RD(4), FD(5)

vía C: RD(3), FD(6)

Por lo tanto, DUAL determina que la ruta a través de D tiene el menor costo total. En consecuencia, la ruta a través de D se marcará como "sucesora", se le asignará el estado pasivo y se registrará en la tabla de enrutamiento. La ruta a través de C se mantiene como "sucesora factible", ya que su RD es menor que el FD de la sucesora.

Destino: Enrutador A

vía D: RD(4), sucesor FD(5)

vía C: RD(3), FD(6) sucesor factible