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 1 Description Technique 1.1 Principe de fonctionnement 1.2 Formats des messages 1.2.1 Message RREQ 1.2.2 Message RREP 1.2.3 Message RRER 1.2.4 Message RREP-ACK 2 Motivation des acteurs 3 Historique 4 Positionnement par rapport aux autres protocoles ad-Hoc concurents 5 AODV et la sécurité 6 Cas d'implementation 6.1 logiciel 6.2 Réseaux support 6.3 materiel 7 AODV demain 7.1 4G 8 Notes et références 8.1 Notes 8.2 Références 9 Bibliographie 9.1 Articles scientifiques 9.2 Ouvrages 10 Voir aussi 10.1 Liens externes 10.2 Articles connexes

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

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

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

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

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é

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

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

4G

Notes et références

Notes

Références

Bibliographie

Articles scientifiques

• (en) Charles E. Perkins et Elizabeth M. Royer, « Ad-hoc On-Demand Distance Vector Routing », dans [of the 2nd IEEE workshop on mobile computing systems and applications], 1999, p. 90-100 [lien DOI] 
• (en) David B. Johnson et David A. Maltz, « Dynamic source routing in ad hoc wireless networks », dans [Kluwer International Series in Engineering and Computer Science : Mobile Computing], vol. 353, 1996, p. 153-181 (ISBN 978-0-585-29603-6) [texte intégral, lien DOI] 
• (en) Marcel C. Castro et Laura Gallucio, « Opportunistic P2P Communications invDelay-Tolerant Rural Scenarios », dans [Journal on Wireless Communications and Networking], vol. 2011, 14 octobre 2010, p. 1-14 [texte intégral, lien DOI] 
• (en) Lionel Barrère, « Étude et proposition de services dans les réseaux mobiles militaires de type MANet », dans Thèse Université Bordeaux 1, 9 juillet 2009, p. 1-17 [texte intégral] 
• (en) Charles Perkins et Elizabeth Royer, « Ad hoc On-Demand Distance Vector (AODV) Routing », dans [3561], 2003, p. 1-37 [texte intégral] 
• (en) Joseph P. Macker et M Scott Corson, « Mobile Ad Hoc Networking and the IETF », dans [SIGMOBI LE Mobile Computing and Communications Review], vol. 2, n^o 2, avril 1998, p. 9-12 (ISSN 1559-1662) [texte intégral, lien DOI] 
• Valérie Gayraud et Loufti Nuaymi, « La Sécurité dans les Réseaux Sans Fil Ad Hoc », dans [sur la sécurité des technologies de l'information et des communications], 2003, p. 1-20 [texte intégral] 
• (en) Ioanna Stamouli et Patroklos G. Argyroudis, « Real-time Intrusion Detection for Ad hoc Networks », dans [IEEE International Symposium], 27 juin 2005, p. 1-7 [texte intégral, lien DOI] 

Ouvrages

Voir aussi

Liens externes

• Le réseau citoyen Belge
• (en) RFC 3561
• L'implémentation d'AODV-UU par l'université d'Uppsala (Suède)

• (en) An Internet MANET Encapsulation Protocol (IMEP) Specification

Articles connexes

• OLSR

• Portail des télécommunications