Memoire Online - Les technologies sans fil: Le routage dans les réseaux ad hoc (OLSR et AODV)

Lors de la transmission d'un paquet d'une source vers une destination, il est nécessaire de faire appel à un protocole de routage qui acheminera correctement le paquet par le «meilleur » chemin. Plusieurs protocoles ont été proposés au niveau ad hoc. Afin de comprendre leurs comportement dans des réseaux mobiles, nous nous sommes intéressés donc à faire une étude théorique sur quelques protocoles, pour ce la, la première étape à faire fut celle du choix des protocoles sur lesquels se baser. Notre choix s'est porté sur AODV et OLSR. En effet. Ces protocoles montrent une meilleure qualification[4].

AODV et OLSR sont représentatifs de diverses techniques et sont les plus avancés sur la voie d'une normalisation [4]. Ils appartiennent chaqu'un à une famille, le premier, réactif, de Charles Perkins (Nokia) et Elizabeth Royer (University of California), est baptisé AODV (Ad hoc On demand Distance Vector Routing). Il utilise un mécanisme de diffusion (broadcast) dans le réseau pour découvrir les routes valides. Le second est proactif, retenu est français, de l'équipe HIPERCOM de Philippe jacquet (INRIA⁷ Rocquercourt) et s'appelle OLSR (Optimized Link State Routing Protocole). Il utilise un mécanisme qui permet de designer un sous-ensemble de son voisinage responsable de la dissémination des informations de contrôle de topologie dans les réseaux à moindre coût.

Ces deux protocoles (AODV, OLSR) font désormais l'objet d'une Request For Comment(RFC), tendis que les autres sont à des versions assez stabilités de leurs drafts.

Dans ce chapitre, nous allons présenter ces deux protocoles, en commençant par une étude détaillée sur le protocole de routage AODV et sa manière d'agir, on décrira par la suite le protocole OLSR et son principe de fonctionnement et on finira par une brève comparaison entres ces deux protocoles de routage.

3.2 Présentation du protocole de routage AODV«Ad hoc On demand Distance Vector»

AODV est un protocole de routage réactif et base sur le principe des vecteurs de distance, capable à la fois de routage unicast et multicast [11]. Il représente essentiellement une amélioration de l'algorithme proactif DSDV.

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.

En plus des messages cités avant, l'AODV utilise des paquets contrôle H ELLO qui permettent de vérifier la connectivité des routes.

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 infinie 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 maintenus par certains noeuds, deviennent invalide. Les numéros de séquence permettent d'utiliser les routes les plus nouvelles ou autrement dit les plus fraiches (fresh routes), un noeud les 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.

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 suit sur la façon dont il maintien ces routes, une fois valides.

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. Un 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 le 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 doublons, et le noeud continue le traitement en cherchant la destination dans sa table de routage : s'il possède une

route récente, a 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 (FIG 3.4).

Avant de l'envoi de paquet, le noeud intermédiaire sauvegarde l'adresse du noeud précédent et celle du noeud source à partir du quel 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).

Si la requête atteint le noeud destination, un paquet RREP est construit avec le nouveau numéro de séquence de la destination est suit la route inverse notée dans les tables (voir la FIG3.4). Le champ hop count de message route RREP est incrémenté à 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 des ces conditions est satisfaite :

- le numéro de séquence pour la destination dans le paquet de réponse est supérieure a 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.

AODV maintient les routes aussi longtemps que celles-ci sont actives, une route est considérée active tant que des paquets des données transitent périodiquement de la source a la destination selon ce chemin. Lorsque la source stoppe d'émettre des paquets des données, le lien expirera et sera effacé des tables de routage des noeuds intermédiaires. Si un lien se rompt lorsqu'une route est active, le lien est considéré défaillant. Les défaillances des liens sont, généralement, dues à la mobilité du réseau ad hoc.

Afin de détecter cette défaillance, AODV utilise les messages de contrôle « HELLO » qui permettent de vérifier la connectivité ou plutôt l'activité des routes. Un noeud détermine l'activité d'une route en écoutant périodiquement les messages « HELLO » transmis par ses voisins. Si pendant un laps de temps, trois messages « HELLO » ne sot pas reçus consécutivement, le noeud considère que le lien -vers ce voisin est cassé. Il envoi un message d'erreur (RERR) à la source et la route devient invalide.

En fait, lors de la rupture d'un lien d'une route active, AODV tente de réparer la connectivité localement en diffusant une requête de recherche de route dans le voisinage. Si cette tentative échoue, alors la route est supprimée, et nouvelle recherche de route est lancée par la source.

L'un des avantages d'AODV est l'utilisation de numéro de séquence dans les messages. Ces numéros de séquences permettent l'éviter les problèmes de boucles infinies et sont essentiels au processus de mis à jour de la table de routage.

