54
Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles Routage

  • Upload
    gale

  • View
    83

  • Download
    1

Embed Size (px)

DESCRIPTION

Les réseaux ad hoc mobiles Routage. Introduction – Qu’est-ce que les réseaux ad hoc. Caractéristiques des MANETs. Autonomes ( pas de routeurs dédiés), Liaisons radios (bande passante limitée, taux d’erreurs élevé), Topologie dynamique (mouvement des nœud, entrée en sommeil), - PowerPoint PPT Presentation

Citation preview

Page 1: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobilesRoutage

Page 2: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 2

Caractéristiques des MANETs

Autonomes (pas de routeurs dédiés), Liaisons radios (bande passante limitée, taux d’erreurs

élevé), Topologie dynamique (mouvement des nœud, entrée en

sommeil), Utilisation de batteries pour l’énergie (Problème

d’énergie), …,Sécurité physique limitée (vol),

Introduction – Qu’est-ce que les réseaux ad hoc

Page 3: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 3

Introduction – Qu’est-ce que les réseaux ad hoc

•Exemple d’application des réseaux ad-hoc :

- Recherche d’urgence et opérations de secours,

- Meetings (ou conventions) où des personnes veulent s’échanger rapidement des information,

- Opérations d'acquisition de données dans des terrains inhospitaliers,

- Réseaux locaux dans le future ?

Page 4: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 4

Limitations typiques des réseaux ad hoc• consommation d’énergie élevée• Bande passante faible• Taux d’erreur élevé• Mobilité élevée pour chaque nœud du réseau

Introduction – Qu’est-ce que les réseaux ad hoc

Page 5: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 5

Défis de Recherches

Problèmes de la couche MAC

• Fiabilité de la couche liaison ?

• QoS dans MAC? Économie de l’énergie ? Problèmes de la couche réseau

• Routage ; (QoS?) Économie de l’énergie ?

• Multicast ? Problèmes de la couche transport

• Fiabilité de bout-en-bout; Contrôle de congestion? QoS? Problèmes de la couche application : Sécurité? QoS? Interactions avec les couches; Interconnexion avec Internet;

Introduction – Qu’est-ce que les réseaux ad hoc

Page 6: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 6

Organismes de recherche

IETF MANET WG• Routage (unicast, multicast, etc.)• Routage avec QoS ?• Sécurité;• http://www.ietf.org/html.charters/manet-charter.html

Gouvernements : US, Finlande, Germany, France, …

Universités : CMU, INRIA, UCLA, Industriels : Nokia, Siemens, Eriksson, etc.

Page 7: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 7

Comment acheminer• Utiliser identificateur => adresse globale uniqu

e, ex: IP• Trois types d’acheminement

• datagramme (sans connexion), ex: UDP,TCP/IP

• circuit virtuel (avec connexion), ex: ATM

• routage par source

Routage dans le réseau Ethernet

Page 8: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 8

Routage dans le réseau Ethernet : par source

Routeur 1 Routeur 4

Routeur 3

Routeur 2

Host A

Host B

2

1

0

3

2

1

0

1

2

3

3

0

1

2

3

122

0

033

3B0

•Interface d’entrée, prochain saut, Interface de sortie

Page 9: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 9

Routeur 1 Routeur 4

Routeur 3

Routeur 2

Host A

Host B

2

1

0

3

2

1

0

1

2

3

3

0

1

2

3

0

Host C

Host D

30

3

1

B

C

D

A

Dest. Inter. de sortie

Routeur 2

Routage dans le réseau Ethernet : sans connexion

Page 10: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 10

3 (Token-ring)

1 (Ethernet)

2 (Ethernet)

Routeur 1

Routeur 2

Routeur 3

Host 1

Host 7

Host 3Host 2

Host 8

Host 4

Host 5 Host 6

Réseau 4 (point-à-point)Numéro Saut réseau prochain

1 R32 R13 Interface 14 Interface 0

