AODV (pour Ad hoc On Demand Distance Vector) est un protocole de routage destiné aux réseaux mobiles (réseau ad hoc). Il est à la fois capable de routage unicast et multicast. Il est libre de boucle, auto-démarrant et s'accommode d'un grand nombre de nœuds mobiles (ou intermittents). Lorsqu'un nœud source demande une route, il crée les routes à la volée et les maintient tant que la source en a besoin. Pour les groupes multicast, AODV construit une arborescence. Ce protocole de routage est peu gourmand en énergie et ne nécessite pas de grande puissance de calcul, il est donc facile à installer sur de petits équipements mobiles.

La première publication faisant état de AODV apparaît lors du proceedings of the 2nd IEEE workshop on mobile computing systems and application.. La démarche visait à normaliser les différents protocoles du MANET (Mobile Ad-hoc NETworks) pour les réseaux ad hoc. L'intérêt du routage dynamique ad hoc apparaît dès 1996 dans des articles comme Dynamic source routing in ad hoc wireless networks (1996).. L'appropriation par la communauté technique de ce protocole entraîne de nombreuses évolutions et adaptations. Le nombre de publications qui s'en sont ensuivies a atteint un pic d'une centaine par an en 2004 et 2005 montrant l'intérêt porté à ce protocole lors de cette période. La mise à disposition par les opérateurs de réseaux à coût raisonnable et disposant d'une couverture proche de 100 % restreint l'intérêt des réseaux ad hoc.

L'intérêt majeur des réseaux ad-hoc est qu'ils sont très facile à mettre en place et pour un coût faible. Quelques expériences furent tentées, comme le « Réseau Citoyen ». en Belgique. D'autres exemples existent de par le monde, en Afrique, ou le projet (SARI). en Inde. son utilisation pourrait pallier une couverture opérateur limitée. L'armée (Projet FELIN). ou la sécurité civile réfléchit à l'intérêt de cette organisation pour pallier une défaillance générale en cas de catastrophe naturelle par exemple.

Description technique

Principe de fonctionnement

AODV. définit cinq types de messages distincts, référencés à l'Internet Assigned Numbers Authority (IANA), transmis via le port UDP 654. Parmi ces messages ce sont les requêtes RREQ.(route request) et les réponses RREP. (route reply) qui permettent de construire ses routes utilisées pour relayer les informations sur le réseau.

Lorsqu’un nœud source veut établir une route vers une destination pour laquelle il ne possède pas encore de chemin, il diffuse en broadcast un paquet RREQ. Si une réponse RREP est reçue alors l’opération de découverte de route est terminée. Dans le cas contraire, au bout d’un délai d’attente NET_TRANVERSAL_TIME., il rediffuse le message RREQ et attend une période supérieure à la première. En l'absence de réponse RREP, ce processus peut être répété jusqu'à RREQ_RETRIES fois (par défaut RREQ_RETRIES = 2.). S'il n’y a toujours pas de réponse au bout des trois (ou RREQ_RETRIES + 1) tentatives, le processus de recherche de route est abandonné. Une nouvelle demande de route sera initiée au bout d’un délai de . Un nœud recevant un paquet RREQ émettra alors un paquet RREP (route reply) s'il est la destination ou s'il possède une route vers la destination avec un numéro de séquence supérieur ou égal à celui du paquet RREQ sinon il rediffuse le paquet RREQ. Les nœuds conservent chacun une trace des IP sources et des identifiants de diffusion des paquets RREQ. Dans le cas où ils reçoivent un paquet RREQ qu’ils ont déjà traité, ils le suppriment.

