Rio de Janeiro, Agosto de 2006. Carina Teixeira de Oliveira CPE 825 - Roteamento em Redes de Computadores Prof. Luís Henrique M. K. Costa Ad Hoc On-Demand

Rio de Janeiro, Agosto de 2006.

Carina Teixeira de Oliveira

CPE 825 - Roteamento em Redes de Computadores

Prof. Luís Henrique M. K. Costa

Ad Hoc On-Demand Distance Vector (AODV)

http://www.gta.ufrj.br

Sumário

Introdução

Características do AODV

Descoberta de Rotas

Caminho Reverso

Manutenção de Rotas

Conclusão

Bibliografia

http://www.gta.ufrj.br3

Introdução

Ad hoc On-Demand Distance Vector (AODV)

• Projetado para uso em redes móveis ad hoc

• Redes sem infra-estrutura

• Nós auto-organizáveis

• Topologia arbitrária e temporária

• Tabelas de roteamento precisam ser atualizadas de forma rápida o suficiente para retratar a topologia da rede o mais próximo possível do atual



Protocolo baseado em Vetor de Distância

Protocolo Reativo

• Atua 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

• Evita o desperdício de banda

• Minimiza o uso de memória e processamento nos nós que atuam como roteadores

• Rotas para destinos com os quais os nós não estejam em comunicação ativa não são mantidas



Combinação• Dynamic Source Routing (DSR)

• Mecanismos de descoberta e manutenção de rotas

• Diferença: confia no estabelecimento dinâmico das entradas nas tabelas de roteamento dos nós intermediários

• evita sobrecarga da rede• não é preciso que cada pacote contenha todo o caminho da fonte até o destino

• Destination-Sequence Distance-Vector (DSDV)

• Adota o conceito de número de seqüência

• Diferença: cada nó ad hoc mantém um contador de número de seqüência monotonicamente crescente usado pra substituir rotas passadas

• assegura roteamento livre de loops



Mensagens de Roteamento

• Route Request (RREQ)• Route Reply (RREP)• Route Error (RERR)

Cada nó possui dois contadores

• Número de seqüência

•Incrementado em duas situações:•Imediatamente antes de iniciar um processo de descobrimento de rota•Imediatamente antes de enviar um RREP em resposta a um RREQ

• Identificador de Broadcast

• Mantido separadamente por cada nó• Incrementado sempre que um novo RREQ é transmitido


Descoberta de Rotas

Inundação de Route Requests (RREQ)

Identificam de forma exclusiva um RREQ

Endereço da Fonte

Número de Seqüência da Fonte

Endereço do Destino

Número de Seqüênciado Destino

Identificador de Broadcast

Contador de Saltos


Descoberta de Rotas


Usado para manter as informações mais recentes no caminho reverso para a origem

Endereço da Fonte





Contador de Saltos


Descoberta de Rotas


Atualizado sempre que um nó recebe uma nova informação sobre um destino

Especifica o quão recente uma rota para um destino deve estar antes de ser aceita pela origem

Garante a ausência de loops

Endereço da Fonte





Contador de Saltos


Descoberta de Rotas


Valor inicial = 0

Endereço da Fonte





Contador de Saltos


Descoberta de Rotas

Nó intermediário recebeu um RREQ

Verifica o par <Endereço da Fonte, Identificador de Broadcast>

É um novo RREQ?

Sim Não

Incrementa <Contador de Saltos>

Inunda RREQ para seus vizinhos

É duplicata.Descarta RREQ

Nó intermediário não possui rota válida para

alcançar o destino


Descoberta de Rotas

Nó intermediário possui rota válida

para alcançar o destino

Nó recebeu um novo RREQ

Compara <N° de Seqüência do Destino> É maior ou igual?

Envia RREP

Sim

Incrementa <Contador de Saltos>

Inunda RREQ para seus vizinhos

Não


Descoberta de Rotas

Nó Destino recebeu um novo RREQ

Envia RREP


Descoberta de Rotas

RREP• unicast

Antes de enviar o RREP um nó destino deve atualizar seu número de seqüência para o MÁXIMO entre o seu valor atual e o seu valor que constava no RREQ

Endereço da Fonte



Contador de Saltos

Tempo de Vidada Rota


Caminho Reverso

