Notions de base sur les files d’attente

Les télécommunications sont définies comme la transmission à distance d’informations avec des moyens à base d’électronique et d’informatique. Actuellement, les télécommunications utilisent des équipements électroniques associés à des réseaux analogiques ou numériques. Un réseau est le résultat de l’interconnexion de plusieurs matériels reliés entre eux, dans le but de traiter et de transférer des données sur une distance étendue de quelques mètres vers des milliers de kilomètres. Ces matériels sont appelés nœuds. [1] Pour que chaque paramètre d’un nœud du réseau puisse fonctionner, il est nécessaire de modéliser chaque nœud du réseau en file d’attente, formant ainsi un réseau de files d’attente. Les files d’attente, eux, se caractérisent par l’arrivée de «clients » dans des «stations » afin de recevoir des « services » dont la durée est généralement aléatoire. Il existe plusieurs possibilités de modélisation de réseau comme les Réseaux de Pétri, ou encore les réseaux de Neurones Artificiels mais dans ce travail, seuls les réseaux de files d’attente sont considérés. [2] [3] Cependant, la modélisation d’un réseau de files d’attente risque de durer plusieurs heures, voire plusieurs jours, dépendant du nombre de nœuds dans le réseau. Pour en donner un aperçu, notre travail s’intitule «ETUDE D’UN RESEAU DE TROIS FILES D’ATTENTE ».

NOTIONS DE BASE SUR LES FILES D’ATTENTE 

Un réseau de files d’attente est composé de plusieurs files d’attente élémentaire, modélisées au préalable pour avoir un fonctionnement optimal. Il est donc nécessaire de voir de plus près ce qu’est d’abord «Les files d’attente». Ce chapitre sera consacré aux notations sur les files d’attente, les files d’attente les plus répandues, et ainsi soutirer quelques modèles qui nous seront utiles pendant la modélisation d’un réseau de files d’attente. Les données analytiques issues de ce chapitre donneront les algorithmes à utiliser pour la suite et l’étude d’un cas particulier de réseau de files d’attente.

RAPPELS

a) VARIABLE ALEATOIRE
Les variables aléatoires sont les variables mesurées dans les expériences aléatoires. Une variable aléatoire est définie par une éventualité w. Donc, une variable aléatoire Esur un espace probabilisé (Ω,N,P) décrivant une expérience aléatoire, est une fonction d’évènement élémentaire E(w). Si cette variable est mesurable, il est possible d’observer l’événement suivant : la valeur de E appartenant à un intervalle donné ∆ quel que soit ∆ .

b) LOI DE PROBABILITE
La loi de probabilité d’une variable aléatoire ou répartition d’une variable aléatoire E est donnée par l’équation (1.1). Pour définir la loi de la variable E, il suffit de donner la fonction .

PE(∆)=P{w : E(w)Є∆} (1.1)

qui est appelée fonction de répartition de la variable E.

c) PROCESSUS ALEATOIRE
Un processus aléatoire sur un espace probabilisé (Ω,N,P) est une famille de variables aléatoires E(t,w)dépendant d’un paramètre réel t appartenant à un ensemble T. Cet ensemble est dit ensemble de définition du processus. Les variables aléatoires E(t,w) peuvent être réelles, complexes ou vectorielles .

d) STATIONNARITE
Les processus stationnaires dont tels ou tels caractéristiques sont invariants par une translation du temps ou du paramètre spatial, ou, d’une façon générale, les processus dont certaines caractéristiques sont invariantes par un groupe ou un semi-groupe de transformations, occupent une place importante en théorie des processus aléatoires. De tels processus possèdent certaines propriétés d’invariance, de stationnarité. Une distribution stationnaire est une distribution de probabilité. Et une distribution de probabilité régie par une loi de probabilité décrit de manière théorique le caractère aléatoire d’une expérience qui est considérée comme aléatoire. Ce concept se formalise mathématiquement à l’aide de la théorie de la mesure : une loi de probabilité est une mesure, souvent vue comme la loi décrivant le comportement d’une variable aléatoire, discrète ou continue.

