Protocolo AODV para Redes Ad Hoc

Prévia do material em texto

Ad Hoc On-Demand Distance Vector (AODV)
Carina T. de Oliveira1
1Grupo de Teleinformática e Automação (GTA)
Universidade Federal do Rio de Janeiro (UFRJ)
Rio de Janeiro – RJ – Brasil
carina@gta.ufrj.br
Abstract. A mobile ad hoc network needs dynamic routing protocols capable
to operate in agreement with the specific characteristics of the network. This
paper presents a study on one of the existing ad hoc routing protocols: Ad Hoc
On-Demand Distance Vector (AODV).
Resumo. Uma rede móvel ad hoc necessita de protocolos de roteamento
dinâmicos capazes de operar de acordo com as caracterı́sticas especificas da
rede. O presente trabalho apresenta um estudo sobre um dos protocolos de
roteamento ad hoc existentes: o Ad Hoc On-Demand Distance Vector (AODV).
1. Introdução
Atualmente, presenciamos um acelerado crescimento nas área de redes locais sem-fio
(WLANs - Wireless Local Area Networks). Essas redes permitem a mobilidade dos
equipamentos, flexibilidade, diminuição de custos de infra-estrutura, instalações em áreas
de difı́cil cabeamento, maior confiabilidade e robustez, dentre outros. Todas estas carac-
terı́sticas permitem que a tecnologia móvel sem-fio ofereça aos usuários a possibilidade
de acesso aos mesmos serviços a qualquer instante e de diferentes lugares.
As redes sem fio podem ser divididas em duas categorias: redes com e sem infra-
estrutura. Em uma rede com infra-estrutura toda a comunicação entre os nós móveis
ocorre através de um ponto de acesso (AP). Mesmo próximos uns dos outros, os nós
móveis não conseguem realizar qualquer tipo de comunicação direta. O AP representa
a parte fixa da rede e serve como ponte para outras redes. As redes celulares são um
exemplo de rede infra-estruturada.
Uma rede sem infra-estrutura, mais conhecida como rede ad hoc ou Mobile Ad
hoc NETworks (MANET), corresponde a uma coleção de nós móveis sem-fio com a
capacidade de auto-organização em uma topologia arbitrária e temporária na qual não
existe um ponto de acesso que coordene a comunicação. Um nó em uma rede ad hoc
pode se comunicar diretamente com outros nós que estiverem no seu alcance, ou seja,
com nós que sejam seus vizinhos. Caso a distância entre a origem e o destino seja maior
que o raio de cobertura, os nós móveis agem como roteadores encaminhando pacotes de
dados para outros nós. Desta forma, uma rota entre esses dois nós é estabelecida para
que a comunicação fim-a-fim se torne possı́vel. Essas caracterı́sticas tornam as aplicações
em redes ad hoc recomendáveis para operações militares, trabalhos de emergência em
locais atingidos por grandes catástrofes, eventos que necessitam de instalações rápidas,
comunicações inter-grupos, dentre outras.
A topologia de uma rede ad hoc muda freqüentemente. Como os nós móveis
movimentam-se arbitrariamente, com diferentes velocidades e, geralmente, não con-
seguem se comunicar diretamente, é preciso que as tabelas de roteamento sejam atu-
alizadas de forma rápida o suficiente para retratar a topologia da rede o mais próximo
possı́vel do atual. As limitações de banda passante e energia para que rotas entre nós
sejam descobertas e mantidas devem ser cuidadosamente controladas. Devido as suas pe-
culiaridades, o roteamento em redes ad hoc não é realizado de maneira eficiente quando
utilizados algoritmos de roteamento tradicionais de redes fisicamente conectadas.
O presente trabalho apresenta um estudo sobre um dos protocolos de roteamento
para redes ad hoc mais citados na literatura: o Ad Hoc On-Demand Distance Vector
(AODV). O restante do trabalho está dividido da seguinte maneira. A Seção 2 discute
a questões relativas ao roteamento em redes ad hoc. A Seção 3 apresenta as principais
caracterı́sticas do AODV. Na Seção 4, 5 e 6 são discutidos os mecanismos relacionados à
descoberta e manutenção de rotas e ao estabelecimento do caminho reverso. Por fim, são
apresentadas a conclusão e a bibliografia.
2. Roteamento em Redes Ad Hoc
A função de um protocolo de roteamento é encontrar, estabelecer e manter rotas entre dois
nós que desejam se comunicar. No contexto de redes ad hoc, os protocolos de roteamento
podem ser classificados como pró-ativos ou reativos.
Nos protocolos pró-ativos todo nó da rede possui na sua tabela de roteamento
as informações para todos os possı́veis destinos. A grande vantagem desses protocolos
é o fato dos pacotes poderem ser enviados com um atraso mı́nimo já que os nós con-
hecem previamente as rotas. Porém, é preciso que as redes possuam banda suficiente para
evitar congestionamento e não possuam recursos escassos de energia, já que a troca de
mensagens de roteamento é elevada para garantir o conhecimento de rotas válidas. O Op-
timized Link State Routing (OLSR) e o Destination-Sequenced Distance-Vector (DSDV)
são exemplos de protocolos pró-ativos.
Nos protocolos reativos uma rota só é determinada quando um nó deseja enviar
um pacote para outro nó, ou seja, o protocolo atua sob demanda. Desta forma, os recursos
como banda passante e energia podem ser utilizados de uma forma mais eficiente, pois
só são gastos quando há necessidade de descoberta de rotas. A desvantagem desses pro-
tocolos é o maior atraso no envio dos pacotes, pois se a rota do destino do pacote não
for conhecida, o procedimento de descoberta de rota deve ser realizado. Como exemplos
desses protocolos existem o Dynamic Source Routing (DSR) e o Ad hoc On-Demand
Distance Vector (AODV).
3. AODV
O algoritmo de roteamento AODV foi projetado para uso em redes móveis ad hoc. Realiza
tanto roteamento unicast, quanto roteamento multicast [1]. É um protocolo reativo que
pode ser considerado basicamente uma combinação do DSR e do DSDV [2]. O AODV
adota os mecanismos de descoberta e manutenção de rotas usados no DSR, mas ao invés
de utilizar roteamento na origem confia no estabelecimento dinâmico das entradas nas
tabelas de roteamento dos nós intermediários [3]. Assim, é possı́vel evitar a sobrecarga
da rede, principalmente em redes com muitos nós, pois não é necessário que cada pacote
contenha todo o caminho da fonte até o destino. Do DSDV o AODV adota o conceito
de número de seqüência do destinatário para manter a informação de roteamento mais
recente entre nós [3]. Porém, diferente do DSDV, cada nó ad hoc mantém um contador de
número de seqüência monotonicamente crescente que é usado para substituir rotas pas-
sadas. O uso dessas técnicas assegura um roteamento livre de loops e resolve o problema
de contagem ao infinito tı́picos dos protocolos de vetor de distância.
Como o algoritmo funciona sob demanda, só existe a necessidade de um nó A
conhecer uma rota para um nó B quando a comunicação entre eles for necessária. Desta
forma, evita-se o desperdı́cio de banda e minimiza-se o uso de memória e processamento
nos nós que atuam como roteadores. As rotas para destinos com os quais os nós não
estejam em comunicação ativa não são mantidas.
4. Descoberta de Rotas
No AODV, um processo de descoberta de rotas é realizado através da inundação de pa-
cotes Route Requests (RREQ). Cada nó possui dois contadores: um número de seqüência
e um identificador de broadcast. Sempre que um nó fonte deseja se comunicar com outro
nó para o qual ele ainda não possui uma entrada em sua tabela de roteamento, ele incre-
menta o seu número de seqüência e inunda a rede com um RREQ.
O RREQ possui os seguintes campos: Endereço da Fonte, Número de Seqüência
da Fonte, Identificador de Broadcast, Endereço do Destino, Número de Seqüência do
Destino e Contador de Saltos (valor inicial igual à zero). Juntos, os campos Endereço
da Fonte e Identificador de Broadcast identificam de forma exclusiva um RREQ. O Iden-
tificador de Broadcast é um contador local mantido separadamente por cada nó e incre-
mentado sempre que um novo pacote RREQ é transmitido [5]. O Número de Seqüência
da Fonte é usado para manter as informaçõesmais recentes do caminho reverso para a
origem e o Número de Seqüência do Destino especifica o quão recente uma rota para um
destino deve estar antes de ser aceita pela origem.
Quando um nó receber um pacote RREQ, o par (Endereço de Origem, Identi-
ficador de Broadcast) é verificado para saber se o nó já havia recebido anteriormente
alguma requisição com o mesmo Identificador de Broadcast e o mesmo endereço de
origem. Sendo uma duplicata, o RREQ redundante é descartado. Caso contrário, cada
nó que receber uma requisição pela primeira vez realiza determinadas ações dependendo
das condições citadas abaixo:
• Se não for o destino e não possuir uma rota válida para alcançar o destino
desejável, o nó incrementa em uma unidade o Contador de Saltos e inunda seus
vizinhos com o RREQ.
• Se for o próprio destino ou se tiver armazenado em sua tabela de roteamento uma
entrada ativa para o destino com o Número de Seqüência do Destino maior ou
igual ao Número de Seqüência do Destino contido no pacote RREQ, então o nó
envia ao vizinho que lhe enviou o RREQ (caminho reverso) um pacote Route
Reply (RREP) em unicast formado pelos seguintes campos: Endereço da Fonte,
Endereço do Destino, Número de Seqüência do Destino, Contador de Saltos e
Tempo de Vida da Rota.
Essa comparação entre os campos Número de Seqüência do Destino é necessária,
pois permite que o nó fonte identifique o quão recente é a informação sobre a rota ar-
mazenada na tabela de um nó intermediário. Desta forma, pode-se assegurar que as rotas
mais atualizadas serão sempre as escolhidas.
Um nó de origem pode iniciar a transmissão de dados assim que receber o primeiro
RREP. Ao aprender uma rota melhor, o protocolo atualiza as informações de roteamento
de forma transparente para a aplicação.
5. Caminho Reverso
Enquanto o pacote RREQ vai sendo inundado pela rede ad hoc, o caminho reverso é
estabelecido de todos os nós de volta para a fonte. Assim, no caso de um destino ser
alcançável, a rede tem as informações necessárias para retornar a resposta até a fonte.
Para a formação do caminho reverso cada nó que inunda a rede com um RREQ
deve armazenar automaticamente o endereço do vizinho de quem recebeu a primeira
cópia do RREQ, o número de seqüência da fonte e um tempo de expiração. Todas es-
sas informações devem ser armazenadas em uma entrada relativa ao endereço da fonte. O
caminho reverso é mantido durante o tempo suficiente para que o RREQ atravesse a rede
e produza uma resposta para o nó fonte [3].
Todos os nós no caminho reverso aprendem a rota para o destino como um sub-
produto da descoberta de rota da origem [5]. Os nós que não participaram do caminho
reverso apagarão a entrada da tabela de rotas inversas quando o tempo associado expirar.
6. Manutenção de Rotas
No AODV, se um nó fonte se movimenta durante uma sessão ativa, ele pode decidir entre
reiniciar ou não um processo de descobrimento de rota para estabelecer um novo caminho
até um destino [3]. Se o nó fonte ainda tiver pacotes para transmitir é realizado um novo
processo de descobrimento de rota. Porém, se uma rota não é muito utilizada não há
necessidade de uma inundação.
Quando a movimentação na rede ad hoc é realizada por nós destinatários ou por
nós intermediários pode ocorrer a quebra de um determinado enlace que estava sendo
utilizado para realizar o roteamento de pacotes. A quebra do enlace também pode ocorrer
quando um nó é desativado.
Existem duas maneiras de um nó atestar a informação de conectividade com seus
vizinhos. A primeira forma é escutando pacotes broadcast que são endereçados à outros
vizinhos. A segunda forma é enviando periodicamente por difusão mensagens de hello
com sua identidade, seu número de seqüência e um campo TTL (time-to-live com valor 1
para indicar que apenas os vizinhos recebem e atualizam sua informação de conectividade
local) [1]. Todo nó que receber uma mensagem de hello cria ou atualiza uma entrada na
sua tabela de roteamento relativa ao vizinho que lhe enviou a mensagem. Se um hello não
for recebido, considera-se que houve quebra de um enlace e que, portanto, houve alguma
mudança na topologia da rede.
O nó que detectou a falha tem a função de informar a todos os nós que dependiam
da conexão sobre a quebra do enlace. Isso é possı́vel, pois os nós predecessores são
mantidos em cada entrada da tabela de roteamento, permitindo que o nó fonte identifique
os nós vizinhos que usam a entrada falha para rotear pacotes de dados [6]. Uma vez
verificado na tabela de roteamento os destinos que utilizam o enlace, o nó notifica a quebra
do enlace enviando um pacote de erro (Route Error - RERR) aos nós afetados. O nó
que recebe a notificação, por sua vez, encaminha o pacote RERR para todos os seus
predecessores.
Tal procedimento age de forma efetiva fazendo com que todas as rotas que de-
pendiam do enlace inativo sejam retiradas de todas as tabelas de roteamento da rede. O
término desse processo é garantido por que o AODV mantém somente rotas livres de loop
e também devido ao número de nós nas rede ad hoc ser finito. Em contraste com o DSR,
os pacotes RERR no AODV possuem a vantagem de informar a todos os nós que usam
um enlace quando uma falha ocorre [6].
7. Conclusão
Em redes ad hoc de múltiplos saltos cada nó age como um roteador encaminhando men-
sagens para outros nós. Um dos maiores desafios nesse tipo de rede é o desenvolvimento
de protocolos de roteamento dinâmicos que consigam de maneira eficiente encontrar ro-
tas entre dois nós comunicantes considerando o alto grau de mobilidade dos nós que
freqüentemente modifica a topologia da rede de forma drástica e imprevisı́vel.
O AODV foi apresentado como um protocolo de roteamento dinâmico para redes
móveis ad hoc. Este protocolo caracteriza-se principalmente pela realização de descoberta
de rotas sob demanda, utilização de tabelas de roteamento, único encaminhamento de
um pacote RREQ, armazenamento de uma rota por destino, utilização de números de
seqüência, adoção de mecanismos que evitam loops e determinam as rotas mais atual-
izadas.
Diversos trabalhos vêm sendo propostos com melhorias para resolver os proble-
mas do AODV, principalmente os referentes ao consumo de energia, a segurança e ao
desempenho. Desta forma, o AODV ainda pode ser considerado um grande desafio na
área de roteamento em redes móveis sem-fio.
8. Referências
[1] Perkins, C. E.; Belding-Royer, E. M.; Das, S. R.; Ad Hoc On-Demand Distance
Vector Routing, Request for Comments: 3561, rfc3561.txt, julho de 2003.
[2] Cordeiro, C. M.; Agrawal, D. P.; Mobile Ad hoc Networking, Tutorial/Short Course
in 20 th Brazilian Symposium on Computer Networks, May 2002, pp. 125-186.
[3] Perkins, C. E.; Belding-Royer, E. M.; Ad hoc On-Demand Distance Vector Routing.
Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications,
New Orleans, LA, February 1999, pp. 90-100.
[4] AODV site, http://moment.cs.ucsb.edu/AODV/aodv.html. Acessado em 30 de julho
de 2006.
[5] Tanenbaum, A. S.; Redes de Computadores. 4a Ed. Rio de Janeiro: Campus, 2003.
[6] Perkins, C. E.; Belding-Royer, E. M.; Das, S. R.; Marina, M. K.; Performance Com-
parison of Two On-Demand Routing Protocols for Ad Hoc Networks, IEEE Personal
Communications, fevereiro de 2001.