Apostila Roteamento

Prévia do material em texto

PROTOCOLOS DE ROTEAMENTO DA IN PROTOCOLOS DE ROTEAMENTO DA 
INTERNET PROTOCOLO 
 
SNET 
Extraído dos livros “REDES E SISTEMAS DE COMUNICAÇÃO DE DADOS, WILLIAM 
STALLINGS” e “REDES DE COMPUTADORES, Larry L. Peterson” 
 
 
Os roteadores em uma inter-rede são responsáveis por receber e encaminhar pacotes pelo 
conjunto de redes interconectadas. Cada roteador toma decisões de roteamento com base no 
conhecimento da topologia e das condições de tráfego/atraso da inter-rede. Em uma inter-rede 
simples, um esquema de roteamento fixo é possível, em que uma única rota permanente é 
configurada para cada par origem-destino de nós na rede. As rotas são fixas, ou no máximo só 
mudam quando existe uma modificação na topologia da rede. Assim, os custos do enlace usados 
no projeto das rotas não podem se basear em qualquer variável dinâmica, como o tráfego. Porém, 
eles poderiam se basear nos volumes de tráfego estimado entre diversos pares de origem-destino 
ou na capacidade de cada enlace. 
Em inter-redes mais complexas, um grau de cooperação dinâmica é necessário entre os 
roteadores. Em particular, os roteadores precisam evitar partes da rede que falharam, e devem 
evitar partes da rede que estão congestionadas. Para tomar tais decisões de roteamento 
dinâmico, os roteadores trocam informações de roteamento mediante um protocolo de roteamento 
especial para essa finalidade. São necessárias informações sobre o status da inter-rede, em 
termos de que redes podem ser alcançadas por quais rotas, e as características de atraso das 
várias rotas. 
Na análise da função de roteamento, é importante 
distinguir dois conceitos: 
• Informações de roteamento: Informações sobre a topologia e os atrasos da inter-rede 
• Algoritmo de roteamento: O algoritmo utilizado para tomar uma decisão de roteamento para 
determinado datagrama, com base nas informações de roteamento atual 
Sistemas autónomos 
Para prosseguir com nossa discussão dos protocolos de roteamento, precisamos introduzir o 
conceito de um sistema autónomo. Um sistema autónomo (AS) exibe as seguintes 
características: 
1. Um AS é um conjunto de roteadores e redes gerenciados por uma única organização.
 
 
PROTOCOLOS DE ROTEAMENTO 
 
 
 
FIGURA 8,3 Aplicação dos protocolos de roteamento exterior e interior. 
2 Um AS consiste em um grupo de roteadores que trocam informações por meio de um protocolo de 
roteamento comum. 
3 Exceto em momentos de falha, um AS está conectado (no sentido da teoria dos grafos); ou seja, há 
um caminho entre qualquer par de nós. 
Um protocolo de roteamento compartilhado, ao qual nos referiremos como um Interior Router 
Protocol (IRP), passa informações de roteamento entre os roteadores dentro de um AS. O protocolo em 
uso dentro do AS não precisa ser implementado fora do sistema. Essa flexibilidade faz com que os IRPs 
se ajustem a aplicações e requisitos específicos. 
Todavia, pode acontecer que uma inter-rede seja construída de mais de um AS. Por exemplo, 
todas as LANs em um site, como um complexo de escritório ou campus, poderiam se ligar por 
roteadores para formar um AS. Esse sistema poderia estar conectado por meio de uma rede de longa 
distância com outros ASs. A situação é ilustrada na Figura 8.3. Nesse caso, os algoritmos de 
roteamento e as informações nas tabelas de roteamento utilizadas pêlos roteadores em diferentes 
ASs podem diferir. Apesar disso, os roteadores em um AS precisam de pelo menos um nível mínimo 
de informação referente a redes fora do sistema que possam ser alcançadas. Vamos nos referir ao 
protocolo utilizado para passar informações entre roteadores em ASs diferentes como um Exterior 
Router Protocol (ERP).1 
Em termos gerais, IRPs e ERPs possuem um sabor um tanto diferente. Um IRP precisa montar um 
modelo de certa forma detalhado da interconexão de roteadores dentro de um AS a fim de calcular o 
caminho de menor custo de determinado roteador para qualquer rede dentro do AS. Um ERP admite a 
troca de informações de resumo do alcance entre ASs separadamente administrados. Normalmente, 
esse uso das informações de resumo significa que um ERP é mais simples e usa informações menos 
detalhadas do que um IRP. 
No restante desta seção, examinamos aqueles que talvez sejam os exemplos mais importantes 
desses dois tipos de protocolos de roteamento: BGP e OSPF. 
1
 Na bibliografia especializada, os termos Interior Gateway Protocol (IGP) e Exterior Gateway Protocol (EGP) normalmente refe-