Une fois que la source a reçu les paquets RREP, elle peut commencer à émettre des paquets de données vers la destination. Si, ultérieurement, la source reçoit un RREP contenant un numéro de séquence supérieur ou égal, mais avec un nombre de sauts plus petits, elle mettra à jour son information de routage vers cette destination et commencera à utiliser la meilleure route. Une route est maintenue aussi longtemps qu’elle continue à être active, c'est-à-dire tant que des données transitent entre la source et la destination. Le lien expire quand il n’y a plus de données en transit sur le lien et au bout d'un délai appelé ACTIVE_ROUTE_TIMEOUT.. En cas de coupure du lien, le nœud extrémité émet un paquet RERR. (Route Error) vers le nœud source pour le prévenir que la destination est désormais injoignable. Si le nœud source veut toujours obtenir une route vers cette destination, il doit recommencer le processus de découverte de route.

La figure ci-dessous illustre une recherche de route à l’initiative du nœud et en direction de et les différentes tables de routages constituées. La diffusion du message RREQ à partir de se fait en broadcast vers tous ses voisins. Lorsque reçoit le message il retourne un message RREP à en passant par , et .

thumb|center|upright=3.1|Synoptique de détection de route possible par AODV entre deux nœuds A et J avec les tables de routages.

La figure ci-dessous illustre le flux de requêtes lors de l'établissement d'une connexion entre deux nœuds. La fin du schéma représente la rupture des échanges entre des nœuds en cours de transmission des données. thumb|Flux de requêtes pour la découverte de routes et lors de la rupture de lien |center|upright=2

Formats des messages Message RREQ Le message RREQRFC3561 p6 de demande de route, est le message d'interrogation des routes disponibles. Il est constitué d'une trame de : Les quatre premiers octets sont constitués du champ Type sur 8 bits forcé à 1 indiquant qu'il s'agit d'un message RREQ. Les bits suivants : J, R, G, D, U décrits plus bas indiquent les différentes utilisations du message. Un champ reserved sur 11 bits mis à 0 laisse la possibilité d'évolution ultérieurs. Puis un champ de 8 bits indique le nombre de sauts. Les quatre octets suivants portent l'identification du message. Les quatre suivants l'adresse IP de la destination. Les quatre suivants le numéro de séquence de la destination. Les deux suivants l'adresse IP d'origine. Les quatre derniers sont destinés à l'identification de la transaction par la source IP.

thumb|Message RREQ|left|upright=3

Le champ Type est forcé à 1. Le bit J : est positionné à 1 sur le message sortant en cas d'utilisation de multicast. Le bit R : est positionné à 1 sur le message retour en cas d'utilisation de multicast. Le bit G : Drapeau RREP gratuite, indique si un RREP gratuite doit être envoyé en unicast vers le nœud spécifiée dans le champ Adresse IP destination. Le bit D : Drapeau de destination seulement, indique que la destination seul peut répondre à cette RREQ. Le bit U : Numéro de séquence inconnue, indique à la destination que le numéro de séquence est inconnu. Reserved : Envoyés à 0, ignoré à la réception. Hop count : Le nombre de sauts à partir de l'adresse IP origine jusqu'au nœud de traitement de la demande. RREQ ID : Un numéro de séquence unique permet d'identifier les RREQ notamment lorsqu'elle est prise en association avec l'adresse IP d'origine. Destination IP Address : L'adresse IP destinataire pour laquelle une route est souhaitée. Destination Sequence Number : Le dernier numéro de séquence reçu par l'émetteur pour toute route vers le destinataire. Originator IP Address : L'adresse IP du nœud à l'origine de la demande de route. Originator Sequence Number : le numéro de séquence actuelle utilisée dans l'itinéraire pointant vers l'initiateur de la route demandée.

Message RREP Le message RREPRFC3561 p7 de réponse à la demande de route, est le message indiquant au demandeur les routes disponibles. Il est constitué d'une trame de : Les quatre premiers octets sont constitués du champ Type sur 8 bits forcé à 2 indiquant qu'il s'agit d'un message RREP. les deux bits R et A décrits plus bas indiquent pour le premier qu'une route défectueuse est réparée, le deuxième pour sa part indique que ce message sera suivi d'un RREP-ACK. Puis 12 bits réservés pour évolution mis à 0. 5 bits de préfixe référençant le nœud pour les routages. Puis un champ de 8 bits indique le nombre de saut. Les quatre octets suivants portent l'identification du message. Les quatre suivants l'adresse IP de la destination. Les quatre suivants le numéro de séquence de la destination. Les deux suivants l'adresse IP d'origine. Les quatre derniers sont destinés à l'identification de la transaction par la source IP.

