Algotel 2004 -- 28/05/041

Modélisation analytique des algorithmes d’ordonnancement GPS & WFQ

BOCKSTAL Charles, GARCIA J.M. et BRUN Olivier

Algotel 2004 -- 28/05/042

Plan de l’exposé

Qualité de service dans les réseaux IP

Modélisation stationnaire de GPS/WFQ

Conclusion et perspective

Algotel 2004 -- 28/05/043

Qualité de service Pourquoi ?

• Applications types voix, vidéo, multimédia interactif. • Contrainte en terme de délai, de perte, de gigue…

Objectif :

• Contrôle partiel des ressources du réseau.• Garanties de performance.

Réalisation : Architecture DiffServ

• Agrégation de flux en classe de service.• Traitements différentiés via l’ordonnanceur (GPS – WFQ)

Algotel 2004 -- 28/05/044

Description du système:

File GPS/WFQ

• K files d’attente : Isolation des classes de service.

• Garantir un pourcentage k minimum de bande passante par file à tout instant.• Partage du surplus de bande passante en fonction des poids.

• General Processor Sharing (GPS) : algorithme idéal (paradigme)

Vision fluidique du trafic. Traitement en parallèle.

• Weighted Fair Queueing Implémentation réelle: même ordre de sortie des paquets que GPS

Algotel 2004 -- 28/05/045

Hypothèses de modélisation:

File GPS/WFQ

1

2

3

Files d’attente

Serveur

1

2

3

K files d’attente Pondérations GPS/WFQ k

Sources poissonniennes d’intensité k

Taux de service exponentiel global

Le facteur d’utilisation k=k/On cherche le nombre de client Xk de la classe k dans le système

Algotel 2004 -- 28/05/046

Observation : un exemple à 2 classes

Linéarité de la charge en fonction des poids des algorithmes GPS/WFQ Comportement limite (k=1)

• File idéalement isolée GPS => M/M/1• File non idéale WFQ => Priorité non préemptive

λ0 = 0.1λ1 = 0.2μ = 1

φ1 = 1 - φ0

φ0 [0.05..0.95]

Algotel 2004 -- 28/05/047

GPS à deux classes

1

11

10 11limlim

1

k

kkkk XXXX

kk

Comportement aux limites:

k

kkX

k

1lim

1

Charge global du système:

Algorithme conservateur de travail Comportement global M/M/1

110

1

0

XXXXK

kkLa charge globale s’écrit :

Quand le poids k tends vers 1, la file k se comporte comme si elle était seule.

La charge de cette file s’écrit alors :

Quand le poids k tends vers 0, les paquets de la file k occupent ce qui reste :

Algotel 2004 -- 28/05/048

GPS à deux classes

11111 1

1

1

1

k

kk

k

k

k

kkX

L’expression de la charge Xk d’une file d’attente pour des charges peu importante est quasi linéaire par rapport aux pondérations de GPS.

L’équation est de la forme :

kkkk BAX

En résolvant le système, on obtient :

Algotel 2004 -- 28/05/049

GPS à deux classes : Résultats

λ0 = 0.1λ1 = 0.2μ = 1

λ0 = 0.5λ1 = 0.05μ = 1

Comparaison entre l’approximation analytique et l’intégration de la chaîne de Markov Charges des deux files en fonction de φ0

Résultats convenables même pour des systèmes déséquilibrés

Algotel 2004 -- 28/05/0410

GPS à K classes

1

1

0

K

kkXX

k

kk

K

ki

ii XXX

kk

11

limlim1

1

01

Comportement aux limites :

k

kkX

k

1lim

1Quand k→1, la file k se comporte comme si elle était seule:

Les autres files ont le nombres de paquets restants:

Problème : nous ne connaissons que les ressources occupées par l’agrégat des files restantes.

Charge global du système :

Algotel 2004 -- 28/05/0411

GPS à K classes

kkjkkjk

jkK

jjkk

k

kkk ZZZX

,

2

1 111

1

0,

K

kj

jjiki kiX ki

k

ki

k

,11

lim ,1

L’idée : repartir la charge restante proportionnellement au débit moyen des trafics.

Justification : les poids des files restantes sont égaux (→0) et si l’on considère l’agrégation de ces files, elles se comportent comme une file Mk/M/1

On a alors : avec

En résolvant le système comme précédemment, nous trouvons que :

)1(,)1(

)1(

11

Kkk

Kk

KkkZ

avec

Algotel 2004 -- 28/05/0412

Evaluation GPS linéarisé: erreur relative

= 0.2

Bonne approximation sur tout le domaine des pondérations

Algotel 2004 -- 28/05/0413

Modélisation de WFQ

*

1

0

1 1lim k

k

K

jjk

kk NXk

File prioritaire:

Différence avec GPS: Non fluidique

Lorsque le poids d’une file tends vers 1, ces performances ne peuvent être meilleures que celle d’une file prioritaire non préemptive

On utilise l’équation d’une file prioritaire

On garde les mêmes équations en intégrant l’équation de la file prioritaire

Algotel 2004 -- 28/05/0414

WFQ : Résultats

λ0 = 1λ1 = 0.5

μ = 5λ2 = 0.3

λ0 = 0.3λ1 = 0.5

μ = 5λ2 = 1

Comparaison entre l’approximation analytique et la simulation événementielle

Charges des trois files, φ0 variant entre [0.05..0.85], φ1 = 0.9 - φ0 et φ2 = 0.1

Résultats convenables

Algotel 2004 -- 28/05/0415

Conclusion

Qualité de service dans IP

• Importance des algorithmes GPS et WFQ pour la QoS.• Pas de modèle exact pour K classes.

Approximation du régime stationnaire

• Pour GPS et WFQ à K classes avec loi d’arrivée et de service exponentielles.• Évaluation rapide de performance (boucle d’optimisation).• Intégré dans un logiciel d’évaluation de performance de réseau (DHS).

Algotel 2004 -- 28/05/0416

Perspective

Développements déjà réalisés

• Étendu à des lois de service générales avec taux de service par classe et par type de flux (file Mk/Gk/1).

• Algorithme d’ordonnancement avec N files prioritaires + K files WFQ.

• Étude de scénario de panne et routage dynamique (modèle transitoire).

Problème à résoudre

• Modèle avec capacités finies (pertes).• Loi d’arrivée complexe (ON-OFF, TCP, générale).• Réseau de file d’attente (interconnexion)

Algotel 2004 -- 28/05/0417

Merci

Algotel 2004 -- 28/05/0418

Régime transitoire : Résultats WFQ 3 classes

λ0 = 0.3 et φ0=0.45λ1 = 0.5 et φ1=0.45

μ = 5λ2 = 1 et φ2=0.1

λ0 = 0.5 et φ0=1/9λ1 = 1 et φ1=3/9

μ = 5λ2 = 1.5 et φ2=5/9

Résultats convenables