Routeur2

Routage dans le réseau Ethernet : Internet

Page 11: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 11

Problème principal du Routage

Le standard (Mobile) IP a besoin d’une infrastructure• Home Agent/Foreign Agent dans le réseau fixe.

• DNS, routage etc. n’étaient pas conçus pour la mobilité.

Pas d’infrastructure dans les réseaux ad hoc• Aucun routeur par défaut n’est disponible.

• Chaque hôte (nœud) doit être capable de router les paquets.

Page 12: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 12

Vecteur distance (Distance Vector)• Compteur de sauts

Etat de lien (Link state)• Coût de lien

Route ad hoc

Routage dans le réseau Ethernet : sélection de la route

Page 13: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 13

Algorithmes classiques de routage

Vecteur de distance « Distance Vector » (RIP)• Échange périodique des tables de routage entre tous les

voisins physiques Chaque entrée de la table de routage contient la destination et le prochain routeur à traverser pour l’atteindre.

• Choix du plus court chemin dans le cas ou il y a plusieurs chemins disponibles

État de lien « Link State » (OSPF)• Chaque routeur inonde le réseau par l’état courrant de

tous les liens physiques. • Le routeur à une vue complète sur le réseau.

Page 14: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 14

Routage dans les réseaux ad hoc

Les différences entre le routage dans les réseaux Ethernet et dans les réseaux ad-hoc :• Mobilité,• Structure dynamique de topologie de réseau,• IP != localisation physique,• Chaque nœud mobile joue le rôle d’un routeur,• Liens unidirectionnels,• Limitations technologiques

Page 15: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 15

Routage dans les réseaux ad hoc

6

1

2

12

4

10

8

7

93

5

11

13

Page 16: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 16

Les algorithmes classiques dans les MANETs

Dynamique de la topologie• Changements fréquents de liens, qualité des liens,

Performances limitées des systèmes mobiles• les mises à jour périodiques des tables de routage ont

besoin de l'énergie et parfois inutiles (sans contribuer à la transmission des données d'utilisateur, les modes veille sont difficiles à réaliser).

• Les échanges des informations de routage réduisent de plus en plus la bande passante.

Problème : ces protocoles ont été conçus pour les réseaux fixes avec des changements peu fréquents et supposent typiquement des liens symétriques

Page 17: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 17

Routage dans les MANETs

Solution

- Concevoir des algorithmes spécialement pour les réseaux ad hoc

Léger (Énergie)

Optimal (précision des routes)

Scalable (mobilité / nœuds)

Multicast, sécurité, …

Page 18: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 18

Routage Ad Hoc

DSDV CGSR

Routage géographiqueRoutage plat Routage hybrides

proactif réactif

OLSR AODV

DSR

ZRP HSR … LAR GPSR …FSR

WRPADV

TORA

ABR

Page 19: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 19

Deux types de routage :• Basé-table • Basé-source initialisation (à la demande)

Routage dans les réseaux ad hoc

= Table-driven / proactif

= on-demand / reactif

Page 20: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 20

• Chaque nœud maintient une ou plusieurs tables pour stocker des information de routage

• Chaque nœud réagit aux changements de la topologie du réseau en propageant des mises à jour à travers le réseau dans le but de maintenir une vue consistante du réseau

• Diffusion de changements

Deux types de routage :• Basé table

• Basé-source initialisation (à la demande)

Routage dans les réseaux ad hoc

Page 21: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 21

Deux types de routage :• Basé-table • Basé-source initialisation (à la demande)

Routage dans les réseaux ad hoc

Page 22: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 22

• Crée les routes à la demande du nœud source

• Lorsqu’une route est établie, elle est maintenue par une procédure de maintenance jusqu’à ce que la destination devient inaccessible à travers chaque chemin depuis la source ou lorsque la route n’est plus désirée

Deux types de routage :• Basé-table • Basé-source initialisation (à la demande)

