Bornes Stochastiques (stochastic Bounds)

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Université Abderrahmane Mira de Béjaia Ecole Doctorale d’Informatique

Option : REseaux et SYstèmes Distribués

Bornes stochastiques (Stochastic bounds)

Nadir BOUCHAMA Saïd YAHIAOUI

JUILLET 2004

http://www.univ-bejaia.dz/ http://www.lamos.org

Sommaire Résumé ...................................................................................................................................... 1 Introduction .............................................................................................................................. 2 I.

Chaînes de Markov à grand espace d’états .................................................................. 2 1.

II.

Méthode des bornes stochastiques ............................................................................................. 3

Ordres stochastiques (Stochastic orderings).................................................................. 4

1. 2. 3.

Principe....................................................................................................................................... 4 Ordre stochastique fort (strong stochastic order) ....................................................................... 4 Comparaison de deux chaînes de Markov.................................................................................. 5

III.

Algorithme de VINCENT .............................................................................................. 6

1. 2. 3.

Principe....................................................................................................................................... 6 Notation...................................................................................................................................... 7 Remarques importantes sur l’algorithme de Vincent ................................................................. 7

IV. 1. 2.

V.

Améliorations de l’algorithme de VINCENT............................................................... 8 Résoudre le problème de suppression de transitions dans la matrice v(P) ................................. 8 Amélioration de l’exactitude des bornes ................................................................................... 8

Méthodologie pour réduire la compléxité ................................................................... 10 1. 2. 3.

VI. 1. 2. 3.

Matrices Hessenberg-supérieures............................................................................................. 11 Notion de décomposabilité (lumpability) ................................................................................. 11 Matrices de la classe C ............................................................................................................. 12

Ordre ICX .................................................................................................................... 14 Définitions et notations ............................................................................................................ 14 Remarque sur l’algorithme de construction d’une borne supérieure icx-monotone................. 15 icx-monotonicité pour les matrices stochastiques de la classe C ............................................. 16

VII. Applications des bornes stochastiques........................................................................ 16 VIII. Exemple ......................................................................................................................... 16 CONCLUSION....................................................................................................................... 22 BIBLIOGRAPHIE ................................................................................................................. 23

Bornes stochastiques

Résumé L’intérêt des bornes stochastiques est d’éviter le problème numérique dû à la taille des modèles originels et de calculer rapidement un encadrement des quantités à évaluer. Ceci permet de montrer que les contraintes de Qualité de Service (QoS) sont satisfaites, mais pas d’obtenir une valeur exacte. Plus précisément, cette approche consiste à construire des modèles qui fournissent des bornes supérieures (upper bounds) ou inférieures (lower bounds) des distributions stationnaires ou transitoires, ou plus simplement de leurs premiers moments. Il est à noter que le cadre de travail considéré ici est les Chaînes de Markov à Temps Discret (CMTD). Dans ce rapport nous essayerons d’introduire au lecteur la notion de bornes stochastiques. Nous donnerons d’abord les fondements théoriques ainsi que l’algorithme de Vincent qui est le point de départ pour tous les autres algorithmes cités infra. Par la suite, on reprendra un exemple pratique de l’utilisation des bornes stochastiques pour l’évaluation des taux de pertes de cellules dans un tampon (buffer) d’ un commutateur ATM.

Mots clés : Bornes stochastiques, ordre stochastique, chaînes de Markov, st-monotonicité, fonctions de récompense, ordre de Stoyan, ordre icx, algorithme de Vincent.

BOUCHAMA Nadir et YAHIAOUI Saïd

1

RESYD 2004

Bornes stochastiques

Introduction La complexité des systèmes informatiques ne fait qu’augmenter. Par conséquent, il faut développer des outils puissants pour leur planification et gestion. Afin de raccourcir les délais de prototypage et de test, des méthodes de modélisation et de prédiction de performances sont mises en œuvre. De façon générique, ces deux étapes sont appelés évaluation de performances [FER 98]. L’évaluation de performances des systèmes informatiques a pour objectif d’obtenir des valeurs numériques d’un certain nombre d’indices dont on considère qu’ils rendent compte de leurs performances. Trois catégories de méthodes sont employées dans ce but : les techniques de mesures, la simulation et les méthodes analytiques, ces deux dernières étant fondées sur des modèles des systèmes étudiés qui font eux-même référence à des théories mathématiques [MOR 03]. Lorsque la taille du modèle markovien empêche sa résolution exacte à l’équilibre, il reste au modélisateur à se tourner vers une des trois approches classiques : la simulation, l’approximation ou les méthodes de bornes [MOR 03]. Pour les systèmes trop importants pour permettre une étude exacte, markovienne ou non, on a recours aux méthodes approchées ou aux méthodes dites de bornes. Les méthodes de bornes stochastiques conduisent à résoudre des systèmes plus simples qui sont déduits du modèle (réseau de files d’attente ou autres). Un des intérêts de ces techniques est de garantir une estimation de l’erreur commise en utilisant les bornes en lieu et place des indices exacts, pour autant bien entendu qu’on dispose de majorations et minorations au niveau du modèle.

I. Chaînes de Markov à grand espace d’états Pour les systèmes de communication où l’interaction entre les différents objets est très complexe et les méthodes classiques d’évaluation de performances ne sont pas adéquates pour faire face à cette complexité, il faut développer des outils mathématiques et logiciels très performants. Depuis les travaux de Brigitte Plateau sur la décomposition et la représentation compacte d’une chaîne de Markov en utilisant les Réseaux d’Automates Stochastiques (RAS), on sait comment modéliser les systèmes complexes à composant en interaction et à grand espace d’états [FOU 03a]. L’idée principale dans l’approche des RAS est de décomposer le système en ses composants et de modéliser chaque composant de façon séparée. Une fois ceci fait, les interactions et les dépendances entre composants peuvent être ajoutées pour compléter le modèle. La matrice stochastique de la chaîne est obtenue par des sommations et produits tensoriels des composants locaux [FOU 03a].

