Redes I
Encaminhamento (Routing)
Prof. Dr. Amine BERQIA
[email protected]
http://w3.ualg.pt/~bamine/
Encaminhamento IP

Executado por routers
 Baseado em tabelas
 Encaminha numa base de pulo-por-pulo
(hop-by-hop)
 Endereço de destino é utilizado para
determinação da rota
Sumário Routing/Forwarding






Retira cabeçalhos da camada 2
Extrai o campo de endereço de destino, D,
Procura D na tabela de encaminhamento
Procura próximo endereço de salto, N,
Envia datagrama para N
Adiciona cabeçalhos da camada 2
Operações Básicas de Routing (1)
Basic Routing
A.34
4321
A.24
3483
B.29
4923
A.1
D.1
D.3
3984
D.90
1834
B.56
4002
B.1
Router
C.1
C.45
8732
C.88
6202
Operações Básicas de Routing (2)
Routing Table
Layer 2 <--> Layer 3 Table
Network
Interface
Network.Host
Layer 2
A
0
A.34
4321
B
1
A.24
3483
C
2
B.29
4923
D
3
B.56
4002
C.45
8732
C.88
6202
D.3
3948
D.90
1834
Operações Basicas de Routing (3)
From C.45 to A.34
C.45 knows that A.34 isn't on the same net and sends it to router at C.1
Note DA for layer 2
3012
8732
JIP
A
34
C
45
Data
FCS
Inside the router the Layer 2 headers and trailers are removed leaving only the
layer 3 packet.
The router looks up the packet's DA in the routing table and forwards to the
appropriate interface.
A
34
C
45
Data
45
Data
At the interface, layer 2 headers and trailers are added back.
DA is the address of the destination host.
SA is the address of the router.
FCS is recalculated.
4321
2398
JIP
A
34
C
FCS
Routing de TCP/IP
IP Routing
140.192.10.5
0060CA23BE45
140.192.10.25
0060CA34CD29
140.192.100.34
0060CA4AD2EE
140.192.10.1
00C0C1AA3411
140.192.201.1
00C0C1AA3410
140.192.201.22
0060CA3499CC
140.192.201.126
0060CA3499DE
140.192.100.8
0060CAAABBCC
140.192.100.1
00C0C1AA3412
Router
140.192.34.1
00C0C1AA3413
140.192.34.34
0060CA114499
140.192.34.35
0060CA7819AA
Routing TCP/IP (2)
Layer 2 <--> Layer 3 Table
ARP Table
Routing Table
Network
Interface
Network.Host
Layer 2
140.192.10.0
0
140.192.10.5
0060CA23BE45
140.192.100.0
1
140.192.10.25
0060CA34CD29
140.192.201.0
2
140.192.100.34
0060CA4AD2EE
140.192.34.0
3
140.192.100.8
0060CAAABBCC
140.192.201.22
0060CA3499CC
140.192.201.126
0060CA3499DE
140.192.34.34
0060CA114499
140.192.34.35
0060CA7819AA
TCP/IP Routing(3)
From 140.192.34.34 to 140.192.10.5
140.192.34.34 knows that 140.192.10.5 isn't on the same net and sends it to router at 140.192.34.1
Note DA for layer 2
00C0C1AA3413
0060CA114499
IP
140.192.10.5 140.192.34.34
Data
FCS
Inside the router the Layer 2 headers and trailers are removed leaving only the
layer 3 packet.
The router looks up the packet's DA in the routing table and forwards to the
appropriate interface.
140.192.10.5 140.192.34.34
Data
At the interface, layer 2 headers and trailers are added back.
DA is the address of the destination host.
SA is the address of the router.
FCS is recalculated.
0060CA23BE45
00C0C1AA3411
IP
140.192.10.5 140.192.34.34
Data
FCS
Exemplo duma tabela de Routing IP
 Tabela
(b) é para router do centro (a)
O Conceito
O endereço de destino num cabeçalho dum
datagram refere-se sempre ao último destino.
Quando um router remeter o datagrama a outro
router, o endereço do próximo salto não aparece
no cabeçalho do datagrama.
Requisitos dum Protocolo de
Routing
 Tamanho de tabela de encaminhamento eficiente
 Mensagens de controlo de encaminhamento
eficientes
 Robustez e fiabilidade
prevenir loops
evite buracos negros
tempo de reconvergência é curto
Fonte de Informação da tabela de
Rotas
Manual
• Tabela criada à mão
• Útil em redes pequenas
• Útil se rotas nunca mudam
Automático
• tabelas criada/actualizada por software
• Necessário em redes grandes
• Altera rotas de quando ocorrem falhas
Calcule Caminho melhor/mais curto
Métrica Possível
• distância geográfica
• custo económico
• capacidade
Algoritmos para Calcular Caminho
mais Curto
Distance Vector
• Troca que tabelas de routing com routers
vizinhos
• por exemplo, RIP, RIPv2
Estado de ligação
• Routers trocam informação do estado de
ligação
• por exemplo, OSPF
Distance Vector