Routage dans les réseaux ad hoc

Page 23: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 23

Protocoles de routage basé-table

DSDV• (Destination-Sequenced Distance-Vector Routing)

CGSR • ( Clusterhead Gateway Switch Routing)

OLSR • (Optimized Link State Routing)

Proactifs

Page 24: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 24

DSDV(Destination-Sequenced Distance-Vector Routing)

Mécanisme de routage classique Bellman-Ford (pas de boucle)

Utilisation d’une table ( < destination, saut prochain, #sauts, seq°>)

Mises à jour périodiques diffusés dans le réseau Un paquet de mise à jour contient le nouveau seq°

incrémenté du nœud émetteur, Seq° reçu> seq° : mise à jour de l’entrée dans la table locale Seq° reçu = seq° : #sauts reçu<#sauts : mise à jour autres entrées reçues ignorées

Full dump (toute la table), plusieurs NPDU réseau Incremental (changement), entre full dump

Page 25: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 25

CGSR(Clusterhead Gateway Switch Routing )

Réseau constitué en clusters Chaque cluster est contrôlé par un cluster head CH

Tous les nœuds dans la portée de transmission du CH sont dans ce cluster élection du CH : séparation de codes entre clusters, accès canal, routage et

allocation de bande passante.

Pb. Changements fréquents de CH => performances – LLC (Least Cluster Change) :

deux CH se rencontrent (à la portée l’un de l’autre), un nœud se déconnecte de tous les CH.

Page 26: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 26

CGSR(Clusterhead Gateway Switch Routing )

Au début, utiliser l’algorithme de priorité p pour créer les clusters initiaux.

Un nœud non CH dans cluster i se déplace vers un cluster j : aucun CH ne change ni dans i ni dans j.

Un nœud non CH se déplace en dehors de son cluster et ne rentre dans aucun cluster, il devient nouveau CH.

Un CH(i) se déplace vers un autre cluster j ayant CH(j) : CH(i) ou CH(j) doit renoncer à sa position de cluster head selon p.

Nœuds qui se séparent d’un cluster doivent recalculer le groupement (clustering) selon p.

p = plus petite identité, connectivité élevée, etc.

heuristique

Page 27: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 27

CGSR (Clusterhead Gateway Switch Routing )

CGSR = DSDV + routage hiérarchique (depuis le cluster head vers la passerelle (gateway GW) pour router le

trafic depuis la source vers la destination )

nœuds GW sont des nœuds dans la portée de communication de deux ou plusieurs CH

paquet envoyé par un nœud est d’abord acheminé à son CH, ensuite acheminé vers un GW, ensuite vers un autre CH et ainsi de suite jusqu’au CH du nœud

destination.

Nœud Gateway Cluster Head

1

2

34

5

6

7

8

C1

C2

C3

Routage du nœud 1 vers le nœud 8

2

4

7

3

6

Page 28: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 28

OLSR (Optimized-LS-Routing)INRIA

Proactif Calcul périodique des routes vers toutes les destinations

Routes prêtes à la demande. (QoS) Diminue la charge supplémentaire en réaction

aux changements de topologie. Très performant dans le cas de communications

fréquentes entre plusieurs nœuds. L’information sur l’état des liens est diffusée

périodiquement dans tous le réseau. Utilisation des MPR (Optimisation)

Utilisation des liens bidirectionnels!!

Page 29: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 29

• Sous ensemble des voisins d’un nœud.• Se charge de l’acheminement du trafic et la rediffusion des messages de

contrôle.

Plus la taille de l’ensemble MPR est petite plus OLSR est optimal.• Tous les voisins de degrés 2 doivent être atteints seulement avec les

rediffusion des MPR.• Un nœud calculant le plus court chemin vers une destination ne se base que

sur ses voisins et tous les MPR des autres nœuds

OLSR est optimisé pour les réseaux denses Sinon tous les nœuds deviennent des MPR et OLSR

devient l’algorithme état de liens classique.• Le calcul de l’ensemble MPR est NP-Complet

Utilisation d’heuristiques efficaces

OLSR (Optimized-LS-Routing)NRIAMPR (MultiPoint Relay)

Page 30: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 30

Pour chaque nœud x, N1(x) voisins (bidirectionnels) de degré 1, N2(x) voisins (bidirectionnel) de degrés 2,

MPR(x) est sous ensemble de N(x). Chaque nœuds envoie la liste de ses voisins (Messages Hello).

1. Commencer par MPR(x) vide,2. Ajouter à MPR (x) les nœuds de N1(x) qui sont les seuls voisins des

nœuds de N2(x) /*Optimisation*/3. Tant que il existe des nœuds dans N2(x) non couverts par MPR(x)

faire a) Pour chaque nœud dans N1(x)-MPR(x) calculer le nombre

