Maîtrise de la dimension temporelle de la qualité de service dans les réseaux

1

Maîtrise de la dimension temporellede la qualité de service dans les réseaux

Thèse de doctoratUniversité Paris XII

Steven MARTIN

Directrice de thèse :

Co-encadrement :

Pascale MINETLaurent GEORGE

1

PLAN DE LA PRESENTATIONPLAN DE LA PRESENTATION

Sujet et problématique

Modèles considérés

Cas monoprocesseur

Cas distribué

Exemple d’application : DiffServ/MPLS

Conclusion et perspectives

1

Maîtrise de la dimension temporellede la qualité de service dans les réseaux

Thèse de doctoratUniversité Paris XII

Steven MARTIN

Directrice de thèse :

Co-encadrement :

Pascale MINETLaurent GEORGE

Présentation Modèles Cas distribué Applications ConclusionMonoprocesseur

1





Cas monoprocesseur

Cas distribué



1

1

Applications temps-réel- téléphonie sur IP

- vidéo à la demande

- contrôle/commande de processus industriels

- jeux interactifs distribués

- délai de bout-en-bout < 250 ms

- variation du délai de bout-en-bout < 50 ms

Exemple : téléphonie

L’évolution rapide des débits n’est pas une solution- surdimensionnement coûteux

- surplus de bande passante rapidement utilisé

- aucune assurance pour les applications temps-réel

INTRODUCTIONINTRODUCTION

2

Modèles Cas distribué Applications ConclusionMonoprocesseur




Cas monoprocesseur

Cas distribué



1

Présentation

1


DIFFERENCIATION DE SERVICES / ASSURANCE DE PERFORMANCESDIFFERENCIATION DE SERVICES / ASSURANCE DE PERFORMANCES












2

1


DIFFERENCIATION DE SERVICES / ASSURANCE DE PERFORMANCESDIFFERENCIATION DE SERVICES / ASSURANCE DE PERFORMANCES












2

PROBLEMATIQUEPROBLEMATIQUE

Flux : séquence de paquets ayant des caractéristiques communes.

3

- son temps de réponse de bout-en-bout,

- sa gigue de bout-en-bout.

Fournir à chacun des flux des garanties déterministes sur :

1



3

Flux : séquence de paquets ayant des caractéristiques communes.

- son temps de réponse de bout-en-bout,

- sa gigue de bout-en-bout.

Fournir à chacun des flux des garanties déterministes sur : Le temps de réponse de bout-en-bout d’un paquet comprend :

- un délai fixe ;

- un délai variable.

1

Le temps de réponse de bout-en-bout d’un paquet comprend :

- un délai fixe ;

- un délai variable.



3

processeurprocesseur

14

Réseau fiable.

Liens supposés FIFO (First In First Out).

Lmin ≤ délais réseau ≤ Lmax.

MODELE DE RESEAUMODELE DE RESEAU

Cas distribué Applications ConclusionMonoprocesseur


3

Présentation Modèles

1


4

Réseau fiable.



MODELE DE RESEAUMODELE DE RESEAU

1


4

Réseau fiable.



MODELE DE RESEAUMODELE DE RESEAUMODELE DE FLUXMODELE DE FLUX

5

Soit τ = {τ1, τ2, … , τn} l’ensemble des n flux sporadiques.

Ti

instant de génération

instant deprise en compte

Ji Ci1

t + Di

tCi

h

Ciq

Chaque flux τi est caractérisé par : Ti , Cih , Ji , Di

m11

hh

qq

1


MODELE DE FLUXMODELE DE FLUX

5


Ti



Ji Ci1

t + Di

tCi

h

Ciq


m11

hh

qq

1


MODELE DE FLUXMODELE DE FLUX

5


Ti



Ji Ci1

t + Di

tCi

h

Ciq


m11

hh

qq

6

MODELE DMODELE D '' ORDONNANCEMENTORDONNANCEMENT

Chaque flux spécifie deux paramètres de QoS :

1) un degré d’importance (critère principal d’ordonnancement)associé à une priorité fixe.

Les paquets sont ordonnancés selon leurs priorités fixes (ordonnancement FP non-préemptif).Les paquets sont ordonnancés selon leurs priorités fixes (ordonnancement FP non-préemptif).

2) un paramètre temporelpermettant d’attribuer une priorité dynamique à chaque paquet.

