une démarche d’évaluation des performances et de la fiabilité

Formalismes de modélisation

Les systèmes que nous étudions sont des systèmes à évènements discrets, c’est-à-dire que l’état de ces systèmes est décrit par des variables d’états discrètes. L’évolution du système est représentée par des changements qui se déclenchent sous l’occurrence d’évènements. Par exemple, dans un réseau de communication, l’évolution du système peut-être décrite par le nombre de paquets en attente dans un routeur. Ainsi, les évènements tels que l’arrivée des paquets ou leur départ font augmenter ou diminuer la taille de la file d’attente par exemple. Ces systèmes à événements discrets sont présents dans des domaines assez variés tels que les systèmes informatiques, les systèmes de production ou encore les réseaux de communication.
Différents formalismes de modélisation sont utilisés afin de représenter ces systèmes. Cer-tains formalismes sont plus adaptés à une analyse qualitative, et d’autres à une analyse quantitative. Dans [1], l’analyse qualitative définit les propriétés structurelles et com-portementales du système, telles que la vivacité, les invariants du système ou la stabilité. Alors que l’analyse quantitative s’intéresse plus au calcul des mesures de performance. Les travaux qui sont présentés dans cette thèse ne traitent que de l’aspect quantitatif de l’analyse. Pour les aspects qualitatifs, nous laissons le soin au lecteur de se référer à la littérature correspondante [5–7].
L’un des formalismes de modélisation les plus répandus, dans le domaine de l’analyse des réseaux de communications, est le réseau de files d’attente pour modéliser l’attente sur des ressources partagées. Les réseaux de Pétri et les réseaux d’automates stochastiques sont également utilisés afin de modéliser la synchronisation des processus. Les chaînes de Markov représentent un formalisme de modélisation à un niveau plus bas, permettant d’utiliser des méthodes mathématiques efficaces d’analyse de performance.
Il existe sur le marché des outils logiciels permettant de générer automatiquement une chaîne de Markov à partir des formalismes de spécification de haut niveau tels que les réseaux de Pétri, les réseaux d’automates stochastiques ou les réseaux de files d’attente. Dans cette thèse, nous avons utilisé l’outil SHARPE 2 [8] développé en 96 par Sahner et Trivedi pour la génération et la résolution de chaînes de Markov et SimEvent 3 pour la simulation des systèmes à événements discrets dans un réseau de files d’attente. Dans la suite, nous présentons différents formalismes de modélisation.

Réseaux de Petri Stochastique

Dans leur version première, les réseaux de Petri (Petri Nets :PN) ont été développés dès les années 60 [9–11] pour la modélisation et l’analyse qualitative des systèmes complexes présentant des caractéristiques de concurrence et de synchronisation. Une première exten-sion temporelle a été introduite pour adapter les PN à l’analyse quantitative en ajoutant une temporisation sur les transitions [12, 13] ou alors sur les places [14]. Pour tenir compte des comportements probabilistes des systèmes et avoir une équivalence avec les chaînes de Markov, les PN stochastique (SPN) sont proposés dans [15–17] avec différentes séman-tiques pour gérer les événements en conflit. Enfin, parmi les extensions des PN, citons la généralisation des SPN (GSPN) qui considèrent à la fois des transitions avec des durées non-nulles, et d’autres avec des durées nulles [18, 19] (transitions immédiates).

Réseaux d’Automates Stochastiques

Le formalisme des réseaux d’automates stochastique (SAN) est introduit par Plateau [20, 21] pour une représentation à un haut niveau de spécification des chaînes de Markov de grandes tailles. Le système est décrit comme un ensemble de sous-systèmes, exploi-tant ainsi le fait que les composantes du système peuvent évoluer presque indépendam-ment rendant ainsi possible le parallélisme (quand les automates n’interagissent pas) et la synchronisation (quand ils interagissent). Chaque sous-système est représenté par un automate traditionnel auquel on rajoute des comportements stochastiques et des méca-nismes de synchronisation. Ainsi, l’intérêt des réseaux d’automates stochastiques est de pouvoir exprimer la matrice de transition de la chaîne de Markov sous un format de pro-duit tensoriel afin de calculer la distribution de probabilité transitoire et stationnaire. Les premières études ont porté sur le cas des modèles à temps continu [20–22]. Pour représen-ter les transitions d’un processus stochastique à échelle de temps discrète (distributions géométrique), la notion d’événements compatibles a été introduite pour identifier les évé-nements pouvant avoir lieu simultanément pendant une même unité de temps [23, 24]. Enfin, le formalisme SAN a été enrichi par l’ajout d’un niveau d’abstraction supplémen-taire sur l’espace d’états. Une agrégation, directement sur le modèle de haut niveau, est proposée sous certaines conditions. Ces SAN, avec réplications, sont basés sur le fait qu’un système présente souvent plusieurs entités identiques.

Réseaux de Files d’Attentes