BOUCHAMA Nadir et YAHIAOUI Saïd

2

RESYD 2004

Bornes stochastiques En fait, l’avantage des RAS est double : 1. Chaque composant du système peut être modélisé plus facilement, 2. L’espace requis pour le stockage de la matrice de transition est plus petit. La représentation tensorielle est donnée par : P = ∑ ⊗j M ij i

Mais, l’utilisation de cette représentation au lieu de la représentation éparse de la matrice de transition augmente le temps nécessaire pour l’analyse numérique des chaînes de Markov. Malgré le nombre considérable de travaux faits pour l’analyse numérique des chaînes de Markov, des problèmes se posent toujours quand l’espace des états est très grand. Heureusement, lors de la modélisation des réseaux à haut débit il est souvent suffisant de satisfaire les exigences attendues en Qualité de Service (QoS). En effet, des valeurs exactes des indices de performances ne sont pas nécessaires dans ce cas. De ce fait, il nous est suffisant d’encadrer les fonctions de récompense. Supposons que nous devons modéliser un système possédant une chaîne de Markov à grand espace d’états, nous avons besoin de calculer son état stationnaire (steady-state) afin d’obtenir des fonctions de récompense (rewards functions).

1. Méthode des bornes stochastiques 1.1. Idée clé Les méthodes de réduction de l’espace des états ont montré leur puissance pour faire face au problème d’explosion de l’espace des états [DAY 99][FOU 95][BEN 02a]. L’idée clé de la méthode des bornes stochastiques est de concevoir une nouvelle chaîne de Markov telle que les fonctions de récompense de celle-ci soient une borne supérieure (upper bound) ou inférieure (lower bound) des fonctions de récompense de la chaîne de Markov originale. La nouvelle chaîne est un modèle agrégé ou simplifié du modèle original. En fait, ces bornes et les critères de simplification sont basés sur la notion d’ordre stochastiques (stochastic orderings) appliqués aux chaînes de Markov.

Ainsi, comme l’espace des états et/ou la complexité ont été considérablement réduits, on peut par la suite utiliser les méthodes numériques pour calculer efficacement des bornes stochastiques pour les fonctions de récompense. Plusieurs méthodes ont été proposées pour borner les fonctions de récompense : résolution d’un système algébrique linéaire par Courtois et Semal, le processus markovien de décision par van Dijk, etc. [FOU 03a][FOU 03b]

BOUCHAMA Nadir et YAHIAOUI Saïd

3

RESYD 2004

Bornes stochastiques

1.2. Les deux étapes d’obtention des bornes L’obtention des bornes stochastiques se fait en deux étapes : 1. Obtenir une matrice bornante (bounding matrix) ainsi qu’une borne des distributions 2. Simplifier les calculs pour la résolution numérique.

II. Ordres stochastiques (Stochastic orderings) 1. Principe La méthode des ordres stochastiques pour l’évaluation des performances consiste à encadrer stochastiquement l’indice des performances considéré. Autrement dit, on définit un ordre entre la distribution de probabilités de la variable d’état du système analysé et celle d’un système qui fournira le majorant (ou le minorant) de l’indice de performance étudié. En général, l’espace d’états est discret et dénombrable. Plusieurs ordres stochastiques existe en littérature : ordre sample-path, ordre st, ordre icx, etc [BEN 00][DAY 99][YAZ 91]. Soient deux variables aléatoires X et Y qui prennent des valeurs dans un espace totalement ordonné et qui sont comparables dans les sens de l’ordre stochastique fort. Intuitivement, X <st Y signifie qu’il est plus probable pour X de prendre des valeurs que Y [DAY 99][BEN 00] alors que X
2. Ordre stochastique fort (strong stochastic order) On se restreint ici aux Chaînes de Markov à Temps Discret (CMTD) avec un espace d’états fini E = {1, 2,…, n}. Les modèles à temps continu peuvent être aussi considérés après uniformisation. On note par Pi,* la ligne i de la matrice P. Selon Dietrich Stoyan, on peut définir l’ordre stochastique fort par un ensemble de fonctions non décroissantes ou par la matrice Kst.

Définition 1 Soient X et Y des variables aléatoires prenant des valeurs dans un espace totalement ordonné. Alors X est dit plus petit que Y dans l’ordre stochastique fort noté X <st Y si et seulement si E[ f(X)] ≤ E[ f(Y)] pour toutes les fonctions non décroissantes f où les espérances existent.

BOUCHAMA Nadir et YAHIAOUI Saïd

4

RESYD 2004

Bornes stochastiques Si X et Y prennent des valeurs dans l’espace fini d’états {1, 2,...,n} avec p et q comme vecteurs de distribution de probabilités, alors X est dit plus petit que Y dans l’ordre stochastique fort n

noté X <st Y si et seulement si ∑ Pj ≤ j =k

n

∑q

j

pour k=1,2,…n.

j =k

Les indices de performances tels que la population moyenne, le taux de perte sont des fonctions non décroissantes. Par conséquent, les bornes sur les distributions impliquent des bornes sur les indices de performances.

Définition 2 (en utilisant la matrice Kst) Si X et Y prennent des valeurs dans l’espace d’états fini {1, 2,…, n} avec p et q comme vecteurs de distribution de probabilité alors X est dit plus petit que Y dans le sens stochastique fort noté X <st Y si et seulement si p.Kst ≤ q.Kst

Avec Kst =

1

0

0 ... 0

1

1

0 ... 0

1

1

1 ... 0

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

1

1 ... 1

Exemple Soient α= (0.1, 0.3, 0.4, 0.2) et β = (0.1, 0.1, 0.5, 0.3) deux vecteurs de distributions de probabilité. Alors on a α <st β car : 0.2 ≤ 0.3 0.4 | 0.2 ≤ 0.5 | 0.3 0.3 | 0.4 | 0.2 ≤ 0.1 | 0.5 | 0.3