rem-se ao que aqui denominamos IRP e ERP. Porém, como os termos IGP e EGP também se referem a protocolos específicos, 
evitamos empregá-los para definir os conceitos gerais. 
 
Sistema autónomo 2 Sistema autónomo 1 
Interior router protocol 
Exterior router protocol 
Border Gateway Protocol 
O Border Gateway Protocol (BGP) foi desenvolvido para uso em conjunto com inter-redes que 
empregam o conjunto TCP/IP, embora os conceitos sejam aplicáveis a qualquer inter-rede. BGP 
tornou-se o exterior router protocol preferido para a Internet. 
BGP foi projetado a fim de permitir que roteadores, chamados gateways no padrão, em diferentes 
sistemas autónomos (ASs) cooperem na troca de informações de roteamento. O protocolo opera em 
termos de mensagens, que são enviadas por conexões TCP. A versão atual do BGP é conhecida 
como BGP-4. 
Três procedimentos funcionais estão envolvidos no BGP: 
• Aquisição de vizinho 
• Alcance de vizinho 
• Alcance de rede 
Dois roteadores são considerados vizinhos se estiverem ligados à mesma rede. Se os dois roteadores 
estiverem em diferentes sistemas autónomos, eles podem querer trocar informações de roteamento. 
Para essa finalidade, é necessário antes realizar aquisição de vizinho. O termo vizinho refere-se a dois 
roteadores que compartilham a mesma rede. Basicamente, a aquisição de vizinho ocorre quando dois 
roteadores vizinhos em diferentes sistemas autónomos concordam em trocar informações de 
roteamento regularmente. Um procedimento de aquisição formal é necessário, pois um dos roteadores 
pode não querer participar. Por exemplo, o roteador pode estar sobrecarregado e não querer ser 
responsável pelo tráfego que vem de fora do AS. No processo de aquisição de vizinho, um roteador 
envia uma mensagem de solicitação para o outro, que pode aceitar ou recusar a oferta. O protocolo 
não resolve o problema de como um roteador sabe o endereço ou até mesmo a existência de outro 
roteador, nem de como decide que precisa trocar informações de roteamento com esse roteador específico. 
Essas questões devem ser tratadas no momento da configuração, ou pela intervenção ativa de um 
gerente de rede. 
Para realizar a aquisição de vizinho, um roteador envia uma mensagem Open para outro. Se o roteador 
de destino aceitar a solicitação, ele retornará uma mensagem Keepalive em resposta. 
Quando um relacionamento de vizinho se estabelecer, o procedimento de alcance de vizinho será 
usado para manter o relacionamento. Cada parceiro precisa ter certeza de que o outro ainda existe e 
ainda está engajado no relacionamento de vizinho. Para essa finalidade, os dois roteadores 
periodicamente emitem mensagens Keepalive um para o outro. 
O procedimento final especificado pelo BGP é o alcance de rede. Cada roteador mantém um banco de 
dados das redes que ele pode alcançar e a rota preferida para chegar a cada rede. Sempre que se faz 
uma mudança nesse banco de dados, o roteador emite uma mensagem Update que é transmitida por 
broadcast a todas as outras rotas para as quais possui um relacionamento de vizinho. Como a 
mensagem Update é transmitida por broadcast, todos os roteadores podem juntar e manter suas 
próprias informações de roteamento. 
Protocolo Open Shortest Path First (OSPF) 
O protocolo OSPF é bastante utilizado como um interior router protocol nas redes TCP/IP. O OSPF utiliza o 
que é conhecido como um algoritmo de roteamentopor estado do enlace. Cada roteador mantém 
descrições do estado de seus enlaces locais com as redes, e de vez em quando transmite informações de 
estado atualizadas para todos os roteadores dos quais está ciente. Cada roteador que recebe um 
pacote de atualização precisa confirmá-lo ao emissor. Essas atualizações produzem um mínimo de 
tráfego de roteamento, pois as descrições de enlace são pequenas e raramente precisam ser enviadas. 
O OSPF calcula uma rota pela inter-rede que ocasione o menor custo, com base em uma medida de custo 
confi-gurável pelo usuário. O usuário pode configurar o custo para expressar uma função de atraso, taxa de 
dados, custo em dólar ou outros fatores. OSPF é capaz de balancear as cargas por vários caminhos de 
mesmo custo. 
Cada roteador mantém um banco de dados que reflete a topologia conhecida do sistema autónomo do 
qual faz parte. A topologia é expressa como um grafo direcionado. O grafo consiste no seguinte: 
• Vértices, ou nós, de dois tipos: 
• Roteador 
• Rede, que por sua vez é de dois tipos: 
- Trânsito, se puder transportar dados que não começam nem terminam em um sistema final 
ligado a essa rede 
- Stub, se não for uma rede em trânsito 
• Arcos, de dois tipos: 
• Um arco de grafo que conecta dois vértices de roteador quando os roteadores correspondentes 
estão conectados entre si por um enlace ponto a ponto direto. 
• Um arco de grafo que conecta um vértice de roteador a um vértice de rede quando o roteador 
está conectado diretamente à rede. 
A Figura 8.4 mostra um exemplo de um sistema autônomo, e a Figura 8.5 é o grafo direcionado 
resultante. 
O mapeamento é direto:
 
