Performances et QoS
Chapitre 1
Qualité de Service
Jürgen Ehrensberger IICT/HEIG
1-QoS.ppt
Définition QoS Recommandation E-800 de l’UIT-T « La Qualité de Service est l'effet collectif des performances d'un services qui détermine le degré de satisfaction de l'utilisateur du service. » – N’est pas liée à des mécanismes particuliers – La QoS de cette définition est difficile à quantifier Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
2
Service Level Agreement Un SLA est établi entre un fournisseur de service et un client – Définit les paramètres de performances du service offert – Définit la disponibilité du service « Carrier grade »: Five nines (99,999%) – Les performances spécifiées ne sont pas respectées pendant au maximum 5 minutes par an
– Mesurable N’est plus basé sur la ‘satisfaction’ de l’utilisateur
Problème : Quelle performance est nécessaire ? Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
3
Paramètres de performances Différentes définitions existent – UIT-T Æ téléphonie, réseaux des opérateurs – IETF Æ Internet Groupe de travail IETF: – IPPM: IP Performance Metrics – Définit les paramètres de performances et les méthodes de mesure
Paramètres les plus importants – – – –
One-way Delay : délai de transit One-way Delay Variation : Variation du délai de transit One-way Packet Loss : Taux de perte unidirectionnel Débit ??? Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
4
Délai de transit Définition (OWD, One-way delay): « Le délai de transit d'un paquet à travers un réseau complet est donné par le temps entre l'émission du premier bit du paquet par la source et la réception du dernier bit du paquet par le destinataire. » (RFC 2679) – Paquet perdu Æ OWD = ∞
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
5
Composants du OWD Délai de traitement: Délai de calcul nécessaire à un noeud –
Vérification de la somme de contrôle, acheminement, ...
–
De l’ordre de microsecondes
Délai d’attente: Si la ligne de sortie est occupée, le paquet doit attendre dans un tampon de transmission, derrière les autres paquets –
De l’ordre de 1 – 100 ms par noeud
Délai de transmission: Temps nécessaire pour placer les bits d’un paquets sur la ligne, à un débit fixe –
Dtrans = L / R
(L: longueur du paquet, R: débit en bits/s)
–
De l’ordre de 1 µs – 1 ms
Délai de propagation: Délai du signal physique entre l’émetteur et le récepteur –
Dépend de la vitesse de propagation du signal (200’000 – 300’000 km/s)
–
Peut être important dans les réseaux WAN (40 ms sur la fibre optique transatlantique)
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
6
Variation du délai de transit Définition (OWDV, One-way delay variation): « La variation du délai de transit est définie pour une paire de paquets P1 et P2. Elle est donnée par la différence des délais de transit des deux paquets : OWDV(P1, P2) = OWD(P2) − OWD(P1). » (RFC 3393) – Peut être positive ou négative – P1 ou P2 perdu Æ OWDV = ∞ Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
7
Variation maximum absolue du délai de transit Définition: « Considérons n mesures du délai de transit OWD1, . . . ,OWDn. La variation maximum absolue du délai de transit est donnée par OWDVmax = max(OWD1,...,OWDn) − min(OWD1,...,OWDn). » – Estimation de la partie variable du délai de transit – Souvent appelée gigue ou jitter Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
8
Taux de perte unidirectionnel Définition (One-way packet loss average): « Soit T un intervalle de temps T = [t1, t2] et S = {P1, . . . , Pn} la séquence des paquets émis pendant l'intervalle T. Un paquet est considéré comme correctement reçu, s'il arrive sans erreurs et après un délai de transit maximum OWDmax défini. Le taux de perte unidirectionnel, mesuré sur l'intervalle T, est défini comme le rapport entre le nombre de paquets expédiés dans l'intervalle T et le nombre de paquets correctement reçus. » (RFC 2680) – Tient compte du fait qu’il est difficile de distinguer un paquet perdu d’un paquet lent Applications multimédia (UDP) : imposent un OWDmax fixe Transfert de fichier (TCP) : OWDmax = délai de retransmission Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
9
Débit de transmission Difficile à donner une définition qui permet une mesure – Débit UDP ≠ débit TCP – Débit flux TCP court ≠ débit flux TCP long
Définition (Débit de transmission et throughput) : « Le débit de transmission d'un flux est défini comme le nombre de bits émis pendant un intervalle de temps divisé par la longueur de l'intervalle. » « Le throughput d'un flux est défini comme le nombre de bits correctement reçus pendant un intervalle de temps divisé par la longueur de l'intervalle. Des paquets qui sont reçus corrompus ou dupliqués ne sont pas comptés. » Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
10
Mesures des paramètres de performances Mesure passive – Observe les paquets à plusieurs endroits dans le réseau – Évite des perturbations avec du trafic de test
Mesure active – Injecte du trafic de test et mesure les performances obtenues – Permet des mesures mieux contrôlées Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
11
Mesure passive Identification des paquets – Un paquet doit être intercepté et identifié à plusieurs points de mesure (p.ex. entrée et sortie) – Solution simple: fonction de hachage
Calcule un identificateur unique Collisions des identificateurs possibles mais probabilité négligeable
– Permet l’échantillonnage
Synchronisation des points de mesure – Nécessaire pour le calcul du OWD – Avec un récepteur GPS
Précision de l’ordre de nanosecondes Bonne réception uniquement à l’extérieur
– Avec un récepteur DCF77
Utilisé par les horloges radio-contrôlées Synchronisation avec ±5 ms de précision Réception peu stable, perturbée par les équipements électroniques
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
12
Mesure active Injecter des paquets de test qui échantillonnent les performances observées par le trafic normal Comment éviter un biais des résultats de l’échantillonnage?
PASTA (Poisson Arrivals See Time Average) « Sous des conditions très générales et pour un système quelconque, les arrivées d'après un processus de Poisson observent l'état du système avec une probabilité qui est asymptotiquement égale à la fraction de temps que le système passe dans cet état. »
Échantillonnage poissonnien – Interarrivée des paquets selon une distribution exponentielle avec une fréquence λ – Taille de paquet fixe ou variable Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
13
Besoins de QoS La satisfaction de l’utilisateur détermine la QoS requise pour chaque application Objectifs des mécanismes de QoS: Offrir une QoS adéquate à chaque application, sans gaspiller des ressources
Approche par surdimensionnement Offrir la même QoS excellente à toutes les applications
Applications à considérer – Streaming multimédia – Applications multimédia interactives – Transfert de fichiers Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
14
Streaming multimédia Vidéo à la demande (VoD), Télévision sur IP (IPTV) et streaming audio Caractéristique principale – Le récepteur doit reproduire le signal analogique avec une fréquence constante ¾ Un paquet qui arrive trop tard ne pourra pas être utilisé ¾ Le récepteur doit égaliser les variations de délai à l’aide d’un tampon de lissage Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
15
Tampon de lissage Le récepteur remplit le tampon à moitié au début de la transmission Les paquets sont lus à une fréquence constante du tampon Introduit un délai supplémentaire Récepteur
Source
Flux synchrone
Réseau
Tampon de lissage
Flux synchrone
Délais de transit variables
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
16
Dimensionnement du tampon de lissage Dépend de la variation maximum absolue du délai de transit ∆ Taille du tampon = 2 ∆ R
(R: débit)
– Le premier paquet a un délai inconnu OWD1 – Temps de restitution :
OWD1+ ∆
Effet – Le tampon ne sera jamais vide : OWDmax = OWDmin+ ∆ ≤ OWD1+ ∆
– Le tampon ne déborde jamais : OWDmin = OWDmax- ∆ ≥ OWD1- ∆ Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
17
Conséquences pour les mécanismes de QoS et les méthodes d’évaluation Le délai de transit moyen ne permet pas de dimensionner le tampon de lissage Il faut connaître – Les valeurs extrêmes ou – Les percentiles de la distribution
QoS déterministe OWD ≤ OWDmax
pour tous les paquets
QoS statistique P[OWD > OWDmax] ≤ ε
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
18
QoS pour le streaming multimédia Variation du délai de transit – Doit être limitée à une valeur maximum
Délai de transit – Peu important
Taux de perte – Dépend du codec voix/vidéo – En général ~1% de perte est tolérable
Débit de transmission – Dépend du codec – Voix: débit constant faible – Vidéo: débit très variable (facteur 10-20) Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
19
Applications multimédia interactives Voix/téléphonie sur IP (VoIP), Conférence vidéo et Jeux d’action en ligne Caractéristiques principales – Flux multimédia Æ tampon de lissage – Interactivité Æ Délai de transit court
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
20
Délai de transit Un délai de transit trop long rend l’interaction difficile (effet talkie-walkie) Recommandation UIT-T G.114 – Référence souvent citée – Basée sur une étude de perception subjective de la QoS – Recommandations : OWD ≤ 150 ms est à peine perceptible OWD ≤ 400 ms est perceptible mais normalement acceptable OWD > 400 ms n’est acceptable que dans des cas exceptionnels
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
21
Qualité subjective de la VoIP Dépend du codec, du délai de transit et des pertes Modèles
5.0 Excellent
4.5
E-Model
Qualité PSTN
Bon
4.0
Quelques utilisateurs non satisfaits
– Recommandation UIT-T G.107 MOS
3.5
– Calcule un facteur R dans [0, 100]
Beaucoup d’utilisateurs non satisfaits Presque tous les utilisateurs non satisfaits
3.0 2.5
Mean Opinion Score (MOS)
Non recommandé
2.0
– Recommandation UIT-T P.800
1.5
– Calcule une valeur MOS dans [0, 5]
1.0 0
10
20
30
40
50
60
70
80
90 100
Facteur R
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
22
Influence du codec et du délai de transit Les codecs ont une QoS intrinsèque, en fonction du taux de compression – G.711: MOS=4.5 – G.729: MOS=4.2
Les codecs ont une sensibilité différente par rapport aux délais – G.711: MOS=3.8 à 300 ms OWD – G.723 à 5.3 kb/s MOS=3.6 à 100 ms OWD Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
23
Influence du délai et des pertes
Méthodes de masquage de perte de paquets – Insertion de bruit – Répéter le dernier paquet – Interpolation
Des pertes de paquets isolées sont à peine perceptibles – Les rafales de pertes conduisent à une forte dégradation
G.711 (avec masquage)
Jürgen Ehrensberger
G.729 (avec masquage)
IICT/HEIG
Cours PQS
1-Qualité de Service
24
Applications de transfert de fichiers
Le Web
L’e-mail et
Le P2P
La satisfaction de l’utilisateur dépend du délai de transfert du fichier – Paramètre de performance: throughput
Objectifs de l’allocation des ressources 1. Répartition équitable de la capacité entre les flux 2. Utilisation efficace des ressources Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
25
Flux élastiques et non élastiques Flux élastiques – Utilisent un contrôle de congestion qui adapte le débit de transmission à la charge du réseau – Contrôle de congestion de TCP Congestion légère (perte isolée Æ acquittements dupliqués): Décroissance multiplicative puis évitement de congestion Congestion sévère (plusieurs pertes dans une fenêtre Æ timeout du temporisateur): Décroissance multiplicative puis démarrage lent
Flux non élastiques (UDP) – La source impose un débit fixe
Problèmes avec les flux non élastiques – Ils mettent en danger la stabilité du réseau – Ils monopolisent la capacité du réseau – Ils peuvent diminuer l’efficacité de l’utilisation des ressources Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
26
Exemple des effets de flux non adaptatifs Scénario
3 connexions TCP
S1
– 3 flux TCP – 1 flux UDP – Le flux UDP traverse un lien à 128 kb/s
10 M
D1 b/s
R1 S2
1.5 Mb/s
b/s 10 M
R2
b/s 10 M
128
kb/s
1 flux UDP
D2
Effet de l’augmentation du débit UDP – Le lien R1-R2 sature – Le débit des connexions TCP diminue – Les paquets UDP sont perdus sur R2-D2 – Le throughput total du réseau diminue
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
27
Solutions pour la cohabitation TCP-UDP 1. Gestion active des files d’attente – Un routeur pourrait détecter les flux trop agressifs et supprimer les paquets pour augmenter l’équité – Problèmes
Devrait tenir compte de flux individuels Comment définir l’agressivité d’un flux
2. Ordonnancement – Gérer des files d’attentes différentes pour le trafic élastique et non élastique – Sera discuter dans le chapitre 3
3. Contrôle de congestion pour les flux UDP – Nouveau protocole DCCP (Datagram Congestion Control Protocol) – Control de congestion similaire à TCP ou avec moins de variations du débit Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
28
Équité et efficacité
Les mécanismes de QoS et de contrôle de gestion ont deux buts 1. Répartition équitable des ressources
Pour donner une QoS équitable à chaque flux
2. Utilisation optimale de ressources
Pour maximiser la QoS globale
Problèmes – Qu’est-ce qu’une répartition équitable ? – Les deux objectifs sont conflictuels ! Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
29
Exemple I: Maximisation du throughput n0 flux du type 0 avec un débit r0
Lien i avec capacité c
Noeud 1
Noeud 2
Noeud 3
Noeud 4
ni flux du type i avec un débit ri
Contrainte : Throughput total du réseau :
¾ Devient maximum pour r0 = 0 ! Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
30
Exemple II: Équité simpliste : Parts égales 1 flux du type 0 avec un débit r0
Liens avec capacité c
Noeud 1
Noeud 2
1 flux du type i avec un débit ri
Noeud 3
9 flux du type i avec un débit ri
Objectif : Chaque flux reçoit la même part de la capacité
Lien 2 (10 flux) : – Chaque flux du type 0 et du type 2 reçoit c/10
Lien 1 (2 flux) : – Le flux du type 1 doit recevoir le même débit comme type 0 – Le lien est utilisé à 20%
¾ Le throughput total peut être augmenté sans pénaliser le type 0 Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
31
Equité Max-Min Idée : – Une allocation de ressources est équitable si on ne peut augmenter les ressources allouée à un utilisateur qu'au prix d'une diminution des ressources déjà inférieures d'autres utilisateurs.
Définition : Équité max-min Soit r le vecteur de l'allocation des ressources des utilisateurs. Une allocation réalisable est max-min équitable si et seulement si pour toute autre allocation réalisable s, si si > ri pour un utilisateur i, alors il existe un j tel que rj ≤ ri et sj < rj .
Si une allocation max-min équitable existe, elle est unique Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
32
Modèle de réseau
Modèle – Sources s = 1, ...,S avec un débit rs – Liens l = 1, ...,L avec une capacité cl – Coefficients de routage Al,s : la part du débit de la source s qui traverse le lien l
Modèle générique – Permet du load-balancing – Permet le multicast – Permet de tenir compte de l’encapsulation/tunnels
Théorème : (Allocation unique max-min équitable) Pour le type de réseau défini ci-dessus, avec des coefficients de routage Al,s fixes, il existe une allocation max-min équitable qui est unique. Elle peut être trouvée avec l'algorithme de remplissage progressif. Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
33
Goulot d’étranglement Définition : (Goulot d'étranglement, bottleneck link) Un lien l est un goulot d'étranglement pour la source s si et seulement si 1. le lien l est saturé : cl = ∑i Al,i ri, 2. la source s sur le lien l a le débit maximum parmi toutes les sources qui utilisent ce lien l : rs ≥ rs’ pour toutes les sources s’ avec Al,s’ > 0.
Théorème : Une allocation réalisable de débits r est max-min équitable si et seulement si chaque source a un goulot d'étranglement. Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
34
Algorithme de remplissage progressif 1.
Les débits de toutes les sources sont initialisés à 0
2.
Pour toutes les sources dont le débit n’a pas été bloqué 1.
Augmenter les débits en parallèle jusqu’à ce qu’un ou plusieurs liens soient remplis
2.
Le débit des sources qui traversent ce lien reste alors fixe
Après l’algorithme –
Chaque source utilise un lien saturé
–
Les débits des autres sources qui utilisent ce lien sont égaux ou plus petits
¾
Chaque source a un goulot d’étranglement
¾
L’allocation est max-min équitable
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
35
Exemple n0 flux du type 0 avec un débit r0
Lien i avec capacité c
Noeud 1
Noeud 2
Noeud 3
Noeud 4
ni flux du type i avec un débit ri
Contrainte:
pour tous les i
Le premier lien saturé i0 est celui avec le plus grand nombre de flux ni0 – Alors r0 = c / (n0 + ni0 ) – Puis Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
36
Exemple cont. Si tous les ni sont égaux : – Toutes les sources obtiennent le même débit r :
c c r0 = = n + n 2n – Capacité maximale :
c − n (c / 2 n ) c ri = = n 2n
∑ c = (L + 1)c i
– Throughput total:
∑r
i
( L + 1)c =
i
2
¾ L’équité max-min ne tient pas compte du fait que les flux du type 0 utilisent plus de ressources du réseau ¾ Elle peut conduire à une faible utilisation du réseau Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
37
Équité proportionnelle
Développée comme modèle économique Idée : – Une allocation est équitable si pour augmenter le débit d'une source on doit enlever une proportion moyenne plus grande des autres sources
Théorème : Une allocation de débits r est proportionnellement équitable si et seulement si pour toute autre allocation réalisable s :
Théorème : Il existe une allocation unique qui est proportionnellement équitable. Elle peut être trouvée en maximisant J(r) := ∑i ln(ri) sur l'ensemble des allocations réalisables. Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
38
Exemple n0 flux du type 0 avec un débit r0
Lien i avec capacité c
Noeud 1
Noeud 2
Noeud 3
Noeud 4
ni flux du type i avec un débit ri
Contrainte:
pour tous les i
Maximiser
c sur les valeurs 0 ≤ r0 ≤ n0 Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
39
Exemple cont. Dérivée : Maximum pour et
Pour ni = 1:
et
¾ Les sources de type 0 obtiennent un débit inférieur comme elles utilisent plus de ressources I
¾ Throughput total :
∑ r = c(I −1) i
i =0
Jürgen Ehrensberger
IICT/HEIG
Cours PQS
1-Qualité de Service
40