Les paquets de même priorité fixe sont ordonnancés selon leurs priorités dynamiques (ordonnancement DP).

1


6







1



6






7

τ i : Pi

Pi1(t)11

Pi2(t)22

33 Pi3(t)

44 Pi4(t)

A chaque flux τi est assignée une priorité fixe : Pi.

ORDONNANCEMENT FP/DP

A tout paquet de τi sont assignées des priorités dynamiques : Pi

h(t).

1


7


τ i : Pi

11

22

33

44

Pi1(t)

Pi2(t)

Pi3(t)

Pi4(t)




h(t).


ORDONNANCEMENT FP/DP*

A tout paquet de τi est assignée une priorité dynamique : Pi(t).

Pi (t)

1



7

τ i : Pi

11

22

33

44




h(t).


ORDONNANCEMENT FP/DP*

A tout paquet de τi est assignée une priorité dynamique : Pi(t).

Pi (t)

8

m

t + Di

tm’

t’

t’ + Dj

Exemples d’ordonnancement FP/DP* : FP/FIFO* et FP/EDF*

?11

hh

qq

(τi) (τj)

m ou m’

18


m

t + Di

tm’

t’

t’ + Dj


?11

hh

qq

(τi) (τj)


m ou m’

1

ETAT DE LETAT DE L '' ARTART

Tous les flux visitent un seul et même noeud. - Flux : tâche,

- Paquet : instance de tâche.

tPaquet moins prioritaire

9

m

Calcul du temps de réponse pire cas : - Approche “préemptif non-préemptif” (Tindell, Migge)

- Approche “instant de démarrage au plus tard” (Tindell, George)

8


m

t + Di

tm’

t’

t’ + Dj


?11

hh

qq

(τi) (τj)

m ou m’

Cas distribué Applications ConclusionModèlesPrésentation Monoprocesseur

1






9

m

Wi(t)

de traitement du paquet m

Début Fin



Ci

1



m

Wi(t)

RESULTATS AVEC FP/DPRESULTATS AVEC FP/DP