Routers anunciam periodicamente e aprendem
sobre redes IP
Custo da rota está baseado em saltos até à rede
(número de routers para passar)
Quando acontece falhas de ligações cálculos são
feitos de novo
Problema de Contagem Infinita


O que acontece quando a ligação 1 < - >5 falha?
Será que 5 pensa que pode chegar lá através do 2?
Resolver o Problema de Contagem
Infinita

Esperar
• Espere por um período de tempo antes de trocar caminhos.
Anunciar rota valida com custo infinito. Baseado em
temporizadores.

Informar o caminho completo
• Garante que não há loops, mas caro.

Horizonte dividido (split horizon)
• Não anuncie rotas a vizinhos se a rota foi recebida daquele vizinho.
Não é à prova de falha.
Outras Melhorias de Distance
Vector

Actualizações despelotadas
• Anuncia mudanças assim que as aprende. Pode ajudar a melhorar
tempo de convergência. Pode criar instabilidade de
encaminhamentos por agitar rotas.

Poison Reverse
• Usado com Split Horizon. Anuncia custo infinito no lugar de nada.

Algoritmo de Actualização difusa (DUAL)
• Parecido ao Esperar, mas routers são informados de caminhos
quebrados. Complexo. Não popular.
Estado de ligação
Routers distribuem informação de custo de
ligação e de topologia para todos os outros
routers na sua área.
 Todos os routers têm informação completa
sobre a rede.
 Cada router calcula o seu próprio caminho
óptimo para os destinos.
 Assegura ambientes livres de loops.

Protocolo Gateway
AS - Sistema Autónomo:
Redes geridas por organizações independentes (por exemplo, companhias.)
Regiões administrativas que contêm um conjunto de redes e routers.
Um local(site) pode administrar o encaminhamento dentro de sua região do modo que desejar, mas
fluxos de informação de encaminhamentos entre regiões só por mecanismos cuidadosamente
controlados
IGP - Protocolo de Gateway Interior:
Um protocolo de encaminhamento o que corre dentro dum AS.

Os AS’s devem poder se isolar de outros locais. Eles devem poder manter as internets locais delas
operando mesmo quando outras partes da Internet falharam.

Gateways locais (provavelmente) não querem saber (em detalhe) sobre mudanças topologicas que
acontecem longe.

Locais(sites) querem controlo administrativo sobre as gateways e redes delas e podem não querer
correr os mesmos protocolos de encaminhamento que outros locais.
EGP - Protocolo de Gateway Exterior:
Um protocolo de encaminhamento que corre entre AS’s. O que liga sistemas autónomos:

Permite a um local(site) anunciar ao resto do mundo um caminho para as redes dentro de seu
sistema autónomo.

Permite a um local(site) aprender sobre redes localizadas em outras regiões autônomas.
Protocolo de Gateway Interior: OSPF
OSPF - Open Shortest Path First
Está a tornar-se o IGP principal. Permite uma hierarquia de endereçamento de modo que
torna o encaminhamento mais fácil.
As requisitos utilizados no desenho do OSPF :







Tinha de ser “Sistema Aberto" - publicado em literatura.
Tinha que suportar várias métricas de " distância", incluindo comprimento físico,
atraso, capacidade, etc.
Tinha de ser dinâmico, capaz de adaptar-se a topologias variáveis.
Tinha de suportar " tipo de serviço" - capaz mudar comportamento do
encaminhamento baseado em características dos quadros.
Tinha de fazer balanceamento de carga; capaz utilizar múltiplas rotas no lugar de
uma de cada vez.
Tinha de suportar sistemas hierárquicos de forma que nenhum router precisava
entender a rede inteira.
Tinha de fornecer algum tipo de segurança.
Protocolo de Portal interior: OSPF
OSPF suporta três tipos de redes:

Linhas ponto-a-ponto entre dois routers.

Redes multi-acesso com difusão (LANs).

Redes multi-acesso sem difusão(comutação
de pacotes WANs). [Uma rede multi-acesso
é uma que tem múltiplos routers, cada um
pode falar com todos os outros. Esta é uma
propriedade de LAN/WAN comum.]
Na forma que OSPF está definido este:

Divide um Sistema Autónomo em" áreas."
Uma área é uma rede ou conjunto de redes
contíguas. Não é necessário que todos os
routers dum AS pertençam a uma Área.

Utiliza um algoritmo de ligação de estado
dentro de uma área. Distâncias são
calculadas baseado no comprimento, ou
outras propriedades. Ver figura.
Protocolo de Gateway exterior: BGP
BORDER GATEWAY PROTOCOL(BGP):




BGP é o Exterior Gateway Routing Protocol (EGP) mais usado.
Protocolo Distance-Vector , não só considera a
distancia, mas também para critérios de rota específicos.
BGP pode tomar em consideração políticas de conta, questões de
segurança e economia.