Vector das distâncias

ALGORITMO DO VECTOR
DAS DISTÂNCIAS
Gabriel Santos

VECTOR DAS DISTÂNCIAS

Cada router mantém uma tabela (ou vector) que fornece a melhor distância conhecida até cada destino;
As tabelas são actualizadas através de troca de mensagens com seus routers vizinhos.
Pode-se representar essa rede usando um grafo em que os nós correspondem aos routers se os dois routers estiverem conectados directamente por um link.

VECTOR DAS DISTÂNCIAS

O custo da aresta representa o atraso no link (v,w); o menor caminho é aquele que minimiza o atraso entre uma fonte s e um destino t. Para isso, podemos usar o algoritmo de
Bellman-Ford, já que ele utiliza apenas conhecimentos locais dos nós vizinhos - suponha que o nó v mantém seu valor de menor distância a t igual a M[v]; então, para actualizar esse valor, v só precisa obter o valor de M[w] de cada vizinho w e computar min(P(v,w)+M[w]) baseado nas informações obtidas, onde P(v,w) é o atraso do link entre v e w.

VECTOR DAS DISTÂNCIAS

Entretanto, esse algoritmo pode ser melhorado de forma que se torna melhor para aplicar a routers e, ao mesmo tempo, um algoritmo mais rápido, na prática.
Em cada iteração i, cada nó v tinha que entrar em contacto com cada vizinho w e 'puxar' o novo valor M[w] ('pull-based implementation'). Se um nó w não mudar o seu valor, então não há necessidade de v apanhar o valor M[w] novamente; porém, pelo algoritmo de Bellman-Ford, não tem como v saber isso e ele 'puxará' esse valor de qualquer maneira.

VECTOR DAS DISTÂNCIAS

Esse desperdício sugere uma 'Push-based implementation', onde o valor é apenas transmitido quando sofre alguma mudança. Ou seja, cada nó w cujo valor da distância é alterado em alguma iteração informa seu novo valor a todos os vizinhos na próxima iteração; isso permite que os vizinhos actualizem seus valores de acordo com a mudança que w sofreu.
Se M[w] não mudou, então os vizinhos de w já tem o seu valor e não há necessidade de