1max;0max

)(),(min1

)(1)(

)(

)(

,

jtsplpj

ii

i

jtspj j

jijij

hpj j

jii

CCT

Jt

CT

JtGtWC

T

JtWtW

ii

ii

10

Ci





9

m

Wi(t)



Ci

1


RESULTATS AVEC FP/DPRESULTATS AVEC FP/DP

10

1max;0max

)(),(min1

)(1)(

)(

)(

,

jtsplpj

ii

i

jtspj j

jijij

hpj j

jii

CCT

Jt

CT

JtGtWC

T

JtWtW

ii

ii

-Ji Bi(ti0)

tCtWR iiSt

ii

)(max


m

Wi(t)

Ci

Gj,i(t) = - Jl + kl·Tl

t

1


EXEMPLESEXEMPLES

11

0

5

10

15

20

25

30

35

40

Flux 1 Flux 2 Flux 3 Flux 4 Flux 5

FP/EDF

FP/FIFO

FP

Flux 1

Flux 2

Flux 3

Flux 4

Flux 5

Pi Ci Ti Di

1 4 20 26

1 4 20 28

1 4 20 30

2 4 20 20

3 8 40 15

1


EXEMPLESEXEMPLES

11

0

5

10

15

20

25

30

35

40

Flux 1 Flux 2 Flux 3 Flux 4 Flux 5

FP/EDF

FP/FIFO

FP

Flux 1

Flux 2

Flux 3

Flux 4

Flux 5

Pi Ci Ti Di

1 4 20 26

1 4 20 28

1 4 20 30

2 4 20 20

3 8 40 15

12

Sous certaines hypothèses, FP/EDF domine FP/FIFO.

Région d’ordonnançabilitéRégion d’ordonnançabilitéavec FP/FIFOavec FP/FIFO

Améliorations obtenuesAméliorations obtenuesavec FP/EDFavec FP/EDF

1


EXEMPLESEXEMPLES

12




1

EXEMPLESEXEMPLES

12




Présentation Modèles Applications ConclusionMonoprocesseur Cas distribué


13

Deux techniques différentes pour la détermination du temps de réponse pire cas de bout-en-bout :

- Approche holistique (Tindell & Clark)

- Network calculus (le Boudec & Thiran)

Analyse pire cas basée sur une approche par trajectoire.

1



13





1



13





MEME LIGNE DE DIFFUSIONMEME LIGNE DE DIFFUSION

14

11

q-1q-1

qq

m

m

m

t

Wiq(t)

1



14

11

q-1q-1

qq

m

m

m

t

f(q) m

f(q-1) f(q)

f(1) f(2)

0

Wiq(t)

maxq

iqi

q

h

hf

hfg

hg

qi LqtCCtW

1)()( ,1

1

)1(

)()(

1

f(q)

f(q-1) f(q)

f(2)



14

11

q-1q-1

qq

t

f(q)

f(q-1) f(q)

f(2)

0

maxq

iqi

q

h

hf

hfg

hg

qi LqtCCtW

1)()( ,1

1

)1(

)()(

f(1)

m

f(1) m

slow

1


maxq

iqi

q

h

hf

hfg

hg

qi LqtCCtW

1)()( ,1

1

)1(

)()(


f(q)

f(q-1) f(q)

f(2)

14

11

q-1q-1

qq

t

f(q)

f(q-1) f(q)

f(2)

0

f(1) m

slow

15

max

1)(

1)(

)(

,min

min

11max;0max

max1

)(,)(min1

)(1)(

q

j

q

j

LqC

CCCT

Jt

CT

JtGStW

CT

JStWtW

q

h

hj

tsplpj

q

slowhh

qi

hj

itsplpj

slowi

i

i

slowj

tspj j

jijqi

slowj

hpj j

jqiq

i

ii

ii

i

i

1



15

max

1)(

1)(

)(

,min

min

11max;0max

max1

)(,)(min1

)(1)(

q

j

q

j

LqC

CCCT

Jt

CT

JtGStW

CT

JStWtW

q

h

hj

tsplpj

q

slowhh

qi

hj

itsplpj

slowi

i

i

slowj

tspj j

jijqi

slowj

hpj j

jqiq

i

ii

ii

i

i

tCtWR qi

qi

Sti

i

)(max

1


max

1)(

1)(

)(

,min

min

11max;0max

max1

)(,)(min1

)(1)(

q

j

q

j

LqC

CCCT

Jt

CT

JtGStW

CT

JStWtW

q

h

hj

tsplpj

q

slowhh

qi

hj

itsplpj

slowi

i

i

slowj

tspj j

jijqi

slowj

hpj j

jqiq

i

ii

ii

i

i


15

tCtWR qi

qi

Sti

i

)(max

EXEMPLE : FP/EDF*EXEMPLE : FP/EDF*

16

0

25

50

75

100

125

150

175

200

1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9

Flux 1

Flux 2

Flux 3

Flux 4

Pi Ti Di

1 30 50

1 30 47

2 30 44

3 30 39

Approche holistique Approche par trajectoire Valeurs exactes

Flux 1

Flux 2

Flux 3

Flux 4

1



16

0

25

50

75

100

125

150

175

200

1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9

Flux 1

Flux 2

Flux 3

Flux 4

Pi Ti Di

1 30 50

1 30 47

2 30 44

3 30 39


Flux 1

Flux 2

Flux 3

Flux 4

1



16

0

25

50

75

100

125

150

175

200

1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9

Flux 1

Flux 2

Flux 3

Flux 4

Pi Ti Di

1 30 50

1 30 47

2 30 44

3 30 39


Flux 1

Flux 2

Flux 3

Flux 4

CAS GENERAL DISTRIBUECAS GENERAL DISTRIBUE

17

τi

τj

1



17

firstj lastj

τi

τj

slowj

1



17

firstj lastj

τi

τj

slowj

max

1)(

1)(

)(

max,min

maxmin

11max;0max

max1

)()(,)(min1

)()(1)(

LqC

CCCT

Jt

CT

JStMtGStW

CT

JStMStWtW

q

h

hj

tsplpj

q

slowhh

qi

hj

itsplpj

slowi

i

i

slowj

tspj j

jfirstiij

lasti

slowj

hpj j

jfirsti

lastiq

i

ii

ii

j

i

jfirst

j

jjlast

j

j

j

i

jfirst

j

jjlast

j

j

18

tCtWR qi

qi

Sti

i

)(max

1



18

max

1)(

1)(

)(

max,min

maxmin

11max;0max

max1

)()(,)(min1

)()(1)(

LqC

CCCT

Jt

CT

JStMtGStW

CT

JStMStWtW

q

h

hj

tsplpj

q

slowhh

qi

hj

itsplpj

slowi

i

i

slowj

tspj j

jfirstiij

lasti

slowj

hpj j

jfirsti

lastiq

i

ii

ii

j

i

jfirst

j

jjlast

j

j

j

i

jfirst

j

jjlast

j

j

tCtWR qi

qi

Sti

i

)(max

1

MISE EN OEUVRE DES RESULTATSMISE EN OEUVRE DES RESULTATS

19

DiffServDiffServ

Présentation Modèles ConclusionMonoprocesseur


18

max

1)(

1)(

)(

max,min

maxmin

11max;0max

max1

)()(,)(min1

)()(1)(

LqC

CCCT

Jt

CT

JStMtGStW

CT

JStMStWtW

q

h

hj

tsplpj

q

slowhh

qi

hj

itsplpj

slowi

i

i

slowj

tspj j

jfirstiij

lasti

slowj

hpj j

jfirsti

lastiq

i

ii

ii

j

i

jfirst

j

jjlast

j

j

j

i

jfirst

j

jjlast

j

j

tCtWR qi

qi

Sti

i

)(max

Cas distribué Applications

1



19

FP

EF

AF

Best-effort

DP*

DiffServDiffServMPLSMPLS

1



19


Label(20 bits)

TTL(8 bits)

Exp(3 bits)

Stack(1 bit)

priorité fixelabel / priorité dynamique

1



19


Label(20 bits)

TTL(8 bits)

Exp(3 bits)

Stack(1 bit)

priorité fixelabel / priorité dynamique

EXEMPLE DEXEMPLE D '' APPLICATIONAPPLICATION

20

Classe EF : faibles délais et faibles taux de pertes.

Aucune garantie quantitative !

- le Boudec : faible taux d’utilisation

- Gerla : garanties non déterministes

Mise en place d’un contrôle d’admission

1



20






1



20






21

Rejetoui

Les contraintes du nouveau fluxseront-elles satisfaites ?

non

Rejetnon

Acceptation

oui

Le nouveau flux peut-il compromettre les garanties données

aux flux déjà acceptés ?

Contrôle d’admission

1



21

Rejetoui


non

Rejetnon

Acceptation

oui




1



21

Rejetoui


non

Rejetnon

Acceptation

oui




1



22


τi

Flux EF

(Di)di

1 di2 di

3 di4

Quatre conditions à vérifier par le contrôle d’admission :

- Condition de charge locale

- Condition de charge distribuée

- Condition sur les durées de séjour

- Condition sur les temps de réponse de bout-en-bout

1


22


τi

Flux EF

(Di)di

1 di2 di

3 di4

Quatre conditions à vérifier par le contrôle d’admission :

- Condition de charge locale

- Condition de charge distribuée

- Condition sur les durées de séjour

- Condition sur les temps de réponse de bout-en-bout

CONCLUSIONCONCLUSION

23

Applications à fortes contraintes temporelles- Degré d’importance (priorité fixe)

- Paramètre temporel (priorité dynamique)

Etablissement de bornes mathématiquement calculables- Temps de réponse de bout-en-bout

- Gigue de bout-en-bout

Ordonnancement FP/DP* (FP/FIFO* et FP/EDF*)- Contexte monoprocesseur

- Ligne de diffusion

- Cas général distribué

Mise en œuvre des résultats établis- Architecture DiffServ/MPLS

- Contrôle d’admission pour la classe EF

Présentation Modèles Cas distribuéMonoprocesseur Applications Conclusion

1



23










1



23










PERSPECTIVESPERSPECTIVES

24

Ordonnancement- Précision de la borne / Complexité de calcul

- FP/FIFO* vs. FP/EDF*

Garanties proposées- Garanties probabilistes

- Garanties de type (m,k)-firm


Network calculus- Intégration des résultats dans l’approche Network Calculus

- FP/DP* vs. FP/DP

- Caractérisation des scénarios pire cas

1



24







- FP/DP* vs. FP/DP


1

Présentation Modèles Cas distribué ApplicationsMonoprocesseur


24







- FP/DP* vs. FP/DP


Conclusion

Documents

Maîtrise de la dimension temporelle de la qualité de service dans les réseaux