1 Qualité de Service dans les Réseaux Mobiles Ad Hoc Nadir BOUCHAMA Division Théorie & Ingénierie des Systèmes Informatiques (DTISI) [email protected]

1

Qualité de Service dans les

Réseaux Mobiles Ad Hoc

Nadir BOUCHAMADivision Théorie & Ingénierie des Systèmes Informatiques (DTISI)

[email protected]

Centre de Recherche sur l’Information Scientifique & Technique

25 ieme Anniversaire du CERIST2

Plan de l’Exposé..

Réseaux Mobiles Ad Hoc : Définition, ApplicationsQualité de Service dans les Réseaux 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 délai dans AODVModèles de QoS dans les MANETsConclusion générale


Réseaux mobiles ad hoc (MANET)

GW

InternetRéseaux

Mobiles Ad hocRéseaux

MESHRéseaux de

capteurs

Réseaux ad hoc

Ad hoc : locution latine• Pour cela (LAROUSSE)• Formé dans un but précis (WIKIPEDIA).


Liens sans filsCanal sujet aux interférences et aux erreursUne topologie dynamiqueRessources limitées et volatiles Ex: bande passante, énergie, mémoire, CPUVulnérabilité aux attaques

Caractéristiques des réseaux mobiles ad hoc


Domaines d’application

Militaire Gestion de catastrophes

Accès Internet (backhauling)

VANETS (Vehicular Ad hoc Networks)


InternetCentre de

CommandeCERIST

Scénario d’application dans le cas de catastrophes


Revers de la médaille: plus de défis…

Routage efficace

Gestion de la mobilité

Contrôle de flux

ScalabilitéÉquité

Sécurité

Économie d’énergie

Qualité de Service (Quality of Service)

Auto-configuration


Qualité de Service ?

• Le terme Qualité de Service est souvent ambigu

• Plusieurs définitions existent dans la littérature

• Le sens de chaque définition dépend de façon très étroite du contexte d’utilisation

• Cependant, deux définitions sont largement Définition donnée dans le RFC 2386 de l’IETF (Internet engineering Task Force) Définition donnée dans la recommandation E.800 de l’ITU (International Telecommunications Union)


Qualité de Service ?

Comme définie dans le RFC 2386,« Ensemble de besoins à assurer par le réseau pour le transport d’un trafic d’une source à une destination. Ces besoins peuvent être traduits en un ensemble d’attributs pré-spécifiés et mesurables en terme de : Délai de bout en bout Variance de délai (gigue) Bande passante :. Taux de Perte de paquets »

Ces deux définitions ne sont pas adéquates pour les réseaux mobiles ad hoc

La Qualité de Service dans les réseaux mobiles ad hoc veut dire fournir des paramètres afin d’adapter les applications à la “qualité “ du réseau. Objectif principal: OPTIMISER l’utilisation des ressources

Recommandation E.800 du CCITT :

« Effet global des performances du service qui détermine le degré de satisfaction d’un utilisateur du service. »


Motivation

Au début des réseaux sans fils :

Le premier souci est de permettre la connectivité

Le principe utilisé est le BEST EFFORT c’est-à-dire « AU MIEUX»

Aucune garantie de livraison des données SEND AND PRAY

Mais….pour certains applications ce service n’est pas du tout suffisant

Exemple:

Applications multimédias, téléphonie, jeux, applications critiques, communications dans un champs de bataille, etc.

La QoS n’est pas une OPTION mais une NECESSITÉ pour permettre d’attirer surtout l’attention des INDUSTRIELS


Exemple d’exigences en QoS

Source:


Obstacles dans les réseaux ad hoc

La topologie du réseau change de façon dynamique Information d’état souvent impréciseRessources dispersées et limitées (Ex: mémoire)Ressources d’énergie épuisables (batterie ou cellules

solaires)Nœuds des fois hétérogènesMédium non sécurisé (des intrus peuvent violer les

garanties en QoS)Erreurs du canal


Complexité

Qualité de service dans les MANETs = Fournir une fonctionnalité complexe dans un environnement très dynamique où les ressources sont rares.

