Performances des réseaux et des systèmes informatiques

Thomas Bonald, Mathieu Feuillet

Description

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.

Sujets

• Informatique
• Mathématiques
• réseaux

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 14 avril 2011
• Nombre de lectures: 179
• EAN13: 9782746241152
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

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 parPierre-Noël F AVENNEC Comité scientifique de la collection Président: Claude G UÉGUEN Michel A LLOVON –Orange Labs Chantal A MMI –Télécom Ecole de management Annie B LANDIN –Télécom Bretagne Jean-Pierre C OCQUEREZ –UTC, GDR ISIS Frédérique DE F ORNEL –ICB, GDR Ondes Gérard E UDE –Orange Labs Georges F ICHE –APAST Alain H ILLION –Télécom Bretagne René J OLY –Télécom ParisTech Henri M AÎTRE –Télécom ParisTech Chantal M ORLEY –Télécom SudParis Gérard P OGOREL –Télécom ParisTech Gérard P OULAIN –APAST Serge P ROULX –UQAM Montreal Nicolas P UECH –Télécom ParisTech Guy P UJOLLE –UPMC Pierre R OLIN –Télécom SudParis Basel S OLAIMAN –Télécom Bretagne Sami T ABBANE –SupCom Tunis Joe W IART –Orange Labs http://ctst.institut-telecom.fr

Table des matières

Avantpropos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Les réseaux de communication . . . . . . . . . . . . . . . . . . . . . . . 1.3. Le trafic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4. Les files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5. Structure du livre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 2. Loi exponentielle. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Analogue discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Une loi amnésique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4. Minimum de variables exponentielles . . . . . . . . . . . . . . . . . . . 2.5. Somme de variables exponentielles . . . . . . . . . . . . . . . . . . . . 2.6. Somme aléatoire de variables exponentielles . . . . . . . . . . . . . . . 2.7. Une loi limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8. Une variable « très » aléatoire . . . . . . . . . . . . . . . . . . . . . . . 2.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 3. Processus de Poisson. . . . . . . . . . . . . . . . . . . . . . . . . 3.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Analogue discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

11 11 11 13 14 14 15

17 17 18 19 20 21 22 22 23 24 25

27 27 28

6

Performance des réseaux et des systèmes informatiques

3.3. Un processus amnésique . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4. Répartition des points d’un processus de Poisson . . . . . . . . . . . . 3.5. Superposition de processus de Poisson . . . . . . . . . . . . . . . . . . 3.6. Subdivision d’un processus de Poisson . . . . . . . . . . . . . . . . . . 3.7. Un processus limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8. Un processus « très » aléatoire . . . . . . . . . . . . . . . . . . . . . . . 3.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 4. Chaînes de Markov. . . . . . . . . . . . . . . . . . . . . . . . . . 4.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Probabilités de transition . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Périodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4. Equations d’équilibre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5. Mesure stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6. Stabilité, ergodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7. Récurrence, transience . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8. Fréquence de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9. Formule des transitions conditionnelles . . . . . . . . . . . . . . . . . . 4.10. Chaîne en temps retourné . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11. Réversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12. Critère de Kolmogorov . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.13. Troncation d’une chaîne de Markov . . . . . . . . . . . . . . . . . . . 4.14. Marche aléatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.15. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.16. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 5. Processus de Markov. . . . . . . . . . . . . . . . . . . . . . . . . 5.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Taux de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Analogue discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4. Equations d’équilibre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5. Mesure stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6. Stabilité, ergodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7. Récurrence, transience . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8. Fréquence de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.9. Transitions virtuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10. Chaîne incluse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.11. Formule des transitions conditionnelles . . . . . . . . . . . . . . . . . . 5.12. Processus en temps retourné . . . . . . . . . . . . . . . . . . . . . . . . 5.13. Réversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.14. Critère de Kolmogorov . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.15. Troncation d’un processus réversible . . . . . . . . . . . . . . . . . . .

30 30 31 32 32 33 33 34

37 37 38 38 38 39 39 40 41 41 42 42 43 44 45 46 46

51 51 51 52 53 54 54 55 55 55 56 57 58 58 59 59

Table des matières

5.16. Produit de processus de Markov indépendants . . . . . . . . . . . . . . 5.17. Processus de naissance et de mort . . . . . . . . . . . . . . . . . . . . . 5.18. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.19. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 6. Files d’attente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1. Notation de Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Trafic et charge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3. Discipline de service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4. Files élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5. Une file générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6. Formule de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7. Propriété PASTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.8. Insensibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9. Formule de PollaczekKhinchin . . . . . . . . . . . . . . . . . . . . . . 6.10. Paradoxe de l’observateur . . . . . . . . . . . . . . . . . . . . . . . . . 6.11. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.12. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 7. Réseaux de files d’attente. . . . . . . . . . . . . . . . . . . . . . 7.1. Réseaux de Jackson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2. Equations de trafic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3. Distribution stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4. Propriété MUSTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5. Réseaux fermés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6. Réseaux de Whittle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7. Réseaux de Kelly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 8. Trafic circuit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1. Modèle d’Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2. Formule d’Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3. Formule d’Engset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4. Formule d’Erlang à attente . . . . . . . . . . . . . . . . . . . . . . . . . 8.5. Modèle d’Erlang multiclasse . . . . . . . . . . . . . . . . . . . . . . . . 8.6. Formule de KaufmanRoberts . . . . . . . . . . . . . . . . . . . . . . . 8.7. Modèle de réseaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8. Approximation par découplage . . . . . . . . . . . . . . . . . . . . . . . 8.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

60 61 61 63

69 69 70 71 72 77 79 80 80 81 83 85 87

93 93 94 96 97 98 99 100 102 103

109 109 110 112 115 117 120 121 122 123 125

8

Performance des réseaux et des systèmes informatiques

Chapitre 9. Trafic temps réel. . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1. Flots et paquets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2. Modèle de niveau paquet . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3. Modèle de niveau flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4. Taux de congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5. Débit moyen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.6. Taux de perte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.7. Modèle multidébit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.8. Modèle de réseaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.10. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 10. Trafic élastique. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.1. Partage de bande passante . . . . . . . . . . . . . . . . . . . . . . . . . 10.2. Taux de congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3. Débit moyen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.4. Taux de perte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.5. Modèle multidébit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.6. Modèle de réseaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.7. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.8. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 11. Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1. Réseaux d’accès IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Réseaux mobiles 2G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3. Réseaux mobiles 3G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4. Réseaux mobiles 3G+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.5. Réseaux d’accès WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.6. Centres de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.7. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.8. Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . .

Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

131 131 132 134 135 136 138 139 140 141 143

149 149 152 153 154 155 157 158 160

167 167 170 173 177 180 185 187 189

195