roteamento estado enlace

Prévia do material em texto

Redes de Computadores II
Roteamento por Estado de Enlace
Prof. Rodrigo Campiolo
11/10/17
Universidade Tecnológica Federal do Paraná
Departamento Acadêmico de Computação
Bacharelado em Ciência da Computação
 
2
Introdução
● Roteamento por estado de enlace – Link State Routing
● Fundamento:
– os nós mantém o mapa da rede e calculam 
localmente as melhores rotas.
● Principais protocolos:
– IS­IS (Intermediate System to Intermediate System)
– OSPF (Open Shortest Path First)
 
3
Roteamento por estado de enlace
● Passos (Roteadores):
1)  Descobrir seus vizinhos e aprender seus endereços de 
rede.
2)  Medir o retardo ou o custo para cada um de seus 
vizinhos.
3)  Criar um pacote que diga tudo o que acaba de ser 
aprendido.
4)  Enviar esse pacote a todos os outros roteadores.
5)  Calcular o caminho mais curto para cada um dos outros 
roteadores.
 
4
Roteamento por estado de enlace
● Passo 1: Descobrir os vizinhos e aprender os  
endereços de rede.
– Ao iniciar um roteador, é enviado um pacote de 
identificação para todos os vizinhos.
– os roteadores vizinhos  respondem com um 
pacote de identificação.
 
5
Roteamento por estado de enlace
● Passo 1 (cont.)
– Quando os roteadores estão conectados por uma 
LAN, a LAN deve ser considerada um nó virtual.
 
6
Roteamento por estado de enlace
● Passo 2: Medir o custo para cada um dos 
vizinhos.
– Medidas:
● Retardo (echo).
● Comprimento da fila.
● Capacidade da linha.
● Saltos.
– Vantagens e desvantagens das métricas.
 
7
Roteamento por estado de enlace
● Passo 3: Criar um pacote que diga tudo o que 
acaba de ser aprendido. 
– O pacote deve conter: id. do transmissor, número de 
sequência, idade e lista de vizinhos com os custos.
– Questão: Quando criar? Periodicamente, eventos 
significativos, ...
 
8
Roteamento por estado de enlace
● Passo 4: Enviar o pacote a todos os outros 
roteadores. 
– Distribuição deve ser confiável.
– Problemas:
● os primeiros roteadores a receberem os pacotes alteram 
as rotas, logo podem surgir inconsistências, conduzindo 
a laços, perda de pacotes ou retardos.
– Usar o flooding para distribuir os pacotes.
 
9
Roteamento por estado de enlace
● Passo 4 (cont.):
– Pacotes com número de sequência e identificação para 
evitar a duplicação.
– Problemas:
● Se um roteador falhar, a sequência é reiniciada em 0.
● Se o número for adulterado.
– Solução:
● Campo idade  decrementado a cada 1 segundo. 
● Se idade atingir o valor 0, o pacote é descartado.
 
10
Roteamento por estado de enlace
● Passo 4 (cont.):
– Otimizações
● um pacote (flooding) ao chegar em um roteador não é 
imediatamente retransmitido (área de retenção).
● Há confirmação de recebimento de pacotes para evitar 
erros.
● quando a linha fica ociosa, a área de retenção é 
revistada para localizar pacotes ou confirmações a 
serem enviados.
 
11
Roteamento por estado de enlace
● Passo 4 (cont.):
Figura: Área de retenção do roteador B.
* Os vizinhos de B são A, C e F.
* O que fazer se uma cópia chegar?
Recebido por:
 EAB e EFB
 
12
Roteamento por estado de enlace
● Passo 5:
– Calcular o menor caminha usando um algoritmo de 
grafos.
– Algoritmo comumente usado é o de Dijkstra. 
 
13
Roteamento por estado de enlace
● Referências:
– TANENBAUM, Andrew S.; WETHERALL, David. Redes de 
computadores. 5. ed. São Paulo, SP: Pearson, 2011.