Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Performances des réseaux et des systèmes informatiques

De
214 pages
Les réseaux et les systèmes informatiques sont devenus extraordinairement complexes. Les protocoles et algorithmes qui en assurent le partage permettent d'absorber les fluctuations du trafic liées au comportement aléatoire des utilisateurs, ceci au prix d'une dégradation de la qualité des communications et de l'interactivité des applications.
Cet ouvrage présente les principaux outils d'analyse de performance de ces systèmes, permettant d'estimer l'impact de leur charge sur la qualité de service. Performances des réseaux et des systèmes informatiques expose les résultats de la théorie de Markov et de la théorie des files d'attente utiles à la modélisation du trafic et à la résolution de problèmes concrets d'ingénierie. Performances des réseaux et des systèmes informatiques est destiné aussi bien aux étudiants de niveau Master qu'aux chercheurs et ingénieurs dans le domaine de l'informatique et des réseaux.
Chaque développement est illustré par une série d'exercices corrigés. Un chapitre est consacré à l'application des résultats au dimensionnement des réseaux d'accès IP et WiFi et des réseaux cellulaires 2G, 3G et 3G+.
Chapitre 1. Introduction. Chapitre 2. Loi exponentielle. Chapitre 3. Processus de Poisson. Chapitre 4. Chaînes de Markov. Chapitre 5. Processus de Markov. Chapitre 6. Files d'attente. Chapitre 7. Réseaux de files d'attente. Chapitre 8. Trafic circuit. Chapitre 9. Trafic temps réel. Chapitre 10. Trafic élastique. Chapitre 11. Applications. Index.
Voir plus Voir moins




















Performances des réseaux et des systèmes informatiques





















Cet ouvrage appartient à la Collection Télécom (précédemment Collection Technique et
Scientifique des Télécommunications (CTST)), publiée sous l’égide de l’Institut Télécom,
avec le soutien de Orange Labs. Cette collection rend compte des derniers développements
dans l’ensemble des domaines des sciences et technologies de l’information et de la
communication.














© Institut Télécom et LAVOISIER, Paris, 2011
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-2977-8
ISSN 2109-8204



Le Code de la propriété intellectuelle n’autorisant, aux termes de l’article L. 122-5, d’une
part, que les "copies ou reproductions strictement réservées à l’usage privé du copiste et non
destinées à une utilisation collective" et, d’autre part, que les analyses et les courtes citations
dans un but d’exemple et d’illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.


Printed and bound in England by Antony Rowe Ltd, Chippenham, April 2011.






Performances des réseaux

et des systèmes

informatiques












Thomas Bonald

Mathieu Feuillet







Collection Télécom
dirigée par Pierre-Noël FAVENNEC



Comité scientifique de la collection


Président : Claude GUÉGUEN


Michel ALLOVON – Orange Labs
Chantal AMMI – Télécom Ecole de management
Annie BLANDIN – Télécom Bretagne
Jean-Pierre COCQUEREZ – UTC, GDR ISIS
Frédérique DE FORNEL – ICB, GDR Ondes
Gérard EUDE – Orange Labs
Georges FICHE – APAST
Alain HILLION – Télécom Bretagne
René JOLY – Télécom ParisTech
Henri MAÎTRE – Télécom ParisTech
Chantal MORLEY – Télécom SudParis
Gérard POGOREL – Télécom ParisTech
Gérard POULAIN – APAST
Serge PROULX – UQAM Montreal
Nicolas PUECH – Télécom ParisTech
Guy PUJOLLE – UPMC
Pierre ROLIN – Télécom SudParis
Basel SOLAIMAN – Télécom Bretagne
Sami TABBANE – SupCom Tunis
Joe WIART – Orange Labs


http://ctst.institut-telecom.fr



