Redes Ad Hoc
Elda Regina de Sena
Rafael Fernandes Lopes
Sumário










Introdução às Redes Ad Hoc
Desenvolvimento
Características
Aplicações
Tipos
Vantagens X Desvantagens
O Padrão IEEE 802.11
Roteamento e Segurança
Caching em redes Ad Hoc
Considerações finais
2
Introdução às Redes Ad Hoc

Ad Hoc

definição: formado ou utilizado para determinado
fim ou necessidade específica ou imediata.


Merriam-Webster’s Collegiate Dictionary
Redes Ad Hoc

definição: plataformas ou nós móveis que podem
se mover arbitrariamente dentro de uma infraestrutura temporária e estabelecer uma rede
efêmera sem a presença de uma entidade central.
3
Introdução às Redes Ad Hoc

Redes Wireless

Estruturadas




depende de infra-estrutura instalada.
recursos são alocados por uma entidade central.
serviços estão integrados no sistema.
Ad Hoc



não depende de infra-estrutura prévia.
recursos são alocados pelos participantes.
serviços dependem unicamente dos participantes.
4
Introdução às Redes Ad Hoc

Redes Estruturadas

Sistema Celular
Modelo de comunicação em redes móveis infra-estruturadas
5
Introdução às Redes Ad Hoc

Redes Ad Hoc

dispositivos móveis interconectados formam a rede
Modelo de comunicação em redes móveis ad hoc
6
Redes de Comunicação direta

Neste tipo de rede os nós da rede se
comunicam única e exclusivamente com os
nós que estão dentro do seu raio de
cobertura
7
Redes de Múltiplos Saltos (Multihop)

Neste tipo de rede os nós se comportam
como roteadores, permitindo a comunicação
entre nós da rede cuja distância ultrapassa
o raio de cobertura, tornando-a bem mais
complexa
8
Vantagens

Grande flexibilidade: Podem ser formadas
rapidamente mesmo em lugares ermos

Baixo custo de instalação

Robustez: podem resistir a catástrofes da
natureza e a situações de destruição por
motivo de guerra
9
Desvantagens


As estações são mais complexas: rotear
pacotes e prover mecanismos de acesso ao
meio
Adiciona-se todos os problemas de redes sem
fio:
 Baixa taxa de transmissão
 Alta probabilidade de Erro
 Grande variação das condições do meio de
transmissão
10
Desenvolvimento

DARPA


PRNet (Packet Radio Network) – 1972/1981
SURAN (Survivable Radio Network) –
1983/1992



LPR (Low Cost Packet Radio)
GloMo (Global Mobile) – 1994/2000
Militares


TI (Tactical Internet)
ELB (Extending the Litoral Battlespace)
11
Desenvolvimento

IETF MANET WG

objetivo: padronizar um protocolo de roteamento
com diversos modos de operação, sendo cada um
deles especializados em diferentes contextos
ambientais.


http://www.ietf.org/html.charters/manet-charter.html
http://tonnant.itd.nrl.navy.mil/manet/manet_home.html
12
Características Ad Hoc

Dispositivos completamente funcionais



Segurança
Capacidade de roteamento
Topologia dinâmica


Dispositivos móveis
Impacto nos protocolos de roteamento
13
Características Ad Hoc

Enlaces instáveis


Altas taxas de erro
Protocolos adequados para ambientes
wireless


TCP em ambientes wireless
Energia escassa


Dispositivos de baixo consumo
Limita processamento e capacidade de
transmissão
14
Aplicações Ad Hoc

Redes Instantâneas

Sensores e Atuadores

Aplicações Militares

Computação Pervasiva
15
Redes Instantâneas

Ausência de infra-estrutura

destruição de infra-estrutura instalada –
calamidades


terremotos, enchentes
criação de infra-estrutura provisória

sala de imprensa
16
Redes Instantâneas

Impossibilidade de Instalação



prédios históricos
construções tombadas
infra-estrutura inadequada
17
Sensores e Atuadores

Sensores coordenados – Sensor Dust


Controles ambientais
Sensores embarcados


automotivos
aéreos – “fly-by-wireless” !
18
Aplicações Militares

Aplicações Militares



distribuição da rede
eliminação de ponto único de falhas
sem necessidade de infra-estrutura
19
Computação Pervasiva

Computação Pervasiva




Ubiquitous Computing – meio ambiente
computacional
computação distribuída e invisível todo o tempo
sincronização de informação entre dispositivos
informação disponível todo o tempo em
qualquer lugar
20
Computação Pervasiva

boas idéias:



casas inteligentes
redes automotivas
boas tentativas:

Electrolux Screen Fridge 1999