de nœuds qu’il couvre parmi ceux de N2(x) non encore couverts;b) Ajouter le nœud qui couvre le maximum de voisins N2(x) à

MPR(x).

OLSR (Optimized-LS-Routing)RIACalcul des MPR : heuristique

Page 31: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 31

Chaque nœud calcule son ensemble MPR Envoi un message Hello à ses voisins contenant son

ensemble MPR, Chaque voisins recevant Hello, met à jour l’ensemble des nœuds qui

l’ont choisi comme MPR (MS : MPR selectors), Chaque message Hello à un Numéro de Séquence (âge).

La mise à jour des états de liens d’un nœud x est réduite aux MPR selectors MS de x (MS(x)).

Le nœud x ne peut être joint que par ses MPR Le routage n’est rien d’autre que l’inondation périodique avec des

messages TC (Topology Control) envoyé par chaque nœud pour déclarer son ensemble MS (avec TTL=255).

Tous les nœuds qui reçoivent cette information mettent à jour leurs tables de topologie et ensuite leur table de routage.

Un numéro de Séquence MSSN pour les MS est attaché à TC pour permettre les mises à jours.

OLSR (Optimized-LS-Routing)Algorithme

Page 32: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 32

Protocoles de routage basé-source initialisation

DSR • (Dynamic Source Routing)

AODV • ( Ad Hoc On demand Distance Vector Routing)

Page 33: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 33

DSR (Dynamic Source Routing)MU

Réactif Calcul des routes à la demande

Phase de route discovery dans le cas ou aucune route n’est disponible « Délai »

Garder la trace de tous les nœuds intermédiaires pour atteindre la destination (Source Routing)

Routage Multi-chemins (Multipath) grâce à l’utilisation de source routing

Tampon mémoire « Agressif » de plusieurs routes pour les utiliser en cas de panne de route.

Pas de boucles de routage (Loopfree) grâce à source routing Utilisation de « Promiscuous mode »

N’envoyer les route_request que s’ils n’ont pas été déjà vus

Page 34: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 34

Algorithme : 2 Phases (1/2) Découverte d’une route (route discovery) Si aucune route n’est disponible d’un nœud S vers un autre

nœud D alors S inonde le réseau par route_request Utilisation de route_record pour enregistrer les nœuds intermédiaires de S à D. Les tables de routage contiennent des route_record

Chaque nœud maintient une liste de couples (initiator_adr,request_id) Éviter de traiter plusieurs fois le même message.

DSR (Dynamic Source Routing)

Page 35: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 35

Algorithme : 2 Phases (2/2) Répondre à une requête de routage (route reply) Quand un nœud reçoit un message route_request, il vérifie

1. Le couple (initiator_adr,request_id),

2. Si c’est lui la destination,

3. S’il connaît une route vers la destination

DSR (Dynamic Source Routing)

Page 36: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 36

1. S’il a déjà traité le message il ignore ce message

2. Sinon2.1 S’il ne connaît pas une route vers la destination