3. Comparaison de deux chaînes de Markov Il est connu depuis longtemps que la monotonicité et la comparabilité des matrices de transitions sont suffisantes pour comparer deux CMTDs. Dans ce qui suit nous donnerons la définition de la st-monotonicité.

3.1. St- monotonicité Définition Soit P une matrice stochastique. P est st-monotone si et seulement si pour tout u et v si u <st v alors u.P <st v.P

BOUCHAMA Nadir et YAHIAOUI Saïd

5

RESYD 2004

Bornes stochastiques

3.2. Comparaison stochastique de deux matrices stochastiques La monotonicité et la comparabilité des matrices de transitions sont suffisantes pour comparer deux CMTDs.

Définition Soient P et Q deux matrices stochastiques. Alors P <st Q sauf seulement si P.Kst ≤ Q.Kst Ceci peut être caractérisé par Pi,* <st Qi,* pour tout i.

III. Algorithme de VINCENT 1. Principe Pour qu’une matrice carrée Q soit une borne supérieure st-monotone pour une matrice carrée P de même dimension, il faut que le système d’inéquations suivant soit vérifié : n

∑

k= j

P i, k ≤

n

∑Q

i,k

k= j

≤

n

∑Q

i, k

k= j

n

∑Q

i +1 ,k

k= j

∀ i, j

∀ i, j

(1)

L’idée de base dans l’algorithme de Vincent est de remplacer les inéquations dans le système (1) par des équations comme dans le système d’équations (2) : n

∑

k = j

P i, k =

n

∑Q k= j

i,k

=

n

∑

Q

i,k

k = j

∀ i, j

(2)

n

∑Q

i +1 ,k

k= j

∀ i, j

Algorithme de Vincent

Algorithme 1: Construction d’une borne supérieure st-monotone optimale Q q1,n = p1,n ; pour i =2,3,…,n faire qi,n = max (qi-1,n, pi,n) ; fait pour l = n-1,n-2,…1 faire q1,l = p1,l ; pour i =2,3,…,n faire n

n

n

j =1

j =1

j=i +1

qi,l = max(∑qi−1, j ,∑ pi, j) − ∑qi, j ; fait

fait

BOUCHAMA Nadir et YAHIAOUI Saïd

6

RESYD 2004

Bornes stochastiques

2. Notation Nous noterons v(P) la matrice obtenue en appliquant l’algorithme de Vincent à la matrice de transition P.

Exemple de déroulement de l’algorithme de Vincent 0.5 0.2 0.1 0.2 0.0

0.5 0.2 0.1 0.2 0.0

P1 =

0.1 0.7 0.1 0.0 0.1 0.2 0.1 0.5 0.2 0.0

v(P1) =

0.1 0.6 0.1 0.1 0.1 0.1 0.2 0.5 0.1 0.1

0.1 0.0 0.1 0.7 0.1

0.1 0.0 0.1 0.7 0.1

0.0 0.2 0.2 0.1 0.5

0.0 0.1 0.1 0.3 0.5

Calcul de l’état stationnaire En calculant les distributions stationnaires on trouve :

•

πp1 = (0.180, 0.252, 0.184, 0.278, 0.106)

•

πQ = (0.143, 0.190, 0.167, 0.357, 0.143) (On peut vérifier facilement que : πp1 <st πQ )

•

Espérances : 1.87 pour P1 et 2.16 pour v(P1)

3. Remarques importantes sur l’algorithme de Vincent 3.1. Optimalité L’algorithme de Vincent donne la plus petite borne supérieure dans le sens de l’ordre stochastique fort. Ceci est donné dans le théorème 1 suivant :

Théorème 1 L’algorithme de Vincent offre la plus petite borne supérieure st-monotone pour une matrice P. Autrement dit, si on considère une autre borne supérieure st-monotone U pour P, alors Q<st U.

Cependant, des améliorations peuvent être faites pour améliorer la précision des bornes sur les fonctions de récompense. On verra infra comment utiliser des polynômes pour améliorer l’exactitude des bornes.

3.2. Suppression de transitions dans la matrice v(P) Il peut arriver que la matrice v(P) calculée par l’algorithme de Vincent soit réductible bien que P ne l’est pas.

3.3. Complexité Il arrive que v(P) soit plus difficile à résoudre que P. Par exemple:

P=

0.5 0.2 0.1 0.1 0.1

0 . 5 0 . 2 0 .1 0 . 1 0 . 1

1.0 0.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0

0 . 5 0 . 2 0 .1 0 . 1 0 . 1

v(P) =

0 . 5 0 . 2 0 .1 0 . 1 0 . 1

1.0 0.0 0.0 0.0 0.0

0 . 5 0 . 2 0 .1 0 . 1 0 . 1

1.0 0.0 0.0 0.0 0.0

0 . 5 0 . 2 0 .1 0 . 1 0 . 1

BOUCHAMA Nadir et YAHIAOUI Saïd

7

RESYD 2004

Bornes stochastiques

On voit bien que la matrice originale P est plus facile à résoudre que v(P)celle obtenue en appliquant l’algorithme de Vincent à la matrice P

IV. Améliorations de l’algorithme de VINCENT 1. Résoudre le problème de suppression de transitions dans la matrice v(P) Comme nous m’avons vu dans la remarque 2, il peut arriver que la matrice v(P) obtenue en appliquant l’algorithme de Vincent à la matrice P soit réductible bien que P ne l’est pas. Quelques éléments de v(P) peuvent être nuls alors que les éléments correspondants dans la matrice P sont strictement positifs. Pour ce faire une amélioration de l’algorithme de Vincent est donnée dans l’algorithme 2 ci-dessous :

Algorithme 2: Construction d’une borne supérieure st-monotone optimale Q sans suppression des transitions q1,n = p1,n ; pour i =2,3,…,n faire qi,n = max (qi-1,n, pi,n) ; fait pour l = n-1,n-2,…1 faire q1,l = p1,l ; pour i =2,3,…,n faire n