www.electrolux.se/screenfridge/
NCR “Microwave Bank” 1998

www.knowledgelab.com
21
A tecnologia 802.11


Com o uso deste padrão evita-se colisões,
interferências na transmissão, etc.
Dois hosts que não se comunicam diretamente
podem transmitir mensagens simultaneamente
para um vizinho comum sobre a mesma
freqüência
22
A tecnologia 802.11

IEEE 802.11


altamente difundido, grande infra-estrutura
instalada
altas taxas de transmissão para novas versões


IEEE 802.11a – até 54Mbps
mas não permite multihop


indispensável para redes Ad Hoc
dispensável para redes pervasivas
23
Roteamento e segurança



As aplicações wireless normalmente confiam em
algum ponto de suporte à mobilidade, como as
estações base
Muitas vezes é necessário estabelecer comunicação
quando a infra-estrutura está inacessível,
sobrecarregada, danificada ou destruída
Para remover esta dependência, todos os nós móveis
disponíveis são tratados como “comutadores
intermediários”
24
Roteamento e segurança



Estender a quantidade de nós móveis é melhor que
estender a quantidade de transceivers base
Fácil instalação e atualização, baixo custo e
manutenção, mais flexibilidade e a habilidade de
empregar novos e eficientes protocolos de
roteamento para comunicação wireless
Porém, como os nós da rede empregam relações de
confiança, a comunicação pede algumas
características extras no que diz respeito à segurança
25
Roteamento e segurança

Roteamento



Roteamento eficiente = desafio
Os algoritmos convencionais de roteamento não funcionam,
pois broadcasts são necessários para a sincronização entre
os nós e banda destas redes é geralmente escassa
Problemas:





Atualizações periódicas da topologia de rede aumenta o
overhead da banda
Transmissão de informação tem alto custo energia
A quantidade de informação de sincronização é proporcional ao
número de nós da rede, prejudicando portanto a escalabilidade
Rotas redundantes acumulam-se sem necessidade
Sistemas de comunicação muitas vezes não podem responder
às mudanças dinâmicas na topologia de rede
26
Roteamento e segurança

Tipos de algoritmos de roteamento:

Algoritmos de roteamento On-Demand


São conhecidos como protocolos reativos, pois as
rotas somente são estabelecidas quando isto é solicitado
Algoritmos de roteamento de estado de enlace

São conhecidos como protocolos pró-ativos porque
informações sobre as rotas são negociadas mesmo que
as rotas nunca tenham sido utilizadas
27
Roteamento e segurança

Algoritmos de roteamento:

Algoritmos de roteamento On-Demand



Roteamento pela origem dinâmico (DSR)
Roteamento vetor-distância sob demanda Ad Hoc
(AODVR)
Algoritmos de roteamento de estado de enlace


Roteamento de estado de enlace otimizado (OLSR)
Topologia de broadcast baseada em repasse de caminho
inverso (TBRPF)
28
Roteamento e segurança

Algoritmos de roteamento On-Demand

Roteamento pela origem dinâmico (DSR)



Baseia-se no conceito de roteamento pela origem, em
que o nós emissor deve prover a seqüência de todos os
nós através dos quais um pacote viajará
Cada nó mantém seu próprio cache de rotas,
essencialmente uma tabela de roteamento com os
endereços dos nós intermediários
As rotas são determinadas dinamicamente e somente se
houver necessidade; não existem broadcasts periódicos
29
Roteamento e segurança




Caso um nó origem queira enviar um pacote, ele deve
primeiramente checar seu cache de rotas
Se existir uma entrada válida para o destino, o nó envia
o pacote usando aquela rota
Se nenhuma rota válida está disponível, o nó origem
inicia o processo de descobrimento de rotas, enviando
um pacote especial de requisição de rotas (RREQ) para
todos os nós vizinhos
O RREQ propaga-se através da rede, coletando os
endereços de todos os nós visitados, até que ele alcance
o nó destino ou um nós intermediários que tenha uma
rota válida para o nó destino
30
Roteamento e segurança




O nó destino pode responder para o nó origem utilizando
roteamento inverso ou iniciando um processo de descoberta de
rotas do nó origem
Caso na procura de uma rota, um nó encontre um link que não
mais existe (ou que esteja down), ele envia um pacote de erro
de rota (RERR)
Este algoritmo é fácil de implementar, pode trabalhar com links
assimétricos e não envolve overhead quando não há mudanças
na rede
Existem porém o problema da grande largura de banda
utilizada, overhead inerente ao roteamento pela origem
31
Roteamento e segurança
Roteamento pela origem dinâmico. Um nó origem (1) envia um pacote especial de
requisição de rota para todos os nós vizinhos, e ele propaga a através da rede. Após o
recebimento da RREQ o nó destino (6) envia um pacote especial de resposta de rota para o
nó origem anunciando a nova rota descoberta
32
Roteamento e segurança