FIGURA 8.4 Um exemplo de sistema autónomo. 
 
N12 N13 N14 
N12 
 
 
2 
 
 
N15 
• Dois roteadores unidos por um enlace ponto a ponto são representados no grafo como se 
estivessem conectados por um par de arcos, um em cada direção (por exemplo, roteadores 6 e 
10). 
• Quando vários roteadores estão conectados a uma rede (como uma LAN ou rede de 
comutação de pacotes), o grafo direcionado mostra todos os roteadores bidirecionalmente 
conectados ao vértice da rede (por exemplo, os roteadores l, 2, 3 e 4 se conectam à rede 3). 
• Se um único roteador estiver conectado a uma rede, esta aparecerá no grafo como uma conexão 
stub (por exemplo, a rede 7). 
• Um sistema final, chamado host, pode se conectar diretamente a um roteador, quando será 
representado no grafo correspondente (por exemplo, host 1). 
• Se um roteador estiver conectado a outros sistemas autónomos, então o custo do caminho de 
cada rede no outro sistema precisa ser obtido por algum Exterior Routing Protocol (ERP). Cada 
uma dessas redes é representada no grafo por um stub e um arco para o roteador com o custo de 
caminho conhecido (por exemplo, redes de 12 a 15). 
Um custo está associado ao lado de saída de cada interface de roteador. Esse custo é 
confígurável pelo administrador do sistema. Os arcos no grafo são rotulados com o custo da interface 
de saída do roteador correspondente. Os arcos que não têm custo rotulado possuem um custo 0. 
Observe que os arcos que saem das redes para os roteadores sempre possuem um 
custo 0. 
 
 
FIGURA 8.5 Grafo direcionado do sistema autónomo da Figura 8.4. 
Um banco de dados correspondente ao grafo direcionado é mantido por cada roteador. Ele é montado a partir 
de mensagens de estado de enlace de outros roteadores na inter-rede. Mediante um algoritmo explicado na 
próxima subseção, um roteador calcula o caminho de menor custo para todas as redes de destino. Os resultados 
para o roteador 6 da Figura 8.4 aparecem como uma árvore na Figura 8.6, sendo R6 a raiz da árvore. A árvore 
indica a rota inteira para qualquer rede ou host de destino. Porém, somente o próximo salto para o destino é 
usado no processo de encaminhamento. A tabela de roteamento resultante para o roteador 6 aparece na 
N12 N13 N14 
 
N7 
R12 
Tabela 8.2. A tabela inclui entradas para roteadores que anunciam rotas externas (roteadores 5 e 7). Para redes 
externas cuja identidade é conhecida, também são fornecidas entradas. 
 
 
 
 
FIGURA 8.6 A árvore SPF para o roteador R6. 
 
N12 N13 N14 
N1 
N7 
R12 
Tabela 8.2 Tabela de roteamento para R6 
Destino 
 
Próximo salto 
 
Distância 
 
NI 
 
R3 
 
10 
 N2 
 
R3 
 
10 
 
