Encaminhamento de datagramas em roteadores IP Objetivo

Encaminhamento de datagramas em roteadores IP
Objetivo
Modelar e implementar um algoritmo para encaminhamento de datagramas1 IP2 em um
roteador.
Introdução
Um roteador IP encaminha datagramas recebidos para as interfaces correspondentes às rotas
apropriadas. Uma rota apropriada é aquela que aponta um caminho para chegar ao endereço de
destino do datagrama, e contém as seguintes informações:
Prefixo de rede, Máscara de rede, Endereço do próximo roteador
Ex:
192.168.1.0, 255.255.255.0, 200.135.37.62
As rotas conhecidas ficam guardadas em uma tabela de rotas. Assim, ao receber um
datagrama o roteador busca nessa tabela a rota mais adequada para chegar a seu endereço destino.
Por exemplo, se o datagrama recebido tiver como endereço destino o IP 192.168.1.10, e a tabela do
roteador contiver as seguintes rotas:
192.168.0.0, 255.255.0.0, 10.0.0.2
192.168.1.0,255.255.255.0, 10.0.0.6
0.0.0.0, 0.0.0.0, 200.135.37.254
... a rota escolhida será a segunda (192.168.1.0,255.255.255.0, 10.0.0.6). Se chegar outro
datagrama endereçado a 192.168.10.18, a rota escolhida será a primeira. Por fim, se um terceiro
datagrama chegar, desta vezes endereçado a 150.162.14.10, a rota escolhida será a terceira (também
conhecida como rota default).
O roteador sempre escolhe a rota mais específica para um determinado endereço de destino.
A rota mais específica é aquela que possui a maior máscara de rede. Uma máscara de rede tem 32
bits (o mesmo que um endereço IP), e seu tamanho é dado pelo número de bits em 1 que possui.
Assim, no exemplo anterior a maior máscara de rede é 255.255.255.0 (possui 24 bits em 1), seguida
por 255.255.0.0 (16 bits em 1) e finalmente 0.0.0.0 (nenhum bit em 1). Isto fica mais claro ao se
observarem essas máscaras em binário:
11111111 11111111 11111111 00000000
255
255
255
0
11111111 11111111 00000000 00000000
255
255
0
0
00000000 00000000 00000000 00000000
0
0
0
0
1 Datagrama é nome dado a uma mensagem do protocolo IP
2 Internet Protocol
O teste de uma rota, para verificar se é adequada para determinado endereço IP de destino,
se faz com o seguinte procedimento:
1. Faz uma operação AND bit-a-bit entre o IP de destino e a máscara de rede
2. Compara-se o resultado dessa operação com o prefixo de rede da rota testada: se for igual,
então a rota é adequada ao IP de destino
Voltando-se ao exemplo do roteador com a tabela de rotas:
192.168.0.0, 255.255.0.0, 10.0.0.2
192.168.1.0,255.255.255.0, 10.0.0.6
0.0.0.0, 0.0.0.0, 200.135.37.254
Para identificar a rota para o IP de destino 192.168.18.10, o roteador começa pela rota mais
específica (no caso, 192.168.1.0,255.255.255.0, 10.0.0.6):
192.168.18.10 AND 255.255.255.0 = 192.168.18.0
Em binário:
11000000 10101000 00010010 00001010 192.168.18.10
AND 11111111 11111111 11111111 00000000 255.255.255.0
----------------------------------------------------------11000000 10101000 00010010 00000000 192.168.18.0
... que é diferente do prefixo de rede dessa rota (192.168.1.0). O roteador então testa a
próxima rota mais específica (192.168.0.0, 255.255.0.0, 10.0.0.2):
192.168.18.10 AND 255.255.0.0 = 192.168.0.0
Em binário:
11000000 10101000 00010010 00001010 192.168.18.10
AND 11111111 11111111 00000000 00000000 255.255.0.0
----------------------------------------------------------11000000 10101000 00000000 00000000 192.168.0.0
... que desta vez é igual ao prefixo de rede da rota (192.168.0.0). Portanto, o roteador
escolhe essa rota para encaminhar o datagrama.
Exercício
Modele um algoritmo para escolher a rota mais adequada para o encaminhamento de um
datagrama IP. Assuma que a tabela de rotas reside em memória – na verdade, você deve inclui-la em
seu algoritmo como se fosse uma constante. Identifique os dados de entrada e de saída, e informe
como devem ser modelados (que variáveis e de que tipos). O algoritmo deve ser inicialmente
modelado em fluxograma e pseudo-linguagem, para então ser traduzido para linguagem C.