Roteamento vetor-distância sob demanda Ad
Hoc (AODVR)



Quando uma rota é requisitada, ele utiliza um processo de
descoberta de rota similar ao do DSR
A diferença entre o AODVR e o DSR está fundamentalmente no
fato de que, enquanto o DSR armazena as informações de toda
a rota, o AODVR só mantém uma entrada por destino
Esta entrada armazena somente a informação do próximo salto
para um determinado destino
33
Roteamento e segurança





A descoberta é feita enviando um broadcast de RREQ
Cada nó que recebe pela primeira vez um pacote RREQ coloca
em sua tabela uma entrada com a rota reversa, para o
originador da mensagem, e reenvia esse pacote de RREQ
Ao chegar no destino (ou em algum nó com uma rota válida
para o destino) um pacote RREP será enviado em unicast para
o nó origem, utilizando esta rota
Na volta do pacote RREP, as rotas inversas também serão
formadas pelos roteadores intermediários
As rotas são mantidas atualizadas utilizando-se um número de
seqüência e um broadcast_id (que são incrementados quando
a conectividade de um nó muda e quando um nó realiza um
novo pedido de descobrimento de rotas, respectivamente) 34
Roteamento e segurança

O AODVR oferece muitas vantagens se comparado ao
DSR:




Ele suporta multicast por construir árvores conectando
todos os membros multicast com os nós requeridos
Menores pacotes de controle e mensagens resultam em
menos overhead de banda de rede
A necessidade de ter somente dois endereços quando
estiver roteando – destino e o próximo salto – melhor que
ter a seqüência inteira garante boa escalabilidade por
causa do tamanho do pacote que não depende do
diâmetro da rede
Como desvantagens, o AODVR trabalha somente com
links simétricos e por causa disto ele não habilita o
roteamento com vários caminhos (multipath), novas
rotas devem ser descobertas quando um link é quebrado
35
Roteamento e segurança

Algoritmos de roteamento:
Algoritmos de roteamento On-Demand
Roteamento pela origem dinâmico (DSR)
Roteamento vetor-distância sob demanda Ad Hoc
(AODVR)

Algoritmos de roteamento de estado de enlace


Roteamento de estado de enlace otimizado (OLSR)
Topologia de broadcast baseada em repasse de caminho
inverso (TBRPF)
36
Roteamento e segurança

Algoritmos de roteamento de estado de enlace

Roteamento de estado de enlace otimizado (OLSR)



Uma otimização do protocolo de estado de enlace
Introduz números seriais para tratar rotas antigas
Tem como objetivo:





Reduzir a inundação de mensagens de controle de topologia
Reduzir o tamanho das mensagens de controle de topologia
Utiliza Multipoint Relays (MPRs), que repassam todo o
tráfego de um nó
Cada nó anuncia aos nós que ele selecionou como MPR
A partir destas informações outros nós podem construir uma
tabela “último salto” e calcular a tabela de roteamento disso
37
Roteamento e segurança
Retransmitting node
or multipoint relay
v
Um subconjunto de vizinhos de “um salto” são escolhidos como MPRs. O conjunto de
MPRs deve cobrir todos os vizinhos de “dois saltos”
38
Roteamento e segurança

Topologia de broadcast baseada em repasse de
caminho inverso (TBRPF)






Utiliza caminhos mais curtos para cada destino
Cada nó computa uma source tree (provendo caminhos para todos
os nós alcançáveis) baseado nas informações parciais da topologia,
armazenado em uma tabela de topologias, usando uma
modificação do algoritmo de Dijkstra
Para minimizar o overhead, cada nó reporta somente partes de sua
source tree para os seus vizinhos
Utiliza uma combinação de atualizações periódicas e diferenciais
para informar a vizinhança sobre as suas source trees
Utiliza mensagens HELLO para descobrir as mudanças no estado
das vizinhanças
Mensagens muito menores que as mensagens utilizadas em outros
protocolos de estado de enlace, por exemplo, como o OSPF
39
Roteamento e segurança

Segurança



Algoritmos de roteamento normalmente
consideram todos os nós da rede como nós
confiáveis
Ataques contra a segurança da rede ah hoc
poderiam afetar esses protocolos
Os ataques são classificados como:


Ativos
Passivos
40
Roteamento e segurança

Tipos de Ataques Ativos:




