Routage dans les réseaux mobiles ad hoc

1

Routage dans les réseaux mobiles ad hoc

Presenté par :H. BENKAOUHA

2

Introduction

Tous les nœuds de même niveauxPas de routeurs dans le réseauUn nœud sourceVers un nœud destinationPassant par des nœuds intermédiaires

3

Critères de Performances

Nombre de hopsBande passante disponibleStabilité des routes par rapport à la mobilitéConsommation d'énergie

4

Classes de protocoles de routage

Proactifs : DSDV OLSR TBRPF

Réactifs : DSR AODV

Hybrides : Cluster ZRP

5

Protocoles de routage proactifs (1)

Chaque nœud du réseau maintient une table de routage. Les mises à jour de la table sont obtenues par échange périodique d'informations de topologie entre les nœuds.Se basent sur la technique des plus courts chemins.

6


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. Le calcul du plus court chemin entre deux hôtes est basé sur le nombre de noeuds intermédiaires (nombre de sauts : hops)

7


On peut associer un coût représentant un facteur à minimiser : les délais relatifs de communication, taux de l'utilisation d'un lien, …2 techniquesEtat de Lien (Link State)Vecteur de Distance (Distance Vector)

8

Protocoles proactifs : Technique Link State

Chaque nœud maintient sa propre vision de la topologie du réseauMise à jour : PériodiqueS'il y a un changement d'état de liens

Chaque nœud diffuse (par inondation) l'état des liens de ses voisins à tous les nœuds du réseau.

9

Protocoles proactifs : Technique Link State

Un nœud qui reçoit les informations concernant l'état des liens : Mise à jour de sa vision de la topologie du réseau

Application d'un algorithme de calcul des chemins optimaux=> Choix du prochain noeud pour une destination

donnée

10

Protocoles proactifs : Distance Vector

Chaque hôte mobile comme un noeud de routage.Chaque noeud de routage diffuse à ses noeuds de routage voisins, sa vision des distances le séparant de tous les hôtes du réseau.

11


En se basant sur les informations reçues par tous ses voisins, chaque noeud :Fait un certain calcul pour trouver le chemin

le plus court vers n'importe quelle destination.

Tant qu'il y a un changement de la distance minimale séparant deux noeuds,

Le processus de calcul se répète

12


Généralement : Un message de mise à jour contient un vecteur d'une ou plusieurs entrées dont chaque entrée contient la distance vers une destination donnée.Cette technique est basée sur l'algorithme distribué de Bellman-Ford.

13

Protocoles de routage réactifs (1)

Etablissement d'une route uniquement lorsqu’elle est demandée.Initialisation d'un mécanisme de découverte. Les nœuds mobiles ne maintiennent pratiquement pas d’informations sur la topologie du réseau.

14


Le nœud source émet une requête de route qui est diffusée dans le réseau ad hoc jusqu’au noeud destination. Les nœuds intermédiaires sont découverts et mémorisés durant cette phase de diffusion.

15


Lorsque le nœud destination reçoit la requête, il utilise le chemininverse pour contacter le nœud source et lui transmettre les informations de routage.

16

Choix du protocole de routage (1)

Ces deux approches de routage ne présentent pas les mêmes propriétésLe choix dépend du type d’applications envisagé. Un protocole réactif permet un meilleur passage à l’échelle :

17


Il réduit de manière significative la charge de trafic dans le réseau Grâce à la non diffusion périodique des informations de topologie.Une approche proactive offre un meilleur temps de latence pour établir une route.

18


Ne nécessite aucun mécanisme de découverte au préalable.Protocoles réactifs mieux adaptés aux réseaux mobiles disposant d'une bande passante limitée.Protocoles proactifs mieux adaptés aux réseaux mobiles ayant des contraintes sur le temps.

19

Protocoles de routage hybrides

Tels que le protocole ZRP (Zone Routing Protocol) Combinant proactivité et réactivité. Ils permettent d’offrir un compromis entre charge de trafic et temps de latence.

20

Exemple de protocole proactif

