Theorie de la file d’attente

De nos jours, la télécommunication a beaucoup évoluée : elle est devenue un domaine fondamental que l’être humain ne peut plus s’en passer. Elle, comme son nom l’indique, réalise la communication dans le monde : d’où la naissance de l’Internet. L’étude de la dynamique de l’Internet est un sujet de recherche actif depuis 1988, en termes de croissance et des flux qui le composent. Sa composante de trafic principale, les flux TCP (Transmission Control Protocol), a été dotée de différents mécanismes améliorant les performances en cas de congestion. Bien que nécessaires et performants, ces mécanismes sont insuffisants pour fournir un bon service en toutes circonstances, surtout lorsqu’il s’agit d’applications sensibles aux délais, tel que les flux temps réel. En effet, les flux temps réel sont caractérisés par des contraintes strictes en termes de délais, de gigues, de pertes, d’utilisation de la bande passante … etc.

Il existe, dans la littérature, trois approches majeures permettant d’assurer une certaine Qualité de Service ou QoS (Quality of Service) dans les réseaux, à savoir : IntServ (Integrated Service) basée sur la réservation statique de ressources (flux par flux), DiffServ (Differenciated Service) permettant de fournir des garanties par classe et AQM (Active Queuing Management) conçu pour la gestion des files d’attente au niveau des routeurs.

THEORIE DE LA FILE D’ATTENTE 

Généralités

La théorie des files d’attente s’attache à modéliser et à analyser de nombreuses situations en apparence très diverses, mais qui relèvent néanmoins toutes du schéma descriptif général suivant. Des clients arrivent à intervalles aléatoires dans un système comportant plusieurs serveurs auxquels ils vont adresser une requête. La durée du service auprès de chaque serveur est elle-même aléatoire. Après avoir été servis (ce qui suppose un arrêt chez un ou plusieurs serveurs selon le cas), les clients quittent le système.

Le but de l’analyse est de caractériser le degré de performance du système en répondant à des questions du type suivant:
• en moyenne, combien de temps attend un client avant d’être servi?
• quel est le nombre moyen de clients dans le système?
• quel est le taux d’utilisation moyen des serveurs?
• ….

Pour mettre un peu d’ordre au milieu du chaos, les théoriciens ont été amenés à classifier les systèmes rencontrés en précisant certaines de leurs caractéristiques. En particulier, on distingue ainsi :

• Les systèmes à serveurs parallèles, où chaque client ne requiert le service que d’un seul serveur et tous les serveurs sont capables de fournir ce service
• Les systèmes à serveurs en série, où chaque client doit visiter plusieurs serveurs successifs dans un ordre fixe pour recevoir satisfaction.

Les arrivées de clients peuvent être groupées ou individuelles; de même pour le service par chaque serveur. Les clients forment une ou plusieurs files d’attente, éventuellement caractérisées par des priorités différentes (par exemple, dans un atelier, commandes urgentes ou non). Au sein de chaque file, le prochain client à servir est sélectionné sur base d’une règle prédéterminée, appelée discipline de service. Les disciplines de service les plus courantes sont: premier arrivé premier servi (First In First Out, First Come First Served) (surtout utilisée dans les services, par souci d’équité), temps de service le plus court d’abord. L’agence bancaire, le supermarché et le parking fournissent des exemples de systèmes à serveurs parallèles, et la chaîne de montage automobile est un exemple de système en série. Plus généralement, les ateliers de production peuvent présenter une structure parallèle, ou en série, ou une organisation plus générale encore (si les divers ordres de fabrication visitent les machines selon des séquences différentes) (utilisé dans les ateliers de production), dernier arrivé premier servi, sélection aléatoire, etc.

La capacité du système, c’est-à-dire le nombre de clients pouvant être simultanément présents dans le système, est limité ou non. Dans le premier cas, on suppose que les clients qui arrivent lorsque le système est déjà saturé le quittent immédiatement sans obtenir le service désiré. On dit que ces clients sont perdus. Dans le cas d’un système à capacité illimitée, bien sûr, aucun client n’est perdu (mais la longueur des files d’attente peut grandir indéfiniment !). Dans notre cas, nous nous limiterons à l’étude de systèmes à serveurs parallèles à arrivées et service individuels. Nous supposerons également que tous les clients demandent le même service et que les serveurs sont identiques.

Mesures de performance – Comportement à long terme

Nous appelons état d’un système à l’instant t le nombre n (t) de clients présents dans le système à cet instant (un client est « présent dans le système » si il est en file d’attente ou en cours de service). Les quantités fondamentales auxquelles s’intéresse l’analyste dans le cadre des modèles de files d’attente sont les probabilités d’état, que nous définissons de la façon suivante: pour n = 0, 1, 2, … et t ≥ 0,

Remarque