thumb|Message RREP|left|upright=3

Le champ Type : forcé à 2. Le bit R : Indicateur de réparation; utilisée pour le multicast. Le bit A : acquittement requis. Reserved : Envoyé à 0, ignoré à la réception. Prefix Size : Si non nul, la taille de préfixe à 5 bits indique que le saut suivant peut être utilisé pour tous les nœuds avec le même préfixe de *routage (tel que défini par le préfixe Taille) pour la destination demandée. Hop Count : Le nombre de sauts à partir de l'adresse IP origine à l'adresse IP de destination. Pour une route de multicast demandée, indique le *nombre de sauts à effectuer à chaque membre de l'arbre en envoyant l'RREP. Destination IP : L'adresse IP de la destination pour laquelle une route est fournie. Destination Sequence Number : Le numéro de séquence de la destination associée à l'itinéraire. Originator IP Address : L'adresse IP du nœud à l'origine du RREQ pour laquelle l'itinéraire est fourni. Lifetime : Le temps en millisecondes pendant lequel les nœuds recevant l'RREP peuvent considérer la route comme étant valide.

Message RERR Le message RERRRFC3561 p9 indiquant une route en erreur est le message retour signalant au demandeur les routes en erreur. Il est constitué d'une trame de : Les quatre premiers octets sont constitués du champ Type sur 8 bits forcé à 3 indiquant qu'il s'agit d'un message RERR. le bit N décrit plus bas indique qu'une route défectueuse est réparée. Puis 15 bits réservés pour évolution mis à 0. Les 8 bits suivants indiquent le numéro de destination inaccessible. Puis sur quatre octets l'adresse IP de destination inaccessible. Les huit suivants indiquent si besoin le complément d'adresse.

thumb|Message RERR|left|upright=3

Le champ Type : forcé a 3. le bit N : Indicateur de non-suppression. Quand un nœud a effectué une réparation locale d'un lien. Les nœuds amont ne doivent pas supprimer la route. Reserved : Envoyé à 0, ignoré à la réception. DestCount : Le nombre de destinations inaccessibles inclus dans le message, doit être d'au moins de un. Unreachable Destination IP Address : L'adresse IP destinatrice qui est devenue inaccessible en raison d'une coupure de liaison. Unreachable Destination Sequence Number : Le numéro de séquence dans l'entrée de la table de routage pour la destination indiquée dans le champ précédent Destination IP inaccessible.

Message RREP-ACK Le message RREP-ACKRFC3561 p10 d'accusé de réception de route de repli, est le message indiquant la prise en compte d'une autre route disponible. Il est constitué d'une trame de . Le premier octet est constitué du champ Type sur 8 bits forcé à 4 indiquant qu'il s'agit d'un message RREP-ACK. Les 8 bits suivant mis à 0 sont réservés pour évolution.

thumb|Message RREP-ACK|left|upright=3

Le champ Type : forcé à 4. Reserved : forcé à 0, ignoré à la réception.

Motivation des acteurs AODV a été expérimenté sur de nombreux moyens de communications (Wi-Fi., WiMAX., 4G., etc.) ainsi que des évolutions de ce protocole ont été développées pour être compatible avec des systèmes d’exploitation comme Linux. et Windows..

Études Spécifiques En une étudecapteurs sans fils a été publiée sur les réseaux de capteurs ainsi que sur les différents protocoles de routage dont AODV. Cette étude aborde les contraintes liées aux capteurs sans fil (consommation énergétiquecapteurs sans fils (p2.2), la qualité de servicecapteurs sans fils (p2.5), etc ), les perspectivescapteurs sans fils (p3.1) futures d’utilisation de ces réseaux dans les domaines comme le médical, le militaire, dans des applications commerciales, mais aussi dans le domaine environnemental.