Uma das principais funções da camada de rede é a de estabelecer uma rota de menor custo entre determinada origem e destino. Essa função é chamada de
roteamento e é executada por elementos ativos da rede chamados de
roteadores (e, atualmente, também pelos chamados
switches de camada 3).
A literatura enumera muitas classificações para os algoritmos de roteamento. Uma delas leva em consideração a adaptabilidade (ou não) das rotas estabelecidas. Quanto a esse critério, os algoritmos de roteamento são classificados em estáticos e dinâmicos.
Os
algoritmos estático não se adaptam às mudanças na carga da rede ou em sua topologia. Através deles, as rotas a serem utilizadas pelos pacotes em tráfego, são estabelecidas normalmente
off-line para, somente então, serem transferidas aos roteadores.
Por outro lado, os
algoritmos dinâmicos se adaptam de acordo com mudanças na topologia e na carga da rede. Esses algoritmos diferem na forma de obter informações de roteamento, no tempo de atualização de suas tabelas e na unidade métrica utilizada para a otimização.
Essa última classe de algoritmos, tema central do nosso post de hoje, são classificados em mais duas categorias: vetor de distância e estado de enlace.
Utilizando um algoritmo de
vetor de distância (DV -
Distance Vector), um roteador mantêm uma tabela (vetor) atualizada através da troca de informações com roteadores vizinhos. Esse mesmo procedimento é realizado pelos outros nós (roteadores), cascateando e atualizando as informações. Portanto o processo é iterativo e distribuído.
Através do algoritmo de estado de enlace (LS -
Link State), as rotas são calculadas usando conhecimento completo e global sobre a rede. Essa característica ocasiona um
overhead inicial, mas que são suavizados nas alterações subsequentes na tabela. Para o cálculo do menor custo, algoritmos de estado de enlace normalmente são baseados no SPF (Shortest Path First) de Dijkstra.
Complicou? Vamos esquematizar:
Portando essas informações, vamos discutir alguns protocolos utilizados na Internet que se baseiam nas ideias desses algoritmos de roteamento.
1. RIP (Routing Information Protocol)
O RIP é um protocolo de roteamento interno (intra-SA), ou seja, é rodado dentro de um sistema autônomo (SA) da Internet. Ele é um protocolo de vetor de distância que usa contagem de saltos (
hops) como métrica de custo, utilizando um
limite de 15 saltos por SA.
Por meio do RIP, as tabelas de roteamento são trocadas, aproximadamente, a cada 30 segundos por meio de mensagens chamadas de
anúncios (ou resposta) RIP. Roteadores enviam mensagens RIP por UDP, porta 520.
As principais melhorias da
versão 2 do RIP em relação a sua versão original é o reconhecimento de sub-redes e uma camada de segurança por meio de autenticação utilizando MD5.
2. OSPF (Open Shortest Path First)
O OSPF é considerado como sucessor do RIP. Ele apresenta características mais avançadas em relação ao seu antecessor. É um protocolo de roteamento interno que utiliza o algoritmo de estado de enlace (por isso o SPF em seu nome).
Por meio do OSPF é construído um grafo de todo o sistema autônomo. O algoritmo SPF é rodado, a partir de um nó (roteador) raiz, de forma a gerar uma
árvore de escoamento considerando os demais nós do SA.
O pacote Hello do OSPF é utilizado para estabelecer adjacências de roteadores vizinho. Por padrão, esses pacotes são enviados a cada 10 segundos.
Diferente do RIP,
o OSPF não utiliza protocolos de transporte. Suas informações são enviadas diretamente utilizando-se a camada IP.
Outras características do OSPF:
- Autenticação com MD5;
- Capacidade de estruturar hierarquicamente um SA;
- Nesse caso, cada área (ou "sub-SA") criada, roda sua própria instância do OSPF;
- Suporte para roteamento unicast e multicast;
- Considera caminhos múltiplos quando esses têm o mesmo custo;
3. BGP (Border Gateway Protocol)
A versão 4 do BGP é o padrão "de fato" para roteamento entre SAs (inter-SA) na Internet. Por meio dele, são estabelecidas
conexões semipermanentes TCP entre pares de roteadores (pares BGP), usando a porta 179.
Uma
sessão BGP corresponde a uma conexão TCP junto com o conjunto de mensagens trocadas entre pares BGP. Essa sessão pode ser denominada
externa (ou
eBGP) quando abrange dois SAs e
interna (ou
iBGP) quando estabelecida por roteadores dentro do mesmo SA. Sim! Também há conexões semipermanentes dentro dos SAs.
 |
| Fonte: Kurose |
Para questões de concurso sobre esse tema, clique aqui.
REFERÊNCIAS
[1] TANENBAUM, A. S. – Redes de Computadores – 5ª Ed.,Pearson, 2011.
[2] KUROSE, J. F. e ROSS, K. - Redes de Computadores e a Internet - 5ª Ed., Pearson, 2010.
[3] http://imasters.com.br/artigo/3457/redes-e-servidores/roteadores-vizinhos-distance-vector
[4] http://www.dcc.fc.up.pt/~pbrandao/aulas/0405/arq_r/slides/Routing-RIP.pdf
[5] http://www.kraemer.pro.br/cisco/exploration2/cap11.pdf
