Antes de comenzar a leer este artículo, le aconsejamos que se familiarice con el material sobre el cálculo del camino de acuerdo con el Bellman - Ford Algorithm.
El algoritmo de actualización de difusión (álgoritmo de actualización difusor -dual) es uno de los dos algoritmos discutidos aquí originalmente destinados a la implementación en una red distribuida. Es único, ya que también elimina la información sobre la capacidad de alcance y la topología contenida en la autómata final del algoritmo. Otros algoritmos discutidos aquí dejaron la eliminación de la información a discreción de la implementación del protocolo, y no consideran este aspecto del trabajo del algoritmo dentro del algoritmo en sí.
Para 1993, Bellman-Ford y Dijkstra se implementaron como algoritmos distribuidos en varios protocolos de enrutamiento. La experiencia obtenida como resultado de estas implementaciones y implementaciones tempranas condujo a la "segunda ola" de investigación y reflexión sobre el problema del enrutamiento en las redes de conmutación de red, lo que llevó a la apariencia del vector de la ruta y la doble.
Dado que Dual está diseñado como un algoritmo distribuido, es mejor describir su trabajo en la red. Para este propósito, se utilizan las figuras 8 y 9. Para explicar dual, este ejemplo se rastreará en una corriente de tres destinos, y luego los cambios se procesan en el estado de disponibilidad para los mismos elementos de destino. En el primer ejemplo, el caso se considerará cuando haya un camino alternativo, pero no hay un vecino en sentido descendente, el segundo considerará el caso cuando haya un camino alternativo y al vecino corriente abajo.
En la Figura 8, estudio d desde el punto de vista A:
- A aprende dos formas de D:
- A no reconocerá el camino a través de B, porque B usa A como su sucesor:
- A compara las rutas disponibles y selecciona la ruta más corta sin bucles:
- A comprueba los caminos restantes para determinar si hay alguno de ellos vecinos aguas abajo:
A sabe esto porque C anuncia la ruta a D con su métrica local igual a 3.
A mantiene una métrica local C en su tabla de topología.
En consecuencia, A conoce el valor local en C y el valor local en A.
- 3 (Costo en C) = 3 (Costo en a), por lo que esta ruta puede estar bucle, por lo tanto, C no satisface la condición de viabilidad. C no está etiquetado como vecinos aguas abajo.
Los vecinos aguas abajo en Dual se llaman posibles sucesores. Supongamos que el canal [A, H] no funciona. Dual no confía en las actualizaciones periódicas, por lo que no puede simplemente esperar otra actualización con información confiable. Más bien, una debe seguir activamente un camino alternativo. Por lo tanto, este es un proceso de detección difuso de un camino alternativo. Si el canal [A, H] no funciona, considerando SOLAMENTE D:
- A comprueba su mesa local para posibles sucesores (vecinos aguas abajo).
- No hay posibles sucesores, por lo que debe encontrar una trayectoria alternativa sin bucles a D (si existe).
- A envía una solicitud a cada vecino para determinar si hay algún camino alternativo sin bucles a D.
- C ª:
- En b:
- A obtiene estas respuestas:
En la Figura 9, el elemento Destino (D) se movió con H a E. Esto se utilizará en el segundo ejemplo.
En este ejemplo, hay un posible sucesor (vecino aguas abajo).
Estudiar D desde el punto de vista A:
- A aprende dos formas de D:
- A no reconocerá ninguna forma a través de B:
- A compara las rutas disponibles y selecciona la ruta más corta sin bucles:
- A comprueba los caminos restantes para determinar si hay alguno de ellos vecinos aguas abajo:
Si el canal [A, C] no funciona, simplemente considerando A:
- A comprueba su tabla de topología local para un posible sucesor.
- Existe posible sucesor a través de H.
- A cambia su mesa local en H como la mejor manera.
- A envía una actualización a sus vecinos, señalando que su costo de logro D ha cambiado de 3 a 4.
Como puede ver, procesando cuando haya un posible sucesor, mucho más rápido y más fácil que sin él. En las redes donde se implementó el protocolo de enrutamiento utilizando DUAL (en particular, EIGRP), uno de los principales objetivos de diseño limitará el volumen de cualquier solicitud generada en ausencia de un posible sucesor. El área de solicitud es el principal factor determinante de cómo se completa rápidamente el algoritmo doble y, por lo tanto, la rapidez converge la red.
La figura 10 muestra la máquina dual terminada básica.
Las cosas incluidas en la ruta empeoran (la degradación de la ruta) puede ser:
- Fallo del canal o vecino conectado
- Obtención de una actualización para una ruta con una métrica más alta.
- Obtención de una consulta del sucesor actual
- Obteniendo una nueva ruta de un vecino
- Se encontró un nuevo vecino, así como las rutas por las cuales puede obtener
- Obteniendo todas las solicitudes enviadas a los vecinos cuando la ruta empeora
