Antes de comezar a ler este artigo, aconsellamos a familiarizarse co material sobre o cálculo do camiño segundo o algoritmo de Bellman - Ford.
O algoritmo de actualización de difusión (difusión de algoritmos de actualización -dual) é un dos dous algoritmos discutidos aquí orixinalmente destinados á implementación nunha rede distribuída. É único porque tamén elimina información sobre a obtención e topoloxía contida na automatización final do algoritmo. Outros algoritmos discutidos aquí abandonan a eliminación da información a discreción da implementación do Protocolo e non consideran este aspecto do traballo do algoritmo dentro do propio algoritmo.
En 1993, Bellman-Ford e Dijkstra foron implementados como algoritmos distribuídos en varios protocolos de enrutamento. A experiencia gañada como resultado destas implementacións e implementacións precoz levou á "segunda onda" de investigación e reflexión sobre o problema do enrutamento en redes de conmutación de rede, que levaron á aparición do vector do camiño e dobre.
Xa que Dual está deseñado como algoritmo distribuído, o mellor é describir o seu traballo na rede. Para este propósito, úsanse figuras 8 e 9. Para explicar dual, este exemplo será trazado nun fluxo de tres destinos e, a continuación, os cambios son procesados no estado de dispoñibilidade para os mesmos elementos de destino. No primeiro exemplo, o caso será considerado cando hai un camiño alternativo, pero non hai veciño de Downstream, o segundo considerará o caso cando hai un camiño alternativo e un veciño de Downstream.
Na Figura 8, estudo D desde o punto de vista a:
- A Aprende dúas maneiras de D:
- A non recoñecerá o camiño a través de B, porque B usa un como o seu sucesor:
- A compara as rutas dispoñibles e selecciona o camiño máis curto sen loops:
- A comproba os camiños restantes para determinar se hai algún dos veciños máis baixos:
A sabe isto porque C anuncia a ruta a D coa súa métrica local igual a 3.
A mantén unha métrica local C na súa táboa de topoloxía.
En consecuencia, un coñece o valor local en C e o valor local en A.
- 3 (custo en c) = 3 (custo nun), polo que esta ruta pode ser loop, polo tanto, C non satisfai a condición de viabilidade. C non está etiquetado como veciños downstream.
Os veciños downstream en dobre chámanse posibles sucesores. Supoña que a canle [a, h] non funciona. Dual non depende das actualizacións periódicas, polo que non só pode esperar a outra actualización con información confiable. Pola contra, un debe seguir activamente un camiño alternativo. Así, este é un proceso de detección difusa dun camiño alternativo. Se a canle [a, h] non funciona, considerando só D:
- A comproba a túa táboa local para posibles sucesores (veciños downstream).
- Non hai posibles sucesores, polo que é imprescindible atopar un camiño alternativo sen loops a D (se existe).
- A envía unha solicitude a cada veciño para determinar se hai algún camiño alternativo sen loops a D.
- En C:
- En B:
- A obtén estas respostas:
Na Figura 9, o elemento de destino (d) foi movido con H a E. Isto empregarase no segundo exemplo.
Neste exemplo, hai un posible sucesor (veciño de Downstream).
Estudo D desde o punto de vista a:
- A Aprende dúas maneiras de D:
- A non recoñecerá a través de B:
- A compara as rutas dispoñibles e selecciona o camiño máis curto sen loops:
- A comproba os camiños restantes para determinar se hai algún dos veciños máis baixos:
Se a canle [a, c] non funciona, simplemente tendo en conta un:
- Un cheque a súa táboa de topoloxía local para un posible sucesor.
- Existe o posible sucesor a través de H.
- A cambia a súa mesa local en H como o mellor xeito.
- A envía unha actualización aos seus veciños, observando que o seu custo de logro D cambiou de 3 a 4.
Como podes ver, procesar cando hai un posible sucesor, moito máis rápido e máis fácil que sen el. Nas redes onde o protocolo de enrutamento foi despregado usando dobre (en particular, EIGRP), un dos principais obxectivos de deseño limitará o volume de calquera solicitude xerada en ausencia dun posible sucesor. A área de solicitude é o principal factor determinante como se completa o algoritmo dobre e, polo tanto, a rapidez con que a rede converte a rede.
A Figura 10 mostra a máquina Dual acabada básica.
As cousas incluídas na ruta empeoran (a degradación da ruta) pode ser:
- Fallo da canle conectada ou o veciño
- Obtención dunha actualización para unha ruta cunha métrica superior
- Obter unha consulta do sucesor actual
- Obter unha nova ruta dun veciño
- Atopouse un novo veciño, así como rutas polo que pode conseguir
- Obtendo todas as solicitudes enviadas a veciños cando a ruta empeora
