Qualité de Service dans les Réseaux Mobiles Ad Hoc (Quality of Service in Mobile Ad Hoc Networks )

8/8/2019 Qualit de Service dans les Rseaux Mobiles Ad Hoc (Quality of Service in Mobile Ad Hoc Networks )

1/50

1

Qualit de Service dans les

Rseaux Mobiles Ad

HocNadir BOUCHAMADivision Thorie & Ingnierie des Systmes Informatiques (DTISI)[email protected]

Web Page:http://nadirbouchama.webs.com/Aboutme.htm

Centre de Recherche sur lInformation Scientifique & Technique
mailto:[email protected]://nadirbouchama.webs.com/Aboutme.htmhttp://nadirbouchama.webs.com/Aboutme.htmmailto:[email protected]


2/50

2

Nadir BOUCHAMA, Qualit de Service dans lesRseaux Mobiles Ad Hoc. Confrence donne loccasion du 25 ime Anniversaire du CERIST. 08 juin2010. Ben Aknoun, Algrie


3/50

325 ieme Anniversaire du CERIST

Plan de lExpos..

Rseaux Mobiles Ad Hoc : Caractristiques & ApplicationsQualit de Service dans les Rseaux Mobiles Ad HocApproches pour offrir la QoS: Taxonomie et CritiquesNotions de soft QoS, hard QoS, pseudo-hard QoSRoutage avec QoS dans les MANETsRoutage avec contrainte de dlai dans AODVModles de QoS dans les MANETsConclusion Gnrale


4/50

425 ieme Anniversaire du CERIST25 ieme Anniversaire du CERIST

Rseaux mobiles ad hoc (MANET)

GW

InternetRseaux

Mobiles Ad hocRseaux

MESHRseaux de

capteurs

Rseaux ad hoc

Ad hoc : locution latine Pour cela (LAROUSSE) Form dans un but prcis (WIKIPEDIA).


5/50


Liens sans filsCanal sujet aux interfrences et aux erreursUne topologie dynamiqueRessources limites et volatilesEx: bande passante, nergie, mmoire, CPU

Vulnrabilit aux attaques

Caractristiques des rseaux mobiles ad hoc


6/50


Domaines dapplication

Militaire Gestiondecatastrophes

AccsInternet(backhauling)

VANETS(VehicularAd hocNetworks)


7/50725 ieme Anniversaire du CERIST

InternetCentre de

Commande

CERIST

Scnario dapplication dans le cas de catastrophes

Backbone Mesh


8/508


Revers de la mdaille: plus de dfis

R o u t a g e e f f i c a c e

Gestion de la mobilit

Contrle de flux

Scalabilit

quit

S c u r i t

conomie dnergie

