Algoritmo Link State
Protocolo OSPF
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Algoritmo Link State
 Baseado no conceito de mapas distribuídos
todos os nodos do mapa tem uma cópia
 O conteúdo das mensagens de atualização são as
ligações de um nó a seus vizinhos, a identificação
do enlace e o custo.
 As informações divulgadas são acrescentadas ao
mapa de quem as recebe
 Caso, haja alterações do mapa devido a divulgação
as rotas são recalculadas.
 O protocolo OSPF Implementa o algoritmo Linkstate
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Link State - Mapa
 Exemplo
A
1
3
B
2
C
4
5
D
E
6
De
A
A
B
B
B
C
C
D
D
E
E
E
Para
B
D
A
C
E
B
E
A
E
C
B
D
Enlace
1
3
1
2
4
2
5
3
6
5
4
6
Métrica
1
1
1
1
1
1
1
1
1
1
1
1
 Cada registro é divulgado pela estação
“responsável”
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Link State - Flooding
A
1
3
B
2
C
Falha de comunicação
4
5
D
E
6
 A e B detectam a falha
 A e B alteram os registros na base de dados pelos
quais são responsáveis
 A gera atualização para D e B para C e E
 C, D e E irão desencadear novas atualizações
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Flooding
 D enviará para E, C enviará para E e E enviará
para C e B
 Loop?
Prevenção do loop é feita pela utilização de um número
de seqüência no pacote de atualização
 Algoritmo
Recebe mensagem
Seleciona registro na base
se o registro não está presente
então adiciona e envia uma mensagem em broadcast para os
vizinhos, exceto pelo enlace pelo qual foi recebida
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Flooding
senão
se o número de seqüência da entrada na base < o número de seqüência da
mensagem
então atualiza e gera broadcast
senão
se número da base > o número de seqüência da mensagem
então
gera uma nova divulgação
atualiza o número de seqüência da mensagem
envia a mensagem para interface pela qual foi recebida
senão
se os números de seqüência são iguais não faz nada.
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Exemplo
 Mensagem de A
From A, to B, link 1,
distance = infinite,
number = 2.
 Mensagem de B
From B to A, link 1,
distance = infinite,
number = 2
Tabela Final
De
A
A
B
B
B
C
C
D
D
E
E
E
Para
B
D
A
C
E
B
E
A
E
C
B
D
Enlace
1
3
1
2
4
2
5
3
6
5
4
6
Métrica
inf
1
inf
1
1
1
1
1
1
1
1
1
Seq.
2
1
2
1
1
1
1
1
1
1
1
1
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Adjacências - Atualização
A
1
3
B
2
Falha de comunicação
C
4
5
D
E
 Duas versões do mapa
Mapa 1 -BCE
Mapa 1 - AD
A B 1 inf
B A 1 inf
D E 1 inf
2
2
2
A B 1 inf
B A 1 inf
E D 1 inf
2
2
2
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Atualizações
A
3
1
B
2
Falha de comunicação
C
4
5
D
E
 Mapa BCE sofrerá atualizações que não serão
refletidas no AD
Mapa 1 -BCE
A B
B A
B C
C B
E D
1
1
2
2
1
inf
inf
inf
inf
inf
2
2
2
2
2
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Reestabelecimento
 Ao restabelecer a comunicação entre AD e BCE é
necessário que ocorra um processo de sincronização
 Pelo processo normal leva muito tempo para
convergir
 Sincronização - “data base description packets”
1.ª fase: nodo distribui o seu mapa
2.ª fase: solicita aos vizinhos os “registros interessantes”
3.ª fase: flooding
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Problemas - No. de Seq.
 Quando um nodo da rede cai e volta rapidamente
não terá sido retirado dos mapas dos outros hosts
irá realizar o flooding com seu número de seqüência
incial
esse número será mais antigo (menor) que os mantidos
nos mapas dos vizinhos
então para acelerar a convergência, ele deve aceitar o
número de seqüência que os outros irão lhe enviar,
incrementá-lo e imediatamente retransmitir seus
registros com o novo número.
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Shortest Path First - SPF
 Dijkstra - SPF
