Introduction aux Mécanismes de Qualité de Servicechaput.perso.enseeiht.fr/supports/2007-2008/QoS...Fondee sur des informations contenues dans les paquets´ Necessaire du fait de

Introduction aux Mecanismes de Qualite de Service

Chaput Emmanuel

2007-2008

Chaput Emmanuel () Introduction aux Mecanismes de Qualite de Service 2007-2008 1 / 85

1 Introduction

2 Schema general

3 Exemples d’AQM

4 Exemples de shaper

5 Algorithmes d’ordonnancement

6 Un cas d’etude


Introduction

Introduction

1 Introduction

2 Schema general

3 Exemples d’AQM



6 Un cas d’etude


Notes :

Notes :

Notes :

Introduction

Le probleme

Reseaux a commutation de paquets : multiplexage temporelasynchrone

Alteration du profil temporel des flots de paquetsInequite lors de contention entre les taux de perte des flotsPas de traitement specifique en fonction de besoins differents

Comportement best effort

Le reseau fait ce qu’il peutSans garantir quoi que ce soit


Introduction

Objectifs

Fournir des mecanismes permettant d’assurer de la “Qualite deservice” dans les reseaux de paquets.

Distribuer “equitablement” le debit des liensIsoler les trafics entre euxAccroıtre les performances du service fourni

Delai de bout en boutGigue sur un fluxDebit sur le cheminPerte de paquets


Introduction

Differents types de metriques

Metrique additiveMr1,r2 = Mr1 + Mr2

pe delai, gigueMetrique concave

Mr1,r2 = min(Mr1 ,Mr2)pe debit

Metrique multiplicativeMr1,r2 = Mr1 ×Mr2

pe probabilite de non perte


Notes :

Notes :

Notes :

Introduction

Mecanismes =/= architecture

Mise en œuvre de la qualite de service

Une architecture (IntServ, DiffServ, . . . )Des protocoles (RSVP, DSCP, . . . )Des mecanismes (ordonnancement, lissage, . . . )

Mecanismes non lies a une architecture bien queSouvent implantes pour assurer des services definis dans lecadre d’une architecture


Schema general

Schema general

1 Introduction

2 Schema general

3 Exemples d’AQM



6 Un cas d’etude


Schema general

Les fonctions

Classifier Marker

CAC

AQM Scheduler

Meter

Shaper

Policer

Presence et localisation dependantes

De l’architectureIntServ [3], DiffServ [1], . . .

De l’entite dans l’architectureRouteur de frontiere, de cœur, . . .


Notes :

Notes :

Notes :

Schema general

Classifier

Objectif : realiser une segregation des paquetsSegregation par flot (a la IntServ)Segregation par classe (a la DiffServ)Fondee sur des informations contenues dans les paquetsNecessaire du fait de l’absence de connexion IP


Schema general

Meter

Objectif : mesurer les caracteristiques (temporelles) d’un ensemble depaquets

Caracteristiques selon criteres de segregationVerification de conformite

A un profil de trafic negocieComparaison a des seuils

Eventuellement negociesEventuellement dynamiques


Schema general

Marker

Objectif : ajouter des informations pertinentes au paquet

Emplacement prevu dans les entetesChamp ToS d’IPv4, . . .

Encapsulation supplementaireLabel MPLS, . . .

Structure de donnees associeeTraitement local

Pemet un traitement plus rapide en aval


Notes :

Notes :

Notes :

Schema general

Shaper

Objectif : Lisser le trafic

Le rendre conforme a un profil temporelEvite les bursts en avalIntroduction de “delai” entre paquetsImplante dans le scheduler


Schema general

Policer

Objectif : contraindre le trafic

Le rendre conforme a un contratDestruction/remarquage de paquetsPas de lissageIsolation des trafics


Schema general

Active Queue Management

Objectif : diminuer les risques de congestion

Gestion active des files d’attente [2]Eviter les files d’attente pleines

Capacite a accueillir les burstsMinimiser le temps de traversee

