HYMAD: Hybrid DTN-MANET routing
for dense and highly dynamic
wireless networks
Autores: John Whitbeck e Vania Conan
Apresentação: Glauco Fiorott Amorim
Roteiro
Introdução
 Motivação
 Proposta do Protocolo HYMAD

Roteamento Intra-grupo
 Roteamento Inter-grupo

Simulações e Resultados
 Conclusão
 Críticas

Introdução

A utilização de redes sem fio tem crescido muito nos últimos
anos
 Redes sem fio Ad Hoc
 Não necessita de infra-estrutura
 Baixo custo
 Auto-configurável
 Protocolos de roteamento baseados na conectividade
dos nós
 Delay/Disruption-Tolerant Network (DTN)
 Tolerante a atrasos
 Conexões esporádicas
 Redes conectadas intermitentemente
DTN

Redes onde a conectividade fim-a-fim não é
garantida

Enlaces existem em função do tempo

Protocolos de roteamento utilizam o paradigma:
store-carry-and-forward
Protocolo de Roteamento Epidemic
F
B
E
F
C
F
F
F
F
A
D
Protocolo de Roteamento Spray-and-Wait
1
D
F
1
1
D
E
D
B
1
4
D
D
2
A
D
D
2
D
D
C pode entregar a msg a D
C
Problema

Muitos cenários onde:
Redes razoavelmente densas
 Mobilidade dos usuários é muito alta


Rede freqüentemente
conectados
separada
em
grupos

Nestes cenários, os protocolos tradicionais de
redes Ad Hoc e DTNs não são satisfatórios
Protocolo HYMAD
A idéia principal é usar todos os grupos de nós ao
invés de um nó individual como foco do protocolo
DTN
 Cada nó regularmente difundi duas mensagens de
controle:

Um vetor de distância alterado para todos os membros
do seu grupo (mensagem do algoritmo do grupo)
 Uma lista de mensagens mantidas pelos membros do
seu grupo, com seus respectivos destinos, responsáveis
e número de cópias (lista de mensagens no grupo)


Duas fases: roteamento intra-grupo e inter-grupo
Roteamento Intra-grupo


Utiliza um algoritmo vetor de distância simples. Cada nó
roda periodicamente o algoritmo e difundi seu vetor de
distância
Pequena diferença


Se o próximo salto não está disponível, o nó se responsabiliza pela
mensagem, armazena em sua lista e avisa aos seus vizinhos
Definição do grupo:


Diâmetro
 Preserva a igualdade entre os nós e possibilita a migração entre
os grupos com facilidade
Regra:
 O grupo irá aceitar um novo membro se o seu diâmetro é menor
do que um parâmetro máximo permitido
Criação do Grupo
b
(b:0, b:1,
(a:0)
(a:0,
a:1) c:1, d:1)
(b:0, a:1)
a
(d:0,
a:1,
c:1,
b:2)
(a:0,
(a:0)
(c:0,
b:1,
a:1)
c:1,
d:1)
(d:0, a:1)
(a:0)
(a:0,
(d:0, b:1,
a:1,(c:0,
c:1,(a:0)
d:1)
b:2)
a:1)
c
d
(d:0,
(a:0,
(e:0, b:1,
d:1,
a:1)
a:1, c:1,
a:2) d:1)
b:2)
e
(d:0,
(e:0, d:1,
a:1, c:1,
a:2) b:2)
Roteamento Inter-grupo
Utiliza o roteamento Spray-and-wait
 Nós de borda conhecem a formação dos grupos
adjacentes
 Pode pedir mensagens aos nós que mantêm a
custódia da mesma para repassar ao outro grupo.
Duas possibilidades:

Se o destino da mensagem está no grupo vizinho,
requisitar a mensagem e repassá-la
 Se seu grupo tem mais de uma cópia, pode requisitar o
máx(1, nc/nb+1) e repassá-la, onde: nc é o número de
cópias e nb é o número dos nós de borda do grupo

Roteamento Inter-grupo

Quando um nó de borda recebe uma cópia de um
grupo adjacente ele pode:
Se o destino pertence ao grupo, repassá-la utilizando o
roteamento intra-grupo
 Caso contrário, selecionar aleatoriamente um membro
para ser o responsável pela mensagem


Dois tipos de mensagens são usadas:
Requisição de uma cópia
 Redução no número de cópias

Exemplo do protocolo de Roteamento
Discussões

Reação às mudanças topológicas


Muitas situações podem fazer com que os grupos tenham vários nós
responsáveis pela mesma mensagem
 Lista de mensagens no grupo e Redução do número de cópias
Gerenciamento do número de cópias



Envia uma requisição de cópia
Estima o número de cópias armazenadas e o número de nós de
borda para calcular o número de cópias repassadas
Usa a mensagem de redução de cópias para que os nós
responsáveis reduzam o número de cópias
Discussões

Escolha do diâmetro do grupo


Escolha do diâmetro envolve um trade-off:
 Visão mais atualizada da topologia
 Tempo de convergência dos grupos
Dmax deveria ser escolhido para permitir que nós
com afinidades pudessem permanecer no mesmo
grupo
Simulações e Resultados
HYMAD foi implementado no simulador ONE
 No cenário padrão, o buffer considerado foi de
100MB, tamanho da mensagem de 10kB/s,
velocidade de transmissão de 100kB/s e TTL
infinito
 Dois tipos de simulação:

Modelo baseado no Random Waypoint
 Trace de conectividade Rollernet


20 rodadas para cada cenário e 95% de intervalo
de confiança
Simulações e Resultados – Random
Waypoint
Overhead nos enlaces x períodos de criação de
novas mensagens
 Mensagens são criadas a cada segundo

Comparação entre os protocolos
simulando congestionamento
Influência da conectividade da rede
Influência do número de cópias
Simulação e Resultados - Rollernet
Simulação e Resultados - Rollernet
Simulação e Resultados - Rollernet
Conclusões



Autores identificaram uma nova classe de redes sem fio
móveis com alta mobilidade de nós e razoável densidade
onde protocolos convencionais de redes ad hoc e DTN não
são satisfatórios
Simulações mostram que o HYMAD tem um desempenho
melhor que o Spray-and-wait
Existem oportunidade de pesquisa em:




Dmax precisa ser um parâmetro para toda a rede?
Ele poderia ser dinâmico e quais nós deveriam concordar com isso?
Diferentes algoritmos de particionamento de grupo deveriam ser
investigados
Pares de protocolos Manet/DNT mais elaborados deveriam ser
explorados
Críticas

O protocolo proposto deveria ter sido comparado com pelo
menos um outro protocolo híbrido

Nos resultados, a comparação é feita na maioria das vezes
com o Spray-and-wait clássico, apesar de alguns resultados
mostrarem que o Epidemic tem um desempenho melhor

A métrica de atraso deveria ser melhor explorada nos
resultados apresentados

As figuras dos resultados deveriam estar melhor distribuídas
no artigo para que fossem próximas aos comentários no
texto