Un autre avantage est le rappel de l'adresse IP du noeud origine dans chaque message. Ceci permet de ne pas perdre la trace du noeud à l'origine de l'envoi du message lors des différents relais.

Un inconvénient d'AODV est qu'il n'existe pas de format générique des messages. Chaque message a son propre format : RREQ, RREP, RERR.

3.3 Présentation du protocole de routage OLSR (Optimized Link State Routing)

OLSR est un protocole de routage proactif, conçu pour fonctionner dans un environnement mobile distribué sans aucune entité centrale le contrôlant et réagissant à la mobilité (réseaux Ad hoc).Il est utilisé dans les réseaux denses et peu mobiles [5].

Il représente une adaptation et une optimisation du principe de routage à état de lien pour les réseaux ad hoc. Il permet d'obtenir les routes de plus court chemin. L'optimisation tient au fait que dans un protocole à état de lien, chaque noeud déclare ses liens directs avec tous ses voisins à tout le réseau. Dans le cas d'OLSR, les noeuds ne vont déclarer qu'une sous partie de leurs voisinage par l'utilisation de relais multipoints MPR (Multipoint Relay).

Contrairement à AODV qui offre un format spécifique à chaqu'un de ses messages, le protocole OLSR définit un format général du paquet, donné sur la figure (FIG3.5).Ce format est unique pour tout les messages circulant sur le réseau.

En plus des messages d'échange de trafic de contrôle HELLO et TC (Topologie Control), le protocole OLSR propose deux autres types différents de messages : MID (Multiple Interface Declaration) et HNA (Host and Network Association)

Chaque paquet peut contenir plusieurs messages identifiés par un type. Ceci permet d'envoyer plusieurs informations à un noeud en une seule transmission. Selon la taille de MTU (Maximum Transfer Unit), un noeud peut ajouter de différents messages et les transmettre ensemble. Par conséquent différents types de messages peuvent être émis ensemble mais traités et retransmis différemment dans chaque noeud. Quand ce dernier reçoit un paquet, il examine les entêtes des messages et en détermine le type selon la valeur du champ message type. Dans OLSR, un message du control individuel est uniquement identifier par une adresse initiale (Originator address) et son numéro de séquence MSN (Message Sequence Num ber).

Le champ Originator address indique la source d'un message, par contre au champ MSN nous permet d'éviter le traitement et relayage multiple de même message pour un noeud.

Le routage des données, se fait saut par saut. Sur la base des informations reçus à partir des paquets de contrôle (HELLO et TC) envoyés par un noeud du réseau, chaque noeud / routeur calcule sa table de routage. Le protocole OLSR ne manipule pas directement les paquets de données. C'est la couche I P (réseau) qui prend en charge les paquets de données et les routes suivant les informations contenues dans sa table de routage. OL SR utilise le format standard des paquets I P pour envoyer les messages de contrôle.

Le concept des relais multipoint vise à réduire le nombre de messages de contrôle inutiles lors de l'inondation dans le réseau.

Le principe se base sur une règle (appelé règle de multipoint) : dont chaque noeud choisit une sous partie minimale de ses voisins symétriques à un saut, de tel sorte à pouvoir atteindre tout le voisinage à deux saut (les voisins des voisins).

Cet ensemble de noeuds choisi, s'appel « le relais multipoint » (MPR).Le relais multipoint porte des avantages du fait qu'il permet une diffusion optimisée en minimisant l'utilisation de la bande passante en évitant l'envoi périodique des messages de contrôle à tout le réseau. La diffusion par relais multipoint se fait différemment de la diffusion classique par inondation .Dans la diffusion classique par inondation un noeud retransmet un message s'il ne l'a pas déjà reçu. Par les relais multipoint on obtient une optimisation en ajoutant une condition : si le message n'est pas déjà reçu, et le noeud est considéré comme MPR pour le noeud dont il a reçu le message. Un noeud N1 qui ne fait pas parti de l'ensemble des MPR de noeud N2 reçoit et traite les messages envoyés par N2 mais ne les retransmette pas.

FIG3.7.a: Transmission par inondation pure FIG3.7.b : transmission avec les MPR

La figure (FIG 3.7) donne un exemple de gain en nombre de messages transmis. Le nombre de messages dans l'inondation pure (FIG 3.7.a) est de 54 messages, alors que dans le cas des Relais multipoint (FIG 3.7.b) est de 34 messages.

OLSR fournit des routes optimales en nombre de sauts, il convient pour les grandes réseaux grâce à son mécanisme de MPR, mais sans doute moins efficace pour de petite réseaux.