e) PROCESSUS ALEATOIRE STATIONNAIRE
Soit (Ω,N,P) un espace probabilisé donné sur lequel on considère des processus aléatoires {E(t),tЄT}, où T est un ensemble de la forme ]-∞,∞[, [0,∞[ (t continu) ou {0,±1,2,..},{0,1,2…} (t discret). Un processus aléatoire est dit stationnaire au sens large si son espérance mathématique ne dépend pas de t et sa fonction de corrélation B(t,s) ne dépend que de la différence (t-s), c’est-à-dire si ;

B(t,s)=B(t-s)

La loi exponentielle est la loi de probabilité mise en évidence dans ce chapitre. Mais la loi exponentielle peut se diviser en deux parties suivant les types de routage des serveurs. Si les serveurs sont en série, la loi de service est dite hypo-exponentielle, si les serveurs sont en parallèle, la loi est dite hyper-exponentielle.

f) LOI EXPONENTIELLE
La loi exponentielle est utilisée dans la plupart des cas avec une file d’attente à un seul serveur. Ce travail s’est basé sur ce concept en considérant le système comme une file d’attente à un seul serveur.

RESEAU DE FILES D’ATTENTE 

PRESENTATION GENERALE 

Un système qui comporte plus d’une file d’attente est dit un réseau de files d’attente. C’est le cas d’Internet qui est le plus grand réseau informatique de nos jours.

Ceci n’est qu’un exemple mais le type de routage peut varier selon le réseau. En effet, les deux types de routage les plus connus sont : le routage en anneau et le routage en étoile. Mais comme pour Internet, ces deux types de routage peuvent coexister.

Le routage en anneau peut se résumer comme un routage où les clients qui quittent une file d’attente n’y reviennent pas sauf s’ils ont été servis par tous les autres serveurs de chaque file constituant le réseau, c’est-à-dire que le service ne va que dans un sens .

Le routage en étoile est plus complexe que le précédent, mais c’est le cas le plus général et le plus répandu. En effet, dans cette configuration, il existe toujours une probabilité pour qu’un client déjà traité dans une file i retourne vers la file i-1. Le routage se fait dans les deux sens .

PRINCIPAUX TYPES 

Il existe plusieurs types de réseaux de files d’attente, suivant la structure et le fonctionnement ainsi que les besoins du système en question. Il peut arriver que ces différents types soient mélangés pour former encore d’autres types de réseau.

i. Réseau ouvert
Un réseau ouvert est un réseau où les clients proviennent de l’extérieur, progressent dans le système pour être traités par les nœuds, puis le quittent .

C’est le cas le plus courant puisque l’entrée peut être considérée comme un arrivé et la sortie comme un départ. En résumé, un réseau où tout client présent ou entrant dans le système, pouvant quitter le système est un réseau ouvert.

ii. Réseau fermé
Le réseau fermé est un réseau où le nombre de clients est fixe à tout instant. Ceci veut dire que les clients sont pris dans une, voire des boucles, et n’en sortent jamais. La sortie devient l’entrée et l’entrée devient la sortie. Ce type de réseau de files d’attente est utilisé en dépannage de réseau, en ne laissant sortir aucun paquet ou message pour voir ou estimer les éventuelles problèmes matériels ou logiciels .

iii. Réseau à classe
Le réseau à classe est un réseau où les priorités de traitement des messages ou paquets dans le système ont les mêmes priorités de traitement (mono-classe) ou sont de priorités différentes (multi-classe). Les classes définissent l’ordre de priorité pour le traitement des clients. La classe la plus élevée est traitée en premier lieu, c’est ensuite que les autres classes de clients seront traitées. Ce type de classe peut exister dans les réseaux ouverts ou les réseaux fermés. Un réseau est dit mixte s’il est ouvert pour certaines classes de clients et fermé pour d’autres.

Table des matières

INTRODUCTION
Chapitre 1 : NOTIONS DE BASE SUR LES FILES D’ATTENTE
1.1 RAPPELS
a) Variable aléatoire
b) Loi de probabilité
c) Processus aléatoire
d) Stationnarité
e) Processus aléatoire stationnaire
f) Loi exponentielle
g) Loi hypo-exponentielle
h) Loi hyper-exponentielle
1.2 THEORIE DES FILES D’ATTENTE
a) Présentation
b) Caractéristiques d’une file d’attente
c) Notation de Kendhall
1.3 PRINCIPALES FILES D’ATTTENTE
a) File M/M/1
b) File M/M/K
c) File G/G/1
d) Formule de Little
e) Limite d’une file d’attente
Chapitre 2 : RESEAU DE FILES D’ATTENTE
2.1 PRESENTATION GENERALE
2.2 PRINCIPAUX TYPES
a) Réseau ouvert
b) Réseau fermé
c) Réseau à classe
2.3 PARAMETRES PERTINENTS DU RESEAU
2.4 DIFFERENTES CATEGORIES
a) Réseau de files d’attente à forme produit
b) Réseau de files d’attente à forme non produit
2.5 CONDITION DE STABILITE
2.6 RESEAU DE JACKSON
Chapitre 3 : ETUDE DE RESEAU DE TROIS FILES D’ATTENTE
3.1ARCHITECTURE CONSIDEREE
3.2 HYPOTHESE SIMPLIFICATRICE
a) Architecture
b) Forme du réseau
c) Stabilité
d) Type de réseau
3.3 ETAPE DE MODELISATION
3.4 INTERFACE GRAPHIQUE
a) Description des zones
b) Entrée
i) Entrée par saisie
ii) Entrée par fichier
c) Sortie
d) Réseau équivalent
3.5 RESULTATS
a) Stabilité du système
i) Système instable
ii) Système stable
b) Temps de traversée
3.6 REDIMENSIONNEMENT
CONCLUSION
ANNEXES

Lire le rapport complet