Il faut se garder de confondre l’existence des probabilités stationnaires (1.02) et la disparition (à long terme) des fluctuations aléatoires du système. Pour bien comprendre ceci, il faut remarquer que l’état d’un système stochastique est en général soumis à deux sources de variabilité: d’une part, les fluctuations aléatoires qui affectent le système en permanence, et qui, même dans un très court laps de temps, sont responsables des variations du système autour de son état moyen; d’autre part, l’évolution temporelle du système à plus long terme, qui peut être vue comme un déplacement de l’état moyen lui- même. (Par exemple, la valeur d’un titre boursier peut enregistrer de légers gains ou pertes quotidiens tout en affichant une tendance – un trend – à la hausse dans le long terme.) L’existence des probabilités stationnaires signifie seulement que, au fil du temps, l’évolution temporelle tend à disparaître, sans que l’état du système devienne parfaitement prédictible (déterministe) pour la cause.

Distribution exponentielle

Intuitivement, il existe deux façons de décrire le processus selon lequel les arrivées de clients surviennent dans un système: on peut en effet vouloir placer l’accent sur:
• le nombre de clients qui arrivent dans un intervalle de temps donné (par exemple, 10 clients par heure),
• ou sur l’intervalle de temps écoulé entre deux arrivées successives (par exemple, une arrivée toutes les 6 minutes).

Table des matières

INTRODUCTION
CHAPITRE 1 : THEORIE DE LA FILE D’ATTENTE
1.1. Généralités
1.2. Mesures de performance – Comportement à long terme
1.2.1. Remarque
1.2.2.Proposition 1 (Loi de Little)
1.2.3. Démonstration
1.2.4. Exemple
1.3. Processus de Poisson
1.4. Distribution exponentielle
1.4.1. Proposition 2
1.4.2. Proposition 3
1.4.3. Démonstration
1.5. Processus de service
1.6. Notations de Kendall
1.7. Processus de naissance et de mort
1.7.1. Définition
1.7.2. Processus de naissance pur
1.7.3. Processus de mort pur
1.8. Système M/M/1
1.9. Système M/M/c
1.10. Système M/M/c/N
1.11. Techniques de gestion de file d’attente
1.12. Conclusion
CHAPITRE 2 : LA LOGIQUE FLOUE
2.1. Introduction
2.2. Historique de la logique floue
2.2.1. Premières applications
2.2.2. Essor
2.3. Intérêt et utilisation de la logique floue pour le contrôle
2.3.1. Utilisation pour le contrôle
2.3.2. La capitalisation du savoir-faire
2.4. Théorie des ensembles flous
2.4.1. Notion d’appartenance partielle
2.4.2. Fonctions d’appartenance
3.4.3. Fuzzification – Degré d’appartenance
2.5. Opérateurs logiques flous
2.5.1. Choix des opérateurs
2.5.2. Intersection
2.5.3. Exemple
2.5.4. Union
2.5.5. Complément
2.5.6. Ladder flou
2.5.7. Classification floue
2.6. Règles floues
2.6.1. La logique floue et l’intelligence artificielle
2.6.1.1. Prédicat
2.6.1.2. Inférence
2.6.1.3. Conclusion
2.7. Mécanisme d’inférence de Mamdani
2.7.1. Principe
2.7.2. Fuzzification
2.7.3. Degré d’activation
2.7.4. Implication
2.7.5. Agrégation
2.8. Défuzzification
2.9. Règles « libres » et « en tableau »
2.10. Contrôle flou
2.10.1. Algorithme du contrôleur flou
2.10.2. Contrôle flou et système expert
2.10.3. Règles
2.10.4. Les prédicats
2.10.5. Défuzzification, méthodes de Mamdani et Sugeno
2.10.6. Avantage du contrôle flou
2.11. Conclusion
CHAPITRE 3 : QOS ET LES ALGORITHMES AQM
3.1. Introduction
3.2. Qualité de Service ou QoS
3.2.1. Généralité
3.2.2. Fonctions par rapport à la gestion de la QoS
3.2.2.1. Classifieur
3.2.2.2. Ordonnanceur
3.2.3. Mécanisme de lissage de trafic
3.2.4. Ordonnancement des files de sortie
3.2.4.1. FIFO
3.2.4.2. Par Priorité
3.2.4.3. Round Robin
3.2.4.4. Class-Based Queuing
3.2.4.5. Weighted Fair Queuing
3.3. Approche IntServ (Integrated Service)
3.3.1. Le protocole RSVP (Resource ReserVation Protocol)
3.3.2. Modèles de Réservation
3.3.3. Principe de RSVP pour la réservation
3.3.4. Format d’un message RSVP
3.3.5. Conclusion sur IntServ
3.4. Approche DiffServ
3.4.1. Présentation et architecture d’un réseau DiffServ
3.4.2. Classification et conditionnement du trafic
3.5. Les différents algorithmes AQM (Active Queue Management)
3.5.1. Gestion de la file d’attente
3.5.2. A quoi ca sert l’AQM ?
3.5.3. Avantages d’AQM
3.5.4. Early Random Drop
3.5.5. Random Early Detection
3.5.6. Adaptive RED
3.5.7. BLUE
3.5.7.1. Motivation
3.6. Conclusion
CHAPITRE 4 : THEORIE MATHEMATIQUE DU CONTROLEUR ADAPTATIF
CONCLUSION

Lire le rapport complet