Infraestrutura e configuração

Protocolos de roteamento, como o próprio nome menciona, se preocupa com a "criação" de rotas para transmitir uma mensagem: descobre, estabelece e faz manutenção das conexões. O protocolo AODV está preocupado com a Atualização da Rede, Manutenção das Rotas e o Caminho Reverso.

O protocolo utiliza para calcular suas rotas o algoritmo Bellman-Ford assim como em DSDV.

Descoberta de rotas

A partir de [1], quando um nó recebe um pacote de controle AODV de um vizinho, ou atualiza uma nova rota para um determinado destino ou sub-rede, o mesmo verifica sua tabela de rotas para a entrada e o destino. Caso não haja uma entrada correspondente para esse destino, o número de sequência desse nó é incrementado e a rede é inundada a partir de pacotes Route Requests (RREQ). A figura abaixo apresenta o formato da RREQ.

Os seus campos dados da seguinte forma:

1. Type: 1
2. J: Join flag, reservado para multicast
3. R: Repair flag, reservado para multicast
4. G: Gratuitous RREP flag, indica se um RREP gratuito deve ser unicast para o nó especificado no campo Destination IP Address
5. D: Destination only flag, indica que apenas o destino pode responder a este RREQ
6. U: Unknown sequence number, indica que o número de sequência do destino é desconhecido
7. Reserved: Enviado como 0 e é ignorado quando recebido
8. Hop Count: Contador de Saltos a partir do Originator IP Address até o nó que trata da solicitação. (valor inicial igual a zero)
9. RREQ ID: Um número de sequência que identifica exclusivamente o RREQ específico quando tomado em conjunto com o endereço IP do nó de origem.
10. Destination IP Address: Endereço IP do destino
11. Destination Sequence Number: O último número de sequência do destino
12. Originator IP Address: Endereço IP da fonte
13. Originator Sequence Number: O número de sequência atual a ser usado na entrada de rota apontando para o originador da solicitação de rota

Quando um nó recebe um pacote RREQ, são verificados o Originator IP Address e o RREQ ID, caso seja uma duplicata, então o RREQ é descartado. Caso contrário, o nó que receber a requisição fará o seguinte:

• Caso o nó não seja o de destino e ele não possua uma rota válida para alcançar o destino, o Hop Count será incrementado e o nó inundará seus vizinhos com o RREQ.
• Se o nó for o próprio destino ou se ele possuir uma entrada ativa para o destino com um Destination Sequence Number maior ou igual que o Destination Sequence Number contido no pacote RREQ, então o nó responde o seu vizinho com um Route Reply (RREP) em unicast.

Os campos da RREP são dados da seguinte forma:

1. Type: 2
2. R: Repair flag, reservado para multicast
3. A: Acknowledgment requirement
4. Reserved: Enviado como 0 e é ignorado quando recebido
5. Prefix Size: Se diferente de zero, o tamanho do prefixo de 5 bits especifica que o próximo salto indicado pode ser usado para quaisquer nós com o mesmo prefixo de roteamento
6. Hop Count: Contador de Saltos a partir do Originator IP Address até o nó que trata da solicitação. (valor inicial igual a zero)
7. Destination IP Address: Endereço IP do destino
8. Destination Sequence Number: O último número de sequência do destino
9. Originator IP Address: Endereço IP da fonte
10. Lifetime: Tempo de vida da rota em milisegundos

Manutenção do AODV

Como os participantes da rede são dispositivos móveis, então a cada movimentação é preciso decidir se o nó descobrirá uma nova rota até o destino. Além disso, é possível que se ocorra uma quebra de enlace tendo em vista que os nós se movimentam. Existem duas formas de um nó verificar sua conectividade com seus vizinhos:

1. Escutar pacotes broadcast que são endereçados à outros vizinhos.
2. Enviar periodicamente por difusão mensagens Hello. Os nós que recebem este tipo de mensagem, criam ou atualizam uma entrada em sua tabela de roteamento relativa ao vizinho que enviou a mensagem. Caso o Hello não seja recebido, então é determinado que ocorreu a quebra de um enlace, ou seja, teve uma mudança na topologia da rede.

Quando algum nó percebe alguma falha, ele avisa aos nós afetados dependentes do antigo enlace a partir de mensagens Route Error (RERR). Os nós que recebem esse tipo de mensagem, encaminham o pacote RERR aos seus predecessores. A figura abaixo apresenta o formato da RERR.

Os seus campos dados da seguinte forma:

1. Type: 3
2. N: No delete flag; quando o nó executou um reparo local de um enlace, então é feito isso para os nós não exluirem a rota.
3. Reserved: Enviado como 0 e é ignorado quando recebido
4. Hop Count: Contador de Saltos a partir do Originator IP Address até o nó que trata da solicitação. (valor inicial igual a zero)
5. DestCount: Número de destinos inalcançáveis incluídos na mensagem. (Mínimo é 1)
6. Unreachable Destination IP Address: O endereço IP do destino que se tornou inalcançavel devido a quebra do enlace.
7. Unreachable Destination Sequence Number: Número de sequência da tabela de roteamento do destino que não foi alcançado contido no campo Unreachable Destination IP Address.

AODV e Atualização de rotas

Quando um nó recebe um pacote de controle AODV de um vizinho, ou atualiza uma nova rota para um determinado destino ou sub-rede, o mesmo verifica sua tabela de rotas para a entrada e o destino. Caso não haja uma entrada correspondente para esse destino, o número de sequência desse nó é incrementado e a rede é inundada a partir de pacotes Route Requests (RREQ).

Para usos militares ou em equipes de resgate a solução abordada é bastante consistente, uma vez que todos os membros da rede são igualmente confiáveis e fazem parte da mesma equipe. Porém ao estender-se o AODV para propósitos mais gerais, tal solução passa a não ser viável.

AODV e segurança

Analisando o funcionamento de tal algoritmo, é notável que em nenhum momento mencionou-se a questão da segurança. Em uma primeira análise, fica evidente que grande parte de seus usos é compatível com um modelo de criptografia simétrico, no qual diversos nós utilizam a mesma chave para se autenticar.

Para usos militares ou em equipes de resgate a solução abordada é bastante consistente, uma vez que todos os membros da rede são igualmente confiáveis e fazem parte da mesma equipe. Porém ao estender-se o AODV para propósitos mais gerais, tal solução passa a não ser viável.

Há a necessidade de se garantir a confiabilidade dos nós por diversos motivos, mas um bom caso é levantado em [3] com o black hole attack. Um nó mal intencionado pode enviar um RREP mesmo não sendo o destinatário ou não tendo um caminho descoberto para ele, e no caso do RREP falsificado chegar primeiro até o remetente, tal nó malicioso receberia todo tráfego, que originalmente deveria ir ao destinatário.

Ainda em [3], os autores propõem um algoritmo que não garante a autenticação dos nós e nem sua lisura, todavia impede que nós maliciosos possam gerar maiores prejuízos à conectividade da rede. Tal algoritmo utiliza pacotes de segurança com números de sequência aleatórios, de tal forma que uma fonte/destinatário precisa receber no mínimo dois pacotes de uma mesma terminação passando por caminhos distintos para validá-la.

Secure AODV

Ao receber algum pacote RREP, o remetente adiciona a rota a sua tabela de roteamento e envia pacotes SRREQ ao destinatário através das rotas descobertas, esses pacotes contém um mesmo número gerado aleatoriamente por R (remetente). Por sua vez, o destinatário irá receber tais pacotes e adicionará as rotas a sua tabela de roteamento local.

Em seguida, os números de sequência serão verificados, se D tiver pelo menos duas entradas com o mesmo número, ele enviará pacotes do tipo SRREP para R, pelo mesmo caminho que os respectivos SRREQ foram recebidos.

R esperará até receber pelo menos dois pacotes SRREP, quando isso acontecer, o destinatário terá pelo menos dois caminhos confiáveis da fonte até D. Além disso, no caso de detecção de algum RREP que tenha chego antes desses melhores caminhos descobertos, R enviará em broadcast que os nós intermediários responsáveis por ele devem ser isolados.

Qualidade de serviço

Nesta sessão, discutiremos o protocolo QS-AODV, proposto em [10], que tenta estender funcionalidade de qualidade de serviço no protocolo padrão. Tal preocupação é justificável, especialmente quando é necessário o tráfego de vídeo em tempo real, que poderia ser útil em desastres naturais para guiar resgates por exemplo.

Pelo funcionamento padrão do protocolo, descrito nos capítulos anteriores é possível notar que ele não faz nenhuma menção à qualquer serviço diferencial fornecido pelo caminho descoberto, sendo a conexão em si o único fim.

Portanto, mudanças nos mecanismos de descobertas e manutenção de rotas são necessárias, sendo descritas originalmente em [10] e resumidas aqui com o intuito de garantir a coesão do trabalho.