Les MPR d'une diffusion ne seront pas forcément les mêmes, puisque chaque noeuds sélectionne ses MPR comme bon lui semble, donc chaque noeud N a son propre ensemble d'MPR cet ensemble est dénoté MPR(N). par conséquent un noeud MPR maintient des informations sur les noeuds qui l'ont choisit comme MPR. Cet ensemble s'appel « le sélecteur de relais multipoint » (MPR selector set).

Le problème qui consiste à trouver le plus petit ensemble de MPRs est analogue au problème de la recherche d'ensemble dominant minimal dans un graphe, qui est connu pour être NP complet [5].dans OLSR, plusieurs heuristiques (le lecteur pourra trouver c'elle proposée dans RFC dans [7]) existent qui permettent de se rapprocher de l'ensemble minimal dans la majeure partie des cas.

Dans ce qui suit, on va se détailler sur le fonctionnement de protocole OLSR en commençant d'abord par la détection de voisinage en suit la sélection des relais multipoint, en parlera par la suit comment le protocole gère la topologie de réseau et on finira par ses messages MID et H NA. Pour bien comprendre le principe de fonctionnement de OL SR, pour

tout le reste de chapitre, on considère un réseau Ad hoc déployé avec 10 noeuds, chaque noeud est équipé d'une seule interface réseau (voir FIG 3.8).

Pour accomplir le choix des relais multipoint, chaque noeud doit déterminer ses voisins symétriques directs, mais vue la mobilité des réseaux Ad hoc, certaines liens peuvent devenir asymétriques, par conséquent, il faut tester tout les liens dans les deux sens avant de les considérer valides. Pour cela OLSR propose le mécanisme de détection de voisinage, ce mécanisme est assuré par l'échange périodique des messages « HELLO » qui contient des informations sur les voisins connus et l'état des liens avec ceux-ci. La fonction des messages « HELLO » est multiple. Il permet à un noeud de renseigner sa table de voisinage afin de connaitre ses voisins directs et leurs types de lien. Et comme chaque noeud diffuse ce type de message, un noeud peut acquérir des informations sur les voisins de ses voisins directs, donc il aura la topologie du réseau à deux sauts.

A base de ses informations un noeud choisit ses MPR, après leur sélection, il les déclare dans une partie de message « HELLO ». Ceci permet à un noeud de savoir quels voisins l'ont choisi comme MPR, autrement dit de construire la liste M PRset. A la réception de message « H ELLO », chaque noeud mis à jour sa table de voisinage pour sauvegarder ses voisins à un saut et leurs types de lien à savoir (symétriques, asymétriques ou MPR). La table suivante montre la table de voisinage du noeud A.

Noeuds voisins Types de lien

B Symétrique

C Symétrique

E Asymétrique

F Symétrique

Vu que dans les réseaux Ad hoc, la topologie est totalement distribuée et les noeuds peuvent se déplacer, se connecter et se déconnecter facilement du réseau. Alors, il est indispensable de vérifier à chaque fois la topologie du réseau.

Le contrôle de la topologie ne se fait que par les noeuds élus comme MPR. Ces noeuds diffusent périodiquement des messages de contrôle de la topologie TC (Topology Control).

Le message TC contient l'adresse de générateur du message, l'adresse du noeud destinataire, le numéro de séquence et la durée de vie du message. Il envoi dans ce message l'ensemble des noeuds qui ont sélectionné ce noeud comme MPR (MPR selector_set). Cette information va aider les autres noeuds à construire leur table topologique, puis leur table de routage.

Dans l'exemple de la Figure (FIG3.8), nous présenterons l'ensemble des MPR choisis par chaque noeud. Les MPR_selestor de chaque noeud élu comme MPR ainsi que la table topologique du noeud A.

Noeuds destinataire	Noeud du dernier saut	Numéro de séquence	Durée de vie
B	G	SN1	T1
C	D	SN2	T2
D	C	SN3	T3
F	G	SN4	T4
G	B	SN5	T5
H	F	SN6	T6
I	J	SN7	T7
J	D	SN8	T8
D	J	SN9	T9
G	F	SN10	T10

À chaque changement de topologie, le calcul des routes vers toutes les destinations est déclenché pour mettre à jour les tables de routage. Par ailleurs, lorsque son ensemble de voisins directs ou à deux sauts change, un noeud doit effectuer la sélection de ses M PRs à nouveau.

Puisque le réseau est dynamique et sans infrastructures centralisé d'autres noeuds peuvent se connecter et déconnecter a tout moment, ce qui provoque le changement de la topologie du réseau et les liens entre les noeuds.

Le protocole OSLR est conçu pour trouver et recalculer les routes, il offre des routes optimales (nombre de sauts minimal) entre les noeuds de réseau. Pour calculer ces routes, il est indispensable de connaitre la topologie de réseau (avoir la table topologique du réseau) et avoir la liste des voisins et leurs types de liens (voir Tab 3.1).

