Approches (m,k)-firm pour

la gestion de la QdS temps réel

D’après travaux communs avec:– Anis Koubâa (thèse en 2004)– Jian Li (thèse en cours)

Yeqiong SONG, LORIA-INPL

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 2

Plan• Notions préliminaires: modèles de contraintes

temps réel dur, souple et (m,k)-firm• Ordonnancement sous contrainte (m,k)-firm: un

état de l’art• (m,k)-firm et QdS dans les réseaux

– Control d’admission– Gestion de la congestion (surcharge)

• Application à la transmission des flux MPEG• (m,k)-firm permet-elle de diminuer la demande de

ressource par rapport à (k,k)-firm ?

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 3

(m,k)-firm

• Temps réel dur: non respect d’une échéance entraîne des conséquences catastrophiques

• Temps réel souple: non respect des échéances entraîne une diminution de performances (QdSdégradée)– Temps réel « firm »: temps réel souple mais avec le non

traitement des invocations ne pouvant pas respecter leur échéances (invocations écartées)

– (m,k)-firm: respect des échéances d’au moins m parmi kinvocations consécutives quelconques [Hamdaoui95]

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 4

(m,k)-firm et états du system

• Exemple de (2,3)-firm• k-séquence

1111

1100

101

100

1

0

011

010

001

000

0

1

0

1

0

1

0 11

0

10

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 5

k-séquence et expression de contraintes

(3,5)-firm- k-séquence fixe = k-pattern

1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 . . .

1 0 0 1 1 1 0 1 0 1 1 1 0 1 0 ...

- k-séquence dynamique

Un système exécutant tous les m « 1 » du k-pattern respecte la contrainte (m,k)-firm. La réciproque n’est pas vraie.

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 6

Garanties du respect des contraintesDéterministe

TR dur:P[temps de réponse ≤ échéance] = 1

(m,k)-firm:P[temps de réponse de m parmi k consécutives ≤ échéance] = 1

En moyenne et probabilisteTR souple:

temps moyen de réponse ≤ échéanceP[temps moyen de réponse ≤ échéance] = 1-ε

(m,k)-firm: temps de réponse de m parmi k consécutives ≤ échéance

P[temps de réponse de m parmi k consécutives ≤ échéance] = 1 -ε

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 7

Modèle

• Partage de serveur avec des sources sous contrainte (mi,ki)-firm

Serveur

FIFOSource

...

(m1,k1)

(m2,k2)

(mN,kN)

c

Ordonnancement non préemptifdes clients en tête des files

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 8

Questions qu’on se pose

• Quelles applications sous contraintes (m,k)-firm

• Quels algorithmes d’ordonnancement• Quels avantages

– Si garantie en moyenne et probabiliste, relaxation de demande de ressources

– Si garantie déterministe, relaxation de demande de ressources dans certains cas

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 9

Pourquoi s’intéresser à (m,k)-firm

• Temps réel dur sur-dimensionne le système car on considère le pire cas (en cas normal, ressources sous-utilisées)

• Dans la pratique, bon nombre de systèmes classés temps réel dur ne sont pas si « dur». Le non respect occasionnel des échéances peut être toléré si correctement distribué (e.g. Transmission de paquets audio/vidéos, contrôle-commande sur-échantillonné)

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 10

Pourquoi s’intéresser à (m,k)-firm

• Exemple de flux vidéo MPEG

IB B B

PB B

PB B

PB

IB B B

PB B

PB B

PB

1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 11

Maquette de tests

Routeur ClickCommutateur

LAN 1Commutateur

LAN 2

LAN 1 100 Mbits/s

Netmask = 255.0.0.0

LAN 210 Mbits/s

Netmask = 255.255.255.0

Lien 1 100 Mbits/s

Lien 2 10 Mbits/s

Serveur 1 @IP : 10.0.0.2

Serveur 2@IP : 10.0.0.3

Client 1 @IP : 192.168.1.2

Client 2@IP : 192 .168 .1.3

VideoLan : générateur de trafic MPEG

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 12

Test sur maquette

• Vidéo initiale:

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 13

• Test 1: rejet de tous les paquets de type I

Image fixe

Test sur maquette

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 14

• Test 2: rejet de tous les paquets de type P

Test sur maquette

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 15

• Test 3: rejet de tous les paquets de type B

Test sur maquette

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 16

QdS selon le modèle (m,k)-firm

• Adopter (m,k)-firm permet d’une souplesse de garantie entre (k,k)-firm et (m,k)-firm (avec m < k)

• En plus, un algorithme d’ordonnancement en-ligne facilitera la gestion dynamique des différents niveaux de QdS (par contrôle d’admission)

• QdS selon le modèle (m,k)-firm peut être intégrée dans OS TR [West02] et Internet (e.g. Intserv et Diffserv pour améliorer RED, WFQ, …) [Wang01], [Koubâa04] pour une meilleure performance temporelle.

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 17