Cada nó que inunda a rede com um RREQ deve armazenar automaticamente:

• Endereço do vizinho de quem recebeu a primeira cópia do RREQ

• Número de Seqüência da Fonte

• Tempo de Expiração • o caminho reverso é mantido o tempo suficiente para que o RREQ atravesse a rede e produza uma resposta para o nó fonte

Todas essas informações devem ser armazenadas em uma entrada relativa ao endereço da fonte

Todos os nós no caminho reverso aprendem a rota para o destino como um sub-produto da descoberta da rota de origem


Exemplo

B

A

S E

F

H

J

D

C

G

KN

M

• Nó S deseja enviar pacotes de dados ao nó D


RREQ

B

A

S E

F

H

J

D

C

G

K

Broadcast

M

N

Exemplo


Caminho reverso

Exemplo

B

A

S E

F

H

J

D

C

G

KN

M


Exemplo

• Nó C recebe RREQ de G e H• C não encaminha RREQ (duplicata)

B

A

S E

F

H

J

D

C

G

KN

M


Exemplo

• Nó D não encaminha RREQ

B

A

S E

F

H

J

D

C

G

KN

M


Exemplo

• Nó D recebe primeiro RREQ de J • Nó D envia um RREP para J (unicast)

B

A

S E

F

H

J

D

C

G

KN

M

Dest Next Saltos

D E 4


Exemplo

Caminho estabelecido

B

A

S E

F

H

J

D

C

G

IK

N

M

Dest Next Saltos

D E 4


Exemplo

Se outros RREPs forem recebidos por S, somente os RREPs com <Número de Seqüência do Destino> maior ou igual com menor número de saltos serão atualizados pelo nó fonte

• Assegura informações de roteamento mais rápidas e atualizadas

Ao aprender uma rota melhor, o AODV atualiza as informações de roteamento de forma transparente para a aplicação



Nó Fonte

Movimenta-se durante uma sessão ativa

• Reiniciar ou não um processo de descobrimento de rota

Nó Destino ou Nó Intermediário

Movimentam-se

São desativados

Quebra de Enlace



Maneira de um nó conhecer seus vizinhos (atestar conectividade)

• Escutando pacotes broadcast de outros nós

• Mensagens Hello

• Time-to-Live (TTL) = 1

• Receber resposta dos vizinhos

• Não receber confirmação dos vizinhos (quebra de enlace)

• Receber resposta de novos vizinhos



Nó que detectou a falha deve informar sobre a quebra do enlace

• Nós predecessores são mantidos em cada entrada da tabela de roteamento

• RERR (unicast ou broadcast)

• Nó que recebe o RERR encaminha para todos os seus predecessores

Todas as rotas que dependiam do enlace inativo são retiradas de todas as tabelas de roteamento da rede

Quando nó fonte recebe notificação de quebra de link, decide se reinicia ou não um novo processo de descobrimento de rota



Término do processo é garantido

Rotas livres de loops

Número de nós finito

AODV mais vantajoso em relação ao DSR

AODV informa todos os nós que usam o enlace quando uma falha ocorre


Conclusão

AODV foi apresentado como um protocolo de roteamento dinâmico para redes móveis ad hoc

Características:

• Descoberta de rotas sob demanda

• Único encaminhamento de um pacote RREQ

• Armazenamento de uma rota por destino

• Utilização de números de seqüência

• Mecanismos que evitam loops

• Rotas mais atualizadas


Bibliografia

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.

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.

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.

AODV site, http://moment.cs.ucsb.edu/AODV/aodv.html. Acessado em 30 de julho de 2006.

Tanenbaum, A. S.; Redes de Computadores. 4a Ed. Rio de Janeiro: Campus, 2003.

Perkins, C. E.; Belding-Royer, E. M.; Das, S. R.; Marina, M. K.; Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks, IEEE Personal Communications, fevereiro de 2001.


Carina Teixeira de Oliveira

[email protected]

http://www.gta.ufrj.br/~carina

Ad Hoc On-Demand Distance Vector (AODV)

Documents

Rio de Janeiro, Agosto de 2006. Carina Teixeira de Oliveira CPE 825 - Roteamento em Redes de Computadores Prof. Luís Henrique M. K. Costa Ad Hoc On-Demand