Solution: Deux approches classiques:

Sur-dimensionnement

Ingénierie de trafic


Analogie avec le trafic routier

Ingénierie de traficsurdimensionnement


Sur-Dimensionnement (over-dimensioning)

Avantages: Facile et peut se faire de façon graduelle; Aucun mécanisme de QoS n’est nécessaire;

Inconvénients: Peut être très coûteux pour le déploiement et la mise à jour; Difficile à prédire les besoins futurs du trafic; Ne peut pas offrir des garanties sur le délais; Dans la plupart des cas, il s’agit d’un déplacement du problème; Perte de ressources (réseau sous-utilisé); Pour un réseau mobile ad hoc les ressources sont rares et

volatiles; La bande de fréquence est très limitée

Principe :Agir sur les RESSOURCES (solution matérielle) Approvisionner le réseau avec « suffisamment » de ressources si besoin est

Principe :Agir sur les RESSOURCES (solution matérielle) Approvisionner le réseau avec « suffisamment » de ressources si besoin est

PROHIBITIF


Ingénierie de trafic (Traffic engineering )

Principe Agir sur le TRAFIC (solution logicielle) Utiliser des mécanismes de contrôle et de priorité pour le trafic

Principe Agir sur le TRAFIC (solution logicielle) Utiliser des mécanismes de contrôle et de priorité pour le trafic

Avantages: Non coûteuse; Utilisation rationnelle des ressources;

Inconvénients: Complexe à implémenter Problème de passage à l’échelle

(scalability)


Taxonomies…..

Couche MAC

Protocoles de

signalisation

Routage avec 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 citée:

Modèles de QoS

Qualité de Service dans les Réseaux Ad Hoc


Critiques

Taxonomie critiquée notamment dans:

[Chaudet2006] Claude Chaudet, Isabelle Guérin Lassous, - État des lieux sur la qualité de service dans les réseaux ad hoc - Invited paper, in 'Colloque Francophone sur l'Ingénierie des Protocoles'' - November 2006 - Tozeur, Tunisia.

Raisons ?

• Impossible de classifier les solutions existantes selon cette taxonomie;• Pourquoi séparer la signalisation et le QoS routing alors qu’ils sont souvent complémentaires;• Un bon modèle de QoS est souvent construit à partir de plusieurs blocs de base


Taxonomie selon le niveau de QoS

Niveau Définition Autres noms Example d’applications

Difficulté

Best Effort (BE)

le réseau envoie les paquets sans aucune garantie.

send and pray courrier électronique, transfert de fichiers,

+

QoS relâchée (soft QoS)

la garantie de service estofferte avec une probabilité. Il peut y avoir des périodes transitoires où la QoS n’est pas garantie.

QoS statistique,Mieux que le best

effort,QoS qualitative,QoS relative

voix sur IP, ++

QoS pseudo ferme

(Pseudo Hard QoS)

les garanties de QoS sont de type ferme, sauf en cas de fluctuations du canal radio ou de changement de topologie.

communications militaires;

+++

QoS ferme (hard QoS)

si les exigences ne sont pas satisfaites, le service n’est pas du tout fourni

TOUT ou RIEN

QoS déterministe,service garanti,QoS quantitative,QoS absolue

- contrôle de trafic aérien,

- chirurgie à distance, - contrôle d’un réacteur nucléaire,

etc.

impossible

Niv

eau

de Q

oS


Routage avec QoS dans

Les MANETs


Objectifs du Routage avec QoS

Les TROIS objectifs principaux du routage avec QoS sont les suivants:

1. Déterminer dynamiquement un chemin répondant aux exigences de QoS entre une source et une destination ;

2. Optimiser les ressources du réseau (load balancing);3. Permettre une dégradation gracieuse (graceful

degradation) des performances du réseau

http://www.ietf.org/rfc/rfc2386.txt


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 et demande une QoS en bande passante de Bw=4

Besoin en QoS: BW≥4


Positionnement

Network requirementsApplication requirements


Composantes du routage avec QoS ?

Le routage avec QoS nécessite deux entités:

•Protocole de routage (algorithme distribué): récolte et distribution des information sur les ressources;

