Dynamic MANET OnDemand (DYMO)
Universidade Federal do Rio de Janeiro
Programa de Engenharia Elétrica
Natalia Castro Fernandes
Professor: Luís Henrique M. K. Costa
CPE825 - Roteamento em Redes de Computadores
GTA – COPPE
Abril/2006
Introdução

Dynamic MANET On-demand (DYMO)
 Protocolo de roteamento
 Redes
de Múltiplos saltos sem-fio
 Mobilidade
 Reativo
• Armazenamento de rotas ativas
 Simples
 Poucos
estados de roteamento
 Algumas implementações
Introdução

Aplicabilidade
 Redes
móveis de pequena, média
e larga escala
 Nós com restrições de memória
 Simplicidade
 Tráfego
esparso
 Redes baseadas em segurança
Introdução
 Operações
básicas
 Descoberta
e manutenção de rotas
• Route Request (RREQ)
• Route Reply (RREP)
• Route Error (RERR)
 Números
de seqüência
 Atualização
 Loops
 Monitoramento
 Notificação
dos enlaces
da fonte
Funcionamento Básico

Descobrimento de rotas
Tabela de Rot. A
Tabela de Rot. A
Viz. Dest. Nº. Seq
Viz. Dest. Nº. Seq
F
F
1
F
F
1
D B
1
RREP F
D||DF | 1
RREQ
Tabela de Rot. F
F
Viz. Dest. Nº. Seq
A
D
1
RREQ F | D | 1
A
Tabela de Rot. B
Tabela de Rot. B
Viz. Dest. Nº. Seq
Viz. Dest. Nº. Seq
A F
1
RREQ
RREP D
F| F
D || 11
A F
1
D
D
1
B RREQ
RREP F
D||DF | 1
Tabela de Rot. D
D
C
E
Viz. Dest. Nº. Seq
RREQ F | D | 1 B
F
Tabela de Rot. C
Tabela de Rot. E
Viz. Dest. Nº. Seq
Viz. Dest. Nº. Seq
F
C
F
1
F
1
1
Funcionamento Básico
Tabela de Rot. A

Notificação de Erro
Tabela de Rot. B
Viz. Dest. Nº. Seq
F
F
1
B
D
1
Viz. Dest. Nº. Seq
RERR
Dados
D
RERR
D
Dados
Tabela de Rot. F
D
F
1
D
D
1
B
F
Viz. Dest. Nº. Seq
A
A
B
A
RERR D
1
D
C
Viz. Dest. Nº. Seq
E
Tabela de Rot. C
Tabela de Rot. E
Viz. Dest. Nº. Seq
Viz. Dest. Nº. Seq
F
C
F
1
F
Tabela de Rot. D
1
B
F
1
Estrutura de Dados

Tabela de Roteamento
Opcionais
IP
Dest.
Num.
Seq.
IP
Próx.
Salto
Interf.
Próx.
Salto
Tempo Tempo Num.
de
de
de
Val.
Exc.
Saltos
...
Gatew. Pref.
Uso
0-1
0-1
Tamanho da máscara
Estrutura de Dados

Mensagens
 Formato
generalizado
 UDP
 Suporte
a IPv4 e IPv6
 Roteamento ou Erro
Estrutura de Dados

Cabeçalho
IP
Campos das mensagens de
roteamento
 RREQ
e RREP
IP de Destino=LL_ALL_MANET_ROUTERS
...
Campos
Obrigató
- rios
IP Próx. Salto Limite de Saltos IP Destino IP Origem
Num. de Seq. Origem Ult. Num. de Seq. Dest.
End. Adicionais Num. de Seq. Adicionais Num. de Saltos
Campos
Opcionais
Prefixo do destino
Gateway Destino
Ausência do caminho
Ignorar
Apenas destino pode
responder ou intermediários
Origem
Estrutura de Dados

Campos da Mensagem de Erro
IP de Destino=LL_ALL_MANET_ROUTERS
...
Limite de Saltos
Endereços Inalcançáveis
Num. de Seq. dos Nós Inalcançáveis Ignorar
Cabeçalho
IP
Campos
Obrigatórios
Campos
Opcionais
Números de Seqüência
Se perder
seqüência
0
Entra na
rede
1
Incremento
N = N+1



Escolha de rotas mais atualizadas
Evitar loops
Número Próprio de Seqüência
16 bits sem sinal
 0  Valor reservado