Problème et état de l’art• Problème: algorithmes nouveaux (autres que RM,

FP, EDF, WFQ, etc.) pour prendre en compte la contrainte (m,k)-firm

• Algorithmes pour (m,k)-firm– DBP (Distance based Priority) [Hamdaoui95]– DWCS (Dynamic Window-Constrained Sched.)

V1[West99], V2[West04]– ERM (Enhanced Rate Monotonic), [Ramanathan99]– EFP (Enhanced Fixed-Priority), [Quan00]

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 18

DBP (Distance based Priorité)

• DBP d’une k-séquence est définie comme le nombre des échéances non respectées consécutives (nombre de zéros) conduisant à un état d’éche

• Exemple de (3,5)-firm– (11011) a DBP = 2 car 11(01100)– (10111) a DBP = 3 car 101(11000)– (10001) a DBP = 0

• L’affectation de priorité dans DBP est dynamique (qui dépend de k-séquence)

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 19

DBP dans notre modèle

• Une source est caractérisée par:• DBP peut être implémenté matériellement par un registre• En cas d’égalité de priorité DBP, EDF par défaut

{ }, , , ,i i i i i ic T D m kτ =

),,,( 111

111 iiki δδδ −+−

),,,( 221

212 iiki δδδ −+−

21

22

23 ,,, +++ iii jjj

),,,( 11N

iN

iN

ki N δδδ −+−

Ni

Ni

Ni jjj 123 ,,, +++

11

11, ++ ii pj1

11

21

3 ,,, +++ iii jjj

21

21, ++ ii pj

Ni

Ni pj 11, ++

DBP

DBP

DBP

Serveur

...

...

1τ

Nτ

2τ

xij : ième client de source x x

ip : priorité de ième client de source x

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 20

y=y-1x=x

y=y-1x=x-1

DWCS

• Garantie (x,y): au maximum x échéances dépassées dans une fenêtre fixe de y [West99]

• Priorité selon le facteur de perte: Wi = xi/yi

1110000111y y

x xEquivalence dans une fenêtre glissante:pas plus de 2x échéances dépassées y+x i.e. (y-x, y+x)-firm

1001000111y y

0101010110

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 21

(m,k)-WFQ [Thèse d’Anis Koubâa]

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 22

WFQ

P21P22P23P24P25

WFQ

3Φ =

1Φ =

P11P12P13P14P15P16

Flux 1 : 3 Mbit/s

Flux 2 : 1 Mbit/s

P11P12P13P21P14P15P16P22

P17P18P19

P23P24P25D2

D1

{ }1max , ( )k

k k j

j j

j

LF F V t−

Φ= +Temps Virtuel de DTemps Virtuel de Déépartpart

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 23

WFQ et temps de réponse borné

• WFQ garantit à chaque source de flux τi– une portion de bande passante gi

proportionnelle à son coefficient de partage Φi

– un délai maximal ssi le trafic du flux est borné par une courbe d’arrivée (σi,ρi)-borné et avec ρi ≤ gi :

max,max

ii

i

LDg cσ

= +

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 24

Problème de WFQ pour temps réel• WFQ est initialement conçue pour garantir la

bande passante mais pas le délai !• Pour un flux donné, plus le coefficient de partage

est petit, plus le délai est grand– Problème : flux temps-réel de faible besoin en bande

passante, mais nécessitant un délai étroit (Voix sur IP avec Débit=64Kb/s)

• Sous-utilisation de ressources si garantir le délai– Borne sur le délai = f(Bande passante réservée, Rafale)

max,max

ii

i

LDg cσ

= +

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 25

(m,k)-WFQ

• Objectifs de (m,k)-WFQ:– Prise en compte de (m,k)-firm– Utilisation plus efficace de la bande passante

pour réduire Dmax

• Principe de (m,k)-WFQ:– Marquage des paquets par la source selon κ-

pattern (introduction de deux priorités)– Estampillage des paquets selon le temps virtuel

de départ de WFQ

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 26

Algorithme (m,k)-WFQ

Paquet Critique Paquet Optionnel

Echéance RatéeEchéance Respectée

Envoyer le paquet Rejet du paquet

Sélection min(Fik)

parmi les paquets critiquesSinon parmi les paquets optionnel

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 27

Un exemple

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 28

(m,k) Débit Trafic κ-pattern Echéance Voix (4,5) 64 kb/s ON/OFF (500/755/50)ms 11011 10 ms

Vidéo (3,5) 2Mb/s Pseudo Périodique ~2Mb/s 10110 4 ms FTP (0,1) 7,936 Mb/s Pseudo Périodique ~7.936 Mb/s 0 Infinie

Performances de (m,k)-WFQ

Taille de paquet constante = 1 Ko

(m,k)-WFQ WFQ (m,k)-FIFO FIFOVoix 9,769 4776,83 20,529 48,031Vidéo 3,999 41,084 21,086 49,031FTP 3,837 18,048 21,442 49,083

Temps de réponse maximal simulé :

Taux de rejet (m,k)-WFQ: Voix: 6,8%Vidéo: 5,5%

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 29

Garantie de temps de réponse de (m,k)-WFQ

S

t

bitsρ

σ

((σ,ρσ,ρ))--ShaperShaper

(m, k)(m, k)--FiltreFiltre

Flux CritiqueFlux Critique

(k(k--m,k)m,k)--FiltreFiltre (b,(b,ρρ))--ShaperShaperkk--mmkk

Flux OptionnelFlux Optionnel

*R (t)MUXMUX

σ ρ⎛ ⎞⎜ ⎟⎝ ⎠

−+∼*( ) , m k mR t bk k

R(t)

(σ,ρ)

Le nombre maximum de paquets optionnels transmis par le serveur est l’ensemble des paquets ayant un délai inférieur àl’échéance désirée Dop : b = ρDop ≤ σ(supposons que la bande passante du serveur g = ρ)

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 30

Borne de temps de réponse de (m,k)-WFQ

• Les deux systèmes suivants sont équivalents• servi par un serveur WFQ• servi par un serveur (m,k)-WFQ

• Borne sur le délai d’un flux (σ,ρ)-borné servi par (m,k)-WFQ

σ ρ⎛ ⎞⎜ ⎟⎝ ⎠

−+∼*( ) , m k mR t bk k

( )σ ρ∼( ) , R t

σρ= +

** maxmax

LD C

σρ ρ

−= + +* maxmax

Lm k mbD Ck k

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 31

Borne de temps de réponse de (m,k)-WFQ

• Si aucun paquet optionnel n’est servi:

• Pour garantir un temps de réponse entre D*min et D*max, on peut ajuster Dop qui détermine b = ρDop

σρ= +* max

minLmD Ck

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 32

DDéélai Garanti par (m,k)lai Garanti par (m,k)--WFQWFQ

*( , )

*max

maxσρ

− = +m k WFQ LD C( , ) maxmax λ σ λρ ρ

− = + +M Om k WFQ LbD C

WFQ

maxmax

σρ= +WFQ LD C

σ

ρ

Temps (sec)

Arrivées (bits)

DWFQ R

T= Lmax/c

Courbe de Service

Courbe d’arrivée

Le flux est (σ,ρ)-borné

(m,k)-WFQ

σ

ρ

Temps (sec)

Arrivées (bits)

DWFQ R

T= Lmax/c

Courbe de ServiceCourbe

d’arrivée

D(m,k)-WFQ

ρ∗

σ∗

Le flux est (σ∗,ρ∗)-borné

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 33

Garantie déterministe de (m,k)-firm [Thèse de Li]

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 34

Garantie déterministe de (m,k)-firm

11

Ni i

i i i

c mT k=

⎡ ⎤≤⎢ ⎥

⎣ ⎦∑ au lieu de

11

Ni

i i

cT=

⎡ ⎤≤⎢ ⎥

⎣ ⎦∑Charge:

Garantie déterministe de (k,k)-firm donnée par condition suffisante de [Jeffay91]

Question: (m,k)-firm permet-elle de relaxer la demande de ressources par rapport à (k,k)-firm?

Analyse de l’ordonnançabilité sous contrainte (m,k)-firm

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 35

Condition suffisante pour DBPCondition suffisante est donnée pour l’ensemble de flux périodique ou sporadique sous contrainte (m,k)-firm[Li04, WFCS04]

0

5

10

15

20

25

30

35

0 5 10 15 20

(m,k)-firm (k,k)-firm

Cumulative workload

t

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 36

Problème de garantie déterministeIl est toujours possible de trouver un ensemble de (mi,ki) qui impose le service de tous les clients pendant la pire période occupée dans le cas généralNous ne pouvons pas améliorer la condition de Jeffay [DEA

LI]

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 37

Problème de garantie déterministe

• Une condition suffisante pour DWCS est donnée [West04] avec des hypothèses particulières (même Ci et Ti= qCi)

• [Mok01] a prouvé qu’un ensemble de sources périodiques peut ne pas être ordonnançable sous DWCS même avec une charge arbitrairement faible.

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 38

Conclusion et perspectives• Le modèle (m,k)-firm permet de fournir une

certaine souplesse dans la fourniture de la QdS. Exemple: (m,k)-WFQ [Koubâa04]

• Problème de garantie déterministe de (m,k)-firm est NP-dur ([Quan00], [Mok01], [Li03]) relaxation de demande de ressource n’est pas toujours possible

• Travaux futurs: – mécanismes protocolaires de gestion de QdS dans

l’architecture Diffserv– D’autres pistes pour relaxer la demande de ressource

ETR’2005, Nancy, 13-16 sept. 2005 Y.Q. Song 39

Questions?