•Algorithme de routage (algorithme local) qui s’intéresse à la recherche d’un chemin faisable qui vérifie la QoS NP-Complet si le nombre de métriques additives 2Utiliser heuristiques


Comment concevoir un nouveau protocole de routage avec QoS

Deux approches principales: Concevoir le nouveau from scratch

Prendre un protocole existant (ex: AODV, OLSR) et ajouter des briques de bases pour le rendre sensible à la QoS selon la métrique choisie

Avantage majeur: facilité

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

Extension du protocole AODV Métrique: délai Estimation du délai local à chaque nœud Le délai est une métrique ADDITIVE :

Délai de bout en bout = Délais à un saut

S D

25 ieme Anniversaire du CERIST2604/11/23 26

Principe du protocole AODV

• AODV: Ad hoc On Demand Vector Distance Routing protocol• Protocol réactif• IETF RFC 3561. Juillet 2003


MAC

Architecture synoptique de AODV-D

Estimation du délai MAC

LLC

Physique

Présentation

SessionTransport

Réseau

AODVRoutage avec QoS

Besoins en QoSApplicatio

n

CAC


Estimation du délai de mise en file au niveau MAC

Question principale: Quel modèle de files d’attente utiliser pour estimer le délai au niveau du 802.11 ?

Recherche Bibliographique:

M/MMGI/1/K Ozdemir et al 2004

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

M/G/1/K Ozdemir et al 2004

M/M/1/K Chikh Sarr, 2007 Ph.D Thesis

G/G/1 Bisnik et al 2009


File M/M/1/K

Nombre de clients dans la file

Taux d’utilisation du serveur

Temps de séjour dans le système

•L'arrivée de paquet suit une loi exponentielle de paramètre λ•Le taux de service suit également une loi exponentielle de paramètre µ•La taille de la file d'attente est limitée par la valeur K. •La politique d’ordonnancement est FIFO (Premier Arrivé Premier Servi)


File M/M/1/K (suite)

Nombre moyen de clients dans le système

Comme la somme est égale au temps de service alors:

D’où:

?

(Loi de Little)


Estimation du délai moyen de transmission

Soit p la probabilité de collision sur un lien. La probabilité de réussite de transmission au premier envoi est donc 1-pLa probabilité de réussite de transmission au 2ième envoi est p .(1-p)

Après C tentatives de transmission échouées, la trame est éliminée(Pour le 802.11 C =7 )

Soit X la variable aléatoire qui compte le nombre de tentatives pour une transmission réussie d’une trame

Nombre moyen de retransmissions pour une trame donnée:


Délai 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 réussie d’un paquet de taille m à l’aide du 802.11


04/11/23 33

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

Bande passante désirée

Délai max demandé

Délai un saut calculé

RREQ ID

Destination IP Address

Destination Sequence Number

Originator IP Address

Originator Sequence Number

TYPE R | A PREFIX SZ HOP COUNT

Destination IP Address

Destination Sequence Number

Originator IP Address

Lifetime

Probabilité de collision

Extension des paquets de contrôle


Echange d’information

Les nœuds échangent des messages HELLO chaque intervalle de temps Δ secondes

Ces messages HELLO contient un information supplémentaire: me taux d’occupation du canal

La valeur du paramètre Δ est cruciale: grande: stabilité des résultats mais mauvais résultats en cas de

mobilité petite : trop d’overhead et de calcul mais bonne réaction à la

mobilité Les auteurs proposent: Δ = 1 seconde

Chaque nœud estime le taux d’occupation du canal à son niveau et envoie l’information dans le paquet HELLO

La taux d’occupation du canal au niveau d’un nœud est donné par: (Ts + Tr ) / Δ


AODV-DDélai ≤ 150 AODV-DDélai ≤ 150

AODVPlus court chemin

AODVPlus court chemin

Scénario de simulation


Résultats de simulation (NS-2)Délai de bout en bout


Modèles de QoS dans

Les MANETs


Modèles de QoS Modèle de QoS

Un modèle définit généralement les blocs de base d’une solution

donnée : Contrôle d’admission politique