Prevenir la congestion plutot que la subirDefinition de taux de remplissage seuilsActions curatives (anticipees) ou preventivesActions plus equitables


Notes :

Notes :

Notes :

Schema general

Scheduler

Objectif : realiser le multiplexage temporel

Utiliser “equitablement” le debit disponibleAppliquer les choix faits lors des etapes precedentesImplantation integre les fonctions de shaper/policerEventuellement non work conserving (CF page suivante)


Schema general

Ordonnancement Work Conserving

Ordonnancement Work ConservingUn paquet en attente est emis des que le support est disponibleUtiliser au mieux la bande passante

Ordonnancement Work ConservingUn paquet en attente doit de plus etre eligible pour etre emisAttendre un paquet plus prioritaireMettre en place du lissage


Schema general

Connexion Admission Control

Objectif : Verifier qu’un contrat peut etre assure

Negociation de parametres de QoSAssocie a de la reservation de ressourceNecessite un protocole oriente connexion ou un equivalentPeut permettre l’isolation des trafics

Notion de SLA

Service Level AgreementAccord entre le client et l’operateurDescription des parametres de QoS


Notes :

Notes :

Notes :

Schema general

Un exemple : IntServ

Classifier Policer Scheduler

CAC

Ressources reservees par RSVP


Schema general

Un exemple : DiffServ (edge router)

Classifier Marker

Meter

ShaperPolicer

Segregation evoluee (MF-classifier)Marquage simple (DSCP) pour le domainePolicing (ingress router)Shaping (egress router)


Schema general

Un exemple : DiffServ (core router)

Classifier Scheduler

segregation simplecomportement conforme a un PHB


Notes :

Notes :

Notes :

Exemples d’AQM

Exemples d’AQM

1 Introduction

2 Schema general

3 Exemples d’AQM



6 Un cas d’etude


Exemples d’AQM

Random Early Detection

p=1 p=00 < p < 1

Observation de l’etat de la fileDefinition d’une probabilite en fonction de l’etatMarquage/destruction de paquets choisis aleatoirementDesynchronisation des TCPsPremiere proposition en 1993 [7]


Exemples d’AQM

RED with In and Out

1

0

P(drop)

Pmax_in

Pmax_out

max_out/avg_total

max_in/avg_inmin_out/avg_total min_in/avg_in

Double RED [4]Paquets marques in ou out

Perdre prioritairement des paquets hors-profilIndependant du marquage des paquetsQuel parametrage ?


Notes :

Notes :

Notes :

Exemples de shaper

Exemples de shaper

1 Introduction

2 Schema general

3 Exemples d’AQM



6 Un cas d’etude


Exemples de shaper

Leaky bucket

b

r

Les paquets entrent dans le “seau”Sortie du seau a debit borne (r)Si capacite (b) finie : policingSeau = metering


Exemples de shaper

Token bucket

b

r

Chaque paquet (octet) consomme un jetonBursts possibles en sortie (limites par b)Paquets hors profil (pas de jeton)

Retardes (shaper)Detruits/declasses (policer)


Notes :

Notes :

Notes :

Algorithmes d’ordonnancement

Algorithmes d’ordonnancement5 Algorithmes d’ordonnancement

First In First OutRound RobinDeficit Round RobinFair QueuingStochastic Fair QueuingGeneralized Processor SharingPacket Generalized Processor SharingVirtual ClockPriority QueuingObjectifsImplantation dans Linux

Architecture generaleLes architecturesLes ordonnanceursLa mecanique DiffServLes outils annexesPolicing de trafic

Exemple de mise en placeLe lienLe terminal satellite

Les difficultes techniquesDeveloppementInteractionsServeur de QoS


Algorithmes d’ordonnancement First In First Out

First In First Out

Tail dropSimple a implanterPas de distinction entre trafics du buffer)


Algorithmes d’ordonnancement Round Robin

Round Robin

Classification du traficSimple a implanterCertaine isolation entre les traficsEquitable en paquets : en debit ?


Notes :

Notes :

Notes :

Algorithmes d’ordonnancement Deficit Round Robin