n

n

j =1

j =1

j=i +1

qi,l = max(∑qi−1, j ,∑ pi, j) − ∑qi, j ; n

si (qi,l = 0) et (pi,l > 0) et (

∑qi, j < 1)

alors

j = i +1

qi,l= ε * (1-

n

∑qi, j ) ; fait

j = i +1

fait Remarque : ε est une valeur réelle positive strictement inférieure à 1. L’algorithme 2 essaye de garder presque toutes les transitions de P dans v(P). Une preuve nécessaire et suffisante sur p pour obtenir une matrice irréductible est donnée par le théorème 2 suivant :

Thèorème 2 Soit P une matrice stochastique finie irréductible. La matrice Q calculée à partir de P par l’algorithme 2 est irréductible si et seulement si chaque ligne du tringle inférieur de la matrice P contient au moins un élément strictement positif.

2. Amélioration de l’exactitude des bornes En fait, comment peut-on améliorer l’exactitude de la distribution de l’état stationnaire ?

BOUCHAMA Nadir et YAHIAOUI Saïd

8

RESYD 2004

Bornes stochastiques Ceci peut se faire en appliquant quelques transformations sur P avant d’appliquer l’algorithme de Vincent

2.1. Utilisation de polynômes 2.1.1. Idée clé En premier lieu, utiliser une fonction α(P,δ)=(1−δ).I +δ.P avec δ∈[0.1] . En effet :




Ceci n’a aucun effet sur la distribution de l’état stationnaire,




Ceci a une large influence sur l’algorithme de Vincent.

Théorème 3 Soient P une CMTD et deux variables réelles δ1, δ2 ∈ [0,1] et tels que δ1 < δ2. Alors:

π

v ( α ( P , δ 1 ))

< st πv (α ( P , δ 2 )) < st πv ( P )

2.1.2. Choix de δ Définition : Une matrice est dite à diagonale dominante si tout ses élément diagonaux sont supérieurs ou égaux à 0.5.

Corollaire : Si P est une matrice stochastique à diagonale dominante. Alors v(P) et v(α(P)) ont la même distribution de probabilité à l’état stationnaire.


δ = ½ est suffisant pour transformer une matrice stochastique arbitraire en une matrice à diagonale dominante Par conséquent, la transformation P/2 + I/2 offre la meilleure borne.

Définition : Soit D l’ensemble des polynômes Φ() tels que Φ(1) =1, Φ différent de l’identité, et tout les coefficients de Φ sont non négatifs.

Théorème 4 Soit Φ un polynôme arbitraire dans D. L’algorithme de Vincent appliqué surΦ(P) fournit une borne plus exacte que l’état stationnaire de Q. Autrement dit :

πP <st πv(Φ(P)) <st πv(P) Remarque Plus le degré de Φ est plus grand, plus la borne v(Φ(P)) est exacte. Ceci est illustré dans l’exemple suivant :

Exemple : Soit la matrice stochastique suivante : 0 .1 0 .2 0 .4 0 .3 P3 =

0 .2 0 .3 0 .2 0 .3 0 .1 0 .5 0 .4

0

0 .2 0 .1 0 .3 0 .4

BOUCHAMA Nadir et YAHIAOUI Saïd

9

RESYD 2004

Bornes stochastiques




On étudiera les polynômes Φ(X) = X/2 + I/2 et Ψ(X) = X2/2 + I/2

Les résultats sont les suivants : 0.55 0.1

Φ (P3) =

0 .1

0 .2

0.15

0.65 0.1

0.15

0.05 0.25 0.7 0 .1

0.55 0.1 v(Φ (P3)) =

0.575 0.155 0.165 0.105

0.17

0.55 0.2

0.15

0.05 0.1

0.05 0.15 0.7

0.075 0.13

0.15

0.05 0.25 0.55 0.15

0

Ψ (P3) = 0.08 0.63 0.155 0.135 0.075 0.185 0.65 0.09

0 .1

0 .2

0.15 0.7

0.575 0.155 0.165 0.105 v(Ψ (P3)) =

0.08

0.63

0.155 0.135

0.075 0.185 0.605 0.135

0.625

0.075 0.13

0.17

0.625

D’autre part, on a : 0 .1 0 .2 0 .4 0 .3 v (P3) =

0 .1 0 .2 0 .4 0 .3 0 .1 0 .2 0 .4 0 .3 0 .1 0 .2 0 .3 0 .4

On calcule les états stationnaires :

πv(P3) = (0.1, 0.2, 0.3667, 0.3333) πv (Φ(P3)) = (0.1259, 0.2587, 0.2821, 0.3333) πv(ψ(P3)) = (0.1530, 0.2997, 0.2916, 0.2557) πP3 = (0.1530, 0.3025, 0.3167, 0.2278) Il est très clair que les bornes obtenues par Ψ sont plus exactes que les autres bornes.

V. Méthodologie pour réduire la compléxité Pour réduire la complexité de résolution des systèmes d’équation, on peut :




Utiliser des matrices avec des propriétés structurelles et numériques particulières




Utiliser des algorithmes (plus efficaces) pour la résolution numérique




Utiliser des matrices à caractéristiques spéciales: matrices de Hessenberg, matrices

décomposables en blocs, matrices de classe C ,etc.

BOUCHAMA Nadir et YAHIAOUI Saïd

10

RESYD 2004

Bornes stochastiques

1. Matrices Hessenberg-supérieures 1.1. Définition Une matrice H est dite Hessenberg-supérieure sauf seulement si Hi,j= 0 pour i > j+1. En fait, les matrices Hessenberg-supérieures font mouvoir la masse probabilité de la gauche vers la droite.

