Universidade do Vale do Rio dos Sinos
Redes Avançadas
Multicast em redes AdHoc
Mateus Raeder
Tipos de Comunicação
 Multicast
 Multicast Ad Hoc
 Classificação de Protocolos
 Árvores

 Protocolos Árvores
 Vantagens e Desvantagens

Malhas
 Protocolos Malhas
 Vantagens e Desvantagens
Outros Protocolos
 Conclusões


Em redes de computadores, é comum a troca de
mensagens entre os participantes

Unicast
 Grande parte do tráfego na Internet era realizado através
de Unicast
 Um transmissor envia uma mensagem apenas para um
receptor, se quer enviar para X receptores, deve enviar X
mensagens
 Aumento do tráfego

Broadcast
 Envia apenas uma mensagem que é recebida por todos os
participantes
 Este envio pode ser inconveniente
 Analogia do aeroporto: Chamada para embarque é ouvida por
todos. Porém, uma pessoa sem interesse no voo não precisaria
ouvir esta mensagem

Anycast
 A mensagem é enviada
 A mensagem vai ser recebida pelo participante mais
próximo (ou com mais chances)



Transmissão de uma mensagem para um grupo
específico ao mesmo tempo
Somente uma mensagem para todos
Diminuição do tráfego desnecessário
 Por
exemplo,
transmissão
clientes
assistindo
uma
determinada

Pode-se “realizar” um Multicast através de Unicast e
Broadcast
 Unicast:
com
destinatários
múltiplas
cópias
enviadas
para
os
▪ Largura de banda desperdiçada (duplicações)
 Broadcast: enviado para todos mas só os interessados
irão aceitar
▪ Sobrecarga na rede

Multicast é importante pois envia apenas para os que
realmente têm interesse

Redes Ad Hoc sem fio apresentam um grande grau de
mobilidade dos seus componentes

O caminho entre dois participantes da rede pode ser
alterado

Assim, os protocolos de roteamento Multicast de redes
fixas não podem ser usados em redes Ad Hoc

Nestas redes, todos os nodos têm a capacidade de
computar, manter e guardar informações de roteamento

Para habilitar a comunicação em grupo nas redes Ad
Hoc protocolos de roteamento foram propostos

O objetivo da maioria dos protocolos multicast Ad Hoc é
construir e manter uma topologia de comunicação
 Levando em conta mobilidade dos nós
 Reações rápidas a mudanças na rede
 Minimizar perdas de pacotes

Protocolos Ad Hoc x Protocolos Redes Fixas
 Redes fixas: protocolos pró-ativos
 Redes Ad Hoc: protocolos sob-demanda

Protocolos de roteamento
classificados em dois tipos:
Multicast
podem
ser
 Dependentes de Aplicação
▪ Somente para aplicações especificas para as quais foram
desenvolvidos
 Independentes de Aplicação
▪ Baseado em Topologia
▪ Baseado em Zonas de Roteamento

Independentes de Aplicação
 Baseado em Topologia
▪ Árvores
▪ Malhas

Cria uma topologia estruturada como uma Árvore

Estabelece uma rota única entre quaisquer dois nós

O meio de transmissão é compartilhado por somente
dois nós, ou seja, só existe uma ligação entre eles

Os arquivos e mensagens são armazenados em um nó
intermediário na rota antes de seguir para o próximo nó

Não existem rotas alternativas