N3 
 
R3 
 
7 
 
N4 
 
R3 
 
8 
 
N6 
 
RIO 
 
8 
 
N7 
 
RIO 
 
12 
 
N8 
 
RIO 
 
10 
 
N9 
 
RIO 
 
11 
 
N10 
 
RIO 
 
13 
 
NU 
 
RIO 
 
14 
 
Hl 
 
RIO 
 
21 
 R5 
 
R5 
 
6 
 
R7 
 
RIO 
 
8 
 
N12 
 
RIO 
 
10 
 
N13 
 
R5 
 
14 
 
N14 
 
R5 
 
14 
 
N15 
 
RIO 
 
17 
 
 
 
 
 
4.2 Roteamento 
Neste e no capítulo anterior, consideramos que os switches e os roteadores possuem 
conhecimento suficiente da topologia da rede para que possam escolher a porta correta pela qual 
cada pacote deve ser encaminhado. No caso dos circuitos virtuais, o roteamento é um problema 
apenas para o pacote de solicitação de conexão; todos os pacotes seguintes seguem o mesmo 
caminho da solicitação. Nas redes de datagrama, incluindo as redes IP, o roteamento é um 
problema para cada pacote. De qual quer forma, um switch ou roteador precisa ser capaz de 
examinar o endereço de destino do pacote e depois determinar qual das portas de saída é a 
melhor opção para levar o pacote até esse endereço. 
Como vimos na Seção 3.1.1, o switch toma essa decisão consultando uma tabela de 
encaminhamento. O problema fundamental do roteador é: "Como os switches e os roteadores 
adquirem as informações em suas tabelas de roteamento"? 
Reafirmamos uma distinção importante, que normalmente é desconsiderada, entre 
eccaminhamento e roteamento. O encaminhamento consiste em apanhar um pacote, 
examinar seu endereço de destino, consultar uma tabela e enviar o pacote em uma direção 
determinada por essa tabela. Vimos vários exemplos de encaminhamento na seção 
anterior. O roteamento é o processo pelo qual as tabelas de encaminhamento são criadas. 
Também observamos que o encaminhamento é um processo relativamente simples e bem 
definido, realizado localmente em um nó, enquanto o roteamento depende de algoritmos 
distribuídos complexos, que têm continuado a evoluir no decorrer da história das redes. 
Embora os termos tabela de encaminhamento e tabela de roteamento às vezes sejam usados 
para indicar a mesma coisa, faremos uma distinção entre eles aqui. A tabela de encaminhamento 
é usada quando um pacote está sendo encaminhado e, portanto, precisa conter informações 
suficientes para realizar a função de encaminhamento. Isso significa que uma linha na tabela de 
encaminhamento contém o mapeamento de um número de rede a uma interface de saída e 
alguma informação de MAC, como o endereço Ethernet do próximo salto. A tabela de 
roteamento, por outro lado, é a tabela criada pêlos algoritmos de roteamento como precursora 
para a criação da tabela de encaminhamento. Ela geralmente contém mapeamentos entre 
números de rede e próximos saltos. Ela também pode conter informações sobre como essas 
informações foram descobertas, de modo que o roteador possa decidir quando deverá descartar 
alguma informação. 
Se a tabela de roteamento e a tabela de encaminhamento são realmente estruturas de dados 
separadas ou não, isso é algo que fica por conta da implementação, mas existem diversos motivos 
para mante-las separadas. Por exemplo, a tabela de encaminhamento precisa ser estruturada a 
fim de otimizar o processo de consulta de um número de rede quando estiver encaminhando um 
pacote, enquanto a tabela de roteamento precisa ser otimizada para fins de cálculo de mudanças 
na topologia. Emalguns casos, a tabela de encaminhamento pode até mesmo ser implementada 
em hardware especializado, enquanto isso raramente ou nunca é feito para a tabela de 
roteamento. A Tabela 4.4 contém um exemplo de uma linha de cada tipo de tabela. Nesse caso, a 
tabela de roteamento nos diz que a rede número 10 deve ser alcançada por um roteador do 
próximo salto com o endereço IP 171.69.245.10, enquanto a tabela de encaminhamento 
contém as informações sobre exatamente como encaminhar um pacote para esse próximo salto: 
enviá-lo pela interface número 0 com um endereço MAC 8:0:2b:e4:b:l:2. Observe que essa última 
informação é fornecida pelo ARP (Address Resolution Protocol). 
Tabela 4.4 Exemplo de linhas das tabelas de (a) roteamento e (b) encaminhamento. 
 
 
 
 
 
 
 
 
 
 
 (b) 
 
 