Descoberta de Novos nós

Primeiramente, é necessário organizar os processos por um session ID, ao invés de se utilizar do nó de destino nas tabelas de roteamento, já que diferentes aplicações podem utilizar a mesma rota, mas objetivando métricas distintas.

A lógica de se enviar uma mensagem em broadcast quando determinado destino precisa ser alcançado e o mesmo não se encontra na tabela de roteamento do remetente é o mesmo, porém quando um vizinho não atende o requisito estabelecido no pacote, como largura de banda por exemplo, a mensagem é descartada. Garantindo assim que a mesma só se propague por rotas capazes de sustentar a aplicação.

Todavia, pode ser que a largura de banda antes disponível não esteja mais presente em determinado nó, de modo que ele precisará enviar aos nós antecedentes um pacote RERR com flag marcada para RREPFAIL, de modo que o caminho será recursivamente desalocado. Ao chegar no destinatário, o mesmo poderá ter descoberto outro caminho para o remetente, enviando o RREP através dele.

Manutenção de Rotas

É possível de se imaginar que quando uma variável de qualidade de serviço é adicionada, mais difícil e repetitivo será o processo de manutenção. No QS-AODV, assume-se que se um nó cai, provavelmente o próximo ainda estará disponível, de modo que é necessário somente encontrar um caminho até ele. Para tanto, é necessário adicionar o nó seguinte ao próximo na tabela de roteamento.

Quando um determinado link cai, o nó remetente envia um pedido de reparo local, RREQ, informando a largura de banda desejada e com o TTL igual a 3, para favorecer nós locais. Se um nó receber esse pacote e tiver recursos disponíveis, o mesmo criará uma entrada para a origem e reenviará o pacote em broadcast para seus vizinhos. Quando o nó almejado receber o pacote (o sucessor do nó caído), ele enviará um RREP para o remetente através do nó antecessor, este último adicionará uma rota para ele e alocará os recursos de rede necessários, então encaminhando ao nó que inicialmente perdeu a conectividade.

Se o pedido de reparo expirar e seu número de sequência é maior que 1, um pacote RERR é enviado em broadcast para todos os vizinhos alertando que a rota caiu, então estes desalocam a largura de banda e inviabilizam as rotas partindo do nó caído. Se o número de sequência é igual a 1, então o pacote é enviado em unicast até o remetente.

Bibliografia

[1] Samir R. Das, Charles E. Perkins e Elizabeth M. Belding-Royer. Ad hoc On-Demand Distance Vector (AODV) Routing. RFC 3561. Jul. de 2003. DOI: 10.17487/RFC3561. URL: https://www.rfc-editor.org/info/rfc3561.

[2] GloMoSim: Simulator Projects. URL: https://networksimulationtools.com/glomosim-simulator-projects/.

[3] Songbai Lu et al. “SAODV: A MANET Routing Protocol that can Withstand Black Hole Attack”. Em: 2009 International Conference on Computational Intelligence and Security. Vol. 2. 2009, pp. 421–425. DOIi: 10.1109/CIS.2009.244.

[4] Página local sobre o MobiCS. URL: http://www-di.inf.puc-rio.br/~endler//MobiCS/index.html.

[5] Elizabeth M Royer e Charles E Perkins. “Ad-hoc on-demand distance vector routing”. Em: Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications. Vol. 2. 1999, pp. 90–100.

[6] Elizabeth M Royer e Charles E Perkins. “Multicast operation of the ad-hoc on-demand distance vector routing protocol”. Em: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking. 1999, pp. 207–218.

[7] Meeta Singh e Sudeep Kumar. “A survey: Ad-hoc on demand distance vector (AODV) protocol”. Em: International Journal of Computer Applications 161.1 (2017), pp. 38–44.

[8] Jie Wu e I. Stojmenovic. “Ad hoc networks”. Em: Computer 37.2 (2004), pp. 29–31. DOI: 10.1109/MC.2004.1266292.

[9] Manel Guerrero Zapata. “Secure ad hoc on-demand distance vector routing”. Em: ACM SIGMOBILE Mobile Computing and Communications Review 6.3 (2002), pp. 106–107.

[10] Yihai Zhang e T Aaron Gulliver. “Quality of service for ad hoc on-demand distance vector routing”. Em: WiMob’2005), IEEE International Conference on Wireless And Mobile Computing, Networking And Communications, 2005. Vol. 3. IEEE. 2005, pp. 192–19.