MAODV (Multicast Ad Hoc On Demand Distance Vector)
Um nó origina uma mensagem RREQ quando quer entrar ou mandar uma
mensagem para um grupo multicast

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• O nó manda uma mensagem RREQ para seus vizinhos por broadcast
• Se os nós vizinhos (nós intermediários) não fazem parte do grupo
• Somente atualiza a sua tabela de roteamento com o número de sequência e o caminho
para chegar até o nó que originou o RREQ
• E manda a mensagem RREQ por broadcast até chegar nos membro do grupo multicast

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Quando os nó membros do grupo multicast recebem o RREQ
• Atualiza sua tabela de roteamento
• Manda de volta um RREP unicast de volta para o nó que originou a mensagem
RREQ
• Nós intermediários recebem um RREP, atualizam a tabela de roteamento

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Mandam a mensagem RREP até chegar ao nó que originou a mensagem RREQ
• O nó Source fica esperando por um período de tempo as mensagens RREP
chegarem

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• O nó Source escolhe o menor caminho até chegar nos membros do grupo multicast
descartando as outras rotas.

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Após o período de tempo acabar
• O nó Source manda uma mensagem de ativação (MACT) para a rota escolhida
• Se o nó que receber é parte da árvore multicast ele não propaga o MACT
• Senão ele propaga o MACT até chegar no nó que originou o RREP

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Como o nó não faz parte do grupo multicast
• Ele ativa o nó como sendo parte da árvore e propaga o MACT até atingir o nó que
originou a mensagem RREP

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
B
A
D
• O MACT garante que a árvore não tenha vários caminhos para qualquer nó da
árvore.
• Os integrantes do grupo irão transmitir apenas pelo caminho da rota ativada

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Um nó quer entrar para o grupo multicast

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• o nó Source manda um RREQ por broadcast para o nós vizinhos

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Se os nós vizinhos não são membros do grupo multicast
• Eles atualizam sua tabela de roteamento e mandam a mensagem RREQ para seus
vizinhos até que um membro do grupo receba o RREQ

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Após os nós membros do grupo receberem o RREQ
• Eles mandam um RREP unicast até o nó Source

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• O nó Source fica esperando por um período de tempo as mensagens RREP
chegarem

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Após esperar por um período de tempo
• o nó Source escolhe a menor rota e manda uma mensagem de ativação (MACT)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Se o nó não faz parte da árvore, ele ativa o nó como sendo parte da árvore e
propaga o MACT até atingir os membros da árvore

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
E
F

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• O nó source quer fazer parte do grupo multicast
• Então manda um RREQ para seus vizinhos por broadcast

MAODV (Multicast Ad Hoc On Demand Distance Vector)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Como seus vizinhos já fazem parte do grupo multicast
• Eles mandam um RREP

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Após passar um período de tempo
• O nó Source escolhe a menor rota e manda uma mensagem de ativação (MACT)

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F

MAODV (Multicast Ad Hoc On Demand Distance Vector)
Líder
Grupo Hello:
• Primeiro membro do grupo se torna o líder
• Ele mantém o número de sequência do grupo, repassando-os aos demais nós
• Periodicamente envia mensagens (broadcast) do tipo Grupo Hello
• Os nodos membros da árvore atualizam sua distância em relação ao líder
• Não há RREP para este tipo de mensagem

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Eventualmente, nodos que são membros de um grupo multicast
desejam sair do grupo
 Árvore precisa ser atualizada
 Dois casos podem acontecer
▪ Quando o membro que pretende sair não é folha
▪ Quando o membro que pretende sair é uma folha

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se não for uma folha
▪ Muda seu status (não é mais membro)
▪ Porém, continua como roteador na árvore

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
• Ele deve podar a si mesmo

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
MACT
• Utiliza uma mensagem MACT com a flag P_flag (prune) setada

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
• Após enviar o MACT, o ex-membro retira todas as informações do grupo de suas
tabelas

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
PODA
• Quando o pai recebe um MACT com P_flag setada, remove a entrada do nodo da
tabela do grupo

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
• O nodo que efetuou a poda pode não ser membro do grupo
• Neste caso, ele vai realizar a poda da mesma maneira

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
MACT

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
PODA

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Se for uma folha
• O processo de poda continua até que um membro seja atingido

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Podem ocorrer quebra de links entre os nodos da árvore
 Os
nós detectam links quebrados quando não recebem
mensagem do seu vizinho em um determinado tempo
▪ Pacotes ou mensagens Group Hello (vindas do líder)
 Detectada a quebra, alguém deve tentar
reparar a árvore
 O nó envolvido na quebra que estiver mais
afastado do líder é o responsável pelo reparo
▪ Apenas um dos dois é escolhido para evitar
rotas diferentes e loops
▪ A escolha pelo nodo abaixo da quebra
controla a queda do líder, pois não há ninguém
acima dele

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
= link quebrado
= responsável pelo reparo

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Envia um RREQ com a flag Join setada, e informando a distância dele para o líder
• Somente nós com distância no mínimo menor que a informada respondem
• Isto evita loops e assegura que uma rota até o líder será encontrada

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• RREQ em broadcast

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Encontrou algum nó que está na árvore, responde com RREP em unicast

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Encontrou algum nó que está na árvore, responde com RREP em unicast

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Se recebe resposta, pode enviar MACT para criar um novo ramo

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Se recebe resposta, pode enviar MACT para criar um novo ramo

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
H
G
E
H
F
• E a árvore é reparada

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Porém, o nodo que está tentando reparar pode não receber nenhuma resposta
• Após algumas tentativas sem sucesso, o nodo assume que a árvore foi particionada

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Duas árvores para o mesmo grupo multicast
• A primeira tem um líder (A), a segunda não
• Um novo líder para esta árvore deve ser escolhido