Antes de entrarmos nos detalhes do roteamento, precisamos nos lembrar da pergunta chave 
que devemos fazer sempre que tentarmos criar um mecanismo para a Internet: "Essa solução é 
expansível?" Para os algoritmos e protocolos descritos nesta seção, a resposta é não. Eles são 
projetados para redes de tamanho bastante modesto - na prática, menos de cem nós. Porém, 
as soluções que descrevemos servem como um bloco de montagem para uma infra-estrutura 
de roteamento hierárquico que é usada na Internet atual. Especificamente, os protocolos 
descritos nesta seção são conhecidos coletivamente como protocolos de roteamento 
intradomínio, ou protocolos de gateway interior (IGPs - Interior Gateway Protocols). Para 
entender esses termos, precisamos definir um domínio de roteamento: uma boa definição 
funcional é uma inter-rede em que todos os roteadores estão sob o mesmo controle 
administrativo (por exemplo, um único campus universitário ou a rede de um único provedor de 
serviços da Internet). A relevância dessa definição se tornará aparente na próxima seção, 
quando examinarmos os protocolos de roteamento interdomínio. Por enquanto, o importante a 
ter em mente é que estamos considerando o problema de roteamento no contexto de redes de 
tamanho pequeno a médio, e não para uma rede do tamanho da Internet. 
NúmeroRede PróximoSalto 
171.69.245.10 10 
(a) 
NúmeroRede Interface Endereço MAC 
10 8:0:2b:e4:b:1:2 ifO 
4.2.1 A rede como um grafo 
 
Basicamente, o roteamento é um problema de teoria de grafos. A Figura 4.14 mostra um grafo 
representando uma rede. Os nós do grafo, rotulados de A até F, podem ser hosts, switches, 
roteadores ou redes. Para nossa discussão inicial, vamos nos concentrar no caso em que os nós 
são roteadores. As bordas do grafo correspondem aos enlaces da rede. Cada borda possui um 
custo associado, que oferece alguma indicação do desejo de enviar tráfego por esse enlace. 
Uma discussão de como os custos da borda são atribuídos é dada na Seção 4.2.4.3 
 
 
Figura 4.14 flecte representada como um grafo. 
 
O problema básico do roteamento é encontrar o caminho de menor custo entre dois nós 
quaisquer, onde o custo de um caminho é igual à soma dos custos de todas as bordas que 
compõem o caminho. Para uma rede simples, como a da Figura 4.14, você poderia imaginar-se 
simplesmente calculando todos os caminhos mais curtos e carregando-os em algum tipo de 
armazenamento não volátil em cada nó. Essa técnica estática possui várias limitações: 
• Ela não trata de falhas de nó ou de enlace. 
• Ela não considera o acréscimo de novos nós ou enlaces. 
• Ela implica que os custos da borda não podem mudar, embora poderíamos 
razoavelmente querer atribuir temporariamente um custo alto a cada enlace que esteja 
bastante carregado. 
Por esses motivos, o roteamento é alcançado na maior parte das redes práticas pela execução 
de protocolos de roteamento entre os nós. Esses protocolos oferecem um modo distribuído e 
dinâmico de resolver o problema de localizar o caminho de menor custo na presença de falhas de 
enlace e de nó e custos de borda variáveis. Observe a palavra "distribuído" na sentença anterior: 
é difícil tornar soluções centralizadas escaláveis, de modo que todos os protocolos de roteamento 
amplamente utilizados usam algoritmos distribuídos. 
A natureza distribuída dos algoritmos de roteamento é um dos principais motivos pelos quais 
esse tem sido um campo de pesquisa e desenvolvimento tão rico - existem muitos desafios para fazer 
com que os algoritmos distribuídos funcionem bem. Por exemplo, os algoritmos distribuídos levantam a 
possibilidade de que dois roteadores em determinado instante tenham ideias diferentes a respeito do 
caminho mais curto até algum destino. De fato, cada um pode pensar que o outro estámais próximo 
do destino e decidir enviar pacotes para o outro. Logicamente, tais pacotes ficarão presos em um 
loop até que a divergência entre os dois roteadores seja resolvida, e seria bom resolver isso o mais 
cedo possível. Esse é apenas um exemplo do tipo de problema que os protocolos de roteamento 
precisam enfrentar. 
 
 
3
 Nas redes de exemplo (grafos) usadas no decorrer deste capítulo, usamos bordas não direcionadas e 