Le formalisme file d’attente (Queueing Network : QN) est développé pour la modélisation des phénomènes de partage de ressources [19, 25–27]. Ce formalisme est essentiellement utilisé pour l’analyse quantitative des systèmes. Une file d’attente est un système dans lequel les clients arrivent, pour recevoir un service délivré par un ou plusieurs serveurs, puis quittent le système. Les clients, accèdent aux ressources de façon prioritaire ou non selon une discipline de service et peuvent même subir un temps d’attente (bufferisa-tion). L’intérêt des files d’attentes est que, dans le cas où les temps des inter-arrivées et les services sont exponentiels, ces systèmes peuvent-être décrits par des chaînes de Markov de type processus de naissance et de mort dont les distributions de probabilité ainsi que des indices de performances peuvent être calculés à partir de formules connues [1]. Ainsi, dans le domaine des télécommunications, la formule d’Erlang B permet de calculer la probabilité de rejet dans un central téléphonique, et l’Erlang C la probabilité d’attente. Dans le cas de lois d’inter-arrivées et de service plus généraux les chaînes de Markov peuvent être déduites, comme par exemple dans le cas de l’Erlang, mais avec des tailles plus importantes que dans le cas de lois exponentielles [1].
Un réseau de files d’attente est un ensemble de files d’attente interconnectées. Ils per-mettent de représenter par exemple un réseau de routeurs où les paquets sont routés selon une certaine probabilité. Le routage peut être dynamique (selon l’état des files), ou déterministe comme par exemple le routage cyclique. Il existe différents types de réseaux : ouverts ou fermés, mono ou multiclasses qui on été largement étudiés. Les réseaux de files d’attente ont été généralisés aux réseaux à clients positifs et négatifs appelés G-Networks (Generalized queueing network ou Gelenbe network) [28]. Les clients négatifs détruisent les clients positifs, ce qui permet de modéliser par exemple des départs synchronisés comme dans le cas de la primitive Join. Ils sont également utilisés dans le domaine des réseaux neuronaux.
Dans cette thèse, nous avons essentiellement travaillé sur le formalisme des réseaux de files d’attente et des chaînes de Markov. Nous nous sommes concentrés sur des méthodes ma-thématiques pour l’analyse quantitative de systèmes dans l’évaluation des performances. Dans la suite, nous présentons les principales méthodes d’analyse quantitative afin de mieux situer celles sur lesquelles nous avons travaillé.

Méthodes d’analyse quantitative

La mesure

La mesure est une méthode empirique de collecte de données issues d’un système en exé-cution. De ce point de vue, elle impose l’existence d’un système. C’est la façon la plus directe pour évaluer les performances d’un système puisque les mesures sont celles du système lui-même et non ceux d’un modèle.
La mesure peut être aussi employée pour valider les conclusions obtenues à partir d’un modèle d’évaluation de performance. Toutefois, elle n’est pas tout à fait simple à im-plémenter. En effet, il se pose le problème de la collecte et du stockage des volumes d’informations souvent importants ainsi que leurs interprétations. Mais aussi une instru-mentation lourde et des difficultés de positionner les sondes pour la capture des mesures de performances attendues.
Enfin, la mesure est limitée de façon intrinsèque par l’existence d’un système. Ceci réduit considérablement la classe des cas possibles pour son usage.

La simulation

La simulation à événements discrets consiste à reproduire l’évolution du système dans le temps en étudiant une réalisation particulière du modèle stochastique. L’avantage de la si-mulation est qu’elle permet d’analyser n’importe quel système ce qui est particulièrement intéressant pour des systèmes où l’on ne peut pas utiliser des méthodes mathématiques. Par contre, son inconvénient est qu’elle est très gourmande en temps de calculs. De plus, il ne s’agit pas d’une technique exacte et les résultats devront être accompagnés d’un intervalle de confiance pour estimer la précision des résultats. De ce point de vue, la si-mulation nécessite un temps de simulation relativement long. Par exemple, dans le cas des simulations de systèmes à évènements rares, il faut un nombre important de réalisations pour rencontrer au moins une fois ce type d’évènements. Et dans le cas particuliers de systèmes hautement critiques où la panne est un évènement rare, il arrive souvent que ce type d’évènements ne se produise pas sur un ensemble d’exécutions. Donc la simulation peut seulement confirmer l’existence d’un état critique mais ne peut jamais prouver son absence.

Analyse opérationnelle

L’analyse opérationnelle, voir les travaux de Denning et Buzen [29], consiste à dériver un ensemble de relations à partir d’observations faites sur le système sur une période de temps donnée. Elle permet d’avoir une première approche des mesures de performance d’un système vu comme une boite noire à partir des paramètres d’entrée et de sortie.
Dans le cas d’une file d’attente simple, l’analyse opérationnelle permet de définir des paramètres de performances en régime transitoire. Dans le cas d’un système stable, on s’intéressera aux valeurs de ces paramètres à l’infini. L’analyse opérationnelle permet d’introduire des critères de performances comme le nombre moyen de clients par unité de temps ou le temps moyen de réponse du système.
Dans le cas de réseaux de files d’attente, on pourra s’intéresser à des paramètres globaux du réseau, ou par station.

Méthodes analytiques

Les méthodes analytiques permettent une représentation formelle du système sous forme d’équations mathématiques. Il s’agit d’appliquer la théorie des files d’attente afin d’analy-ser les performances du système. Les mesures de performance peuvent être, dans certains cas, calculées simplement et de façon exacte comme des solutions à forme-produit. Mais le plus souvent, la classe de modèles admissibles aux solutions à forme-produit est très limitée. Dans ce cas, on a recourt à des méthodes de résolutions approximatives ou à des méthodes de bornes.
La section suivante détaille ces méthodes en particulier celles relatives aux encadrements par les techniques de bornes stochastiques qui font l’objet de cette thèse.