MAODV (Multicast Ad Hoc On Demand Distance Vector)
Líder
• Se o nó que tentou reconstruir a rota for membro do grupo, ele é o novo líder

MAODV (Multicast Ad Hoc On Demand Distance Vector)
PODA
• Se o nó que tentou reconstruir a rota não for membro do grupo e possuir apenas um
filho (um hop até o grupo), ele se poda através do envio da mensagem MACT
• O processo de poda continua até que seja encontrado um membro
• Este membro é o novo líder

MAODV (Multicast Ad Hoc On Demand Distance Vector)
PODA
PODA
• Se não for um membro e possuir mais de um filho, não pode se podar, pois
partionaria a árvore

MAODV (Multicast Ad Hoc On Demand Distance Vector)
MACT
• Seleciona o primeiro filho e manda um MACT unicast com GF_flag (Group Leader)
setada
• Se for membro, é o novo líder
• Se não for membro, continua processo de seleção e envio de MACTs

MAODV (Multicast Ad Hoc On Demand Distance Vector)
• Porém, a árvore que já possuía líder pode ter ficado com um nó que não é membro
• Se for folha, ele começa o processo de poda

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Os links da árvore podem voltar a qualquer momento
 Nós vão começar a receber mensagens Group Hello de líderes
diferentes
 A árvore, então, deve ser unida novamente
C
A
B
D
Group Leader ’
Group Leader
G
E
F

MAODV (Multicast Ad Hoc On Demand Distance Vector)
 Existem agora 2 líderes
 Quando um nodo membro do grupo recebe um Group Hello com
informações de liderança diferente das que possui, começa a
reconstrução da árvore

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• O nodo envia um RREQ (em unicast) para seu líder com a flag R_flag (repair)
setada
• É um pedido para começar a reconstrução

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• O líder responde com um RREP em unicast, dando-o permissão para começar a
reconstrução da árvore
• Isto evita que mais de um nó tente reparar a árvore

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Nodo recebe o RREP do seu líder e envia um RREQ para o outro líder (informação
do outro líder que veio no Group Hello)
• Este RREQ contém o número de sequência da sua árvore particionada

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Quando recebe o RREQ e vê a flag R_flag setada, pega os dois números de
sequência: o seu e o que veio na mensagem
• Escolhe o maior e incrementa este valor em um
• Ele, agora, é o novo líder
• Envia um RREP em unicast para o nodo que começou a reparação

MAODV (Multicast Ad Hoc On Demand Distance Vector)
C
A
B
D
G
E
F
• Líder envia o Group Hello com a flag U_flag (update) setada
• Nós recebem o Group Hello e atualizam suas informações nas suas tabelas
• A árvore é reconstruída

Número mínimo de cópias são usados para disseminar
pacotes para um grupo multicast acarretando uma
maior eficiência na banda

Estrutura de fácil roteamento
 A mensagem é enviada somente para os nós ligados
 Estes nós se encarregam de enviar a mensagem até os
destinatários, enviando apenas para os ligados a ele

Falhas de links podem ocasionar uma reconfiguração
de toda árvore

Monitoramento dos estados de todos os links (galhos) é
necessário

Existe apenas um caminho entre quaisquer dois nós
 Não existe caminho alternativo

Cria uma topologia estruturada como uma Malha

Múltiplas rotas entre os nós

Utiliza o conceito de grupos
 Somente um sub-conjunto dos nós realizam encaminhamentos

Cada computador pode ser ligado a uma, ou várias
estações

O protocolo opera com uma fase de Request e outra de
Reply

ODMRP(On-Demand Multicast Routing Protocol)
• Um nó quer enviar uma mensagem, mas não está no grupo ou não conhece uma
rota