Met son ID dans le route_record et retransmet le message2.2 Sinon /*il connaît la destination ou une route vers la destination*/

Répond par un message route_reply2.2.1. Si les liens sont bidirectionnels alors Il utilise probablement le chemin inverse de

route_request2.2.2. Sinon Il commence un route_request vers le nœud S pour

répondre par route_reply

DSR (Dynamic Source Routing)

Page 37: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 37

Maintenance des routes (Route Maintenance) Maintenance des routes par l’envoi de paquets route_error

quand la couche liaison de donnée (DLL) rencontre un problème de transmission.

A la réception d’un paquet route_error, le nœud qui a causé l’erreur est supprimé du cache et toutes les routes qui contiennent ce nœud sont tronqués à cet endroit.

DSR (Dynamic Source Routing)

Page 38: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 38

DSR (Dynamic Source Routing)

Un exemple de propagation du paquet RREP depuis la destination 15 vers la source 1 avec le protcole DSR.

Exemple

RREP

RREQ

[1]

[1,11]

[1,11,12][1,11,12,13]

[1,11,12,13,14]

[1]

[1,2]

[1,2]

[1,2]

[1,2,3]

[1,2,10]

[1,2,6]

[1,2,10]

[1,2,6,5]

[1,2,10,9]

1 2

11

12 13

14

15

10

6

5

9

8

7

3

4

[1,2,10,9]

[1,2,6,5]

[1,2,3,4]

[1,2,10,9,8]

Un exemple de propagation du paquet RREQ depuis la source 1 vers la destination 15 avec le protcole DSR.

Page 39: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 39

AODV (Ad hoc On demand-DV)

Plusieurs chances d’être standardisé par (WG-MANET de IETF)

Établissement des routes à la demande Phase (RREQ/RREP) pour la recherche d’une nouvelle route

Gestion des pannes de route (RRER) Pas de boucle (Loop-free)

Utilisation des numéros de séquence Seq# pour chaque nœud. Chaque nœud incrémente son Seq# quand la topologie change (changement de ses voisins)

Utilisation des liens bidirectionnels

Page 40: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 40

Phase RREQ S nœud source, D nœud destination. S inonde (selon TTL) un message RREQ et active un timer pour

contrôler la durée de recherche

Chaque nœud recevant RREQ- Répondre par RREP (connaît route vers D)

ou- Rediffuser le message

* Garder trace du chemin inverse (vers S)* Éventuellement, mise à jour des seq# (pourS)

Garder le seq# le plus grand pour la destination S- Détruire le message (D-Seq#(RREQ) >D-Seq#(Nœud))

AODV (Ad hoc On demand-DV)A

Page 41: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 41

Chaque nœud incrémente son Seq# dès qu’il découvre un changement de topologie. (Le nombre de messages Hello est optimisé)- Assurer des routes fraîches- Éviter les boucles dans les chemins- Preuve « théorique » de loop-freedom

Format de la table de routage- DIP@, D-Seq#,- Next Hop IP@, Hop count D,- Last Hop Count, - List of Precursors (Pour envoyer RRER quand une route expire)- Life time,-Routing Flags- Interfaces

AODV (Ad hoc On demand-DV)A

Page 42: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 42

Options de RREQ (Expanding Ring Search)

- Utilisation du diamètre de la requête (TTL),

ttl_start .. ttl_start+threshold

- Nombre de retransmissions rreq_retries

- Garder le diamètre de la route, pour l’utiliser en cas de perte (pannes des routes).

Le diametre est gardé dans Last Hop Count

AODV (Ad hoc On demand-DV)

Page 43: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 43

RREP - Établissement du chemin - D ou autre nœud intermédiaire répond à RREQ par

- Si intermédiaire répond garde chemin inverse vers S à utiliser pour répondre à d’autres RREQ vers S.- Si S ou intermédiaire reçoivent plusieurs RREP traitement selon la pertinence de ces RREP

