4.2. PRESENTATION DU PROTOCOLE DE ROUTAGE AODV «Ad
hoc On demand Distance Vector»
4.2.1 Definition :
AODV est un protocole de routage réactif et basé
sur le principe des vecteurs de distance, capable à la fois de routage
unicast et multicast. Il représente essentiellement une
amélioration de l'algorithme proactif DSDV15.
15 J.CARSIQUE, N.DAUJEARD, A.LALLEMAND et R.LADJADJ. Op. cit.
4.2.2. Le type des messages dans AODV :
Le protocole AODV fonctionne à partir de trois types de
messages :
- les messages de demande de route RREQ : Route
Request Message. - les messages de réponse de route
RREP : Route Reply Message.
- les messages d'erreur de route RERR : Route
Error Message.
? Message de demande de route (RREQ) : Il est
sous la forme suivante :
? Message Route Reply (RREP) : Ce message est
sous la forme suivante:
? Message d'erreur (RERR) : Il est sous la forme
suivante.
En plus des messages cités avant, l'AODV utilise des
paquets contrôle HELLO qui permettent de vérifier
la connectivité des routes.
4.2.3 Le principe de numéro de séquence :
La circulation inutile des paquets de messages, qui peut
arriver avec le DBF (Distribution de Bellman Ford), est intolérable dans
les réseaux mobiles ad hoc, caractérisés par une bande
passante limitée et des ressources modestes.
L'AODV utilise les principes de numéro de
séquence afin d'éviter le problème des boucles infini et
des transmissions inutiles de messages sur le réseau, en plus il permet
de maintenir la consistance des informations de routage. A cause de la
mobilité des noeuds dans le réseau ad hoc, les routes changent
fréquemment ce qui fait que les routes maintenues par certains noeuds,
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 mis à jour chaque fois qu'une nouvelle
information provenant d'un message RREQ, RREP ou RERR, il incrémente son
propre numéro de séquence dans les circonstances suivantes :
- 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. 4.2.4 Fonctionnement de protocole :
Dans cette partie nous détaillerons le fonctionnement
de protocole AODV, en commençant d'abord par la manière dont il
découvre les routes, nous parlerons par la suite sur la façon
dont il maintient ces routes, une fois valides.
4.2.4.1 Découverte de route :
Lorsqu' un noeud veut émettre un message, il cherche
dans sa table de routage si une route valide existe pour la destination qu'il
souhaite atteindre, s'il n'en existe aucune, il se met à la recherche
d'une route.
Cette tâche est réalisée par la diffusion
de message RREQ sur une adresse de type broadcast au travers de réseau.
Le champ numéro de séquence destination de paquet RREQ,
contient la dernière valeur connue du numéro de séquence
associé au noeud 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. Une 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 stable historique si
cette requête a déjà été vue et
traitée. Si le paquet est doublon, le noeud 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
future 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érieure ou
égale au numéro de séquence dans le paquet RREQ. Dans ce
cas, le noeud envoi un paquet de réponse (RREP) à la source lui
indiquant comment atteindre la destination. Autrement le noeud ne connait pas
la route vers la destination : il incrémente le nombre de sauts et
rediffuse le paquet.
Avant de l'envoi de paquet, le noeud intermédiaire
sauvegarde l'adresse du noeud 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 traversé par le paquet réponse de la
route de manière unicast (cela veut dire qu'AODV supporte seulement
les liens symétriques).
Fig.4.1. Réponse de la route
notée dans les tables le champ hop count de
message route RREP est incrémentée à chaque noeud
traversé, une fois le noeud origine atteint, la valeur du champ hop
count représente la distance en nombre de sauts pour aller du noeud
source vers le noeud destination. Quand le noeud 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érieure à 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.
| 
