II.2.2.2 Le protocole de routage AODV
Ad Hoc On-Demand Distance-Vector Protocol (AODV)
[Per01] est un protocole réactif basé sur le principe des
protocoles de routage à vecteur de distance. Il est pour l'essentiel une
combinaison de DSDV et de DSR. Il emprunte, à DSR ses mécanismes
de découverte et de maintenance des routes << Route Discovery
>> et << Route Maintenance >>; à DSDV, son routage
<< saut par saut >>, les numéros de séquences ainsi
que la diffusion des mises à jour des tables de routage. Ce protocole
fait l'objet d'un grand nombre de recherches dû à toutes ses
caractéristiques; il est en effet l'un des principaux
protocoles au sein du groupe de recherche MANET.
Comme le fait DSR, AODV utilise une requête de route
dans le but de créer un chemin vers une certaine destination. Cependant,
AODV maintient les chemins d'une façon distribuée en gardant une
table de routage au niveau de chaque n°ud de transit appartenant au chemin
cherché. Une entrée de la table de routage contient
essentiellement :
- L'adresse de la destination.
- Le n°ud suivant.
- La distance en nombre de n°ud (i.e. le nombre de
n°ud nécessaire pour atteindre la destination).
- Le numéro de séquence destination.
- Le temps d'expiration de l'entrée de la table.
Quand un noeud de transit envoie le paquet de la requête
à un voisin, il sauvegarde aussi l'identificateur du noeud à
partir duquel la première copie de la requête est reçue.
Cette information est utilisée pour construire le chemin inverse (figure
2-6 (b)) qui sera traversé par le paquet réponse de route (cela
induit que l'AODV ne supporte que les liens symétriques). Puisque le
paquet réponse de route va être envoyé à la source,
les n°uds appartenant au chemin de retour vont modifier leurs tables de
routage suivant le chemin contenu dans le paquet de réponse.
Un n°ud diffuse une requête de route (RREQ :
Route REQuest) dans le cas où il aurait besoin de
connaître une route vers une certaine destination et qu'une telle route
ne serait pas disponible (figure 2-6 (a)). Cela peut arriver si la destination
n'est pas connue au préalable, ou si le chemin existant vers la
destination est devenu défaillant (i.e. la métrique qui lui est
associée est infinie). 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. Le numéro de séquence
source du paquet RREQ contient la valeur du numéro de séquence du
n°ud source. Comme nous lavons déjà dit,
après la diffusion du RREQ, la source attend le paquet réponse de
route (RREP : Route REPly). Si ce dernier n'est pas reçu
pendant une certaine période (appelée RREP_ WAIT_TIME),
la source peut rediffuser une nouvelle requête RREQ. A chaque
nouvelle diffusion, le champ Broadcast ID du paquet RREQ est
incrémenté. Si la requête RREQ est rediffusée un
certain nombre de fois (RREQ_RETRIES) sans la réception de
réponse, un message d'erreur est délivré.
RREQ
2
RREQ
6
RREQ
RREQ
RREQ
5
RREQ
Source Destination
1
8
3
RREQ
RREQ
4
RREQ
7
(a)La propagation du paque RREQ
RREP
RREP
2 6
RREP
Source Destination
1
8
3
5
4
7
(b)Le chemin pris par RREP
Figure 2.6: Les deux requêtes RREQ et RREP utilisées
dans le protocole AODV.
Afin de maintenir des routes consistantes, une transmission
périodique du message "HELLO" est effectuée. Si trois
messages "HELLO" ne sont pas reçus consécutivement
à partir d'un Q°ud voisin, le lien en question est
considéré défaillant. Les défaillances des liens
sont, généralement, dues à la mobilité des
n°uds dans le réseau. Les mouvements des n°uds qui ne
participent pas dans le chemin actif n'affectent pas la consistance des
données de routage. Quand un lien reliant un n°ud p
à un n°ud qui le suit dans le chemin de routage devient
défaillant, le n°ud p diffuse un paquet UNSOLICITED
RREP, avec une valeur de numéro de séquence égale
à l'ancienne valeur du paquet RREP incrémentée de
un, et une valeur infinie
de la distance. Le paquet UNSOLICITED RREP est
diffusé aux voisins actifs jusqu'à ce qu'il arrive à la
source. Une fois le paquet est reçu, la source peut initier le processus
de la découverte de routes.
L'AODV maintient les adresses des voisins à travers
lesquels les paquets destinés à un certain n°ud arrivent. Un
voisin est considéré actif, pour une destination donnée,
s'il délivre au moins un paquet de donnée sans dépasser
une certaine période (appelée active timeout period).
Une entrée de la table de routage est active si elle est
utilisée par un voisin actif. Le chemin reliant la source à la
destination en passant par les entrées actives des tables de routage est
dit un chemin actif. Dans le cas de défaillances de liens, toutes les
entrées des tables de routage participant au chemin actif et qui sont
concernées par la défaillance sont supprimées. Cela est
accompli par la diffusion d'un message d'erreur entre les n°uds actifs.
Le protocole de routage AODV (tout comme le protocole DSR),
n'assure pas l'utilisation du meilleur chemin existant entre la source et la
destination. Cependant, des évaluations de performances récentes
ont montré qu'il n'y a pas de grandes différences (en terme
d'optimisation) entre les chemins utilisés par le protocole AODV et
celles utilisées par les protocoles basés sur les algorithmes de
recherche des plus courts chemins. De plus, le protocole AODV ne
présente pas de boucle de routage et évite le problème du
comptage à l'infini "counting to infinity" de Bellman-Ford,
ce qui offre une convergence rapide quand la topologie du réseau
est dynamique.
Dans les protocoles réactifs, plus le niveau de
mobilité des n°uds est élevé, plus le nombre de
demandes d'itinéraire augmente. En raison de cela, le délai
d'attente moyen tend à devenir plus grand [Per00].
Le DSR est meilleur que le AODV dans tous les niveaux de
mobilité et principalement dans les plus petits réseaux. Un tel
comportement peut être justifié par la forme dont les
itinéraires sont établis dans DSR. Cependant, dans de grands
réseaux, AODV prend les dessus sur le DSR.
| 