(hop-cnt2 < hop-cnt1 ou D-seq2 > D-seq1)

Hop-cnt DIP@ D-seq# SIP@ lifetime

AODV (Ad hoc On demand-DV)

Page 44: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 44

Maintenance des routes RERR Gestion de connectivité local

- Messages hello, hello_interval,allowed_hello_loss

Action après rebootage (Loop-free) Attendre pendant delete_period, ne répond à aucune requête de routage, répond aux paquets de données par des RRER Il ne devient pas routeur active

Il saura son seq# quand il recevera des RREQ dont il est destination.

AODV (Ad hoc On demand-DV)

Page 45: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 45

AODV (Ad hoc On demand-DV)Exemple

RREQ

[1]

[1,11]

[1,11,12][1,11,12,13]

[1,11,12,13,14]

[1]

[1,2]

[1,2]

[1,2,3]

[1,2,10]

[1,2,6]

[1,2,10]

[1,2,6,5]

[1,2,10,9]

1 2

11

12 13

14

15

10

6

5

9

8

7

3

4

[1,2,10,9]

[1,2,6,5]

[1,2,3,4]

[1,2,10,9,8]

Un exemple de création de route depuis le nœud source 1 vers le nœud destination 15.Acheminement par diffusion des messages RREQ jusqu’à la destination.

[1,2]chemin inverse

Réponses des nœuds depuis la destination jusqu’à la source : établissement du chemin inverse.

Page 46: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 46

AODV (Ad hoc On demand-DV)Exemple

1 2

11

12 13

14

15

10

6

5

9

8

7

3

4

Acheminement des réponses RREP depuis la destination en retour à la source et établissement de la route pour l’acheminement des paquets de données.

RREP

acheminement

Page 47: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 47

Routage (Multicast)

Le multicast est toujours sujet chaud même dans l'Internet;

Dans les réseaux ad hoc,sans compter les problèmes traditionnels dans l’Internet, tels que le contrôle de congestion, le routage multicast lui même est un autre grand problème;

Quelques protocoles de routage multicast: AMroute, ODMRP, AMRIS, CAMP, etc.

La maille est meilleure que l’arbre!? Diffusion directe meilleure que l’arbre et la maille ?!

Page 48: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 48

D’autres recherches dans le routage

Routage supportant la QoS; Routage économisant la consommation

d’énergie; Routage Intelligent Routage Scalable (mobilité/taille) Sécurité Méthodes d’accès au canal.

Page 49: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 49

Les domaines qui nous intéressent (pour l’instant)

Diffusion pour le transport routier (Diffusion scalable et fiable);

Interconnexion avec l’Internet, Nouvelle architecture pour les réseaux ad

hoc, Multicast et Qualité de service

Page 50: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 50

Quelques bonnes références

MANET homepage :

http://www.ietf.org/html.charters/manet-charter.html Site du gouvernement américain : http://w3.antd.nist.gov/wctg/

manet/index.html,

http://protean.itd.nrl.navy.mil/manet/manet_home.html Les universités :

http://menetou.inria.fr/olsr/ (olsr)

http://www.monarch.cs.rice.edu/ (dsr)

http://moment.cs.ucsb.edu/AODV/aodv.html (aodv)

Page 51: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 51

Recherche de route AODV

Page 52: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 52

Création de routes dans DSR

Page 53: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 53

Création de routes dans DSR (cont.)

Page 54: Les réseaux ad hoc mobiles Routage

Les réseaux ad hoc mobiles : Routage - A. Benslimane 54

Comparaisons de routage ad hoc

Protocoles basé-Table• Complexité en temps : élevé

• Philosophie de routage : plat, CGSR est hiérarchique

• Capacité de Multicast : Non

• #tables requises : élevé

Routage basé-Source Initialisation ou à la demande• Philosophie de routage : plat

• AODV supporte le multicast

• N’utilisent pas les messages de contrôle périodiques => préservent la bande passante et la puissance