1. Inicialize o conjunto E contendo somente o nodo fonte, e R
contendo todos os outros nodos. Inicialize a lista de caminhos O
contendo os segmentos que partem de S. Cada segmento tem
custo igual ao valor da métrica. Ordene O em em forma
crescente.
2. Se a lista O está vazia, ou se o primeiro path tem métrica
infinita, marque todos os nodos em R como inalcançáveis e
termine o algoritmo.
3. Examine P, o menor caminho de O. Remova P de O. Atribua
a V o último nodo em P. Se V já está em E, volte ao passo 2.
Senão P é menor caminho para V, retire V de R e adicione em
E.
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Shortest Path First - SPF
4. Construa um conjunto de caminhos candidatos concatenando
P e e cada um dos enlaces iniciando em V. O custo destes
caminhos é o resultado da soma do custo de P e a métrica do
enlace adicionado. Insira-os em O em ordem crescente. Volte
ao passo 2.
Redes de Computadores - PUCRS - Prof.ª Ana Benso
OSPF
 O protocolo OSPF utiliza outros protocolo para
implementar seus mecanismos
Hello, Flooding e Exchange
 Funcionamento
Envia um pacote Hello para conhecer seus vizinhos
Em redes de acesso múltiplo elege um roteador
designado e um back-up
Cada roteador envia periodicamente um LSA (link state
advertisement)
Calcula as rotas
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Informações Seguras –
Protocolo OSPF
 Flooding tem reconhecimento hop-by-hop
 Os pacotes de descrição são transmitidos de forma
segura
 Cada registro é protegido por um timer e é
removido da base de dados caso não receba
atualização
 Todos os registros são protegidos por checksum
 Todas as mensagens podem ser autenticadas por
password.
Redes de Computadores - PUCRS - Prof.ª Ana Benso
OSPF x RIP
 Convergência rápida e sem loops
 Suporta métricas precisas e se necessário várias
métricas
 Suporta múltiplos caminhos para um mesmo
destino
 Múltiplas Áreas
 Representação diferenciada para rotas externas
Redes de Computadores - PUCRS - Prof.ª Ana Benso
OSPF – Roteadores
Vizinhos
 “Vizinhos” são aqueles que compartilham o
mesmo enlace físico
 Um roteador OSPF descobre os seus vizinhos
enviando e recebendo mensagens do protocolo
HELLO
Um roteador envia a cada 10 segundos uma mensagem
de HELLO em multicast para todos os enlaces
diretamente conectados a ele
 Endereço de multicast: 224.0.0.5 (ALLSPFRouters)
Vizinhos respondem enviando uma mensagem de
HELLO periodicamente
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Após o HELLO
 Após os vizinhos terem sido estabelecidos eles
passam a trocar informações de roteamento
 Quando seu mapa da topologia está totalmente
atualizado, ou seja, sincronizado, eles são
denominados “fully adjacents”
 O Hello continua sendo transmitido continuamente a
cada 10 segundos
As informações de topologia enviadas pelo transmissor
permanecem na tabela enquanto forem recebidas
mensagens de Hello.
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Exemplo - OSPF
A
1
3
B
2
C
4
Falha de comunicação
5
D
A
3
E
1
B
2
C
4
5
D
E
Restabelecendo (ou iniciando)
de comunicação
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Exemplo ...
Link Status Acknowledge
Link Status Update
Link Status Request
Database Description
Database Description
Hello
Hello
A
3
1
B
2
C
4
5
D
E
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Frame OSPF
Version
Type
1
2
3
4
5
Hello
Database Description
Link Status Request
Link Status Update
Link Status Acknowledment
Message Length
Source Route IP Address
Area ID
Checksum
Authentication Type
Authentication (Octets 0-3)
Authentication (Octets 4-7)
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Hello Message
OSPF Header Type=1
Network Mask
Dead Timer
Hello Inter G. Priority
Designated Router
Backup Designated Router
Neighbor1 IP Address
...........
Neighborn IP Address
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Database Descriptor
OSPF Header Type=2
Must be Zero
I M S
1
2
3
4
5
Router Link
Network Link
Summary Link (IP Network)
Sumary Link (link to border)
External Link
Data Base Sequence Number
Link Type
Link ID
Advertising Router
Link Sequence Number
Link Checksum
Link Age
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Link Status Request
Message
OSPF Header Type=3
Link Type
Link ID
Advertising Router
.........
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Link Status Update Message
OSPF Header Type=4
Number of Link Status Advertisements
Link Status Advertisement1
..............
Link Status Advertisement n
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Link Status Advertisment
Link Type
Link ID
Advertising Router
Link Sequence Number
Link Checksum
Link Age
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Topologias de Rede
 O OSPF trabalha com as seguintes topologias
Broadcast Multiaccess
 Pode ser um LAN com uma Ethernet, Token Ring ou FDDI
 O OSPF envia tráfego em broadcast
 É necessário escolhar um roteador desginado (DR) e um
roteador designado de backup (BDR)
Ponto-a-Ponto
 Não é necessário um roteador designado, nem seu backup
 Tráfego em multicast (224.0.0.5)
Ponto-a-Multiponto
 Uma interface de origem conectada a vários destinos
 Trata como uma série de ligações ponto-a-ponto
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Topologias
Nonbroadcast Multiaccess
 Parece com ponto-a-ponto, mas muitos destinos são possíveis
 WAN: X.25 ou Frame Relay
 OSPF trata esta rede como uma topologia de broadcast,
representada por uma subrede
 Necessita de seleção manual do DR e do BDR
 Todo tráfego entre vizinhos será replicado em todos os enlaces
físicos usando um endereço de unicast, uma vez que multicast
e broadcast não são suportados.
Frame Relay
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Topologias...
Virtual Links
 Conexão virtual para uma área remota que não tem qualquer
conexão com o backbone
 Usada para criar um túnel de tráfego
 Envia dados usando endereços unicast
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Roteadores Designados
 São necessário em redes de broadcast para
evitar a criação de inúmero enlaces entre todos os
roteadores
diminuir o número de mensagens do OSPF circulando
na rede
 Como eleger?
Dinâmica
 O roteador com o ID ou endereço IP mais alto
Manual
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Múltiplas Métricas
 Tipos de métricas
maior throughtput
menor delay
custo mais baixo
melhor confiabilidade
 Tratar diferentes métrica exige
documentar várias métricas para os diferentes enlaces
calcular diferentes tabelas de roteamento para cada
métrica
representar a métrica selecionada em cada pacote
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Exemplo
1
A
2
C
B
1: enlace de satélite T1
2 e 3: enlace T1 terrestre
4 e 5: enlaces de 64Kbps terrestre
E
OBS: satélite tem delay de 275 ms
enlaces terrestre tem 10 ms
5
3
4
D
 D, C, A e B tem throughput de 1.5 Mbps e delay de 295ms
 D, E e B tem throughtput de 64kbps e delay de 20ms
 1.ª Métrica: throughput
 2.ª Métrica: delay
 Decisões de métricas tem de ser coerentes em todos os
roteadores
 Considere que D receba de B um pacote e o roteie considerando o
melhor throughput, então irá para C.
 E C roteie considerando o melhor delay ?????
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Solução
 Os pacotes devem ter a indicação clara de qual a
métrica a ser utilizada.
 OSPF versão 2 suporta esta extensão
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Múltiplos Paths
A
1
3
B
2
C
4
5
D
E
6
 Caminhos de A para E através de B ou D tem a
mesma métrica
 Análises Matemáticas provam que dividir o
tráfego é mais eficiente
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Múltiplos Paths
 Enlaces com métricas diferenciadas?
Dividir proporcionalmente
Loop
 Solução: um pacote enviado por X pode ser retransmitido
através de Y, somente se Y for mais próximo do destino que o
nodo local.
 Altere o algoritmo SPF para esta situação
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Múltiplas Áreas
 Redução do tamanho da base (mapa)
 Tempo de processamento das rotas
 Redução do volume de mensagens de atualização
 Roteamento hierárquico: divide a rede em um
conjunto de partes independentes interligadas por
um área de backbone.
Os mapas de área incluem somente o estado do enlaces
da área
Flooding ocorre somente até os limites da área
Rotas são calculadas somente para os enlaces da área
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Múltiplas Áreas
 Roteadores da Área de Backbone
Area Border Routers
Eles mantém uma mapa para cada área
Emitem mensagens contendo “summary links”
 Roteadores de Borda Externor
External Border Routers
Redes de Computadores - PUCRS - Prof.ª Ana Benso
Exemplo
b1
BB0
BB1
b2
A1
a1
c1
AB2
BC1
b3
a2
A3
b6
b5
AB4
a3
C2
c2
BC3
C4
c3
b4
 Áreas A e C
 Backbone B
 AB2 receberá de AB4 informações sumarizadas
 AB2 receberá de BB0 rotas externas
Redes de Computadores - PUCRS - Prof.ª Ana Benso