Incremento  Número de seqüência desconhecido
Se N = 65535  Seqüência
Incre- 256
mento
Máximo = 65535
 Reinicialização = 256
 Perda do número = 1

Números de Seqüência

Inicialização do Número Próprio de
Seqüência

ROUTE_DELETE_PERIOD

Nó espera fora da rede
• Não emite mensagens de roteamento

Recebe mensagens de controle
• Não encaminha

Pedido de encaminhamento de dados
• Emissão de RERR
• Reinicialização do período de espera

Número de seqüência passa a 1
Route Request

Criação do RREQ
Incremento do número de seqüência
próprio
 Inserir endereço de destino



Rota buscada
Inserir último número de seqüência

Exceções
• Desconhecido  Somente destino
responde
• 0  Qualquer nó responde
– Processo em aberto
Opcionais

Inserir último número e saltos

Exceções
Route Request





Inserir endereço de origem
Inserir número próprio de
seqüência
Inserir campos opcionais sobre a
origem
Número de saltos = 0
Limite de saltos = diâmetro da
rede
Route Reply

Criação do RREP

Incremento do número de seqüência
próprio
Número de seqüência anterior não
preenchido
 Número de seqüência anterior = 0
 Número de seqüência anterior > Número
próprio de seqüência
 Número de seqüência anterior = Número
próprio de seqüência

• Número de saltos anterior desconhecido
• Número de saltos atravessados
desconhecido
• Número de saltos anterior < Número de
saltos atravessados
Processamento das
Mensagens de Roteamento

Ao receber
Decrementar limite de saltos
 Incrementar número de saltos
 Incrementar número de saltos de endereços
adicionais
 Processar informação para destino

Se atual  Atualiza tabela
 Se velha  Descarta mensagem


Processar informação adicional
Se atual  Atualiza tabela
 Se velha  Retira da mensagem

Adicionar outras rotas (opcional)
 Encaminhar / Responder / Esperar

Processamento das
Mensagens de Roteamento

Inserção de novas rotas
 Reduzir
número de RREQs
 Inserção do próprio nó
intermediário
 Incremento
do número de
seqüência
 Informações opcionais
 Controle
1
de rotas
entrada por rota
Atualização da Tabela de
Roteamento

Avaliação da qualidade da informação

Rotas velhas

Número de seqüência novo < número de
seqüência da tabela
• Descartar nova informação

Propensão a loops
Número de seqüência novo = número de
seqüência da tabela
 Número de saltos =0 ou desconhecido

• Descartar nova informação
Atualização da Tabela de
Roteamento
 Inferioridade
 Número
de seqüência novo =
número de seqüência da tabela
 Novo número de saltos ≥ Número de
saltos da tabela
 Descartar nova informação
 Aceitar
demais informações
Atualização da Tabela de
Roteamento

Preenchimento da tabela
Troca das campos pelos valores
recebidos
 Próximo salto é o nó que enviou
 Validade = Tempo atual +
ROUTE_VALID_TIMEOUT
 Valores desconhecidos = 0


Utilização da rota
Verificação do tempo de validade
 Se a rota está vencida


Verificação do tempo de exclusão
• Apagar a rota
Route Error

Rotas inexistentes, indisponíveis ou
inválidas
Lista de nós inalcançáveis
 Números de seqüência (opcional)


Encaminhamento de dados
Entrada inválida ou inexistente na tabela
 Emissão do RERR
 Adição de outras rotas


Próximo salto e interface em comum
Route Error

Processamento

Busca na tabela
Próximo salto = último nó a encaminhar
 Número de seqüência da rota no RERR ou
na tabela =0

• Ou inexistente
• Ou número de seqüência da tabela ≥ número
de seqüência no RERR
Exclusão de rotas da tabela
 Remoção de rotas do RERR

Informação desnecessária
 Se mensagem vazia  Não encaminhar

Considerações de
Segurança


Ausência de mecanismos de
segurança
Identidade Falsa
 Autenticação
 IPSec
 Associação
 Autorização
prévia de segurança
Conclusão

Simples

Não garante melhor caminho


Rotas sem loops
Pontos chaves
Controle do número de seqüência
 Manutenção de rotas



Implementações
Extensões
SDYMO
 DYMO-low
 QoS

Dynamic MANET OnDemand (DYMO)
Universidade Federal do Rio de Janeiro
Programa de Engenharia Elétrica
Natalia Castro Fernandes
Professor: Luís Henrique M. K. Costa
CPE825 - Roteamento em Redes de Computadores
GTA – COPPE
Abril/2006