|
Cette représentation sous forme de produit tensoriel permet de représenter efficacement des systèmes de taille quasi illimitée. Mais les algorithmes d'atteignabilité, de calcul de probabilités stationnaires (échec sur un horizon infini) ou transitoires (sur un horizon fini), ou de vérification ne peuvent traiter des modèles de cette taille. Calculer une distribution, stationnaire ou transitoire, ou une partie de cette distribution suscite souvent une grande quantité de calculs numériques ou des difficultés analytiques. Dans ces conditions, borner la probabiblité que l'on cherche à calculer par une probabilité plus simple à obtenir numériquement ou analytiquement est une approche très intéressante. On voit cependant immédiatement que la borne calculée doit être compatible avec la récompense qui sera ensuite appliquée à la distribution bornante, et que de multiples notions de comparaison sont possibles. Une autre possiblité de ces méthodes est d'établir directement une comparaison entre les performances de deux mécanismes, sans pouvoir réellement les calculer. L'approche consiste alors à construire des modèles qui fournissent des bornes supérieures ou inférieures des distributions stationnaires ou transitoires ou des premiers moments de ces distributions. Un des aspects difficiles de ce type d'approche réside dans les nombreux ordres possibles sur les processus vectoriels et sur un un traitement algorithmique efficace des ces relations d'ordre. Clairement, à chaque caractérisation d'une distribution stationnaire ou transitoire on peut associer une ou des méthodes de bornes. Ainsi l'approche stationaire vue comme un problème d'algèbre linéaire conduit aux méthodes de Courtois et Semal récemment amélioré par Rubino et Maevas du projet ARMOR. Les systèmes dynamiques sur matrice positive mènent aux algorithmes d'encadrement actuellement développés à PRiSM. Enfin la charactérisation en tant que système dynamique probabiliste est associé aux ordres trajectoriels dont nous avons récemment obtenu une caractérisation algorithmique efficace. L'idée de base de la méthode est de comparer, au sens d'un ordre stochastique, la distribution stationnaire ou transitoire pour une chaîne de Markov modélisant un phénomène complexe à la distribution d'une chaîne plus simple ou plus régulière. Cette approche a déjà été utilisée avec succès, sur des distributions de chaînes de Markov et également sur des séquences de dates de franchissement pour des graphes de tâches et des réseaux de Petri afin d'obtenir des bornes sur les distributions de temps d'execution ou de temps de cycle. Dans le cas de la comparaison de distributions de chaînes de Markov, les méthodes sont sensiblement plus difficiles puisqu'à l'inverse des dates, les états des chaînes ne sont pas toujours croissants. Il existe cependant certains résultats théoriques pour des ordres forts (ex : ordre "strong" de Stoyan signifiant qu'une des fonctions de répartition est toujours supérieure à l'autre) pour des processus de Markov (c'est à dire à espace d'états continu). Dans le cas d'espaces dénombrables ou finis, nous avons déjà donné une caractérisation algorithmique très simple de l'ordre "strong". Il est à noter que ces méthodes permettent de borner aussi bien les distributions stationnaires que les distributions transitoires. Elles sont assocíees aux mesures de fiabilité asymptotique et aussi aux mesures transitoires. Les travaux précurseurs de Barlow et Prochan montraient déjà le lien entre l'étude de la fiabilité et les ordres sur les variables aléatoires. Nous avons donc proposé des méthodees de comparaison de trajectoires permettant de calculer beaucoup plus facilement un point plus grand ou plus petit en tout point de l'évolution d'un système, grâce à des concepts de monotonie. On garantie ainsi une borne supérieure ou inférieure de la fiabilité à horizon finie ou infinie. Nous avons déjà employés ces méthodes en évaluation de performances (souvent pour les états stationnaire (horizon infini)) pour évaluer des délais de discipline Fair Queueing ou des taux de pertes dans des tampons. Nous avons également développé des algorithmes associés à cette problématique du stationnaire. Ces algorithmes calculent une matrice réduite dont la solution plus simple fournit une borne supérieure ou inférieure de la vraie solution qui reste incalculable. Typiquement les algorithmes procèdent par colonne et seuls quelques vecteurs de l'espace des états (2 ou 3 selon les algorithmes) sont stockés en mémoire. La matrice décrivant le système reste sur disque (dans le cas d'un stockage creux) ou en format tensoriel. |