Qualit de Service(Quality of Service

Auto-configuration


9/509


Qualit de Service ?

Le terme Qualit de Service est souvent ambigu Plusieurs dfinitions existent dans la littrature

Le sens de chaque dfinition dpend de faon trs troite du

contexte dutilisationCependant, deux dfinitions officielles sontlargement cites:

Dfinition donne dans le RFC 2386 de lIETF (Internetengineering Task Force)

Dfinition donne dans la recommandation E.800 de lITU

(International Telecommunications Union)


10/5010


Qualit de Service ?

Comme dfinie dans le RFC 2386 , Ensemble de besoins assurer par le rseau

pour le transport dun trafic dune source unedestination. Ces besoins peuvent tre traduitsen un ensemble dattributs pr-spcifis etmesurables en terme de :

Dlai de bout en boutVariance de dlai (gigue)Bande passante :.Taux de Perte de paquets

Ces deux dfinitions ne sont pas adquates pour lesrseaux mobiles ad hocLa Qualit de Service dans les rseaux mobiles ad hoc veut dire fournirdes paramtres afin dadapter les applications la qualit du rseau.

Objectif principal: OPTIMISER lutilisation des ressources

Recommandation E.800 du CCITT :

Effet global des performances duservice qui dtermine le degrde satisfaction dun utilisateur du service.


11/5011


Motivation

Au dbut des rseaux sans fils :Le premier souci est de permettre la connectivitLe principe utilis est le BEST EFFORT cest--dire AU MIEUXAucune garantie de livraison des donnes SEND AND PRAY

Mais.pour certains applications ce service nest pas du tout suffisant

Exemple:Applications multimdias, tlphonie, jeux, applications critiques,communications dans un champs de bataille, etc.

La QoS nest pas une OPTION mais une NECESSIT pourpermettre dattirer surtout lattention des INDUSTRIELS


12/5012


Exemple dexigences en QoS

Source :


13/5013


Obstacles dans les rseaux ad hoc

La topologie du rseau change de faon dynamiqueInformation dtat souvent imprciseRessources disperses et limites (Ex: mmoire)Ressources dnergie puisables (batterie ou cellulessolaires)

Nuds des fois htrognesMdium non scuris (des intrus peuvent violer lesgaranties en QoS)Erreurs du canal


14/50


Complexit

Qualit de service dans les MANETs = Fournir unefonctionnalit complexe dans un environnement trsdynamique o les ressources sont rares.

Solution: Deux approches classiques:

Sur-dimensionnement

Ingnierie de trafic


15/50


Analogie avec le trafic routier

Ingnierie de traficsurdimensionnement


16/50


Sur-Dimensionnement ( over-dimensioning )

Avantages:Facile et peut se faire de faon graduelle;Aucun mcanisme de QoS nest ncessaire;

Inconvnients:Peut tre trs coteux pour le dploiement et la mise jour;Difficile prdire les besoins futurs du trafic;

Ne peut pas offrir des garanties sur le dlais;Dans la plupart des cas, il sagit dun dplacement du problme ;Perte de ressources (rseau sous-utilis);Pour un rseau mobile ad hoc les ressources sont rares etvolatiles;La bande de frquence est trs limite

Principe :Agir sur les RESSOURCES(solution matrielle) Approvisionnerle rseau avec suffisamment de ressources si besoin

est

P R O H

I B I T I F


17/50


Ingnierie de trafic ( Traffic engineering )

PrincipeAgir sur le TRAFIC (solution logicielle )

Utiliser des mcanismes de contrle et de priorit pour le trafic

Avantages:Non coteuse;Utilisation rationnelle des ressources ;

Inconvnients:Complexe implmenter

Problme de passage lchelle(scalability)


18/50


Taxonomies..

CoucheMAC

Protocolesdesignalisatio

n

Routageavec QoS

[WuH99] K. Wu and J. Harms, QoS Support in Mobile Ad Hoc Networks. Crossing Boundaries-the GSA Journal of University of Alberta, Volume 1, n 1. pages 92- 106. Novembre 2001

Classification la plus connue et la plus cite:

Modlesde QoS

Qualit de Servicedans les Rseaux Ad Hoc


19/50


Critiques

Taxonomie critique notamment dans:

[Chaudet2006] Claude Chaudet, Isabelle Gurin Lassous, - tat des lieux sur la qualit de servicedans les rseaux ad hoc - Invited paper, in 'Colloque Francophone sur l'Ingnierie des Protocoles''- November 2006 - Tozeur, Tunisia.

Raisons ?

Impossible de classifier les solutions existantes selon cettetaxonomie;

Pourquoi sparer la signalisation et le QoS routing alors quilssont souvent complmentaires; Un bon modle de QoS est souvent construit partir deplusieurs blocs de base


20/50


Taxonomie selon le niveau de QoS

Niveau Dfinition Autres nomsExampledapplications

Difficult

Best Effort (BE) le rseau envoie les paquets sans aucunegarantie.

send and pray courrier lectronique,transfert de fichiers,

+

QoS relche(soft QoS)

la garantie de service estofferte avec une

probabilit. Il peut y avoir des priodes transitoires o la QoS nest pasgarantie.

QoS statistique,Mieux que le best

effort,QoS qualitative,QoS relative

voix sur IP, ++

QoS pseudoferme

(Pseudo HardQoS)

les garanties de QoS sontde type ferme, sauf encas de fluctuations ducanal radio ou dechangement de

topologie.

communications militaires; +++

QoS ferme(hard QoS)

si les exigences ne sont pas satisfaites, le servicenest pas du tout fourniTOUT ou RIEN

QoS dterministe,service garanti,QoS quantitative,QoS absolue

- contrle de traficarien,

- chirurgie distance,- contrle dun racteur

nuclaire , etc.

impossible

Niv

eau deQoS


21/50


Routage avec QoS

dansLes MANETs

Obj if d R Q S


22/50


Objectifs du Routage avec QoS

Les TROIS objectifs principaux du routage avec QoS sont lessuivants:

1. Dterminer dynamiquement un chemin rpondant auxexigences de QoS entre une source et une destination ;

2. Optimiser les ressources du rseau (load balancing);3. Permettre une dgradation gracieuse (graceful

degradation) des performances du rseauhttp://www.ietf.org/rfc/rfc2386.txt


23/50


Exemple de Routage avec QoS

Chemin satisfaisant la QoS

S

B C

D

E F

D

2

3

4

2

5

6

44

3

Plus court chemin

D

S Source

Destination

Exemple:Une source S veut communiquer avec une destination D etdemande une QoS en bande passante de Bw=4

Besoin en QoS: BW4


24/50


Positionnement

Network requirements Application requirements


25/50


Composantes du routage avec QoS ?

Le routage avec QoS ncessite deux entits:

Protocole de routage (algorithme distribu): rcolte etdistribution des information sur les ressources;

Algorithme de routage (algorithme local) qui sintresse larecherche dun chemin faisable qui vrifie la QoS

NP-Complet si le nombre de mtriques additives 2Utiliser heuristiques

C t i t l d


26/50


Comment concevoir un nouveau protocole deroutage avec QoS

Deux approches principales:Concevoir le nouveau from scratch

Prendre un protocole existant (ex: AODV, OLSR) et ajouter desbriques de bases pour le rendre sensible la QoS selon la mtriquechoisie

Avantage majeur: facilit

Exemple: AODV-D ( AODV with delay constraints )(Travail avec un tudiant en PFE (UMMTO))

Extension du protocole AODVMtrique: dlaiEstimation du dlai local chaque nudLe dlai est une mtrique ADDITIVE :

Dlai de bout en bout = Dlais un saut

S D


27/50


21/07/11 27

Principe du protocole AODV AODV: Ad hoc On Demand Vector Distance Routing protocol Protocol ractif

IETF RFC 3561. Juillet 2003

A hi i d AODV D


28/50


MAC

Architecture synoptique de AODV-D

Estimation du dlai MACLLC

Physique

Prsentation

SessionTransport

RseauAODV

Routageavec QoS

Besoinsen QoSApplicatio

n

CAC


29/50


Estimation du dlai de mise en file au niveau MAC

Question principale:Quel modle de files dattente utiliser pour estimer le dlai au niveau du 802.11 ?

Recherche Bibliographique:

M/MMGI/1/KOzdemir et al 2004

M/G/1 Meraihi et al, 2004 Ph.D Thesis

M/G/1/KOzdemir et al 2004

M/M/1/KChikh Sarr, 2007 Ph.D Thesis

G/G/1Bisnik et al 2009

File M/M/1/K


30/50


File M/M/1/K

Nombre de clients dans lafile

Taux dutilisation duserveur

Temps de sjour dans le systme

L'arrive de paquet suit une loi exponentielle de paramtre Le taux de service suit galement une loi exponentielle de paramtre La taille de la file d'attente est limite par la valeur K.

La politique dordonnancement est FIFO (Premier Arriv Premier Servi)

Fil M/M/1/K ( it )


31/50


File M/M/1/K (suite)

Nombre moyen de clients dans le systme

Comme la somme est gale au temps de servicealors:

Do:

?

(Loi de Little)

Estimation du dlai moyen de transmission


32/50


Estimation du dlai moyen de transmission

Soit p la probabilit de collision sur un lien.La probabilit de russite de transmission au premier envoi est donc 1- p

La probabilit de russite de transmission au 2ime envoi est p .(1- p)

Aprs C tentatives de transmission choues, la trame est limine(Pour le 802.11 C =7 )

Soit X la variable alatoire qui compte le nombre de tentatives pour unetransmission russie dune trame

Nombre moyen de retransmissions pour une trame donne:

l i d i i ( i fi )


33/50


Dlai moyen de transmission (suite et fin)

Sarr a galement calcul le backoff moyen:

Enfin, on obtient:

O:

Temps consomm dans une collision Temps de transmission russie dun paquet de taille m laidedu 802.11

E t i d q t d t l


34/50

3425 ieme Anniversaire du CERIST21/07/11 34

TYPE J | R | G | D |U RESERVED HOP COUNT

Bande passantedsire

Dlai maxdemand

Dlai un sautcalcul

RREQ ID

Destination IP Address

Destination Sequence Number

Originator IP AddressOriginator Sequence Number

TYPE R | A PREFIX SZ HOP COUNT

Destination IP AddressDestination Sequence Number

Originator IP Address

Lifetime

Probabilit de collision

Extension des paquets de contrle

Echange dinformation


35/50


Echange d information

Les nuds changent des messages HELLO chaque intervalle detemps secondesCes messages HELLO contient un information supplmentaire: metaux doccupation du canalLa valeur du paramtre est cruciale :

grande : stabilit des rsultats mais mauvais rsultats en cas demobilit

petite : trop doverhead et de calcul mais bonne raction lamobilitLes auteurs proposent: = 1 seconde

Chaque nud estime le taux doccupation du canal son niveau etenvoie linformation dans le paquet HELLO

La taux doccupation du canal au niveau dun nud est donn par:(Ts + Tr ) /

S i d i l i


36/50


21/07/11 36

AODV-DDlai 150

AODVPlus court

chemin

Scnario de simulation

Rsultats de simulation (NS 2)


37/50


21/07/11 37

Rsultats de simulation (NS-2)Dlai de bout en bout


38/50


Modles de QoS

dansLes MANETs

M dl d Q S


39/50


Modles de QoSModle de QoS

Un modle dfinitgnralement les blocs debase dune solution

donne :Contrle dadmissionpolitique dordonnancementcontrle de congestion,signalisation,routage avec QoSLissage de trafic, etc

Dfinir QUI FAIT QUOI ?Interaction ?

Aspect architectural

Question Principale


40/50


Question Principale

Les deux modles classiques IntServ et DiffServsont-ils applicables aux rseaux mobiles ad hoc ?

MOTIVATION:Pourquoi rinventer la roue et inventer des modles

ex nihilo alors que deux modles existent dj ?Prendre en considration la possibilit de connexion Internet Interoprabilit avec IntServ et DiffServclassiques

Faut-il une volution ou une

INTERNET

Passerelle(gateway)

IntServ (Integrated services)


41/50


IntServ (Integrated services)

Emulation de circuits; Mcanisme de bout en bout; mcanisme de QoS par flux ; Utilise le protocole de signalisationRSVP

Pour MANETS ?


42/50


Pour MANETS ?

AVANTAGES:Fournit une bonne QoS;Zro paquets perdus

INCONVENIENTS:

Ncessite des informations exactes sur ltat des liens, chose quiest difficile dans le contexte des rseaux mobiles ad hoc;

Gnre beaucoup doverhead;Complexit au niveau du cur du rseau ;Nest pas pratique pour les flux de courte dure;

Scalabilit

DiffServ (Differentiated Services)


43/50


DiffServ (Differentiated Services)

Rsoudre le problme de scalabilit par deux faons:Remplacer le principe par flux par un principe par agrgats;La complexit dans les nuds du coeur est dplace versles quipements aux extrmits;

Nudinterne

Nuddentre

Nudde sortie


44/50


AVANTAGESPlus scalable que IntServModle lger dans les nuds du rseau plus facile dployerPeut fournir des fois une bonne QoS

INCONVENIENTS:Ne signale pas la congestion de faon expliciteQuand la topologie du rseaux change les rles des noeuds

changent galementDifficile de ngocier dynamiquement un profil de trafic

PourMANETS ?

INSIGNIA


45/50


INSIGNIAhttp://comet.columbia.edu/insignia/

Ides principales de INSIGNIA:Premier protocole de signalisation pour MANETSInspir de IntServfournir un modle de QoS de bout en bout

Un modle de QoS adaptif

SWAN (Stateless Wireless Ad hoc Networks)
http://comet.columbia.edu/insignia/http://comet.columbia.edu/insignia/


46/50


SWAN (Stateless Wireless Ad hoc Networks)http://comet.columbia.edu/swan/overview.htm

Soft QoSInspir de DiffServNe pas garder les informations sur ltat2 classe de trafic: best effort et real time Dfinit un contrle dadmission pour accepter/rejeter unenouvelle connexion

FQMM (Flexible QoS Model for MANETs)
http://comet.columbia.edu/swan/overview.htmlhttp://comet.columbia.edu/swan/overview.html


47/50


Q ( e b e QoS ode o s)

Modle hybride : IntServ + DiffServ Conu pour les MANETS de taille moyenne (jusqu 50 noeuds) Flexible

Rfrences bibliographiques pertinentes


48/50


g p q p

G-S. Ahn, L-H. Sun, A. Veres, and A. T. Campbell, SWAN: ServiceDifferentiation in stateless wireless Ad hoc Networks , INFOCOM, 2002.

D. Awduche, A. Elwalid A. Chiu, I. Widjaja, and X. Xiao, RFC3272: Overviewand Principles of Internet Traffic Engineering , 2002.

C. Chaudet and I. Gurin-Lassous, Etat des lieux sur la Qualit de Servicedans les Rseaux Ad hoc , Colloque Francophone sur lIngnierie desProtocoles (CFIP), Tozeur. Tunisia, 2006.

L. Chen and W. Heinzelman, A survey of routing protocols that support QoSin mobile ad hoc networks , IEEE Network 21 (2007), no.6, 3038.

I. Chlamtac, M. Conti, and J. J.-N. Liu, Mobile ad hoc networking:imperatives and challenges , Ad Hoc Networks 1 (2003), no. 1, 1364.

L. Hanzo and R. Tafazolli, A survey of QOS Routing Solutions for Mobile Adhoc Networks , IEEE Communications Surveys and Tutorials 9 (2007), no. 1-4,5070.

P. Mohapatra, P. J.Li, and C.Gui, QoS in Mobile Ad hoc Networks , IEEEWireless Communications 10 (2003), no. 3, 44 52.

T. Reddy, I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, Quality of service Provisioning in Ad hoc Wireless Networks: a Survey of Issues andSolutions., Ad Hoc Networks 4 (2006), no. 1, 83124.

Conclusion gnrale


49/50


Conclusion gnrale

La flexibilit des rseaux mobiles ad hoc les rend trs utiles dans plusieurs domaines;

Les caractristiques inhrentes aux rseaux mobiles ad hoc rendent lapprovisionnement de laQoS trs complexe; Vu la volatilitdes ressources, on ne peut pas offrir une hard QoS dans les rseaux ad hoc;La soft QoS (mieux que le best effort) peut tre suffisantedans certains casUn exemple dun protocole de routage soft QoS a t prsent (lestimation du dlai est basesur le modle M/M/1/K);IntServ et DiffServ ne sont pas directement applicables pour les rseaux mobiles ad hoc;DiffServ est mieux adapt aux rseaux mobiles ad hoc que IntServ.


50/50

All your feedback iswelcome to:

[email protected]@gmail.com

Documents

Qualité de Service dans les Réseaux Mobiles Ad Hoc (Quality of Service in Mobile Ad Hoc Networks )