Protocolos de encaminhamento_i

Algoritmos e respetivos protocolos de encaminhamento (1/3)

• Algoritmos de encaminhamento unicasting numa rede IP:

1

Vetor de distância (Distance Vector) determina a direção (vetor) e a distância de todos os links na rede (Ex.: RIP, IGRP, ...)



2

Link state (também chamado de shortest path first) recria a topologia exata da internetwork (totalidade).(Ex.: OSPF, ...)



3

Híbrida balanceada combina aspetos dos algoritmos do link state e distance vector.

Distance Vector (1/4)

Os algoritmos de vetor de distância (distance vector) não permitem que um router conheça a topologia exata da rede.

O router conhece apenas os vizinhos e o custo para os alcançar.

Um processo iterativo de computação com troca de informação com os vizinhos permite construir uma tabela de encaminhamento e fazê-la evoluir dinamicamente

4


5

• Exemplos de protocolos:o Routing Information Protocol (RIP) – O mais comum na Internet, o RIP usa a

contagem de saltos como única métrica de routing.

o Interior Gateway Routing Protocol (IGRP) – Criado pela Cisco para ultrapassar problemas associados ao routing em redes grandes e heterogéneas.

o Enhanced IGRP (EIGRP) – Exclusivo da Cisco inclui muitos dos recursos de um protocolo de routing link state. Por isso, é considerado um protocolo híbrido balanceado mas é, na verdade, um protocolo avançado de routing distance vector .

Distance Vector (3/4)• As tabelas de encaminhamento contêm a distância

(distance) e a direção (vector) para as ligações da rede.

• A distância pode ser a contagem de saltos até à ligação.

• Os routers enviam periodicamente toda ou parte das suas da tabelas de encaminhamento para os routers adjacentes.o As tabelas são enviadas mesmo que não haja alterações na rede.

6


Vantagens

• Fácil de implementar;

• O cálculo da tabela de routing é pouco complexo, pelo que não necessita de grande capacidade de processamento por parte do router.

Desvantagens

• Mensagens de actualização podem ser muito extensas;

• As mudanças propagam-se lentamente entre routers, podendo existir routers com informação incorrecta e esta ser propagada pela rede;

• O algoritmo pode não convergir e é lento quando converge.

7

Convergênciaintervalo de tempo necessário para que os routers tomem conhecimento de alterações e recalculem as rotas

Convergênciaintervalo de tempo necessário para que os routers tomem conhecimento de alterações e recalculem as rotas

Como obter as tabelas de encaminhamento

1. O router começa por identificar os seus vizinhos. Tendo como distância o valor zero.

2. Os routers descobrem o melhor caminho para as redes de destino, com base nas informações que recebem de cada vizinho.

3. Cada uma das entradas da outra rede na tabela de routing tem um vetor de distância acumulado, para mostrar a distância que essa rede se encontra em determinada direção.

8

Alterações na rede• As atualizações das

alterações na rede são feitas passo-a-passo, de router para router.

• Os algoritmos de vetor de distância solicitam a cada router toda a sua tabela de routing para cada um dos vizinhos adjacentes.

Prof. Isabel Caetano 9As tabelas de encaminhamento incluem informações sobre o custo total do caminho (definido pela sua métrica) e o endereço do (primeiro) router no caminho para cada rede

Exemplo 1• A partir da figura obter as tabelas de

encaminhamento finais para cada router, usando o algoritmo de vetor de distâncias.

14

Exemplo 1 - Resolução

15

• Na 1ª iteração cada router verifica a que distância está dos outros preenchendo apenas a linha correspondente ao seu próprio router


16

• Na 2ª iteração os routers vizinhos trocam as tabelas entre si, recebendo dados que lhes permite preencher as restantes linhas e/ou atualizar os dados


17

• Na 3ª iteração voltam a trocar tabelas e os custos mais baixos são aplicados às tabelas que ainda não estavam actualizadas

Contagem até ao infinito

• As atualizações inválidas da rede podem fazer loop. o Essa condição é chamada de

contagem ao infinito.

• O vetor de distância (métrica) do contador de saltos aumenta sempre que o pacote passa por um outro router.

18

Como solucionar os loops? (1/2)

• Limite de número de saltos máximos possíveis (16 saltos – infinito).

• Assim, o loop só se prolonga até aos 16 saltos e o nó será removido da tabela de encaminhamento.

• Todavia, a solução dos 16 saltos não evita que o loop se mantenha, por vezes, bastante tempo (pode demorar alguns minutos) sendo possível perder-se informação de encaminhamento relativa a outras redes.

19

Como solucionar os loops? (2/2)

• O split horizon tenta evitar que informações incorretas sejam enviadas de volta para um router contradizendo informações corretas.

• Se uma atualização sobre a rede 1 chegar do router A, o router B (ou D) não poderá enviar informações sobre a rede 1 de volta para o router A.

• O split horizon reduz assim as informações incorretas e reduz a sobrecarga do routing.

20

Protocolo de encaminhamento dinâmico RIP

• Existem dois tipos de RIP actualmente: RIP v.1 e RIP v.2.

• Este protocolo usa o algoritmo do vetor das distâncias de Bellman-Ford.

• O RIP apenas deve ser usado em pequenas redes, devido ao seu problema de convergência (lenta) e limite de saltos (15).

• No RIP, a escolha dos caminhos é baseada apenas no número de saltos até ao destino.

21

Hop count no RIP

22

• Quando um router recebe a tabela de um router vizinho a indicar que é possível alcançar a rede X com um número de saltos N, significa que ele pode alcançar a mesma rede X com um número de saltos N+1.

Problemas associados ao RIP

23

• Pôr de parte alternativas melhores (largura de banda, congestionamento, fiabilidade, …) > só conta o número de saltos.

• Atualizações:o Em cada 30 segundos cada router envia para os seus vizinhos

as actualizações.o Ao fim de 90 segundos sem receber informação de outro router

(vizinho) marca essa rede como inacessível.o Ao fim de 3 minutos sem "dar notícias" os routers vizinhos

apagam a linha da tabela de routing que continha essa rede – o que pode provocar loops.

• Incapacidade de detetar loops na rede.

Government & Nonprofit

Protocolos de encaminhamento_i