Algorithme 3 : Construction d’une borne supérieure st-monotone et Hessenberg Supérieure Q q1,n = p1,n ; pour i =2,3,…,n faire q1,i = p1,i ; qi+1,n= max (qi,n, pi+1,n ) ; fait pour i =2,3,…,n faire pour l = n-1,n-2,…,i faire pour i =2,3,…,n faire qi,l = max(

n

n

n

j =1

j =1

j=i +1

∑qi −1, j ,∑pi,l) − ∑qi, j ; fait n

si (qi,l = 0) et (pi,l > 0) et (

∑q

i, j

< 1) alors

j = i +1

qi,l = ε * (1-

n

∑qi, j ) ; fait

j = i +1 n

qi,i-1 = 1-

∑qi, j

;

j =i

pour l = i-2, i-3,…,1 faire qi,l = 0 ; fait fait

2. Notion de décomposabilité (lumpability) Le principe de décomposabilité de la matrice transition a été utilisé par Truffet pour les réseaux de commutation de l’ATM. En fait, la décomposabilité implique une réduction de l’espace des états. Ceci est très intéressant pour les systèmes complexes à grand espace d’états.

2.1. Définition de la décomposabilité ordinaire (ordinary lumpability) Soit X une CMTD finie irréductible, Q sa matrice de transition, soit Ak une partition des états. X est ordinairement décomposable par rapport à Ak, sauf seulement si pour tous les états e et f dans le même macro-état Ai on a :

∑q

e, j

j∈ Ak

BOUCHAMA Nadir et YAHIAOUI Saïd

=

∑q

j∈ Ak

f, j

pour tout macro-état Ak

11

RESYD 2004

Bornes stochastiques

2.2. Propriétés des blocs Supposons que les états sont ordonnés selon la partition des macro-états

Théorème 5 Soit Q une matrice st-monotone qui est une borne supérieure pour P. Supposons que Q est ordinairement décomposable pour la partition Ak et soit Qm,l et P m,l les blocs de transitions de l’ensemble Am vers l’ensemble Al pour P et Q respectivement, alors pour tout m et l, le bloc Qm,l est st-monotone.

Algorithme 3 : Construction d’une borne supérieure st-monotone et ordinairement décomposable Q q1,n = p1,n ; pour i = 2,3,…,n faire qi,n = max (qi-1,n, pi,n) ; pour x = r, r-1,…,1 faire pour l = e(x)…b(x) faire si l
q 1,1 = max( 0 , ∑ p 1, l − j=l

n

∑q

1, j

);

j = l +1

pour i = 2, 3, …., n faire

q 1,1 = max( 0 , max(

n

n

j =l

j=1

∑ q i − 1, j , ∑ p i, l) −

n

∑q

i, j

); fait;

j = l +1

fait; pour y = 1,2,…, r faire

c=

c( x)

∑q

e ( y ), j

;

j =b( x)

c( x)

pour I = b(y),…, e(y) faire qi,b(x) = c -

∑q

i, j j = b ( x ) +1

; fait ;

fait ; fait ;

3. Matrices de la classe C [BEN 02a][FOU 03a][FOU 03b] 3.1. Définition Une matrice stochastique Q = (qi,j)1≤ i,j ≤ n appartient à la classe C si pour chaque colonne j il existe une constante réelle cj satisfaisant les conditions suivantes: qi+1,j = qi,j + cj

1≤ i≤ n-1

Puisque Q est une matrice stochastique, la somme des éléments de chaque ligne doit être n

égale à 1, ainsi :

∑c n =1

j

= 0

BOUCHAMA Nadir et YAHIAOUI Saïd

12

RESYD 2004

Bornes stochastiques

3.2. Intérêt des matrice de la classe C Les matrices stochastiques de la classe C ont des propriétés très intéressantes. par exemple :




Leur état stationnaire peut être résolu en un temps linéaire. En effet, on a :

j q 1, j − 1 ∑ j=1 n

π j = q 1, j + c j *

n

1-∑ j c j j =1




La caractérisation de la st-monotonicité est très simple aussi dans cette classe. Elle est donnée par la propriété suivante :

Propriété Soit P une matrice stochastique appartenant à la classe C. P est st-monotone sauf seulement si : n

∑c

k

≥ 0 ∀j ∈ {1,...,n}

k= j

Algorithme 4: Construction d’une matrice bornante supérieure st-monotone Q appartenant à la classe C

(n−1)pi, n −(i −1) ]; n−i pi, n −q1, n + cn = [max 2≤ i ≤n ( )] ; i −1 pour j = n-1, n-2,…2 faire

