Antes de começar a ler este artigo, aconselhamos que você se familiarize com o material sobre o cálculo do caminho de acordo com o Algoritmo do Bellman - Ford.
O algoritmo de atualização de difusão (algoritmo de atualização de difusão -Dual) é um dos dois algoritmos discutidos aqui originalmente destinado a implementação em uma rede distribuída. É único em que também remove informações sobre a realização e a topologia contidas nos autômatos finais do algoritmo. Outros algoritmos discutidos aqui deixam a remoção de informações a critério da implementação do Protocolo, e não considerar esse aspecto do trabalho do algoritmo dentro do próprio algoritmo.
Em 1993, Bellman-ford e Dijkstra foram implementados como algoritmos distribuídos em vários protocolos de roteamento. A experiência adquirida como resultado dessas implementações e implantações iniciais levaram à "segunda onda" de pesquisa e reflexão sobre o problema do roteamento nas redes de comutação de rede, que levaram à aparência do vetor de caminho e dupla.
Como Dual é projetado como algoritmo distribuído, é melhor descrever seu trabalho na rede. Para isso, as Figuras 8 e 9 são usadas. Para explicar dual, este exemplo será rastreado em um fluxo de três destinos e, em seguida, as alterações são processadas no estado de disponibilidade para os mesmos itens de destino. No primeiro exemplo, o caso será considerado quando há um caminho alternativo, mas não há vizinho a jusante, o segundo considerará o caso quando há um caminho alternativo e o vizinho a jusante.
Na Figura 8, estude D do ponto de vista A:
- A aprende duas maneiras de d:
- A não reconhecerá o caminho através de B, porque B usa um como seu sucessor:
- A compara os caminhos disponíveis e seleciona o caminho mais curto sem loops:
- Um verifica os caminhos restantes para determinar se há algum deles vizinhos a jusante:
A sabe disso porque C anuncia a rota para D com sua métrica local igual a 3.
A mantém uma métrica local C em sua tabela de topologia.
Consequentemente, a conhece o valor local em C e o valor local em A.
- 3 (Custo em C) = 3 (custo em A), portanto, esta rota pode ser loop, portanto, C não satisfaz a condição de viabilidade. C não é rotulado como vizinhos a jusante.
Os vizinhos a jusante em Dual são chamados possíveis sucessores. Suponha que o canal [A, H] não funcione. Dual não confia em atualizações periódicas, portanto, não pode esperar outra atualização com informações confiáveis. Em vez disso, um deve ativar ativamente um caminho alternativo. Assim, este é um processo difuso de detecção de um caminho alternativo. Se o canal [A, H] não funcionar, considerando apenas D:
- Um verifica sua tabela local para possíveis sucessores (vizinhos a jusante).
- Não há sucessores possíveis, então um deve encontrar um caminho alternativo sem loops para D (se existir).
- A envia uma solicitação para cada vizinho para determinar se há algum caminho alternativo sem loops para D.
- Em C:
- Em B:
- A obtém essas respostas:
Na Figura 9, o item de destino (D) foi movido com H para E. Isso será usado no segundo exemplo.
Neste exemplo, há um possível sucessor (vizinho a jusante).
Estudo D do ponto de vista A:
- A aprende duas maneiras de d:
- A não reconhecerá de acordo com B:
- A compara os caminhos disponíveis e seleciona o caminho mais curto sem loops:
- Um verifica os caminhos restantes para determinar se há algum deles vizinhos a jusante:
Se o canal [A, C] não funcionar, simplesmente considerando um:
- Um verifica sua tabela de topologia local para um possível sucessor.
- Possível sucessor existe através de H.
- A alterna sua mesa local em h como a melhor maneira.
- A envia uma atualização para seus vizinhos, observando que seu custo de realização D mudou de 3 a 4.
Como você pode ver, processar quando há um possível sucessor, muito mais rápido e mais fácil do que sem isso. Em redes onde o protocolo de roteamento foi implantado usando Dual (em particular, EIGRP), um dos principais objetivos de design limitará o volume de quaisquer solicitações geradas na ausência de um possível sucessor. A área de solicitação é o principal fator determinante como o algoritmo duplo é preenchido rapidamente e, portanto, a rapidez com que a rede converge.
A figura 10 mostra a máquina dupla terminada básica.
As coisas incluídas na rota pioram (a degradação da rota) pode ser:
- Falha do canal ou vizinho conectado
- Obtendo uma atualização para uma rota com uma métrica mais alta
- Obtendo uma consulta do sucessor atual
- Obtendo uma nova rota de um vizinho
- Um novo vizinho foi encontrado, bem como rotas pelo qual pode obter
- Obtendo todas as solicitações enviadas aos vizinhos quando a rota piora