Deficit Round Robin

Constat : packet round robin non equitable si taille variableService pondere : Qi bits max par tour pour la file iPrise en compte du deficit (Qi - service) au tour suivantCompatible avec SFQ

[14]


Algorithmes d’ordonnancement Deficit Round Robin

Deficit Round Robin : algorithme

Qi nombre max de bits du flux i transmis par cycleDCi deficit du flux i

Lki nombre de bits du paquet k du flux i

AlgorithmeDCi = 0A chaque cycle, pour chaque flux i

DCi ← DCi + Qitant qu’il existe un paquet k en attente tel que Lk

i ≤ DCi

emettre le paquetDCi ← DCi − Lk

i


Algorithmes d’ordonnancement Fair Queuing

Fair Queuing

Simulation d’un round-robin fluide (bit a bit)Reception d’un paquet : calcul de sa date de depart theoriqueEmission ordonnee selon les dates theoriques[11] [12] [6]


Notes :

Notes :

Notes :


Fair Queuing : principe

NotationR(t) nombre de cycles du round robin a t

Na(t) nombre de flux actifs a tak

i date d’arrivee du paquet i du flux kLk

i nombre de bits du paquet i du flux kSk

i et F ki dates de debut et fin de service du paquet i du flux k en

nombre de cyclesProprietesNa(t) = card({k ,F k

max(i,aki )≤ t)})

F ki = Sk

i + Lki

Ski = max(F k

i−1,R(aki )) (respect de l’ordre !)

∂R(t)∂t = 1

Na(t) si 1 bit par unite de temps



Fair Queuing : algorithme

Reception d’un paquet : calcul de sa date de fin de service par unround-robin bit a bitSupport libre : emission du paquet de plus faible F k

i

On ne s’interesse pas aux dates reelles puisque r(t) eststrictement croissanteDuree de cycle variable (arrivee d’un paquet sur un flux inactif)

Dates (reelles) de depart theorique a recalculerDates en R(t) inchangees !


Algorithmes d’ordonnancement Stochastic Fair Queuing

Stochastic Fair Queuing

Constat du Fair Queuing : lourd a implanter a haut debit (gestionsdes files)Flots repartis selon une methode de hachageHachage modifiee regulierement[10] [9]


Notes :

Notes :

Notes :

Algorithmes d’ordonnancement Generalized Processor Sharing

Generalized Processor Sharing (GPS)

Service fluide pondere (debit de sortie φi pour flux i)Chacun obtient φiP

φi

Extremement equitableImpossible a implanter


Algorithmes d’ordonnancement Generalized Processor Sharing

Packet GPS

