Embed Size (px)
Citation preview
Ordonnancement temps réel dans les réseaux
Ye-Qiong SONG
Université de Lorraine – LORIA
40 ans de recherches en ordonnancement temps réel Nantes 8 juin 2012
30 ans d’ordonnancement dans les réseaux – Plan de la présentation
72-80: ordonnancement monoprocesseur, peu de travaux d’ordonnacement sur les réseaux
80-90: bus de terrain (réseaux de capteurs, actionneurs et automates, filaires) et le besoin d’ordonnancer le trafic temps réel
90-00: CAN, bus à priorité fixe et analyse du pire temps de réponse 00-10: Ethernet commuté industriel (Profinet, AFDX, …) 10- : Réseaux sans fil, NCS (Networked Control System) et CPS
(Cyber-Physical System) Réflexions sur les approches d’évaluation de temps de réponse Ordonnancement sous contrainte (m,k)-firm
Bus de terrain et ordonnancement
Procédé industriel
automate1 automate2
actionneur2 actionneur1 capteur1
capteur2 capteur3
Boucles de contrôle-commande partagent le même bus de communication Problème: ordonnancer les demandes d’accès au bus Similaire aux protocoles MAC, mais avec la notion d’échéance/période
Procédé industriel
Bus de terrain et ordonnancement automate1 automate2
actionneur2 actionneur1 capteur1
capteur2 capteur3
FIP Distributeur (table de scrutation)
Solution de FIP: table de scrutation, modèle producteur-consommateur [Thomesse05]
Mi (Ci, Ti); cycle élémentaire EC=PGCD(Ti); macro cycle MC=PPCM(Ti) Exemple: A(1, 2); B(1, 4); C(1, 8)
A! A! A! A! t (CE)
B! B!C!
1 2 3 4 A! A! A! A!
B! B!C!
5 6 7 8
Discussion 1: bus de terrain Réseau dédié dont les applications sont connues Correspond au besoin du niveau bas (terrain) des
systèmes automatisés de production, une fois configurées (trafics ordonnancés), n’évoluent pas ou peu
Exemple d’applications de FIP: TGV, LHC Problèmes:
– Ordonnancement statique et hors-ligne, ne supporte pas des applications dynamiques (ajout ou retrait d’équipements, par ex)
– Manque de la robustesse face aux aléas
CAN (Controller Area Network) CAN, conçu en 1983 par Bosch pour automobile,
standard ISO depuis 1994
CMOSEKSur µC
BSI
CAN (réseau inter-systèmes)
VAN (réseau confort)
A C
BVAOSEKSur µC
A C
SUSOSEKSur µC
A C
ABS/CDSOSEKSur µC
A C
CAV/CdPOSEKSur µC
A C
OSEKECRAN
…
… OSEKCOMB
OSEKNAV
OSEKSTAT
OSEKCLIM
OSEKRADIO
OSEKGSM
CAN, bus à priorité fixe
Méthode d'accès – Bit dominant 0 et bit récessif 1 (Codage
NRZ) – CSMA avec arbitrage bit par bit sur le champ ID (par ET
logique sur la ligne) u Débit limité par le MAC
Données de la machine A
Données de la machine B
Données sur le média
Prise de parolesimultanée
B n’a rien remarqué etcontinue à émettre
A détecte le conflitet s’arrête
CAN: exemple d’applications
CM ABS/CDS
SUS BVA CAV/CdP
BSI
CAN
VAN
Nom de tâche Message entrant Durée (ms) Période (ms) Message généré ChargeT_CM1 2 10 M1 0,20T_CM2 2 20 M3 0,10T_CM3 2 100 M10 0,02T_CM4 M4 2 15 0,13T_CM5 M2 2 14 0,14T_CM6 M8 2 50 0,04T_CM7 M6 2 40 0,05
0,69
Nom de tâche Message entrant Durée (ms) Période (ms) Message généré ChargeT_BVA1 2 15 M4 0,13T_BVA2 2 50 M11 0,04T_BVA3 M8 2 50 0,04T_BVA4 M2 2 14 0,14
0,36
CAN: pire temps de réponse
Temps de réponse des messages du pire cas [Tindell94] :
Rm = Cm + Im + Jm
j
mhpj j
bitjnm
mnm C
TJI
BI ∑∈∀
+
⎥⎥
⎥
⎤
⎢⎢
⎢
⎡ +++=
)(
1 τ
CAN: Application à la messagerie PSA
0,00
0,50
1,00
1,50
2,00
2,50
3,00
3,50
4,00
4,50
5,00
1 2 3 4 5 6 7 8 9 10 11 12
Avg RT
WCRT
DLC (byte) Periode (ms) Priority Avg RT WCRT
8 10 1 0,63 1,04
3 14 2 0,44 1,38
3 20 3 0,45 1,72
2 15 4 0,41 2,02
5 20 5 0,54 2,44
5 40 6 0,54 2,86
4 15 7 0,51 3,24
5 50 8 0,55 3,66
4 20 9 0,52 4,04
7 100 10 0,64 4,46
5 50 11 0,56 4,72
1 100 12 0,40 4,72
Messagerie PSA Peugeot-Citroën pour les 1ères voitures avec multiplexage CAN
AvgTR si M/G/1 avec priorité et sans préemption WCRT: pire temps de réponse
[Simonot-Lion95]
Discussion 2: CAN et surdimensionnement
Réseau dédié, donc applications connues Largement répandu dans l’automobile Certaine flexibilité (ajout ou supression de messages
de faible priorité a peu d’impact) Débit très limité à cause de l’arbitrage bit par bit Surdimensionnement du besoin en bande passante à
cause de la considération du pire cas – Solution de déphasage (cf. travaux de Navet)
Robustesse face aux erreurs de transmission – Garantie probabiliste du pire temps de réponse
CAN: prise en compte des erreurs de tx
Erreurs de transmission augmentent le TdR
WCDFP pour mesurer la robustesse:
{ })max23)(()(
)(j
mmhpjbiterrm CtNtE
∪∈∀+= τ
jmhpj j
bitjnm
mmnmm
nm C
PJI
BCIEI ∑⎥⎥⎥
⎤
⎢⎢⎢
⎡ +++++=
∈∀
+
)(
1 )(τ
])([ max iierr KRNP > (Ki nb max de retransmissions avant de conduire à la violation de l’échéance)
[Navet00]
CAN: modèle d’occurrence des erreurs
Nombre d ’erreurs durant [0, t]: Avec:
– N(t) suit une loi de Poisson composé
– u est une v.a. qui peut suivre une distribution quelconque
∑==
)(
0)(
tN
iierr ytN
⎩⎨⎧
=α
α
- 1 éprobabilit une avec ,1 éprobabilit une avec ,u
yi
Erreurs individuelles et en rafale
t * * *
* * *
* * * *
u
Ethernet commuté pour communication indus.
!"#$$%&'(%!)*+!',*-%$.%/0' +/-1"2.%/0' 3"*!*&*245' #/-'()%21'4!%22' 4+33*"!%/0' 16%4!%/0' )%0)1"721812' 3"*!*&*24' $*"'/*/7"1#27!%,1'!"#$$%&'4+&)'#4'(1979#41-',#%/!1/#/&1:';%0:'<:'-13%&!4'#/'%/-+4!"%#2'=!)1"/1!'3"*!*&*2'4+%!1',*-12:'>"%*"%!.'4&)1-+2%/0' %4' %/!"*-+&1-' %/!*' 4(%!&)14' #4' (122' #4' 4*+"&1'/*-14'!*'01!'#4',+&)'"1#27!%,1'31"$*",#/&1'#4'3*44%9215'#!'!)1'4#,1'!%,1'#4'!)1'+41'*$'4!#/-#"-'3"*!*&*24'2%?1'@A>BC>'#/-'=!)1"/1!'%4'3"141"81-:'D1&*0/%E1'!)#!'%/-+4!"%#2'=!)1"/1!')#4'!*'4+33*"!'/*!'F+4!'
!)1'/11-'$*"'9*!)'"1#27!%,1'&*/!"*2'#/-'%/4!"+,1/!#!%*/5'9+!'#24*'!)1'/11-'!*'16!"#&!'%/$*",#!%*/'#9*+!'!)1'32#/!'#/-'%!4'1G+%3,1/!'(%!)*+!'-%4!+"9#/&1'!*'!)1'"1#27!%,1'(*"2-:'@)1'/1!(*"?'!"#$$%&'&#/'91'&2#44%$%1-'%/!*'!)"11'!.314H<I A.&2%&' 8#"%#9214' #"1' #2(#.4' 01/1"#!1-' &.&2%.:' C/'
,#/.'"1#27!%,1'#332%&#!%*/45'&.&2%&'8#"%#9214'"13"141/!'!)1',#F*"' &*,3+!#!%*/#2' -1,#/-4' %/' &*/!"*2' 4.4!1,:'@)1.'!.3%.'#"%41'$"*,'41/4*".'-#!#'#&G+%4%!%*/'#/-'&2*41-72**3'&*/!"*2'!#4?4:''
JI =81/!' 8#"%#9214' #"1' 01/1"#!1-' ()1/' *&&+""%/0:' @)1.'"13"141/!'181/!4'%/'%/-+4!"%#2'&*,,+/%&#!%*/5'4+&)'#4'#2#",4' 41/!' $"*,' $%12-' -18%&14' !*' !)1' &1/!"#2' &*/!"*2'4.4!1,:'
KI L144#014' #"1' 01/1"#!1-' ()1/' "1G+%"1-5' 4+&)' #4'-*(/2*#-' *$' 41!7+345' +32*#-' *$' -%#0/*4!%&4' #/-'(1979#41-'#332%&#!%*/4:''
!" #$%&'%()*&)+)(*,-,&./&,0-12$%'&31$%4+%1&@)1' !"#/4$1"' -12#.'*$' #' $"#,1' 1631"%1/&14' $"*,' 21#8%/0'
$"*,' 4*+"&1' /*-1' !*' 91%/0' &*,321!12.' "1&1%81-' 9.'-14!%/#!%*/'/*-1'&#/'91'&2#44%$%1-'%/!*'$*+"'0"*+34H'<I @)1' -12#.' #!' 4*+"&1' /*-1' %/&2+-14H' M#I' !)1' 3"*!*&*2'
3"*&144' !%,1' $*"' 1/"+2#!%/0' "#(' -#!#N' M9I' !)1'G+1+%/0'!%,1'#'$"#,1',+4!'(#%!'%/'9+$$1"'()1/'LOA'*+!3+!'%4'9+4.N'M&I'!)1'41/-%/0'!%,15'()%&)'-131/-4'*/'!)1' $"#,1' 21/0!)' #/-' !)1' LOA' *+!3+!' "#!1:' P1'&*,9%/1' !)1' 2#4!' !(*' %!1,4' #/-' ' !)1,' !)1' 9+$$1"'"143*/41'!%,1'*$'#'$"#,1'#!'4*+"&1'/*-1:'
JI @)1' -12#.' #!' =!)1"/1!' 4(%!&)' %/&2+-14H' M#I' @)1'-14!%/#!%*/'!#921'2**?7+3'!%,1'#/-'4(%!&)'$#9"%&'41!7+3'
!%,15'()%&)'#"1'!)1'9#4%&'-12#.'*$'=!)1"/1!'4(%!&)N'M9I'@)1'G+1+%/0'!%,1'#'$"#,1',+4!'(#%!'%/'9+$$1"'()1/'!)1'LOA' *+!3+!' %4' 9+4.N' M&I' @)1' $*"(#"-' !%,15' ()%&)'-131/-4' */' !)1' $*"(#"-' ,*-1' !)#!' =!)1"/1!' 4(%!&)'#-*3!4:'P)1/'4!*"1'#/-'$*"(#"-',*-1'%4'#-*3!1-5'!)1'$*"(#"-'!%,1'%4'%/'-%"1&!'3"*3*"!%*/'!*'!)1'$"#,1'21/0!):'P1'#24*'&*,9%/1'!)1'2#4!'!(*'%!1,4'#/-''!)1,'!)1'9+$$1"'"143*/41'!%,1'*$'#'$"#,1'#!'=!)1"/1!'4(%!&):'
KI @)1' -12#.' #!' -14!%/#!%*/' /*-1' %/&2+-14H' M#I' !)1'"1&1%8%/0' !%,15' ()%&)' -131/-4' */' !)1' $"#,1' 21/0!)N'()1/'!)1'-%4!#/&1'91!(11/'!)1'4(%!&)'#/-'-14!%/#!%*/'/*-1' %4' /*!' $#"5' !)1' "1&1%8%/0' !%,1' &#/' 91' *,%!!1-'91&#+41' !)1' 41/-%/0' #/-' "1&1%8%/0' #2,*4!' !#?1' 32#&1'4%,+2!#/1*+42.N'M9I'!)1'3"*!*&*2'4+%!1'3"*&144'!%,1'$*"'-1/"+2#!%/0'!)1'$"#,1'!*'*9!#%/'!)1'"#('-#!#:''
QI '@)1'-12#.'*/' !"#/4$1"' 2%/14'-131/-4'*/' !)1' !*!#2' 2%/1'21/0!)' 91!(11/' 4*+"&1' /*-1' #/-' -14!%/#!%*/' /*-1:'P)1/' !(%4!1-73#%"' %4' #-*3!1-5' !)1' !"#/4$1"' -12#.' %4'#9*+!'< , */'#' JRR5 '2%/1:'
P1' $+"!)1"'-%8%-1' !)1' #9*81'-12#.4' %/!*' !(*'3#"!4:'@)1'$%"4!'3#"!'%4'!)*41'-12#.4'!)#!'-131/-'*/'!)1'$"#,1'21/0!)5'!)1'LOA' *+!3+!' "#!15' !)1' 9#4%&' -12#.' *$' =!)1"/1!' 4(%!&)5' !)1'3"*!*&*2'4+%!1'31"$*",#/&1'*$'=!)1"/1!'/*-145'#/-'!)1'21/0!)'*$'!"#/4$1"'2%/14:'@)1'41&*/-'3#"!'%4'!)1'9+$$1"'"143*/41'!%,1'#' $"#,1' 1631"%1/&14' %/' =!)1"/1!' 4(%!&)' #/-' 4*+"&1' /*-15'()%&)'%4'!)1',*4!'4%0/%$%&#/!'3#"!'%/'!)1'()*21'-12#.'()1/'!)1' /1!(*"?' %4' 9+4.5' #/-' %4' #24*' !)1' ,#%/' "1#4*/' $*"'/*/7-1!1",%/%4!%&'%/'4(%!&)1-'=!)1"/1!:''@"#-%!%*/#2'4(%!&)1-'=!)1"/1!'-*14'/*!'3"*8%-1'1$$1&!%81'
3"%*"%!.' !"#/4$1"',1&)#/%4,' $*"' %/-+4!"%#2' &*,,+/%&#!%*/:'S1&#+41'/*/7"1#27!%,1'-#!#'01/1"#22.')#81'2*/0'$"#,15'()1/'#' "1#27!%,1' -#!#' #""%8145' %$' !)1"1' )#331/4' !*' 91' #',#44' *$'/*/7"1#27!%,1' -#!#' (#%!%/0' $*"' 41"8%&15' !)1/' !)1' "1#27!%,1'-#!#'(%22'91'-12#.1-'4%0/%$%&#/!2.:'@)1'9+$$1"'"143*/41'!%,1'*$'#'$"#,1'#!'4*+"&1'/*-1'*"'=!)1"/1!'4(%!&)'%4'1#4%2.'-1"%81-'#4
<
<
-
- 00
4%,6.+,%
( ('
25''''''''''''''''''''''''''''''''''M<I'
()1"1 - -( 5 5 0 0( 5 5 -5 #/- 05 #"1' $"#,1'
21/0!)4' *$' !)1' &*/4%-1"1-' $"#,1' #/-' G+1+1-' $"#,145'"1431&!%812.5 '%4' !)1',%/%,+,'=!)1"/1!' %/!1"7$"#,1' 0#35'
#/- 2 '%4'!)1'LOA'*+!3+!'"#!1:'S1&#+41'!)1'181/!'8#"%#9214'#/-',144#014'#"1'43*"#-%&5'!)1'/+,91"'*$'G+1+1-'$"#,14' 0%4' +/&1"!#%/' ()1/' !)1' $"#,1' - '"1#&)14' !)1' LOA' 9+$$1":'@)1"1$*"15' !)1' ,#6%,+,' 9+$$1"' "143*/41' !%,1' *$' &.&2%&'8#"%#9214'%4'/*!'9*+/-1-:'
CCC: >DCTDC@U'VAW=XYZC[\'C['LOA'SY;;=D
@)1'C===]RJ:<3'G+1+%/0'$1#!+"1' %4'$%"4!2.' %/!"*-+&1-'%/'!)%4' 41&!%*/5' #/-' !)1/' !)1' 3"%*"%!.' 4&)1-+2%/0' 9#41-' */'C===]RJ<:<3'%/'4(%!&)1-'%/-+4!"%#2'=!)1"/1!'%4'-14&"%91-:'
!"#$%&$"'()*'+,&-'..*/
0$,12345$'",676
8339:;39:'<=(9>>>
?@9 3*9
4&"$%&$"'9%A"ABA1+49/
9%CA%C"D'6B#$-E1C&F
!"#$%&$"'98G
=A&20$,123C5$'",676
0$,12"C5$')94
)1,%56
'*A&"%A11AAH6
83396$%ICB$6 ;39
6$%ICB$6
;%0:'<:''O/'%/-+4!"%#2'=!)1"/1!'3"*!*&*2'4+%!1',*-12:'
3367
I1 ≥ d
Ij
IN
O1
Om
ON
S1
Sj
u
SN
pj1 pjm
pjN
s1
sm
sN
Ethernet Commuté: évaluation de délai Hypothèse:
– M sources périodiques classées en P priorités (P<9)
– Destinées au même port de sortie (i.e., nous connaissons l’application !)
Notation:
Prior=1
S1
Sk1
SK1
Prior=i
Prior=P
S1
Ski
SKi
S1
SkP
SKP
{Ci(ki), Ti(ki), Di(ki)} ki = 1, 2, …, Ki i = 1, 2, …, P
[Song02]
Ethernet commuté: pire temps de réponse
Pour Ki > 1 et quelque soit l’échéance, un paquet de priorité i peut être bloqué par un autre de la même priorité – Paquets issues d’autres sources mais classifiés en
la même priorité (effet de Ki > 1) – Paquets en attente, issues de la même source, et
pas encore transmis au moment de l’arrivée du paquet considéré (effet de l’échéance supérieure à la période)
Comment definir le pire temps de réponse?
Ethernet commuté: pire temps de réponse « Busy period » de priorité i a une durée finie ssi:
« Busy period » démarre avec l’hypothèse que toutes les autres sources de priorité supérieure ou égale envoient leurs paquets, et qu’un paquet de priorité inférieure vient de commencer sa tx
Calculer le délai Ri,k(ki) pour tous les k (k = 1, 2, …) paquets transmis durant la « busy period »
« Busy period » se termine quand on rencontre Ri,k(ki) < Ti(ki) Le max de Ri,k(ki) correspond au pire temps de réponse
! jj=1
i
! = Bi +C j (k j )Tj (k j )k j=1
K j
!j=1
i
! "1
Ethernet commuté: pire temps de réponse 0
1 1( ) ( )
j
j
Ki
i i i j jj k
I k B C k= =
= +∑∑
1
1 1
( )( ) ( ) ( )( )
j
jj i
K nin i ii i i i i j j
j k j jk k
I kI k B kC k C kT k
+
= =≠
⎡ ⎤= + + ⎢ ⎥
⎢ ⎥⎢ ⎥∑ ∑
, ( ) ( ) ( 1) ( )i k i i i i iR k I k k T k= − −
On arrête quand: Ri,k(ki) ≤ Ti(ki)
,( ) max { ( )}i i k i k iR k R k=
Réflexions sur les approches d’évaluation de temps de réponse
Serveur de capacité
c
τ1
τ2
τN
.
.
.
politique d’ordonnancement des clients en tête
des files
interarrivée sources
clients
Problème de partage d’une ressource commune, sans préemption, en respectant l’échéance è besoin d’évaluer le temps de réponse
Flux d’arrivées et Techniques d’évaluation
- Communauté « ordonnancement », application connue - Tâches périodique ou sporadique: (Ci, Ti) - Tâches périodique avec gigues : (Ci, Ti, Ji)
- Communauté « réseaux », application partiellement connue - Flux de paquets (σi, ρi)-borné - Flux de paquets aléatoire et durée de tx aléatoire: (λ, µ)
avec λ= moy(1/Ti ), µ = moy(1/Ci )
Hypothèses sur flux d’arrivée
Techniques: - Probabiliste: files d’attente - Trajectoires majorantes :
- pire temps de réponse - network calculus
Pire temps de réponse sous l’ordonnancement non préemptif à priorité fixe
i i i iR C I J= + + i iR T≤
11
11
max ( ) ( 1)i
ni i j N j j
j
ni j
jI C C
I JT
−+
+ ≤ ≤
=
= +⎢ ⎥+⎢ ⎥ +⎢ ⎥⎣ ⎦
∑0 0iI = Calcul récurrent :
Condition de convergence :
1n ni iI I+ =
11
ij
j j
CT=
≤∑
Technique de « network calculus »
t
6 5 4 3 2 1
Bornes pour majorer les flux d’entrée
F(t) périodique
F(t) périodique avec gigues
0 1 2 3 4 5 6 7
J
flux ( , )-borné 1
1
ijj
σ−
=∑ 1
1
ijj
ρ−
=∑
( )11
max 1
1
maxi
j i j N jj
i i
jj
W
D
c
σ
ρ
+ ≤ ≤
=
−
=
+
=
−
∑
∑
Ai(t)!Ai(s)"!i+"i(t!s) #0"s"t
Relation entre périodique pire cas et (σ, ρ)-borné
ii
i
WT
ρ =
( )ii i i
i
W T JT
σ = +
/i iC W c=
L'effet de la gigue
-50
0
50
100
150
200
250
300
-22 -20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34
Qtt Travail Arrivée J= 8 Qtt Travail Arrivée J=0Pente Optimale J=8 Pente Optimale J=0
σ2
σ1
[Koubaa04]
Temps de réponse probabiliste Hypothèse: demandes de ressource aléatoires Modèle: file d’attente M/G/1 avec priorité et sans
préemption
Distribution des temps de réponse pour des cas particuliers (e.g., Poisson, Binomial) è P[Ri >Di] < ε
iii
iii Caa
CECqERE +−−
=+=− )1)(1(2
][][][1
2λ
][...][][][ 222
221
12n
n CECECECEλλ
λλ
λλ
+++=
λ = λ1 + λ2 + … + λnaj = λ1C1 + λ2C2 + … + λjCj
Quelle approche dans un réseau multi-saut? 1
11
1
1
maxˆ *
ij ji j N
ji i i i
jj
W
c
σ
σ σ ρρ
⎛ ⎞⎜ ⎟⎜ ⎟⎝ ⎠
−
+ ≤ ≤=
−
=
+
= +
−
∑
∑
NP-FP ( ),i iσ ρ ( )ˆ ,i iσ ρ
Point clé: caractériser le flux de sortie: - des résultats existent pour le flux
(σi, ρi)-borné, mais problème de surdimensionnement [Grieu04],[Bouillard10]
- Pire trajectoire par flux sur tout le chemin, valable pour des flux statiques [Martin04], [Bauer10]
- flux de sortie d’une file M/G/1 n’est plus Markovien en général, rendant difficile l’analyse probabiliste
Evaluation de délais de bout en bout est un problème difficile, nécessite plus de recherches
D’où vient l’échéance? Jusqu’à présent, on suppose un modèle (Ci, Ti, Di) qui conduit à
considérer le pire cas et à une allocation de ressource surdimensionnée. Mais est-il possible de relâcher la contrainte sur échéance afin d’éviter le surdimensionnement? – Applications “temps réel” dans l’Internet (voix, vidéo), le modèle (m,k)-
firm peut convenir – Les boucles de contrôle-commande fermées sont souvent robustes, dont la
fréquence d’échantillonnage est sur-estimée (4 à 10 fois)
Possible d’exploiter un espace de solutions plus large pour des applications temps réel “souple” ou “firm”
Modèle (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 (QdS dégradée) – Temps réel « firm »: temps réel souple mais avec le non
traitement des paquets ne pouvant pas respecter leur échéances (paquets rejetés)
– (m,k)-firm: respect des échéances d’au moins m parmi k paquets consécutifs quelconques [Hamdaoui95]
(m,k)-firm et états du system Exemple de (2,3)-firm k-séquence
111 1
110 0
101
100
1
0
011
010
001
000
0
1
0
1
0
1
0 1 1
0
1 0
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
Exemple d’une application acceptant la contrainte (m,k)-firm
Flux vidéo MPEG
I B B B
P B B
P B B
P B
I B B B
P B B
P B B
P B
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
GOP (Groupe Of Pictures)
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
Test sur maquette
Vidéo initiale:
Test 1: rejet de tous les paquets de type I
Image fixe
Test sur maquette
Test 2: rejet de tous les paquets de type P
Test sur maquette
Test 3: rejet de tous les paquets de type B
Test sur maquette
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’échec
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)
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 = ci , pi ,Di ,mi ,ki{ }
),,,( 111
111 iiki δδδ −+−
),,,( 221
212 iiki δδδ −+−
21
22
23 ,,, +++ iii jjj
),,,( 11Ni
Ni
Nki N δδδ −+−
Ni
Ni
Ni jjj 123 ,,, +++
11
11, ++ ii pj1
112
13 ,,, +++ 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
Ordonnancement NP-DBP-EDF Priorité 0: le paquet en cours de service (transmission) a la
plus haute priorité (non préemption) Priorité 1: paquets avec DBP=1 en attente de transmission
(doivent être garantie, sinon violation de la contrainte) Priorité i: paquets avec DBP=i (i>1) en attente de
transmission (transmis s’ils peuvent l’être avant leur échéance, écartés sinon)
Paquets avec la même valeur de DBP sont ordonnancés selon EDF
Garantie déterministe de (m,k)-firm
cipi
miki
!
"#
$
%&
i=1
N
! "1 au lieu de cipi
!
"#
$
%&
i=1
N
! "1Charge:
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
DBP: condition suffisante (1) Pour trouver la condition suffisante
d’ordonnançabilité, le point clé est de trouver la période pire cas et sa charge (workload) correspondante
Le pire cas a lieu pendant la DBP=1 busy period où seuls les paquets avec DBP=1 sont transmis.
DBP: condition suffisante (2)
Supposons l’existence d’une telle période qui commence à l’instant t0 et se termine à td.
Trois cas sont identifiés: 1) DBP=1 busy period commence quand le serveur est
libre à t0, et tous les paquets ont leur échéance avant td .
2) DBP=1 busy period commence mais le seuveur est bloqué par un paquet de DBP>1 à t0, et tous les paquets ont leur échéance avant td .
3) Il y a quelques paquets dont l’échéance est après td.
Workload dans le cas 1 L= td - t0 : longueur de la DBP=1 busy period Paquets classés en deux sous-ensembles :
– U : paquets avec DBP=1 à t0 – a()-U : paquets avec DBP >1 à t0 mais devenus DBP=1
à tx < td Tous les paquets doivent être transmis car leur
échéance est avant td , la workload est définie comme le temps nécessaire pour transmettre tous ces paquets
Cas 1: Workload du sous-ensemble U td
kipi fragment
kipi
t0
DBP=1 busy period
L
1 LW m cU i ik pi U i i
⎛ ⎞⎢ ⎥⎜ ⎟= ⎢ ⎥∑⎜ ⎟⎢ ⎥∈ ⎣ ⎦⎝ ⎠
2 ,
LL k pi i k pi iW Min m cU i ipi U i
⎛ ⎞⎢ ⎥⎢ ⎥⎜ ⎟⎢ ⎥− ⎢ ⎥⎜ ⎟⎢ ⎥⎢ ⎥⎣ ⎦⎜ ⎟= ∑ ⎢ ⎥⎜ ⎟⎢ ⎥∈⎜ ⎟⎢ ⎥⎜ ⎟⎢ ⎥⎣ ⎦⎝ ⎠
Lk pi i
⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
Workload durant la part entière :
i i
LLk pi i
k p⎢ ⎥⎢ ⎥−⎢ ⎥⎣ ⎦
Workload durant la partie du fragment:
CAS 1: Workload du sous-ensemble a()-U
kjpj kjpj
tx
pj pj
1 2 DBP=a
1
t0
DBP=1 busy period
a-1 a-2 fragment
td L
Dans le pire cas : l = tx – t0 =1+(DBPj(t0)-2)pj Workload du sous-ensemble a()-U :
1()
()
L lW m ca U j jk pj a U j j
⎛ ⎞⎢ ⎥−⎜ ⎟⎢ ⎥= ∑− ⎜ ⎟⎢ ⎥⎜ ⎟∈ − ⎣ ⎦⎝ ⎠
( )2 ,()
()
L lL l k pj j k pj jW Min m ca U j jpj a U j
⎛ ⎞⎢ ⎥⎢ ⎥−⎜ ⎟⎢ ⎥⎢ ⎥− −⎜ ⎟⎢ ⎥⎢ ⎥⎜ ⎟⎣ ⎦⎢ ⎥= ∑− ⎜ ⎟⎢ ⎥∈ − ⎜ ⎟⎢ ⎥⎜ ⎟⎢ ⎥⎜ ⎟⎢ ⎥⎣ ⎦⎝ ⎠
L lk pi i
⎢ ⎥−⎢ ⎥
⎢ ⎥⎣ ⎦
durant
( )i i
L lL lk pi i
k p⎢ ⎥
−⎢ ⎥− −⎢ ⎥⎣ ⎦
durant
Cas 1: Workload totale
Somme de la workload des deux sous-ensembles :
+
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎥⎥⎥
⎦
⎥
⎢⎢⎢
⎣
⎢⎥⎦⎥
⎢⎣⎢−
+⎥⎦⎥
⎢⎣⎢∑
∈Uiii
i
iiii
iii
cmppkLpkL
MinmpkL ,
L’analyse similaire est appliquée aux cas 2 et cas 3
( )
()
1 ( ( ) 2)1 ( ( ) 1)
1 ( ( ) 2),
j jj j j j
j jj jj j j
j a U j j j
L DBP t pL DBP t p k p
k pL DBP t pm Min m c
k p p∈ −
⎛ ⎞⎛ ⎞⎢ ⎥⎢ ⎥− − −⎜ ⎟⎜ ⎟− − − −⎢ ⎥⎢ ⎥⎢ ⎥⎜ − − − ⎟⎜ ⎟⎢ ⎥⎢ ⎥⎣ ⎦+⎢ ⎥⎜ ⎟⎜ ⎟⎢ ⎥⎢ ⎥⎣ ⎦⎜ ⎟⎜ ⎟⎢ ⎥⎜ ⎟⎜ ⎟⎢ ⎥⎜ ⎟⎣ ⎦⎝ ⎠⎝ ⎠
∑
DBP: condition suffisante (3) Théorème: [Li06] Pour un ensemble de paquets périodiques ou
sporadiques a(), a()= {a(1),a(2),…,a(n)}, a(i)= {ci, pi, mi, ki}, di = pi,
Si a() satisfait les conditions C1 et C2, NP-DBP-EDF sera capable d’ordonnancer un
ensemble periodic ou sporadique concret quelconque généré à partir de a(). i.e. les contraintes (mi, ki)-firm sont garanties.
DBP: condition suffisante (4) +
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎥⎥⎥
⎦
⎥
⎢⎢⎢
⎣
⎢⎥⎦⎥
⎢⎣⎢−
+⎥⎦⎥
⎢⎣⎢∑
∈Uiii
i
iiii
iii
cmppkLpkL
MinmpkL ,
( )Lcmp
pkptDBPLpkptDBPL
MinmpkptDBPL
jUaj
jj
jj
jjjjjj
jjj
jj ≤
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎥⎥⎥
⎦
⎥
⎢⎢⎢
⎣
⎢⎥⎦⎥
⎢⎣⎢ −−−−−−−
+⎥⎦⎥
⎢⎣⎢ −−−∑
−∈ (),
)2)((1)1)((1)2)((1
, , min( )ii L L p∀ ∀ >
1 1, 1
i
i i ii ii
i i ii i i
L cL c k p
k pL c m Min m ck p p
+
+
⎛ ⎞⎛ ⎞⎢ − ⎥⎢ ⎥⎜ ⎟− −⎜ ⎟⎢ ⎥⎢ ⎥⎛ ⎞⎜ ⎟⎢ ⎥− ⎣ ⎦⎜ ⎟⎢ ⎥⎜ ⎟+ + − − +⎜ ⎟⎢ ⎥ ⎜ ⎟⎢ ⎥⎜ ⎟⎣ ⎦⎜ ⎟⎝ ⎠ ⎜ ⎟⎢ ⎥⎜ ⎟⎜ ⎟⎢ ⎥⎣ ⎦⎝ ⎠⎝ ⎠
( )Lcmp
pkptDBPLpkptDBPL
MinmpkptDBPL
jiaaj
jj
jj
jjjjjj
jjj
jj ≤
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜
⎝
⎛
⎥⎥⎥
⎦
⎥
⎢⎢⎢
⎣
⎢⎥⎦⎥
⎢⎣⎢ −−−−−−−
+⎥⎦⎥
⎢⎣⎢ −−−∑
−∈ )((),
)2)((1)2)((1)2)((1
C1:
C2:
Exemple numérique
n Mbit/s
S 1
S 2
S 3
S 4
Router Controller
Packet size
(kbit) Interarrival time/deadline (ms) (m,k)-firm
constraint S0 8 12 (2,5) S1 8 20 (4,5) S2 1 5 (1,4) S3 4 6 (1,5)
Exemple numérique
(m,k)-firm vs. (k,k)-firm (HRT)
0
5
10
15
20
25
30
35
0 5 10 15 20
(m,k)-firm (k,k)-firm
Cumulative workload
t
Conclusion L’ordonnancement de messages/paquets dans les réseaux est
nécessaire pour la QdS (e.g. Priorité, WRR) Messages/paquets non préemptifs L’approche de l’analyse du pire temps de réponse offre une borne
intéressante par rapport à la borne (σ, ρ), mais peut conduire au problème de surdimensionnement
Besoin d’aller au-delà de simple échéance sur paquet et s’intéresser à l’application (e.g. boucle de contrôle, capacité de tolérance applicative) – (m,k)-firm est un exemple de remède au problème de surdimensionnement
Perspectives L’histoire ne s’arrête pas à l’âge de 40 ans L’évaluation de délais dans des réseaux multi-
sauts soulève des problèmes difficiles Coupler l’ordonnancement en-ligne et la qualité de
l’application, e.g. qualité du contrôle dans des NCS (Networked Control Systems) è vers des systèmes auto-adaptatifs [Aubrun10]
CPS (Cyber-Physical Systems) et réseaux sans fil: ordonnancement en-ligne sous contraintes de perte de paquets et variation de débit
Bibilographie [Thomesse05] Jean-Pierre Thomesse, Fieldbus technology in industrial automation,
Proceedings of the IEEE 93, 6 (2005) 1073-1101. [Tindell94] Tindell, K., A. Burns, “Guaranteeing message latencies on controller area network
(CAN)”, 1st international CAN conference (iCC’94), Germany, sept. 1994. [Simonot-Lion95] Simonot-Lion F., Song Y.Q., Berthomieu B., Vernadat F., « Vérification des
applications temps réel », Dans Encyclopédie de l'informatique et des systèmes d'information, Vuibert (ed.) (2005).
[Navet00] N. Navet, Y.Q. Song, F. Simonot, "Worst-case deadline failure probability in real-time applications distributed over CAN (controller area network)", Journal of systems architecture - the EUROMICRO Journal, 46 (2000) pp607-617.
[Song02] Y.Q. Song, A. Koubâa, F. Simonot, "Switched Ethernet For Real-Time Industrial Communication: Modelling And Message Buffering Delay Evaluation", WFCS’2002, Vasteras (Sweden), pp27-35, August 28-30, 2002.
[Koubaa04] A. Koubâa, Y.Q. Song, "Evaluation and improvement of response time bounds for real-time applications under non pre-emptive fixed priority scheduling", International Journal of Production Research, Vol.42, No.14, pp2899-2913, Taylor & Francis group, July 2004.
Bibliographie [Bouillard10] Anne Bouillard, Laurent Jouhet, and Eric Thierry. Tight performance bounds in
the worst-case analysis of feed-forward networks. INFOCOM’10, San Diego, USA, pages 1316–1324, March 2010.
[Grieu04] Jérome Grieu. Analyse et évaluation de techniques de commutation Ethernet pour l’interconnexion des systèmes avioniques. PhD thesis, INPT Toulouse, France, September 2004.
[Martin04] Steven Martin. Maîtrise de la dimension temporelle de la qualité de service dans les réseaux. PhD thesis, Université Paris 12, 2004.
[Bauer10] Henri Bauer, Jean-Luc Scharbarg, and Christian Fraboul. Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach. IEEE Transactions on Industrial Informatics, 6(4) :521–533, November 2010.
[Hamdaoui95] M. Hamdaoui and P. Ramanathan, “A dynamic priority assignment technique for streams with (m, k)-firm deadlines”, IEEE Transactions on Computers, 44(4), 1443–1451, Dec.1995.
[Li06] Li J., Song Y.Q., Simonot-Lion F., “Providing Real-time Applications with Graceful Degradation of QoS and Fault Tolerance According to (m,k)-firm Model”, IEEE Transactions on Industrial Informatics 2, 2 (2006) 112-119
[Aubrun10] Aubrun C., Simon D., and Song Y.Q. (eds), Co-design Approaches for Dependable Networked Control Systems, ISTE and J. Wiley, 2010, 314 pages.