atribuímos um único custo a cada borda. Essa é, na realidade, uma ligeira simplificação. E mais preciso tornar as 
bordas direcionadas, o que normalmente significa que haveria um par de bordas entre cada nó - uma fluindo em 
cada direção, e cada uma com seu próprio custo de borda. 
 
 
 
Para iniciar nossa análise, vamos considerar que os custos de borda na rede sejam conhecidos. 
Vamos examinar as duas classes principais de protocolos de roteamento: com vetor de distância e 
por estado de enlace. Na Seção 4.2.4, retornamos ao problema de calcular os custos de borda de um 
modo significativo. 
 
 
4.2.2 Roteamento com vetor de distância (RIP) 
A ideia por trás do algoritmo com vetor de distância é sugerida por seu nome:4 cada nó constrói um 
array unidimensional (um vetor) contendo as "distâncias" (custos) até todos os outros nós e distribui 
esse vetor aos seus vizinhos imediatos. A suposição inicial para o roteamento com vetor de distância é 
que cada nó conhece o custo do enlace para cada um de seus vizinhos conectados diretamente. Um 
enlace que esteja inativo recebe um custo infinito. 
Para ver como funciona um algoritmo de roteamento com vetor de distância, é mais fácil considerar 
um exemplo como aquele representado na Figura 4.15. Nesse exemplo, o custo de cada enlace é 
definido como l, de modo que um caminho de menor custo é simplesmente aquele com menos saltos. 
(Como todas as bordas possuem o mesmo custo, não mostramos os custos no grafo.) Podemos 
representar o conhecimento de cada nó a respeito das distâncias até todos os outros nós sob a 
forma de uma tabela, como a que aparece na Tabela 4.5. Observe que cada nó só conhece as infor-
mações contidas em uma linha da tabela (aquela que contém seu nome na coluna da esquerda). A vi-
são global, apresentada aqui, não está disponível a qualquer ponto isolado na rede. 
 
 
 
Figura 4.15 Roteamento com vetor de distância: um exemplo de rede. 
Podemos considerar cada linha da Tabela 4.5 como uma lista de distâncias de um nó para to-
dos os outros nós, representando as convicções atuais desse nó. Inicialmente, cada nó define 
um custo de l aos seus vizinhos conectados diretamente e a todos os outros nós. Assim, A 
inicialmente acredita que pode alcançar B em um salto e que D é inalcançável. A tabela de 
roteamento armazenada em A reflete esse conjunto de convicções e inclui o nome do próximo 
salto que A usaria para atingir qualquer nó alcançável. Inicialmente, então, a tabela de roteamento 
de A se pareceria com a Tabela 4.6. 
 
 
 
 
 
 
 
 
4
 O outro nome comum para essa classe de algoritmo é Bellman-Ford, que recebeu os nomes de seus inventores. 
Tabela 4.5 Distâncias iniciais armazenadas em cada nó (visão global) 
 
Distância para alcançar o nó Informaçõesarmazenadas 
no nó 
 
A 
 
B 
 
C 
 
D 
 
E 
 
F G 
 
A 
 
0 
 
1 
 
1 
 
oo 
 
1 
 
1 oo 
B 
 
1 
 
0 
 
1 
 
oo oo oo oo 
C 
 
1 
 
1 
 
0 
 
1 
 
oo 
 
oo oo 
 
D oo 
 
oo 
 
1 
 
0 oo oo 1 
E 
 
1 
 
oo 
 
oo 
 
oo 
 
0 
 
oo oo 
 F 
 
1 
 
oo oo oo oo 
 
0 1 
 G 
 
oo 
 
oo 
 
oo 
 
1 
 
oo 
 
1 0 
 
Tabela 4.6 Tabela de roteamento inicial no nó A. 
Destino 
 
Custo 
 
PróximoSalto 
 
B 
 
1 
 
B 
 C 
 
1 
 
C 
 
D 
 
00 
 
- 
 E 
 
1 
 
E
 
F 
 
1 
 
F 
G 
 
00 
 
- 
 