qi,n = max 1≤ i ≤n-1[

n  n p i,k − ∑ q 1 ,k ∑  k= j αj = max 2≤ i ≤n  k = j i − 1  

  ;  

n   n  i −1  n n −1 p i , k − q i , k q n ,k −1 ; gi = +    n−i  k = j k = j +1  n − i  k = j +1 

∑

∑

∑

q1,j = [max 1≤ i ≤ n-1 gi]+ ;

− q 1, j ,α cj = max ( n −1

+ j

−

n

∑

c k );

k = j +1

fait; n

q1,1 = 1 -

∑ q1 j=2

,j

;

Remarque Les propriétés et leurs démonstrations des matrices de la classe C sont étudiées en détails dans le papier [BEN 02b].

BOUCHAMA Nadir et YAHIAOUI Saïd

13

RESYD 2004

Bornes stochastiques

VI. Ordre ICX [YAZ 91][FOU 03b] 1. Définitions et notations Définition Soient X et Y des variables aléatoires prenant des valeurs dans un espace totalement ordonné. Alors X est dit X
Définition (en utilisant la matrice Kicx) Si X et Y prennent des valeurs dans l’espace d’états fini {1, 2,…, n} avec p et q comme des vecteurs de distribution de probabilité alors X
Avec Kicx =

1

0

0

... 0

2

1

0

... 0

3 ...

2 ...

1 ...

... 0 ... 0

n

n − 1 n − 2 ... 1

Autre notation algébrique n

X < icx Y ⇔ ∑ ( k − i +1 ). p k ≤ k =i

n

∑ ( k − i +1 ). q

k

∀ i ∈ {1,.., n}

k =i

Exemple Soit les deux vecteurs α = (0.2, 0.4, 0.4) et β = (0.3, 0.1, 0.6). Alors on α



De façon similaire, l’ordre concave est défini par un ensemble de fonctions concaves non décroissantes ou par la matrice Kicv définie comme suit : T K icv = − K icx

La comparaison selon l’ordre « icx » ainsi que la monotonicité des matrices stochastiques sont définies de façon analogue que celles pour l’ordre « st ».

Une condition suffisante pour la icx-monotonicité est donnée par :

−1 K icx PK icx ≥ 0

BOUCHAMA Nadir et YAHIAOUI Saïd

14

RESYD 2004

Bornes stochastiques La condition ci-dessus conduit à une chaîne de Markov dont le dernier état est absorbant. Benmammoun à défini des conditions nécessaires et suffisantes pour la icx-monotonicité

Algorithme 6 : Construction d’une borne supérieure icx-monotone q1,n = p1,n ; q2,n = max (q1,n, p2,n) ; pour i = 3,…,n faire qi,n = max (pi,n, 2qi-1,n – qi-2,n) ; fait pour j = n-1, n-2,…, 2 faire q1,j = max (0, ∑ k = j (k − j + 1) p1, k − ∑ k = j −1 (k − j + 1)q1, k ) ; n

n

q2,j = max (max( ∑ k = j (k − j + 1) p 2, k , ∑ k = j (k − j + 1)q1, k ) n

n

∑

n k = j −1

(k − j + 1)q 2, k , 0) ;

pour i = 3, 4, …, n faire n qi,j = max (0, max ( ∑ k = j (k − j + 1) p i , k , 2∑k = j (k − j + 1)q i −1, k − ∑ k = j (k − j + 1)q i − 2, k ) n

-

∑

n k = j −1

n

(k − j + 1)q i , k ) ;

fait fait pour i = 1, 2,…, n faire qi,1 = 1 -

∑

n j =2

q i , j ; fait

2. Remarque sur l’algorithme de construction d’une borne supérieure icxmonotone La sortie de cet algorithme n‘est pas toujours une matrice stochastique (on trouve des fois des élément supérieurs à 1)




Il peut donner un bon résultat :




Comme il peut en donner un mauvais !!!

On remarque que l’élément q3,3 = 1.05. Par conséquent, Q ne peut être une matrice stochastique. Pour résoudre ce problème, des heuristiques ont été définies.

BOUCHAMA Nadir et YAHIAOUI Saïd

15

RESYD 2004

Bornes stochastiques

3. icx-monotonicité pour les matrices stochastiques de la classe C Proposition 1 n

P icx - monotone ⇔ ∑ (k − j +1 ) ck ≥ 0 k= j

Proposition 2 Si P est de la classe C alors on a : P est st-monotone ⇒ P est icx-monotone

Attention : Ceci n’est pas toujours vrai pour les matrices n’appartenant pas à la classe C Algorithme L’algorithme de construction d’une borne supérieure icx-monotone appartenant à la classe C est donné dans [FOU 03a].

VII. Applications des bornes stochastiques Dans la littérature, on trouve plusieurs applications des bornes stochastiques. Dans [BON 03], T.Bonald et A. Proutière utilisent la méthode des bornes stochastiques pour évaluer les performances des réseaux à processeur partagé. Dans [YAZ 91], N. Yazici-Pekergin et J.M. Vincent utilise l’ordre icx que nous avons défini supra pour borner les temps d’exécution de programmes parallèles en considérant que le nombre de processeurs est illimité.

Dans ce qui suit nous reprendrons un exemple cité dans [ABU 01][ABU 97][BEN 02b] [FOU 03b].

VIII. Exemple "Bornes stochastiques pour les taux de pertes dans un tampon mémoire ATM" Comme exemple, nous présentons l’analyse d’une politique d’un Tampon mémoire (Buffer) ATM, qui combine le mécanisme de "PushOut" pour la gestion de l’espace et la discipline de service "Head Of Line" [FOU 03a]. On suppose qu’il existe deux types de paquets avec des niveaux distincts de taux de pertes. On indique par haute priorité, les paquets qui ont les plus hautes exigences, c'est-à-dire, le plus petit taux de perte. Les paquets à basse priorité, sont ceux qui sont perdus lorsqu’ils arrivent et trouvent le tampon plein. Si le tampon n’est pas plein, les deux types de paquets sont acceptés.

BOUCHAMA Nadir et YAHIAOUI Saïd

16

RESYD 2004

Bornes stochastiques Le mécanisme "PushOut" spécifie que quand le tampon est plein, l’arrivée d’un paquet de haute priorité pousse dehors un paquet de basse priorité s'il y en a dans le tampon. Sinon le paquet de haute priorité est perdu. Comme la taille du tampon est B, le nombre d’états est (B + 1)(B + 2)/2 si les arrivées suivent un processus d’arrivées par groupe simple. Pour simplifier, la taille des groupes est supposée entre 0 et 2. On utilise la représentation suivante pour l’espace d’états (T, H) où T est le nombre total de paquets et H est le nombre de paquets de haute priorité. Les états sont ordonnés suivant un ordre lexicographique non décroissant. Il doit être clair à ce point que l’ordre des états est très important. En premier, les récompenses doivent être des fonctions non décroissantes des indices de performance. En outre, comme la propriété de la stmonotonicité est basée sur la représentation et l’ordre des états, l'exactitude des résultats peut dépendre de ce classement. La cellule à haute priorité pousse dehors la cellule à basse priorité

L

L

H

HHHHL L

Arrivée par groupe des cellule à haute et basse priorité

Temps de service déterministe La cellule à basse priorité est perdue

Figure 1 : Description du mécanisme « Push-Out »

Ici, nous sommes intéressés par le nombre attendu de paquet perdus par slot. On dénote par R Mi cette espérance mathématique pour les paquets de type i et soit R = R H + R L . Le problème difficile ici est le calcul de R H . En effet, R peut être calculé avec une plus petite chaîne puisque le mécanisme "Pushout" ne change pas le nombre global de pertes. Il est suffisant d’analyser le nombre global de paquets (c'est-à-dire : sans distinction). Une telle chaîne a seulement B + 1 états si on utilise un processus d’arrivées par groupe simple. Pour des valeurs réalistes de la taille du tampon (c’est-à-dire : 1000), une telle chaîne est très simple à résoudre avec les algorithmes numériques habituels. Cependant pour la même valeur de B, la chaîne des mécanismes HOL+Pushout a environ 5x105 états. Donc on utilise l'Algorithme 3 pour obtenir une matrice bornante décomposable et on analyse la chaîne de macro-états.

BOUCHAMA Nadir et YAHIAOUI Saïd

17

RESYD 2004

Bornes stochastiques En premier, on décrit d’abord l’ordre des états et les récompenses. Soit p kH la probabilité d’arrivée de k paquets de haute priorité durant un slot.

RH =

∑ Π (T , H ) p

H 2

max(0, ( H + 2 − B − 1T = H ))

(T , H )

Où 1T = H est une fonction indicatrice qui affirme si un paquet de haute priorité peut quitter le tampon à la fin du slot après achèvement du service (T = H : il n’y a aucun paquet de basse priorité). Donc max(0, ( H + 2 − B − 1T = H )) est le nombre de paquets qui dépassent la taille du tampon. Pour ce cas particulier, dû à l’ordonnancement des arrivés et au service, RH peut être calculé par une expression plus simple :

R H = p 2H × Π( B, B) Il est clair que, nous devons estimer seulement une probabilité et la récompense est une fonction non décroissante qui est nulle partout à l’exception du dernier état qui a pour valeur un. Pour un processus d’arrivées plus général, la fonction de récompense est seulement légèrement différente.

L’idée clé pour réduire l’espace d’états est d’éviter les états avec un grand nombre de paquets à basse priorité. Donc, on borne la matrice avec une matrice ordinairement décomposable Q avec ο ( B × F ) macro-états où le paramètre F permet un compromis entre la complexité de calcul et l’exactitude des résultats. Plus précisément, on définit les macro-états (T, Y ) où Y est contraint d’évoluer dans l’intervalle T…T-F. Si Y = T-F , alors l’état (T, Y ) est un réel macro-état qui contient tous les états (T, X ) tel que X ≤ T − F . Dans ce cas Y est une borne supérieure pour le nombre de paquets à haute priorité dans les états qui sont agrégés. Si Y > T − F alors l’état contient seulement un état (T, X ) où Y = X. Donc, Y représente

exactement le nombre de paquets à haute priorité dans le tampon (voir la figure 2). Il est clair que, si la valeur de F est grande, on ne réduit pas l’espace des états mais on s’attend à trouver des bornes plus étroites.

BOUCHAMA Nadir et YAHIAOUI Saïd

18

RESYD 2004

Bornes stochastiques Les états où des cellules de haute périorité peuvent être pérdues

Macro-états les états inchangés

Figure 2 : la chaîne agrégée

Dans [FOU 95], les auteurs ont analysé des tampons de petite taille pour montrer l’exactitude des bornes et des tampons de grande taille pour montrer l’efficacité de la méthode. Ici on présente une comparaison typique de ces bornes pour un tampon de petite taille (80 cellules). En effet, cette petite valeur permet le calcul de résultats exactes à des fins de comparaison. La charge est 0.9 avec 2/3 de paquets de haute priorité. Avec une valeur largement suffisante de F (typiquement 10), l’algorithme donne des résultats exacts. Le résultat exact pour RH dans cet exemple est 8.9 x 10-13. La borne avec F = 10 est 9.5 x 10-13 . Evidement, si F est très petit, le résultat est mauvais et peut atteindre 10-6 pour F = 2. La chaîne originale contient 3321 états alors que la borne avec F = 10 est calculée avec une chaîne de 798 états. Le nombre d’états est divisé par 4, et on perd seulement quelques chiffres. Il est intéressant de remarquer qu’une réduction par un ordre sur l’espace des états implique une réduction par deux ou trois fois les temps de calcul de la distribution stationnaire. La réduction est encore plus importante si la chaîne originale est plus grande. Typiquement, pour un tampon de 1000 et un facteur d’agrégation F égal à 20, la matrice bornante obtenue à partir de l’algorithme 5 a approximativement 20000 états. L’espace d’états original est 25 fois plus grand [FOU 03a]. Les résultats présentés précédemment sont très exacts. Il existe plusieurs raisons pour cette propriété. En premier, la distribution est asymétrique. Presque toute la masse de probabilité est concentrée dans les états avec un petit nombre de paquets. De plus, la première

BOUCHAMA Nadir et YAHIAOUI Saïd

19

RESYD 2004

Bornes stochastiques partie de la matrice initiale est déjà st-monotone. Cette propriété est dû à l’ordre des états considéré. Par exemple, on considère la matrice d’une chaîne pour un petit tampon de taille 4. la chaîne a 15 états ordonnés par ordre lexicographique : {(0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (3, 3), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)}. On dénote par p, q et r respectivement les probabilités d’arrivées pour les groupes de taille 0, 1 ou 2. Et a est la probabilité qu’un paquet arrivé soit d’une priorité basse. Similairement, b est la probabilité pour les paquets à haute priorité. Les distributions des types de paquets dans un groupe de taille 2 sont respectivement, c pour 2 paquets à basse priorité, e pour 2 à haute priorité, et d pour un groupe mixte.

La matrice P montre que les 10 premières ligne de la matrice satisfont déjà la propriété de st-monotonicité. Pour un model d’un tampon de grande taille, cette propriété est encore vraie pour les états où le tampon n’est pas plein. On suppose que F = 2, alors, on considère 2 macro-états réel : {(3, 2), (3, 3)} et {(4, 2), (4, 3), (4, 4)}. Il est à noter, que la matrice initiale est déjà décomposable puisque l’ordonnancement du service et des arrivées implique que quelques états ont des transitions similaires. Par exemple, les états (0), (1, 0) et (1, 1) peuvent être groupés en un seul macro-état. L’algorithme 4 fournit une matrice décomposable avec des macro-états déjà définis, qui peuvent être agrégés pour obtenir :

BOUCHAMA Nadir et YAHIAOUI Saïd

20

RESYD 2004

Bornes stochastiques

Tel que : f = min (qb, rc) et g = max (qb, rc).

BOUCHAMA Nadir et YAHIAOUI Saïd

21

RESYD 2004

Bornes stochastiques

CONCLUSION Ainsi, la méthode des bornes stochastiques permet de faire face au problème d’explosion d’états du modèle markovien et de vérifier que les exigences en Qualité de Service (QoS) sont vérifiées (notamment dans les réseaux à haut débit). Dans plusieurs cas, les bornes donnent une information suffisante sur le fonctionnement du système. D’autre part, il est à noter que l’ordre stochastique à choisir (ordre fort de Stoyan, ordre icx, sample-path ou autre) dépend de la fonction de récompense à étudier. Comme nous l’avons vu, plusieurs algorithme ont été définis pour trouver des matrices bornantes (bounding matrices) et peuvent être incorporés dans un logiciel d’évaluation de performances des systèmes basés sur les chaînes de Markov.

BOUCHAMA Nadir et YAHIAOUI Saïd

22

RESYD 2004

Bibliographie

BIBLIOGRAPHIE [ABU 97]

Oula ABU AMSHA, Jean Michel FOURNEAU et Nihal PEKERGIN, « Bornes stochastiques pour les taux de pertes dans un tampon mémoire ATM ». Mai 1997.

[ABU 01]

Oula ABU AMSHA, Jean Michel FOURNEAU et Nihal PEKERGIN, « Bornes stochastiques pour les taux de pertes dans un tampon mémoire ATM ». RSR-CP – 13/2001. Performances des réseaux et systèmes, pages 533 à 555.

[BEN 00]

Mouad BENMAMMOUN,et Nihal PEKERGIN, « Closed-form stochastic bounds on the stationary distribution of markov chains ». Laboratoire PRiSM. Université de Versailles Saint Quentin.

[BEN 01]

Mouad BENMAMMOUN et Nihal PEKERGIN, «Stochastic Delay Bounds of Fair Queuing Policies by Analyzing Weighted Round Robin Related Policies ».Submitted to Elsevier Science .12 November 2001.

[BEN 02a]

Mouad BENMAMMOUN, Jean-Michel FOURNEAU, Nihal PEKERGIN et Alexis TROUBNIKOFF, « An algorithmic and numerical approach to bound the performance of high speed networks ». Proceedings of the 10th IEEE Symposium on Modeling, Analysis & Simulation of Computer & Telecommunications Systems (MASCOTS’02).

[BEN 02b]

Mouad BENMAMMOUN et Nihal PEKERGIN, « Closed form stochastic bounds on the stationary distribution of markov chains ». Laboratoire PRiSM, Université de Versailles Saint Quentin.

[BON 03]

T.BONALD et Alexandre PROUTIERE, « On stochastic bounds for monotonic processor sharing networks ». France Telecom R&D. Article paru le 3 Juin 2003.

[DAY 99]

Tugrul DAYAR et Nihal PEKERGIN, «Stochastic Comparison, Reorderings, and Nearly Completely Decomposable Markov Chains ».Proceedings of the International Conference on the Numerical Solution of Markov Chains (NCMS 99). (Ed. Plateau , B.Stewart, W.). Prensas universitarias de Zaragoza. P 228-246.

[FER 98]

Paulo Henrique Lemelle FERNANDES, «Méthodes Numériques pour la Solution de Systèmes Markoviens à Grand Espace d’États ». Thèse de Doctorat d’Etat en Informatique soutenue en février 1998 à l’Institut National Polytechnique de Grenoble.

[FOU 95]

FOURNEAU J.M., PEKERGIN N., TALEB H., « An Application of Stochastic Ordering to the Analysis of the PushOut Mechanism », Performance Modelling and Evaluation of ATM Networks, Chapman and Hall, 1995, p. 227-244.

[FOU 03a]

Jean Michel FOURNEAU et Nihal PEKERGIN, « An algorithmic approach to

BOUCHAMA Nadir et YAHIAOUI Saïd

23

RESYD 2004

Bibliographie

stochastic bounds». Laboratoire PRiSM, Université de Versailles Saint Quentin.

[FOU 03b]

Jean Michel FOURNEAU, Mathieu LE COZ, Nihal PEKERGIN et Franck QUESSETTE, « An open tool to compute stochastic bounds on steady-state distributions and rewards». Laboratoire PRiSM, Université de Versailles Saint Quentin.

[MOR 03]

Patrice MOREAUX «Structuration des modèles et analyse de performances des systèmes à évènements discrets ». Mémoire présenté le 19 décembre 2003 à l’Université Paris Dauphine pour habilitation à diriger les recherches.

[PEK 99]

Nihal PEKERGIN, «Stochastic Performance Bounds by State Space Reduction».Performance Evaluation 36-37, p 1-17.

[YAZ 91]

Nihal YAZICI-PEKERGIN et Jean-Marc VINCENT, «Stochastic Bounds on Execution Times of Parallel Programs». IEEE transactions on software engineering, vol. 17, no. 10, October 1991.

BOUCHAMA Nadir et YAHIAOUI Saïd

24

RESYD 2004

© Nadir BOUCHAMA et Saïd YAHIAOUI Ecole Doctorale d’Informatique de Béjaia Réseaux et Systèmes Distribués RESYD Courriel : [email protected] [email protected] JUIN 2004