Weighted Fair Queuing (pondere par φi , ou∑φi = 1

Pour chaque paquet : estimation de sa date de sortie sur un GPS

Paquets emis dans l’ordre de ces dates[6] [13]


Algorithmes d’ordonnancement Packet Generalized Processor Sharing

Packet GPS : principes

Notations du Fair Queuing plusV (t) temps virtuel evoluant proportionnellement a 1P

i∈{actifs} φisi

1 bit par unite de tempsProprietes

F ki = Sk

i +Lk

iφi

Ski = max(F k

i−1,V (aki ))

∂V (t)∂t = 1P

i∈{actifs} φisi 1 bit par unite de temps


Notes :

Notes :

Notes :

Algorithmes d’ordonnancement Virtual Clock

Virtual Clock

Inspire du TDM

Calcul d’une date de depart theoriqueDate calculee en supposant un debit constantEmission ordonnee selon les dates theoriquesIsolation des flux[15]


Algorithmes d’ordonnancement Virtual Clock

Virtual Clock : principes

Notationsri debit moyen associe au flot i (i ∈ [1 . . . n])

Ski et VCk

i dates de debut et fin de service du paquet i du flux kak

i date d’arrivee du paquet i du flux kLk

i nombre de bits du paquet i du flux kProprietes

VCki = Sk

i +Lk

iri

Ski = max(F k

i−1,aki ) (respect de l’ordre !)


Algorithmes d’ordonnancement Priority Queuing

Priority Queuing

Chaque file est dotee d’une prioriteFile de plus faible priorite servie si prioritaire videGeneralement pas de preemptionRisque de famine


Notes :

Notes :

Notes :

Un cas d’etude

Un cas d’etude

6 Un cas d’etudeObjectifsImplantation dans Linux





Un cas d’etude Objectifs






Un cas d’etude Objectifs

Architecture de qualite de service dynamique

Definition d’une architecture de qualite de service

Utilisation de l’implantation des mecanismes DiffServ dans lenoyau Linux ;Couplage avec les couches hautes et basses

QoS server ;Couche MAC (allocation) ;

Evaluation des algorithmes disponibles (tache 2).


Notes :

Notes :

Notes :

Un cas d’etude Implantation dans Linux

Implantation dans Linux







Objectifs de l’architecture

Lissage des trafics : supression des salves, . . .Ordonnancement des paquets selon diverses strategies

Policing des trafics entrantsDestruction des paquets hors-limites



Architecture de base


Notes :

Notes :

Notes :


Trois grandes familles

Les architectures fournissent un cadreLes ordonnanceurs . . . ordonnancentLes outils annexes offrent d’autres fonctionnalites



Les architectures

CBQ ancetre historique propose par S. Floyd et Van Jacobson[8]

CSZ partiellement implante [5]HTB autre implantation des concepts de CBQ



Clark Shenker Zhang

Description de trafic et controle d’admissionToken bucket ou debit max

Classification des fluxTemps reel avec contraintes strictesTemps reel “mou”Best effort

OrdonnancementIsolation pour temps reel (WFQ)Technique non optimale pour le reste (FIFO, FIFO+)

Quelle garantie de bout en bout ?


Notes :

Notes :

Notes :


Clark Shenker Zhang (implantation)

Version simplifieePas de controle d’admissionFIFO + priorites pour non temps reelWFQ version paquet simplifiee



Hierarchical Token Bucket, CBQ

Issu des travaux de Floyd et V. JacobsonHierarchisation des traficsCadre generique pour partager les liens :

Debit par classeOrdonnancement avec/sans congestionPartage du debit non utilise



Hierarchical Token Bucket, CBQ (implantation)

Bien plus simple que CSZ

Estimation des ressources utliseesDetermination des classes a controlerUtilisation du debit residuel


Notes :

Notes :

Notes :


Prio



Prio

Plusieurs niveaux de prioritesClassifieursCorrespondance avec le champ TOS



First In, First Out

Premier arrive premier serviLimite sur longueur de fileVersion paquet et version octet


Notes :

Notes :

Notes :


FIFO rapide

FIFO a trois prioritesImplantation du TOS IPv4Plus rapide que PRIO + FIFO



Token Bucket Filter

Classique. ParametresTaille du seau, debitTaille maximale de la fileBurst maximal



Stochastic Fairness Queuing

Distribution des flux sur des filesTourniquet sur les filesHashage pour repartition


Notes :

Notes :

Notes :


...

classifier

discipline dsmark

marquageclassediscipline



Le plus haut niveau

Outil dsmarkCadre general(Re)marquage des paquetsConsultation du DSCP



Le filtrage en entree

Classifieur tcindexChoix d’une classe en fonction du marquageDefinition d’un nouveau champUtilisation delicate


Notes :

Notes :

Notes :


Prio



Random Early Detection

Destruction (marquage) probabilisteInteraction avec ECN possible[2]



Generalized RED

Files d’attentes virtuellesCaracteristiques a la RED distinctesPossibilite de prioritePour les BAs de type AF de DiffServ


Notes :

Notes :

Notes :


Policing de trafic

Discipline ingress

Policing par des filtresPeu evolutif



Itermediate Queuing device

Peripherique virtuelRecoit le trafic de peripheriques reelsRe-injecte le trafic dans le systeme


Un cas d’etude Exemple de mise en place

Exemple de mise en place






Notes :

Notes :

Notes :


1 Introduction2 Schema general3 Exemples d’AQM4 Exemples de shaper5 Algorithmes d’ordonnancement

First In First OutRound RobinDeficit Round RobinFair QueuingStochastic Fair QueuingGeneralized Processor SharingPacket Generalized Processor SharingVirtual ClockPriority Queuing







Architecture generale

ST

user

satellite

NCC

émulateur



Simulation du lien

Outil de simulation de reseau netem pour pertes et retardOrdonnancement pour debit

# tc qdisc add dev eth0 root handle 1 : netem delay240ms 1ms loss 0.00001% 90%# tc qdisc add dev eth0 parent 1 : handle 2 : tbfrate 512kbit


Notes :

Notes :

Notes :


Configuration du ST

eth0 eth1 réseau satelliteréseau utilisateur

Terminal

Satellite



Classification des trafics

Possibilites MFC tres vastes

Tous les champs de l’en-tete paquetNombreux autres champsResultat routageResultat policing



Policing

ingress et filtres# tc qdisc add dev eth0 handle ffff : ingress# tc filter add dev eth0 parent ffff : protocolip u32 match ip src 1.2.3.0/24 police rate128kbit burst 10k drop flowid :1

IMQ si necessaire# ip link set imq0 up# qdisc add dev imq0 root handle 1 : dlb# iptables -t mangle -A PREROUTING -i eth1 -pudp -j IMQ --todev 0


Notes :

Notes :

Notes :


Ordonnancement : strategie

# tc qdisc add dev eth1 handle 1 : root dsmarkindices 64 set tc index# tc filter add dev eth1 parent 1 : prio 1 tcindexmask 0xfc shift 3

Classe dscp indiceaf11 001010xx 0x05. . . . . . . . .

af13 001110xx 0x07. . . . . . . . .ef 101110xx 0x17. . . . . . . . .



Ordonnancement : organisation

Utilisation d’une hierarchie de classes# tc qdisc add dev eth1 parent 1 : handle 2 : htbrate 2mbit burst 16k# tc filter add dev eth1 parent 2 : protocol ip prio1 tcindex mask 0x1c shift 3 pass on

Trafic Classeaf1n 0x1naf2n 0x2naf3n 0x3naf4n 0x4n

ef 0x50be 0x60



Ordonnancement : repartition

# tc filter add dev eth1 parent 2 : protocol ip prio1 handle 1 tcindex classid 2 :10# tc filter add dev eth1 parent 2 : protocol ip prio1 handle 2 tcindex classid 2 :20# tc filter add dev eth1 parent 2 : protocol ip prio1 handle 3 tcindex classid 2 :30# tc filter add dev eth1 parent 2 : protocol ip prio1 handle 4 tcindex classid 2 :40


Notes :

Notes :

Notes :


Ordonnancement : gestion des files

Expedited Forwarding# tc class add dev eth1 parent 2 : classid 2 :50rate 512Kbit ceil 1Mbit# tc qdisc add dev eth1 parent 2 :50 red limit256000 min 16000 max 32000 avpkt 1000 burst 10probability 0.02 bandwith 512 ecn

Assured Forwarding . . . patience !Best Effort# tc class add dev eth1 parent 2 : classid 2 :50rate 512Kbit ceil 1Mbit



Assured Forwarding

Les AFxy (x constant) ont des taux de pertes differents# tc class add dev eth1 parent 2 : classid 2 :10 htbrate 64kbit ceil 128kbit# tc qdisc add dev eth1 parent 2 :10 gred setup DPs3 default 3 grio



Assured Forwarding

Parametrage des taux de perte# tc qdisc change dev eth1 parent 2 :10 gred limit2048 min 512 max 1024 burst 10 avpkt 512 bandwidth64kbit DP 1 probability 0.05 prio 1# tc qdisc change dev eth1 parent 2 :10 gred limit2048 min 512 max 1024 burst 10 avpkt 512 bandwidth64kbit DP 2 probability 0.10 prio 2# tc qdisc change dev eth1 parent 2 :10 gred limit2048 min 512 max 1024 burst 10 avpkt 512 bandwidth64kbit DP 3 probability 0.15 prio 3


Notes :

Notes :

Notes :

Un cas d’etude Les difficultes techniques

Les difficultes techniques







Algorithmes de traitement de la QoS

Lissage, marquage, ”policage” ;Reecriture ?

Deja faitPlus adapte !

Remplacement ?Choix des remplacants ?Plus perenne.



Dialogue emulation/prototypage

Flux de donnees / informations de controle ;Efficacite/mise en œuvre ;Impact des deux cotes ;TUN/TAP, Netfilter/libipq, netlink, appels systeme, . . .


Notes :

Notes :

Notes :


Quelle implantation ?

Actuellement : module applicatif dialogant avec le module de miseen œuvre de la QoS ;Transitoirement : le meme module controlant l’ordonnanceur ;Idealement : module proche de l’ordonnanceur.



[1] S. Blake, D. Black, M. Carlson, E. Davies, and Z. Wang January.RFC 2475 - an architecture for differentiated service.Informational, IETF, December 1998.

[2] B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin,S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson,K. Ramakrishnan, S. Shenker, J. Wroclawski, and L. Zhang.RFC 2309 : Recommendations on queue management andcongestion avoidance in the internet.Technical report, IETF, April 1998.Category : Informational.

[3] R. Braden, D. Clark, and S. Shenker.Integrated services in the internet architecture : an overview.Technical report, Internet Engineering Task Force, United States,1994.

[4] David D. Clark and Wenjia Fang.Explicit allocation of best-effort packet delivery service.



IEEE/ACM Trans. Netw., 6(4) :362–373, 1998.

[5] David D. Clark, Scott Shenker, and Lixia Zhang.Supporting real-time applications in an integrated services packetnetwork : Architecture and mechanism.In SIGCOMM, pages 14–26, 1992.

[6] A. Demers, S. Keshav, and S. Shenker.Analysis and simulation of a fair queueing algorithm.In SIGCOMM ’89 : Symposium proceedings on Communicationsarchitectures & protocols, pages 1–12, New York, NY, USA, 1989.ACM Press.

[7] Sally Floyd and Van Jacobson.Random early detection gateways for congestion avoidance.IEEE/ACM Transactions on Networking, 1(4) :397–413, 1993.

[8] Sally Floyd and Van Jacobson.Link-sharing and resource management models for packetnetworks.


Notes :

Notes :

Notes :


IEEE /ACM Transactions on Networking, 3(4) :365–386, 1995.

[9] Paul E. McKenney.High-speed event counting and classification using a dictionaryhash technique.Proceedings of the International Conference on ParallelProcessing, 3 :71–75, 1989.

[10] P.E. McKenney.Stochastic fairness queuing.In IEEE, editor, INFOCOM’90 proceedings, volume 2, pages733–740, June 1990.

[11] J. Nagle.On packet switches with infinite storage.Technical report, IETF, United States, 1985.

[12] J. B. Nagle.On packet switches with infinite storage.Innovations in Internetworking, pages 136–139, 1988.



[13] Abhay K. Parekh and Robert G. Gallager.A generalized processor sharing approach to flow control inintegrated services networks : the single-node case.IEEE/ACM Trans. Netw., 1(3) :344–357, 1993.

[14] M. Shreedhar and George Varghese.Efficient fair queueing using deficit round-robin.IEEE/ACM Trans. Netw., 4(3) :375–385, 1996.

[15] L. Zhang.Virtual clock : a new traffic control algorithm for packet switchingnetworks.In SIGCOMM ’90 : Proceedings of the ACM symposium onCommunications architectures & protocols, pages 19–29, NewYork, NY, USA, 1990. ACM Press.


Notes :

Notes :

Notes :

Documents

Introduction aux Mécanismes de Qualité de Servicechaput.perso.enseeiht.fr/supports/2007-2008/QoS...Fondee sur des informations contenues dans les paquets´ Necessaire du fait de