Définition de sous-réseaux bornants dans les réseaux de files d’attente

Définition de sous-réseaux bornants dans les réseaux de files d’attente

Dans l’évaluation des performances des réseaux de communication, on s’intéresse souvent qu’à une partie du réseau : délai de bout en bout d’un chemin, probabilité de blocage ou de panne d’un nœud. Lorsque le réseau est de grande taille, l’analyse exacte est très difficile si la distribution de probabilité du système n’a pas de solution évidente (une forme produit par exemple). De plus, la résolution du système par des méthodes numériques ou sa simulation est quasi impossible à cause de l’explosion de l’espace d’états. Nous nous intéressons également au calcul de la distribution de probabilité transitoire qui est très complexe pour des CMTC multidimensionnelles. A partir de cette constatation, nous allons définir des sous-systèmes bornants plus simples à étudier que le système d’origine, et qui nous permettent d’encadrer les mesures de performance stationnaires et transitoires en utilisant la comparaison stochastique.Avec cette approche, nous proposons un compromis entre la taille de l’espace d’états et la qualité des bornes obtenues. En ce sens, elle est une solution intéressante pour l’évaluation des systèmes complexes. Nous verrons également, comment la qualité des bornes est influencée par les paramètres des systèmes étudiés.

Nous appliquons l’approche en étudiant deux types de réseaux :– Un réseau de files d’attente multi-serveurs pour calculer des bornes sur des probabilités – Un réseau G-Network avec catastrophe qui modélise par exemple un réseau de com- munication infecté de virus. On cherchera à calculer des bornes sur les temps avant l’arrivée dans une station d’un premier virus ou le nombre de fois qu’une station a été infectée. Ce travail a été publié dans la conférence ValueTools en mai 2011.Ce chapitre comporte deux grandes sections, une pour chacun des deux réseaux ci-dessus. Dans chacune d’elles, les systèmes sont décrits et la construction des systèmes bornants est détaillée en utilisant la comparaison stochastique basée sur le couplage par fonction de projection dans un espace d’état plus petit. Nous donnons, en fin de chacune des sections, des résultats numériques avant de conclure par une discussion autour des paramètres qui peuvent influer sur les systèmes bornants.Comme nous l’avons dit, nous utilisons la méthode du couplage par fonction de projection. L’intérêt de cette méthode est qu’elle est assez générale car elle ne suppose pas que l’un des processus soit monotone. Ainsi, les réseaux multi-serveur sont monotones (voir [56]) mais les G-Networks ne le sont pas à cause du départ synchronisé de clients . Nous proposons d’utiliser cette méthode qui est intuitive car elle est basée sur les équations d’évolution des systèmes et la comparaison des états du système après le déclenchement des événements.

Etude d’un réseau de files d’attente M/M/c

Nous considérons un système représenté par un réseau de files d’attente M/M/ci/ki. Avec des hypothèses markoviennes, les modèles de bas niveau sous-jacents sont des CMTC multidimensionnelles. Pour certains réseaux, avec certaines conditions [1, 35], les solutions à forme produit sont connues à l’état d’équilibre. Par contre, s’il n’y a pas de solution à forme produit, le calcul de la distribution de probabilité stationnaire s’avère très dur voire insoluble en raison de l’explosion de l’espace d’états. L’analyse transitoire de ces systèmes étant, bien évidemment, encore plus difficile [57] car il est impossible de dériver une expression analytique de la distribution transitoire pour le système que nous étudions. De plus, l’utilisation de méthodes numériques pour calculer les distributions stationnaire et transitoire, est difficile à cause de l’explosion combinatoire de l’espace d’états. Dans ce cas, la comparaison stochastique permet d’apporter des solutions intéressantes. Massey, [53], a utilisé la comparaison par les ensembles croissants afin de définir l’ordre faible « weak » entre un réseau de files d’attente du type Jackson et un réseau de files indépendantes M/M/1. Il a ainsi pu borner la queue de la distribution transitoire d’un réseau de Jackson par le produit des queues de distributions transitoires des files M/M/1.

L’intérêt est que les distributions de probabilités transitoires d’une M/M/1 sont calculables.L’approche de Massey consiste à construire un système bornant en coupant les liens entre toutes les files, pour se ramener à un système dont la distribution de probabilité transitoire est calculable. L’approche que nous proposons est différente car nous coupons les liensentre un sous-réseau et le reste du réseau de façon à définir des sous-réseaux bornants. Ainsi l’analyse transitoire par des méthodes numériques ou la simulation de réseaux de taille plus petite est plus facile. De plus on garde la dynamique du sous-réseau et donc nos bornes sont plus proches du système exact.Un autre avantage de notre approche est donc, de proposer une famille de systèmes bornants obtenus par découpage, plus ou moins important, des liens entre les files d’attente afin de proposer un compromis entre la précision des bornes et la complexité des calculs. Le point intéressant de ces sous-systèmes bornants est la capacité de maintenir inchangée la dynamique interne puisque nous conservons le transit entre les files d’attente du sous- réseau.