Table des matières
Avant-propos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Chapitre 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2. Les réseaux de communication . . . . . . . . . . . . . . . . . . . . . . . 11
1.3. Le trafic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4. Les files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5. Structure du livre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chapitre 2. Loi exponentielle . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2. Analogue discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3. Une loi amnésique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4. Minimum de variables exponentielles . . . . . . . . . . . . . . . . . . . 20
2.5. Somme de v e . . . . . . . . . . . . . . . . . . . . 21
2.6. aléatoire de variables exponentielles . . . . . . . . . . . . . . . 22
2.7. Une loi limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8. Une variable « très » aléatoire . . . . . . . . . . . . . . . . . . . . . . . 23
2.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Chapitre 3. Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2. Analogue discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
16 Performance des réseaux et des systèmes informatiques
3.3. Un processus amnésique . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4. Répartition des points d’un processus de Poisson . . . . . . . . . . . . 30
3.5. Superposition de processus de Poisson . . . . . . . . . . . . . . . . . . 31
3.6. Subdivision d’un de . . . . . . . . . . . . . . . . . . 32
3.7. Un processus limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.8. Un « très » aléatoire . . . . . . . . . . . . . . . . . . . . . . . 33
3.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Chapitre 4. Chaînes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2. Probabilités de transition . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3. Périodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4. Equations d’équilibre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5. Mesure stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.6. Stabilité, ergodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.7. Récurrence, transience . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.8. Fréquence de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.9. Formule des transitions conditionnelles . . . . . . . . . . . . . . . . . . 41
4.10. Chaîne en temps retourné . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.11. Réversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.12. Critère de Kolmogorov . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.13. Troncation d’une chaîne de Markov . . . . . . . . . . . . . . . . . . . 44
4.14. Marche aléatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.15. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.16. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Chapitre 5. Processus de Markov . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2. Taux de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3. Analogue discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.4. Equations d’équilibre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.5. Mesure stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.6. Stabilité, ergodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.7. Récurrence, transience . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.8. Fréquence de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.9. Transitions virtuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.10. Chaîne incluse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.11. Formule des transitions conditionnelles . . . . . . . . . . . . . . . . . . 57
5.12. Processus en temps retourné . . . . . . . . . . . . . . . . . . . . . . . . 58
5.13. Réversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.14. Critère de Kolmogorov . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.15. Troncation d’un processus réversible . . . . . . . . . . . . . . . . . . . 59Table des matières 7
5.16. Produit de processus de Markov indépendants . . . . . . . . . . . . . . 60
5.17. Processus de naissance et de mort . . . . . . . . . . . . . . . . . . . . . 61
5.18. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.19. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Chapitre 6. Files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.1. Notation de Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2. Trafic et charge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.3. Discipline de service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.4. Files élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.5. Une file générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.6. Formule de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.7. Propriété PASTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.8. Insensibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.9. Formule de Pollaczek-Khinchin . . . . . . . . . . . . . . . . . . . . . . 81
6.10. Paradoxe de l’observateur . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.11. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.12. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Chapitre 7. Réseaux de files d’attente . . . . . . . . . . . . . . . . . . . . . . 93
7.1. Réseaux de Jackson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2. Equations de trafic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.3. Distribution stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.4. Propriété MUSTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.5. Réseaux fermés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.6. de Whittle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.7. Réseaux de Kelly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.8. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.9. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Chapitre 8. Trafic circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.1. Modèle d’Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.2. Formule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
8.3. F d’Engset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.4. Formule d’Erlang à attente . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.5. Modèle multi-classe . . . . . . . . . . . . . . . . . . . . . . . . 117
8.6. Formule de Kaufman-Roberts . . . . . . . . . . . . . . . . . . . . . . . 120
8.7. Modèle de réseaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.8. Approximation par découplage . . . . . . . . . . . . . . . . . . . . . . . 122
8.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258 Performance des réseaux et des systèmes informatiques
Chapitre 9. Trafic temps réel . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
9.1. Flots et paquets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
9.2. Modèle de niveau paquet . . . . . . . . . . . . . . . . . . . . . . . . . . 132
9.3. de niveau flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
9.4. Taux de congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.5. Débit moyen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
9.6. Taux de perte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.7. Modèle multi-débit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.8. de réseaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
9.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Chapitre 10. Trafic élastique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.1. Partage de bande passante . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.2. Taux de congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
10.3. Débit moyen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.4. Taux de perte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
10.5. Modèle multi-débit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
10.6. de réseaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
10.7. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
10.8. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Chapitre 11. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
11.1. Réseaux d’accès IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
11.2. mobiles 2G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
11.3. Réseaux 3G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
11.4. mobiles 3G+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
11.5. Réseaux d’accès WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
11.6. Centres de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.7. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11.8. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195Avant-propos
L’idée que l’on se fait des files d’attente est d’abord celle de la vie de tous les jours :
caisse de supermarché, guichet de banque, péage autoroutier, etc. Il est plus difficile de
se représenter les files d’attente de nos ordinateurs et réseaux de communication, qui
pourtant en assurent le bon fonctionnemement et en conditionnent les performances.
Les bits et octets étant plus maléables que les êtres humains, les files d’attente qui nous
intéressent ici sont bien plus diverses et plus riches que celles de notre quotidien.
Le trafic étant aléatoire, l’analyse des files d’attente repose sur la théorie des proba-
bilités, et plus particulièrement sur la théorie de Markov. Celle-ci, très simple dans son
principe et très puissante dans son champ d’application, est devenue au fil des décen-
nies un outil indispensable non seulement de l’informatique et des réseaux (codage et
compression de l’information, files d’attente), mais de nombreuses autres disciplines
scientifiques comme les statistiques (méthodes d’inférence), la physique (thermody-
namique), la biologie (analyse du code génétique) et les sciences économiques et
sociales (finance, modèles de transition). Nous avons donc choisi d’en présenter les
principaux rouages, sans prétendre à l’exhaustivité, en ne faisant appel qu’à des notions
élémentaires de probabilités.
La partie consacrée aux réseaux proprement dits est le fruit de notre expérience dans
les laboratoires de R&D de France Télécom, où nous avons pu mesurer l’importance
de la modélisation du trafic et de l’évaluation de performance dans tous les domaines
de l’ingénierie des réseaux : conception, planification, choix d’architecture, mesure,
contrôle, etc. C’est en analysant chaque partie de ces énormes machines que sont les
réseaux de communication qu’on en comprend le fonctionnement global et qu’on peut
in fine en améliorer les performances.
Ce livre est issu d’un cours donné aux élèves de Télécom ParisTech depuis 2004.
Il a bénéficié de leurs nombreuses remarques, suggestions et interrogations. Qu’ils en
soient remerciés.10Chapitre 1
Introduction
1.1. Motivation
L’analyse de performance des réseaux et systèmes informatiques, et la théorie des
efiles d’attente qui en est issue, est née au début du XX siècle lorsque deux ingénieurs
1 2scandinaves, Erlang et Engset , trouvent indépendamment des formules très proches
pour calculer la probabilité de rejet d’un appel téléphonique sur un concentrateur. C’est
à partir de ces formules que les opérateurs téléphoniques ont pu dimensionner leurs
réseaux de façon optimale, en fonction de prévisions de trafic et d’un taux de rejet cible,
acceptable pour les clients.
Aujourd’hui encore, l’ingénierie des réseaux et systèmes informatiques au sens
large, qui concerne non seulement l’architecture et le dimensionnement de ces sytèmes,
mais également les algorithmes et protocoles de partage des ressources et de contrôle
du trafic, repose sur des outils mathématiques dérivés de la théorie des files d’attente.
L’objectif de ce livre est de décrire quelques outils-clés et de montrer comment ils
permettent de résoudre des problèmes concrets d’ingénierie.
1.2. Les réseaux de communication
Il existe en gros deux types de techniques pour partager les ressources d’un réseau
de communication :
1. Agner Krarup Erlang, ingénieur et mathématicien danois (1878 – 1929).
2. Tore Olaus Engset, et norvégien (1865 – 1943).
1112 Performance des réseaux et des systèmes informatiques
– la technique dite circuit, qui consiste à réserver des ressources avant toute com-
munication, puis à transférer l’information une fois la réservation effectuée, le long du
circuit établi ;
– la technique dite paquet, pour laquelle les communications se font sans réservation
préalable, l’information étant transférée sous forme de paquets indépendants, soumis
aux aléas du trafic sur leur chemin jusqu’à la destination.
(a) Mode circuit
(b) Mode paquet
Figure 1.1. Techniques de communication.
Schématiquement, c’est le téléphone (commuté) contre l’IP : le principe de la
réservation contre le principe du partage. Du point de vue de la qualité de service, ce
sont les critères d’accessibilité (taux de rejet d’un appel) contre les critères de vitesse
(débit) et d’intégrité (délai des paquets, taux de perte).
La frontière entre mode circuit et mode paquet n’est pas aussi nette en pratique. La
technologie MPLS (Multi-Protocol Label Switching) utilise des circuits virtuels en IP
par exemple ; les réseaux d’accès radio 3G utilisent à la fois le mode circuit et le mode
paquet ; un fournisseur à Internet peut bloquer certains flux vidéos en cas de
congestion, chaque flux pouvant alors être considéré comme un circuit virtuel dans le
réseau IP. On pourrait multiplier les exemples. Malgré tout, cette classification entre
circuit et paquet est très utile. Elle correspond à deux grandes classes de modèles que
nous allons étudier :
– pour le mode circuit, le modèle d’Erlang et ses extensions, qui font l’objet du
chapitre 8 ;
– pour le mode paquet, les modèles de trafic IP, qui font l’objet du chapitre 9 pour
le trafic temps réel et du chapitre 10 pour le trafic dit élastique.
Pour les systèmes utilisant les deux modes, circuit et paquet, il faut combiner ces
modèles, comme nous le verrons en fin d’ouvrage.Introduction 13
1.3. Le trafic
Les performances des réseaux et des systèmes informatiques sont essentiellement
liées aux fluctuations statistiques du trafic dues au comportement des utilisateurs.
3Pour trouver sa formule en 1917, Erlang avait par exemple supposé que les appels
4téléphoniques arrivaient selon un processus de Poisson et avaient des durées aléatoires
3de loi exponentielle , comme illustré par la figure 1.2-(a). Ces hypothèses lui permirent
3en utilisant la théorie encore toute neuve de Markov d’exprimer le taux de rejet d’un
appel en fonction du nombre de circuits disponibles et de l’intensité de trafic.
Erlang avait en outre remarqué par simulation que sa formule était insensible à la
loi de la durée des appels, mise à part leur moyenne. Cette propriété, qui ne fut prouvée
5que 40 ans plus tard , fait de la formule d’Erlang un résultat simple et extrêmement
robuste : elle ne dépend des caractéristiques du trafic que par son intensité. Ceci
explique pourquoi la formule est toujours utilisée de nos jours, alors que le trafic
téléphonique d’aujourd’hui n’a évidemment plus rien à voir avec celui de l’époque
d’Erlang.
80 80
60 60
40 40
20 20
0 0
0 5 10 15 20 25 30 0 10 20 30 40 50 60
Temps (mn) Temps (mn)
(a) Trafic téléphonique (b) Trafic de données
Figure 1.2. Aléa du trafic.
De la même manière, les performances des réseaux IP dépendent de la nature aléa-
toire du trafic. La figure 1.2-(b) montre par exemple des flots de données arrivant selon
un processus de Poisson, de volumes aléatoires distribués selon une loi exponentielle,
schématisés par les hauteurs des barres verticales. Nous verrons que, sous certaines
hypothèses de partage des ressources par les flots en cours, la plupart des métriques de
performance sont également insensibles à la loi du volume des flots, mise à part leur
3. ERLANG A.K., Solution of some problems in the theory of probabilities of significance in
automatic telephone exchanges, 1917.
4. Nous reviendrons en détail sur ces notions dans les chapitres 2 à 5.
5. SEVASTYANOV B.A., An ergodic theorem for Markov processes and its application to
telephone systems with refusals, 1957.
Appel
Flot14 Performance des réseaux et des systèmes informatiques
moyenne. Elles ne dépendent des caractéristiques du trafic que par son intensité, ce
qui fait des résultats présentés des extensions naturelles de la formule d’Erlang pour
les réseaux IP : simples, utiles et robustes. Ces résultats sont largement applicables
aux systèmes informatiques, dont les ressources sont également partagées de façon
dynamique.
1.4. Les files d’attente
Les files d’attente sont omniprésentes dans les réseaux de communication fonction-
nant en mode paquet. On en trouve dans chaque ordinateur, chaque routeur, chaque
point d’accès radio. Ce sont de véritables entonnoirs dont le but est de maximiser
l’utilisation des ressources du réseau. C’est à leur niveau que l’on met en place les
politiques de partage entre les utilisateurs par l’ordonnancement et le rejet sélectif des
paquets. Lorsque plusieurs transferts de données se partagent un même lien, le système
constitué de l’ensemble des fichiers en cours de transfert peut lui-même être vu comme
une file d’attente virtuelle, distribuée sur l’ensemble des serveurs où sont stockés les
fichiers en cours de transfert.
Par extension, les modèles de réseaux à commutation de circuits sont considérés
comme des files d’attente particulières, sans attente justement, puisque les flux sont
simplement admis ou rejetés. Dans certains cas, comme les réseaux mobiles ou les
centres d’appel, l’opérateur peut mettre en place un système de mise en attente plus
ou moins limitée, dans l’espoir qu’une ressource se libère rapidement. Formellement,
on devrait donc parler de files d’attente et de rejet ; l’usage est cependant d’utiliser le
terme plus simple de file d’attente.
1.5. Structure du livre
Chapitre 1. Introduction
Chapitres 2 à 5. Processus de Poisson et théorie de Markov 6 et 7. Éléments de la théorie des files d’attente
Chapitres 8 à 10. Modèles de trafic
Chapitre 11. Applications
Les dépendances entre chapitres sont données par la figure 1.3. Chaque chapitre
est ponctué d’une liste d’exercices avec corrigés, permettant de manipuler les outils
présentés.
On utilisera les abbréviations p.s. pour « presque sûrement » et i.i.d. pour « indé-
pendants et identiquement distribués ».Introduction 15
2. Loi exponentielle 4. Chaînes de Markov
3. Processus de Poisson 5. Processus de Markov
6. Files d’attente 7. Réseaux de files d’attente
9. Trafic temps réel 10. Trafic élastique8. Trafic circuit
11. Applications
Figure 1.3. Relations de dépendance entre chapitres.
1.6. Bibliographie
Pour aller plus loin, on pourra consulter les ouvrages suivants :
BRÉMAUD P., Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues,
Springer-Verlag, 1999.
KELLY F., Reversibility and Stochastic Networks, Wiley, Chichester, 1979.
KLEINROCK L., Queueing Systems : Volume I – Theory, Wiley Interscience, 1975.
ROSS K. W., Multiservice Loss Networks for Broadband Telecommunications Net-
works, Springer-Verlag, New York, 1995.
SERFOZO R., Introduction to Stochastic Networks, Springer-Verlag, New York, 1999.16Chapitre 2
Loi exponentielle
J’ai une mémoire admirable, j’oublie tout.
Alphonse Allais (1854 – 1905).
2.1. Définition
On dit qu’une variable aléatoire réelle positive X suit une loi exponentielle de
paramètre> 0 si :
tP(X >t) =e ; 8t2R :+
1
0.8
0.6
0.4
0.2
0
0 1 2 3 4 5
t
Figure 2.1. Loi exponentielle de paramètre = 1 et temps de demi-vie.
La densité de cette loi est donnée par :
tf(t) = e ; 8t2R :+
17
P(X>t)18 Performance des réseaux et des systèmes informatiques
La moyenne et la variance deX sont respectivement données par :
Z Z1 11 12 2E(X) = tf(t)dt = ; var(X) = t f(t)dt E(X) = :
2 0 0
La loi exponentielle est utilisée par exemple en physique pour représenter le temps de
vie d’une particule, le paramètre représentant la vitesse à laquelle la particule vieillit.
Le temps de demi-vie de la particule est ainsi le tempst tel que P(X >t) = 1=2, soit
t = ln(2)= , comme illustré par la figure 2.1.
2.2. Analogue discret
La loi exponentielle est au temps continu ce que la loi géométrique est au temps
discret. Une variable aléatoire entière strictement positiveX suit une loi géométrique
de paramètrep2 (0; 1] si :
n 1P(X =n) =p(1 p) ; 8n 1;
ou de manière équivalente si :
nP(X >n) = (1 p) ; 8n2N:
Figure 2.2. Approximation d’une loi exponentielle par une loi géométrique.
La moyenne et la variance deX sont respectivement données par :
1X 1n 1E(X) = np(1 p) = ;
p
n=1
1X 1 p2 n 1 2var(X) = n p(1 p) E(X) = :
2p
n=1
Ainsi sip représente la probabilité de gain au loto,X donne la distribution du nombre
de tentatives nécessaires pour gagner. Lorsquep est faible, la loi géométrique est proche
d’une loi exponentielle, comme illustré par la figure 2.2.Loi exponentielle 19
()Formellement, on note X une variable aléatoire géométrique de paramètre
()p = , où est un paramètre fixé, strictement positif, et un pas de temps
()suffisamment faible. Lorsque tend vers zéro, la variable aléatoire réelleX tend
en loi vers une variable aléatoire exponentielle de paramètre :
t() () b c tP(X >t) = (1 p ) !e ; 8t2R :+
2.3. Une loi amnésique
La loi géométrique est sans mémoire : au loto, le nombre de tentatives nécessaires
pour gagner ne dépend pas des tentatives précédentes. Cette propriété d’amnésie est
également satisfaite par la loi exponentielle et s’écrit :
P(X >s +tjX >s) = P(X >t); 8s;t2R :+
Ceci est illustré par la figure 2.3.
Figure 2.3. Propriété d’amnésie : une variable exponentielle oublie son passé.
En notant F (t) = P(X > t) la fonction de répartition inverse de la variable
aléatoireX, et en remarquant que pour touts2R tel queF (s)> 0,+
F (s +t)
P(X >s +tjX >s) = ;
F (s)
la propriété d’amnésie est équivalente à l’équation fonctionnelle :
F (s +t) =F (s)F (t); 8s;t2R :+
Les fonctions exponentielles sont les seules solutions de cette équation. CommeF est
une fonction décroissante, non identiquement égale à 1, il existe une constante> 0
telle que :
tF (t) =e ; 8t2R :+
Une conséquence de cette propriété est qu’une variable exponentielle peut être
simplement décrite par son comportement au temps t = 0, comme illustré par la