TechCodeview

O algoritmo do vetor Distância é iterativo, assíncrono e distribuído.
Distribuído:É distribuído na medida em que cada nó recebe informações de um ou mais de seus vizinhos diretamente conectados, realiza cálculos e então distribui o resultado de volta aos seus vizinhos.Iterativo:É iterativo porque seu processo continua até que não haja mais informações disponíveis para serem trocadas entre vizinhos.Assíncrono:Não requer que todos os seus nós operem na etapa de bloqueio entre si.
• O algoritmo de vetor de distância é um algoritmo dinâmico.
• É usado principalmente em ARPANET e RIP.
• Cada roteador mantém uma tabela de distância conhecida como Vetor .

Três chaves para entender o funcionamento do algoritmo de roteamento vetorial de distância:

Conhecimento sobre toda a rede:Cada roteador compartilha seu conhecimento por toda a rede. O roteador envia o conhecimento coletado sobre a rede para seus vizinhos.Roteamento apenas para vizinhos:O roteador envia seu conhecimento sobre a rede apenas para os roteadores que possuem links diretos. O roteador envia tudo o que possui sobre a rede através das portas. As informações são recebidas pelo roteador e as utilizam para atualizar sua própria tabela de roteamento.Compartilhamento de informações em intervalos regulares:Dentro de 30 segundos, o roteador envia as informações para os roteadores vizinhos.

Algoritmo de roteamento de vetor de distância

Deixe d_x(y) seja o custo do caminho de menor custo do nó x ao nó y. Os menores custos são relacionados pela equação de Bellman-Ford,

 d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} 

Onde o minv é a equação adotada para todos os x vizinhos. Depois de viajar de x para v, se considerarmos o caminho de menor custo de v para y, o custo do caminho será c(x,v)+d_em(s). O menor custo de x a y é o mínimo de c(x,v)+d_em(y) assumiu todos os vizinhos.

Com o algoritmo Distance Vector Routing, o nó x contém as seguintes informações de roteamento:

• Para cada vizinho v, o custo c(x,v) é o custo do caminho de x até o vizinho diretamente conectado, v.
• O vetor de distância x, ou seja, D_x= [ D_x(y): y em N], contendo seu custo para todos os destinos, y, em N.
• O vetor de distância de cada um de seus vizinhos, ou seja, D_em= [ D_em(y): y em N] para cada vizinho v de x.

O roteamento de vetor de distância é um algoritmo assíncrono no qual o nó x envia a cópia de seu vetor de distância para todos os seus vizinhos. Quando o nó x recebe o novo vetor de distância de um de seus vetores vizinhos, v, ele salva o vetor de distância de v e usa a equação de Bellman-Ford para atualizar seu próprio vetor de distância. A equação é dada abaixo:

linux editar um arquivo

 d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N 

O nó x atualizou sua própria tabela de vetores de distância usando a equação acima e envia sua tabela atualizada a todos os seus vizinhos para que eles possam atualizar seus próprios vetores de distância.

Algoritmo

 At each node x, <p> <strong>Initialization</strong> </p> for all destinations y in N: D<sub>x</sub>(y) = c(x,y) // If y is not a neighbor then c(x,y) = &#x221E; for each neighbor w D<sub>w</sub>(y) = ? for all destination y in N. for each neighbor w send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to w <strong>loop</strong> <strong>wait</strong> (until I receive any distance vector from some neighbor w) for each y in N: D<sub>x</sub>(y) = minv{c(x,v)+D<sub>v</sub>(y)} If D<sub>x</sub>(y) is changed for any destination y Send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to all neighbors <strong>forever</strong> 

Nota: No algoritmo de vetor de distância, o nó x atualiza sua tabela quando vê qualquer mudança de custo em um nó diretamente vinculado ou recebe qualquer atualização de vetor de algum vizinho.

Vamos entender através de um exemplo:

Partilhando informação

• Na figura acima, cada nuvem representa a rede e o número dentro da nuvem representa o ID da rede.
• Todas as LANs são conectadas por roteadores e são representadas em caixas rotuladas como A, B, C, D, E, F.
• O algoritmo de roteamento de vetor de distância simplifica o processo de roteamento assumindo que o custo de cada link é de uma unidade. Portanto, a eficiência da transmissão pode ser medida pelo número de links para chegar ao destino.
• No roteamento de vetor de distância, o custo é baseado na contagem de saltos.

Na figura acima, observamos que o roteador envia o conhecimento para os vizinhos imediatos. Os vizinhos somam esse conhecimento ao seu próprio conhecimento e enviam a tabela atualizada para seus próprios vizinhos. Dessa forma, os roteadores obtêm suas próprias informações, além de novas informações sobre os vizinhos.

Tabela de roteamento

Dois processos ocorrem:

• Criando a Tabela
• Atualizando a Tabela

Criando a Tabela

Inicialmente, é criada a tabela de roteamento para cada roteador que contém pelo menos três tipos de informações como ID da rede, custo e próximo salto.

ID REDE:O ID da rede define o destino final do pacote.Custo:O custo é o número de saltos que o pacote deve realizar para chegar lá.Próximo salto:É o roteador ao qual o pacote deve ser entregue.

• Na figura acima, são mostradas as tabelas de roteamento originais de todos os roteadores. Em uma tabela de roteamento, a primeira coluna representa o ID da rede, a segunda coluna representa o custo do link e a terceira coluna está vazia.
• Essas tabelas de roteamento são enviadas a todos os vizinhos.

Por exemplo:

 A sends its routing table to B, F & E. B sends its routing table to A & C. C sends its routing table to B & D. D sends its routing table to E & C. E sends its routing table to A & D. F sends its routing table to A. 

Atualizando a Tabela

• Quando A recebe uma tabela de roteamento de B, ele usa suas informações para atualizar a tabela.
• A tabela de roteamento de B mostra como os pacotes podem se mover para as redes 1 e 4.
• O B é vizinho do roteador A, os pacotes de A para B podem chegar em um salto. Assim, soma-se 1 a todos os custos dados na tabela B e a soma será o custo para chegar a uma determinada rede.

• Após o ajuste, A combina esta tabela com sua própria tabela para criar uma tabela combinada.

• A tabela combinada pode conter alguns dados duplicados. Na figura acima, a tabela combinada do roteador A contém os dados duplicados, portanto mantém apenas os dados de menor custo. Por exemplo, A pode enviar os dados para a rede 1 de duas maneiras. O primeiro, que não usa próximo roteador, portanto custa um salto. O segundo requer dois saltos (A para B e depois B para a Rede 1). A primeira opção tem o menor custo, portanto é mantida e a segunda é descartada.

• O processo de criação da tabela de roteamento continua para todos os roteadores. Cada roteador recebe as informações dos vizinhos e atualiza a tabela de roteamento.

As tabelas finais de roteamento de todos os roteadores são fornecidas abaixo: