Optimized Link State Routing
Universidade Federal do Rio de Janeiro
COPPE - UFRJ
Julio Heitor Silva Nóbrega
Agosto 2006
Introdução





Projetado para redes móveis e sem fio;
Utiliza inundação para sincronizar as bases de
dados;
Implementa o algoritmo de caminho mínimo;
Utiliza mensagens HELLO para verificar atividade
de links;
Suporte a inclusão de novas funcionalidades.
Inundação



Todos os nós da rede enviam as
atualizações em broadcast.
Excesso de pacotes na rede.
Maior dificuldade em contornar
possíveis congestionamentos.
Inundação
Multipoint Relays (MPRs)



Nós selecionados que ficarão encarregados de
fazer a inundação.
Objetivo é minimizar o overhead da inundação na
rede, reduzindo mensagens redundantes.
Cada nó deve montar um conjunto de seus MPRs
e, sempre que uma atualização chegar, este deve
enviar apenas para seus vizinhos selecionados.
Multipoint Relays (MPRs)


Um nó seleciona um conjunto MPR de seus nós
vizinhos de modo que estes consigam alcançar
todos os nós vizinhos de 2ª ordem do nó que os
selecionou.
Essa condição é necessária pois, numa rede sem
fio, nem todos os nós da rede estão ao alcance um
dos outros. Então, a inundação ficará ao encargo
dos nós vizinhos para enviar informações
atualizadas sobre a rede para nós distantes.
Multipoint Relays (MPRs)
1.
2.
3.
4.
5.
Começe com um conjunto MPR vazio;
Calcule D(y), para todos os nós y de N, onde N é a lista de vizinhos de um
nó e D(y) o número de vizinhos de y;
Adicione ao conjunto MPR apenas os nós de N que fornecem
alcançabilidade para algum nós de N2. Remova esse nó alcançável da lista
N2;
Enquanto existir nós na lista N2 que não são alcançáveis por algum nó do
conjunto MPR faça:

Pra cada nó y da lista N, calcule o número de nós em N2 que ainda
não são alcançáveis por pelo menos um nó MPR mas que é
alcançável por esse nó y.

Adicione ao conjunto de MPRs o nó que alcançar o maior número
de vizinhos da lista N2 e remova esses nós da lista N2 .
Some todos os conjuntos MPRs de cada uma das interfaces,
formando um único conjunto.
Multipoint Relays (MPRs)
Multipoint Relays (MPRs)



Quanto menor o conjunto de MPR menor será o
overhead da inundação.
Em alguns casos pode ser necessário selecionar nós
MPRs redundantes (back-up) aumentando o tamanho
do conjunto.
Isso ocorre quando, em uma rede móvel, os nós deixam
de ser vizinhos uns dos outros com muita freqüência.
Os MPRs de back-up fornecerão rotas alternativas, sem
a necessidade de se recalcular o conjunto MPR.
Mensagens HELLO



Funcionamento parecido com o protocolo HELLO
do OSPF.
Os objetivos principais das mensagens HELLO no
protocolo OLSR é sinalizara seleção de vizinhos
MPRs, detectar vizinhanças, bem como verificar
alcançabilidade dos enlaces.
Mensagens HELLO são enviadas dentro da carga
útil de mensagens OSLR.
Mensagens HELLO
Mensagens HELLO

Se o campo “Link Code” estiver setado um valor
menor que 15, este deve ser interpretado como
dividido em dois sub-campos.
Mensagens HELLO


Se o sub-campo ”Neighbor Type”contiver o valor
MPR_NEIGH então este nó foi eleito como
Multipoint Relay do nó que enviou a mensagem
HELLO.
O valor SYM_NEIGH para esse campo, significa
que este é um vizinho do nó que enviou a
mensagem, mas não foi selecionado como MPR.
Mensagens HELLO

Através de trocas de mensagens HELLO
entre vizinhos de 1a ordem, um nó pode
obter informações de seus vizinhos de 2ª
ordem, montando assim a lista N2 descrita
anteriormente.
Cálculo do caminho mínimo


Para calcular o caminho mais curto de uma origem
para um destino qualquer, o nó origem deve
rastrear pares conectados em uma ordem
descendente através de seu mapa da topologia.
Primeiramente, o nó origem deve encontrar um par
(X,R) que contém o número mínimo de nós entre X
e R, sendo R o destino. Em seguida, um par (Y,X)
deve ser descoberto, e outro par (Z,Y),e assim por
diante.
Cálculo do caminho mínimo
Conclusões



Em redes densas e com muitos nós, a redução do controle de
tráfego pode ser de magnitude de várias ordens comparado
ao protocolo OSPF que utiliza o algoritmo tradicional de
inundação.
A otimização usando MPRs reduz consideravelmente o
overhead gerado pelas mensagens durante a inundação,
permitindo um controle muito maior sobre possíveis
congestionamentos.
Quanto a segurança, o OLSR não especifica nenhum
algoritmo de criptografia ou autenticação.