ODMRP(On-Demand Multicast Routing Protocol)
• Envia em broadcast uma mensagem do tipo Join Query
• Somente nós membros do grupo respodem esta mensagem

ODMRP(On-Demand Multicast Routing Protocol)
• A cada mensagem recebida, os nós armazenam as informações do source
(originador) e do next hop (nó do qual veio a mensagem)

ODMRP(On-Demand Multicast Routing Protocol)

ODMRP(On-Demand Multicast Routing Protocol)

ODMRP(On-Demand Multicast Routing Protocol)

ODMRP(On-Demand Multicast Routing Protocol)
• Quando um membro recebe um Join Query, ele responde em broadcast com um
Join Reply, enviando as informações de sua tabela (informando o originador e o next
hop, que é por onde recebeu a mensagem)

ODMRP(On-Demand Multicast Routing Protocol)
• Quando um nó recebe um Join Reply, ele verifica se ele encontra-se no caminho
entre o nó que mandou o Join Reply e o originador do Join Query
• Se ele está no caminho, ele sabe que ele faz parte do Grupo de Encaminhamento
(ou FG – Fowarding Group). Seta, então, uma flag chamada FG_FLAG

ODMRP(On-Demand Multicast Routing Protocol)
• Os nós, então, após receberem um Join Reply, enviam em broadcast um Join Reply
com as informações da sua tabela

ODMRP(On-Demand Multicast Routing Protocol)
• As mensagens de Join Reply continuam pela rede, criando FGs por todo o caminho
entre a origem e os membros do grupo

ODMRP(On-Demand Multicast Routing Protocol)

ODMRP(On-Demand Multicast Routing Protocol)
• Ao chegar ao originador, a malha está pronta
• Cada FG (baseado nas diversas informações que recebeu nos Join Reply) sabe o
menor caminho entre todos pares de nodo da topologia

ODMRP(On-Demand Multicast Routing Protocol)
• Enquanto um membro do grupo ainda quer enviar pacotes para o grupo, ele envia
periodicamente pacotes do tipo Join Request, que é uma espécie de “alive”

ODMRP(On-Demand Multicast Routing Protocol)
• Quando um novo membro deseja enviar mensagens no grupo, o processo é
exatamente o mesmo
• Um Join Query em broadcast é enviado, os membros respondem com Join Reply,
que populam a rede com informações sobre as menores rotas

ODMRP(On-Demand Multicast Routing Protocol)
Membro do grupo e FG
• Um membro do grupo também pode ser um FG
• Quando um membro deseja deixar o grupo, basta ele não enviar os Join Reply para
aquele grupo

Disponibiliza várias rotas
 com isso se torna mais resistente a falhas de conexão e
consequentemente à mobilidade
 maior confiabilidade

Rotas são otimizadas, percorrendo o menor caminho
entre os nodos

Facilidade de entrada e saída do grupo multicast

Cria redundâncias para superar a dinamicidade da rede

Usa mais cópias para disseminar os pacotes

Não escalável para redes muito grandes

Intervalo de inundação de mensagens de controle (Join
Query) é crítico
 Intervalo muito pequeno: muitas mensagens na rede (talvez
desnecessárias)
 Intervalo muito grande: aumenta a probabilidade de achar que
membros deixaram o grupo
 Predição de mobilidade pode ajudar a estipular a frequência das
mudanças de rotas

Árvore
 AMRoute (Ad Hoc Multicast Routing Protocol)
 AMIRS (Ad Hoc Multicast Routing Protocol Utilizing
Increasing ID-Numbers)

Malha
 NSMP (Neighboar Supporting Ad Hoc Multicast Routing
Protocol)
 CAMP (Core-Assisted Mesh Protocol)

Árvores x Malhas
 As árvores são compartilhadas entre todos os nós do grupo
Multicast
 Ocasionando congestionamentos na rede

Árvores x Malhas
 Na Malha, os diferentes nós não compartilham o mesmo
caminho
 Os FGs sabem o menor caminho entre dois nós

Árvores x Malhas
Características
Organização da rede
Definição de rotas
Uso dos recursos da rede
Como lida com
mobilidade
Overhead
Árvores
Malhas
Árvore
Malha
Somente um caminho
Vários caminhos
Eficiente
Desperdício
Caminho único
Caminhos alternativos
Baixo
Alto