Reseaux .pdf



Nom original: Reseaux.pdf

Ce document au format PDF 1.5 a été généré par LaTeX with hyperref package / dvips + ESP Ghostscript 7.05, et a été envoyé sur fichier-pdf.fr le 12/05/2013 à 14:02, depuis l'adresse IP 41.99.x.x. La présente page de téléchargement du fichier a été vue 3413 fois.
Taille du document: 174 Ko (25 pages).
Confidentialité: fichier public


Aperçu du document


Recherche opérationnelle
Les réseaux de files d’attente
ˆ
Jean-Franc¸ois Heche
´
´ erale
´
Ecole
Polytechnique Fed
de Lausanne

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.1

Réseaux de files d’attente
Un réseau de files d’attente est simplement un système
composé d’une ou plusieurs files d’attente reliées entre elles.
Les clients (dans les cas les plus simples, tous « identiques »),
une fois leur service terminé dans une station (file), se
déplacent vers une autre station ou quittent le système selon
des règles de routage (déterministes ou stochastiques).
Arriv´ees
externes

Routage
1

3

2

Sortie du syst`eme

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.2

Réseaux ouverts, fermés et mixtes
Un réseau est ouvert si tout client présent ou entrant dans le
système peut le quitter.
Un réseau est fermé si les clients ne peuvent le quitter. Dans un
réseau fermé, le nombre de client est fixe et ces derniers sont
présents dans le système dès le début de son évolution.
Finalement, un réseau est mixte s’il est ouvert pour certains
clients et fermé pour d’autres.

R´eseau ouvert

R´eseau ferm´e

R´eseau mixte
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.3

Réseaux à forme produit
La définition la plus simple de l’état d’un réseau consiste à
définir l’état x(t) du système au temps t comme le vecteur
(x1 (t) . . . xn (t)) où xj (t) est le nombre de clients présents à
l’instant t dans la file j .
Sous certaines conditions, un réseau stable possède une
distribution stationnaire π ∗ de la forme
π ∗ (x) = π ∗ (x1 . . . xn ) =

n
Y

πj∗ (xj ).

j=1

Un tel réseau est dit à forme produit et se comporte comme
autant n files indépendantes de distributions stationnaires
respectives πj∗ , j = 1, . . . , n.
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.4

Les réseaux de Jackson
Un réseau de Jackson est composé de n files exponentielles
c’est-à-dire de files d’attente
. comportant chacune un ou plusieurs serveurs identiques (m j
pour la file j ),
. fournissant des services de durée exponentielle (le taux de
service de la file j est noté µj ),
. de capacité infinie,
. utilisant une discipline de service F IF O.

Les clients (appartenant tous à la même classe) arrivent dans le
système selon des processus de Poisson indépendants, le taux
d’arrivée externe dans la file j étant égal à γj .
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.5

Les réseaux de Jackson : règles de routage
Après avoir terminé son service à la station j , un client se
déplace à la station k avec probabilité rjk et quitte le système
avec probabilité rj0 où
rj0 = 1 −

n
X

rjk .

k=1

De telles règles définissent un routage markovien.

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.6

Exemple (chaque file n’a qu’un seul serveur)
γ2

r11 = 1/4
γ1

µ1

µ2

r12 = 1/2

r13 = 1/4

r20 = 1/3

r23 = 2/3
µ3

r30 = 1/5

r31 = 4/5



1/4 1/2 1/4


R= 0

4/5

0
0




2/3 
0



0





r·0 =  1/3 
1/5

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.7

Conditions de stabilité
Sans surprise :
Un réseau est stable ⇐⇒ chacune de ses files l’est.
Notant λj le taux effectif (ou taux moyen) d’arrivée dans la file j ,
on peut écrire les équations de conservation
λj = γ j +

n
X

λi rij

j = 1, . . . , n.

i=1

Sous forme matricielle, ces équations deviennent
λ = γ + λR

⇐⇒

λ(I − R) = γ.
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.8

Conditions de stabilité (2)
Pour un réseau ouvert, on a limn→∞ Rn = 0 et l’unique solution
du système précédent est
λ = γ(I − R)−1 .

Connaissant les taux effectifs d’arrivée λ, la file j est stable si et
seulement si
λj
ρj =
<1
m j µj

et le réseau est stable si et seulement si chacune des files le
composant l’est.
R EMARQUE . Un réseau fermé est toujours stable !
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.9

Exemple (2)
γ2

r11 = 1/4
γ1

µ1

µ2

r12 = 1/2

r13 = 1/4

r20 = 1/3

r23 = 2/3
µ3

r30 = 1/5

r31 = 4/5

Les équations de conservation du flot dans le réseau sont

+ λ3 r31

 λ1 = γ1 + λ1 r11
λ2 = γ2 + λ1 r12


λ3 =
λ1 r13 + λ2 r23

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.10

Exemple (3)
⇐⇒

⇐⇒



 λ1
λ2


 λ3


λ1






λ2

= γ1 + λ1 /4

+ 4λ3 /5

= γ2 + λ1 /2
=
60
=
γ1
17

λ1 /4 + 2λ2 /3
32
+
γ2
17

30
33
=
γ1 +
γ2
17
17








 λ3 = 35 γ1 + 30 γ2
17
17

Le réseau est donc stable si γ1 , γ2 , µ1 , µ2 et µ3 sont tels que
λ1
ρ1 =
<1
µ1

λ2
ρ2 =
<1
µ2

λ3
ρ2 =
< 1.
µ3
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.11

Distribution stationnaire
Les réseaux de Jackson sont des réseaux à forme
produit.
La distribution stationnaire d’un réseau ouvert et stable est
π ∗ (x) = π ∗ (x1 . . . xn ) =

n
Y

πj∗ (xj ).

j=1

où πj∗ (xj ) est égal à la probabilité stationnaire d’observer x j
clients dans une file M/M/mj .
Un tel système se comporte donc comme n files M |M |mj
indépendantes d’intensité respective ρ1 = mλ11µ1 , . . . , ρn = mλnnµn .
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.12

Réseau de Jackson ouvert : exemple (p. 137)
r11 = 1/5
r20 = 4/5

γ1 = 6
−/M/1

−/M/1

r12 = 4/5

µ1 = 15

µ2 = 10

r21 = 1/5

Équations de conservation du flot :
(

λ1 = γ1 + λ1 r11 + λ2 r21
λ2 = γ2 + λ1 r12 + λ2 r22

⇐⇒

(

λ1 = 6 +
λ2 =

1
5 λ1
4
5 λ1

+

1
5 λ2

75
15
Solution unique : λ1 = , et λ2 = .
8
2
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.13

Stabilité du réseau
. Première file stable ⇐⇒
λ1
ρ1 =
<1
⇐⇒
m 1 µ1

75/8
75
5
ρ1 =
=
= <1
1 · 15
120
8

. Deuxième file stable ⇐⇒
λ2
ρ2 =
<1
⇐⇒
m 2 µ2

15/2
15
3
ρ2 =
=
= <1
1 · 10
20
4

=⇒ le réseau est stable et possède une distribution stationnaire

unique et à forme produit :
x1 x2
x1 x2
3
3 5
3 5
1 3
x1
x2

π (x1 , x2 ) = (1 − ρ1 )ρ1 (1 − ρ2 )ρ2 =
=
8 8
4 4
32 8
4

où x1 ≥ 0 et x2 ≥ 0 représentent, respectivement, le nombre de
clients dans la première et la deuxième file.
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.14

Mesures de performance
Le nombre moyen de clients présents dans la première file est :
¯1 =
N


∞ X
X

x1 π ∗ (x1 , x2 ) =

x1 =0 x2 =0

=


X


∞ X
X

x1 (1 − ρ1 )ρx1 1 (1 − ρ2 )ρx2 2

x1 =0 x2 =0

x1 (1 − ρ1 )ρx1 1

x1 =0

!
|

5
5/8
ρ1
= .
=
=
1 − ρ1
1 − 5/8
3


X

x2 =0

(1 − ρ2 )ρx2 2
{z
1

!
}

De même, le nombre moyen de clients dans la deuxième file est
¯2 =
N

ρ2
3/4
= 3.
=
1 − ρ2
1 − 3/4
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.15

Mesures de performance (2)
Le temps moyen de séjour d’un client dans le système est
¯sys
¯2
¯1 + N
N
5/3 + 3
7
N
¯
=
=
= [h]
T =
λsys
γ1
6
9

où λsys est le taux global d’arrivée dans le système (ici,
simplement γ1 ).

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.16

Mesures de performance (2)
Le temps moyen de séjour d’un client dans le système est
¯sys
¯2
¯1 + N
N
5/3 + 3
7
N
¯
=
=
= [h]
T =
λsys
γ1
6
9

où λsys est le taux global d’arrivée dans le système (ici,
simplement γ1 ).
Remarque. Une erreur à ne pas commettre est de calculer T¯ à
l’aide de
T¯ = T¯1 + T¯2

avec

¯1
8
N
5/3
¯
=
T1 =
=
λ1
75/8
45

et

¯2
2
N
3
¯
= .
T2 =
=
λ2
15/2
5
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.16

Réseau de Jackson fermé : exemple
r21 = 1
r12 = 1
−/M/1

−/M/1

µ1 = 15

µ2 = 10

Le système contient à tout instant K = 10 clients.

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.17

Réseau de Jackson fermé : exemple
r21 = 1
r12 = 1
−/M/1

−/M/1

µ1 = 15

µ2 = 10

Le système contient à tout instant K = 10 clients.
Équations de conservation du flot :

(

λ1 = λ 2
λ2 = λ 1

.

=⇒ le système possède une infinité de solutions !

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.17

Réseau de Jackson fermé : exemple
r21 = 1
r12 = 1
−/M/1

−/M/1

µ1 = 15

µ2 = 10

Le système contient à tout instant K = 10 clients.
Équations de conservation du flot :

(

λ1 = λ 2
λ2 = λ 1

.

=⇒ le système possède une infinité de solutions !

Le système est toujours stable car le nombre de clients est fixe !
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.17

Distribution stationnaire
Les probabilités stationnaires π(x1 , x2 ) d’avoir x1 clients dans la
première file et x2 clients dans la seconde ne sont définies que
pour les valeurs entières et non négatives de x1 et x2 vérifiant
x1 + x2 = 10.

Il n’y a donc que 11 couples différents pour lesquelles elles sont
définies.
La distribution stationnaire du système est, ici aussi, à forme
produit et est donnée par
1
1
π (x) = π (x1 , x2 ) =
F1 (x1 )F2 (x2 ) =
G(10)
G(10)






λ1
µ1

x1

λ2
µ2

x2

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.18

Distribution stationnaire (2)
Dans l’expression
x1



λ1
µ1

(x1 , x2 ) ∈ S = {(x1 , x2 ) ∈

2

1
π (x1 , x2 ) =
G(10)


λ2
µ2

x2

qui n’est applicable que pour
| x1 + x2 = 10},

les « taux » λ1 et λ2 correspondent à une solution quelconque
des équations de conservation du flot. Fixant, arbitrairement,
λ1 = 1, on obtient dans notre cas λ2 = λ1 = 1 et
1
π (x1 , x2 ) =
G(10)




1
15

x1

1
10

x2

(x1 , x2 ) ∈ S.
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.19

Constante de normalisation
La constante G(10) est une constante de normalisation assurant
que la somme des probabilités stationnaires est égale à 1 :
x1 10−x1 10 X
x1
10
10
X
1
1
1
10
G(10) =
=
15
10
10
15
x1 =0
x1 =0
!

10 X
10
11
10 x1
1 − 23
1
1
2
=
=
.
2
10
3
10
1− 3
x =0
1

´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.20

Constante de normalisation : cas général
Pour un réseau de Jackson fermé comptant n files
exponentielles et K clients, la distribution stationnaire n’est
définie que pour les états x = (x1 , . . . , xn ) vérifiant
x = (x1 , . . . , xn ) ∈ SK



= (x1 , . . . , xn ) ∈




X
n


n
xj = K .


j=1

Même pour des valeurs modérées de n et K , l’ensemble S K est
énorme :


|SK | =

n+K −1
K

(n + K − 1)!
=
K!(n − 1)!

=⇒ le calcul de la constante G(K) constitue l’une des principales

difficultés lors de l’étude d’un réseau de Jackson fermé.
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.21

Réseaux BCMP
Les réseaux de Jackson ne sont pas les seuls réseaux
possédant une distribution stationnaire à forme produit. Une
classe importante de tels réseaux, englobant ceux de Jackson,
sont les réseaux BCMP dont le nom fait référence à leurs
« inventeurs » : Baskett, Chandy, Muntz et Palacios.
Ces réseaux généralisent ceux de Jackson et sont formés
a) de files exponentielles −/M/m − F IF O
b) de centre de délai −/M/∞ ou −/G/∞
c) de files −/G/1 − LIF O − P R
d) de files −/G/1 − P S
La forme produit est cependant loin d’être la règle !
´
ˆ
Recherche operationnelle,
J.-F. Heche,
EPFL – p.22


Aperçu du document Reseaux.pdf - page 1/25

 
Reseaux.pdf - page 3/25
Reseaux.pdf - page 4/25
Reseaux.pdf - page 5/25
Reseaux.pdf - page 6/25
 




Télécharger le fichier (PDF)


Reseaux.pdf (PDF, 174 Ko)

Télécharger
Formats alternatifs: ZIP Texte



Documents similaires


reseaux
grp ti 13 09 2013
informatique complet 1
2012 10 10 1414 jdc chauffage climatisation co
memoire de master
reseau concepts

Sur le même sujet..




🚀  Page générée en 0.034s