Wikipédia:Pages soupçonnées de violation de copyright/AODV

Un article de Wikipédia, l'encyclopédie libre.

[modifier] AODV

Le protocole "Routage avec Vecteur de Distance à la Demande" ( AODV : Ad hoc On-demand Distance Vector ) [PER 2000, PER 99], représente essentiellement une amélioration de l'algorithme DSDV discuté dans la section 3.2.1. Le protocole AODV, réduit le nombre de diffusions de messages, et cela en créant les routes lors du besoin, contrairement au DSDV, qui maintient la totalité des routes. L'AODV est basé sur l'utilisation des deux mécanismes "Découverte de route" et "Maintenance de route" ( utilisés par le DSR ), en plus du routage noeud-par-noeud, le principe des numéros de séquence et l'échange périodique du DSDV. L'AODV utilise les principes des numéros de séquence à fin de maintenir la consistance des informations de routage. A cause de la mobilité des noeuds dans les réseaux 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 fraîches ( fresh routes ). De la même manière que dans le DSR, l'AODV utilise une requête de route dans le but de créer un chemin vers une certaine destination. Cependant, l'AODV maintient les chemins d'une façon distribuée en gardant une table de routage, au niveau de chaque noeud de transit appartenant au chemin cherché. Une entrée de la table de routage contient essentiellement : 1- L'adresse de la destination. 2- Le noeud suivant. 3- La distance en nombre de noeud ( i.e. le nombre de noeud nécessaire pour atteindre la destination ). 4- Le numéro de séquence destination. 5- Le temps d'expiration de l'entrée de la table.

Quand un nœud de transit ( intermédiaire ) envoi 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 3.9(b) ), qui sera traversé par le paquet réponse de route ( cela veut dire que l'AODV supporte seulement les liens symétriques ). Puisque le paquet réponse de route va être envoyé à la source, les noeuds appartenant au chemin de retour vont modifier leurs tables de routage suivant le chemin contenu dans le paquet de réponse. Un noeud 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 n'est pas disponible ( figure 3.9(a) ). Cela peut arriver si la destination n'est pas connue au préalable, ou si le chemin existant vers la destination a expiré sa durée de vie ou il 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 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. Le numéro de séquence source du paquet RREQ contient la valeur du numéro de séquence du noeud source. Comme nous avons 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 durant 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é à l'application.

(a) La propagation du paquet RREQ ( requête de route ). 

RREQ

RREQ

RREQ

RREQ

RREQ

RREQ

RREQ

Source

Destination

1

RREQ

8

RREQ

7

6

5

4

3

2

(b) Le chemin pris par le paquet RREP ( requête de réponse ). Figure 3.9 : 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 noeud voisin, le lien en question est considéré défaillant. Les défaillances des liens sont, généralement, dû à la mobilité du réseau ad hoc. Les mouvements des noeuds qui ne participent pas dans le chemin actif, n'affecte pas la consistance des données de routage. Quand un lien, reliant un noeud p avec le noeud qui le suit dans le chemin de routage, devient défaillant, le noeud 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 noeud 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 du routage est active, si elle est utilisée par un voisin actif. Le chemin reliant la source et 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 participantes dans le chemin actif et qui sont concernées par la défaillance sont supprimées. Cela est accomplit par la diffusion d'un message d'erreur entre les noeuds actifs. Le protocole de routage AODV( et même 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

RREP

RREP

RREP

Source

Destination

1

8

7

6

5

4

3

2

plus courts chemins [DAS 98]. En plus de cela, le protocole AODV ne présente pas de boucle de routage ( une preuve de cela est détaillée dans [PER 99] ), et évite le problème "counting to infinity" de Bellman-Ford, ce qui offre une convergence rapide quand la topologie du réseau ad hoc change.

[1] [2]