IBTS-77-RP-1000
Vers une démarche d’évaluation des performances et de la fiabilité
L’évaluation de performance et de la fiabilité désigne un ensemble d’étapes partant d’un système et aboutissant au calcul des mesures de performances et de fiabilité.
Comme exemple de mesures de performances, citons le délai de bout en bout dans un réseau ou la probabilité de rejet des appels dans un central téléphonique. En termes de fiabilité, des mesures telles que le taux de pannes d’un routeur sont des paramètres dont les valeurs sont cruciales pour garantir le bon fonctionnement d’un réseau. L’évaluation des performances intervient à deux niveaux dans le cycle de vie d’un système : à sa conception et durant son exploitation.
En conception : Le système n’existe pas, il s’agit donc de le créer en respectant un cahier des charges. Il est indispensable, vu la complexité des systèmes actuels et de l’exigence des utilisateurs, de mettre en place une démarche claire d’évaluation des performances des systèmes. Ainsi, construire un système sans mener au préalable des études de performance et de fiabilité peut conduire aux problèmes suivants :
Un sous-dimensionnement et donc des performances insuffisantes qui provoquent une dégradation de la qualité de service (QoS). Mais aussi un déficit de fiabilité pouvant engendrer des catastrophes. Nous avons vu l’exemple de l’opérateur Orange mais nous pouvons citer aussi l’explosion de la fusée Ariane V en 96. Ces incidents génèrent une forte dégradation de l’image de la société et des pertes financières importantes.
Un surdimensionnement entrainant, là aussi, des coûts d’exploitation inutilement élevés et dans certains cas des difficultés de réaliser le système.
En exploitation : Lorsque, sur un système existant, on souhaite réaliser :
Une optimisation : Il s’agit alors d’améliorer les performances du système en évaluant l’impact de tel ou tel changement. Par exemple, un nouveau plan de routage ou une discipline de priorité.
Des tests pour évaluer les points de ruptures (cas pire) ou la survivabilité du système. Par exemple, un système avionique se doit de résister à une défaillance d’un ou plusieurs éléments du système et continuer à fonctionner même dans des états dégradés. Dans un réseau, on peut s’intéresser à des cas de surcharge du trafic.
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 . 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 (bufferisation). 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 . 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 .
Un réseau de files d’attente est un ensemble de files d’attente interconnectées. Ils permettent 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). 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.
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 à implé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 instrumentation 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 simulation 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 simulation 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.
Etude d’un réseau G-Networks avec catastrophes
Depuis la série inaugurale de Gelenbe dans le début des années 90, les réseaux généralisés de files d’attente ont reçu une attention considérable. Actuellement, il y a plusieurs centaines de références consacrées à ce sujet et un livre donne un aperçu de quelques-unes des orientations de la recherche, du développement et des applications dans le domaine des réseaux de files d’attente avec des clients positifs et négatifs. Les clients positifs sont les clients en attente dans le réseau et les clients négatifs sont souvent appelés « Signaux », et leur rôle est de détruire les clients positifs. Dans les modèles des réseaux de files d’attente (tels que Jackson ou BCMP), il n’existe pas de mécanismes pour que certains clients éliminent d’autres clients, ou les réorientent parmi les files d’attente. En d’autres termes, les clients de réseaux de files d’attente traditionnelles ne peuvent pas exercer un contrôle direct sur les autres clients. Les modèles des réseaux généralisés (G-Networks ou G-Net) permettent de surmonter certaines des limites des modèles classiques de réseaux de files d’attente tout en conservant la propriété de forme produit pour la distribution de probabilité stationnaire. Ils contiennent des clients inhabituels pouvant avoir les comportements suivants : les clients négatifs qui éliminent les clients normaux, les catastrophes qui vident tous les clients dans une file d’attente , ou les déclencheurs qui déplacent les clients d’une file d’attente vers une autre . Les réseaux G-Networks ont été introduits pour modéliser les réseaux de neurones dans les échanges des signaux inhibiteurs et excitateurs . Ils sont également utilisés pour modéliser des opérations complexes telles que la suppression des travaux ou des infections virales des logiciels . Comme vu au début de ce chapitre, l’analyse transitoire de ces réseaux de files d’attente est très difficile et la comparaison stochastique offre des solutions intéressantes pour résoudre ce problème en permettant la construction de bornes stationnaires et transitoires des distributions des probabilités. Dans , les études de Massey ont été reprises, et donc le formalisme des ensembles croissants est développé en fonction des événements pour définir l’ordre « weak » dans le cas des G-Networks et des G-Networks avec catastrophes.
|
Table des matières
Introduction générale
1 Vers une démarche d’évaluation des performances et de la fiabilité
2 Formalismes de modélisation
2.1 Réseaux de Petri Stochastique
2.2 Réseaux d’Automates Stochastiques
2.3 Réseaux de Files d’Attentes
3 Méthodes d’analyse quantitative
3.1 La mesure
3.2 La simulation
3.3 Analyse opérationnelle
3.4 Méthodes analytiques
4 Solutions à forme produit
5 Méthodes numériques
6 Méthodes d’approximation
7 Méthodes des bornes stochastiques
8 Apport et organisation de la thèse
8.1 Apport de la thèse
8.2 Organisation de la thèse
I La comparaison stochastique sur des espaces multidimensionnels
1 Introduction
2 Les ordres sur des espaces multidimensionnels
3 La comparaison stochastique
3.1 Comparaisons stochastiques de variables aléatoires
3.2 Comparaisons stochastiques de chaînes de Markov
4 Le couplage
4.1 Exemple
5 Méthode des ensembles croissants
II Définition de sous-réseaux bornants dans les réseaux de files d’attente
1 Etude d’un réseau de files d’attente M/M/ci/ki
1.1 Description du système
1.2 Définition de la projection du processus X(t)
1.2.1 Projection du processus X(t)
1.2.2 Définition des taux de transitions de g(X(t))
1.3 Le couplage pour la construction de la borne supérieure
1.4 Calculs des taux de transition des systèmes bornants
1.4.1 Borne supérieure
1.4.2 Borne inférieure
1.5 Analyse numérique des bornes
2 Etude d’un réseau G-Networks avec catastrophes
2.1 Description du G-Networks avec catastrophes
2.2 Définition des bornes du G-Networks avec catastrophes
2.2.1 Projection du processus X(t)
2.2.2 Définition des taux de transition
2.3 Construction de la borne supérieure
2.4 Construction de la borne inférieure
2.5 Comparaison des mesures transitoires
2.6 Analyse numérique des indices de performances transitoires
3 Conclusion
III Evaluation de la performabiblité d’un système de télécommunication
1 Modèle composite d’Erlang avec perte
1.1 Description du modèle
1.2 Résolution approximative par approche MRM
2 Système bornant à forme produit
2.1 Définition d’un système bornant à forme produit
2.2 Comparaison stochastique des processus X(t) et XS1(t)
3 Systèmes bornants agrégés
3.1 Construction des modèles agrégés
3.2 Monotonicité du processus bornant agrégé
3.3 Calculs des taux des systèmes bornants agrégés
3.3.1 Définition des taux de la borne supérieure
3.3.2 Définition des taux de la borne inférieure
4 Résultats
5 Conclusion
IV Contrôle d’admission et handover forcé dans les réseaux mobiles
1 Approche combinée de contrôle d’admission et de handovers forcés dans un réseau monocellulaire
1.1 Description du mécanisme proposé
1.2 Description de la cellule étudiée
1.3 Définitions des transitions des différents mécanismes
1.3.1 Les transitions du système MAHO
1.3.2 Les transitions du système MG
1.3.3 Les transitions du système LMG
1.4 Comparaison stochastique des systèmes MG1 et LMG1
1.5 Résultats numériques des mécanismes étudiés
2 Approche combinée de contrôle d’admission et de handovers forcés dans un réseau
multicellulaire
2.1 Description du système multicellulaire
2.2 Définition des sous-réseaux bornants
2.2.1 Projection du processus XLMG2 (t)
2.2.2 Définition des taux de transition .
2.3 Construction de la borne supérieure
2.4 Construction de la borne inférieure
3 Résultats numériques sur un réseau multicellulaire
3.1 LMG2 vs MG2 : l’influence de la charge
3.2 LMG2 et MG2 : l’influence du seuil s
3.3 Agrégation bornante : l’impact de la taille des sous-systèmes bornants sur la qualité
V Conclusions générales et perspectives
1 Conclusions
1.1 Méthode de couplage appliquée à des réseaux de files d’attente
1.2 Application de la comparaison stochastique sur des réseaux de communications
2 Perspectives
2.1 Couplage par fonction de projection : application à des formalismes de haut niveau
2.2 Vers un algorithme de couplage de processus
2.3 Estimation de l’erreur entre les bornes
2.4 Choix de l’ordre sur l’espace d’états
2.5 Comparaison de systèmes non-markoviens et semi-markoviens
2.6 Ordres stochastiques faibles
2.7 Applications futures
Télécharger le rapport complet
