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

CHAPITRE 2

Routage dans les réseaux Ad hoc

2.1 Introduction

Le routage est une méthode d'acheminement des informations vers la bonne destination à travers un réseau de connexion donnée, il consiste à assurer une stratégie qui garantit, à n'importe quel moment, un établissement de routes qui soient correctes et efficaces entre n'importe quelle paire de noeud appartenant au réseau, ce qui assure l'échange des messages d'une manière continue. Vu les limitations des réseaux ad hoc, la construction des routes doit être faite avec un minimum de contrôle et de consommation de la bande passante.

Dans ce qui suit, nous décrirons brièvement la difficulté de routage dans les réseaux ad hoc et les différents mécanismes de routages apparus pour la résolution de ce problème.

2.2 La difficulté du routage dans les réseaux Ad hoc

De fait qu'un réseau ad hoc est un ensemble de noeuds mobiles qui sont dynamiquement et arbitrairement éparpillés d'une manière ou l'interconnexion entre les noeuds peut changer à tout moment. Il se peut qu'un hôte destination soit hors de la portée de communication d'un hôte source, ce qui nécessite l'emploi d'un routage interne par les noeuds intermédiaires afin de faire acheminer les paquets de message à la bonne destination.

En effet, la topologie évoluant constamment en fonction des mouvements des mobiles, Le problème qui se pose dans le contexte des réseaux ad hoc est l'adaptation de la méthode d'acheminement utilisée avec le grand nombre d'unités existant dans un environnement caractérisé par de modestes capacités de calcul et de sauvegarde.

D'ailleurs dans la pratique il est impossible qu'un hôte puisse garder les informations de routage concernant tous les autres noeuds, dans le cas où le réseau serait volumineux.

2.3 Les contraintes de routages dans les réseaux ad hoc

L'étude et la mise en oeuvre d'algorithmes de routage pour assurer la connexion des réseaux ad hoc au sens classique du terme (tout sommet peut atteindre tout autre ), est un problème complexe. L'environnement est dynamique et évolue donc au cours du temps, la topologie du réseau peut changer fréquemment. Il semble donc important que toute conception de protocole de routage doive étudier les problèmes suivants :

· Minimisation de la charge du réseau : l'optimisation des ressources du réseau renferme deux autres sous problèmes qui sont l'évitement des boucles de routage, et l'empêchement de la concentration du trafic autour de certains noeuds ou liens.

· Offrir un support pour pouvoir effectuer des communications multi-points fiables : Le fait que les chemins utilisés pour router les paquets de données puissent évoluer, ne doit pas avoir d'incident sur le bon acheminement des données. L'élimination d'un lien, pour cause de panne ou pour cause de mobilité devrait, idéalement, augmenter le moins possible les temps de latence.

· Assurer un routage optimal : La stratégie de routage doit créer des chemins optimaux et pouvoir prendre en compte différentes métriques de coûts (bande passante, nombre de liens, ressources du réseau,... etc.). Si la construction des chemins optimaux est un problème dur, la maintenance de tels chemins peut devenir encore plus complexe, la stratégie de routage doit assurer une maintenance efficace de routes avec le moindre coût possible.

· Le temps de latence : La qualité des temps de latence et de chemins doit augmenter dans le cas où la connectivité du réseau augmente [1].

2.4 Classification des protocoles de routage

Vue la difficulté de routage dans les réseaux ad hoc, les stratégies existantes utilisent une variété de techniques afin de résoudre ce problème. Suivant ces techniques, plusieurs classifications sont apparues, parmi lesquelles nous allons citer :

2.4.1 Routage hiérarchique ou plat :

Le premier critère utilisé pour classifier les protocoles de routage dans les réseaux ad hoc concerne le type de vision qu'ils ont du réseau et les rôles qu'ils accordent aux différents mobiles.

y' Les protocoles de routage à plat : considèrent que tous les noeuds sont égaux (FIG 2.1). La décision d'un noeud de router des paquets pour un autre dépendra de sa position. Parmes les protocoles utilisant cette technique, on cite l'AODV ( Ad hoc On Demand Distance Vector).

FIG 2.1 Routage à plat

