Le protocole de routage AODV
(Ad -Hoc On Demand Distance Vector)
Sommaire
I- Introduction ......................................................................................................................................... 2
II- Définition ............................................................................................................................................ 2
III-Les types de messages dans AODV .................................................................................................... 2
IV-Principe du numéro de séquence ...................................................................................................... 3
V-Découverte de chemins ...................................................................................................................... 4
VI-Maintenance des routes .................................................................................................................... 6
Conclusion ............................................................................................................................................... 7
Références............................................................................................................................................... 8
I- Introduction
Lors de la transmission d’un paquet d’une source vers une destination, il est nécessaire de
faire appel à un protocole de routage qui acheminera correctement le paquet par le
« meilleur chemin ». Ils sont responsables du choix de la meilleure route vers la destination
qui minimise les collisions, les interférences ou encore le délai.
Au lieu de maintenir les tables de routage en tout temps, le routage réactif crée les routes à
la demande du nœud émetteur. L’instabilité des nœuds dans les réseaux ad hoc due au
déplacement des nœuds rend le routage réactif plus adapté à ces réseaux par rapport au
routage proactif.
Dans ce qui suit, nous allons voir en détail le protocole de routage AODV qui fait partie des
protocoles de routage réactifs dans les réseaux Ad-Hoc.
II- Définition
Ad- Hoc On Demand Distance Vector (AODV) est un protocole de routage réactif basé sur le
principe des vecteurs de distance. Il détermine l’itinéraire de la source vers la destination
que lorsque la source prend l’initiative.
III-Les types de messages dans AODV
Le protocole AODV fonctionne à partir de trois (3) types de message :
Message de demande de route RREQ : Route Request Message. Il est diffusé en
broadcast par le nœud source à tous ses voisins directs pour chercher une
destination.
Fig1 : format d’un paquet RREQ
Hop count : nombre de sauts à partir de l’adresse IP d’origine jusqu’au nœud de
traitement de la demande.
RREQ ID : un numéro de séquence unique permettant d’identifier les RREQ
Destination Sequence Number : le dernier numéro de séquence reçu par l’émetteur
pour toute route vers la destination.
Message de réponse de route RREP : Route Reply Message. C’est la réponse à un
paquet RREQ.
Fig2 : format d’un paquet RREP
Message d’erreur de route RERR : Route Error Message. Il est généré en cas de route
non valide pour informer la source de relancer la découverte de route.
Dest count
Fig3 : format d’un paquet RERR
Dest Count : nombre de destinations inaccessibles inclues dans le message, doit être
au moins égale à 1.
En plus des messages ci-dessus, l’AODV utilise des paquets de contrôle HELLO pour vérifier la
connectivité des routes.
IV-Principe du numéro de séquence
L'AODV utilise les principes de numéro de séquence afin d'éviter le problème des boucles
infinie et des transmissions inutiles de messages sur le réseau. Il permet aussi de maintenir
la consistance des informations de routage.
A cause de la mobilité des nœuds dans le réseau ad hoc, les routes changent fréquemment
ce qui fait que des routes maintenues par certains nœuds deviennent invalides.
Les numéros de séquence permettent d'utiliser les routes les plus nouvelles ou autrement
dit les plus fraiches (fresh routes). Un noeud est mis à jour chaque fois qu'une nouvelle
information provient d'un message RREQ, RREP ou RERR. Il incrémente son propre numéro
de séquence dans les cas suivants :
Il est lui-même le noeud destination et offre une nouvelle route pour l'atteindre.
Il reçoit un message AODV (RREQ, RREP, RERR) contenant de nouvelles informations
sur le numéro de séquence d'un noeud destination.
Le chemin vers une destination n'est plus valide.
V-Découverte de chemins
Le processus de découverte de chemin est lancé lorsqu’un nœud source a besoin de
communiquer avec un autre nœud pour lequel il n’a pas d’information dans sa table de
routage.
Cette tâche est réalisée par la diffusion de message RREQ sur une adresse de type broadcast
à travers le réseau. Le champ numéro de séquence destination du paquet RREQ contient la
dernière valeur connue du numéro de séquence associé au nœud destination. Cette valeur
est recopiée de la table de routage. Si le numéro de séquence n'est pas connu, la valeur
nulle sera prise par défaut. Avant l'envoi du paquet RREQ, le noeud origine sauvegarde
l'identificateur du message et l'adresse IP de façon à ne pas traiter le message dans le cas où
un voisin le lui renverrait. Un fois la demande de route effectuée, le noeud demandeur se
met en attente de réponses.
Quand un noeud de transit (intermédiaire) reçoit le paquet de la requête, il vérifie dans sa
table historique si cette requête a déjà été vue et traitée. Si le paquet est doublon, le nœud
doit l'ignorer et arrêter le traitement. Dans le cas contraire le couple (@ source, ID de
requête) sera inscrit dans la table historique pour rejeter le futur doublon et le noeud
continue le traitement en cherchant la destination dans sa table de routage. S'il possède une
route récente, à noter qu'une route est récente si le numéro de séquence de la destination
dans la table est supérieur ou égal au numéro de séquence dans le paquet RREQ alors le
noeud envoi un paquet de réponse (RREP) à la source lui indiquant comment atteindre la
destination. Sinon si le noeud ne connait pas la route vers la destination, il incrémente le
nombre de sauts (Hop Count) et rediffuse le paquet.
Avant l'envoi du paquet, le noeud intermédiaire sauvegarde l'adresse du nœud précédent et
celle du noeud source à partir duquel la première copie de la requête est reçue. Cette
information est utilisée pour construire le chemin inverse qui sera emprunté par le
paquet réponse de la route de manière unicast (cela veut dire qu'AODV supporte seulement
les liens symétriques).
Si la requête atteint le noeud destination, un paquet RREP est construit avec le nouveau
numéro de séquence de la destination et suit la route inverse notée dans les tables. Le
champ hop count de message route RREP est incrémenté à chaque noeud traversé. Une fois
le noeud origine atteint, la valeur du champ hop count représente la distance en nombre de
sauts du nœud source vers le nœud destination. Quand le nœud reçoit une réponse de
route, le paquet est examiné et une entrée pour la route vers la destination est inscrite dans
la table de routage si au moins une de ces conditions est satisfaite :
Aucune route vers la destination n'est connue ;
Le numéro de séquence pour la destination dans le paquet de réponse est supérieur
à la valeur présente dans la table de routage ;
Les numéros de séquences sont égaux mais la nouvelle route est plus courte.
Afin de limiter le coût dans le réseau, AODV propose d'étendre la recherche
progressivement. Initialement, la requête RREQ est diffusée à un nombre de sauts limité. Si
la source ne reçoit aucune réponse après un délai d'attente déterminé, elle retransmet un
autre message de recherche en augmentant le nombre maximum de sauts. En cas de non
réponse, cette procédure est répétée un nombre maximum de fois avant de déclarer que
cette destination est injoignable.
A chaque nouvelle diffusion, le champ Broadcast ID du paquet RREQ est incrémenté pour
identifier une requête de route particulière associée à une adresse source. Si la requête
RREQ est rediffusée un certain nombre de fois (RREQ.RETRIES) sans réception de réponse,
un message d'erreur est délivré à l'application.
VI-Maintenance des routes
AODV maintient les routes aussi longtemps que celles-ci sont actives. Une route est
considérée active tant que des paquets de données transitent périodiquement de la source à
la destination selon ce chemin. Lorsque la source stoppe d'émettre des paquets de données,
le lien expirera et sera effacé des tables de routage des nœuds intermédiaires. Si un lien se
rompt lorsqu'une route est active, le lien est considéré défaillant. Les défaillances des liens
sont généralement dues à la mobilité du réseau ad hoc.
Afin de détecter cette défaillance, AODV utilise les messages de contrôle « HELLO » qui
permettent de vérifier la connectivité ou plutôt l'activité des routes. Un nœud détermine
l'activité d'une route en écoutant périodiquement les messages « HELLO » transmis par ses
voisins. Si pendant un laps de temps, trois messages « HELLO » ne sont pas reçus
consécutivement, le noeud considère que le lien vers ce voisin est cassé. Il envoie un
message d'erreur (RERR) à la source et la route devient invalide.
Exemple d’application
Conclusion
L'un des avantages d'AODV est l'utilisation de numéro de séquence dans les messages. Ces
numéros de séquences permettent d'éviter les problèmes de boucles infinies et sont
essentiels au processus de mise à jour de la table de routage.
Un autre avantage est le rappel de l'adresse IP du noeud origine dans chaque message. Ceci
permet de ne pas perdre la trace du noeud à l'origine de l'envoi du message lors des
différents relais.
Références
Les technologies sans fil : Le routage dans les réseaux ad hoc (OLSR et AODV) :
https://www.memoireonline.com/01/09/1878/m_les technologies-sans-fil-Le-routage-dans-
les-reseaux-ad-hoc-OLSR-et-AODV4.html
OLSR-AODV :
http://wapiti.enic.fr/commun/ens/peda/options/ST/RIO/pub/exposes/exposzsrio2006/Beau
doux-Lemay/aodv_p4.html
Le protocole AODV – Découverte chemin : https://youtu.be/xNNOdyl9nVc
AODV (Ahoc ONdemand Distance Vector outing) - MANET REACTIVE ROUTING PROTOCOL :
https://youtu.be/wlyibjr-Hhrs