Ataques
Ataques
Ataques
Ataques
de modificação
de fabricação
de personificação (impersonating)
cooperativos
41
Roteamento e segurança

Como evitar estes ataques ?





Chaves simétricas
Assinatura Digital – Chaves assimétricas
Hash Chains
TESLA
Protocolos mais utilizados


SAODV
Ariadne
42
Caching em redes Ad Hoc



Suponhamos uma rede wireless, sendo utilizada em
um campo de batalha, que consiste de comandantes
e um grupo de soldados
Os soldados podem acessar centros de informação
para obter informações geográficas detalhadas,
informações sobre o inimigo, obter novos comandos,
etc
Soldados vizinhos tendem a ter missões similares e
portanto interesses comuns. Muitos soldados
precisam acessar o mesmo dado em instantes
diferentes de tempo
43
Caching em redes Ad Hoc



Se este dado estiver próximo a um soldado, pode-se
evitar acessos posteriores ao centro de informação,
economizando energia da bateria, largura de banda e
tempo
Em redes ad hoc, nós móveis comunicam-se com
cada um dos outros utilizando links wireless multihop
Na falta de um suporte de infra-estrutura cada nó
funciona como um roteador, repassando os pacotes
de dados para outros nós
44
Caching em redes Ad Hoc



Se usuários de estações móveis, que tem uma área de
cobertura limitada, formam uma rede ad hoc, um usuário
que desloca-se através da rede deve permanecer tendo
acesso aos dados
Se um dos nós através do caminho até a origem dos
dados tiver uma cópia em cache do dado requisitado, ele
pode repassar esse dado ao usuário que o requisitou,
economizando banda e energia, e reduzindo o tempo de
espera
Este processo é conhecido como cache cooperativo e está
preocupado em que, múltiplos nós compartilhem e
coordenem dados cacheados
45
Caching em redes Ad Hoc



Para aumentar a acessibilidade aos dados, nós
móveis devem fazer o cache de itens de dados
diferentes de seus vizinhos.
A replicação desses dados do servidor podem criar
problemas de segurança
Algumas técnicas de cache em redes ad hoc:



CachePath
CacheData
HybridCache
46
Caching em redes Ad Hoc
Cache cooperativo em redes ad hoc. Mecanismos de suporte do middleware provê
cache cooperativo seguro, gerenciamento de cache e busca de informação
47
Caching em redes Ad Hoc
 CachePath e CacheData
Rede ad hoc. Nó N11 é a origem do dado e os nós pretos são nós roteadores. O nó
N1 é a cabeça do cluster
48
Caching em redes Ad Hoc

Consistência de Cache:

Baseada no mecanismo de TTL (Time to Live)

Caso o TTL expire aquele cache é removido

Melhoria deste algoritmo:

sempre que uma nova cópia do dado passar pelo nó que
contém o cache, deve-se atualizar sua informação de
cache
49
Caching em redes Ad Hoc

HybridCache



Combina as técnicas de CachePath e CacheData
Quando um determinado dado passa por um nó
móvel, ele faz o cache do caminho ou do dado
baseado em alguns critérios
Estes critérios incluem o tamanho e o TTL do item
de dados
50
Considerações finais

Redes Móveis




Maior desafio: Roteamento


área nova de pesquisa
vasto campo de pesquisa
vários desafios a serem vencidos
Protocolos de roteamento: DSR e AODV
Algoritmos de Roteamento


características boas e ruins dependendo das
condições da rede.
futuro próximo:ter-se algorítmos eficientes e
adaptáveis às mais variadas características
ambientais.
51
Dúvidas
52
Referências bibliográficas



WU, Jie, STOJMENOVIC, Ivan. Ad Hoc Networks. IEEE Personal
Communications, 02/2004, p. 29.
CAO, Guohong, YIN, Liangzhong, DAS, Chita R. Cooperative CacheBased Data Access in Ad Hoc Networks. IEEE Personal
Communications, 02/2004, p. 32.
MILANOVIC, Nikola, MALEK, Miroslaw, DAVIDSON, Anthony,
MILUTINOVIC, Veljko. Routing and Security in Mobile Ad Hoc
Networks. IEEE Personal Communications, 02/2004, p. 61.

JUNIOR, Aurelio Amodei, DUARTE, Otto Carlos M. B. Segurança no
Roteamento em Redes Móveis Ad Hoc. 2002

ALBUQUERQUE, Luciano Renovato de. Segurança em Redes Ad Hoc.
2003

KOLSTAD, Jon, LUNDIN, Andreas. Ad-Hoc Routing in Wireless Mobile
Networks. 2003
53
Redes Ad Hoc
[email protected]
[email protected]