d’ordonnancement contrôle de congestion, signalisation, routage avec QoS Lissage de trafic, etc

Définir QUI FAIT QUOI? Interaction ?Aspect architectural


Question Principale

Les deux modèles classiques IntServ et DiffServsont-ils applicables aux réseaux mobiles ad hoc ?

MOTIVATION: Pourquoi réinventer la roue et inventer des modèles ex nihilo alors que deux modèles existent déjà ? Prendre en considération la possibilité de connexion à

Internet Interopérabilité avec IntServ et DiffServ classiques

Faut-il une évolution ou une révolution ?

INTERNET

Passerelle(gateway)


IntServ (Integrated services)

• Emulation de circuits;• Mécanisme de bout en bout;• mécanisme de QoS par flux;•Utilise le protocole de signalisation RSVP


Pour MANETS ?

AVANTAGES: Fournit une bonne QoS; Zéro paquets perdus

INCONVENIENTS:

Nécessite des informations exactes sur l’état des liens, chose qui est difficile dans le contexte des réseaux mobiles ad hoc;

Génère beaucoup d’overhead; Complexité au niveau du cœur du réseau ; N’est pas pratique pour les flux de courte durée;

Scalabilité


DiffServ (Differentiated Services)

Résoudre le problème de scalabilité par deux façons: Remplacer le principe par flux par un principe par agrégats; La complexité dans les nœuds du coeur est déplacée vers

les équipements aux extrémités;

Nœud interne

Nœud d’entrée

Nœud de sortie


AVANTAGES Plus scalable que IntServ Modèle léger dans les nœuds du réseau plus facile à

déployer Peut fournir des fois une bonne QoS

INCONVENIENTS: Ne signale pas à la congestion de façon explicite Quand la topologie du réseaux change les rôles des noeuds

changent également Difficile de négocier dynamiquement un profil de trafic

Pour MANETS ?


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

Idées principales de INSIGNIA: Premier protocole de signalisation pour MANETS Inspiré de IntServ fournir un modèle de QoS de bout en bout Un modèle de QoS adaptif


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

Soft QoS Inspiré de DiffServ Ne pas garder les informations sur l’état 2 classe de trafic: best effort et real time Définit un contrôle d’admission pour accepter/rejeter une

nouvelle connexion


FQMM (Flexible QoS Model for MANETs)

• Modèle hybride: IntServ + DiffServ• Conçu pour les MANETS de taille moyenne (jusqu’à 50 noeuds)• Flexible


Références bibliographiques pertinentes

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

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

C. Chaudet and I. Guérin-Lassous, Etat des lieux sur la Qualité de Service dans les Réseaux Ad hoc, Colloque Francophone sur l’Ingénierie des Protocoles (CFIP), Tozeur. Tunisia, 2006.

L. Chen and W. Heinzelman, A survey of routing protocols that support QoS in mobile ad hoc networks, IEEE Network 21 (2007), no.6, 30–38.

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

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

P. Mohapatra, P. J.Li, and C.Gui, QoS in Mobile Ad hoc Networks, IEEE Wireless 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 and Solutions., Ad Hoc Networks 4 (2006), no. 1, 83–124.


Conclusion générale

La flexibilité des réseaux mobiles ad hoc les rend très utiles dans plusieurs domaines

Les caractéristiques inhérentes au réseaux mobiles ad hoc rendent l’approvisionnement de la QoS très complexe

Vu la volatilité des ressources, on ne peut pas offrir une hard QoS dans les réseaux ad hoc

La soft QoS (mieux que le best effort) peut être suffisante dans certains cas Un exemple d’un protocole de routage à soft QoS a été présenté (L’estimation

du délai est basé sur le modèle M/M/1/K) IntServ et DiffServ ne sont pas directement applicables pour les réseaux

mobiles ad hoc DiffServ est mieux adapté aux réseaux mobiles ad hoc que IntServ


Documents

1 Qualité de Service dans les Réseaux Mobiles Ad Hoc Nadir BOUCHAMA Division Théorie & Ingénierie des Systèmes Informatiques (DTISI) [email protected]