Réseaux d’Automates Stochastiques (RAS)

Réseaux d’automates stochastiques

Les réseaux d’automates stochastiques (RAS) sont basés sur l’idée que le système modélisé peut se décomposer sous la forme de plusieurs sous-systèmes. Chacun de ces sous-systèmes peut évoluer indépendamment et peut interagir avec les autres en se synchronisant ou en faisant varier la valeur de ses transitions en fonction des états des autres sous-systèmes, ce comportement étant typiquement celui des services Web composites. C’est du fait que les Web services fonctionnent de manière modulaire et non pas intégrée (c.-à-d. qu’au lieu d’intégrer dans une seule application globale toutes les fonctionnalités, on c rée (ou on récupère) plusieurs applications spécifiques qu’on fait inter-coopérer entre elles sous forme d’un processus métier.

Terminologie

Les RAS font partie des systèmes de transitions étiquetées (Labeled Transition System – LTS) qui sont des modèles permettant de représenter l’évolution d’un système par un graphe incluant des états reliés par des transitions étiquetées par des actions. Les LTS sont basés sur les notions suivantes :
 Les états : Un état représente un état du système prenant en compte les évènements de ce système que l’on souhaite modéliser, c’est-à-dire une étape (visible ou non) à instant donné du système réel.
 Les transitions : Les transitions relient deux états et indiquent les actions qui provoquent les changements d’états du LTS (et donc, par extension, du système).
Ainsi, à un instant donné, l’évolution du système se traduit par le passage d’un état à un autre en franchissant une des transitions reliant ces deux états.
Avant de donner la liste des concepts utilisés dans les réseaux d’automates stochastiques nous commencerons par un petit rappel qui donne que lques définitions d’algèbre tensorielle, employées pour exprimer le générateur de la chaîne de Markov associée à ce formalisme. Et en particulier les trois propriétés suivantes :

Automates, Événement Synchronisant et Transition Fonctionnelle

Les RAS sont un formalisme pour la définition et la solution des systèmes complexes à grandespace d’états. Il est constitué d’un ensemble d’automates, Chaque automate est constitué d’un ensemble d’états, chaque état a un ensemble d’arcs sortant (transitions) et chaque arc est étiqueté par un ensemble d’événements. Les états internes, ou états locaux d’une automate correspondent aux différents états possibles du sous-système modélisé par cet automate. L’état global est défini comme la combinaison de tous les états internes de chaque automate.
L’occurrence d’un événement peut modifier l’état interne d’une ou de plusieurs automates.
Lorsqu’un seul automate est impliqué, l’événement est dit local. Sinon, nous parlons d’événement synchronisant. Dans tous les cas, nous avons un c hangement de l’état global d’un RAS.
Pour représenter graphiquement un R AS, nous pouvons ainsi associer un gr aphe à chaque automate. Les nœuds du graphe correspondent aux états locaux de l’automate, et les arcs sont étiquetés par une liste d’événements. Il se p eut en effet que plusieurs événements distincts produisent le même changement d’état local dans une automate. Dans ce cas, nous avons formellement une transition par événement, et l’arc du graphe représente toutes ces transitions en même temps.

D.PEPS

PEPS (Performance Evaluation of Parallel Systems) est un outil informatique qui permet à la fois la définition et la solution de modèles utilisant le formalisme des réseaux d’automates stochastiques et algèbre tensorielle. Sa première version fût proposée par Plateau, Fourneau et Lee. Actuellement il est dans sa version PEPS 2007. PEPS reçoit la description d’un modèle RAS et calcule le vecteur de probabilité associé à la chaine de Markov correspondant au modèle RAS décrit. Pour cela il utilise un formalisme textuel pour décrire les modèles, qui conserve l’élément cléf du formalisme RAS, à savoir sa spécification modulaire [16]. Cette description textuelle est simple, extensible et flexible :
 simple parce qu’il y a peu de mots réservés, juste assez pour délimiter les différents niveaux de modularité ;
 extensible car la définition des modèles SAN est faite de façon hiérarchique ;
 flexible grâce à l’inclusion de structures de réplication, qui permettent d’une part la réutilisation d’automates identiques, et d’autre part la construction d’automates ayant des blocs d’états de comportement identique répétés, comme on le trouve souvent dans les modèles de réseaux de file d’attente.
Entre le format d’entrée du modèle RAS et la génération du vecteurs de la pr obabilité un certains nombre des structures de données intermédiaires peut être généré. Par la suite on va décrire le format d’entrée et l’ensemble des étapes nécessaires pour la résolution du modèle.

Format textuel

Le premier bloc identifiers contient les déclarations de tous les paramètres : valeurs numériques, fonctions, ou ensemble d’indices (domaines) qui seront utilisés pour les répliquas dans la définition du modèle.
Le mot-clé annonce la définition d’un état. est le nom de l’état, et nous pouvons utiliser , pour répliquer l’état. Le mot clé représente la possibilité d’utiliser les récompenses. Une description de chaque arc sortant de cet état est donnée par la définition d’une section . L’identifiant dans la parenthèse indique l’état d’arrivée de l’arc.
Dans un groupe d’états répliqués, l’expression d’autres états du groupe peut être faite par des références aux positions : l’état courant (==), précédent (– –) ou suivant (++). permet de définir une condition sur la transition. Cette condition est une fonction qui est généralement définie dans le bloc identifiers. Normalement, les valeurs retournées sont en fonction de l’automate actuelle et / ou de l’état courant/cibles.
Finalement, chaque arc est associé à u n ensemble d’événements qui peuvent déclencher la transition. Ils sont exprimés par leur nom , et éventuellement (si différente de 1) par la probabilité de routage associée à cette transition .Les différents événements sont séparés par des espaces ou des sauts de ligne. La section est relativement semblable à la section , sauf qu’elle ne définit pas d’état local. Elle sert à rajouter des arcs qui ne peuvent pas être définis dans une section . Typiquement, nous nous en servons pour définir un a rc sortant d’un état particulier d’un groupe d’états répliqués pour aller dans un état en dehors du groupe. Une file d’attente ayant des états initiaux ou finaux particuliers peut utiliser ce type de définition d’arcs.
Enfin, les fonctions utilisées pour calculer des indices de performances sur le SAN sont définies dans le bloc results.

Structure de données

L’un des avantages apportés par le formalisme des réseaux d’automates stochastiques est la facilité de décrire le générateur de la chaîne de Markov associée au modèle complet de façon compacte, grâce à une formule mathématique appelée descripteur, et bien sur la possibilité de calculer le produit vecteur-descripteur sans jamais exprimer la matrice de façon explicite (approche Kronecker). Cette approche fait partie d’un ensemble des techniques et algorithmes qui portent sur la manière dont les données sont stockées, (la représentation du générateur et les vecteurs de probabilité), ce qui influe largement sur le calcule du vecteur des probabilités stationnaires. Les deux méthodes implémentées dans PEPS 2007 sont les suivantes [16] :
 Stockage explicite, matrice en format creux : consiste à stocker le descripteur de façon explicite en ne gardant que les éléments non nuls et leur position dans la matrice (ceux-ci est le format Harwell-Boeing). Les vecteurs de probabilité sont alors de la taille de l’espace d’états accessibles.
 Approche de Kronecker : consiste à u tiliser un ensemble de petites matrices de dimension pour stocker un grand modèle. est le nombre d’états locaux de l’automate . Cette approche sera décrite ultérieurement.

L’agrégation

L’utilisation de deux techniques précédemment définies n’est pas toujours suffisante pour pallier au problème de l’explosion du nombre d’états. Pour surmonter ce problème, on peut jouer sur le fait que de nombreux systèmes contiennent un grand nombre de composants identiques. Donc, on pe ut alors exploiter ces réplications de composants pour générer une chaîne de Markov réduite, en effectuant une agrégation. L’agrégation est basée sur le fait que, grâce aux répliquas, certains états globaux du SAN ont la même probabilité stationnaire. Pour cela, tous les états du SAN initial équivalents par une permutation de P sont groupés en un unique état de la chaîne de Markov agrégée. Chaque état particulier représente une classe d’équivalence. Pour finir, l’agrégation peut être utilisée avec les deux techniques citées précédemment. Avec la technique de stockage explicite, en stockant la matrice en format creux agrégé. Pour ladeuxième approche, il existe une expression tensorielle de la matrice de la chaîne de Markov agrégée.