Une fois les routes sont trouvées, le noeud construit sa table de routage. La table de routage contient l'adresse de premier saut à suivre (R_dest_addr), adresse du noeud destinataire, le nombre de sauts qui sépare les deux noeuds ainsi que l'interface de noeuds local.

Dans la table Tab 3.3 nous allons voir la table de routage associé au noeud A de l'exemple de la Figure (FIG 3.8)

Noeuds destinataire	Noeud suivant	Nombre de sauts	Interface
B	Directe	1	IF A
C	Directe	1	IF A
D	C	2	IF A
E	Directe	1	IF A
F	Directe	1	IF A
G	B	2	IF A
G	F	2	IF A
H	F	2	IF A
I	C	4	IF A
J	C	3	IF A

Tout changement dans la table topologique ou la table de voisinage provoque automatiquement la modification de la table de routage.

Par exemple, dans la figure suivante (FIG 3.9) si le noeud D veut envoyer un message au noeud F, il a la possibilité d'emprunter deux routes, mais toujours OLSR prend la route optimale (en termes de nombre de sauts).

Ces messages sont émis que par un noeud qui a des interfaces OLSR multiples, afin d'annoncer des informations sur la configuration de ses interfaces au réseau. Un message MID contient une liste d'adresses, L'adresse I_if_addr correspond à une interface ainsi que I_main_addr est l'adresse principale du noeud émetteur. La diffusion de ces messages se fait par les relais multipoints afin de minimiser le nombre de messages circulants sur le réseau.

Ils sont émis que par un noeud qui a des interfaces non-MANET multiples, dont le but est de fournir la connectivité d'un réseau OLSR à un réseau non OLSR. Le noeud passerelle émet des messages HNA contenant une liste d'adresses des réseaux associés et de leurs masques réseau (netmasks).donc, les noeuds se trouvant dans les réseaux MANET vont construire des tuples pour tous les noeuds passerelles où chaque tuple contient :

D'après la présentation ci-dessus du protocole de routage OLSR, nous remarquons qu'il offre des fonctionnalités très intéressantes tout en recherchant des routes optimales en termes de nombre de sauts, il diminue au maximum le nombre de messages de contrôle transmis sur le réseau, en utilisant la technique de sélection des MPR. OLSR gère convenablement la topologie du réseau, en expédiant périodiquement des messages TC et il peut contrôler l'utilisation multiple des interfaces (messages MID) ainsi qu'OLSR offre la possibilité de communication entre un réseau MANET et un réseau filaire (messages HNA)

Tous ces avantages du protocole OLSR ne veut pas dire qu'il n'a pas d'inconvénients, or que le problème actuel d'OLSR est celui de la sécurité [12]. Malgré que ces dernières années beaucoup de recherches ont été faites pour améliorer sa protection contre les attaques, mais OLSR reste toujours vulnérable à certaines attaques.

OLSR et AODV bien que de nature très différentes, sont très similaires en termes de performances. Dans un réseau très mobile, avec de fréquent changement de topologie, AODV a un petit avantage sur OLSR car les routes sont mises à jours plus rapidement. OLSR doit attendre plusieurs paquets Hello perdus avant de modifier l'état du lien et envoyer des informations de mise à jour. Par contre, dans un réseau plus statique, OLSR encombre moins le réseau qu'AODV qui émet beaucoup plus de messages à chaque découverte de route. En effet dans ce cas OLSR n'émet presque pas de message de mises à jour de la topologie.

Dans un réseau très dense, OLSR charge moins le réseau qu'AODV. Dans des réseaux moyens, OLSR et AODV sont équivalent. Lors de communications courtes, OLSR à un énorme avantages sur AODV car les routes sont disponible immédiatement. Dans la plupart des cas, les messages de contrôles d'AODV sont légèrement plus nombreux que ceux d'OLSR. AODV émets d'autant plus de paquets que le réseau est grand.

OLSR est un peu supérieur à AODV car s'il est équivalent dans la plupart des réseaux, il est meilleur dans certains cas particuliers comme des réseaux denses ou des réseaux où le trafic est important et composées de nombreuses et courtes connexions (l'utilisation des réseaux actuelles est dans ce dernier cas).

Ce chapitre a été axé le fonctionnement et le comportement de chaqu'un des protocoles AODV et OLSR dans les réseaux Ad hoc et se finit par une petite comparaison entre eux, en faisant face à des avantages et inconvénients pour introduire le protocole de routage dans le chapitre suivant.

Les technologies sans fil: Le routage dans les réseaux ad hoc (OLSR et AODV)

CHAPITRE 3

Présentation des protocoles de routage