OLSR (Optimized Link State Routing Protocol)Proposé en 2001 par l'équipe HIPERCOM du laboratoire de recherches INRIA Le protocole OLSR spécifié dans la RFC 3626. Optimisation des protocoles à état de liens adaptés à la nature des réseaux ad-hoc.

21

OLSR : idée de base (1)

Le concept principal est de sélectionner un sous-ensemble de nœuds appelés relais multi-points (MPRs : Multi-Point Relays)Les MPRs sont des nœuds choisis qui expédient des messages de diffusion pendant le processus d'inondation.

22

OLSR : idée de base (2)

But : Réduire la surcharge.L'information d'état de lien est produite seulement par des nœuds élus comme MPRs.un nœud MPR doit rapporter seulement des liens entre lui-même et ses sélecteurs.

23

OLSR : Principe de fonctionnement (1)

Chaque noeud réalise deux opérations principales :il détermine la liste des voisins directs en évaluant le voisinage par émission périodique des messages HELLO.HELLO uniquement entre voisins => Pas de routage pour HELLO

24


Les HELLO permettent :Découvrir l'ensemble du réseau.Transmettre l'état et le type de lien entre

l'expéditeur et chaque nœud voisin. Pour spécifier le MPR choisi par l'expéditeur.

25


Chaque MPRIl échange les information de topologie avec les autres nœuds en diffusant des messages TC de contrôle de topologie.

26


Le message TC permet au MPR de : Transmettre la liste de ses voisins qui l'ont choisi

comme MPR. Etablir les tables de routage. Pour qu'il soit diffusé sur tout le réseau.

27

Exemple de protocole réactif

AODV (Ad-hoc On-Demand Distance Vector)Routage avec Vecteur de Distance à la DemandeC.E. Perkins et E. Royer en 1999.Spécifié par la RFC 3561

28

AODV : idée de base (1)

Le protocole représente essentiellement une amélioration d'un autre algorithme : DSDV. Le protocole AODV, réduit le nombre de diffusions de messages.Création des routes lors du besoin, L'AODV est basé sur :

29


L'AODV est basé sur :L'utilisation des deux mécanismes "Découverte

de route" et "Maintenance de route" ( utilisés par un autre protocole appelé DSR ),

Routage nœud-par-nœud, Le principe des numéros de séquenceUtilisation de l'échange périodique comme pour

DSDV.

30


Le principe des numéros de séquence :A cause de la mobilité des nœuds Les routes

changent fréquemmentRisque : routes maintenues par certains nœuds

invalides.Pour maintenir la consistance des informations de

routage.Les numéros de séquence permettent d'utiliser les

routes les plus fraîches (fresh routes).

31


AODV maintient les chemins d'une façon distribuée.Une table de routage au niveau de chaque nœud de transit appartenant au chemin cherché. Une entrée de la table de routage contient essentiellement :

32

AODV : idée de base (5)1- L'adresse de la destination.2- Le nœud suivant (prochain hop).3- compteur de sauts (hops).4- Le numéro de séquence affecté au chemin par

la destination.5- Le temps d'expiration de l'entrée de la table.6- Routing flag : actif ou non.7- liste de nœuds ayant reçu la requête et qui

peuvent recevoir la réponse à la requête.

33

AODV : Principe de fonctionnement (1)

1- Découverte de la route.2- Réponse de route.3- Délivrer les données.4- Maintenance des routes.

34


AODV utilise une requête de route dans le but de créer un chemin vers une certaine destination. Un nœud diffuse une requête de route ( RREQ : Route REQuest ) si 2 conditions se vérifient :S'il aurait besoin de connaître une route vers une

certaine destination.Si une telle route n'est pas disponible.

35


C'à.d. :Destination inconnue.

OUDurée de vie du chemin a expiré.

OUChemin défaillant.

36


Un message RREQ 1-Identificateur (Adresse) de l'initiateur. 2-Numéro de séquence. 3-Identificateur de la destination. 4-Broadcast Id. 5-Le temps de vie (TTL).

37


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 nœud destination.Si le numéro de séquence n'est pas connu, la valeur nulle sera prise par défaut.