A próxima etapa no roteamento com vetor de distância é que cada nó envie uma 
mensagem aos seus vizinhos conectados diretamente, contendo sua lista pessoal de 
distâncias. Por exemplo, o nó F diz ao nó A que pode alcançar o nó G a um custo l; A também 
sabe que pode alcançar F a um custo l, e por isso soma esses custos para obter o custo de 
alcançar G por meio de F. Esse custo total de 2 é menor que o custo atual de infinito, e por isso 
A registra que pode alcançar G a um custo 2, passando por F. Igualmente, A descobre por C 
que D pode ser alcançado a partir de C a um custo 1; ele soma isso ao custo de alcançar C 
(1) e decide que D pode ser alcançado por meio de C a um custo 2, que é melhor do que o 
custo antigo de infinito. Ao mesmo tempo, A descobre por C que B pode ser alcançado a partir 
de C a um custo l, e por isso conclui que o custo de alcançar B por meio de C é 2. Como isso é 
pior que o custo atual de alcançar B (1), essa nova informação é ignorada. 
Nesse ponto, A pode atualizar sua tabela de roteamento com os custos e próximos saltos 
para todos os nós na rede. O resultado aparece na Tabela 4.7 
Tabela 4.7 Tabela de roteamento final no nó A. 
Destino 
 
Custo PróximoSalto 
 
B 1 B 
C 1 C 
D 2 C 
E 1 E 
F 1 F 
G 2 F 
 
 
 
Não havendo quaisquer mudanças de topologia, são necessárias apenas algumas trocas de 
informações entre os vizinhos antes que cada nó tenha uma tabela de roteamento completa. O 
processo de obtenção de informações de roteamento coerentes a todos os nós é chamado de 
convergência. A Tabela 4.8 mostra o conjunto final de custos de cada nó para todos os outros nós 
quando o roteamento tiver convergido. Temos que enfatizar que não há um nó na rede que tenha 
todas as informações dessa tabela - cada nó só conhece o conteúdo de sua própria tabela de 
roteamento. A beleza de um algoritmo distribuído, como esse, é que ele permite que todos os nós 
atinjam uma visão coerente da rede na ausência de qualquer autoridade centralizada. 
Tabela 4.8 Distâncias finais armazenadas em cada nó (visão global). 
Distância para alcançar o nó 
 
Informações 
armazenadas 
no nó 
 
A 
 
B 
 
C 
 
D 
 
E 
 
F 
 
G 
 
A 
 
0 
 
1 
 
1 
 
oo 
 
1 
 
1 
 
oo 
 
B 
 
1 
 
o 
 
 1 
 
oo oo oo oo 
 
C 
 
1 
 
1 
 
0 
 
1 
 
oo 
 
oo oo 
 
D 
 
oo 
 
oo 
 
1 
 
0 
 
oo 
 
oo 
 
1 
 
E 
 
1 
 
oo 
 
oo 
 
oo 
 
oo 
 
oo 
 
oo 
 
F 
 
1 
 
oo 
 
oo 
 
oo 
 
oo 
 
oo 
 
1 
 
G 
 
oo 
 
oo 
 
oo 
 
1 
 
oo 
 
1 
 
0 
 
Existem alguns detalhes a serem explicados antes de concluirmos nossa discussão sobre 
roteamento com vetor de distância. Primeiro, observamos que existem duas circunstâncias 
diferentes sob as quais determinado nó decide enviar uma atualização de roteamento aos seus 
vizinhos. Uma dessas circunstâncias é a atualização periódica. Nesse caso, cada nó envia 
automaticamente uma mensagem de atualização com frequência, mesmo que nada tenha sido 
alterado. Com isso, outros nós saberão que esse nó ainda está funcionando. Isso também 
garante que eles continuam obtendo informações de que possam precisar se as rotas atuais não 
forem viáveis. A frequência dessas atualizações periódicas varia de um protocolo para outro, mas 
normalmente está na faixa de vários segundos até vários minutos. O segundo mecanismo, às 
vezes chamado de atualização acionada, acontece sempre que um nó recebe uma atualização 
de um de seus vizinhos, fazendo com que mudeuma das rotas em sua tabela de roteamento. Ou 
seja, sempre que a tabela de roteamento de um nó mudar, ele enviará uma atualização aos seus 
vizinhos o que pode levar a uma mudança em suas tabelas, fazendo com que também enviem 
uma atualização aos seus vizinhos.