Quality Of Service Routing In Ad Hoc Networks (in French)

Centre de Recherche sur l’Information Scientifique et technique Division Théories et Ingénierie des systèmes Informatiques

Routage avec Qualité de service dans les Réseaux Mobiles ad Hoc Nadir BOUCHAMA [email protected]

11/06/2008

1

Plan de l’Exposé..  Réseaux Mobiles Ad Hoc : Motivation, Application  Notion de Qualité de Service (QoS)  Qualité de Service dans les Réseaux Mobiles Ad Hoc: notion de QoS adaptative  Surdimensionnement versus Ingénierie de trafic  Approches pour offrir la QoS: où se situe le routage avec QoS dans toute cette armada de solutions ?  Principe du routage QoS  Concevoir un protocole de routage avec QoS: compromis  Métriques utilisées  Exemple de routage avec QoS  Conclusions et perspectives

© Nadir BOUCHAMA CERIST 2008

2

Réseaux mobiles ad hoc Un réseau mobile ad hoc ou MANET (Mobile Ad hoc NETwork) est un système autonome de plateformes mobiles appelées nœuds qui sont libres de se déplacer librement. Ce système peut être isolé ou avoir des passerelles ou des interfaces le reliant à un réseau fixe (Internet, ATM)

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

Caractéristiques:  Liens sans fils  Une topologie dynamique  Ressources limitées et volatiles (bande passante, énergie, mémoire, CPU)  Vulnérabilité aux attaques © Nadir BOUCHAMA CERIST 2008

GW

Internet

3

Challenges…     

Routage efficace Gestion de la mobilité Scalabilité Sécurité Partage efficace du médium de communication

Qualité de service

© Nadir BOUCHAMA CERIST 2008

4

Qualité de Service (QoS) adaptative



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 »

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

Cette définition n’est pas adéquate 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

 La QoS est dite alors adaptative © Nadir BOUCHAMA CERIST 2008

5

Motivation

Au début de l’apparition des réseaux mobiles ad hoc : Le premier souci est de permettre la connectivité des noeuds Le principe utilisé est le BEST EFFORT c’est-à-dire « AU MIEUX» Aucune garantie de livraison des données SEND AND PRAY (envoyer et prier que ça réussisse)

Mais…. pour certaines 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.

© Nadir BOUCHAMA CERIST 2008

6

Besoins des applications…

 La QoS n’est pas une OPTION mais une NECESSITÉ pour permettre un déploiement à grande échelle © Nadir BOUCHAMA CERIST 2008

7

Complexité dans le contexte des MANETs

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: Matériel le

Sur-dimensionnement

Logiciell e

Ingénierie de trafic

© Nadir BOUCHAMA CERIST 2008

8

Sur-Dimensionnement Principe :

Agir sur les RESSOURCES (solution matérielle) Approvisionner REACTIVEMENT le réseau avec « suffisamment » de ressources si besoin est DIMENSIONNEMENT GENEREUX

 Avantages:

B I H

F I IT

 Simple et peut se faire de façon graduelle;  Aucun mécanisme de QoS n’est nécessaire;

 Inconvénients:

O R

Peut être très coûteux pour le déploiement et la mise a jour; Difficile à prédire les besoins futurs du trafic; Ne peut pas garantir les 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 On ne peut pas se permettre ce LUXE  La bande de fréquence est très limitée      

P

© Nadir BOUCHAMA CERIST 2008

9

Ingénierie de trafic (Traffic engineering ) Principe

Agir sur le TRAFIC (solution logicielle) Évaluation et optimisation des performances des réseaux IP en utilisant des méthodes scientifiques pour le mesurage,caractérisation, modélisation, et contrôle du trafic. RFC 3272: Overview and Principles of Internet Traffic Engineering

Avantages:  Rentable;  Utilisation rationnelle des ressources;

Inconvénients:  Complexe à concevoir et à implémenter;  Problème de passage à l’échelle (scalability) © Nadir BOUCHAMA CERIST 2008

Congestion-related performance degradation has been found to cause the majority of network downtime costs Michael Howard President, Infonetics Research

10

Analogie avec le trafic routier

surdimensionnement © Nadir BOUCHAMA CERIST 2008

Ingénierie de trafic 11

Taxonomies….. Classification la plus connue et la plus citée: 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

Qualité de Service dans les Réseaux Ad Hoc

X

Sur dimensionnement

Ingénierie de trafic

Protocoles Différentiatio Routage de n avec QoS signalisatio Couche MAC n Interviennent à une couche ou souscouche du modèle de référence OSI © Nadir BOUCHAMA CERIST 2008

Modèles de QoS Approches Inter couche CROSS LAYER 12

Objectifs du Routage avec QoS Les TROIS objectifs principaux du routage avec QoS sont les suivants: • Déterminer dynamiquement un chemin répondant aux exigences de QoS et qui est réalisable entre une source et une destination ; • Optimiser les ressources du réseau (load balancing); • Permettre une dégradation gracieuse (graceful degradation) des performances du réseau http://www.ietf.org/rfc/rfc2386.txt

© Nadir BOUCHAMA CERIST 2008

13

Critiques Taxonomie critiquée notamment dans: 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 routage avec QoS alors qu’ils sont souvent complémentaires; •Un bon modèle de QoS est souvent construit à partir de plusieurs blocs de base dont le routage avec QoS, la signalisation, et les mécanismes de différentiation au niveau de la couche MAC

