Algoritmos DV

Algoritmos DV são também conhecidos como algoritmos de roteamento Bellman-Ford e algoritmos de roteamento Ford-Fulkerson. Nestes algoritmos, cada roteador possui uma tabela de roteamento que mostra o melhor caminho para cada destino. Um grafo e uma tabela de roteamento típicos para o roteador J são mostrados abaixo.


Destino
Peso
Linha
A
8
A
B
20
A
C
28
I
D
20
H
E
17
I
F
30
I
G
18
H
H
12
H
I
10
I
J
0
---
K
6
K
L
15
K

Um  diagrama de rede e tabela de roteamento para um roteador J

Como a tabela mostra, se o roteador J quer enviar um pacote de dados ao roteador D, ele pode enviá-lo para o H. Quando o pacote chegar ao roteador H, ele verifica sua própria tabela e decide como enviar o pacote para D.

Nos algoritmos DV, cada roteador deve seguir alguns procedimentos.

  1. Ele conta o peso dos enlaces conectados diretamente a ele e salva a informação na sua tabela.
  2. Num determinado período de tempo, ele envia sua tabela ao roteador vizinho (não para todos os roteadores) e recebe a tabela de roteamento de cada um de seus vizinhos.
  3. Baseado na informação das tabelas de roteamento de seus vizinhos, ele atualiza a sua.
Um dos mais importantes problemas com o algoritmo DV é chamado "contagem ao infinito". Vamos examinar este problema com um exemplo:

Imagine uma rede com um diagrama como o mostrado abaixo. Como vemos, há somente uma ligação entre A e a outra parte da rede. Aqui podemos ver o grafo e a tabela de roteamento de todos os nós:


A
B
C
D
A
0,-
1,A
2,B
3,C
B
1,B
0,-
2,C
3,D
C
2,B
1,C
0,-
1,C
D
3,B
2,C
0,-
0,-

Diagrama e tabela de roteamento da rede

Imagine que o enlace entre A e B está cortado. Neste momento, B corrige sua tabela. Após um intervalo de tempo específico, os roteadores trocam suas tabelas, e B recebe a tabela de roteamento de C. Desde que C não saiba o que aconteceu ao enlace entre A e B, ele diz ter um enlace com A com o peso de 2 (1 de C para B, e 1 de B para A. Ele não sabe que B não tem um enlace com A). B recebe esta tabela e pensa que existe um enlace isolado entre C e A, então ele corrige sua tabela e alterando de infinito para 3 (1 de B para C e 2 de C para A, como disse C). Uma vez mais, roteadores trocam suas tabelas. Quando C recebe a tabela de roteamento de B, ele vê que B alterou o peso de seu enlace de A de 1 para 3, então C atualiza sua tabela e altera o peso da ligação de A para 4 (1 de C para B, e 3 de B para A, como disse B).

Este processo se repete até que todos os nós descubram que o peso da ligação A é infinito. Esta situação é mostrada na tabela abaixo. Desta forma, especialistas dizem que o algoritmo DV possui uma baixa taxa de convergência.

B
C
D
Soma do peso de A após corte da ligação
,A
2,B
3,C
Soma do peso de B após a primeira atualização
3,C
2,B
3,C
Soma do peso de A após segunda atualização
3,C
4,B
3,C
Soma do peso de A após terceira atualização
5,C
4,B
5,C
Soma do peso de A após quarta atualização
5,C
6,B
5,C
Soma do peso de A após quinta atualização
7,C
6,B
7,C
Soma do peso de A após enésima atualização
...
...
...

O problema da "contagem ao infinito"

Uma maneira de resolver este problema é os roteadores enviarem informações somente aos vizinhos que não estão exclusivamente ligados ao destino. Por exemplo, neste caso, C não deveria enviar qualquer informação para B sobre A, porque B é o único caminho para A.