Algoritmos e respectivos protocolos de encaminhamento

Os algoritmos e protocolos de encaminhamento apenas se aplicam a endereços dinâmicos. Neste ponto abordam-se as formas como os routers de uma rede comunicam entre si e trocam informação, bem como conseguem, face a alterações na rede, permitir a convergência da mesma.

Na gíria de redes é usual ouvir-se dizer frequentemente que uma rede convergiu. Pode definir-se convergência como o intervalo de tempo necessário para que os routers tomem conhecimento de uma alteração na rede e recalculem as rotas para a nova topologia. Os factores que influenciam o t

empo de convergência são:

—A distância em saltos do router ao ponto de mudança;

1. —O número de routers que usam protocolos dinâmicos de encaminhamento;
2. —Largura de banda e congestionamento nos links;
3. —Capacidade de processamento do router;
4. —Protocolo de encaminhamento utilizado.
5. Neste ponto abordam-se dois algoritmos e os respectivos protocolos associados: Distance Vector (RIP) e Link.State (OSPF)

Distance Vector (DV) ou Algoritmo das Distâncias

Cada router tem uma tabela que contém as redes (routers) a ele ligadas directamente e as distâncias associadas. Todos os router da rede trocam as suas tabelas, constituídas por um vector (V,D) [onde V – identifica o destino e D – a distância até ao destino], com os seus routers vizinhos da seguinte forma:

1.Espera a mudança na distância até a um certo destino (geralmente hops) ou do final do temporizador;

2.Recalcula a tabela de encaminhamento;

3.Se a distância for menor para algum destino, notifica (apenas) os vizinhos.

Distance Vector (DV) ou Algoritmo das Distâncias (continuação)

A descoberta da rede é feita através do algoritmo do vector das distâncias ou de Bellman-Ford.

O algoritmo foi descoberto por dois matemáticos americanos Richard E. Bellman (1920-1984) e Lester Randolph Ford , Jr (1927 – presente) e consiste em calcular o caminho mais curto entre dois pontos. A sua aplicabilidade em redes foi deveras importante sendo ainda largamente utilizado em alguns protocolos.

Distance Vector (DV) ou Algoritmo das Distâncias (continuação)

O algoritmo apresenta a seguinte características:

—Iterativo: através da informação recebida dos vizinhos consegue calcular a sua tabela:

—Assíncrono: os routers não enviam a informação em simultâneo:

—Distribuído: cada router comunica apenas com os seus vizinhos directos.