Ad-hoc On-demand Distance Vector

AODV (pour Ad hoc On Demand Distance Vector) est un protocole de routage destiné aux réseaux mobiles (en mode 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 [1]. La démarche visait à normaliser les différents protocoles du MANET (Mobile Ad-hoc NETworks)pour les Réseau 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) [2]. L'appropriation par la communauté technique de ce protocole entraîne de nombreuses évolutions et adaptations. Le nombre de publication qui s'en sont suivies pour atteindre un pic d'une centaine par an en 2004 et 2005 montre 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 par exemple le « Réseau Citoyen »[3] en Belgique. D'autres exemples existent de part le monde, en Afrique, ou le projet (SARI)en Inde [4]. son utilisation pourrait pallier une couverture opérateur limitée. L'armée (Projet FELIN) [5] 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.


Sommaire

Description Technique

Principe de fonctionnement

AODV construit ses routes grâce aux requêtes RREQ [6](route request) et RREP [7] (route reply). AODV utilse le port UDP (User Datagram Protocol) 654[8] pour transmettre ses messages. Il existe 5 types de messages pour le protocole AODV qui sont référencés à l'IANA (Internet Assigned Numbers Authority)[9].

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[10], il rediffuse le message RREQ et attend une période supérieure à la première et ceux-ci 2 fois (RREQ_RRTRIES[11] = 2). Au bout des trois tentatives s'il n’y a pas de réponse alors le processus de recherche de route est abandonné. Une nouvelle demande de route sera initiée au bout d’un délai de 10s. 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. S’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 égale, 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 transite sur le lien et au bout d'un délai appelé ACTIVE_ROUTE_TIMEOUT [12]. En cas de coupure du lien, le nœud extrémité émet un paquet RERR[13] (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.

Formats des messages

Message RREQ

Message RREQ

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 a 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 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 noeud à 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

Message RREP

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 noeud à 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 RRER

Message RRER

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 noeuds amont ne doit 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

Message RREP-ACK

Le champ Type : forcé à 4.
Reserved : forcé à 0 ignoré à la reception

Motivation des acteurs

Historique

En 1997, Il est fait état de AODV, en 1998 lors de la publication du compte rendu du meeting Mobilcom 98: Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking' qui a eu lieu en décembre 1997[14].

À cette occasion d'autres protocoles/algorithmes furent étudiés pour le routage MANET (Mobile Ad-hoc NETworks) :

  • TORA Temporally Ordered Routing Algorithm[15];
  • ZRP Zone Routing Protocol [16];
  • IMEP Internet MANET Encapsulation Protocol [17].

En 1999, le protocol de routage AODV [18] est décrit dans un document co-écrit par Charles E.Perkins et Elizabeth M.Royer.

En 2000, AODV-BR [19] est une évolution du protocole permettant la gestion du backup routing ce qui sécurise les échanges.

En 2000 AODV6[20] une version adaptée pour IPv6.

En 2000 MAODV[21] est une évolution de AODV pour le Multicast qui servira de support en 2004[22] à la création d'un service DNS (Domain Name System) sur les réseaux ad-hoc.

En 2001 AOMDV[23] est une adaptation du protocole AODV pour le Multipath.

En 2002 il est fait une comparaison des consommations d'énergie de 4 principaux protocoles de routage dans les réseaux MANET(DSR, AODV, TORA et DSDV)[24].

En 2003 LB-AODV[25] est une évolution permettant une meilleure efficacité de AODV par l'introduction de la Répartition de charge (load-balancing).

En 2004 AODV-bis[26] permet de limiter à des zones prédéfinies l'envoi des messages de découvertes de routes.

En 2006 AODV-SEC[27] est une évolution de AODV qui permet l'utilisation de certificats et des clés publiques.

En 2009 AODV-GT[28] est une évolution pour la sécurisation des données échangées par AODV dans les réseaux MANET utilisés en cas de crise(eMANETs : emergency mobile ad hoc networks).

En 2010 EA-AODV[29] évolution de AODV pour diminuer la consommation d'énergie de AODV.

En 2010 S-AODV[30]: adaptation de AODV pour les réseaux 6LoWPAN.

En 2011 RE-AODV[31].

Socle de différentes versions comme AODV-MS, AODV-light, etc.

Positionnement par rapport aux autres protocoles ad-Hoc concurents

Protocoles réactifs, dynamiques, statics (topologie) réactifs proactifs.

En 2002 Optimized link state routing protocol OLSR[32] est crée. C'est un protocole réactif.

En 2004 un concurrent de AODV est crée pour diminuer la consommation d'énergie lors de la découverte de routes[33].

En 2010 une étude comparative[34] a été menée entre OLSR et AODV dans les réseaux VANET Vehicular Ad-Hoc Network. Cette étude a démontré qu'AODV est plus adaptée qu'OLSR pour une utilisation dans des voitures.

En 2011 une étude comparative[35] a été menée entre OLSR, AODV et DSDV sur un réseau WiMAX.

Le protocole DSR Dynamic Source Routingest un protocole de routage à la source au lieu de se baser sur la table de routage de chaque routeur intermédiaire comme AODV.

Le protocole MMDV [36] est un protocole de type hybride qui s'appuit sur AODV et en est une amélioration.

AODV et la sécurité

Cette section est en cours de réécriture ou de restructuration importante. Les informations peuvent être modifiées à tout moment par le ou les utilisateurs ayant apposé ce bandeau. novembre 2011

Les recherches récentes sur les réseaux ad-hoc ne se focalisent que très peu sur les aspects sécurité. (réf vers article A Secure Routing Protocol for Ad Hoc Networks à faire). Pourtant les caractéristiques suivantes montrent à quel point les réseaux ad hoc sont vulnérables[37]:

  • transmission en milieu ouvert
  • topologies dynamiques
  • absence d’autorité centrale
  • nécessité de bonne coopération des nœuds
  • hétérogénéité des participants avec pour certains des capacités restreintes

Le routage est une fonction très sensible des réseaux sans fils ad hoc[38]. Si aucun contrôle n'est fait sur la provenance et l'intégrité des messages de routage de réseau, on peut s'exposer aux attaques[39]:

  • Black hole (informatique)
  • grey hole
  • consistant à créer une boucles infinies
  • de type détournement (consommateur d'énergie)

Des solutions de sécurisation ont vu le jour:

  • pour l'authentification «The key agreement»[40] pour ne citer qu'elle, consiste à partager une clé secrète entre les nœuds.
  • La protection de l'intégrité physique[41] des nœuds est plus problématique. S'agissant d'un réseau de capteurs lâchés en pleine nature (pour une surveillance sismique par exemple [42] on comprend d'autant plus la nécessité d'une telle protection.
  • Pour la protection de l'intégrité et de l'authentification, des messages utilisent des signatures numériques ou des MACs[43]. TESLA RFC 4442[44] est une autre solution.
  • Pour la confidantialité[45] on choisira une cryptographie symétrique peu gourmande en calcul.
  • Enfin, il n'existe aucune solution pour contrer un déni de service[46] sur le canal radio.

Un tableau comparatif met en lumière différents types d'attaques et les solutions de protection connues : (lien tableau p36 rachid bellaoui)

Concernant plus spécifiquement les recherches de sécurisation du protocole AODV :

  • ARAN propose une solution de sécurisation dans un environnement ouvert (lien vers 10 article A Secure Routing Protocol for Ad Hoc Networks).
  • SRS-AODV (lien vers SRS_AODV (Secure Routing Scheme for AODV) qui utilise fonctions cryptographiques robustes tout en minimisant la charge du calcul complexe.
  • SEC-AODV[47] dont on a parlé précédemment dans l'historique.

Parmi les solutions concrètes de contre-mesures, on notera RIDAN[48] (Real-time Intrusion Detection for Ad hoc Networks). Initialement développé pour OSPF des études ont été menées pour permettre une adaptation au protocole AODV. Ce système est destiné à détecter des intrusions en temps réel (Système de détection d'intrusion).

Cas d'implementation

Cette section est en cours de réécriture ou de restructuration importante. Les informations peuvent être modifiées à tout moment par le ou les utilisateurs ayant apposé ce bandeau. novembre 2011


logiciel

Le protocole AODV a été implémenté sur des systémes d'exploitations courant comme Linux, en 2004 Kernel 2.4 [49] crées par NIST [50](agency of the U.S. Commerce Department's Technology Administration), en 2005 UoBWinAODV[51] version 0.15 pour Windows XP écrit en C/C++ crée par ComNets de l'Universite de Bremen.

Réseaux support

Le protocole AODV a été adapté est testé sur différents types de support de transmission, sur des réseaux WPAN (Wireless Personal Aera Network) a base de ZigBee/802.15.4 en utilisant AODV-UU, sur des réseaux WIFI norme IEEE 802.11 avec R-AODV [52], sur des réseaux WIMAX [53], sur des réseaux CDMA [54], sur des réseaux 6LoWPAN [55], sur des réseaux 4G (IMT-2000) [56], sur des ondes électromagnétique en milieu sous marin[57].

materiel

Le protocole de routage AODV peut être installé sur différents équipements comme les micro capteurs de Réseau de capteurs sans fil mais aussi sur des PDA, des Ordinateur portable ....

AODV demain

Cette section est en cours de réécriture ou de restructuration importante. Les informations peuvent être modifiées à tout moment par le ou les utilisateurs ayant apposé ce bandeau. novembre 2011


4G

Notes et références

Notes


Références

  1. Perkins 1999
  2. Johnson 1996
  3. Le réseau citoyen
  4. Castro 2010, p. 1
  5. Barrère 2009, p. 2
  6. Perkins 2003, p. 7
  7. Perkins 2003, p. 8
  8. Perkins 2003, p. 11
  9. Ad Hoc On Demand Distance Vector (AODV) Parameters
  10. Perkins 2003, p. 15
  11. Perkins 2003, p. 31
  12. Perkins 2003, p. 13
  13. Perkins 2003, p. 10
  14. Macker 1998, p. 9
  15. Temporally Ordered Routing Algorithm
  16. Zone Routing Protocol
  17. IMEP
  18. Ad-hoc on-demand distance vector routing
  19. AODV-BR backup routing in ad hoc networks
  20. Ad hoc On-Demand Distance Vector (AODV) Routing for IP version 6
  21. http://tools.ietf.org/html/draft-ietf-manet-maodv-00 Multicast Ad hoc On-Demand Distance Vector (MAODV) Routing
  22. Name directory service based on MAODV and multicast DNS for IPv6 MANET
  23. On-demand Multipath Distance Vector Routing in Ad Hoc Networks
  24. A performance comparison of energy consumption for Mobile Ad Hoc Network routing protocols
  25. Efficient On-Demand Routing for Mobile Ad-Hoc Wireless Access Networks
  26. Implementation of geocast-enhanced AODV-bis routing protocol in MANET
  27. Challenges of Secure Routing in MANETs: A Simulative Approach using AODV-SEC
  28. A Game Theoretic Approach for Securing AODV in Emergency Mobile Ad Hoc Networks
  29. New Energy Model:Prolonging the Lifetime of Ad-hoc On-Demand Distance Vector Routing Protocols (AODV)
  30. S-AODV: Sink Routing Table over AODV Routing Protocol for 6LoWPAN
  31. An enhanced routing algorithm for QoS support in wireless ad-hoc sensor networks
  32. Optimized link state routing protocol for ad hoc networks
  33. On-demand energy-efficient routing for delay-constrained service in power-controlled multihop cellular network
  34. Study on the Performance of Ad-hoc Routing Protocols on vehicles
  35. Performance Analysis of Routing Protocol in WiMAX Network
  36. Multipath and MPR based AODV
  37. Gayraud 2003, p. 18
  38. Gayraud 2003, p. 19
  39. Gayraud 2003, p. 10
  40. Gayraud 2003, p. 11
  41. Gayraud 2003, p. 15
  42. Vidéo Senslab
  43. Gayraud 2003, p. 16
  44. RFC4442
  45. Gayraud 2003, p. 17
  46. Gayraud 2003, p. 18
  47. Challenges of Secure Routing in MANETs: A Simulative Approach using AODV-SEC
  48. Stamouli 2005, p. 1
  49. aodv_kernel
  50. NIST
  51. UoBWinAODV
  52. R-AODV: Rate aware routing protocol for WiFi mesh networks
  53. A method to deliver AODV routing messages using WiMAX mesh MAC control messages in maritime wireless networks
  54. Performance Evaluation for Cross-Layer AODV Protocol in CDMA-Based Ad-Hoc Networks
  55. S-AODV: Sink Routing Table over AODV Routing Protocol for 6LoWPAN
  56. Simulation of the Routing Protocol of Mobile Ad Hoc Networks at the Rate of 4G
  57. A Static Multi-Hop Underwater Wireless Sensor Network Using RF Electromagnetic Communications

Bibliographie

Articles scientifiques

Ouvrages

Voir aussi

Liens externes

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Ad-hoc On-demand Distance Vector de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Ad-hoc On-demand Distance Vector — Der Ad hoc On demand Distance Vector Routingalgorithmus (AODV) ist ein Algorithmus zum Weiterleiten von Daten durch ein mobiles Ad hoc Netz. Das Protokoll gehört zu den topologiebasierten, reaktiven Routingverfahren, d. h. Routen zu… …   Deutsch Wikipedia

  • Ad hoc On-Demand Distance Vector Routing — Ad hoc On Demand Distance Vector (AODV) Routing is a routing protocol for mobile ad hoc networks (MANETs) and other wireless ad hoc networks. It is jointly developed in Nokia Research Center of University of California, Santa Barbara and… …   Wikipedia

  • Ad-hoc-Netz — Mesh Netzwerk mit Internet Anbindung und lokalem Radio Stream Ein Ad hoc Netz (lateinisch ad hoc, sinngemäß ‚für diesen Augenblick gemacht‘) ist ein Funknetz, das zwei oder mehr Endgeräte zu einem vermaschten Netz verbindet. Netze, die sich… …   Deutsch Wikipedia

  • List of ad-hoc routing protocols — An Ad hoc routing protocol is a convention or standard that controls how nodes come to agree which way to route packets between computing devices in a mobile ad hoc network (MANET).In ad hoc networks , nodes do not have a priori knowledge of… …   Wikipedia

  • List of ad hoc routing protocols — An ad hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network . In ad hoc networks, nodes are not familiar with the topology of their… …   Wikipedia

  • Mobiles Ad-hoc-Netz — Mesh Netzwerk mit Internet Anbindung und lokalem Radio Stream Ein Ad hoc Netz (lat. ad hoc, sinngemäß „für diesen Augenblick gemacht“) ist ein Funknetz, das zwei oder mehr Endgeräte zu einem vermaschten Netz verbindet. Netze, die sich… …   Deutsch Wikipedia

  • Mobiles Ad-hoc-Netzwerk — Mesh Netzwerk mit Internet Anbindung und lokalem Radio Stream Ein Ad hoc Netz (lat. ad hoc, sinngemäß „für diesen Augenblick gemacht“) ist ein Funknetz, das zwei oder mehr Endgeräte zu einem vermaschten Netz verbindet. Netze, die sich… …   Deutsch Wikipedia

  • Fahrzeug-Ad-hoc-Netz — Ein Fahrzeug Ad hoc Netzwerk (engl. Vehicular Ad Hoc Network, VANet) ist ein mobiles Ad hoc Netz (MANet), dessen Knoten Fahrzeuge sind. Als Knoten eines VANet werden in der Regel Kraftfahrzeuge betrachtet. Wie bei einem MANet handelt es sich um… …   Deutsch Wikipedia

  • Список протоколов маршрутизации в ad hoc сетях — содержит информацию о протоколах маршрутизации в ad hoc сетях, которые классифицируются следующим образом: проактивные, реактивные и гибридные. Проактивные OLSR TBRPF DSDV Реактивные AODV (англ. Ad hoc On Demand Distance Vector ) протокол… …   Википедия

  • AODV — Ad hoc On demand Distance Vector AODV (pour Ad hoc On Demand Distance Vector) est un protocole de routage destiné aux réseaux mobiles (en mode ad hoc). Il est à la fois capable de routage Unicast et Multicast. Il est libre de boucle, auto… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”