© Nadir BOUCHAMA CERIST 2008

14

Taxonomie selon le niveau de QoS Niveau Best Effort (BE)

Niveau de QoS

QoS relâchée (soft QoS)

QoS pseudo ferme (Pseudo Hard QoS)

QoS ferme (hard QoS)

Définition le réseau envoie les paquets sans aucune garantie. la garantie de service est offerte avec une probabilité. Il peut y avoir des périodes transitoires où la QoS n’est pas garantie. les garanties de QoS sont de type ferme, sauf en cas de fluctuations du canal radio ou de changement de topologie. si les exigences ne sont pas satisfaites, le service n’est pas du tout fourni

TOUT ou RIEN

© Nadir BOUCHAMA CERIST 2008

Autres noms Example d’applications send and pray

courrier électronique, transfert de fichiers,

QoS statistique, Mieux que le best effort, QoS qualitative, QoS relative

voix sur IP,

communications militaires;

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.

Difficulté +

++

+++

impossible

15

Qu’attend-t-on d’un protocole de routage avec QoS?  Adaptabilité: s’adapter à l’état du réseau ad hoc  Simplicité: éviter la complexité et la surcharge  Scalabilité: résister aux facteurs limite tels que le nombre de nœuds , nombre de flux, nombre de classes, etc  Efficacité: offrir un bon niveau de QoS pour les applications prioritaires  Equité: vis-à-vis du trafic best effort  Robustesse: résister aux perturbations dans le réseau  Sécurité: dans certains cas comme le domaine militaire

© Nadir BOUCHAMA CERIST 2008

16

Comment concevoir un protocole de 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 (resp. optimal) qui vérifie la QoS connu sous le nom du MCP (Multi Constraint Path) ou MCOP (Multi Constraint Optimal Path) resp. NP-Complet si le nombre de métriques additives 2 Utiliser heuristiques

≥

Type de QoS: Ferme (réservation) ou relâchée (priorisation) Quelle approche adopter: évolutionnaire (étendre les protocoles Best Effort existants) ou révolutionnaire (concevoir un nouveau protocole from scratch)

© Nadir BOUCHAMA CERIST 2008

17

Métriques de QoS pour un protocole de QoS Applicatio n Présentati on Session Transport

Réseau

Liaison (LLC+MAC)

Physique

Conception

Evaluation •Taux d’accept./Bloc. de sessions •Taux de sessions complétées/coupées

•Débit •Débit du réseau •Délai de bout en bout •Débit d’un nœud •Taille du buffer •Délai de découverte d’une route •Gigue •Charge de routage normalisée •Taux de perte de paquets(NRL) •Energie •Durée de vie du réseau •Sécurité •Durée de vie moyenne d’un nœud •Consommation en énergie •Délai MAC •Charge normalisée au niveau •Stabilité du lien MAC •Fiabilité •Consommation en énergie •Signal to Interference Ratio (SIR) •Bit Error Rate (BER) •Niveau de batterie résiduel

© Nadir BOUCHAMA CERIST 2008

18

Métriques au niveau réseau Définition Débit

Appelé aussi bande passante résiduelle : Débit minimal d’un chemin de bout en bout Délai de bout en Délai que met un paquet de la bout source à la destination Espace libre du Nombre de places dans un buffer buffer la gigue est définie comme étant la Gigue variation des délais d’acheminement des paquets dans le réseau Taux de perte rapport entre le nombre de paquets de paquets émis et le nombre de paquets reçus. Energie Sécurité © Nadir BOUCHAMA CERIST 2008

Niveau de confiance

Unité bps/s

milli-secondes

milli-secondes % joules % 19

Classification des métriques

© Nadir BOUCHAMA CERIST 2008

20

Exemple de Routage avec QoS Exemple: Une source D veut communiquer avec une destination D et demande une QoS en bande passante de Bw=4 <5,4> <4,5>

Tuple:

C

B

S

<4,2>

<5,3>

<2,4>

Besoin en QoS: BW≥4

S

Source

D

Destination

<3,4> <3,3>

D

E

F <2,2>

D

© Nadir BOUCHAMA CERIST 2008

<4,4>

Plus court chemin Chemin satisfaisant la QoS

21

Conclusion & Perspectives  Les solutions de QoS doivent impérativement être adaptative dans les réseaux mobiles ad hoc;  Le routage avec QoS est un problème très difficile dans le contexte des réseaux mobiles ad hoc;  A part le protocole PNNI de ATM, aucun protocole de routage avec QoS n’a été standardisé actuellement ni pour les réseaux filaires ni pour les réseaux mobiles ad hoc ;  pour les Le problème de scalabilité (« S » word problem) reste le problème majeur dans la plupart des solutions. Ceci dit, les protocoles à QoS relâchée sont plus scalables que les protocoles à QoS ferme;  Le routage QoS n’est généralement qu’une brique de base (building block) dans la construction d’une architecture de QoS globale (cross layer);  Nous travaillons sur les approches évolutionnaires pour les protocoles AODV, DSR (réactifs), OLSR (proactif) en travaillant principalement sur la métrique bande passante; Perspectives: - Travailler sur la métrique délai pour la VoIP (+ stabilité ??) - Proposer un modèle de QoS (CROSS LAYER) qui fasse intervenir plusieurs couches © Nadir BOUCHAMA CERIST 2008

22

QUESTIONS ? © Nadir BOUCHAMA CERIST 2008

23