Roteamento
Ferramentas de Gerenciamento de
Redes
Prof. Santiago Lopes ([Link]@[Link])
Material baseado no livro:
Arquitetura de Redes de Computadores
2ª. Edição - Luiz Paulo Maia
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento
O roteamento é a tarefa de encaminhar um pacote da origem ao destino
utilizando dispositivos intermediários, chamados de roteadores, que
juntos compõem a rede de interconexão.
Um roteador possui pelo menos duas interfaces de rede, e cada
interface conecta uma rede distinta. Nesse caso, o algoritmo de
roteamento seleciona uma determinada interface para encaminhar um
pacote, em função do endereço IP de destino contido no cabeçalho do
pacote.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento
Na Fig. 6.21 existem quatro redes conectadas por três roteadores (R1, R2 e R3), e
cada roteador possui duas interfaces de rede (1 e 2) conectando uma rede distinta.
Por exemplo, o roteador R1 conecta na interface 1 a rede 20 e na interface 2 a rede 30.
Cada roteador possui a sua própria tabela de roteamento (TR1, TR2 e TR3), formada
por pares indicando a rede e a interface que deve ser utilizada para alcançá-la. No
exemplo, todas as tabelas de roteamento possuem quatro entradas, uma para cada rede
conhecida.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento
Por exemplo, na Fig. 6.22 o roteador R3 não precisa ter rotas para as redes 20 e 30.
Se R3 possuir apenas uma rota padrão definida para a interface 1, todos os pacotes que não
sejam para a rede 50 serão encaminhados para a interface de R3 conectada à rede 40.
O mesmo poderia ser feito no roteador R1, definindo uma rota padrão para a interface 2.
Para definir a rota padrão em redes IP basta criar uma rota com o endereço [Link] para a
interface ou endereço IP para o qual se deseja encaminhar os pacotes.
Um problema surge quando os usuários querem se comunicar com usuários de outras redes,
por exemplo, a rede 20. Para resolver esse problema, as estações da rede local possuem
definido o endereço IP do gateway padrão ou default gateway. O gateway padrão
representa o roteador que recebe todo tráfego que seja endereçado para fora da LAN.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento – Características dos algoritmos
• Selecionar o melhor caminho;
• Convergir rapidamente: Ajuste rápido após uma mudança;
• Oferecer robustez: Funcionar corretamente mesmo na presença de problemas de
hardware, como a falha de um roteador, ou excesso de tráfego na rede. Além
disso, o algoritmo deve garantir que pacotes não bloqueiem a rede (deadlock) ou
fiquem vagando pela rede indefinidamente (livelock);
• Oferecer escalabilidade;
• Consumir poucos recursos.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento – Classificação dos Algoritmos de Roteamento
• Unicast, multicast e broadcast;
• Estático (as tabelas de roteamento são criadas e mantidas manualmente pelo
administrador da rede) e dinâmico (as tabelas são inicializadas e mantidas pelos
próprios roteadores, a partir de informações periodicamente trocadas entre os
dispositivos, permitindo a atualização dinâmica das tabelas de roteamento);
• Plano (todos os dispositivos estão no mesmo nível, ou seja, não existe uma
hierarquia entre os roteadores) e hierárquico (roteadores são agrupados
logicamente em áreas, regiões, domínios ou sistemas autônomos)
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento – Classificação dos Algoritmos de Roteamento
• Interno (são responsáveis apenas pelo roteamento dentro de uma mesma área, não
se preocupando com o roteamento entre as regiões – exemplos: RIP e OSPF) e
Externo (são responsáveis apenas pelo roteamento entre diferentes áreas -
exemplo BGP).
• Local (RIP, conhece apenas o roteador adjacente) e global (OSPF, conhece a rede
toda e por isso é mais robusto.)
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento – Métricas de Roteamento
• Número de saltos (Exemplo: RIP).
• Taxa de transmissão e carga da rede (Maior taxa de transmissão é o melhor
caminho)
• Atraso (O atraso ou latência representa o tempo necessário para que um pacote
transmitido por um roteador alcance o dispositivo adjacente. Geralmente, o atraso
é medido enviando-se um pacote para o dispositivo vizinho e calculando o tempo
de ida e volta do pacote, também chamado de RTT (Round-Trip Time))
• Taxa de erro (A taxa de erro está relacionada ao tipo de meio de transmissão. Fibra
ótica oferece taxas menores que transmissões sem fio)
• Disponibilidade
• Custo (O protocolo EIGRP da Cisco Systems utiliza quatro métricas para o
cálculo do custo: taxa de transmissão, atraso, confiabilidade e carga da rede.)
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Vetor de Distância
• RIP (Routing Information Protocol), definido na RFC-1058 e na RFC-2553. Outro
protocolo baseado no algoritmo de vetor de distância é o IGRP (Internet Gateway
Routing Protocol) da Cisco.
• Um roteador não conhece o caminho completo para determinado destino, mas
apenas o próximo passo para alcançá-lo. A métrica utilizada para o cálculo do
caminho de menor custo pode ser qualquer uma das apresentadas anteriormente,
como número de saltos, atraso ou uma combinação de diferentes métricas.
• No caso do protocolo RIP, o número de saltos é utilizado como métrica.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Vetor de Distância
• O algoritmo de roteamento por vetor de distância pode ser mais bem
compreendido a partir da rede apresentada na Fig. 6.23, formada por cinco
roteadores (A, B, C, D e E), conectados pelos caminhos de C1 a C6. No exemplo,
utilizaremos como métrica o número de saltos, que seria semelhante a considerar
todos os caminhos com custo igual a um [Huitema, 2000].
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Vetor de Distância
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Vetor de Distância
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Vetor de Distância
Recuperação em caso de falhas
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Vetor de Distância
Recuperação em caso de falhas
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Vetor de Distância
Recuperação em caso de falhas
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
O algoritmo baseado no estado do enlace é uma alternativa ao
roteamento por vetor de distância, pois não apresenta situações de loop
e converge mais rapidamente. O roteamento por estado do enlace é
implementado nos protocolos OSPF (Open Shortest Path First) e IS-IS
(Intermediate System to Intermediate System). Enquanto o protocolo
OSPF é um padrão Internet, definido na RFC-2328, o protocolo IS-IS
é um padrão OSI.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
O algoritmo pode ser mais bem compreendido a partir do exemplo
apresentado na Fig. 6.31, formada por oito roteadores (A a H) e um
custo associado a cada caminho da rede. O algoritmo possui quatro
etapas, que são apresentadas a seguir.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
Na primeira etapa, cada roteador envia uma mensagem do tipo Hello
para todas as suas interfaces, solicitando a identificação do dispositivo
adjacente. Ao receber a resposta, o roteador passa a conhecer seus
vizinhos.
Por exemplo, o roteador A envia um Hello para as interfaces que
levam aos dispositivos B e G. Se os roteadores B e G responderem, A
poderá considerá-los seus vizinhos.
Esse mecanismo também é utilizado para garantir que os roteadores
estão ativos. Periodicamente, uma mensagem Hello é enviada para os
dispositivos vizinhos para garantir que estão em funcionamento.
Caso não seja obtida uma resposta, o dispositivo pode ser considerado
fora de operação.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
Na segunda etapa, os roteadores calculam o custo para alcançar cada
um de seus vizinhos, utilizando alguma das métricas apresentadas. No
exemplo, consideremos o atraso como métrica, e, nesse caso, o melhor
caminho será aquele com o menor atraso. Depois de calculado o custo,
cada roteador cria um pacote contendo sua identificação e o custo para
alcançar seus vizinhos, chamado de pacote de estado do enlace ou LSP
(Link State Packet). A Fig. 6.32 apresenta os pacotes que serão
enviados por cada um dos roteadores da rede.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
Na terceira etapa, os pacotes criados por cada roteador são enviados
para todos os demais utilizando o roteamento por inundação, que será
apresentado na seção Roteamento Broadcast. À medida que os pacotes
são recebidos pelo roteador, é criada uma base de dados contendo a
origem, o destino e o custo do enlace. Para garantir que pacotes
antigos não afetem o conteúdo da base de dados, os pacotes são
numerados sequencialmente. Se o roteador recebe um pacote com
número de sequência menor ou igual ao último recebido, o pacote já
foi processado e é simplesmente descartado. Se o pacote possui um
número de sequência maior que o último recebido, as informações
podem ser utilizadas para atualizar a base de dados e o pacote é
reencaminhado. A Fig. 6.33 apresenta a base de dados dos roteadores
após o recebimento dos pacotes LSP. A partir dessa base de dados,
cada roteador terá um mapa completo da rede.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
Na quarta e última fase, cada roteador poderá calcular o melhor
caminho para qualquer destino consultando a base de dados construída
na fase anterior.
O algoritmo mais implementado para o cálculo do melhor caminho é
conhecido como SPF (Shortest Path First) e pode ser consultado em
[Dijkstra, 1959].
O algoritmo SPF cria uma árvore de caminho de menor custo a partir
de determinado roteador, chamado de raiz, para todos os demais. Por
exemplo, a Fig. 6.34 apresenta a árvore de caminho de menor custo
com base na rede da Fig. 6.30 e considerando o roteador A a raiz.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace – Recuperação de Falha
Para exemplificar a recuperação em casos de falhas do algoritmo
baseado no estado do enlace, vejamos o seu funcionamento na
ocorrência de um problema com o caminho B-E na rede da Fig.
6.35a. Ao perceber o problema, o roteador B enviará para A e C um
pacote informando que o custo do caminho para E é infinito.
Depois de um período de tempo, todos os demais roteadores
receberão o pacote, permitindo que as suas bases de dados fiquem
com a mesma informação (Fig. 6.35b).
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Estado de Enlace – Recuperação de Falha
A partir da base de dados atualizada da Fig. 6.35b, cada roteador
pode recalcular as rotas executando novamente o algoritmo SPF.
A Fig. 6.36 apresenta uma possível árvore de caminho de menor
custo considerando a falha de B-E e tendo o roteador A como raiz.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Hierárquico
Os roteadores são agrupados logicamente em regiões,
áreas ou sistemas autônomos (autonomous systems).
Nesse tipo de roteamento, as regiões se comunicam entre si através
de roteadores específicos que fazem a ligação entre as áreas,
chamados de roteadores de borda.
A tabela de roteamento dos roteadores de uma determinada região
precisa conter apenas informações dos roteadores daquela região e
dos roteadores que fazem a ligação entre as várias áreas.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Hierárquico
Os roteadores são agrupados logicamente em regiões,
áreas ou sistemas autônomos (autonomous systems).
Nesse tipo de roteamento, as regiões se comunicam entre si através
de roteadores específicos que fazem a ligação entre as áreas,
chamados de roteadores de borda.
A tabela de roteamento dos roteadores de uma determinada região
precisa conter apenas informações dos roteadores daquela região e
dos roteadores que fazem a ligação entre as várias áreas.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Hierárquico
Os algoritmos de Os algoritmos de
roteamento interno - IGP roteamento externo - EGP
(Interior Gateway (Exterior Gateway
Protocol) são Protocol) são
responsáveis apenas pelo responsáveis apenas pelo
roteamento dentro de uma roteamento entre
mesma região, não se diferentes áreas.
preocupando com o
roteamento entre as áreas.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Hierárquico
A Fig. 6.37 apresenta o exemplo de uma rede estruturada em dois níveis
hierárquicos e quatro regiões; a região 1 possui três roteadores, a região
2, quatro, a região 3, dois, e a região 4, cinco roteadores. Os roteadores
A1, A3, B2, B4, C2, D4 e E4 executam apenas o algoritmo de
roteamento interno, enquanto os roteadores A2, A4, B1, B3, C4 e D2
executam os algoritmos de roteamentos interno e externo.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Hierárquico
A Fig. 6.38a apresenta a tabela de roteamento do roteador A1 considerando o
roteamento plano, ou seja, sem o conceito de hierarquia e regiões. Como pode ser
observado, a tabela de roteamento de A1 possui uma entrada para cada roteador da
rede, totalizando 14 entradas.
A Fig. 6.38b apresenta a tabela de A1 considerando agora a rede, que implementa a
hierarquia dos roteadores em regiões. Como pode ser observado, a tabela de
roteamento de A1 possui apenas seis entradas. As três primeiras para os roteadores de
sua própria região e as outras três entradas representam o caminho para as demais
regiões: R2, R3 e R4.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Hierárquico
Além de melhorar o desempenho e a escalabilidade, o roteamento hierárquico
simplifica o processo de administração da rede, pois permite criar regiões
administrativas que podem ser gerenciadas de forma independente das demais. Essa
facilidade permite, por exemplo, que uma região utilize determinado algoritmo de
roteamento interno diferente das demais.
O modelo Internet utiliza o protocolo BGP (Border Gateway Protocol), definido nas
RFC-1771, RFC-1772 e RFC-1773, para implementação do roteamento hierárquico.
O protocolo BGP é baseado no algoritmo de vetor de distância, apresentado
anteriormente. Para mais informações sobre esse protocolo, consultar [Doyle, 2001],
[Huitema, 2000] e [Stewart, 1998].
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
Roteamento por Broadcast
No roteamento broadcast ou roteamento por difusão, um dispositivo
transmite um pacote que deve ser encaminhado para todos os demais
dispositivos da rede. O problema em utilizar essa abordagem é o enorme
desperdício de recursos da rede de interconexão.
Na Fig. 6.39a, o dispositivo A envia Na Fig. 6.39b, a rede está utilizando o
o mesmo pacote para os dispositivos roteamento broadcast para transmitir o
D1, D2 a Dn utilizando o mesmo pacote de A para os dispositivos
roteamento unicast. Se em nosso Dn. Nesse caso, apenas um pacote é
exemplo n for igual a 1000, para transmitido de A para B e de B para C.
cada dispositivo Dn um pacote é Somente em C os pacotes são entregues
transmitido, totalizando 3000 individualmente, totalizando 1002 pacotes
pacotes. transmitidos.
Roteamento Redes de Computadores | Prof. Santiago Lopes | Sistemas de Informação - AEDB