I Les protocoles de routage hiérarchique : fonctionnent en confiant aux mobiles des rôles qui varient de l'un à l'autre. Certains noeuds sont élus et assument des fonctions particulières qui conduisent à une vision en plusieurs niveaux de la topologie du réseau. Par exemple, un mobile pourra servir de passerelle pour un certain nombre de noeuds qui se seront attachés à lui. Le routage en sera simplifié, puisqu'il se fera de passerelle à passerelle, jusqu'à celle directement attachée au destinataire. Un exemple est donné sur la figure (FIG 2.2), où le noeud N3 passe par les passerelles P1, P2 et P3 pour atteindre N7. Dans ce type de protocole, les passerelles supportent la majeure partie de la charge du routage (les mobiles qui s'y rattachent savent que si le destinataire n'est pas dans leur voisinage direct, il suffit d'envoyer à la passerelle qui se débrouillera) [6]. ]. Un exemple de protocole utilisant cette stratégie est l' OLSR (Optimized Link State Routing)

FIG 2.2 Routage Hiérarchique

2.4.2 Le routage à la source et le routage saut par saut :

y' Le routage à la source : le routage à la source ou « source routing » consiste à indiquer dans le paquet routé l'intégralité du chemin que devra suivre le paquet pour atteindre sa destination. L'entête de paquet va donc contenir la liste des différents noeuds relayeur vers la destination. Le protocole le plus connu basant sur cette classe est : DSR³.

y' Le routage saut par saut : le routage saut par saut ou «hop by hop» consiste à donner uniquement à un paquet l'adresse du prochain noeud vers la destination. AODV fait partie des protocoles qui utilisent cette technique.

2.4.3 Etat de lien et Vecteur de distance :

Autres classification, hérité du monde filaire, est possible pour les protocoles de routage : les protocoles basé sur l'état des liens et se basé sur le vecteur de distance. Les deux méthodes exigent une mise à jour périodique des données de routage qui doivent être diffusées par les différents noeuds de routage du réseau. Les algorithmes de routage basés sur ces deux méthodes, utilisent la même technique qui est la technique des plus courts chemins, et permettent à un hôte donné, de trouver le prochain hôte pour atteindre la destination en utilisant le trajet le plus court existant dans le réseau.

y' Les protocoles basés sur l'état de lien : La famille des protocoles à état de liens se base sur les informations rassemblées sur l'état des liens dans le réseau. Ces

³Dynamic Source Routing

informations sont disséminées dans le réseau périodiquement ce qui permet ainsi aux noeuds de construire une carte complète du réseau. Un noeud qui reçoit les informations concernant l'état des liens, met à jour sa vision de la topologie du réseau et applique un algorithme de calcul des chemins optimaux afin de choisir le noeud suivant pour une destination donnée. En générale ces algorithmes se basent sur le principe de l'algorithme de Djikstra [8] pour calculer les chemins les plus courts entre un noeud source et les autres noeuds du réseau. . Les principaux protocoles de routage dans les réseaux ad hoc qui appartiennent à cette classe sont les suivants : TORA⁴ , OLSR et TBRPF⁵.

y' Les protocoles basés sur le vecteur de distance : Les protocoles à vecteur de distance se basent sur un échange, entre voisins, des informations de distances des destinations connues. Chaque noeud envoie à ses voisins la liste des destinations qui lui sont accessibles et le coût correspondant. Le noeud récepteur met à jour sa liste locale des destinations avec les coûts minimums. Le processus de calcul se répète, s'il y a un changement de la distance minimale séparant deux noeuds, et cela jusqu'à ce que le réseau atteigne un état stable. Les calcules des routes se basé sur le principe de l'algorithme distribué de Bellman-Ford [9] (DBF). les protocoles de routage basés sur le vecteur de distance les plus connus pour les réseaux ad hoc sont : DSR, DSDV⁶ et AODV.

2.4.4 L'inondation :

L'inondation ou la diffusion pure, consiste à répéter un message dans tout les réseaux .Un noeud qui initie l'inondation envoie le paquet à tous ses voisins directe, de même si un noeud quelconque de réseau reçoit le paquet pour la première fois, il le rediffuse à tous les voisins, Ainsi de proche en proche le paquet inonde le réseau (FIG 2.3).

FIG 2.3 Le mécanisme d'inondation

⁴Temparally- Ordered Routing Algorithm.

⁵Topology Dissemi nation Based On Reverse Path Forwardi ng. ⁶Desti nation-Sequenced DistanceVector.

Notons que les noeuds peuvent être anienes appliques (durant l'inondation) certain traitement de contrôle dans le but d'éviter certains problèmes, tel que le bouclage et la duplication des messages, Le mécanisme d'inondation est utilisé généralement dans la première phase du routage plus exactement dans la procédure de découverte des routes, et cela dans le cas où le noeud source ne connaît pas la localisation exacte de la destination.

2.4.5 Le concept de groupe :

Dans la communication de groupe, les messages sont transmis à des entités abstraites ou groupes, les émetteurs n'ont pas besoin de connaître les membres du groupe destinataire. La gestion des membres d'un groupe permet à un élément de se joindre à un groupe, de quitter ce groupe, se déplacer ailleurs puis rejoindre le même groupe. C'est en ce sens que la communication de groupe assure une indépendance de la localisation, ce qui la rend parfaitement basées sur les groupe. Le concept de groupe facilite les taches de la gestion du routage (telles que les transmissions des paquets, l'allocation de la bande passante etc.) et cela en décomposant le réseau en un ensemble de groupes connecté.

FIG 2.4 La décomposition du réseau en groupe 2.4.6 Protocoles uniformes et non-uniformes :

Certains protocoles de routage n'utilisent pas tous les noeuds d'un réseau pour faire transiter les messages, au contraire ils en sélectionnent certains, en fonction du voisinage ou pour former des cellules. Ces protocoles sont dits non-uniformes. Ceux qui utilisent tous les noeuds du réseau capables de router sont appelés protocoles uniformes. [1]

2.4.7 La classification de MANET :

C'est la classification qui nous intéresse et qu'on maintient pour la suite de ce chapitre. Suivant la manière de création et de maintenance de routes lors de l'acheminement

des données, les protocoles de routage peuvent être séparés en : Proactif, Réactif et Hybride.

2.4.7.1 Les protocoles de routage proactifs :

Les protocoles de routage proactifs essaient de maintenir les meilleurs chemins existants vers toutes les destinations possibles (qui peuvent représenter l'ensemble de tous les noeuds du réseau) au niveau de chaque noeud du réseau, Les routes sont sauvegardées même si elles ne sont pas utilisées. La sauvegarde permanente des chemins de routage, est assurée par un échange continu des messages de mise à jour des chemins, Le plus abouti de ces protocoles est OLSR.

Avantages et les inconvénients des protocoles proactifs :

Avec un protocole proactif, les routes sont disponibles immédiatement, ainsi l'avantage d'un tel protocole est le gain de temps lors d'une demande de route. Le problème est que, les changement de routes peuvent être plus fréquents que la demande de la route et le trafic induit par les messages de contrôle et de mise à jour des tables de routage peut être important et partiellement inutile, ce qui gaspille la capacité du réseau sans fi l. De plus, la taille des tables de routage croit linéairement en fonction du nombre de noeud.

De ce fait, un nouvel type de protocole a apparu, il s'agit des protocoles de routage réactifs.

2.4.7.2 Les protocoles de routage réactifs :

Les protocoles de routage réactifs (dits aussi: protocoles de routage à la demande), représentent les protocoles les plus récents proposés dans le but d'assurer le service du routage dans les réseaux sans fils.

La majorité des solutions proposée pour résoudre le problème de routage dans les réseaux ad hoc, et qui sont évaluées actuellement par le groupe de travail MANET (Mobile Ad Hoc Networking working Groupe) de l'IETF (Internet Engineering Task Force), appartiennent à cette classe de protocoles de routage [2].

Les protocoles de routage appartenant à cette catégorie, créent et maintiennent les routes selon les besoins. Lorsque le réseau a besoin d'une route, une procédure de découverte globale de routes est lancée, et cela dans le but d'obtenir une information. Actuellement, le plus connu de ces protocoles est AODV.

Avantages et les inconvénients des protocoles réactifs:

A l'opposé des protocoles proactifs, dans le cas d'un protocole réactif, aucun message de contrôle ne charge le réseau pour des routes inutilisées ce qui permet de ne pas gaspiller les ressources du réseau. Mais la mise en place d'une route par inondation peut être coûteuse et provoquer des délais importants avant l'ouverture de la route et les retards dépassent bien souvent les délais moyens admis par les logiciels, aboutissant à une impossibilité de se connecter alors que le destinataire est bien là.

De ce fait, un nouvel type de protocole a apparu, il s'agit des protocoles de routage hybrides.

2.4.7.3 Les protocoles de routage hybrides :

Dans ce type de protocole, on peut garder la connaissance locale de la topologie jusqu'à un nombre prédéfini- a priori petit- de sauts par un échange périodique de trame de contrôle, autrement dit par une technique proactive. Les routes vers des noeuds plus lointains sont obtenues par schéma réactif, c'est-à-dire par l'utilisation de paquets de requête en diffusion [10]. Un exemple de protocoles appartenant à cette famille est DSR (Dynamic Source Routing), qui est réactif à la base mais qui peut être optimisé s'il adopte un comportement proactif.un autre exemple est le protocole ZRP (Zone Routinier Protocol).

Avantages et inconvénient des protocoles hybrides :

Le protocole hybride est un protocole qui se veut comme une solution mettant en commun les avantages des deux approches précédentes en utilisant une notion de découpe du réseau.

Cependant, il rassemble toujours quelques inconvénients des deux approches proactives et réactives.

2.5 Conclusion

Dans ce chapitre nous avons abordé la notion et les problèmes de routage dans les réseaux Ad hoc.

Comme nous avons vu, le problème de routage est loin d'être évident dans cet environnement,
où ce dernier impose de nouvelles limitations par rapport aux environnements classiques. Les

stratégies de routage doivent tenir compte des changements fréquents de la topologie, de la consommation de la bande passante qui est limitée, ainsi d'autres facteurs.

Finalement, nous avons présenté vue classification de protocole de routage dans les environnements mobiles, avec quelques exemples pour les protocoles de routage proactif et réactif qui ont été conçu pour les réseaux Ad hoc,

Dans le chapitre suivant nous allons se détailler sur le fonctionnement de deux protocoles qui sont les plus avancés sur la voie d'une normalisation [4]. AODV et OLSR font l'objet de chapitre suivant.