38


Quand un nœud de transit ( intermédiaire ) envoie le paquet de la requête à un voisin, il sauvegarde aussi l'identificateur du nœud à partir duquel la requête est reçue. Information utilisée pour construire le chemin inverse.=> AODV supporte seulement les liens symétriques.

39


Un paquet réponse de route doit être envoyé à la source (RREP : Route REPly)Les nœuds appartenant au chemin de retour vont modifier leurs tables de routage suivant le chemin contenu dans le paquet de réponse.Si RREP n'est pas reçu durant une certaine période (RREP_WAIT_TIME) Alors la source peut rediffuser une nouvelle requête RREQ.

40


A chaque nouvelle diffusion, le champ Broadcast ID du paquet RREQ est incrémenté.Si la requête RREQ est rediffusée un nombre de fois = RREQ_RETRIES sans la réception de réponse, un message d'erreur est délivré.

41


Maintenir des routes consistantes : Transmission périodique aux voisins du message "HELLO". Si 3 messages "HELLO" consécutifs ne sont pas reçus d'un nœud voisin, le lien est considéré défaillant. Suppression des entrées des tables de routage participantes dans le chemin actif concernées par les liens défaillants.

42


Chemin actif => passe par des entrées actives dans les tables de routage.Entrée active => utilisée par un voisin actif.Voisin actif pour une destination donnée s'il délivre au moins un paquet de donnée sans dépasser une certaine période.

43


Si défaillance d’un lien entre un nœud p avec le nœud suivant dans le chemin de routage :Le nœud p diffuse un paquet UNSOLICITED RREP,

avec une valeur de numéro de séquence égale à l'ancienne valeur du paquet RREP +1, et une valeur infinie de la distance.

UNSOLICITED RREP est diffusé aux voisins actifs, jusqu'à la source.

A sa réception, la source peut initier la découverte de routes.

44

Exemple de protocole hybride

ZRP Zone Routing Protocol

45

ZRP : idée de baseLes nœuds se trouvant dans une zone proche (à moins d’un certain nombre de sauts) : La topologie est maintenue dans une table de

routage à travers une approche proactive. Les nœuds situés en dehors de cette zone de voisinage (à plus d’un certain nombre de sauts) : Atteints par découverte de route grâce à une

approche réactive.

46

ZRP : Principe de fonctionnement (1)

Une Zone de routage est alors définie pour chaque nœud, Elle inclut les nœuds qui sont à une distance minimale du nœud en questiondistance calculée en terme de nombre de sautsdistance <= δ : Rayon de la zone.

47


ZRP définit donc deux types de protocoles : 1- L’un fonctionnant localement :IARP (IntrAzone Routing Protocol)Proactif

2- Le 2ème fonctionnant entre zones :IERP (IntErzone Routing Protocol) Réactif

48


1- IARPOffrant les routes optimales vers les destinations qui se trouvent à l’intérieur de la zone.Tout changement est répercuté uniquement à l’intérieur de la zone.

49


2- IERP S’occupe de rechercher les routes à la demande pour des destinations en dehors d’une zone.IERP suppose que chaque nœud connaît le contenu de sa zone.

50


ZRP utilise un 3ème protocole BRP (Bordercast Routing Protocol). Utilise les données de la topologie fournies par IARPDans le but : Construire liste des nœuds de périphérie.Façon de les atteindre.

51


BRP utilisé pour guider la propagation des requêtes de recherche de route de IERP dans le réseau.Si le nœud destinataire se trouve dans la zone du nœud source Alors le chemin est déjà connu.

52


Sinon, Initier une demande d’établissement de route « RREQ » vers tous les nœuds périphériques,Ces derniers vérifient, à leur tour :La destination spécifiée par la source

existe-elle dans leurs zones ?

53


Si OUI :Alors la source recevra un paquet « RREP »

contenant le chemin menant à la destination. SiNON :Les nœuds périphériques diffusent la requête de

demande à leurs propres nœuds périphériques.Ces derniers effectuent le même traitement.

Documents

Routage dans les réseaux mobiles ad hoc