Congestion Control In High Speed Networks (master Thesis: Nadir Bouchama). Contrôle De Congestion Dans Les Réseaux à Haut Débit

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université Abderrahmane Mira de Béjaïa Faculté des Sciences et des Sciences de l’Ingénieur Ecole Doctorale d’Informatique

Laboratoire LAMOS

Mémoire de Magistère En Informatique Option Réseaux et Systèmes Distribués

Thème

Contrôle de Congestion dans les Réseaux à Haut Débit

Présenté par Nadir BOUCHAMA

Devant le jury : Z. Sahnoun D. Aissani N. Djellab A. Oukaour

Professeur Professeur M.C M.C

Président Rapporteur Examinateur Examinateur

Université Université Université Université

Promotion 2004 − 2005

de de de de

Constantine Béjaïa Annaba Caen (France)

Dédicaces A mes chers parents, A mes deux frères, A ma soeur, A mes oncles, A ma petite nièce Yasmine et mon neveu Mohammed, A la mémoire de notre collègue Chahine Kacem, Enfin à tous ceux que j’aime et ceux qui m’aiment, Je dédie ce modeste travail

Remerciements

M

ERCI à mes parents pour leur patience et leur soutien indéfectbile qui m’ont été plus qu’indispensables.

Mes très vifs remerciements vont à l’encontre de mon directeur de thèse, le Professeur Djamil Aissani pour avoir accepté de m’encadrer et de m’orienter tout au long de ce travail. Je le remercie également pour m’avoir acceuilli aux séminaires du LAMOS (LAboratoire de Modélisation et d’Optimisation des Systèmes), séminaires dans lesquels j’ai beaucoup appris. Je remercie également Docteur Natalia Djellab de l’université de Annaba pour toute la documentation qu’elle a mise à ma disposition ainsi que pour tous ses conseils très précieux et ses orientations qui m’ont été très bénéfiques et j’espère d’être à la hauteur de son espérance. Je remercie vivement tous les enseignants et responsables de l’Ecole Doctorale d’Informatique de Béjaia pour tous les efforts qu’ils ont fournis pour la réussite et l’épanouissement de l’Ecole. Un grand remerciement va aussi au Professeur Zaïdi Sahnoun de l’université de Constantine pour avoir accepté de présider le jury de ma soutenance et au M.C Amrane Oukaour de l’université de Caen pour avoir accepté de juger ce humble travail. Qu’ils trouvent ici l’expression de ma profonde reconnaissance. Un grand remerciement va à mes collègues de l’Ecole Doctorale RESYD (REseaux et SYstèmes Distribués), notamment pour Saïd Gharout pour son aide très précieuse en LATEX. Qu’il trouve ici l’expression de ma profonde gratitude. Enfin, que tous ceux qui ont contribué de près ou de loin à l’aboutissement de ce travail trouvent ici ma reconnaissance et de ma sympatathie.

Table des matières Introduction Générale

3

1 Panorama des Réseaux Haut Débit 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Taxonomie des réseaux informatiques . . . . . . . . . . . . . . . . . . . 1.2.1 Taxonomie selon la distance . . . . . . . . . . . . . . . . . . . . 1.2.2 Taxonomie en fonction de la topologie . . . . . . . . . . . . . . 1.2.3 Taxonomie en fonction du mode de commutation . . . . . . . . 1.2.3.1 Réseaux à commutation de circuits . . . . . . . . . . . 1.2.3.2 Réseaux à commutation de paquets . . . . . . . . . . . 1.3 Les réseaux à haut débit . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Définitions d’un réseau haut débit . . . . . . . . . . . . . . . . . 1.3.3 Multiplexage statistique dans les réseaux à haut débit . . . . . . 1.4 Technologies pour supporter les hauts débits pour les WANs . . . . . . 1.4.1 La technologie Relais de Trames (Frame Relay) . . . . . . . . . 1.4.2 La technologie ATM (Asynchronous Transfert Mode) . . . . . . 1.4.2.1 Cellule ATM . . . . . . . . . . . . . . . . . . . . . . . 1.4.2.2 Les connexions ATM . . . . . . . . . . . . . . . . . . . 1.4.2.3 Qualité de Service dans ATM . . . . . . . . . . . . . . 1.4.2.4 Paramètres de qualité de service dans les réseaux ATM 1.4.2.5 Classes de services dans ATM . . . . . . . . . . . . . . 1.4.3 La technologie MPLS ( MultiProtocol Label Switching) . . . . . 1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 4 5 5 6 7 7 9 9 11 12 14 14 14 15 17 17 18 20 21 23

2 Contrôle de Congestion dans les Réseaux Haut 2.1 Introduction . . . . . . . . . . . . . . . . . . . . 2.2 Terminologie et concepts de base . . . . . . . . 2.2.1 Allocation de ressources . . . . . . . . . 2.2.2 Notion d’efficacité (efficiency) . . . . . . 2.2.3 Notion d’équité (fairness) . . . . . . . .

24 24 24 24 25 25

i

Débit . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

2.2.4 Goulot d’étranglement . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.5 Produit délai-bande passante (BDP, Bandwidth Delay Product) 27 2.2.6 Notion de Congestion . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Nécessité d’un contrôle de Congestion . . . . . . . . . . . . . . . . . . . 29 2.4 Propriétés d’un bon système de contrôle de congestion . . . . . . . . . 29 2.5 Taxonomie des méthodes de contrôle de congestion . . . . . . . . . . . 31 2.5.1 Taxonomie selon le stade d’intervention . . . . . . . . . . . . . . 31 2.5.2 Taxonomie selon la couche du modèle OSI . . . . . . . . . . . . 32 2.5.3 Taxonomie selon la durée de la congestion . . . . . . . . . . . . 33 2.5.4 Taxonomie selon le mécanisme utilisé (fenêtre dynamique versus approche débit dynamique) . . . . . . . . . . . . . . . . . . . . 34 2.5.5 Taxonomie selon la boucle utilisée (boucle fermée versus boucle ouverte) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.5.6 Taxonomie selon la logique d’intervention (bout en bout versus noeud par noeud) . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.6 Principe du contrôle de congestion dans les réseaux à commutation de paquets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6.1 Détection de la congestion . . . . . . . . . . . . . . . . . . . . . 38 2.6.2 Communication de l’information de congestion . . . . . . . . . . 39 2.6.3 Actions prises par un commutateur . . . . . . . . . . . . . . . . 39 2.6.4 Contrôle de flux du côté des sources . . . . . . . . . . . . . . . . 39 2.6.5 Coopération entre les différents acteurs . . . . . . . . . . . . . . 40 2.7 Contrôle de Congestion dans DECBit . . . . . . . . . . . . . . . . . . . 40 2.8 Contrôle de congestion dans Internet . . . . . . . . . . . . . . . . . . . 42 2.8.1 Effondrement de Congestion (Congestion Collapse) . . . . . . . 43 2.8.2 Contrôle de Congestion dans TCP . . . . . . . . . . . . . . . . . 44 2.9 Améliorations pour TCP dans les réseaux haut débit . . . . . . . . . . 45 2.10 Contrôle de congestion dans les réseaux haut débit . . . . . . . . . . . 45 2.10.1 Mythes non fondés . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.10.2 Difficultés supplémentaires . . . . . . . . . . . . . . . . . . . . . 47 2.11 Contrôle de Congestion dans ATM . . . . . . . . . . . . . . . . . . . . 48 2.11.1 Fonction de Contrôle d’admission (Call Admission Control ) . . 48 2.11.1.1 Problème de la bande passante équivalente . . . . . . . 49 2.11.1.2 Contrôle d’admission basé sur les paramètres de la connexion 49 2.11.1.3 Contrôle d’admission basé sur les mesures . . . . . . . 50 2.11.1.4 Contrôle d’admission basé sur la bande et la capacité du buffer . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.11.2 Fonction de Contrôle des paramètres de l’utilisateur (UPC, User Parameter Control ) . . . . . . . . . . . . . . . . . . . . . . . . . 50 ii

2.11.3 Canalisation du trafic (traffic shaping) . . . . . . . . . . . . . 2.11.4 Gestion Passive de la file d’attente . . . . . . . . . . . . . . . 2.11.4.1 La méthode Drop Tail . . . . . . . . . . . . . . . . . 2.11.4.2 la méthode Drop from Front . . . . . . . . . . . . . . 2.11.5 Contrôle de flux pour la classe ABR (Available Bit Rate) . . . 2.11.6 Réservation rapide de ressources (Fast Resource Management) 2.12 Ingénierie de trafic et contrôle de congestion dans MPLS . . . . . . . 2.13 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Evaluation de Performances des Réseaux ATM 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Les deux étapes de l’évaluation de performances . . . . . . . . . 3.2.1 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Résolution . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Taxonomie des méthodes d’évaluation de performances . . . . . 3.3.1 Les mesures . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Méthodes analytiques . . . . . . . . . . . . . . . . . . . . 3.3.3 La simulation . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Chaînes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Systèmes de Files d’Attente . . . . . . . . . . . . . . . . . . . . 3.5.1 Notation de Kendall . . . . . . . . . . . . . . . . . . . . 3.5.2 Mesures de performance . . . . . . . . . . . . . . . . . . 3.6 Simulation à évènemets discrets . . . . . . . . . . . . . . . . . . 3.6.1 Notions élémentaires . . . . . . . . . . . . . . . . . . . . 3.6.2 Génération des nombres aléatoires . . . . . . . . . . . . . 3.6.3 Validation du générateur aléatoire . . . . . . . . . . . . . 3.6.4 Analyse de Convergence des processus simulés . . . . . . 3.6.5 Méthode des réplications indépendantes . . . . . . . . . 3.6.6 Calcul des intervalles de confiance (confidence intervals) 3.7 Quelques outils pour l’évaluation de performances . . . . . . . . 3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Etude de deux algorithmes de contrôle d’admission 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Définitions et notations élémentaires . . . . . . . . 4.2 Vue hiérarchique du trafic . . . . . . . . . . . . . . . . . . 4.3 Contrôle d’admission basé sur une analyse M/D/1 . . . . . 4.3.1 Algorithme de CAC basé sur une analyse N.D/D/1 4.3.2 Etude analytique . . . . . . . . . . . . . . . . . . . 4.4 Analyse N.D/D/1 au niveau cellule . . . . . . . . . . . . . iii

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . .

51 52 52 53 53 54 55 57

. . . . . . . . . . . . . . . . . . . . .

58 58 59 59 60 61 61 62 62 63 65 65 67 67 67 68 68 68 69 69 70 71

. . . . . . .

72 72 72 73 74 77 77 78

4.5

4.4.1 Multiplexage du trafic CBR de N sources . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78 80

5 Résultats et Discussions 81 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 Environnement de simulation . . . . . . . . . . . . . . . . . . . . . . . 81 5.2.1 Environnement de programmation . . . . . . . . . . . . . . . . . 81 5.2.2 Génération de nombre aléatoires dans avec la fonction rand() . . 82 5.2.3 Génération des arrivées selon une loi exponentielle . . . . . . . . 82 5.3 Résultats analytiques et résultats de simulation pour le modèle M/D/1 82 5.4 Résultats de la simulation de la file d’attente N.D/D/1 . . . . . . . . . 85 5.5 Exemple de calcul du gain statistique . . . . . . . . . . . . . . . . . . . 87 5.5.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Conclusion Générale et Perspectives Références Bibliographiques

92 99

Glossaire des Abréviations

101

iv

Liste des tableaux 1.1 1.2 1.3 1.4

Comparaison des trois classes de réseaux WAN, MAN et LAN . . . . . Comparaison entre commutation de circuits et commutation de paquets Paramètres de Qualité de Service dans ATM . . . . . . . . . . . . . . . Classes de service dans ATM . . . . . . . . . . . . . . . . . . . . . . . .

5 9 19 21

2.1 2.2

Politiques pouvant influer sur la congestion . . . . . . . . . . . . . . . . Comparaison entre le contrôle par fenêtre et le contrôle par débit . . .

32 34

3.1

Comparaison des trois classes de méthodes d’évaluation de performances 64

4.1 4.2

Notations élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . Table de Recherche pour un système M/D/1 : Charge admissible en fonction de la capacité du buffer et de CLP. . . . . . . . . . . . . . . .

5.1 5.2

Charge admissible en fonction de la taille du buffer pour l’analyse M/D/1 pour CLP=10−2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gain statistique pour différentes connexions . . . . . . . . . . . . . . .

v

73 76

85 87

Table des figures 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10

Architecture générale d’un réseau. . . . . . . . . . . . . . . . Réseau à commutation de circuits . . . . . . . . . . . . . . . Réseau à commutation de paquets . . . . . . . . . . . . . . . Transport séparé de données . . . . . . . . . . . . . . . . . . Accès intégré au Réseau RNIS Bande Etroite . . . . . . . . . Illustation du principe du multiplexage statistique . . . . . . Mode de transfert synchrone et mode de transfert asynchrone Format d’une cellule ATM . . . . . . . . . . . . . . . . . . . Division de la capacité d’un conduit de trasmission . . . . . Processus d’acheminement de paquets dans MPLS . . . . . .

. . . . . . . . . .

6 7 8 10 11 13 15 16 17 23

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14

Facteurs causant la congestion dans un noeud . . . . . . . . . . . . . . Variation du débit et du délai en fonction du trafic offert. . . . . . . . . Méthodes de contrôle de congestion en fonction de la durée. . . . . . . . Forward Explicit Congestion Notification. . . . . . . . . . . . . . . . . . Backward Explicit Congestion Notification. . . . . . . . . . . . . . . . . Principe de l’algorithme DECBit. . . . . . . . . . . . . . . . . . . . . . Cycles de régénération dans DECBit. . . . . . . . . . . . . . . . . . . . Exemple de topologie du réseau. . . . . . . . . . . . . . . . . . . . . . . L’introduction d’une laison à haut débit n’a fait qu’aggraver la situation. Principe du contrôle d’admission . . . . . . . . . . . . . . . . . . . . . Principe du seau percé (leaky bucket) . . . . . . . . . . . . . . . . . . . Principe du seau percé à jetons . . . . . . . . . . . . . . . . . . . . . . Congestion due au choix du plus court chemin. . . . . . . . . . . . . . . Solution au problème de congestion par ingénierie du trafic. . . . . . . .

27 28 33 36 36 40 41 44 47 48 51 52 55 56

3.1 3.2 3.3 3.4 3.5

Processus de modélisation . . . . . . . . . . . . . . Illustration des Critères de Performance. . . . . . . Diagramme de transition d’une chaine de Markov. . Système de File d’Attente. . . . . . . . . . . . . . . Un réseau de Pétri à deux places et deux transitions

59 60 65 66 70

vi

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . .

. . . . . . . . . . . . .

. . . . .

. . . . .

. . . . . . . . . .

. . . . .

. . . . . . . . . .

. . . . .

. . . . . . . . . .

. . . . .

. . . . .

4.1 4.2 4.3

Les trois niveaux d’observation du trafic . . . . . . . . . . . . . . . . . . Modèle N.D/D/1 de contrôle d’admission au niveau cellule (ici N=4) . Multiplexage de 3 sources CBR . . . . . . . . . . . . . . . . . . . . . .

5.1

Charge admissible en fonction de la taille du tampon (Résulats exacts pour le modèe M/D/1). . . . . . . . . . . . . . . . . . . . . . . . . . . . Charge admissible en fonction de la taille du tampon (Résulats d’approximation pour le modèe M/D/1)). . . . . . . . . . . . . . . . . . . . Charge admissible en fonction de la taille du tampon (Résultats analytiques et résultats de simulation pour un CLP égale à 10−2 ). . . . . . . Nombre de connexions admises en fonction de la taille du tampon de sortie pour une charge de 100% (modèle N.D/D/1). . . . . . . . . . . .

5.2 5.3 5.4

vii

73 79 80

83 84 84 86

Résumé Dans un système à partage de ressources, la congestion est présente lorsque la demande en ressources dépasse la quantité des ressources diponibles. Contrairement à ce que l’on s’attendait, les technologies à haut débit n’ont fait qu’aggraver la congestion. Par conséquent, il faut concevoir de nouveaux protocoles de contrôle de congestion qui soient approporiés aux caractéristiques de tels réseaux. Le contrôle de congestion consiste à maintenir le système en dessous du seuil de congestion, tout en optimisant l’utilisation des ressources par multiplexage statistique. Il est généralement réalisé par plusieurs moyens préventifs et réactifs. Les premiers visent à rendre l’apparition de ce phénomène exceptionnelle alors que les derniers permettent de revenir à une situation normale lorsque, malgré tout, la congestion se produit. Cette deuxième classe de méthodes est très utilisée dans les réseaux ATM afin de garantir la qualité de service (QoS) des connexions déja admises. L’objectif de ce travail est de faire une synthèse sur les méthodes de contrôle de congestion dans les réseaux haut débit. Par la suite, nous étudierons de façon plus détaillée deux algorithmes de contrôle d’admission (CAC) comme exemples de contrôle préventif dans les réseaux ATM. Mots clés : réseaux à haut débit, congestion, mode de transfert asynchrone, qualité de service, évaluation de performance, simulation à évènements discrets, contrôle d’admission. Abstract In a system with resource sharing, congestion is present when the demand for resources exceeds the quantity of available resources. Unexpectedly, new broadband technologies did nothing but worsen the congestion. Consequently, it is necessary to conceive new congestion control protocols which are appropriate to the characteristics of such networks. Congestion control consists in maintaining the system in lower part of the threshold of congestion, while optimizing the use of the resources by statistical multiplexing. It is generally carried out by several preventive and reactive means. The first aim to return the appearance of this phenomenon exceptional whereas the last make it possible to return to a normal situation when, despite everything, congestion occurs. This second class of methods is very used in ATM networks in order to guarantee quality of service (QoS) of already established connections. The aim of this thesis is to make a synthesis on the methods of congestion control in high speed networks. Thereafter, we will study in a more detailed way two algorithms of control admission (CAC) like examples of preventive control in ATM networks. . Keywords : high speed networks, congestion, asynchronous transfer mode, quality of service, performance evaluation, discrete event simulation, admission control.

"Verba volant, scripta manent" Proverbe latin

Introduction Générale

L

ES progrès significatifs réalisés ces dernières années dans le domaine des réseaux de communication de données et de télécommuinications ont changé radicalement notre façon de vivre et d’interagir. D’une première vue, ces réseaux peuvent être divisés selon le type de commutation utilisé en deux grandes classes : réseaux à commutation de circuits et réseaux à commutation de paquets. Les réseaux à commutation de circuits, très répandus dans le domaine des télécommunications, sont très adéquats pour le transfert de la voix ; alors que les réseaux à commutation de paquets conçus par les constructeurs du matériel informatique sont destinés au transfert de données informatiques (fichiers, images, etc). Le besoin accru en applications multimédias d’une part, et le rapprochement des télécommunications et de l’informatique ont donné naissance au RNIS-BE (Réseau Numérique à Intégration de Services, Bande Etroite). Si ce dernier, connu aussi sous le nom du RNIS de première génération a connu un grand succès lors de son apparition, il n’en est pas autant lors de l’avènement du multimédia . Ainsi, les experts de l’UIT (Union International de Télécommunications) pensèrent au RNIS-LB (RNIS à Large Bande) ou RNIS de deuxième génération. Après de longs débats, le mode de transfert asynchrone (ATM, Asynchronous Transfer Mode) a été adopté au détriment du mode de transfert synchrone (STM, Synchronous Transfer Mode). ATM est une technologie orientée connexion ; c’est à dire, elle établit un circuit virtuel entre deux entités communicantes avant que celles-ci puissent envoyer leurs données sous forme de paquets de taille fixe appelés cellules. Les réseaux ATM permettent de supporter un grand éventail de services ayant des exigences en qualité de service différentes. Avec la standardisation par l’UIT (Union Internationale des Télécommunications) de ATM pour le RNIS-LB, une nouvelle technique de commutation a vu le jour : la commutation de cellules. Cette nouvelle technique tire profit de la flexibilité de la commutation de paquets et de la souplesse de la commutation de circuits. Cependant, un réseau ATM comme tout réseau à commutation de paquets souffre du problème de congestion. Celle-ci peut gravement affecter la qualité de service (QoS, Quality of Service) des usagers. Elle peut même causer un effondrement de congestion (congestion collapse), situation dans laquelle le réseau est totalement "paralysé". A cet 1

Introduction Générale effet, des méthodes de contrôle de congestion ont été définies. Ces méthodes peuvent être classifiées selon plusieurs critères. Selon le stade d’intervention, nous avons trois classes : méthodes réactives, méthodes préventives (appelées aussi méthodes proactives) et méthodes hybrides. Bien que les méthodes réactives ont fait leur preuve dans l’Internet, nous allons voir que sans l’ajonction d’autres mécanismes préventifs, elles sont inefficaces pour les réseaux ATM. Ainsi, et pour permettre de garantir une qualité de service pour les abonnés des réseaux ATM, les organismes de normalisation de l’ATM tels que l’ATM Forum et l’UIT préconisent l’utilisation d’un contrôle préventif aux interfaces usager-réseau (UNI, User Network Interface) ainsi qu’aux interfaces réseau-réseau (NNI,Network to Network Interface). L’exemple le plus connu d’un tel contrôle est sans doute la fonction de contrôle d’admission (CAC, Call Admission Control ). Ceci ne veut nullement dire qu’il faut rejeter de façon définitive le contrôle flux de bout en bout effectué dans une grande partie par le protocole TCP (Transmission Control Protocol ) mais, bien au contraire, il faut améliorer les performances de celui-ci qui a toutes les chances de rester prépondérant même dans les réseaux ayant un produit délai-bande passante (BDP, Bandwidth Delay Product) très grand.

Organisation du mémoire Ce mémoire est consacré au contrôle de congestion dans les réseaux à haut débit1 . A cet effet, nous l’avons scindé en cinq chapitres : Dans le chapitre 1, nous rappelons quelques notions fondamentales dans le domaine des réseaux. Par la suite, nous introduisons quelques technologies nécessaires pour supporter les hauts débits notamment pour les réseaux à grande distance (WAN, Wide Area Networks) : Relais de Trames, ATM et MPLS. Un intérêt particulier sera accordé à ATM, du fait qu’il fut adopté comme standard pour le RNIS-LB. Par la suite, nous introquisonq la notion de qualité de service (QoS, Quality of Service) ainsi que les paramètres et les classes de qualité de service dans les réseaux ATM. Le chapitre 2 introduit la notion de congestion dans les réseaux à commutation de paquets ainsi que la notion d’effondrement de congestion. Nous définissons d’abord la notion de congestion et ses symptômes pour un réseau. Par la suite, nous verrons comment le contrôle de congestion est plus ardu à résoudre dans les réseaux haut débit. Nous montrerons également qu’aucune technologie matérielle actuelle ne peut régler le problème de congestion de façon définitive sans l’ajonction de bon protocoles de contrôle de congestion. Ce chapitre étudie aussi quelques algorithmes de contrôle de congestion qui ont été proposés dans la littérature pour le contrôle de congestion dans ATM, et aborde très brièvement l’ingénierie de trafic dans MPLS . 1

Notons que dans ce mémoire, nous utiliserons les expressions réseaux à haut débit et réseaux haut débit de façon interchangeable.

2

Introduction Générale

Le chapitre 3 traite de l’évaluation de performances des réseaux ATM. Nous y présenterons les trois classes de méthodes d’évaluation de performances, à savoir : les méthodes analytiques, les mesures, et la simulation. Nous accordons un grand intérêt aux systèmes de files d’attente et à la simulation à évènements discrets. A cet effet, ce chapitre introduit des notions élémentaires manipulées pour faire une simulation à évènements discrets : notion d’état, évènements,génération de nombre aléatoire, valisation des résultats de la simualtion, etc. Dans le chapitre 4, nous présenterons deux algorithmes de contrôle d’admission (CAC). Le premier d’entre eux est basé sur une analyse M/D/1 et le deuxième sur une analyse N.D/D/1. Nous expliquerons le principe de chacun des deux algorithmes et nous verrons comment ces deux algorithmes procèdent pour accepter ou rejeter une nouvelle connexion. Le chapitre 5 est consacré à la présentation des résultats des simulations ainsi qu’à la discussion des résultats. Nous terminerons notre mémoire par une conclusion générale et nous énoncerons des prespectives de recherche.

3

Chapitre

1

Panorama des Réseaux Haut Débit

"There is much more to life than increasing its speed." Mahatma Ghandi

1.1

Introduction

H

ISTORIQUEMENT, le Réseau Téléphonique Commuté (RTC) était le premier réseau existant. L’avènement de nouvelles applications telles que la vidéoconférence , l’AoD (Audio on Demand ) et la VoD (Video On Demand ) a, non seulement, engendré un besoin de débit plus important, mais a introduit également des contraintes temporelles strictes dans les échanges de d’informations. Ce n’est que par une réponse architecture et réseau spécifiques : Réseaux Large Bande à Intégration de Services (RNIS-LB) qu’une solution globale à ces nouvelles exigences et contraintes peut être trouvée. Ce chapitre est consacré à quelques rappels sur les réseaux ainsi qu’à la présentation de trois technologies à haut débit pour les réseaux à grande distance (WAN, Wide Area Networks), à savoir : le Relais de Trames (Frame Relay), ATM (Asynchronous Transfer Mode) et MPLS (MultiProtocol Label Switching). Nous accorderons un intérêt particulier à la technologie ATM du fait que celle-ci a été choisie par l’UIT(Union Internationale des Télécommunications)1 comme standard pour le RNIS-LB.

1.2

Taxonomie des réseaux informatiques

Il n’y a pas de classification universellement admise des réseaux informatiques. En revanche, tout le monde reconnaît l’importance de trois caractéristiques : la technique de commutation utilisée, la topologie du réseau et la taille de celui-ci.

1

En anglais : ITU (Internationale Telecommunication Union)

4

Chapitre 1 : Panorama des réseaux haut débit

Réseau (WAN)

Réseau Fédérateur (MAN)

Réseau (LAN)

quelques milliers de kilomètres

de 1 m à 100 km

de 1 m à 2 km

Nombre d’abonnés

plusieurs millions

de 2 à 1000

de 2 à 200

Opérateur

différent des utilisateurs

regroupement d’utilisateurs

l’utilisateur même

Facturation

volume et durée

forfait

gratuit

Débit

de 50 bit/s à 2 Mbit/s

de 1 à 100 Mbit/s

de 1 à 100 Mbit/s

taux d’erreurs

de 10−3 à 10−6

inférieur à 10−9

inférieur à 10−9

Délai

inférieur à 0.5 s

de 10 ms à 100 ms

de 1 à 100 ms

Taille phique

géogra-

Public

Local

lui-

Tab. 1.1 – Comparaison des trois classes de réseaux WAN, MAN et LAN

1.2.1

Taxonomie selon la distance

Les réseaux peuvent être divisés en plusieurs catégories, dont les frontières sont plus ou moins floues, suivant les distances couvertes par ceux-ci [92], [95]. La terminolgie anglaise les désigne sous le nom de WAN (Local Area Networks), MAN (Metropolitan Area Networks) et LAN (Local Area Networks). En français, on les désigne respectivement sous les noms de réseaux publics, réseaux fédérateurs et réseaux locaux. Un réseau public ou réseau longue distance ou encore WAN est un réseau qui couvre une zone géographique importante (un pays, voire un continent) et comporte un ensemble d’ordinateurs qui exécutent des programmes utilisateurs. Les utilisateurs n’ont pas de contrôle ni sur la conception du réseau ni sur son administration ; ils utilisent les services offerts par celui-ci et payent pour le trafic induit. Un réseau métropolitain ou MAN couvre généralement un grand campus ou une ville (d’où son nom) et peut être public aussi bien que privé [91]. Les réseaux locaux appelés aussi ou encore RLE (Réseaux Locaux d’Entreprise), sont des réseaux dont la taille ne dépasse pas quelques kilomètres. Les caractéristiques des ces trois types de réseaux sont résumées dans le tableau 1.1.

1.2.2

Taxonomie en fonction de la topologie

Différentes topologies, c’est à dire formes de réseaux, peuvent aussi servir à classer les types de réseaux. Chaque topologie possède ses forces et ses faiblesses. A chaque topologie sont associés des modes d’accès au support physique. On trouve généralement trois topologies fréquentes notamment pour les réseaux locaux : topologie en bus, 5

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.1 – Architecture générale d’un réseau. topologie en anneau, et topologie en étoile [92]. Sur un réseau de type bus, il n’y a à chaque instant qu’un seule machnine qui est autorisée à transmettre ses données. Toutes les autres doivent s’abstenir d’émettre. Par conséquent, il est nécessaire d’avoir un mécanisme d’arbitrage qui puisse résoudre les conflits survenants lorsque deux machines ou plus veulent simultanément émettre. Sur une topologie en anneau, chaque bit se propage de façon autonome, sans attendre le reste du paquet auquel il appartient. Dans le cas d’une topologie en étoile, le site central (généralement un hub) reçoit et envoie tous les messages, le fonctionnement est simple, mais la panne du noeud central paralyse tout le réseau.

1.2.3

Taxonomie en fonction du mode de commutation

La périphérie d’un réseau est constituée de commutateurs d’accès qui regroupent plusieurs abonnés et qui assurent également un rôle de multiplexeur, tandis que les noeuds internes du réseau commutent les communications entre un lien d’entrée vers un lien de sortie en fonction d’un critère d’acheminement (Fig. 1.1). Un mode de transfert est une technique, ou un ensemble de techniques, utilisée dans un réseau de télécommunication couvrant des aspects liés à la transmission, la commutation et le multiplexage [34]. La commutation est née de la nécessité de mettre en relation un utilisateur avec n’importe quel autre utilisateur (interconnexion totale) et de l’impossibilité de créer autant de liaisons directes. Deux techniques de commutation dominent dans les grands réseaux : la commutation de circuits (principalement dans le système

6

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.2 – Réseau à commutation de circuits téléphonique) et la commutation par paquets (essentiellement pour les réseaux à transmission de données tels que X.25). Selon la commutation, les réseaux peuvent être divisés en deux classes, à savoir : les réseaux à commutation de circuits et ceux à commutation de paquets. 1.2.3.1

Réseaux à commutation de circuits

Dans un réseau à commutation de circuits (circuit-switching network ), un chemin destiné à la communication est établi entre deux stations à travers les noeuds du réseau. Ce chemin est une séquence connectée de liens physiques entre les différents noeuds du réseau. Sur chaque lien, un canal logique est dédié à la connexion. Les données générées par la source sont transmises au long du chemin dédié le plus rapidement possible. A chaque noeud, les données entrantes sont routées ou commutées à la sortie appropriée. L’exemple le plus connu des réseaux à commutation de circuits est le Réseau Téléphonique Commuté (RTC). La communication de données en utilisant la commutation de circuits requiert trois phases, à savoir : l’établissement du circuit entre la source et la destination, le transfert de données entre les deux stations et enfin, la fermeture du circuit. Une caractéristique très importante de ce type de commutation est le fait qu’il n’y pas de stockage intermédiaire. 1.2.3.2

Réseaux à commutation de paquets

Une approche très différente est utilisée dans les réseaux à commutation de paquets (packet-switching networks). Dans ce cas, les données sont plutôt transmises vers les sorties en une séquence de paquets. Chaque paquet est transmis à travers le réseau d’un noeud à un autre en passant par un chemin menant de la source à la destination. A chaque noeud, le paquet entier est reçu, stocké pour une courte durée, puis retransmis vers le noeud suivant. Des applications typiques de la commutation de paquets incluent le transfert électronique de fonds, l’approbation des cartes de crédit, le transfert des fichiers de petite taille et l’envoi du courrier électronique. Les paquets sont envoyés de la source à la destination à travers des ressources partagées en utilisant le multiplexage 7

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.3 – Réseau à commutation de paquets statistique par division du temps. Un exemple typique des réseaux à commutation de paquet est le réseau X.25. La commutation de circuits et la commutation par paquets présentent certaines différences. La différence majeure est que la commutation de circuits réserve statiquement et à priori un circuit et ainsi que intégralité de sa bande passante pour une communication. Contrairement au réseaux à commutation de circuits, les noeuds d’un réseau à commutation de paquets sont appelés "store-and-forward " car il ont des tampons de stockage qui leur permettenet de stocker (store) temporairement les paquets dans le but de les acheminer (forward ) plus tard. La possibilité de stockage dans les noeuds de commutation sous-entend que le multiplexage statistique doit être supporté par les liens reliant ces noeuds. Le tableau 1.2 fait une étude comparative entre ces deux techniques de commutation. Les réseaux à commutation de paquets à leur tour peuvent être divisés en deux classes, à savoir : les réseaux à datagrammes et réseaux à circuit virtuel. Dans un réseau à datagrammes, les paquets provenant d’une même connexion peuvent ne pas suivre le même chemin. Par contre, dans les réseaux à circuit virtuel, les paquets suivent le même chemin. La commutation rapide de paquets (fast packet switching) est née du mariage de la commutation de paquets et de la transmission de données à hauts débits Il existe une autre technique de commutation appelée commutation de cellules qui combine la simplicité de la commutation de circuits et la flexibilité de la commutation de paquets. Cette technique représente une rupture gigantesque avec la tradition centenaire de commutation de circuits (établissement d’un circuit physique) du réseau téléphonique. Ce choix est motivé par plusieurs raisons. D’abord, la commutation de cellules est très souple et s’accomode à la fois des débits constants (audio, vidéo) et des débits variables (données). D’autre part, aux très hauts débits envisagés (gigabits par seconde) la commutation de cellules est plus simple à réaliser que les techniques de multiplexage traditionnelles, en particlier pour les fibres optiques. Enfin, pour la télédistribution, la diffusion est essentielle : c’est une caractéristique essentielle que peut fournir la commutation de cellules mais pas la commutation de circuits [92]. 8

Chapitre 1 : Panorama des réseaux haut débit

Type de Commutation Circuits

Paquets

Circuit dédié

oui

non

Bande passante diponible

fixe

dynamique

Gaspillage potentiel de la bande passante

oui

non

Transmission and forward

Store

non

oui

Chaque paquets suit la même route

oui

oui ou non (selon le réseau)

Etablissement d’un circuit par séquence d’appels

oui

oui ou non (selon le réseau)

Quand peut apparaître la congestion

à l’établissement du circuit

à chaque paquet transmis

Principe de la facturation

à la distance et à la durée

au volume d’informations transmises

Tab. 1.2 – Comparaison entre commutation de circuits et commutation de paquets

1.3 1.3.1

Les réseaux à haut débit Motivation

Depuis plus d’un siècle, le réseau téléphonique constitue l’infrastructure principale de télécommunications. Ce réseau conçu pour la transmission analogique de la voix, est inadapté aux besoins des communications modernes. Anticipant sur l’importante demande exprimée par les utilisateurs pour les services de communications numériques de bout en bout, les opérateurs de télécommunications internationaux se sont réunis sous les auspices de l’UIT pour mener des études devant donner naissance à un seul réseau pour le transport de la voix, des images, de la vidéo et des données. Ce nouveau système avait pour nom Réseau Numérique à Intégration de Services ou RNIS (ISDN, Integrated Services Digital Network ). La motivation majeure du RNIS était l’offre de nouveaux services de communication. Néanmoins, il est important de constater qu’aujourd’hui le transport des signaux vocaux reste une activité importante du RNIS . L’intégration de service a plusieurs avantages : une meilleure utilisation des 9

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.4 – Transport séparé de données ressources, un coût de conception réduit, homogénéité des équipements, etc. Ce RNIS de première génération qu’on appelait quelquefois RNIS-BE (RNIS à bande étroite) ne pouvait pas satisfaire les nouveaux besoins des utilisateurs dont la demande la plus importante était le multimédia et la vidéo à la demande (VoD, Video on Demand ). A cet effet, les experts de l’UIT entamèrent des études sur un nouveau système qui pourrait remédier aux inconvénients du RNIS-BE. Ces études ont conduit au RNIS de deuxième génération que l’on nomme couramment RNIS à large bande (RNIS-LB). Ce dernier est une infrastructure réseau publique capable de supporter les services à bande étroite (narrowband services) et les services large bande (broadband services) sur une seule plateforme flexible, et qui permet au client l’accés à travers une interface unique, ce qui permet de concrétiser le principe du "guichet unique" [34]. La technologie qui rend le RNIS-LB possible est le mode de transfert asynchrone ou ATM (Asynchronous Tansfer Mode). L’idée de base de l’ATM est de transmettre l’information dans de petits paquets de taille fixe : les cellules. Une cellule fait 53 octets : 5 octets d’en-tête et 48 octets de données (voir Fig.1.8). La conception d’un RNIS se base sur un compromis qui doit être établi entre deux composantes principales : qualité de service (QoS, Quality of Service) offerte et le taux d’utilisation des ressources déployées dans le réseau. Pour s’imposer sur le marché, un RNIS Large Bande (RNIS-LB) devra proposer un vaste éventail de services. Ces derniers sont classés dans la recommandation I.211 de l’UIT en deux grandes catégories [47] : – les services dits interactifs représentant les services de conversation, de messagerie et de consultation ; – les services de distribution comprenant les services liés à la diffusion d’information ou d’images. Face à la variété des contraintes en fonction des applications, l’UIT a défini 4 classes d’applications en fonction des critères suivants : 10

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.5 – Accès intégré au Réseau RNIS Bande Etroite – la relation temporelle entre l’émetteur et le récepteur ; les applications seront qualifiées de d’isochrone si une relation temporelle stricte doit être maintenue ou d’asynchrone si aucune relation temporelle n’existe, – le critère de sporadicité : on distingue le trafic à débit constant (CBR, Constant Bit Rate), le critère de sporadicité est alors égal à 1 (ex. : la voix codée MIC), des application à débit variable(VBR, Variable Bit Rate), le critère de sporadicité est alors supérieur à 1, – le mode de mise en relation : cette distinction traditionnelle et télécommunication distingue le mode connecté (ou orienté connexion) du mode non connecté (ou orienté sans connexion). Dans le cas d’un service en mode connecté, l’utilisateur établit au préalable une connexion, l’utilise puis la relâche. En revanche, pour un service en mode non connecté, les ressources physiques ne sont pas réservées. Les services sont dit fiables q’ils n’engendrent pas des pertes de données. Habituellement, la mise en oeuvre d’un service fiable se fait par acquittement (acknowledgement ) de chaque message par le récepteur, de sorte que l’émetteur soit sûr de son arrivée. Cependant, le processus d’acquittement engendre une surcharge du réseau (overhead ) et un délai supplémentaire parfois indésirables.

1.3.2

Définitions d’un réseau haut débit

Un réseau haut débit peut être défini de trois points de vue : celui de l’utilisateur (l’abonné), celui des technologues et enfin celui du concepteur [34]. L’utilisateur attend d’un réseau à haut débit l’offre d’un large spectre de débits avec une fine granularité, des canaux de débits variables adaptés à la sporadicité de certains trafics et des qualités de service. Du point de vue technologique, le terme "haut débit" est lié aux grandes fréquences auxquelles doivent fonctionner les différents équipements 11

Chapitre 1 : Panorama des réseaux haut débit

électroniques et/ou optoélectroniques du réseau (commutateurs, multiplexeurs, etc.) et aux grandes capacités des systèmes de transmission. Du point de vue du concepteur, le haut débit est le débit à partir duquel les algorithmes de partage de ressources des réseaux classiques ne sont pas adaptés et doivent donc être changés. Officiellement, un système large bande est défini selon la recommandation I.113 [49] de l’UIT comme étant : "un système qui demande des canaux de transmission capables de supporter des débits plus grands que ceux fournis par l’accès primaire". Par accès primaire, on voulait dire celui du RNIS de première génération qui avait un débit de 1.544 Mbit/s. Le RNIS-LB offre des interface des connexion à un débit atteignant quelquefois 622 Mbit/s.

1.3.3

Multiplexage statistique dans les réseaux à haut débit

L’économie d’échelle joue un rôle important dans l’industrie des télécommunications. De ce fait, les exploitants de réseaux ont favorisé la mise en place de systèmes très élaborés qui permettent de partager (on dit multiplexer ) entre de nombreux usagers le même support physique de transmission. Le multiplexage a pour but de regrouper plusieurs connexions de transport sur une même connexion de réseau, ce qui va permettre de minimiser les ressources utilisées au niveau réseau, donc de diminuer les coûts de communication. Dans les réseaux classiques, on trouve trois mécanismes principaux qui sont largement utilisés, à savoir : le multiplexage fréquentiel (FDM, Frequency Division Multiplexing), le multiplexage temporel (TDM, Time Division Multiplexing) et le multiplexage en longueur d’onde (WDM, Wavelength Division Multiplexing) [91]. Afin d’introduire la notion de multiplexage statistique utilisé dans les réseaux à haut débit, nous reprendrons l’exemple suivant cité dans [34]. Les trois courbes situées dans la partie inférieure de la figure 1.6 représentent l’évolution du débit de trois sources en fonction du temps. Ces sources ont, respectivement, un débit crête de 3, 2.5, et 3 (l’unité utilisée n’a pas d’importance). Supposons que le réseau dispose d’un conduit de transmission de capacité 5. Si le réseau fait du multiplexage déterministe, c’est à dire, s’il alloue à chaque source son débit crête (débit maximal), une seule connexion peut être acceptée. En effet, on voit bien que la somme des débits crêtes de deux quelconques des sources dépasse la capacité du conduit de transmission. La courbe (S) représente la somme des débits des trois sources en fonction du temps. Ce qui est intéressant à remarquer est le fait que cette somme dépasse rarement la capacité du conduit. Ceci nous incite à penser qu’il serait possible d’accepter les trois connexions, ce qui revient à dire que le réseau alloue à chaque source un débit inférieur à son débit crête. On dit alors que le réseau fait du n P multiplexage statistique. dans ce cas, le total des débits crêtes ( hi ) des connexions se i=1

partageant la même liaison peut dépasser la bande passante (C) de la ligne. Autrement 12

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.6 – Illustation du principe du multiplexage statistique dit :

n X

hi > C

(1.1)

i=1

Où : C : bande passante disponible du lien de sortie ; hi : débit crête de la connexion i ; n : nombre de connexions simultanées sur la ligne. n P Mais le total des débits moyens ( mi ) ne doit pas dépasser la bande passante de la ligne de sortie, c’est à dire :

i=1

n X

mi ≤ C

(1.2)

i=1

Le gain statistique réalisé et qui est noté SMG (Statistical Multiplexing Gain) est défini alors de la façon suivante : C SMG = P n hi

(1.3)

i=1

Le prix à payer est d’associer un identificateur à chaque unité d’information transférée d’une part et de prévoir des buffers capables d’absorber les pics éventuels (au moment où la ligne de sortie ne suit pas) d’autre part.

13

Chapitre 1 : Panorama des réseaux haut débit

1.4

Technologies pour supporter les hauts débits pour les WANs

Pour offrir une bonne qualité de service et satisfaire les besoins des utilisateurs dont le nombre ne cesse d’augmenter, les opérateurs et les concepteurs des réseaux doivent mettre en oeuvre des réseaux très performants et qui permettent de supporter des services qui sont très gourmands en bande passante. Dans cette section, nous présenterons les technologies principales pour supporter les hauts débits dans les réseaux à longue distance (réseaux WAN).

1.4.1

La technologie Relais de Trames (Frame Relay )

Initialement prévue pour une utilisation sur le RNIS, la technologie relais de trames (Frame Relay) a, sous l’égide du Frame Relay Forum, évolué vers un service de liaisons virtuelles permanentes, puis commutées utilisables sur tout support numérique hors RNIS [87], [91]. Parmi les différentes utilisations du Relais de Trames, on peut citer : le transfert de fichiers grand volume, les applications de Conception Assistée par Ordinateur (CAO) ou d’images, le multiplexage de voies basse vitesse en voies haute vitesse, etc. La technologie Frame Relay réduit au strict minimum la charge de travail accomplie par le réseau ; les données de l’usager sont envoyées sans aucun traitement intermédiaire au niveau des noeuds du réseau. Frame Relay est typiquement utilisé comme un service de communication de données privées qui utilise des circuits virtuels et des connections logiques (plutôt que des connections physiques) afin de donner aux usagers l’aspect et la sensation d’un réseau privé. La plupart des réseaux Frame Relay sont publics, ce qui donne aux clients beaucoup de flexibilité et d’avantages économiques, de la même manière que choisir un taxi public est plus flexible et économique que d’acheter une voiture personnelle [38].

1.4.2

La technologie ATM (Asynchronous Transfert Mode)

La technologie ATM (Asynchronous Transfer Mode) était en concurrence avec la technologie STM (Synchronous Transfer Mode) développée par AT&T pour le RNISLB. La différence majeure entre ces deux modes est le fait que dans ATM, les horloges de la source et du réseau ne sont pas corrélées [78]. Le mode de transfert asynchrone , connu aussi sous le nom de relais de cellules 2 (cell relay) est l’aboutissement d’un certain nombre d’évolutions dans les techniques de transfert. Il est similaire en quelque sorte à la commutation de paquets sous X.25 et Frame Relay [91]. Elle constitue un bon compromis des techniques de commutation de circuits (slots et simplicité) et celles 2

Il est appelé ainsi pour le distinguer du Relais de Trames (Frame Relay).

14

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.7 – Mode de transfert synchrone et mode de transfert asynchrone de la commutation de paquets (multiplexage statistique et flexibilité) [81]. Les réseaux basés sur le mode ATM sont caractérisés par : – l’absence de contrôle de flux à l’intérieur du réseau à partir du moment où la communication a été acceptée ; – l’absence de contrôle d’erreurs car d’une part, la transmission sur fibre optique présente une bonne qualité de transmission et d’autre part, détection et reprise diminuent le débit utile ; – un mode orienté connexion pour faciliter la réservation des ressources et assurer le séquencement des cellules ; – l’absence de contrôle de perte au niveau du réseau car des ressources suffisantes ont été allouées aux connexions lors de leurs établissements ; – une unité de transfert appelée cellule, de taille réduite pour faciliter l’allocation mémoire dans les commutateurs et permettre un meilleur entrelacement des flux et une commutation rapide ; – un en-tête de cellule de taille limitée et aux fonctions réduites pour assurer une commutation rapide ; – utilisation du multiplexage statistique. 1.4.2.1

Cellule ATM

L’unité de donnée manipulée dans les réseaux ATM est appelée cellule. La figure 1.8 nous montre la structure de la cellule à l’interface usager-réseau (UNI, User Network Interface) et à l’interface de noeud de réseau (NNI, Node Network Interface). Dans les deux cas, la cellule est composée d’un champ d’information de 48 octets et d’un entête de 5 octets. Les informations utilisateur sont transportées de façon transparente dans le champ d’information. En effet, aucun contrôle d’erreur n’est exercé sur ces 15

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.8 – Format d’une cellule ATM informations dans les différents noeuds du réseau. On se propose de décrire ci-dessous les différents champs de la cellule ATM : • Les champs VPI et VCI Le couple VPI/VCI est appelé champ d’acheminement. Il transporte les informations d’identification du circuit virtuel auquel appartient la cellule. • Le champ PTI Le champ d’identification du type de capacité utile (PTI, Payload Type Identifier ) indique si le champ d’information de la cellule transporte des informations d’usager ou des information de gestion. • Le champ CLP Le champ de priorité de perte de cellule (CLP, Cell Loss Priority) est composé d’un seul bit. Il permet de définir deux niveaux de priorité pour les cellules (CLP = 0 indique la priorité haute). Le bit CLP peut être mis à 1 soit par l’usager, soit par le réseau. Un élément de réseau en état de congestion rejette les cellules en utilisant le champ CLP. • Le champ GFC Comme on le voit, le champ de contrôle de flux générique (GFC, Generic Flow Control ) est défini uniquement à l’UNI. Il est "écrasé" par le premier commutateur qu’il rencontre. Il a été conçu pour servir au contrôle de flux à l’UNI. • Le champ HEC Ce champ est utilisé par la couche physique pour détecter ou corriger des erreurs dans les 4 premiers octets de l’en-tête et réaliser l’alignement de la cellule.

16

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.9 – Division de la capacité d’un conduit de trasmission 1.4.2.2

Les connexions ATM

ATM est une technique orientée connexion. Ceci signifie que tout transfert d’information est composé de trois étapes : l’établissement de la connexion, le transfert de l’information lui même et la fermeture de la connexion. Deux types de connexion sont définis dans les documents de normalisation : les connexions de voie virtuelle (VCC, Virtual Channel Connection) et les connexions de conduit virtuel (VPC, Virtual Path Connection). Elle sont définies comme suit : La capacité de chaque connexion physique est divisée, logiquement, en un certain nombre de liens ATM appelés conduits virtuels (VP, Virtual Path) ou liens de conduit virtuel. Une VPC se compose d’un VP est à la fois divisée logiquement dans un certain nombre de liens ATM appelés voies virtuells (VC, Virtual Channel ) ou liens de voies virtuelle. Une VCC se compse d’un VC ou de la concaténation de plusieurs VC (voir Fig. 1.9). 1.4.2.3

Qualité de Service dans ATM

La notion de qualité de service (QoS, Quality of Service) veut rendre compte, de façon chiffrée, du niveau de performances que l’utilisateur attend du réseau. La signification précise de la notion de Qualité de Service dépend du service envisagé. La Qualité de Service peut être évaluée de plusieurs façons. En général, elle inclut le débit, le délai de bout en bout, les bornes sur les délais, la gigue, le taux de perte. Dans [74], J.L Mélin définit la qualité de service comme étant " la capacité de transporter efficacement le flux de données d’une application tout en satisfaisant les exigences (contraintes) dictées par l’utilisateur (ou l’application)". Les principaux paramètres connus de la qualité de service sont : – Disponibilité : elle est définie comme étant le rapport entre le temps de bon fonctionnement des services et le temps total d’ouverture du service. C’est la forme la plus évidente de QoS puisqu’elle établit la possibilité d’utiliser le réseau ; – Bande passante : c’est la capacité de transmission d’une liaison du réseau me17

Chapitre 1 : Panorama des réseaux haut débit

surée en bits par seconde ; – Latence (délai) : elle correspond au temps que requièrt un paquet pour traverser le réseau d’un point d’entrée a un point de sortie ; – Gigue : elle est définie comme étant la variation des délais d’acheminement (latence) des paquets sur le réseau. Ce paramètre est particulièrement sensible pour les applications multimédia temps réel qui requièrent un délai inter-paquets relativement stable ; – Taux de perte : c’est le rapport entre le nombre d’octets émis et le nombre d’octets reçus. Il s’agit par conséquent de la mesure de la capacité utile de transmission. Une définition officielle de la qualité de service est définie également dans la recommandation E.800 de l’UIT [48] : "La qualité de service correspond à l’effet général de la performance d’un service qui détermine le dégré de satisfaction d’un utilisateur de service." Chaque application peut avoir des besoins spécifiques. Part exemple, garantir une borne sur le délai de transmission des paquets peut être profitable aux applications de téléphonie ; garantir un débit peut être nécessaire pour des applications vidéo à la demande (VoD), etc. Dans ce qui suit, nous présentons les paramètres pertinents de qualité de service concernant les réseaux ATM. 1.4.2.4

Paramètres de qualité de service dans les réseaux ATM

Lorsqu’un circuit virtuel est établi, la couche transport (un processus client sur un ordinateur) et la couche ATM (un processus interne au réseau ATM) doivent conclure un contrat spécifiant la classe de service associée au circuit virtuel ; une étape de négociation est alors entreprise. Le contrat entre le client et l’opérateur comporte généralement trois parties : le trafic susceptible d’être offert ;le service accepté d’un commun accord et enfin les conditions de conformité requises. La première partie du contrat s’appelle descripteur de trafic. Celui-ci caractérise la charge de trafic qui peut être assuré. La seconde partie spécifie la qualité de service souhaitée par l’usager et acceptée par le réseau. Pouir réaliser un contrat de service, le standard ATM a défini un certain nombre de paramètres de qualité de service dont les valeurs peuvent faire l’objet de négociation entre l’usager et le réseau [34], [91], [92]. Le tableau 1.3 résume les paramètres de qualité de service les plus importants dans les réseaux ATM. Les trois premiers paramètres spécifient à quel débit l’usager souhaite pratiquer la transmission de ses cellules : • PCR (Peak Cell Rate) : indique le débit crête de la source. Autrement dit,la valeur maximale du débit envisagé. Le PCR est l’inverse du délai minimal entre l’arrivée de deux-cellules. • SCR (Sustained Cell Rate) : correspond à la valeur moyenne du débit envisagé sur un long intervalle de temps. Pour un trafic de type CBR (Constant Bit Rate) la 18

Chapitre 1 : Panorama des réseaux haut débit

Signification

Paramètre PCR (Peak Cell Rate)

Débit de transmission maximum

SCR (Sustained Cell Rate)

Débit pratiqué sur une longue période de temps

MCR (Minimum Cell Rate)

Débit minimum acceptable

CDVT (Cell Delay Variation Tolerance)

Variation de délai toléré (gigue maximale acceptée)

CLR (Cell Loss Ratio)

Taux de cellules perdues ou arrivées trop tardivement

CTD (Cell Transfer Delay)

Temps d’acheminement (moyen et maximum)

CDV (Cell Delay Variation)

Variance du délai d’acheminement

CER (Cell Error Ratio)

Taux d’erreur (nombre de cellules délivrées sans erreur)

CMR (Cell Misinsertion Rate)

Taux de cellules arrivées à une mauvaise destination

des

cellules

Tab. 1.3 – Paramètres de Qualité de Service dans ATM valeur de SCR est égale à celle du PCR. D’autre part, le rapport PCR/SCR donne une mesure variabilité du trafic (trafic burstiness). • MCR (Minimum Cell Rate) : correspond au débit minimum acceptable par l’utilisateur. En effet, si le réseau n’est pas capable de satisfaire ce minum, l’usager rejette la connexion.

Le quatrième paramètre est un paramètre essentiel pour les applications temps réel : • CVDT (Cell Variation Delay Tolerance ) : ce paramètre exprime la variation admissible du temps de transmission des cellules. Autrement dit, il représente la gigue (jitter ) acceptable. Les trois paramètres suivants donnent les caractéristiques du réseau et qui sont mesurées et vérifiées par le récepteur. Les trois font l’objet de négociations : • CLR (Cell Loss Ratio) : exprime le pourcentage de cellules transmises qui ne sont pas arrivées à destination, ou le pourcentage de cellules arrivées en retard (notamment dans le cas d’un trafic temps réel). Par exemple, une application de vidéoconférence doit avoir un CLR inférieur ou égal à 10−11 . • CTD (Cell Transfer Delay ) : exprime le temps moyen de transit des cellules 19

Chapitre 1 : Panorama des réseaux haut débit

entre la source et la destination. • CDV (Cell Delay Variation) : mesure la variance admissible du temps d’acheminement des cellules au destinataire. Les deux derniers paramètres de QoS spécifient des caractéristiques propres au réseau : • CER (Cell Error ratio) : mesure le nombre moyen de cellules arrivant à destination avec au moins un bit erroné. • CMR (Cell Misinsertion ratio) : mesure le nombre moyen de cellules/seconde qui sont remises à une mauvaise destination par suite d’une erreur non détectée dans leur en-tête. 1.4.2.5

Classes de services dans ATM

Lorsqu’une connexion est établie, elle résulte d’une négociation entre l’usager et le réseau qui stipule la classe de transfert retenue. L’ATM-Forum a organisé les services offerts par les réseaux ATM en cinq catégories (voir 1.3) : 1. La classe CBR (Constant Bit Rate) : La classe CBR définit une transmission à débit constant. La connexion est équivalente à un circuit téléphonique ; cela revient à émuler un support de transmission (un câble électrique ou une fibre optique). Cette classe est importante dans ATM. Elle permet d’écouler un flux de données temps réel ou interactif, comme le trafic téléphonique, l’audio ou la vidéo. 2. La classe RT-VBR (Real Time Variable Bit Rate) : la classe RT-VBR est spécifique aux services qui ont un service variable combiné à des exigences de temps réel importantes, par exemple la vidéo comprimée (comme la vidéoconférence) ou l’échange d’images codées MPEG (Moving Picture Expert Group). Poue cette classe de trafic, le réseau ATM doit contrôler le temps moyen d’acheminement des cellules et ainsi que la variation moyenne du délai d’acheminement des cellules. 3. La classe NRT-VBR (Non Real Time Variable Bit Rate) : la classe NRTVBR est destinée au trafic non temps réel où l’instant de remise est important, même si les applications concernées tolèrent une certaine gigue. Comme exemple, on peut citer le transfert d’un document multimédia. 4. La classe ABR (Available Bit Rate) : la classe ABR définit un débit possible. Cette classe permet d’écouler du trafic sporadique dont la bande passante (ou le débit) nécessaire est difficilement prévisible. 5. La classe UBR (Unspecified Bit Rate) : la classe UBR ne définit aucun débit et ne délivre pas non plus d’information de retour en cas de congestion. 20

Chapitre 1 : Panorama des réseaux haut débit

Classe

Description

Exemple

Débit constant garanti

Téléphone

RT-VBR

Débit variable : trafic temps réel

Vidéoconférence en temps réel

NRT-VBR

Débit variable : trafic non temps réel

Transfert d’un document multimédia

ABR

Débit possible

Surf sur le Web

UBR

Débit non spécifié

Transfert de fichier en tâche de fond

CBR

Tab. 1.4 – Classes de service dans ATM Cette classe est typique de la transmission de données en mode datagrammes, comme par exemple les datagrammes IP. En effet, un tel service est dit " service au mieux" ou best effort : aucune garantie n’est faite par le réseau pour l’arrivée des paquets à destination. Dans la classe UBR, toutes les cellules envoyées dans le réseau sont acceptées. Si la capacité instantanée du réseau est suffisante les cellules sont transmises sans problème jusqu’à destination. Par contre, en cas de surcharge du réseau, les cellules seront détruites en priorité, sans que les expéditeurs respectifs soient avertis, ni même qu’il leur soit demandé de réduire leur trafic.

1.4.3

La technologie MPLS ( MultiProtocol Label Switching )

Afin de combiner les avantages de la commutation rapide de la technologie ATM et ceux des protocoles efficaces de routage IP tout en évitant les problèmes de "scalabilité", une technique de commutation de labels a été proposée. Cette technique offre un support de la qualité de service au protocole IP et permet un découplage des techniques de routage (routing) et de relayage (forwarding) [68]. Un groupe de travail au sein de l’IETF a été créé dans le but de standardiser cette technique de commutation de labels sous le nom de MPLS (Multi Protocol Label Switching) (voir RFC) MPLS est une technique destinée à répondre à plusieurs problèmes liés à la transmission des paquets dans un environnement d’intéréseau moderne. Cette technologie de pointe a de nombreuses utilisations, que ce soit dans un environnement de fournisseur de services (service provider ) ou dans un réseau d’entreprise. Actuellement, MPLS est surtout déployé pour la mise en place de réseaux virtuels (VPN, Virtual Private Network ). La différence essentielle entre MPLS et les technologies WAN traditionnelles tient à la manière dont les labels sont attribués et à la capacité de transporter une pile de labels attachés à un paquet [79]. 21

Chapitre 1 : Panorama des réseaux haut débit

Avant d’expliquer le principe de commutation de MPLS, nous donnons d’abord les définitions suivantes : • Etiquette (label ) : c’est un entier associé à un paquet lorsqu’il circule dans un réseau MPLS et sur lequel ce dernier s’appuie pour prendre des décisions. • MPLS Ingress node : c’est un routeur d’entrée MPLS qui gère le trafic qui entre dans un domaine MPLS. • MPLS Egress node : c’est un routeur de sortie est gère le trafic sortant d’un domaine MPLS. • Routeur LSR (Label Switch Router ) : c’est un routeur d’un réseau MPLS qui est capable de retransmettre les paquets au niveau de la couche 3 en se basant seulement sur le mécanisme de labels. • Routeur LER (Label Edge Router ) : c’est un LSR qui fait l’interface entre le réseau MPLS et le monde extérieur. C’est ce routeur qui est chargé d’étiqueter les paquets lorsqu’ils entrent dans le réseau MPLS. Le fonctionnemnt de MPLS s’appuie sur une technique qui permet d’attribuer une étiquette à chaque flux de données TCP/IP. Cette étiquette courte, de longueur fixe, correspond à un bref résumé de l’en-tête de datagramme IP ; elle fournit des information sur le chemin que le paquet doit parcourir, afin qu’il puisse être commuté ou routé plus rapidement sur les réseaux utilisant différents types de protocoles (ATM, Relais de Trames, Ethernet). Comme illustré dans la figure 1.10, la propagation d’un paquet IP sur une épine dorsale MPLS (MPLS backbone) compte trois grandes étapes qui sont les suivantes : 1. Le routeur LER reçoit un paquet IP, range le paquet dans une classe d’équivalence de transmission (FEC, Forward Equivalence Class) et libelle le paquet avec la pile de labels sortante qui correspond à la FEC sélectionnée ; 2. A l’intérieur du domaine MPLS, des LSR reçoivent ce paquet libellé. Ils se servent des tables de transmission de labels pour échanger le label d’entrée dans le paquet entrant avec le label de sortie qui correspond à la même classe FEC. 3. Lorsque le LER de la classe FEC en question reçoit le paquet libellé, il supprime le label et réalise une consultation classique de couche 3 sur la paquet IP. Pour plus de détails sur le protocole MPLS, le lecteur intéressé pourra consulter [5], [7], [18], et [79].

22

Chapitre 1 : Panorama des réseaux haut débit

Fig. 1.10 – Processus d’acheminement de paquets dans MPLS

1.5

Conclusion

Les futures applications demanderont une bande passante en augmentation constante avec un trafic très hétérogène (voix, données, images). De plus, les utilisateurs souhaiteront payer suivant la qualité de service qu’ils demandent. Les réseaux ATM permettent justement de garantir cette qualité de service indépendamment des caractéristiques du service transporté. Cependant, la volonté d’universalité des réseaux ATM a conduit à un pari difficile : assurer un qualité de service comparable à celle des réseaux synchrone tout en offrant la souplesse des réseaux de paquets desquels ATM a hérité la vulnérabilité aux problèmes de congestion. De ce fait, la définition de mécanismes de contrôle de trafic et de congestion s’avère primordiale pour garantir la qualité de service requise par les utilisateurs. L’étude du phènomène de congestion et des solutions proposées pour y remédier fera l’objet du chapitre suivant.

23

Chapitre

2

Contrôle de Congestion dans les Réseaux Haut Débit

"Popular myths that cheaper memory, high-speed links, and high-speed processors will solve the problem of congestion in computer networks are shown to be false." Raj Jain [53]

2.1

Introduction

L

ES avancées technologiques dans le domaine des réseaux locaux ainsi que l’avènement de la fibre optique ont permis d’offrir un grand éventail de débits pouvant atteindre des centaines de mégabits par seconde. Toutefois, ces nouvelles technologies doivent coexister avec les anciens médias tels que les paires torsadées (twisted pairs). Cette hétérogénéité a donné naissance à une grande disparité entre les taux d’arrivée et de service dans les noeuds intermédiaires dans le réseau, causant ainsi des délais d’attente plus grands, et des phénomènes de congestion. La plupart des réseaux déployés (reposant sur TCP et ATM) implémentent des méthodes de contrôle de congestion. Dans ce chapitre, nous nous intéresserons au phénomène de congestion. Ses causes seront identifiées et les mécanismes proposés seront étudiés. Nous attarderons sur les mécanismes de contrôle de congestion dans les réseaux ATM et aborderons très brièvement l’ingénierie de trafic dans MPLS.

2.2

Terminologie et concepts de base

Dans cette section, nous donnons des définitions générales qui seront nécessaires à la compréhension de ce mémoire.

2.2.1

Allocation de ressources

Dans un réseau à commutation de paquets, le mot ressource inclut les tampons de stockage temporaire, les bandes passantes des différents liens, le temps d’exécution 24

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

sur les processeurs, etc. D’une façon générale, le problème d’allocation de ressources dans les réseaux est le suivant : on se donne un réseau avec une certaine topologie, un ensemble de ressources, et un ensemble d’utilisateurs avec des besoins éventuellement différents les uns des autres ( une personne consultant ses mails n’a pas les mêmes besoins qu’une autre utilisant une application vocale ou audio). Le problème est alors de choisir une façon de partager les ressources du réseau entre les utilisateurs en respectant deux propriétés fondamentales : l’efficacité et l’équité.

2.2.2

Notion d’efficacité (efficiency )

Nous comparons l’efficacité des différentes techniques de partage de ressources en se basant sur le nombre total de paquets (Q) transmis par toutes les sources pour une période de temps bien déterminée et un scénario donné. Les paquets qui sont retransmis à plusieurs reprises (pour une raison ou une autre) en cours d’une connexion ne sont comptabilisés qu’une seule fois. Il s’agit d’un bilan au niveau de la couche transport du modèle OSI, un bilan sur l’utilité tirée du réseau. Pratiquement, si on a n sources, et si qi représente la quantité transmise par la ime source durant la période considérée, alors : n X Q= qi (2.1) i=1

Enfin, on calculera le rapport τU entre cette qauantité et la valeur optimale qui résulterait d’un fonctionnement idéal du réseau. C’est à dire : τU =

Q Qopt

(2.2)

τU représente alors le taux d’utilisation du réseau.

2.2.3

Notion d’équité (fairness)

Dans un environnement partagé, le débit alloué à une source dépend de la demande de l’ensemble des utilisateurs. Quel critère devons-nous prendre pour déterminer si un partage donné est équitable ou non ? Dans le domaine des réseau, le critère le plus souvent utilisé est le critère du max-min [10], [56], [14], [64]. L’idée de base consiste à attribuer le maximum de ressources possible à la source qui en recevra le moins parmi les ressources concurrentes.. Nous nous proposons de définir ci-dessous la procédure du max-min : Soit une configuration ayant n sources concurrentes, avec xi la quantité de ressources allouée à la ime source. On définit alors un vecteur d’allocation de ressources comme suit : v = [x1 , x2 , .., xn ] (2.3)

25

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Ce vecteur servira à sauvegarder l’allocation xi faite à chaque source i. Le nombre de vecteurs d’allocation possibles est infini pour chaque situation. Considérons maintenant l’ensemble de ces vecteurs Vk défini comme suit : Vk = {vi |vi est un vecteur d0 allocation possible}

(2.4)

Soit xmin la plus faible allocation de chaque vecteur d’allocation. L’ensemble des solutions restant possibles est toujours infini. On réduit le problème en retirant la source qui s’est vue attribuer la plus faible quantité de ressources et on répète l’opération pour les (n − 1) sources restantes. On réitère ce processus jusqu’à ce que chaque source se soit vue attribuer le maximum de ressources qu’elle pouvait espérer. Maintenant nous pouvons évaluer un algorithme au niveau de son équité en comparant sa répartition à celle qui est dite optimale selon notre critère de max-min . Nous allons évaluer l’indice d’équité ( fainess index ) d’une répartition des ressources de la façon suivante [56] : Pour ce faire, supposons que l’algorithme dont on étudie l’équité fournisse la répartition v = [x1 , x2 , .., xn ] au lieu de la répartition optimale définie par : v opt = [x1,opt , x2,opt , ..., xn,opt ] Nous calculons la répartition normalisée x˜i pour chaque source comme suit : xi x˜i = xi,opt L’indice d’équité τE est alors : µ n P

τE =

(2.6)

¶2

x˜i

i=1 n P

n

(2.5)

i=1

x˜i 2

(2.7)

Notons que l’équité max-min a été adoptée par l’ATM forum pour le service Available Bit Rate (ABR) de l’ATM.

2.2.4

Goulot d’étranglement

Un goulot d’étranglement est défini comme étant une ressource dont la capacité est en moyenne juste égale ou inférieure au besoin. Une définition plus formelle d’un goulot d’étranglement est donnée dans [14] et [94]. Selon William Stallings [90], on peut classifier les goulots d’étranglement d’un réseau en deux classes : goulots d’étranglement logiques (logical bottlenecks) et goulots d’étranglement physiques (physical bottlenecks). Les goulots d’étranglement physiques sont inhérents aux équipement utilisées (commutateurs, routeurs, les tampons mémoires, liaisons à faible débit, vitesse des processeurs, etc). Les goulots d’étranglement logiques, quant à eux , sont dus à la "logique" utilisée dans les ressources très demandées. On peut citer par exemple : la complexité des algorithmes de routage, algorithmes d’ordonnancement (scheduling), etc. 26

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.1 – Facteurs causant la congestion dans un noeud

2.2.5

Produit délai-bande passante (BDP, Bandwidth Delay Product)

Lorsque’on veut analyser les performances des réseaux, on travaille souvent avec le produit délai-bande passante (appelé aussi produit largeur de bande-délai ) [60],[67], [92]. On obtient celui-ci en multipliant la capacité (en bit/s) par le temps de boucle (en secondes) appelé RTT (Round Trip Time) ou encore RTD (Round Trip Delay). Ce produit est alors la capacité du tube (pipe) en bits entre l’émetteur et le récepteur, et réciproquement. Par exemple, considérons l’envoi de données entre deux villes A et B avec un tampon récepteur de 64 Ko. Supposons que nous avons une liaison à 1 Gbit/s et un délai de transmission de 20 ms. Le produit largeur de bande-délai est alors : (20 ms ∗ 2) ∗ 109 bit/s = 4.107 bits

(2.8)

En d’autres termes, l’émetteur peut transmettre 40 millions de bits avant de recevoir l’accusé de réception. Par conséquent, pour des réseaux présentant un produit délaibande passante suffisament grand, le contrôle de flux par fenêtre de congestion (comme c’est le cas du protocole TCP) est très inefficace [4], [89].

2.2.6

Notion de Congestion

Etymologiquement, le mot congestion a pour origine le verbe latin congerere, qui veut dire "accumuler". Dans le domaine des télécommunications et des réseaux informatiques, on peut définir la congestion 1 comme étant un état de certains éléments d’un réseau pour lequel les objectifs de performance fixés ne peuvent pas être atteints [34]. Ceci arrive quand il y pénurie de ressources. Autrement dit, X

Demandes >

X

Ressources disponibles

(2.9)

Un réseau dans le quel une telle situation survient est appelé alors réseau congestionné (congested network ). 1

Dans la littérature, on parle parfois d’encombrement, d’engorgement, ou encore d’embouteillage. Dans le présent mémoire, nous adopterons le terme congestion.

27

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.2 – Variation du débit et du délai en fonction du trafic offert. La présence d’une congestion est indésirable dans un réseau car elle peut causer : • des délais de bout en bout plus longs ; • des pertes de paquets ; • un affaiblissement du débit du à la perte et des retransmissions de paquets, etc ; Dans les réseaux à commutation de paquets , la congestion a lieu en raison de deux facteurs principaux (Fig. 2.1) : • le débit du lien de sortie est inférieur au débits des données entrantes ; • des sources multiples sont en concurrence pour un seul lien et au même moment. La figure 2.2 (a) montre l’évolution du débit (nombre de paquets délivrés aux stations réceptrices) en fonction de la charge offerte (nombre de paquets transmis par une station émettrice) tandis que la figure 2.2 (b) montre l’évolution du débit en fonction de la charge offerte ([90],[91], et [52]). Dans le cas idéal, le débit et l’utilisation du réseau peuvent atteindre la capacité maximale du réseau. L’utilisation devient peut alors être de 100%. Ce cas idéal implique que toutes les stations sachent, d’une manière ou d’une autre et de façon exacte, le moment auquel elles doivent envoyer ou arrêter l’envoi de leurs données ; chose qui est impossible. Si aucun contrôle n’est exercé, on obtient le graphe des deux figures 2.2 (a) et 2.2 (b) que nous avons appelé "non contrôlé". On remarque que les performances du réseaux chutent rapidemnt après avoir dépassé une certaine charge offerte. Il est clair que cette situation "catastrophique" doit être évitée. Ceci est l’objet des mécanismes de contrôle de congestion. Ces mécanismes permettent d’obtenir des performances acceptables avoisinant même des fois les performances idéales. Ceci est illustré dans les courbes que nous avons appelés "contrôlé" dans les figures 2.2 (a) et 2.2 (b).

28

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

2.3

Nécessité d’un contrôle de Congestion

Puisque la surcharge provient d’une augmentation inconsidérée du trafic offert au réseau, les mécanismes de contrôle vont avoir comme tâche de mesurer et de limiter ce trafic. Une autre contrainte qu’on leur impose est d’accomplir cette limitation de la manière la plus rentable, c’est à dire de permettre au réseau de fonctionner au plus près de sa capacité maximale. Enfin, la contrainte d’équité (equity) est aussi invoquée. Dans la recommandation I.371 [50], le contrôle de trafic est défini comme étant : "l’ensemble des actions qui peuvent être prises par le réseau pour empêcher toute congestion", alors que le contrôle de congestion est défini comme étant " les actions qui peuvent être prises par le réseau pour minimiser l’intensité, l’étendue, et la durée de la congestion". Il est intéressant de montrer la différence entre ces deux notions, tant leurs rapports sont très subtils 2 . Le contrôle de congestion est un problème global, qui tient compte du comportement des ordinateurs et des routeurs, mais aussi du mécanisme de retransmission des paquets à l’intérieur des routeurs et de bien d’autres facteurs qui ont tendance à diminuer la capacité de transport du sous-réseau. Le contrôle de flux (flow control ) se rapporte au trafic point-à-point entre un émetteur et un récepteur particuliers. Son rôle consiste à s’assurer qu’un émetteur rapide ne transmette pas des paquets de façon continue, plus rapidement que le récepteur peut les absorber. Le contrôle de flux implique presque toujours un retour d’information du récepteur vers l’émetteur afin de préciser comment les choses se passent à l’arrivée. Les deux objectifs antagonistes que doit réconcilier un mécanisme de contrôle de congestion sont de garantir la qualité de service pour les connexions déjà établies (aucune congestion) d’une part ; et d’utiliser de façon efficace les capacités de transmission du réseau (utilisation du multiplexage statistique) d’autre part [93].

2.4

Propriétés d’un bon système de contrôle de congestion

Malgré le nombre énorme d’algorithmes de contrôle de congestion proposés dans la littérature, ce domaine fait toujours l’objet d’intenses recherches. Selon Raj Jain [53], il y a deux raisons à cela. La première est due aux exigences contradictoires que l’on doit satisfaire, et la seconde vient de la difficulté à concevoir un algorithme performant et adéquat pour toutes les architectures de réseaux. La difficulté du contrôle provient en majeure partie du caractère distribué des sources du réseau qui fait que le trafic émanant de différentes sources soit non coor2

Certains auteurs préfèrent ne pas faire de distinction entre les deux notions ( voir par exemple

[18]

29

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

donné, et de l’absence d’un organe de contrôle central qui régulerait le trafic en fonction de l’état global du réseau. Un bon mécanisme de contrôle de congestion doit tenter de satisfaire un certain nombre de proprétés fondamentales que nous étudierons dans cette section. En pratique, la plupart des algorithmes ne satisfont que quelques unes de ces propriétés qui sont les suivantes : 1. Simplicité (Simplicity ) La simplicité a été toujours un avantage. Il est très important de réduire la complexité d’un algorithme de contrôle de congestion pour faciliter son implémentation sur matériel (hardware) aussi bien que sur logiciel (software). 2. Efficacité (Efficiency ) Il existe deux aspects d’efficacité d’une méthode de contrôle de congestion. Premièrement, l’overhead que la méthode de contrôle de congestion impose au réseau . En effet, les paquets de contrôle eux-mêmes empirent la situation de congestion dans un réseau. part conséquent, une bonne méthode de contrôle de congestion doit minimiser les données de contrôle. Deuxièmement, on doit maximiser l’utilisation des ressources du réseau. 3. Equité (Fairness) L’équité peut ne pas être très importante au moment où le réseau n’est pas surchargé et toutes les demandes peuvent être satisfaites. Par contre, durant les périodes de congestion où les ressources disponibles sont inférieures aux demandes, il est très important que ces ressources soient partagées de façon équitable. 4. Extensibilité (Scalability ) Les réseaux peuvent être classifiées selon leurs étendues géographiques , le nombre de noeuds, le débit ou le nombre d’usagers. Un bon système de contrôle de congestion ne doit pas être limité à une gamme de vitesses, à une distance ou à un nombre particulier de commutateurs. Ceci garantira que ce même système de contrôle de congestion puisse être utilisé pour les réseaux locaux (LANs) aussi bien que pour les réseaux étendus (WANs). 5. Robustesse (Robustness) Par robustesse, on entend l’insensibilité de l’algorithme de contrôle de congestion aux petites déviations. Par exemple, une petite perte des messages de contrôle ne doit pas causer un effondrement des capacités du réseau. Notons que chez certains auteurs , cette propriété est appelé stabilité (stability). 6. Implémentabilité (Implementability ) Un algorithme de contrôle de congestion ne doit pas dicter un architecture particulière pour les commutateurs du réseau.

30

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

2.5

Taxonomie des méthodes de contrôle de congestion

Un bon nombre d’algorithmes de contrôle de congestion sont bien connus des spécialistes. la question que l’on se pose ici est comment classifier toute cette armada de méthodes. En effet, cette taxonomie peut être faite selon plusieurs critères ( voir par exemple [53], [58],[64], et [102]). Nous résumons dans ce qui suit ces critères de classification.

2.5.1

Taxonomie selon le stade d’intervention

Selon le stade d’intervention, nous pouvons classer les mécanismes de contrôle de trafic essentiellement en trois classes : mécanismes de contrôle réactifs, mécanismes de contrôle préventifs et enfin mécanismes de contrôle hybrides. Dans un mécanisme préventif de contrôle de congestion, chaque source doit décrire, a priori, son trafic au réseau. Le réseau réserve en conséquent les ressources (e.g. mémoire et bande passante) correspondant aux paramètres décrivant le trafic. En cas d’insuffisance de ressources, le réseau n’accepte pas le trafic en question. Ceci permet de minimiser les chances d’une congestion. Contrairement au contrôle préventif, le contrôle réactif agit en fonction de l’évolution de l’état du réseau. Sa philosophie est de pouvoir partager les ressources par le maximum de connexions pour optimiser l’utilisation du réseau. Le principe est le suivant : chaque source doit, de façon dynamique, ajuster son trafic pour partager équitablement (entre les différentes sources) les ressources du réseau. Pour ce faire, le réseau doit indiquer, de façon explicite ou implicite, aux sources les changements d’états . Chaque changement doit se traduire par un ajustement du trafic de la source. Le contrôle réactif suppose que le réseau ou le service n’effectue pas une réservation de ressources, i.e. toutes les connexions/flux sont acceptées sans que le réseau ne garantisse une QoS. Plusieurs algorithmes réactifs ont été proposés et utilisés dans les réseaux de paquets. L’exemple le plus simple est le contrôle le mécanisme de fenêtre de TCP défini par Van Jacobson [51]. Les mécanimes hybrides combinent les caractéristiques du contrôle préventif et celles du contrôle réactif que nous avons décrits ci-dessus. Le principe de ce type de mécanismes est le suivant : le réseau réserve pour chaque source un minimum de ressources correspondant aux paramètres de trafic spécifiés. Les sources sont autorisées à excéder le trafic spécifié pendant les périodes où les ressources du réseau ne sont pas toutes réservées ou utilisées (inactivité d’autres sources). Dans ce cas, le réseau n’offre pas de garanties au trafic excédant celui spécifié au départ. Dans les réseaux ATM, Les trafics du type CBR et VBR utilisent un schéma de 31

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Couche Couche Transport

Couche Réseau Couche Liaison

Voies d’action • • • •

Politique de retransmission Politique de l’accusé de réception Politique du contrôle de flux Définition des intervalles de temps hors délais (time out)

• • • • •

Circuits virtuels ou datagramme Politique de mise en file d’attente et de distribution de paquets Politique de destruction de paquets Politique de routage Gestion de la durée de vie des paquets

• Politique de retransmission • Politique de l’accusé de réception • Politique du contrôle de flux Tab. 2.1 – Politiques pouvant influer sur la congestion

contrôle de congestion préventif alors que le trafic ABR utilise un schéma de contrôle de congestion de type réactif [58]. Les mécanismes réactifs de contrôle de congestion ont été utilisés dans les réseaux classiques. Cependant, ils ne peuvent pas être adaptés pour les réseaux haut débit pour des raisons qu’on verra dans ce chapitre (voir aussi [2], [34], et [68]).

2.5.2

Taxonomie selon la couche du modèle OSI

Une des façons de classifier les algorithmes de contrôle de congestion se fait en fonction de la couche du système de référence OSI (Open System Interconnection) au niveau duquel s’applique l’algorithme (voir Tab 2.1). • Regardons, par exemple, la couche liaison de données (link layer ) ; la politique de retransmission est en rapport avec la vitesse de réaction et le comportement d’un émetteur face à des paquets transmis et dont les accusés de réception sont hors délais. Certains émetteurs "impatients" estiment trop rapidement que les temps sont hors délais et retransmettent, consèquement, tout paquet non encore acquitté, ce qui provoque une surcharge du sous-réseau. La politique de l’accusé de réception influe également sur la congestion. Si chaque paquet est acquitté immédiatement, les paquets créent aussi une surcharge de trafic. • Au niveau de la couche réseau, le choix entre circuit virtuel et mode datagramme a une influence majeure sur la congestion. En effet, un bon nombre d’algorithmes de contrôle de congestion ne fonctionnent que sur des circuits virtuels. La politique de 32

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.3 – Méthodes de contrôle de congestion en fonction de la durée. mise en file d’attente des paquets concerne les routeurs qui gérent les différents flux selon une politique d’ordonnancement (scheduling) donnée. • Au niveau de la couche transport, une difficulté supplémentaire apparaît : la définition des intervalles de temps hors délai lors de la gestion des paquets. En effet, ce temps est plus difficile d’estimer ce paramètre entre deux sources qu’entre deux routeurs : si on prend ce temps très court, des paquets supplémentaires inopportuns sont retransmis ; s’il est plus long, c’est le temps de réponse qui en souffrira à chaque fois qu’un paquet est perdu.

2.5.3

Taxonomie selon la durée de la congestion

La congestion survenant dans un réseau peut être à : 1. Court-terme : Concerne la congestion due aux phénomènes transitoires dans le réseau (arrivée d’une rafale) et au problème de partage de ressources. Elle n’est pas contrôlable à partir de la source sa durée est inférieure au temps de propagation entre le noeud congestionné et la source. 2. Moyen-terme : Congestion plus symptômatique, due à un manque de ressources disponibles sur une période de temps plus importante que celle du transitoire. Ce type de congestion est contrôlable à partir de la source. 3. Long-terme : Congestion récurrente qui résulte du manque de bande passante, mémoire et puissance de calcul dans l’architecture du réseau concerné. Elle est d’une durée infinie si aucune mesure n’est prise pour redimmnesionner le réseau et augmenter les ressources de celui-ci. Le choix d’une méthode de contrôle de congestion dépend du degré et de la durée de celle-ci. La figure 2.3 montre comment la durée de la congestion affecte le choix 33

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fenêtre dynamique

Débit dynamique

Contrôle

Fenêtre (W )

Nombre de paquets (n) et intervalle de temps (T )

Débit effectif

W RT T

n T

Requis si

Le goulot d’étranglement est la mémoire

Le(s) processeur(s) ou les liens sont les goulots d’étranglements

Taille maximale de la file

Limitée à la taille de la fenêtre

Pas de limite

Sporadicité

Donne lieu à un trafic sporadique

Trafic non sporadique du côté de la source

Etendue du contrôle

bout en bout, saut par saut, ou les deux

Saut par saut

Couche réseau

Mode non connecté ou orienté connexion

Orienté connexion

Tab. 2.2 – Comparaison entre le contrôle par fenêtre et le contrôle par débit de la méthode appropriée. La meilleure méthode pour les réseaux qui sont presque souvent congestionnés est de remplacer les liaisons à faible débit par des liaisons à haut débit et de redimmensionner le réseau pour répondre aux nouveaux besoins. Pour une congestion sporadique (sporadic congestion), une solution consiste à utiliser un routage dynamique qui consiste à acheminer le trafic selon la charge des liens du réseau et de rejeter toutes les nouvelles connexions si tous les liens sont lourdement chargés. Pour une durée de congestion moyenne, on pourra utiliser un contrôle d’admission, qui va rejeter toutes les connexions entrantes tant que la congestion persiste. Pour les congestions durant moins que la durée d’une connexion, un mécanisme de contrôle de bout en bout ou saut par saut peut être utilisé . Enfin, pour des congestions de très courte durée, les files d’attente au niveau des noeuds de commutation permettent d’absorber les rafales de donnés au cas où la ligne se sortie n’arrive pas à suivre.

2.5.4

Taxonomie selon le mécanisme utilisé (fenêtre dynamique versus approche débit dynamique)

Il existe deux moyens de contrôler le trafic : la fenêtre dynamique 3 et le débit dynamique. La fenêtre définit le nombre maximum d’octets que peut envoyer une source 3

Le terme "dynamique" (pour contrôle par fenêtre/débit) est utilisé pour indiquer que la taille de la fenêtre ou le débit varient dynamiquement en fonction du contrôle.

34

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

avant de se bloquer en attente d’acquittements. Chaque acquittement fait glisser la fenêtre et déclenche l’envoi de nouveaux paquets. Parmi les mécanismes de contrôle de trafic basés sur l’utilisation d’une fenêtre nous citons le Slow-start utilisé dans TCP [51] et DECBit [83]. Le principe du contrôle par fenêtre (appelé aussi contrôle de flux par crédit) est le suivant : une source se voit allouer un certain nombre W de crédits. Elle peut émettre un paquet à condition d’avoir un crédit. Un fois le paquet envoyé, le crédit correspondant est consommé. Le récepteur acquitte les paquets reçus et l’accusé de réception (acknowledgement) régénère les crédits de l’émetteur, l’autorisant ainsi à poursuivre. Le contrôle de flux par fenêtre est un mécanisme simple à mettre en oeuvre et il a été utilisé pour plusieurs années dans les réseaux existants. Malheureusement, ceci pose un certain nombre de problèmes qui sont détaillés ci-dessous : 1. Taille de la fenêtre : De façon schématique on peut dire que sous le contrôle par fenêtre, la source demande au réseau quel est sont état. Si la réponse est qu’il y un risque de congestion, la source réduit son débit. Cette réponse est en fait donnée de façon implicite par un retard des acquittements. Le problème est que pour les réseaux avec de grandes valeurs du produit bande passante fois délai de propagation (BDP,Bandwidth Delay Product), le délai pour obtenir un réponse est trop important.Par exemple, les performances de TCP chutent de façon dramatique dans des réseaux ayant un BDP relativement grands par rapport aux réseaux classiques. 2. Garantie de débit : Le contrôle de flux par fenêtre a été développé pour les réseaux de données. les applications utilisant ce type de réseaux ont la caractéristique suivante : elles peuvent réduire leurs débits si le réseau le leur demande. par contre, pour les réseaux à haut débit (ATM par exemple), ceci n’est pas possible. En effet, les réseaux à large bande ont été conçus pour le tranport du traffic temps réel et multimédia. Ce type d’application requiert une garantie de bande passante que le contrôle de flux ne permet pas d’offrir. 3. Qualités de services spécifiques : Il n’est pas facile d’offrir des qualités de service spécifiques quand les mécanisme de contrôle de trafic utilisé est le contrôle de flux par fenêtre. En effet, certaines applications temps réel qui ont des contraintes très strictes en termes de gigue et du délai de bout en bout ne peuvent pas réduire leur trafic même si celui-ci cause une congestion. L’autre moyen de contrôler le trafic est l’utilisation d’un contrôle par débit dynamique (rate-based control ). Une source doit envoyer les paquets successifs espacés par un intervalle de temps qui est fonction du débit de la source. L’exemple le plus connu de contrôle par débit est l’ABR (Available Bit Rate) [11]. Dans l’approche débit, la source utilise des informations du réseau pour déterminer le débit maximal auquel elle peut transmettre. Ces informations sont transportées soit par des cellules de gestion de 35

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.4 – Forward Explicit Congestion Notification.

Fig. 2.5 – Backward Explicit Congestion Notification. ressources RM (Resource Management), soit par le biais d’une indication explicite de débit (ERI, Explicite Rate Indication), soit sous la forme d’une indication de congestion codée sur un bit (mode binaire). La notification explicite de congestion ou ECN (Explicit Congestion Notification) en est un exemple : un commutateur détectant un risque de congestion en informant la source soit directement en utilisant la méthode BECN (Backward Explicit Congestion Notification) soit indirectement en utilisant la méthode FECN (Forward Explicit Congestion Notification )[34]. Après un long débat "religieux" qui a duré plus d’une année entre les tenants des mécanismes de contrôle par débit dynamique (opérateurs et constructeurs de télécommunications publiques) et les tenants des mécanismes de contrôle par fenêtre dynamique (constructeurs de matériel informatique), l’ATM Forum a adopté l’approche débit pour le contrôle de flux dans ABR et a rejeté l’approche fenêtre ( voir [44], [45], [55], [85],[84], [88], et [89]). La raison essentielle du rejet du contrôle par crédit est le fait qu’il nécessite des mécanismes de mise en file d’attente très complexes au niveau des commutateurs du réseau, ce qui le rend très lourd à implémenter.

36

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

2.5.5

Taxonomie selon la boucle utilisée (boucle fermée versus boucle ouverte)

Un certain nombre de problèmes propres aux systèmes complexes, tels que ceux rencontrés dans les réseaux d’ordinateurs, peuvent être analysés selon la théorie du contrôle ou de la commande. Cette démarche d’analyse conduit à diviser les systèmes en deux catégories : les systèmes en boucle ouverte (open loop systems), et les systèmes en boucle fermée (closed loop systems). Dans les systèmes en boucle ouverte, on essaye de résoudre au mieux le système lors de sa conception, essentiellement en s’assurant q’un problème n’arrivera pas. Dès que le système est en cours de fonctionnement aucune correction même mineure, n’est possible. Les moyens de contrôle d’un système en boucle ouverte peuvent être, par exemple, de décider à quel moment accepter : d’augmenter le trafic, de recevoir de nouveaux paquets, de détruire des paquets et de décider lesquels, de prendre des décisions d’ordonnancement à divers endroits du réseaux. Le contrôle par boucle fermée, quant à lui, consiste à à envoyer les informations relatives à la congestion de l’endroit où la congestion est apparue vers l’endroit où l’on peut réagir pour résoudre le problème. L’essentiel pour le commutateur qui détecte la congestion, est de transmettre un paquet (ou des paquets) à la destination ou vers la source d’émission de paquets concernés pour leur annoncer le problème. Une caractéristique importante des systèmes utilisant la boucle fermée est le fait que le leur performance dépend au délai de la notification (feedback ). Cette notification peut être implicite (c’est le cas de TCP [51]) ou explicite (c’est le cas de DECBit [83]).

2.5.6

Taxonomie selon la logique d’intervention (bout en bout versus noeud par noeud)

Le contrôle de bout en bout (end to end ) se fait au niveau de la couche transport du modèle de référence OSI. Son rôle essentiel est le contrôle de flux qui consiste à s’assurer que le débit de la source n’est pas trop important pour le récepteur. Par conséquent, il représente un contrôle "égoïste" de contrôle de flux. Le contrôle noeud par noeud (hop by hop), quant à lui, se fait au niveau de la couche réseau du modèle OSI. Son principe consiste à permettre aux routeurs adjacents d’échanger des messages sur leur état de congestion. Ainsi un routeur peut demander à un routeur connecté à l’une de ses entréees de réduire, voire de stopper totalement l’envoi de paquets lorsqu’il est congestionné. Il existe plusieurs variantes qui se basent sur ce même principe, certaines plus complexes et côuteuses que les autres. L’idée est de pouvoir agir rapidement, directement au niveau des routeurs afin d’éviter la perte de paquets. Dans le cas d’un contrôle de bout en bout, on voit le réseau comme étant une boîte noire 37

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

dont les composants internes (noeuds de commutations) ne nous intéressent pas ; tandis qu’un contrôle noeud par noeud, on voit le réseau comme étant une boîte blanche.

2.6

Principe du contrôle de congestion dans les réseaux à commutation de paquets

Nous avons vu que les réseaux à commutation de paquets offrent plusieurs avantages tels que la flexibilité. En contrapartie, le prix à payer est le risque de congestion. En effet, un réseau à commutation de paquets est par essence un réseau de files d’attente. Ces dernières sont d’une taille limitée ; quand le taux d’arrivée des paquets dans un noeud (routeur ou commutateur) dépasse le temps moyen de service, ceci peut mener à une débordement des buffers de ce noeud causant des phénomènes de congestion. Le contrôle de congestion 4 dans les réseaux à commutation de paquets (packet switching networks ) a suscité un grand intérêt au sein de la communauté scientifique depuis le début des années 80 [37]. En effet, il est très important d’éviter les pertes de paquets dans un réseau car quand un paquet est perdu avant qu’il atteigne sa destination, toutes les ressources qu’il a consommées durant son transit sont gaspillées. Dans un réseau à commutation de paquets caractérisé par la non réservation préalable de ressources, le contrôle de congestion doit être réactif. Un tel contrôle est implémenté à deux niveaux : 1. au niveau des commutateurs où la congestion survient ; 2. au niveau des sources qui augmentent et réduisent leur trafic en fonction du signal de congestion. Typiquement, un commutateur utilise quelques métriques pour détecter le début d’une congestion. Par la suite, il notifie cette congestion soit implicitement soit explicitement aux sources qui , comme réponse, réduisent leur trafic. Même si un tel schéma paraît facile, il doit résoudre les problèmes suivants [63] :

2.6.1

Détection de la congestion

Pour détecter une congestion, un commutateur utilise plusieurs alternatives : • le moyen le plus connu est de notifier que les buffers du commutateur n’ont plus de place pour les paquets arrivants ; • un commutateur peut aussi surveiller le taux d’utilisation de la ligne de sortie. En effet, Il a été montré que la congestion survient quand l’utilisation de la ligne de sortie dépasse un certain seuil (typiquement 90 %). Par conséquent, cette métrique peut 4

A cette époque, contrôle de flux et contrôle de congestion étaient utilisés de façon interchangeable

38

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

être utilisée comme signal de congestion. Le problème de cette métrique est la phase de l’évitement de la congestion (congestion avoidance) peut laisser la ligne de sortie inutilisée menant ainsi à une inefficacité du réseau ; • une source peut aussi surveiller les RTTs (Round Trip Times). Une augmentation dans ces derniers signale une augmentation dans la taille des files d’attente et par conséquent un risque de congestion ; • une source peut aussi maintenir un temporisateur (timer ) qui déclenche une alarme quand un paquet n’est pas acquitté à temps [82]. Une fois l’alarme déclenchée, la congestion est alors suspectée.

2.6.2

Communication de l’information de congestion

La communication de l’information de congestion (ou notification de congestion) peut être faite de façon explicite ou implicite. Quand l’information est explicite, les commutateurs envoient la notification de congestion sous forme d’un bit dans l’entête des paquets, ou dans des paquets indépendants (Source Quench) tels que ICMP. Le problème majeur des méthodes explicites est l’overhead (surcharge supplémentaire) qu’elle ajoutent au réseau. Les méthodes implicites ne souffrent pas de ce problème. En revanche, une source n’est pas capable de distinguer entre une congestion et d’autres problèmes de performances.

2.6.3

Actions prises par un commutateur

Un commutateur congestionné peut signaler la congestion aux sources concernées, ou au pire des cas rejeter les paquets arrivant dans ses buffers d’entrée. Le problème revient alors à choisir soit une source à laquelle le commutateur demande de réduire le trafic ou tout simplement choisir quels paquets rejeter. L’équité d’un schéma de contrôle de congestion dépend étroitement de ce choix.

2.6.4

Contrôle de flux du côté des sources

Un nombre de mécanismes de contrôle de congestion ont été conçus pour opérer au niveau des sources. De tels mécanismes utilisent la perte de paquets ou la réception des paquets de sondage (choke paquets) comme signal pour réduire le débit des sources. Dans un schéma de congestion utilisant un sondage de paquets (packet choke), une source arrête carrément son trafic quand elle détecte la congestion. Après une durée de temps, la source est autorisée à envoyer de nouveau. une telle stratégie n’est pas du tout efficace car elle est sujette à des oscillations. Par contre, dans un schéma à contrôle de débit (rate-based control scheme), quand une source détecte une congestion, elle réduit le débit auquel elle envoit ses paquets. L’avantage de cette approche par rapport au sondage de paquets est qu’elle permet une transition graduelle dans le débit d’envoi 39

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.6 – Principe de l’algorithme DECBit. des sources. Par conséquent, elle présente une bonne alternative pour le contrôle de congestion. L’analyse de la stabilité et de l’efficacité de cette approche est donnée dans [63].

2.6.5

Coopération entre les différents acteurs

Dans une situation de congestion ou de façon plus générale de partage de ressources, on fait toujours l’hypothèse que les sources coopérent entre elles afin d’aboutir à un partage équitable des ressources et une utilisation plus efficace du réseau. Cependant, une telle hypothèse ne sera pas toujours vraie dans les grands réseaux où quelques sources ne coopèrent pas et se comportent de façon byzantine. Malheureusement, beaucoup de schémas de contrôle de congestion laissent passer inapercu ce point très important. Par exemple, dans DECBit [83], si une source "malhonnête" choisit d’ignorer le bit de notification de congestion qui a été positionné par un commutateur pour indiquer une congestion, les autres sources "honnêtes" vont automatiquement donner plus de la bande passante à cette source. TCP souffre du même problème dans la version de Van jacobson et Karels [51]. Pour plus de détails sur la coopération entre sources , le lecteur intéressé peut se référer à [94]. Comme exemple d’algorithme de contrôle de congestion dans les réseaux à commutation de paquets, nous nous proposons d’étudier l’algorithme DECBit conçu par K.K. Ramakrishnan et R. Jain aux laboratoires de Digital Equipment Corporation (DEC) à la fin des années 80. OAr la suite, nous abordrons le contrôle de congestion dans TCP.

2.7

Contrôle de Congestion dans DECBit

Dans DECBit[83], les sources ajustent la taille de la fenêtre basée sur un feedback explicite reçu du réseau. Tous les paquets ont un bit appelé Bit d’évitement de Congestion (Congestion Avoidance Bit) (Fig 2.6). Le but de DECbit est de contrôler la congestion tout en maintenant une file d’attente non vide et de taille très petite 40

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.7 – Cycles de régénération dans DECBit. dans chaque commutateur du réseau. Le feedback vers la source est donc explicite. On n’attend pas la perte de paquets pour détecter un état de congestion comme s’est le cas dans TCP Reno ou TCP Vegas. L’algorithme DECBit consiste en deux composantes principales : 1. L’algorithme utilisé par les commutateurs pour positionner les bits d’indication de congestion, 2. L’algorithme utilisé par les sources pour ajuster la taille de la fenêtre en réponse à un feedback. Les commutateurs pisitionnent les bits d’indication de congestion dans les paquets de données si la taille moyenne des files excède un paquet La taille moyenne d’une file est calculée à des intervalles appelés cycles de régénération. Un cycle de régénération (Fig. 2.7) est défini comme étant la durée des périodes oisive + occupée plus la période occupée courante [58], [83]. La source enregistre combien de ses paquets ont provoqué la mise en place du bit du congestion. Plus précisément la source maintient une fenêtre de transmission semblable à celle de TCP et évalue la fraction de cette fenêtre dont les paquets ont été marqués. Si cette part est inférieure à 50 % alors la source accroît la taille de sa fenêtre de 1 paquet. Si 50% ou plus de ces paquets sont marqués alors la source réduit la taille de sa fenêtre à 0.875 fois la taille courante. L’algorithme DECBit a des caractéristiques intéressantes : Il ne requiert qu’un bit supplémentaire dans l’en-tête des paquets et n’exige pas de files d’attentes différenciées pour chacune des connexions. Son implémentation dans le réseau n’est lourde et facilement réalisable. En outre, de nombreuses simulations démontrent sa stabilité [83]. Cependant, cet algorithme conduit à une croissance très lente de la fenêtre de transmission. Trop souvent, la source a fini sa transmission avant que la taille de sa fenêtre ait la valeur optimale. Plus particulièrement, le problème devient de plus en plus gênant lorsque le produit délai-bande passante du réseau est important, ce qui est le cas dans les réseaux actuels. Cet algorithme présente un autre problème : lorsque connexions 41

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

différentes ont des délais inégaux, DECBit devient biaisé contre les connexions à longs délais [58]. En outre, dans les périodes de congestion, il signale la congestion pas seulement aux connexions surchargeantes mais aussi aux connexions qui ont des exigences en dessus de celles du partage max-min équitable . Comme il a été montré dans [19] que la combinaison de mécanismes AIMD (Additive Increase Multiplicative Decrease) avec un marquage sélectif (selective marking) mène à un système stable et équitable, cette solution a été apportée par la suite à DECBit.

2.8

Contrôle de congestion dans Internet

Historiquement, les premiers réseaux à large distance (WANs) étaient les réseaux téléphoniques à commutation de circuits. Du moment que ces réseaux transportaient des données de même type et que le trafic est bien connu, il était alors possible d’éviter la congestion en réservant suffisamment de ressources au début de chaque appel. En revanche, les ressources du réseau sont sous-utilisées en cas des silences. L’émergence des réseaux de communication de données a connu une accrue de grande ampleur depuis les années 80. Cette croissance a engendré un trafic de données très important essentiellement pour les réseaux d’interconnexions tels que Internet. L’architecture protocolaire d’Internet basée sur un service en mode non connecté, de bout-en-bout a fait ses preuves en matière de flexiblilité et de robustesse. En contrepartie, et contrairement aux réseaux à commutation de circuits, il faudrait plus de vigilance pour continuer à fournir un bon service même quand le système est surchargé. Dans certains cas, ceci peut même mener à un effondrement de congestion (congestion collapse), une situation où une augmentation de la charge du réseau provoque une diminution de la charge utile écoulée ([14], [94]). Un tel phénomène a été observé durant la première phase de croissance d’Internet au milieu des années 80 (voir le RFC 896 [75] et [63]). Dans le but de pallier aux pertes dues à ces congestion et aux erreurs de transmission, un protocole pouvant les détecter et les corriger a été conçu : il s’agit du fameux protocole TCP (Transmission Control Protocol). La spécification originale de TCP dans le RFC 793 [82] a inclu un contrôle de flux basé sur le mécanisme de fenêtre glissante (sliding window ) comme un moyen pour un récepteur pour contrôler la quantité de données envoyées par une source. Ce contrôle de flux a été utilisé pour prévenir le débordement des tampons du côté du récepteur. Ainsi, Le RFC 793 [82] rapporta que des segments TCP peuvent être perdus, soit à cause d’erreurs de transmission, soit à cause de la congestion. En revanche, il n’a pas inclu un mécanisme d’ajustement dynamique de la fenêtre de contrôle de flux en réponse à la congestion. Nous présenterons d’abord la notion d’effondrement de congestion. Par la suite, nous verrons les améliorations apportées pour le protocole TCP afin qu’il continue de 42

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

garantir un contrôle de flux de façon efficace dans les réseaux WAN.

2.8.1

Effondrement de Congestion (Congestion Collapse)

Pour présenter la notion d’effondrement de congestion (congestion collapse), examinons le réseau dont la topologie est donnée dans la figure 2.8. Nous ferons les hypothèses suivantes : – La seule ressource à allouer est bande passante des liens, – Si le trafic offert sur un lien ` dépasse la capacité C` du lien, alors toutes les ressources doivent réduire de façon proportionnelle leurs trafics offerts. Nous supposons également que le mécanisme d’ordonnancement utilisé est FIFO (First In First Out). De façon imagée, on peut faire une analogie avec les fluides et considérer les données circulant sur un réseau comme un fluide. Les liens sont alors des canalisations, et les files d’attentes des réservoirs. Elle revient à dire dans notre cas que les paquets vont être envoyées sur le lien dans l’ordre d’arrivée dans le buffer, l’ordonnanceur étant la vanne entre le réservoir et le canal [94]. Les sources S1 et S2 envoient du trafic aux destinations D1 et D2 respectivement. Les capacités (en kb/s) et les noms de chaque lien sont donnés dans la figure 2.8. Les sources ne sont limités que par la bande passante de leur premier lien et ne reçoivent pas de notification de congestion du réseau. Soient λi le débit d’émission de la source i et λ0i son débit sortant. Par exemple, pour notre réseau, on a λ1 = 100 kb/s et λ2 = 1000 kb/s. Mais λ01 = λ02 = 10 kb/s ! !. En effet, la source S1 peut seulement envoyer à 10 kb/s car elle est en compétition avec la source S2 qui envoie à un débit plus grand que celui de la source S1 sur le lien . Par contre, la source S2 est limitée à 10 kb/s à cause du lien L5 . Si la source S2 est au courant de la situation globale du réseau et si elle "coopère", alors elle pourra envoyer à un débit de 10 kb/s seulement sur le lien L2 , ce qui va permettre à la source S1 d’envoyer son trafic à un débit de 100 kb/s sans toutefois que la source S2 ) ne soit pénalisée. Ainsi, le debit global du réseau sera 110 kb/s. Ainsi, on pourra tirer la conclusion suivante : Dans un réseau à commutation de paquets, les sources doivent limiter leurs débits d’émission en prenant en compte l’état du réseau. Sinon, il y a un risque d’effondrement de congestion. Cette situation a déja eu lieu au milieu des années 80 (voir [63] et [51]). Le facteur principal qui a mené à cette situation était l’absence de contrôle de flux dans les réseaux TCP/IP à cette époque. D’autre facteurs tels la fragmentation IP ont aggravé la situation en causant l’effet "avalanche". Dans le RFC 2914 [28], Sally Floyd étudie en détails les raison qui pousse à la situation d’effondrement de congestion.

43

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.8 – Exemple de topologie du réseau.

2.8.2

Contrôle de Congestion dans TCP

Des études récentes du trafic réseau dans plusieurs campus indiquent que plus de 90% du trafic est transporté par le protocole TCP (Transmission Control Protocol ) qui a été défini dans le RFC 793 [82]. Les mécanismes de contrôle de congestion pour les protocoles TCP/IP ont été longtemps étudiés et de nombreux algorithmes ont été proposés dans la littérature. Le contrôle de congestion dans TCP continue d’être un sujet de recherche. Par exemple, dans [15] les auteurs ont montré que l’on pouvait améliorer le débit de TCP de 40 à 70 % en gérant l’horloge de façon plus précise, en prévoyant des congestions avant que les temporisateurs (timers)expirent et en utilisant ces anticipations d’alarme pour améliorer l’algorithme du Slow Start. Le protocole TCP, inventé en 1981 (voir [82]), est un protocole de la couche transport du modèle OSI (Open System Interconnection)qui assure l’arrivée des paquets envoyés leur destination et qui prend en charge la numérotation des paquets, et contrôle la congestion du réseau due à l’envoi trop intensif du trafic . Pour ce faire, il se sert de mécanismes basés sur des accusés de réception (acknowledgments) pour s’assurer de l’arrivée des paquets à bonne destination et de mécanismes à fenêtres (voir [21]) de transmission et de réception pour gérer les congestions. Plusieurs versions de TCP ont été proposées dans la littérature pour améliorer les performances de TCP dans Internet : Dans TCP Tahoe, Van Jacobson donne les premières améliorations de TCP au niveau de ses algorithmes de contrôle de congestion [51]. Il définit un nouveau concept important qui est la fenêtre de congestion (congestion window ) sur laquelle se base deux algorithmes principaux de TCP : Les algorithmes de Slow Start et de Congestion Avoidance. Cette version de TCP porte le nom de TCP Tahoe et date de 1988. par la suite, vinrent d’autres versions : TCP Reno, TCP Vegas, TCP New Reno, etc [16].

44

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

2.9

Améliorations pour TCP dans les réseaux haut débit

Plusieurs études ont montré l’incompatibilité qui existe entre les mécanismes de contrôle de congestion de TCP et les fonctions de contrôle de trafic des réseaux ATM (voir par exemple [2], [22], [26], et [30]). Ceci vient du fait que, contrairement à TCP qui offre un contrôle de congestion réactif, les réseaux ATM implémentent un mécanisme de contrôle préventif. Cependant, le protocole TCP a toutes les chances de rester prépondérant pour de très longues années, dans les réseaux filaires (wired networks) tels que ATM aussi bien que dans les réseaux sans fils (wireless networks). L’ouvrage [41] étudie de façon très détaillée les problèmes de TCP dans les réseaux à fibre optique, les réseaux satellitaires, les réseaux sans fils et les réseaux asymétriques. L’analyse mathématique révèle que le comportement de TCP devient oscillatoire et instable quand le produit délai-bande passante devient relativement grand [73]. L’autre problème dont souffre TCP est l’inefficacité. Ceci est du au mécanisme de l’Additive Increase de TCP qui limite sa capacité de bénéfécier des grands débits offerts par les médias de transmission moderne tels que la fibre optique qui peuvent atteindre des débit de l’ordre du gigabit/s [73]. Plusieurs améliorations ont été apportées dans la littérature à TCP pour qu’il soit efficace dans les réseaux à grand produit bande passante-délai. On peut citer par exemple : Scalable TCP [62], FAST TCP [24], High Speed TCP [29] et XCP [61], [60]. Dans ce dernier, les auteurs développent un protocole baptisé XCP (eXplicit Control Protocol ) qui est demeure efficace, équitable et stable même quand le RTT ou le BDP deviennent grands. Le protocole XCP généralise la proposition de l’ECN (Explicit Congestion Notification) proposée dans le RFC 2841 [?]. En effet, au lieu d’utiliser un seul bit dans ECN, les routeurs supportant XCP doivent informer les sources non seulement si une congestion existe ou non mais indiquent également le degré ce cette congestion. Ainsi, pour XCP la congestion n’est pas représentée comme une variable binaire mais plutôt à des dégrés . Une autre notion très importante aussi dans XCP est le découplage du contrôle d’efficacité et du contrôle d’équité.

2.10

Contrôle de congestion dans les réseaux haut débit

2.10.1

Mythes non fondés

La congestion se produit dans un réseau quand la demande est plus grande que les ressources disponibles. Ceci a mené à de fausses croyances au sein de la communauté 45

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

scientifique [53], [55] concernant des solutions possibles à ce problème . On peut citer par exemple : 1. La congestion est causée par le déficit en terme d’espace mémoire dans les commutateurs et les routeurs, et ceci va être résolu quand le coût de la mémoire va baisser ; 2. La congestion est causée par les liens à faible débit ; ceci va alors être résolu avec l’avènement de liens à haut débit ; 3. La congestion est causée par les processeurs très lents. Le problème va être résolu quand la vitesse des processeurs sera suffisamment grande ; 4. Si aucun des points ci-dessus n’est la vraie raison causant la congestion, alors l’avènement d’une technologie répondant aux trois exigences ci-dessus réglera le problème de congestion de façon définitive. Raj Jain nous montre dans [53], de façon simple, que de telles idées ne sont que des mythes. En effet : – L’augmentation de la taille des tampons dans les différents noeuds du réseau causera des délais d’attente plus grands. Nagle a montré dans [76], et [77] que même si les routeurs disposaient d’une file d’attente infinie, la congestion serait en fait bien pire. Ceci est lié au fait que le temps mis par les paquets pour atteindre la tête de la file est largement supérieur au temps imparti à la transmission d’un paquet (time out). Il en découle que des paquets dupliqués risquent d’arriver sur les entrées du routeur car les sources ont, elles aussi, atteint le temps au bout duquel elles doivent retransmettre un paquets qui n’a pas été acquitté. Tous ces paquets seront donc retransmis plusieurs fois aux routeurs suivants, ce qui augmente d’autant la surcharge du réseau sur la quasi-totalité des destinations. – L’accroissement des débits supportés causera une mésalliance entre les différents acteurs du réseaux aggravant ainsi de plus en plus la congestion. – L’amélioration des vitesses des processeurs dans les différents noeuds du réseau quant à elle ne garantira pas de pallier ce problème. Pour étayer ses propos, il nous donne l’exemple suivant (Fig. 2.9) qui montre que l’introduction d’une liaison haut débit, sans l’adjonction d’un mécanisme de contrôle de congestion adéquat, peut conduire à une réduction considérable des performances. En effet, on s’attendait à réduire le délai de bout en bout du transfert du fichier. Or, ce que c’est passé est tout à fait l’inverse : le temps de transfert est passé de 5 min à 7 heures ! Ceci est justifié par le fait que le débit à l’entrée du premier routeur est devenu largement plus important qu’à sa sortie, conduisant à l’accumulation puis à la perte de paquets dans sa file d’attente. Or, les pertes de paquets donnent lieu à des retransmissions des paquets perdus, qui à leur tour, se font avec un très fort taux de perte et ainsi de suite jusqu’à ce que le fichier soit entièrement transféré. 46

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.9 – L’introduction d’une laison à haut débit n’a fait qu’aggraver la situation. Cet exemple nous illustre à merveille que le contrôle de congestion devient primordial lorsque le réseau est hétérogène, c’est à dire lorsque des liaisons hauts débits sont connectées à des réseaux de plus faibles débits. La congestion à l’interconnexion devient un véritable problème, et les performances obtenues peuvent être inférieures à celles précédant l’intégration de la liaison haut débit. Ainsi, le renforcement d’un seul élément d’un système ne permet pas d’améliorer fortement ses performances ; le plus souvent cela se traduit par un simple déplacement du problème. Le vrai problème est la différence de performances qui existe entre les éléments du système. De ce fait, la congestion persistera aussi longtemps que cette différence demeure [92].

2.10.2

Difficultés supplémentaires

Le contrôle de congestion est plus ardu à résoudre dans les réseaux haut débit ! Ceci est justifié par les points suivants : – Les liaisons à haut débit doivent coexister avec les liaisons à faible débit. En effet, pour des raisons économiques, on ne peut pas se permettre de changer toutes les liason à faible débit par d’autrtes à haut débit ; – Le produit bande passante-délai est très élevé rendant le contrôle de flux par fenêtre inapplicable ; – La congestion survient plus vite que dans les réseaux à faible débit. Par exemple, si on dispose d’un buffer de taille 64 kilo octets, les résultats montrent que la congestion surviendra chaque 8.2 secondes si le lien d’entrée a une capacité de 64 ko/s, et seulement à chaque 0.52 millisecondes si le lien d’entrée a une capacité de 1 gigabit/s ; – Le trafic est très sporadique dans ce type de réseaux, ce qui rend imprévisible la bande passante que l’on doit lui allouer ; – La qualité de service des connexions déja établies doit être toujours garantie ; – Hétérogénéité des services supportés par ces réseaux, etc. 47

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.10 – Principe du contrôle d’admission

2.11

Contrôle de Congestion dans ATM

Le contrôle de congestion dans ATM correspond aux actions prises par le réseau afin de minimiser l’intensité, la durée et l’étendue de la congestion. Malheureusemnt, la plupart des schémas de contrôle de congestion conçus pour les réseaux à commutation de paquets ne sont pas applicables pour les réseaux ATM, et ceci à cause des raisons que nous avons citées ci-dessus. Par conséquent, d’autres protocoles prenant en compte les caractéristiques des réseaux à haut débit ont été conçus et proposés dans la littérature [80]. Dans cette section, nous étudierons les les plus connus de ces algorithmes.

2.11.1

Fonction de Contrôle d’admission (Call Admission Control )

Pendant la négociation du contrat de trafic la source doit caractériser le trafic qu’elle va présenter au réseau. Un paramètre de trafic est défini comme la spécification d’un aspect particulier du trafic, tel que son débit crête, son débit moyen, sa taille maximale de rafale, etc. Un paramètre de trafic peut être qualitatif (par exemple, la source déclare qu’il s’agit d’un service téléphonique) ou quantitatif (en termes de paramètres de QoS). Le descripteur de trafic est un ensemble ou une liste de tous les paramètres de trafic qui peuvent être utilisés par une source pour caractériser son trafic [33]. Dans la recommandation I.371 [50] de l’UIT, le contrôle d’admisssion a été défini comme étant "l’ensemble des actions prises par le réseau pendant la phase d’établissemnt de l’appel (ou durant la renégociation de l’appel) pour établir si une connexion peut être acceptée ou doit être rejetée". La définition de la même fonction est donnée de façon très similaire dans L’ATM Forum. Une connexion ne peut être acceptée que s’il y a des ressources disponibles, dans tous les éléments du réseau que la connexion traverse, pour garantir la QoS négociée tout en continuant de respecter les engagements pris avec les autres connexions préalablement établies [17], [87]. La fonction 48

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

CAC est invoquée pour chaque lien du réseau ATM entre le point d’origine de l’appel et la destination. 2.11.1.1

Problème de la bande passante équivalente

La complexité du trafic hétérogène dans les réseaux haut débit rend la décision d’accepter un nouveau appel très difficile. En effet, dans un mode de transfert utilisant un multiplexage déterministe la décision d’admettre une nouvelle connexion peut être basé tout simplement sur le débit crête (PCR) requis par l’appel et de la bande passante disponible dans le réseau au moment de l’arrivée de cet appel. Par contre , dans le cas d’un mode de multiplexage statistique, une telle décision pour un nouveau appel est plus compliquée car les exigences en bande passante des débits crêtes peuvent dépasser la capacité du lien de sortie. Dans ATM, le réseau ne réserve pas explicitement une bande passante aux différentes connexions. Par contre, le besoin en bande passante est calculé selon plusieurs approches qu’on trouvera dans [18]. Il est possible de développer des algorithmes de CAC en se basant sur des hypothèses de trafic. Par exemple, si on suppose que les trafics sont poissoniens, l’étude de la file M/D/1/k permet d’indiquer le montant de ressources nécessaires pour accepter la connexion (voir Chapitre 4). De même, si on fait l’hypothèse que le trafic est de type ON/OFF (rafales suivies de silences de longueurs exponentiellement distribuées), il est possible de développer un algorithme de contrôle d’admission correspondant [40]. Dans la littérature, beaucoup d’algorithmes de contrôle d’admission ont été proposés : 2.11.1.2

Contrôle d’admission basé sur les paramètres de la connexion

Ce type d’algorithmes utilise les caractéristiques d’une connexion qui sont spécifiées par l’usager pour décider s’il va accepter ou rejeter cette connexion [57]. Ce type d’algorithmes peut être à son tour divisé en deux sous-classes : algorithmes à allocation statistique et ceux à allocation non-statistique. Contrôle d’admission à allocation non statistique Les algorithmes à allocation non statistique (appelée aussi allocation par débit crête) forment la classe la plus simple parmi tous les algorithmes de contrôle d’admission. La seule information requise pour faire une décision sur l’acceptation ou le rejet d’une connexion est le debit crête (PCR). Le principe est de s’assurer que la somme des ressources requises est bornée par la capacité du lien de sortie. Le problème majeur de tels algorithmes est qu’il n’y a pas de gain statistique. Cependant, vu leur simplicité et la très bonne qualité de service (aucune cellule n’est perdue) qu’ils offrent, ces algorithmes ont été largement implémentés dans les commutateurs ATM. Contrôle d’admission à allocation statistique Ces algorithmes ont une philosophie plus compliquée : ils n’acceptent pas une connexion en se basant seulement sur le débit crête mais plutôt la bande passante allouée est si49

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

tuée entre le débit crête (PCR) et le débit moyen (MCR). Par conséquent, il peut arriver que la somme des débits crête dépasse la bande passante du lien de sortie causant ainsi des pertes de cellules. L’avantage de ces algorithme est le gain statistique considérable qu’il permettent d’offrir surtout pour des sources sporadiques. Par contre, dans des situations de congestion sévère, ils deviennent très difficiles à manipuler [80]. 2.11.1.3

Contrôle d’admission basé sur les mesures

Ces algorithmes utilisent les mesures pour estimer la charge courante du trafic existant. Par conséquent, ils ne peuvent être évalués qu’en utilisant des réseaux ATM déja existants ou en utilisant la simulation [96]. Ces algorithmes facilitent la tâche de l’usager qui n’est pas obligé à chaque fois de spécifier les paramètres de sa connexion. 2.11.1.4

Contrôle d’admission basé sur la bande et la capacité du buffer

Dans les algorithmes basés sur la la bande et la capacité du buffer, chaque session est représentée par un couple (σ, ρ) où σ et ρ représentent respectivement l’espace dans le tampon et la bande passante allouée à la connexion dans chaque commutateur. Un tel schéma garantit la qualité de service pour la connexion et s’avère très flexible car la taille du buffer et la bande passante peuvent être dynamiquement alloués en se basant sur les ressources existantes et les connexions déja admises. La taille du buffer σ peut être diminuée en augmentant la bande passante ρ et vice versa [20]. D’autres fonctions CAC existent dans la littérature . Le lecteur intéressé peut consulter par exemple [6], [17], [18], et [31].

2.11.2

Fonction de Contrôle des paramètres de l’utilisateur (UPC, User Parameter Control )

La fonction CAC est responsable de l’admission de nouvelles connexions réseau si celui-ci peut satisfaire la qualité de service exigée. Par contre, cette fonction n’a aucun sens si aucun mécanisme d’UPC n’est utilisé. En effet, les utilisateurs peuvent intentionnellement ou non excéder les paramètres de trafic déclarés lors de l’établissement de la connexion. Par conséquent, ceci peut surcharger le réseau. Pour éviter un tel scénario, une fonction de contrôle des paramètres de l’utilisateur (UPC,User Parameter Control ) doit être définie aussi proche que possible de la source du trafic. L’objectif de l’UPC est de détecter toute violation du contrat de trafic établi et de prendre les actions appropriées. Seul le débit crête doit être obligatoirement contrôlé. Les actions que peut réaliser une fonction d’UP sont les suivantes [56], [63] : – laisser passer la cellule ; – retarder la cellule ; 50

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.11 – Principe du seau percé (leaky bucket) – rejeter la cellule ; – marquer la cellule avec un bit CLP positionné à 1 ; – informer l’entité qui gère la connexion pour que celle-ci décide de fermer la connexion. Une fonction UPC idéale doit être capable de détecter les cellules violant les paramètres déclarés, transparente aux connexions respectant leurs paramètres d’admission et son temps de réponse Divers mécanismes ont été proposés pour implémenter l’UPC. On peut citer par exemple : la fenêtre glissante (sliding window ) et la fenêtre sautante (jumping window ) [31].

2.11.3

Canalisation du trafic (traffic shaping )

L’une des cause principales de la congestion provient du fait que le trafic est aléatoire et très souvent sous forme de données en rafales (bursts) ou en saccades incontrôlées. Une des techniques de contrôle de congestion en boucle ouverte qui permet d’améliorer sensiblement le traitement de la congestion en s’efforçant de maintenir le trafic le plus constant possible dans le réseau est la canalisation du trafic (traffic shaping) qui consiste à réguler la vitesse et le rythme saccadé d’écoulement des données dans le réseau. En comparaison ,la fenetre coulissante du protocole TCP limite la quantité de données A cet effet, L’algorithme du seau percé (leaky bucket) a été défini pour la première fois par Turner [97]. Imaginons un seau d’eau dont le fond est percé d’un trou par lequel l’eau s’écoule en goutte à goutte. Peu importe à quel débit l’eau arrive dans le seau, son écoulement par le trou se fait à une vitesse constante tant qu’il y a de l’eau dans le seau ; l’écoulement s’interrompt dès qu’il n’y a plus d’eau dans le seau. Evidemment, lorsque le seau est plein le surplus d’eau arrivant est perdu, le seau déborde sans que 51

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.12 – Principe du seau percé à jetons cela n’influe sur l’écoulement de l’eau par le trou (Fig. 2.11). Ce principe peut être transposé sans difficulté à la transmission de paquets dans un réseau : un ordinateur n’est autorisé à insérer un paquet dans le réseau qu’à chaque top d’horloge. Ainsi, ce mécanisme transforme un flux irrégulier de paquets provenant d’un processus client interne à un ordinateur source en un flux régulier de paquets sur le réseau permettant ainsi de faire disparaître les pics de trafic qui causent souvent des phénomènes de congestion . Une amélioration du seau percé est l’algorithme du seau percé à jeton (token bucket) ( Fig. 2.12). L’idée de base de cet algorithme est la suivante : quand une nouvelle cellule arrive dans le réseau elle doit se procurer un ticket (token) d’un seau de taille β qui contient des jetons . Un fois la cellule transmise, le nombre de jetons est décrémenté. Si la cellule ne trouve aucun jeton, alors elle doit soit attendre s’il a assez de places dans la file d’attente qui d’une taille K ; soit rejetée si le file d’attente est pleine. La génération des jetons se fait à un débit ρ

2.11.4

Gestion Passive de la file d’attente

La gestion passive de la file d’attente (Passive Queue Management) est la méthode la plus simple pour supprimer les paquets en cas de congestion. Son principe est de rejeter tout paquets arrivant quand la file est pleine. Plusieurs versions ont été proposées dans la littérature pour implémenter cette méthode. Nous en étudierons quelques une dans cette section. 2.11.4.1

La méthode Drop Tail

L’algorithme du Drop tail est le plus simple des algorithmes de rejet de paquets. Son principe est de rejeter tout paquets arrivant lorsque les files d’attente dans les routeurs sont pleines. Aucune notification explicite de perte ne sera envoyée aux sources. 52

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

En effet, il incombe au protocole TCP de détecter implicitement ces pertes soit par l’expiration des temporisateurs, soit par les acquittements reçus. L’avantage du Drop tail est sa simpilcité de mise en oeuvre. En revanche, Drop Tail a plusieurs inconvénients. Le premier inconvénient est qu’il n’est pas capable de faire une isolation entre les differents flux, ce qui sera très gênant pour les application temps réel telles la vidéo, l’audio, et la vidéoconférence. L’inéquité est un autre problème dont souffre Drop Tail. En effet, les connexions avec un large RTT (Rount Trip Delay) ont tendance à augmenter les tailles de leurs fenêtres de façon plus lente que celles (les connexions) qui ont des RTTs plus petits. Un troisième inconvénient est le fait de ne pas agir contre les sources qui se comportent de façon illégale, et ne répondent pas aux indications de congestion (implicites ou explicites) et qui transmettent plus qu’il leur est toléré. ces sources occuperont un grand espace dans les files d’attente des routeurs augementant aisi les taux de perte pour les autres sources qui se comportent de façon lus ou moins légale. 2.11.4.2

la méthode Drop from Front

D’autres approches ont été proposée dans la littérature qui différent un peu de Drop Tail. Lakshman et al proposent de rejeter les paquets à partir de la tête de la file d’attente au lieu de la queue quand la file est pleine . Une telle approche est dite Drop from Front. dans cette approche, TCP va détecter les pertes de paquets plus rapidement que dans Drop Tail. D’autre part, Drop from Front améliore le débit et l’équité en évitant des pertes sporadiques et en évitant les synchronisations entre les différentes sources.

2.11.5

Contrôle de flux pour la classe ABR (Available Bit Rate)

Dans les cas des trafic CBR et VBR, il est impossible de demander à l’émetteur de réduire sa production de cellules, même en présence de congestion, étant donné le caractère temps réel des flux d’information. Par contre, dans le cas d’un trafic UBR (Unspecified Bit Rate) ceci est possible. La capacité de transfert ABR se caractérise par le fait que la bande passante utilsable varie au cours du temps après l’établissement de la connexion, et peut éventuellement atteindre des valeurs très élevées proches de la bande passante de la ligne de transmission. L’idée maîtresse de la capacité ABR (Available Bit Rate) est la suivante : une fois une connexion établie, les ressources du réseau seront mieux utilisées si la source s’adapte à l’état du réseau plutôt l’inverse. Une fois une connexion ABR établie, deux types de contrôle de flux doivent être exécutés par le réseau – Les différents éléments du réseau doivent calculer les ressources disponibles pour la connexion et en informar la sources tout au long de la connexion 53

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

– L’UPC doit contrôler que la source obéit au comportement de référence. Après de nombreuses discussions et de longs débats [84], deux propositions furent particulièrement appréciées. L’une proposée par Kung et Morris [66] était basée sur un crédit d’accès, l’autre proposée par Bonomi et Fendick [11] était basée sur le débit moyen. On trouvera dans [59] et [89] une synthèse sur les différentes méthodes de contrôle de flux pour la classe ABR.

2.11.6

Réservation rapide de ressources (Fast Resource Management)

Souvent, il est très difficile de caractériser des flux très sporadiques avec les paramètres de trafic proposés par l’UIT. Pour faire face à ce problème, une autre approche a été proposée dont le principe est le suivant : la source donne des informations sur le trafic pendant la connexion. par exemple, la source peut informer le réseau avant de transmettre une nouvelle rafale. Par conséquent, le réseau pourra faire une réservation de ressources afin de satisfaire cette demande. ce principe est appelé réservation rapide de ressources. On trouve dans la littérature deux deux protocoles de ce types et qui sont proposé par le Centre National d’Etudes des Télécommunications de France (CNET). dans le premier protocole appelé FRP/DT (Fast Reservation Protocol with Delayed Transmission), la source attend une confirmation du réseau avant de transmettre la rafale. Ainsi, la qualité de service en terme probabilité de perte de cellules est garantie pour les rafales acceptées. Avec le deuxième protocole appelé FRP/IT (Fast Reservation Protocol with Immediate Transmission), la source envoit la rafale tout de suite après la cellule de réservation. Dans ce cas, la rafale est perdue s’il n’y a pas de ressources disponibles dans le réseau. Notons que le protocole FRP-IP est mieux adapté aux services temps réel tandis que le FRP-Dt est meiux adapté aux services de données pour lesquels le retard des rafales ne pose pas de problème. La proposition de la réservation rapide de ressources n’a pas été accepté à l’ATM Forum. Cette proposition faite par France Telecom requiert qu’une source envoie des cellule de contrôle (RM cells). Dans la littérature on trouve d’autres solutions essayant de faire en sorte que les différents schémas de contrôle de congestion étudiés supra "coopèrent" entre eux afin d’aboutir à de meilleurs performances. Ces approches utlisent l’intelligence artificielle et les systèmes multi-agent (voir par exemple [36] et [35]).

54

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.13 – Congestion due au choix du plus court chemin.

2.12

Ingénierie de trafic et contrôle de congestion dans MPLS

Dans cette section ,nous abordons très brièvement la notion d’ingénierie de trafic dans les réseaux MPLS. Par ingénierie de trafic (TE, Traffic Engineering), on veut dire le processus qui tente de balancer le trafic de manière à éviter la congestion dans un réseau et d’optimiser l’utlisation des ressources du réseau [101],[100],[43], [86]. En effet, dans les réseaux classiques, le trafic est routé en se basant sur le principe saut par saut (hop by hop) et le protocole IGP (Internet Gateway Protocol ) utilise toujours l’algorithme du plus court chemin OSPF (Open Shortest Path First) pour acheminer le trafic. Or, OSPF présente deux grands inconvénients[18] : 1. les plus courts chemins de plusieurs connexions peuvent se chevaucher sur un lien commun causant ainsi une congestion sur ces liens ; 2. Le trafic émanant d’un routeur source à un routeur desination peut excéder la capacité des plus courts chemins alors que les chemins les plus longs entre ces deux routeurs sont sous-utlisés. Nous donnons ici un exemple d’ingénierie de trafic dans MPLS tiré de [18]. La figure 2.13 montre un domaine MPLS ayant 8 routeurs. Il y a deux chemins menant du routeurs C au routeur E. Ces deux chemins sont indiqués sur la même figure par 1 et 2. Si le routeur applique l’algorithme du plus court chemin de C à E (qui est C-D-E), alors ce chemin supportera tout le trafic destiné pour E et passant par C. Ceci peut évidemment causer une congestion tandis que l’autre chemin C-F-G-H-E est inutilisé. Afin de maximiser la performance globale du réseau, il serait intéressant de contourner une fraction du trafic d’un lien du réseau à l’autre. Pour résoudre ce problème, 55

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

Fig. 2.14 – Solution au problème de congestion par ingénierie du trafic. l’IETF (Internet Engineering Task Force) a introduit le routage basé sur contraintes (constraint-based routing)[23] et une amélioration au protocole IGP appelée "enhanced link state IGP". Avec l’aide de MPLS, une solution peut être apportée au problème de congestion en utilisant un équilibrage de charge (load balancing). Par exemple, on voit dans la figure 2.14, MPLS a balancé la charge de telle sorte que le réseau soit utlisé de façon efficace. L’ingénierie du trafic offre plusieurs avantages, à savoir [3] : 1. Avec MPLS, les capacités d’ingénierie du trafic sont intégrées à la couche 3, ce qui optimise le routage du trafic IP en fonction des contraintes imposées par la capacité et la topologie du backbone ; 2. Elle achemine les flux de trafic IP à travers le réseau en se basant sur les ressources dont le flux a besoin, et sur les ressources diponibles dans le réseaux ; 3. Elle utilise le routage basé sur les contraintes (constraint-based routing)dans lequel un chemin pour un flux est choisi selon la distance, la bande passante requise, et la priorité du flux ; permettant ainsi de garantir une bonne qualité de service ; 4. Elle permet de s’adapter à un nouvel ensemble de contraintes en cas de présence de défaillance dans les liens du réseau ou en cas de changement de la topologie du réseau.

56

Chapitre 2 : Contrôle de congestion dans les réseaux haut débit

2.13

Conclusion

Dans ce chapitre, nous avons mis en évidence le fait que les technologies haut débit, tellement attendues pour résoudre le problème de congestion, n’ont fait qu’aggraver la situation. Par conséquent, il faut investir d’avantage dans la conception de nouveaux mécanismes et protocoles pour faire face à ce problème. Nous avons également vu que organismes de standardisation de ATM préconisent un contrôle préventif pour garantir une certaine qualité de service. Cependant, le contrôle réactif est aussi présent notamment pour la classe de service ABR. Le choix d’un mécanisme donné au détriment d’un autre se fait selon une métrique de performance. Cette dernière peut être objective (vision du concepteur du réseau) ou subjective (vision des utilisateurs). Nous verrons dans le chapitre qui suit quelques problèmes liés à l’évaluation des performances de réseaux ATM.

57

Chapitre

3

Evaluation de Performances des Réseaux ATM

"Contrary to common belief, performance evaluation is an art." Raj Jain [54]

3.1

Introduction

L

ES administrateurs, les utilisateurs et les concepteurs de systèmes informatiques sont tous intéressés par l’évaluation de performances. En effet, si on néglige l’étape de l’évaluation et on passe directement à l’implémentation réelle et la mise en oeuvre du système, les coûts peuvent être sévères en cas de non-conformité du système aux exigences temporelles requises pour les applications. Prenons comme exemple les réseaux ATM : quand des centaines ou des milliers de réseaux d’ordinateurs sont interconnectés, il se produit des interactions complexes aux conséquences parfois imprévisibles. Cette complexité conduit souvent à des performances médiocres sans même que l’on sache pourquoi. Par conséquent, on doit recourir à des méthodes et des techniques pour éviter de tels scénarios. La nécessité de l’évaluation de performances des réseaux ATM commence à partir de la phase d’installation et jusqu’à la mise en oeuvre opérationelle du réseau. Lorsque le réseau est installé et les indices de performances sont évalués, on pourra s’intéresser à un choix meilleur de la configuration du système. Ainsi, il convient de comparer les performances de deux ou plusieurs réseaux. Notons que l’évaluation de performance peut se faire de deux manières : qualitative et quantitative. L’aspect qualitatif implique l’utilisation de méthodes efficaces capables de contrôler le comportement logique du système alors que l’aspect quantitatif comprend l’utilisation de méthodes permettant d’obtenir les paramètres numériques dans le but d’analyser les performances du système.

58

Chapitre 3 : Evaluation de performances des réseaux ATM

Fig. 3.1 – Processus de modélisation

3.2

Les deux étapes de l’évaluation de performances

L’évaluation de performances peut être partagée en deux étapes distinctes, à savoir : la modélisation qui consiste en le développement d’une description formelle du système ; et la résolution qui consiste en l’obtention des prédictions de performances du système [27].

3.2.1

Modélisation

la modélisation (modelling) joue un rôle primordial dans la conception ou la maintenance des systèmes informatiques, de production et de télécommunications. Avant d’introduire la notion de modèle, nous définissons d’abord la notion de système. Définition 1 (Système) Un système est définie comme étant un ensemble d’éléments qui interagissent entre eux afin de résoudre un tâche bien déterminée. Parfois, il impossible d’étudier le système directement du fait qu’il soit inaccessible, ou trop coûteux pour qu’on puisse l’expérimenter directement. Par conséquent, on fait recours à des modéles. Un modèle est défini comme suit : Définition 2 (Modèle) Un modèle est une représentation de la réalité dans un formalisme donné. Il est développé pour répondre à des questions déterminées et comporte certaines limitations, c’est une abstraction du système réel [9]. Le choix d’un modèle dépend essentiellement de la mesure de performance qui nous intéresse. A partir du modèle, nous voulons obtenir des résultats sur le système étudié. Certains résultats peuvent nous amener à modifier notre vision du système, et nous inciter à calculer de nouveaux résultats sur le modèle. Pour cela, nous pouvons être amenés à complexifier le modèle pour rajouter des informations. De même, nous pouvons nous rendre compte que certains résultats ou éléments du modèle sont inutiles 59

Chapitre 3 : Evaluation de performances des réseaux ATM

Fig. 3.2 – Illustration des Critères de Performance. pour calculer les indices de performances recherchés, et par conséquent, nous pouvons ainsi parfois simplifier le modèle pour faciliter sa résolution. Pour finir, nous comparons les résultats obtenus avec le comportement du système réel , et nous pouvons alors concevoir le système qui donne les performances optimales. L’avantage de la modélisation par rapport aux mesures directes est qu’elle peut être employée aussi bien pendant les phases de conception d’un système que durant les phases de l’exploitation opérationnelle.

3.2.2

Résolution

Dans cette deuxième phase, la question que l’on se pose est la suivante : " Quels sont les critères (ou les indices) de performance qui nous intéresssent ? " Ces critères peuvent êtres définis principalement selon trois angles de vue [46] : point de vue de l’utilisateur, celui de l’administrateur, et enfin celui du concepteur du réseau. Ces critères sont parfois contradictoires comme c’est illustré dans la figure 3.2. L’utilisateur s’intéresse à son expérience avec le réseau et non à la performance technique de celui-ci comme c’est le cas de l’administrateur. Généralement, il s’intéresse aux délais de bout en bout mais d’autres critères peuvent l’intéresser également : disponiblité du système à tout moment, confidentialité des données, équité du réseau, etc . L’administrateur, quant à lui, voudrait maximiser l’utilisation du réseau pour en tirer un maximum de profit. Enfin, le concepteur mesure la performance du réseau dans le but de vérifier comment la performance actuelle s’accorde avec la performance prédite. Il s’intéresse surtout à la capacité des rampons de stockage, à l’efficacité des protocoles de communication et à l’efficacité du contrôle de flux.

60

Chapitre 3 : Evaluation de performances des réseaux ATM

3.3

Taxonomie des méthodes d’évaluation de performances

L’évaluation de performances des réseaux ATM fait appel à plusieurs méthodes qui peuvent être classée en trois classes principales : méthodes analytiques, mesures, et simulation. Le tableau 3.1 fait une étude comparative entre ces trois classes de méthodes [54]. Dans ce qui suit, nous présentons de façon plus détaillée ces trois classes de méthodes avec la discussion des avantages et inconvénients de chaque méthode.

3.3.1

Les mesures

L’objectif principal de cette technique est de cumuler les statistiques sur les événements divers, des les interpréter en termes de performances du sustème opérationnel et de régler les paramètres du réseau pour atteindre la performance la plus optimale possible. Ces techniques permettent de comprendre le vrai comportement du système, mais faire des mesures sur des systèmes réels n’est pas toujours possible car ceci pourrait gêner le fonctionnement du système ou aussi pour des problèmes de coûts (système non encore existant, instruments de mesure complexes, etc). On peut classifier les mesures de performances en deux catégories : mesures orientées utilisateurs et mesures orientées système [65]. Les mesures concernat l’utlisateur sont souvent subjectives : elles peuvent différer d’un utlisateur à l’autre. Ainsi, un réseau est performanr pour un utlisateur donné alors qu’il ne l’est pas pour un autre utlisateur. La réalisation des mesures nécessite l’emploi de deux types de moniteurs : des moniteurs matériels (hardware monitors) et des moniteurs logiciels (software monitors). Les moniteurs matériels servent à observer l’état des composantes matérielles du réseau et de faire des statistiques sur le nombre d’évènements durant un intervalle de temps bien déterminé ; ces évènements peuvent être ,par exemple, le nombre de messages entrant et quittant le réseau, l’utilisation d’une ressource, etc. L’avantage principal de ce type de moniteurs est la précission des résultats obtenus. Les moniteurs logiciels sont constitués de routines du système. Ils cumulent l’information concernant le statut du système. On distingue deux types de moniteurs logiciels : moniteurs à traçage d’évènements et moniteurs échantillonneurs. Un moniteur à traçage d’évènements fournit des statistiques concernant la façon dont progresse les demandes individuelles dans le système. Par exemple, le nombre de noeuds qu’un message traverse avant d’atteindre sa destination et le temps de réponse d’un message. Un moniteur échantillonneur tient le statut instantané du système dans des intervalles périodiques. Il donne des statistiques momentanées comme les longueurs des files d’attente au niveau des noeuds. selon un autre angle de vue, les moniteurs logiciels peuvent être intrusifs ou non in61

Chapitre 3 : Evaluation de performances des réseaux ATM

trusifs. Les premiers altèrent le comportement du système car il génèrent des données de contrôle supplémentaires, tandis que les deuxièmes sont passifs et, par conséquent, les mesures qu’il fournissent reflètent le vrai comportement du système. Souvent, il est nécessaire de tester la validité d’un moniteur logiciel en le comparant à un moniteur matériel. Il existe une troisième catégorie de moniteurs appelés moniteurs hybrides qui combinent les avantages des moniteurs matériels (vitesse et précision) avec ceux des moniteurs logiciels (flexibilité et accès aux informations logicielles).

3.3.2

Méthodes analytiques

Quand on parle de méthodes analytiques, on entend des méthodes qui nous permettent d’écrire une relation fonctionnelle entre les paramètres d’entrée du système et les critères de performance qui nous intéressent [99]. L’avantage de ces méthodes est qu’elles nécessitent un effort minimal et un coût réduit. Cependant, il arrive que l’on s’affronte dans certaines situations à des systèmes dont la modélisation devient très ardue et quasi impossible. Pour évaluer les performances d’un système, les méthodes anlytiques réduisent le système en un modèle mathématique et l’analysent numériquement. Cette approche est parfois rapide à réaliser, mais présente le souci de la représentation fidèle du système. Il parfois très complexe (voire impossible) de modéliser le comportement réel du système considéré mathématiquement. Généralement, on se pose des hypothèses qui simplifient l’étape de modélisation du système et rendent l’évaluation numérique faisable. Il existe dans la littérature plusieurs méthodes analytiques : 1. Les chaînes de Markov (Markov chains) ; 2. Les sytèmes de files d’attente (queuing systems) ; 3. Les automates à états finis (Finite State Automata) ; 4. Les réseaux de Pétri (Petri nets) ; 5. Les approches probabilistes ; 6. Les approches déterministes : analyse du pire temps de réponse, Network Calculus [12], etc. Parmi ces méthodes , les chaînes de Markov et la théorie des files d’attente (queuing theory) jouent un rôle très important dans l’analyse de performances des réseayx ATM. A cet effet, nous les étudierons de façon plus détaillée.

3.3.3

La simulation

Vu la complexité et la taille des réseaux actuels tels que les réseaux basé sur le protocole TCP/IP et les réseaux ATM, il devient très difficile de faire des investigations 62

Chapitre 3 : Evaluation de performances des réseaux ATM

sur les valeurs de performances en utilisant des méthodes analytiques. Par conséquent, le recours aux techniques de simulation est obligatoire. L’utilisation de la simulation est préconisée notamment, lorsque le processus original : – est trop rapide pour qu’on puisse suivre son évolution avec les instruments à disposition (réactions chimiques, processus physiques), – est trop lent pour qu’on puisse en mesurer le comportement en un temps utile (croissance des arbres, mouvements migratoires, évolution des espèces), – est trop dangereux ou occasionnerait trop d’ennuis à l’entourage si l’on l’expérimentait (réaction nucléaire, simulateur de vol) ; – n’existe pas encore (processus industriels, systèmes de transport) – est trop cher pour que l’on puisse en tester le comportement de plusieurs variantes. Le champ d’application de la simulation ne se limite pas aux questions quantitatives. En particulier, elle est aussi utilisée avec succès à la vérification et la validation du bon fonctionnement de mécanismes complexes. Les différentes méthodes de simulation peuvent être classifiées selon plusieurs critères : (i) modèles de simulation dynamiques versus modèles de simulation statiques, (ii) modèles de simulation déterministes versus modèles de simulation stochastiques et (iii) modèles continus versus modèles discrets [13], [71]. Un modèle de simulation statique est une représentation d’un système dans un temps particulier, ou un modèle dans lequel le temps ne joue aucun rôle. Un exemple d’un tel modèle est le modèle de simulation "Monte Carlo". Par contre, un modèle de simulation dynamique est un modèle qui représente comment un système évolue dans le temps. Si un modèle de simulation ne contient pas de composant qui se comporte de façon stochastique (autrement dit de façon aléatoire) alors il est dit modèle déterministe. Dans un tel modèle, les entrées sont déterminées à base des entrées spécifiées du modèle. Malheureusement, la plupart de systèmes réels contiennent des composantes ayant un comportement aléatoire. de tels systèmes ne doivent pas alors être simulés par un modèle de simulation déterministe mais bien au contraire par un modèle de simulation stochastique. La simulation à temps continu s’intéresse à l’évolution d’un système dont les variables d’état change continuellement avec le temps. Ce type de simulation nécessite l’utilisation d’équation différentielles. En revanche, la simulation à évènements discrets s’intéresse à la modélisation d’un système dans le temps, mais cette fois en ne considérant que des instants particuliers dans le temps.

3.4

Chaînes de Markov

Les chaînes de Markov constituent un moyen robuste, flexible, et efficace pour la représentation et l’analyse des propriétés dynamiques d’un système informatique 63

Chapitre 3 : Evaluation de performances des réseaux ATM

Critère

Méthodes analytiques

Simulation

A Quel stade l’utiliser

n’importe

n’importe

Temps requis

court

moyen

Outils utilisés

humain

ordinateurs

Exactitude

dépend du modèle

modérée

Coût

bas

moyen

Mesures le système à étudier doit exister long moniteurs matériels ou logiciels variable haut

Tab. 3.1 – Comparaison des trois classes de méthodes d’évaluation de performances [8]. En principe, chaque système de files d’attente peut être traduit sous forme de processus de markov et par conséquent être évalué mathématiquement par celui-ci. Les processus de Markov constituent la classe la plus classe la plus importante des processus stochastiques alors que ces derniers peuvent être considérés comme un généralisation des variables aléatoires. On distingue deux types de chaînes de Markov : chaînes de Markov à temps continue (CTMC, Continuous Time Markov Chain) et les chaines de Markov à temps discret (DTMC, Discrete Time Markov Chain). Une chaîne de Markov à temps discret présente la propriété usuelle des procesus de Markov : son comportement futur dépend seulement de sont état courant et non pas des états passés par lesquels elle a éventuellement passé. Soit l’ensemble des états S = {0, 1, 2, ...}. Alors, la propriété de markov a la forme suivante : Pr(Xn+1 = in+1 /X0 = i0 , .., Xn = in ) = Pr(Xn+1 = in+1 /Xn = in )

(3.1)

Où i0 , .., in+1 ∈ S. Une chaîne de Markov à temps discret peut être représentée graphiquement par un graphe dont les sommets représentent les états et les arcs représentent les transistions. La figure 3.3 montre un exemple d’une chaîne de Markov [42]. Une chaîne de markov peut aussi être représentée par sa matrice de transition : P = (pi,j ) . Par exemple, pour la figure 3.3, la matrice de transition est donnée par :

P =





1    10 

6 2 2   1 8 1   6 0 4

(3.2)

Cette matrice de transition est toujours une matrice stochastique : la somme des éléments de chaque ligne est égal à 1. Autrement dit, chaque ligne est un vecteur stochastique. Un de prblèmes majeurs auxquel s’affronte la modélisation markovienne est l’explosion de l’espace des états. Par conséquent, plusieurs approches ont été introduites pour réduire la taille de l’espace des états [27]. En pratique, plusieurs systèmes réels peuvent être modélisés à l’aide des chaînes de 64

Chapitre 3 : Evaluation de performances des réseaux ATM

Fig. 3.3 – Diagramme de transition d’une chaine de Markov. Markov à temps continu. La plupart des propriétés des chaines de Markov à temps discret sont applicables aux chaînes de Markov à temps continu.

3.5

Systèmes de Files d’Attente

La théorie des files d’attente a joué un grand rôle dans la modélisation des systèmes téléphoniques au début du vingtième siècle . Elle continue de jouer ce rôle aussi même dans le domaine des réseaux de communication de données et dans les réseaux de télécommunications [1]. Le modèle général d’un système d’attente (queuing system) peut être résumé comme suit : des " clients " arrivent à un certain endroit et demandent un certain " service ". Les instants d’arrivée et les durées de service sont généralement des quantités aléatoires. Si un poste de service est libre, le client qui arrive se dirige immédiatement vers ce poste où il est servi, sinon il prend sa place dans la file d’attente dans laquelle les clients se rangent suivant leur ordre d’arrivée. Ainsi,un système d’attente contient un espace de service avec une ou plusieurs stations de service montées en parallèle, et un espace d’attente dans lequel se forme une éventuelle file d’attente.

3.5.1

Notation de Kendall

Pour identifier un système à files d’attentes, le formalisme suivant a été proposé pour la première fois par D.G. Kendall en 1953 et ,par la suite, complété par A.M. Lee [70] : A/B/n/K/N (3.3) 65

Chapitre 3 : Evaluation de performances des réseaux ATM

Fig. 3.4 – Système de File d’Attente.

• La première lettre A identifie la loi des processus des arrivées avec les conventions : – M : loi "sans mémoire" (arrivées poissonniennes, service exponentiel)1 ; – D : loi déterministe ; – Ek : loi Erlang-k" – Hk : loi "hyperexponentielle" d’ordre k ; – GI : loi générale, les variables successives étant indépendantes ; – G : loi générale, sans hypothèse d’indépendance. • La deuxième lettre B identifie la durée de service d’un client avec les mêmes conventions pour la loi des arrivées. • La troisième lettre n concerne le nombre de serveurs du système • La quatrième lettre K concerne la taille de la file d’attente. Si elle n’est pas mentionnée, alors elle cinsidérée comme étant infinie. • LA cinquième lettre N concerne la discipline de service de mise en file d’attente : FIFO (First In First Out), LIFO (Last In First Out), Shortest Job First, etc. Donnons un exemple concret : un système M/D/1/k est un système : • dont les arrivées sont poissoniennes, i.e : P r(avoir k arrivees pendant une duree de temps T ) =

• • • •

La durée de service suit une loi déterministe ; Le nombre de serveur est 1 ; La taille de la file est k ; la politique de service est FIFO (First In First Out). 1

M veut dire Markov ou Memoryless

66

(λ.T ) −λ.T .e k!

(3.4)

Chapitre 3 : Evaluation de performances des réseaux ATM

3.5.2

Mesures de performance

Quand on évalue les performances d’un système de files d’attente, on s’intéresse généralement aux mesures pertinentes suivantes [8] : • Nombre de clients dans le système : Il est souvent possible de décrire le comportement d’un système de files d’attente en utilisant le vecteur de probabilité du nombre de clients dans le système Pk : Pk = P (Il y a k clients dans le systeme)

(3.5)

• Taux d’utilisation du serveur : Dans le cas d’un système de files d’attente à un seul serveur, le taux d’utilisation ρ (appelé aussi taux d’occupation du serveur) est la fraction de temps dans laquelle le serveur est occupé. Il est défini par : T emps moyen de service T aux d0 arrivee λ = = (3.6) 0 Temps moyen d inter − arrivees Taux de service µ • Temps de réponse T : le temps de réponse, connu aussi sous le nom du temps de séjour est le temps total qu’un client passe dans le système. • Temps d’attente W : Le temps d’attente est le temps qu’un client passe dans la file d’attente avant d’être servi. Ainsi, on a : ρ=

T emps de reponse = T emps d0 attente + T emps de service

(3.7)

• Longueur de la file Q : la longueur de la file est le nombre de clients qu’elle contient. Dans les réseaux ATM, on s’intéresse généralement à deux critères de performances et qui sont aussi deux paramètres pertinents de qualité de service, à savoir : le délai de bout en bout (end to end delays), et le taux de perte de cellules CLR (Cell Loss Ratio).

3.6

Simulation à évènemets discrets

Dans la simulation des systèmes stochastiques, le paradigme le plus répandu est certainement l’approche par évènements discrets. Cela signifie que le simulateur va sauter d’un événement au suivant. L’exécution d’un événement est instantanée (dans le temps du modèle). Chaque événement engendre d’autres événements. Puisque "il ne se passe rien" entre les événements, c’est à dire puisque les variables significatives n’évoluent qu’à ces instants, il n’est pas utile de considérer les périodes inter-événements.

3.6.1

Notions élémentaires

• Dans une simulation discrète, une variable particulière, appelée horloge (simulation clock ), indique en permanence le temps simulé écoulé depuis le début de la 67

Chapitre 3 : Evaluation de performances des réseaux ATM

simulation. Le temps indiqué par l’horloge de simulation n’a aucune relation directe avec le temps physique réellement écoulé pendant le déroulement de la simulation. • On appellera état d’un système l’ensemble des valeurs prises par les variables décrivant le système : nombre de clients dans le système, nombre de clients servis, etc. • On appellera également système discret un système dans lequel la description d’état ne comporte que des variables discrètes (i.e. à variation non continue). • Les instants d’évolution de l’état surviennent donc de façon "discrète" (c’est à dire qu’il n’y en a qu’un nombre fini dans un intervalle de temps fini). On les appelle des événements.

3.6.2

Génération des nombres aléatoires

La génération de nombre aléatoires est très importante dans les méthodes de simulation. Plusieurs méthodes algorithmiques ont été proposées dans la littérature pour générer des nombres aléatoires. On peut citer par exemple : – La méthode congruentielle multiplicative ; – La méthode congruentielle additive ; – La méthode congruentielle mixte, etc. Généralement, la première méthode est la plus utilisée est la prémière méthode.

3.6.3

Validation du générateur aléatoire

Pour valider un générateur de nombre aléatoire, celui ci doit répondre aux propriétés suivantes : – uniformité : les nombres générés sont uniformes dans l’intervalle ]0,1[ ; – indépendance :les nombressont indépendants entre eux : absence de corrélation entre les nombre générés. ; – efficacité : dans une expérience de simulation, il arrive qu’on refasse des millions de fois la même expérience et, par conséquent, l’algorithme de génération des nombres aléatoires doit être aussi rapide que possible.

3.6.4

Analyse de Convergence des processus simulés

Lorsque on simule un système stochastique, on le fait souvent dans le but d’évaluer son comportement et ses performances. La question que nous pouvons poser alors est la suivante : "Quand faut-il arrêter la simulation ?".Plus précisément, il faut déterminer le nombre de réplications de l’expérience. Une des méthodes les plus utlisée est la méthodes des réplication indépendantes que nous décrivons ci-dessous.

68

Chapitre 3 : Evaluation de performances des réseaux ATM

3.6.5

Méthode des réplications indépendantes

Dans cette méthode on fait passer le programme représentant le modèle de simulation plusieurs fois, en utilisant différentes entrées du générateur, à chaque passage. {Yij } 1 ≤ i ≤ n et 1 ≤ j ≤ m

(3.8)

La moyenne du jième passage est donnée par : Y

(j)

=

(j) n X Yi i=1

n

(3.9)

1≤j≤m

(j)

L’ensemble {Y 1 ≤ j ≤ m} forme m variables indépendantes identiquement dis(j) tribuées. Les estimateurs de la moyenne et de la variance de Y sont : Y =

m m X n 1 X 1 X (j) (j) Y = Y m j=1 m ∗ n j=1 i=1 i

et : SY2 =

3.6.6

m 2 1 X (j) (Y − Y ) m − 1 j=1

(3.10)

(3.11)

Calcul des intervalles de confiance (confidence intervals)

Le calcul des intervalles de confiance est très important pour la validation des résultats d’un simulation. Afin de calculer ces intervalles, nous procédons comme suit : Soit un échantillon X1 , X2 , ..X3 de mesures obtenus pour une simulation donnée. La moyenne de l’échantillon est alors donnée par : X=

n 1X Xi n i=1

(3.12)

A cette moyenne, on pourra alors asocier un intervalle de confiance donné par : n 1 X V ar(X) = (X − Xi )2 n − 1 i=1

(3.13)

On s’intéressse généralement à obtenir une caractérisation plus précise de l’erreur entre la vraie moyenne notée M et la moyenne estimée X. Autrement dit, on cherche à trouver un intervalle Iα =]X − α, X + α[ qui contient la vraie moyenne M avec un probabilité d’au moins (1 − α) ∗ 100 %. α est dit dans ce cas niveau de confiance et Iα intervalle de confiance associé à α. Les valeurs typique de Iα sont 0.1, 0.05 et 0.01. Pour n suffisament grand, l’intervalle de confiance sera donné par : s

Iα =]X − 1.96 ∗

V ar(X) , X + 1.96 ∗ n 69

s

V ar(X) [ n

(3.14)

Chapitre 3 : Evaluation de performances des réseaux ATM

Fig. 3.5 – Un réseau de Pétri à deux places et deux transitions

3.7

Quelques outils pour l’évaluation de performances

Chaque outil de modélisation a sa propre place dans le domaine de l’évaluation de performances. Par exemple, les réseaux de Pétri offrent un moyen graphique aussi bien qu’une méthode de notation pour la spécification formelle de systèmes. Un réseau de Pétri est composé de quatre éléments : des places, des transitions, des arcs ,et enfin des jetons. Une place représente un état dans lequel le système ou une partie du système se trouve. Par exemple dans la figure 3.5 montre une réseau de Pétri à deux places A et B symbolisées chacune par un cercle. Le jeton, situé dans la place A, indique que le système se trouve dans l’état A. Une barre horizontale ou verticale symbolise une transition. Chaque transition peut avoir zéro, un ou plusieurs arcs en entrée provenant des places situées en entrée. Elle peut également avoir zéro, un ou plusieurs arcs en sortie allant vers des places situées en sortie. Un transition est dite franchissable si chacune des de ses places en entrée possède au moins un jeton. Lorsqu’une transition franchissable est franchie, on enlève un jeton de chacune des places d’entrée et on ajoute un jeton à chacune des places en sortie. Plusieurs extensions ont été faites pour les réseaux de Pétri. Par exemple, nous trouvons : – Les réseaux de Pétri stochastiques ; – Les réseaux de Pétri stochastiques généralisés ; – Les réseaux de Pétri de haut niveau (réseaux colorés) ; – Les réseaux de Pétri stochastiques généralisés superposés, etc [8], [32]. Les réseaux de Pétri servent surtout à décrire et à valider les protocoles de communication et les algorithmes d’exclusion mutuelle dans les systèmes d’exploitation. Un autre outil très utlisé aussi pour l’évaluation de performnaces des réseaux ATM est les réseaux de neurones. Ces derners offrent un très bon outil mathématique pour la classification de données. Ils ont été largement utilisés dans le domaine de télécommunications (voir par exemple l’ouvrage [103]). Dans la littérature, on trouve beaucoup d’applications des réseaux de neurones pour les réseaux ATM. Par exemple, dans [25], DU et al utilisent les réseaux de neurones pour le contrôle d’admission dans les réseaux ATM.

70

Chapitre 3 : Evaluation de performances des réseaux ATM

3.8

Conclusion

Nous avons vu dans ce chapitre que plusieurs méthodes et outils existent pour l’évaluation de performances des réseaux ATM. Ces outils peuvent être classés en trois classes principales : les méthodes analytiques, les mesures, et la simulation. L’avantage majeur de cette dernière classe est le fait qu’elle permette d’évaluer les performances d’un réseau sans que celui-ci soit disponible contrairement aux méthodes mesures qui exigent que le réseau soit disponible pour l’expérimenter. Dans le chapitre 4, nous nous intéresserons à une étude comparative de deux algorithmes de contrôle d’admission dans les réseaux ATM. Nous ferons également un comparaison entre les résultats analytiques et ceux obtenus par la simulation.

71

Chapitre

4

Etude de deux algorithmes de contrôle d’admission

"The net that likes to say YES !." J.M. Pitts and J.A. Schormans [81]

4.1

Introduction

L

ES performances globales d’un réseau ATM perçues par l’usager sont liées de façon trés étroite aux mécanismes de contrôle dans tous les composants du réseau. Parmi ces mécanismes de contrôle, on trouve la fonction de contrôle d’admission. Celleci offre un contrôle de congestion préventif dans le réseau. Par conséquent, elle a été standardisée par l’UIT et l’ATM Forum. Cependant, ces deux organismes de normalisation n’ont pas spécifié un algorithme particulier pour son implémentation . Ainsi, il incombe aux opérateurs et aux concepteurs du réseau d’implémenter la fonction CAC qui leur paraît la plus appropriée. En guise d’application, nous choisissons deux exemples significatifs pour notre problématique ; le premier basé sur une analyse M/D/1 étant approprié au trafic variable (VBR), tandis que le deuxième, basé sur une analyse N.D/D/1, est adéquat pour la modélisation d’un trafic constant (CBR). Nous donnerons le principe de chaque algorithme, ses avantages ainsi que ses inconvénients.

4.1.1

Définitions et notations élémentaires

Nous commençons d’abord par quelques définitions et notations élémentaires (Tab. 4.1) que nous utiliserons plus tard. Définition 3 (trafic lourd (heavy traffic)) Un trafic lourd est défini comme étant un trafic dans lequel la charge du réseau dépasse 0.80. Définition 4 (Charge admisssible (admissible load )) La charge admissible notée ρ avec 0 < ρ < 1 est définie comme étant une charge maximale que l’algorithme de CAC ne doit pas permettre de dépasser. 72

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

Notation Description λ µ ρ CLPi n hi mi C x

Nombre moyen d’arrivées par unité de temps Taux de service Taux d’utilisation du serveur Probabilité de Perte de Cellules de la connexion i Nombre de connexions en cours Débit crête de la connexion i Débit moyen de la connexion i Capacité du lien de sortie Taille du buffer Tab. 4.1 – Notations élémentaires

Fig. 4.1 – Les trois niveaux d’observation du trafic .

4.2

Vue hiérarchique du trafic

Les articles publiés sur ATM ont suggéré de considérer le trafic transporté par un réseau dans l’un des trois niveaux d’observation principaux suivants (Fig.4.1) : 1. Niveau appel (call level ) : A ce haut niveau, il est possible de déterminer la probabilité de pouvoir accéder au réseau (voir [17], [18], et [31]) de façon analogique à la probabilité d’être rejeté pour un appel téléphonique classique à cause de la pénurie des ressources. 2. Niveau rafale (burst level ) : A ce niveau, on s’intéresse aux rafales de trafic. Les rafales de données constituent un facteur clé de la perte de cellules et de la 73

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

variation de délai de bout en bout. 3. Niveau cellule (cell level ) : Ce niveau représente le comportement statistique de la génération de cellules (par exemple, on pourra s’intéresser à la durée minimale d’inter-arrivée de deux cellules consécutives). Dans ce cas, les évènements à considérer sont l’arrivée des cellules. Par exemple, dans une connexion typique, les cellules sont transmises sur des lien ayant une bande passante de 155.52 M bit/s, le débit d’envoi de cellule est de 366792 cellule/s et le temps de service d’une cellule est de 2.726 µs, ce qui veut dire que le temps d’inter-arrivée entre deux cellules consécutives est de l’ordre de 3 µs. Notons qu’à ce niveau, il est souhaitable de vérifier deux propriétés fondamentales, à savoir l’isolation des flux pour minimiser l’interférence entre les différente connexions et le l’équité de partage la bande passante [39]. Dans le cadre de notre étude, nous nous intéresserons à deux niveaux seulement : niveau rafale et au niveau cellule.

4.3

Contrôle d’admission basé sur une analyse M/D/1

Cette modélisation est adaptée pour le contrôle d’admission dans le cas d’un variable dans le temps [81]. Les hypohèses faites sont les suivantes : • Les arrivées sont poissoniennes ; c’est à dire elle suivent une loi de Poisson de mètre λ : (λ.T ) −λ.T P r(avoir k arrives pendant une duree de temps T ) = .e k! Autrement dit, la durée d’inter-arrivées de cellules suit une loi exponentielle de mètre λ1 : Pr(T emps d0 inter − arrivee ≤ t) = 1 − eλ.t

trafic para(4.1) para(4.2)

• Le taux de service est égal à µ. Autrement dit : les durées de services sont déterministes et sont égales à 1/µ. Dans ce chapitre ainsi que dans le chapitre qui suit, nous considérons que la durée de service est égale à 2.83 µsecondes. La charge admissible est alors ρ définie comme suit : ρ=

λ µ

(4.3)

Notons que dans l’analyse mathématique d’un buffer ATM, la synchronisation est souvent négligée. Ainsi, on suppose qu’une cellule reçoit le service immédiatement après avoir trouvé le tampon vide au lieu d’attendre le début du slot suivant. Une approximation dans le cas d’un trafic lourd pour le système M/D/1 nous donne (voir [81]) : 2.x ρ= (4.4) 2.x − ln(CLP ) 74

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

Avec : ρ : Charge du réseau ; x : Taille du buffer (la file d’attente) ; CLP : Probabilité de perte des cellules (Cell Loss Probability). Dans cette équation, nous avons la charge maximale admissible (ρ) en fonction de la taille de la file d’attente (x) et de la probabilité de perte (CLP ). Comment peut-on utiliser ce résultats d’approximation ? Dans le cas d’une modélisation de la fonction CAC par une file d’attente M/D/1, le contrat de trafic est basé seulement sur deux paramètres, à savoir : •hi : le débit crête (PCR, Peak Cell Rate), • CLPi : Probabilité de perte des cellules (Cell Loss Probability) de la connexion i (où i = 1, 2, 3, ..n désigne l’ensemble des connexions qui ont été déja acceptées par la fonction CAC, et qui sont toujours en progrès, c’est à dire qu’elles ne sont pas encore supprimées). On s’intéresse maintenant à la connexion n + 1 : Peut-on accepter cette connexion ou doit-on la rejeter ? Cet algorithme va procéder de la façon suivante : La connexion va être acceptée si l’inéquation suivante est vérifiée : n hn+1 X hi 2.x µ ¶ + ≤ C i=1 C 2.x − ln min (CLPi )

(4.5)

i=1→n+1

Avec C : Capacité (bande passante maximale) du lien de sortie. Il est important de signaler que toutes les connexions souffrent du problème de perte de cellules car elles passent toutes par le même lien partagé. Par conséquent, les CLP minimum (que nous avonc noté min (CLPi ) dans l’inégalité 4.5 est le CLP qui donne i=1→n+1 la limite la plus rigoureuse et la plus sévère sur la charge acceptée. Ce que nous voyons en fait dans l’inéquation 4.5 dans l’inéquation 4.4 ne sont que des approximations pour un trafic lourd (heavy trafic), c’est à dire pour le cas où la charge du réseau dépasse 80%. Par exemple, pour une taille du tampon égale à 40 cellules et un CLP égal à 10−10 , l’équation 4.4 donne une charge admissible maximale égale à 77.65%, valeur qui est légèrement supérieure à 74.5% obtenue en utilisant une méthode analytique exacte [81]. Cette dernière méthode, bien qu’elle donne des résultats très exacts, demeure lourde pour l’implémentation car elle demande beaucoup d’itérations pour atteindre l’état stationnaire et par conséquent elle consomme beaucoup de temps. Une alternative à cela est l’utilisation des tables de recherche (Look-up tables) dans lesquelles sont sauvegardés les résultats de la méthode analytique exacte ( voir Tab. 4.2). 75

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

CLP (Cell Loss Probability) x 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

10

−1

96.3 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9

−2

−3

−4

10

10

10

10−5 10−6 10−7 10−8 10−9 10−10 10−11 10−12

59.7 85.2 92.4 95.6 97.2 98.2 98.9 99.4 99.7 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9 99.9

41.9 71.2 82.4 87.7 90.7 92.7 94.0 95.0 95.7 96.3 96.7 97.1 97.4 97.7 97.9 98.1 98.2 98.4 98.5 98.6

16.6 60.1 74.2 81.3 85.4 88.2 90.1 91.5 92.6 93.5 94.2 94.7 95.2 95.6 95.9 96.2 96.5 96.7 96.9 97.1

6.6 50.7 66.9 75.5 80.7 84.1 86.6 88.4 89.8 90.9 91.8 92.6 93.2 93.7 94.2 94.6 95.0 95.3 95.5 95.8

2.9 42.7 60.4 70.2 76.2 80.3 83.2 85.4 87.1 88.5 89.6 90.5 91.3 92.0 92.5 93.0 93.5 93.9 94.2 94.5

1.35 35.8 54.4 65.2 72.0 76.7 80.0 82.6 84.6 86.2 87.5 88.6 89.5 90.3 91.0 91.5 92.1 92.5 92.9 93.3

0.62 29.9 49.0 60.5 68.0 73.2 77.0 79.8 82.1 83.9 85.4 86.7 87.7 88.6 89.4 90.1 90.7 91.2 91.7 92.1

0.28 24.9 44.0 56.2 64.2 69.9 74.0 77.2 79.7 81.7 83.4 84.8 86.0 87.0 87.9 88.6 89.3 89.9 90.5 91.0

0.13 20.7 39.5 52.1 60.6 66.7 71.2 74.6 77.4 79.6 81.4 83.0 84.3 85.4 86.4 87.2 88.0 88.7 89.3 89.8

0.06 17.1 35.4 48.2 57.2 63.6 68.4 72.1 75.1 77.5 79.5 81.2 82.6 83.8 84.9 85.9 86.7 87.4 88.1 88.7

0.03 14.2 31.6 44.6 53.9 60.7 65.8 69.7 72.9 75.5 77.6 79.4 81.0 82.3 83.5 84.5 85.4 86.2 86.9 87.6

Tab. 4.2 – Table de Recherche pour un système M/D/1 : Charge admissible en fonction de la capacité du buffer et de CLP.

76

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

4.3.1

Algorithme de CAC basé sur une analyse N.D/D/1

4.3.2

Etude analytique

le modèle N.D/D/1 a été étudié dans [98] et dans d’autres travaux. Dans ce modèle , on fait les hypothèses suivantes : • Il y a N sources, chacune ayant la loi des arrivées suit une loi déterministe. D’après l’analyse du système N.D/D/1, la charge admissible (admissible load ) peut être plus grande que celle donnée par le système M/D/1 pour une CLP donnée [81]. Le problème avec le système N.D/D/1 est qu’il modélise le multiplexage de sources à trafic homogène (par exemple le trafic du type CBR). En pratique, ceci n’est pas toujours le cas. Cependant, pour une charge fixée ρ et un nombre constant de sources N , ce modèle constitue la situation pire cas de perte de cellules dans le cas d’un trafic homogène. Par conséquent, on peut utiliser les résultats de ce modèle et les appliquer en général pour les cas où nous avons N sources ayant différents débits crête (PCR). Comme dans les cas du système M/D/1, nous manipulons les approximations pour la charge lourde pour le système N.D/D/1. Nous avons l’équation suivante : CLP = e−2x( N + x

1−ρ ρ

)

(4.6)

D’où nous pouvons tirer les résulat suivant : ρ=

2.x.N 2.x.N − (2.x2 + N. ln (CLP ))

(4.7)

Si nous remarquons bien, cette formule peut donner des valeurs de ρ plus grandes que 100% quand : 2.x2 + N. ln (CLP ) > 0 (4.8) Il est évident qu’une telle charge du réseau peut causer une perte de cellules plus grande que celle tolérée violant ainsi l’engagement du réseau à garantir la qualité de service des connexions. Cependant, elle nous fournit un premier test pour le contrôle d’admission basée sur cette analyse. C’est à dire, si : n+1≤−

2.x2

µ

ln

¶

(4.9)

min (CLPi )

i=1→n+1

alors dans ce cas, nous pouvons occuper le lien jusqu’à 100%. Autrement dit, on peut accepter la connexion pourvu que : n hi hn+1 X + ≤1 C i=1 C

77

(4.10)

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

Sinon, si on a : n+1>−

2.x2

µ

ln

¶

(4.11)

min (CLPi )

i=1→n+1

alors dans ce cas on acceptera la connexion si : n hi hn+1 X 2.x.(n + 1) · µ ¶¸ + ≤ C i=1 C 2.x.(n + 1). 2.x2 + (n + 1). ln min (CLPi )

(4.12)

i=1→n+1

Nous signalons que l’analyse N.D/D/1 est seulement requise si le nombre de connexions dépasse le nombre de places mémoire dans le buffer de sortie. Autrement dit, si on a N < x. Si par contre, on a moins de sources que de place mémoire, alors la charge admissible est de 100%. Cet algorithme basé sur une analyse N.D/D/1 est approprié pour un trafic de type CBR (Constant Bit Rate). les paramètres requis sont la probabilité de perte de cellules CLPi pour chaque source i , la taille du buffet x, la capacité de transmission du lien de sortie C ainsi que le nombre de connexions qui sont en progrès n. Notons aussi qu’il est possible d’avoir un trafic constant (CBR) et un trafic variable (VBR), pourvu que le débit crête d’un source est utilisé dans le calcul de la charge admissible et de la bande passante allouée à la connexion.

4.4

Analyse N.D/D/1 au niveau cellule

Au niveau cellule, il est souvent possible d’approximer le modèle d’arrivée de cellules d’une large collection de sources CBR qui envoient leurs données vers un buffer par un processus de Poisson. Cependant, une meilleure analyse est donnée par le modèle N.D/D/1. Chaque source envoit à un débit constant de 167 cellules/s, alors le taux d’arrivée de cellules ne va jamais dépasser le taux de service du buffer de sortie et si nous avons N ∗ 167 < 353208 cellules/s alors même le taux total d’arrivée de cellules ne vas pas faire déborder le buffer. Le nombre maximum de sources à admettre est de : 353208 /167 =2115 sources. Autrement dit, chaque source produit une cellule chaque 2115 slots. Le problème qui se pose est la synchronisation des sources de telle sorte qu’elles envoient au même slot leurs cellules.

4.4.1

Multiplexage du trafic CBR de N sources

La figure 4.3 explique le principe de multiplexage de N sources CBR. Dans cette figure, nous avons trois sources qui envoient leurs trafics à un débit constant égal à une cellule chaque trois slots. On remarque que les arrivées des cellules ne se chevauchent pas. Mais ceci n’est pas toujours le cas : il arrive des fois que les cellules envoyées 78

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

Fig. 4.2 – Modèle N.D/D/1 de contrôle d’admission au niveau cellule (ici N=4) par les N sources se chevauchent. Si dans un tel cas nous avons le nombre de sources qui dépasse le nombre de places mémoire dans le buffer, ceci causerait des pertes de cellules. Ceci n’est pas tolérable dans le cas d’un trafic de voix par exemple qui est un cas typique du trafic CBR. Prenons un exemple concret. Si on prend 1000 sources idépendantes alors chaque source a une période de 2115 slots. L’analyse que nous faisons suppose que la taille du buffer est infinie et la probabilité de perte de cellule est approximée par la probabilité (notée Q(x)) que la taille du buffer dépasse une certaine taille x. on pourra alors écrire : N X

(

µ

n−x N! . n!.(N − n)! D

¶n ·

µ

n−x . 1− D

¶¸N −n

)

D−N +x CLP ≈ Q(x) = . D−n+x n=x+1 (4.13) Cependant, pour une charge lourde (heavy load ), c’est à dire une charge dépassant 80%, on peut approximer Q(x) par la formule suivante : Q(x) = e−2x( N + x

1−ρ ρ

)

(4.14)

Avec : N : Nombre de connexions admises (dans le cas où nous avons N>x) ; Une telle approximation est en fait très importante car elle permet de réduire considérablement les temps de calcul pour la fonction CAC. En contrepartie, le prix à payer est une perte dans la précision.

79

Chapitre 4 : Etude de deux algorithmes de contrôle d’admission

Fig. 4.3 – Multiplexage de 3 sources CBR

4.5

Conclusion

Le choix d’une algorithme de contrôle d’admission dépend de façon très étroite du trafic considéré. Un mauvais choix d’un modèle implique de mauvais résultats et de mauvaises performances. Si nous avons un trafic dont le débit est constant dans le temps, il est très facile de prévoir la bande passante à lui allouer. En effet, il suffit de lui allouer comme bande passante son débit crête. Par contre, si le trafic est variable dans le temps alors la prévision de la bande passante à allouer. Plusieurs approches ont été proposées : allocation du débit moyen, allocation de la moyenne du débit moyen et du débit crête, et allocation du débit crête lui-même. On verra dans le chapitre suivant quel est l’avantage, et quel est l’inconvénient de cette dernière approche.

80

Chapitre

5

Résultats et Discussions

"In fact, however, a simulation is a computer-based statistical sampling experiment." Averill M. Law and W. David Kelton [69]

5.1

Introduction

D

ANS ce chapitre, nous faisons une étude comparative entre les deux algorithmes de contrôle de congestion vus dans le chapitre précédent. Les deux critères utilisés pour la comparaison étant le nombre de connexions admises pour les deux algorithmes, et la charge admissible. Par la suite, nous verrons comment calculer le gain statistique si on utilise une allocation statistique au lieu d’une allocation déterministe, et ce pour un trafic de type VBR. Ce facteur est l’un des critère de performances des algorithmes de contrôle d’admission.

5.2

Environnement de simulation

Avant de présenter les résultats obtenus, nous donnons ci-dessus l’environnement de programmation ainsi que quelques détails d’implémentation.

5.2.1

Environnement de programmation

Beaucoup d’environnements de simulation à évènements discrets existent actuellement sur le marché. Ces environnements de simulation peuvent être classés principalement en deux classes principales : langages de simulation (SIMSCRIPT, QNAP,etc) et simulateurs orienté application (Network Simulator, OPNET, etc) [72]. Nous avons utilisé dans notre travail le langage C++ sous l’environnement C++ Builder 6. Cet environnement nous offre plusieurs bibliothèques mathématiques telles que la bibliothèque < math.h > qui contient entre autre des fonctions de génération de nombres aléatoires (rand()) selon une loi normale. D’autre part, cet environnement nous offre une bibliothèque de composants visuels (VCL, Visual Component Library), ce qui facilite la conception des interfaces graphiques de notre application. 81

Chapitre 5 : Résultats et Discussions

5.2.2

Génération de nombre aléatoires dans avec la fonction rand()

Dans une simulation d’un système informatique, c’est un générateur pseudo-aléatoire qui fournira, à chaque appel, une variable selon la loi de probabilité choisie. La fonction rand() implémente un générateur de nombres aléatoires selon une loi normale avec une période de 232 . Il est basé sur la méthode congruentielle multiplicative.

5.2.3

Génération des arrivées selon une loi exponentielle

Pour générer des variables selon une loi quelconque (exponentielle, Cox, géométrique, etc), la fonction rand() tire des variables uniformément distribuées dans l’intervalle ]0,1[. Par la suite, il suffit d’utiliser cette fonction pour générer des arrivées selon la loi voulue. Par exemple, pour générer les arrivées selon une loi de Poisson, nous avons utilisé le code source suivant :

Code Source 1 : Génération de variable aléatoires selon une loi exponentielle double expntl(double x) { double z ; // Nombre Uniforme entre 0 et 1 do { z = ((double) rand() / RAND_MAX) ; } while ((z == 0) || (z == 1)) ; return(-x * log(z)) ; }

5.3

Résultats analytiques et résultats de simulation pour le modèle M/D/1

Dans cette section, nous présentons d’abord un les résultats analytiques du modèle M/D/1, ensuite les résultats de simulation que nous avons obtenus et qui concernent l’estimation la charge admissible en fonction de la taille du buffer et de la probabilité de perte de cellule CLP.Nous commençons d’abord par les résultats obtenuus avec la méthode analytique exacte, nous présentons les résultats analytiques approximatifs. La figure 5.1 donne les résultats exacts de la charge admissible en fonction du CLP et de la taille du buffer x pour un modèle M/D/1 tandis que la figure 5.2 en donne 82

Chapitre 5 : Résultats et Discussions

Fig. 5.1 – Charge admissible en fonction de la taille du tampon (Résulats exacts pour le modèe M/D/1). des résultats d’approximation qui sont obtenus en utilisant une approximation pour un trafic lourd (heavy traffic), c’est à dire pour un trafic dont la charge dépasse 80%. Si nous analysons la figure 5.1 et la figure 5.2, nous remarquons principalement deux choses : 1. La charge admissible augmente à chaque fois que nous augmentons la taille du buffer. Par exemple si on fixe le CLP = 10−2 , la charge admissible est de 59.7% pour une taille du buffer égale à 5 cellule, de 95.6% pour une taille du buffer égale à 20 et de 99.9% pour une taille de buffer égale à 100. 2. La charge admissible décroît quand les besoins du trafic en terme de CLP (qui caractérise la qualité de service d’une connexion) deviennent plus stringeants. Une autre point à noter, c’est que les résultats des deux figures sont très proches. Ceci nous permet d’affirmer qu’il est possible d’utilser la méthode d’approximation pour l’implémentation de la fonction CAC dans le cas ou nous nous disposons pas de table de recherche. En effet, la formule d’approximation que nous avons présentée dans le chapitre précédente ne consomme pas trop de temps de calcul et par conséquent elle peut être évaluée "à la volée". Maintenant, examinons la figure 5.1 qui représente l’évolution de la charge admissible en fonction de la taille du buffer, mais cette fois pour un seul CLP (qui égal à 10−2 ). Cette figure montre trois types de résultats : 1. Résultats analytiques exacts pris directement d’une table de recherche ; 2. Résultats analytiques approximatifs ; 3. Résultats de simulation que nous avons obtenus. 83

Chapitre 5 : Résultats et Discussions

Fig. 5.2 – Charge admissible en fonction de la taille du tampon (Résulats d’approximation pour le modèe M/D/1)).

Fig. 5.3 – Charge admissible en fonction de la taille du tampon (Résultats analytiques et résultats de simulation pour un CLP égale à 10−2 ).

84

Chapitre 5 : Résultats et Discussions

Taille du buffer

Analytiques Analytiques Simulation (exacte) (approximation)

Intervalles de confiance

5

59.70

68.47

57.06

54.80 - 59.33

10

85.20

81.28

77.71

74.52 - 80.90

15

92.4

86.69

88.95

87.60 - 90.30

20

95.60

89.68

90.60

88.35 - 92.84

25

97.20

91.57

95.06

91.88 - 98.23

30

98.20

92.87

94.39

92.87 - 95.90

35

98.90

94.56

97.19

94.74 - 99.63

40

99.40

93.83

97.82

96.15 - 99.50

45

99.70

95.13

99.20

97.99 - 100.40

50

99.90

95.60

99.25

97.94 - 100.55

Tab. 5.1 – Charge admissible en fonction de la taille du buffer pour l’analyse M/D/1 pour CLP=10−2 Pour les résultats que nous avons obtenus, nous avons utilisé le principe de réduction de la charge admissible jusqu’à obtenir une charge pour laquelle le CLP est vérifié. Nous avons refait l’expérience plusieurs fois , calculé la moyenne des observations ainsi que la variance. Enfin, nous avons calculé les intervalles de confiance (voir Tab. 5.1). Nous remarqouns que les résultats que nous avons obtenus sont proches des résultats analytiques et des résultats de simulations. Ceci nous permet de dire qu’il est possible d’utiliser l’approche simulation pour dresser des tables de recherche que la fonction CAC pourra utiliser dans l’admission de nouvelles connexions. L’inconvénient majeur de l’approche simulation est le temps énorme qu’elle consomme pour donner des résultats. De ce fait, un compromis doit perte fait entre un temps de simulation suffisament grand qui donne des résultats satisfaisants, et un temps de simulation court mais qui donne des résultats qui tendent à s’éloigner du vrai résultat.

5.4

Résultats de la simulation de la file d’attente N.D/D/1

Le modèle N.D/D/1 est mieux adapté pour la modélisation de N sources de type CBR. Pour un tel trafic, il très facile de prédire la bande passante à allouer pour une connexion. En effet, une connexion de type CBR envoit ses cellules à un débit constant. Par conséquent, la charge admissible du réseau peut être de 100%. Dans un tel modèle, nous nous intéressons au nombre maximal de connexions que nous pouvons faire sans pour autant risquer de violer les qualités de service des connexions déja admises. 85

Chapitre 5 : Résultats et Discussions

Fig. 5.4 – Nombre de connexions admises en fonction de la taille du tampon de sortie pour une charge de 100% (modèle N.D/D/1). La figure 5.4 montre le nombre de connexions en fonction de la taille du buffer x et une charge de 100%. De façon analogue au modèle M/D/1, nous remarquons que les performances dépendent de façon étroite de la taille du buffer : à chaque fois que la taille du buffer augmentent, nous pouvons admettre plus de connexions dans le réseau. Nous pouvons alors poser la question suivante : " Serait-il intéressant lors du dimensionnement des buffers ATM de maximiser leur taille ? ". Cependant, un autre problème se pose : le délai d’attente moyen dans le buffer pour les applications temps réel telles que la vidéoconférence et la télémédecine dont l’usage est très fréquent dans les réseaux ATM. En effet, de telles applications sont très sensibles aux délais de bout en bout d’une part et à la gigue (c’est à dire la variation des délais inter-cellules) d’autre part. De ce fait, maximiser la taille de buffer va les pénaliser. Notons enfin que ce modèle peut être aussi utilisé pout modéliser un trafic VBR en considérant une connexion VBR comme une connexion CBR à condition qu’on fasse l’hypothèse que le réseau va allouer à la connexion VBR son débit crête hi tout au long de la connexion. Un tel schéma de contrôle d’admission a l’avantage de garantir une meilleure qualité de service pour les connexion VBR. Cependant, il risque de ne pas utiliser efficacement les ressources du réseau. En effet, un source VBR n’envoit pas ses cellules à son débit crête (PCR) mais à un débit moyen (MCR). Par conséquent, les ressources allouées sont gaspillées.

86

Chapitre 5 : Résultats et Discussions

hi

mi

N0

N

Gain tique

35320.76

8830.19

10

28

2.8

17660.38

4415.09

20

65

3.25

11773.59

2943.39

30

103

3.43

8830.19

2207,54

40

142

3.55

7064.17

1766.04

50

181

3.62

5886.79

1471,96

60

220

3.66

5045.82

1264,45

70

259

3.70

4415.09

1103.77

80

298

3.72

3924.53

981.13

90

337

3.74

3532.08

883.02

100

376

3.76

1766.04

441.6

200

771

3.88

1177.36

294,34

300

1167

3.89

883.02

220.75

400

1564

3.91

706.42

176.60

500

1961

3.92

588.68

147.17

600

2361

3.93

504.58

126,145

700

2758

3.94

Statis-

Tab. 5.2 – Gain statistique pour différentes connexions

5.5

Exemple de calcul du gain statistique

Les réseaux ATM utilisent un multiplexage statistique qui permet de tirer un gain statistique. Dans notre exemple nous prendrons la capacité C du lien égale 155.52 Mb/s (capacité de lien standardisée par l’UIT aux interfaces UNI), c’est à dire égale à 353 208 cellule/s. Nous prendrons des exemples de connexions dont le débit crête varie entre 504.58 cellule/s et 35320.76 cellule/s. Nous supposerons également dans tous les cas que : mi =

hi 4

(5.1)

Pour chaque cas, nous calculons le nombre de connexions admises N0 en utilisant l’algorithme N.D/D/1. Dans ce cas, le débit alloué à une connexion est son débit crête (hi ). N0 est calculé de la façon suivante : N0 =

C hi

(5.2)

Nous calculons également le nombre de connexions admises N dans le cas de l’algorithme M/D/1. Dans ce cas, le débit alloué à une connexion est son débit moyen mi . 87

Chapitre 5 : Résultats et Discussions

Notons aussi que la charge admissible dans ce cas n’est pas égale à 100% comme c’est le cas de l’algorithme N.D/D/1, mais il est en fonction de la probabilité de perte CLPi et de N0 . ceci est donné dans l’équation suivante : 1 (ρ.N0 ) [N0 ] −ρ.N0 CLP ≈ .e . (1 − ρ)2 .N0 [N0 ]!

(5.3)

Où L’équation 5.3 est utilisée pour dresser une table de recherche (qu’on peut trouver dans [81]) qui donne ρ en fonction de CLP et de N0 . Nous calculerons alors le gain statistique défini par : N G= (5.4) N0 Avec : ρ.C N= (5.5) mi et : C N0 = (5.6) hi Pour différentes connexions, nous avons obtenus les résultats illustrés dans le tableau 5.2.

5.5.1

Discussion

La table 5.3 montre une comparaison entre le nombre de connexions admises par la fonction CAC pour les deux algorithmes étudiés. Remarquons que le nombre de connexions admises par l’algorithme M/D/1 est toujours supérieur au nombre de connexions admises par l’algorithme N.D/D/1 dans le cas de connexions VBR. rappelons que de telles connexions sont caractérisées par un débit moyen strictement inférieur au débit crête. Dans le cas d’un trafic CBR, le nombre de connexions admises par les deux algorithmes sera le même. Par conséquent, le gain statistique sera égal à 1. Remarquons également que le gain statistique tiré du réseau est inversement proportionnel au rapport débit moyen/débit crête. Ainsi, nous pouvons conclure que l’algorithme M/D/1 est plus adéquat au contrôle d’admission pour un trafic de type VBR, et ce, en terme de gain statistique.

88

Chapitre 5 : Résultats et Discussions

5.6

Conclusion

Un algorithme de contrôle d’admission est primordial dans un réseau ATM pour assurer un contrôle de congestion préventif et présever la qualité de service des connexions édja admises . Le choix d’un tel algorithme dépend essentiellement du type de trafic considéré (CBR, VBR, ABR, etc), le trafic le plus facile à étudier et à modéliser étant de loin le trafic CBR. Pour ce dernier, il faut allouer à chaque connexion son débit crête. En revanche, ceci n’est pas le cas pour des connexions VBR, sinon aucun gain statistique ne sera tiré du réseau. La question est alors quelle bande passante allouer à ce type de connexion ? dans notre étude, nous avons alloué le débit moyen. En pratique, il existe d’autres approches qui procèdent chacune à sa façon. Les une cherchent à maximiser l’utmisation du réseau et, par conséquent, allouent un strict minimum de bande passante à la connexion alors que les autres visent à garantir à tout prix la qualité de service de la connexion, et de cefait allouent à la connexion un débit avoisinant sont débit crête.

89

Conclusion Générale

L

’ÉTUDE réalisée dans ce mémoire a été consacrée au contrôle de congestion dans les réseaux haut débit, plus particulièrement dans les Réseaux Numériques à Intégration de Services à Large Bande (RNIS-LB). Ce dernier a été conçu par l’UIT (Union Internationale des Télécommunications) pour supporter une large gamme de services avec une fine granularité. Après un long débat, l’UIT a opté pour le mode de transfert asynchrone (ATM, Asynchronous Transfer Mode) au détriment du mode de transfert synchrone (STM, Synchronous Transfer Mode) et a choisi une taille de cellule égale à 53 octets. Dans le chapitre 1, nous avons présenté les technologies proposées pour supporter les hauts débits dans les réseaux à grande distance ; nous avons commencé par la technologie Relais de Trames (Frame Relay), ensuite la technologie ATM et enfin la technologie MPLS (Multi Protocol Label Switching) qui est une technologie prometteuse pour garantir la qualité de service dans les réseaux de demain. Nous avons également défini la notion de qualité de service (QoS, Quality of Service) et présenté les paramètres de qualité de service ainsi que les classes de service de ATM. Enfin, nous avons donné un bref aperçu sur la technologie MPLS et le principe de commutation d’étiquettes introduit par celle-ci. Dans le chapitre 2, nous avons vu que comme tout réseau à commutation de paquet, ATM souffre du problème de congestion. Pire encore , et contrairement à quelques fausses idées, ce problème est plus aigu et plus ardu à résoudre dans ATM à cause de plusieurs facteurs : large produit délai-bande passante , exigences très strictes du trafic en terme de qualité de service, hétérogénéité du trafic, etc. Nous avons évoqué l’importance des mécanismes de contrôle de congestion dans le RNIS-LB ainsi que les propiétés que doivent vérifier ces mécanismes. Parmi ces propriétés, nous en citons deux et qui sont souvent difficiles à concilier : l’efficacité et l’équité. Le point essentiel que nous avons dégagé dans ce chapitre est le suivant : Aucune technnologie moderne ne peut résoudre de façon définitive le problème de congestion dans les réseaux haut débit sans l’adjonction de bons protocoles de contrôle de congestion. Nous avons aussi vu que le protocole TCP (Transmission Control Protocol ) conçu pour assurer un contrôle de congestion dans Internet s’est avéré inadéquat pour les réseaux à haut débit caractérisés par un produit délai-bande passante très 90

Conclusion générale et Perspectives

large. Par conséquent, des modifications doivent être apportées à ce protocole pour s’adapter aux réseaux à haut débit. Dans la littérature, beaucoup de solutions ont été proposées : Fast TCP, High Speed TCP, Scalable TCP, etc. Dans le chapitre 3, nous avons introduit les méthodes d’évaluation de performances des réseaux ATM. A première vue, ces méthodes peuvent être classées en trois classes : méthodes analytiques, mesures, et simulation. Cette dernière est une approche très prometteuse pour l’évaluation de performances des réseaux qui n’existent pas encore pour l’expérimentation. Nous avons introduit la notion de simulation à évènements discrets (DES, Discrete Event Simulation) et son principe. Par la suite, nous avons vu comment valider les résultats d’une simulation. Contrairement à Internet qui utilise un contrôle de congestion réactif, ATM préconise l’utilisation d’un contrôle de congestion de préventif. Un exemple de tels mécanismes est le contrôle d’admission (CAC). En effet, la fonction CAC implémentée dans les interfaces UNI (User Network Interface) et les interfaces NNI (Network to Network Interface) agit de façon à éviter que la congestion n’apparaîsse dans le réseau. Son principe consiste à admettre une nouvelle connexion si il y a des ressources suffisantes pour satisfaire la qualité de service (QoS) de cette nouvelle connexion d’une part, et de ne pas violer la qualité de service des connexions déja admises d’autre part. Dans le cas contraire, la connexion est soit rejetée soit renégociée. A cet effet, la fonction CAC doit définir un seuil de charge appelé charge admissible qui ne doit jamais être dépassé. Dans le chapitre 4, nous avons étudié deux algorithmes de contrôle d’admission. Le premier est basé sur une analyse M/D/1 et le deuxième est basé sur une analyse N.D/D/1. Le premier algorithme est adéquat pour une trafic variable dans le temps alors que le deuxième est adéquat pour un trafic constant dans le temps tel que la voix qui est très utilisée dans les réseaux ATM. Cependant, le deuxième algorithme reste aussi applicable pour la modélisation d’un trafic variable dans le temps : il suffit d’allouer à une connexion VBR son débit crête (PCR) et de faire abstraction totale de son débit moyen (MCR). Une telle allocation permet d’offrir une bonne qualité de service en terme de perte de cellules. Cependant, elle n’offre aucun gain statistique. En effet, les résultats montrent que plus le rapport MCR/PCR augmente, plus nous perdons de gain statistique. A cet effet, il serait intéressant, pour un trafic variable, d’utiliser l’analyse M/D/1 au lieu de N.D/D/1. Dans le chapitre 5, nous avons fait une étude comparative entre ces deux algorithmes selon le nombre de connexions admises et la charge admissible. La conclusion que nous avons tirée est que le gain statistique obtenu en allouant le débit moyen augmente avec l’augmentation de la différence entre le débit moyen et le débit crête. En guise de conclusion générale, nous pouvons dire que la congestion est un problème qui persistera dans les réseaux de demain aussi longtemps que l’hétérogénéité 91

Conclusion générale et Perspectives

des équipements existera. Pour apporter une solution à ce problème, il faut ne pas trop compter sur les technologies matérielles mais bien au contraire, il faut investir dans la conception de bon schémas de contrôle de congestion qui doivent permettre de coordonner les efforts des différents acteurs du réseau afin de tirer un maximum de profit de celui-ci et d’offrir de meilleures performances. Comme perspectives, il serait intéressant d’étendre notre étude pour étudier les mécanismes de contrôle de congestion et d’équilibrage de charge ainsi que l’ingénierie du trafic dans MPLS d’une part, et d’étudier les améliorations apportées au contrôle de flux du protocole TCP pour les réseaux utilisant des liaisons satellitaires d’autre part. Il serait également intéressant d’aborder le problème de congestion de façon plus générale, mais cette fois en se basant sur la théorie du Network Calculus.

92

Bibliographie [1] D. Aissani and A. Aissani. La Théorie des Files d’Attente : Fondements Historiques et Applications à l’Evaluation des Performances. Ecole Doctorale d’Informatique de Béjaia, 2004. [2] O. Ait Hellal. Contrôle de Flux dans les Réseaux à Haut Débit. PhD thesis, Université de Nice-Sophia Antipolis, Novembre 1998. [3] V. Alwayn. Advanced MPLS Design and Implementation. O’Reilly and Associates, 2002. [4] C. Barakat, E. Altman, and W. Dabbous. On TCP Performance in a Heterogeneous Network : A Survey. IEEE Communications Magazine, Janvier 2000. [5] R.J. Bates. Broadband Telecommunications Handbook. The McGraw-Hill Companies, 2002. [6] S. Bates. Traffic Characterization and Modelling for Call Admission Control Schemes on Asynchronous Transfer Mode Networks. PhD thesis, The University of Edinburgh, Septembre 1997. [7] S. Beker. Techniques d’Optimisation pour le Dimensionnement et la Reconfiguration des Réseaux MPLS. PhD thesis, Ecole Nationale Supérieure des Télécommunications, Avril 2004. [8] G. Belch, S. Greiner, H. De Meer, and K.S. Trivedi. Queueing Networks and Markov Chains : Modeling and Performance Evaluation with Computer Science Applications. Wiley & Sons, 1998. [9] A. Benoit. Méthodes et Algorithmes Pour l’Evaluation des Performances des Systèmes Informatiques à Grand Espace d’Etats. PhD thesis, Instiut National Polytechnique de Grenoble, Juin 2003. [10] D. Bertsekas and R. Gallagher. Data Networks. Englewood Cliffs, New Jersey, 1992. [11] F. Bonomi and K.W. Fendick. The Rate-Based Flow Control Framework for the Available Bit-Rate ATM Service . IEEE Network Magazine, 9 :25–39, Mars/Avril 1995. [12] J.Y.L. Boudec. Network Calculus, A Theory of Deterministic Queuing Systems for the Internet. Springer Verlag, Mai 2004. 93

Bibliographie

[13] J.Y.L. Boudec. Performance Evaluation of Computer and Communications Systems. Ecole Polytechnique Fédérale de Lausanne (EPFL), 2004. [14] J.Y.L. Boudec. Rate adaptation, Congestion Control and Fairness : A Tutorial. Ecole Polytechnique Fédérale de Lausanne (EPFL). URL : http ://ica1www.epfl.ch/perfeval/, Février 2005. [15] L.S. Brakmo, S.W. Omalley, and L.L. Peterson. TCP Vegas : New Techniques for Congestion Detection and Avoidance. Proceedings of SIGCOMM’94 Conference, pages 24–35, ACM 1994. [16] J. Cannau. Evaluation de performances d’une amélioration de TCP WestWood. Mémoire de DEA. Université Libre de Bruxelles, 2003. [17] Y.H. Cao. Performance Evaluation of Admission Control Policies for High Speed Networks. Master’s thesis, Université de Saskatchewan (Canada), 1994. [18] H.J. Chao and X. Guo. Quality of Service Control in High-Speed Networks. Wiley & Sons, Février 2002. [19] D.M. Chiu and R. Jain. Analysis of Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks. Computer Networks and ISDN Systems, 17 :1–14, 1989. [20] C. Chong and S. Li. (σ, ρ)- Characterization Based Connection Control for Guaranteed Services in High Speed Networks. IEEE INFOCOM’95, pages 835– 844, 1995. [21] D. Clark. RFC 813 : Window and Acknowledgement Strategy in TCP, Juillet 1982. [22] D. Comer. Internetworking with TCP/IP, volume 1. Prentice Hall, 2000. [23] E. Crawley, R. Nair, B. Rajagopalan, and H. Sandick. RFC 2386 : A Framework for QoS-Based Routing in the Internet, Août 1998. [24] C.J. David, X. Wei, and S.H. Low. FAST TCP : Motivation, Architecture, Algorithms, Performance. IEEE Infocom, Hong Kong, Mars 2004. [25] S.X. Du and S.Y. Yuan. Congestion Control for ATM Multiplexers Using Neural Networks : Multiple Sources/Single Buffer Scenario. Journal of Zhejiang University SCIENCE, 5(9) :1124–1129, 2004. [26] O. Elloumi. TCP au-dessus de ATM : Architecture et Performance. PhD thesis, Université de Rennes I, Mai 1998. [27] P.H.L. Fernandes. Méthodes Numériques pour la Solution de Systèmes Markoviens à Grand Espace d’Etats. PhD thesis, Institut National Polytechnique De Grenoble, Février 1998. [28] S. Floyd. Congestion control principles. RFC2914, Octobre 1999. 94

Bibliographie

[29] S. Floyd. HighSpeed TCP for Large Congestion Windows. Internet draft draftfloyd-tcp-highspeed-02.txt. URL : http ://www.icir.org/floyd/hstcp.html, Février 2003. [30] S. Floyd and A. Romanow. Dynamics of TCP Traffic over ATM Networks. in Proceedings of ACM SIGCOMM’94, pages 79–88, Septembre 1994. [31] P.C.F. Fonseca. Traffic Control Mechanisms with Cell-Rate Simulation for ATM Networks. PhD thesis, University of London, Avril 1996. [32] P.J. Fortier and H.E. Michel. Computer Systems Performance Evaluation and Prediction. Digital Press, 2003. [33] R.L. Freeman. Practical Data Communications. Wiley & Sons, 2001. [34] M. Gagnaire et D. Kofman. Réseaux Haut Débit, Tome I : Réseaux ATM et Réseaux Locaux. Dunod, 1999. [35] D. Gaïti and N. Boukhatem. Cooperative Congestion Control Schemes in ATM Networks. IEEE Communications Magazine, Novembre 1996. [36] D. Gaïti and G. Pujolle. Performance Management Issues in ATM Networks : Traffic and Congestion Control. IEEE/ACM Transactions on Networking, 4(2), Avril 1996. [37] M. Gerla and L.Kleinrock. Flow Control : A Comparative Survey. IEEE Transactions on Communications, COM-28(4), 1980. [38] W. Goralski. Frame Relay for High Speed Networks. Wiley & Sons, 1999. [39] S. Gupta. Performance Modeling and Management of High-Speed Networks. PhD thesis, Université de Pennsylvanie, 1993. [40] M. Hamdi. Contrôle de trafic ATM pour sources vidéo à débit variable. PhD thesis, ENST de Bretagne, 1997. [41] M. Hassan and R. Jain. High Performance TCP/IP Networking. Prentice Hall, 2003. [42] B.R. Haverkort. Performance of Computer Communication Systems. Wiley & Sons, 1998. [43] F.M. Holness. Congestion Control Mechanisms within MPLS Networks. PhD thesis, Queen Mary and Westfield College, University of London, Septembre 2000. [44] D. Hughes and P. Daley. Limitations of Credit based Flow Control. AF-TM 94-0776, Septembre 1994. [45] D. Hughes and P. Daley. More ABR Simulations Results. AF-TM 94-0777, Septembre 1994.

95

Bibliographie

[46] M. Ilyas and H.T. Mouftah. Performance Evaluation of Computer Communications Networks. IEEE Communications Magazine, 23(4) :18–29, Avril 1985. [47] ITU-T Recommendation E.211. B-ISDN Service Aspects. International Telecommunications Union, Helsinki, Mars 1993. [48] ITU-T Recommendation E.800. Terms and Definitions Related to Quality of Service and Network Performance Including Dependability. International Telecommunications Union, Août 1994. [49] ITU-T Recommendation I.113. Vocabulary of Terms for Broadband Aspects of ISDN. International Telecommunications Union, Helsinki, Mars 1993. [50] ITU-T Recommendation I.371 . Traffic Control and Congestion Control in BISDN. Août 1996. [51] V. Jacobson and J. Karels. Congestion Control and Avoidance. SIGCOMM’88, Novembre 1988. [52] R. Jain. A Delay Based Approach for Congestion Avoidance in Interconnected Heterogeneous Computer Networks. Computer Communications Review, 19(5) :56–71, Octobre 1989. [53] R. Jain. Congestion Control in Computer Networks : Issues and Trends. IEEE Network Magazine, pages 24–30, Mai 1990. [54] R. Jain. Art of Computer Systems Performance Analysis : Techniques For Experimental Design Measurements Simulation And Modeling. Wiley & Sons, 1991. [55] R. Jain. Myths about Congestion Management in High-Speed Networks. Internetworking Research and Experience, 3(3) :101–113, Septembre 1992. [56] R. Jain. Congestion Control and Traffic Management in ATM Networks : Recent Adcances and A Survey. Computer networks and ISDN Systems, 27, Novembre 1995. [57] S. Jamin, S. Shenker, and P. Danzig. Comparison of Measurement-based Admission Control Algorithms for Controller-Load Service. IEEE INFOCOM’97, pages 973–980, 1997. [58] L. Kalampoukas. Congestion Management in High Speed Networks. PhD thesis, Université de Californie, Septembre 1997. [59] S. Kalyanaraman. Traffic Management for the Available Bit Rate (ABR) Service in Asynchronous Transfert Mode (ATM) Networks. PhD thesis, Ohio State University, 1997. [60] D. Katabi. Decoupling Congestion Control and Bandwidth Allocation Policy With Application to High Bandwidth-Delay Product Networks. PhD thesis, Massachusetts Institute of Technology, Mars 2003. 96

Bibliographie

[61] D. Katabi, M. Handley, and C. Rohrs. Congestion Control for High-BandwidthDelay Product Networks. SIGCOMM’02, Aout 2002. [62] T. Kelly. Scalable TCP : Improving Performance in Highspeed Wide Area Networks . Submitted for publication, Décembre 2002. [63] S. Keshav. Congestion Control in Computer Networks. PhD thesis, Department of EECS at UC Berkeley, Aôut 1991. [64] S. Keshav. An Engineering Approach to Computer Networking. Addison-Wesley, 1997. [65] H. Kobayashi. Modeling and Analysis, An Introduction to System Performance Evaluation methodology. Addison-Wesley Publishing Company, 1978. [66] H.T. Kung and R. Morris. Credit-based Flow Control for ATM Networks. IEEE Network Magazine, 9 :40–48, Mars/Avril 1995. [67] T.V. Lakshman and U. Madhow. The Performance of TCP/IP for Networks with High Bandwidth-Delay Products and Random Loss. IEEE/ACM Transactions on Networking, 5(3), Juin 1997. [68] L. Lamti-Ben-Yakoub. Une Architecture pour la Gestion du Traffic Sortant d’Un Réseau Local. PhD thesis, Université de Rennes I, Décembre 1999. [69] A.M. Law and W.D. Kelton. Simulation Modeling and Analysis. McGraw-Hill, 2000. [70] A.M. Lee. Applied Queuing Theory. Mac Millan, 1966. [71] E. Liu. A Hybrid Queueing Model for Fast Broadband Networking Simulation. Master’s thesis, University of London, Mars 2002. [72] A. Maria. Introduction to Modeling and Simulation. Proceedings of the 1997 Winter Simulation Conference, 1997. [73] R. Marquez, E. Altman, and S.S. Solé-Alvarez. Modeling TCP and High Speed TCP : A Nonlinear Extension to AIMD Mechanisms. HSNMC 2004, pages 132– 143, 2004. [74] J.L. Mélin. Qualité de Service sur IP. Eyrolles, 2001. [75] J. Nagle. RFC 896 : Congestion Control in IP/TCP Internetworks, Janvier 1984. [76] J. Nagle. RFC 970 : On Packet Switches With Infinite Storage, Décembre 1985. [77] J. Nagle. On Packet Switches with Infinite Storage. IEEE Transactions on Communication, COM-35 :435–438, Avril 1987. [78] A. Pattavina. Switching Theory : Architecture and Performance in Broadband ATM Networks. Wiley & Sons, 1998. [79] I. Pepelnjak and J. Guichard. MPLS and VPN Architectures. Cisco Press, 2000. 97

Bibliographie

[80] H. Perros and K. Elsayed. Call Admission Control Schemes : A Review. IEEE Communications Magazine, 34(11), Novembre 1996. [81] J.M. Pitts and J.A. Schormans. Introduction to IP and ATM Design Performance. Wiley & Sons, 2000. [82] J. Postel. RFC 793 : Transmission Control Protocol, Septembre 1981. [83] K.K. Ramakrishnan and R. Jain. A Binary Feedback Scheme for Congestion Avoidance in Computer Networks. ACM Transactions on Computer Systems, 8(2) :158–181, Mai 1990. [84] K.K. Ramakrishnan and P.Newman. ATM FLow Control : Inside the Great Debate. Data Communication, pages 111–120, Juin 1995. [85] K.K. Ramakrishnan and J. Zavgren. Credit Where Credit Is Due. AF-TM 94-0916, Septembre 1994. [86] E. Salvadori and R. Battiti. A Load Balancing Scheme for Congestion Control in MPLS Networks. Proceedings of the Eighth IEEE International Symposium on Computers and Communication (ISCC’03), 2003. [87] C. Servin et S. Ghernaouti-Hélie. Les Hauts Débits en Télécom. Intereditions, 1998. [88] R.J. Simcoe and L. Roberts. The Great Debate Over ATM Congestion Control. Data Communications, pages 75–80, Septembre 1994. [89] D. Sisalem. Rate Based Congestion Control and its Effects on TCP over ATM. Diplomarbeit thesis. Technical University of Berlin, Mai 1994. [90] W. Stallings. ISDN and BroadBand ISDN with Frame Relay and ATM. PrenticeHall, 2001. [91] W. Stallings. Data and Computer Communication. Prentice Hall, 2003. [92] A. Tanenbaum. Réseaux, Cours et Exercices. Coédition :Dunod (Paris) et Prentice Hall International (London), 1999. [93] K.L. Thai and V. Veque et S. Znaty. Architecture des Réseaux Haut Débit : Cours, Exercices et Corrigés. Hermès, 1995. [94] C. Touati. Les Principes d’Equité Appliqués aux Réseaux de Télécommunications. PhD thesis, Université de Nice Sophia-Antipolis, Septembre 2003. [95] L. Toutain. Réseaux Locaux et Internet , Des Protocoles à l’Interconnexion. Hermès, 1999. [96] D. Tse and M. Grossglauser. Measurement-based Call Admission Control : Analysis and Simulation. IEEE INFOCOM’97, pages 981–989, 1997. [97] J.S. Turner. New Directions in Conmmunications (or Which Way to the Information Age). IEEE Communications Magazine, 24 :8–15, Octobre 1986. 98

Bibliographie

[98] J.T. Virtamo. An exact Analysis of D1 + ... + Dk /D/1 Queue. 7th ITC Seminar, Morriston, New Jersey, Paper 11.1. 1990. [99] A. Willig. Performance Evaluation Techniques. Universität Potsdam, Juin 2004. [100] X. Xiao, A. Hannan, B. Bailey, and L. Ni. Traffic Engineering with MPLS. IEEE Networking, 14(2) :28–33, Mars/Avril 2000. [101] X. Xiao and L.M. Ni. Internet QoS : A Big Picture. IEEE Networks, Mars/ Avril 1999. [102] C.Q. Ynag and A.V.S. Reddy. A Taxonomy for Congestion Control Algorithms in Packet Switching Networks. IEEE Networks Magazine, 9 :34–45, Juillet/Août 1995. [103] B. Yuhas and N. Ansari. Neural Networks in Telecommunications. Kluwer Academic Publishers, 1994.

99

Glossaire des Abréviations

Glossaire des Abréviations AAL ABR AoD ATM BDP B-ISDN CAC CBR CER CDV CLP DES DQDB GFC FDDI FDM IEEE IETF ISDN ISO ISP LAN MAC MAN MCR MPEG MPLS N-ISDN NNI OSI PCR QoS RFC

Atm Adaptation Layer Available Bit Rate Audio on Demand Asynchronous Transfert Mode Bandwidth Delay Product BroadBand Integrated Services Digital Network Call (ou Connection) Admission Control Constant Bit Rate Cell Error Ratio CLR Cell Loss Ratio Cell delay Variation Cell Loss Priority Discrete Event Simulation Distributed Queue Dual Bus General Flow Control Fiber Distributed Data Interface Frequency Division Multiplexing Institute of Electrical and Electronics Engineers Internet Engineering Task Force Integrated Services Digital Network International Standards Organisation Internet Service Provider Local Area Network Medium Acces Control Metropolitan Area Network Mean Cell Rate Moving Picture Expert Group Multi Protocol Label Switching Narrowband Integrated Services Digital Network Network Network Interface Open System Interconnection Peak Cell Rate Quality of Service Request For Comments

100

Glossaire des Abréviations

RM RM RNIS RTC SCR SDM STM TCP UBR TDM UDP UIT UNI UPC VBR VCC VCI VoD VPC WAN WDM

Ressource Management Resource Management Réseau Numérique à Intégration de Services Réseau Téléphonique Commuté Sustained Cell Rate Space Division Multiplexing Synchronous Transfert Mode Transmission Control Protocol Unspecified Bit Rate Time Division Multiplexing User Datagram Protocol Union Internationale des Télécommunications User Network Interface User Parameter Control Variable Bit Rate Virtual Channel Connection Virtual Channel Identifier Video on Demand Virtual Path Connection Wide Area Network Wavelength Division Multiplexing

101

Résumé Dans un système à partage de ressources, la congestion est présente lorsque la demande en ressources dépasse la quantité des ressources diponibles. Contrairement à ce que l’on s’attendait, les technologies à haut débit n’ont fait qu’aggraver la congestion. Par conséquent, il faut concevoir de nouveaux protocoles de contrôle de congestion qui soient approporiés aux caractéristiques de tels réseaux. Le contrôle de congestion consiste à maintenir le système en dessous du seuil de congestion, tout en optimisant l’utilisation des ressources par multiplexage statistique. Il est généralement réalisé par plusieurs moyens préventifs et réactifs. Les premiers visent à rendre l’apparition de ce phénomène exceptionnelle alors que les derniers permettent de revenir à une situation normale lorsque, malgré tout, la congestion se produit. Cette deuxième classe de méthodes est très utilisée dans les réseaux ATM afin de garantir la qualité de service (QoS) des connexions déja admises. L’objectif de ce travail est de faire une synthèse sur les méthodes de contrôle de congestion dans les réseaux haut débit. Par la suite, nous étudierons de façon plus détaillée deux algorithmes de contrôle d’admission (CAC) comme exemples de contrôle préventif dans les réseaux ATM. Mots clés : réseaux à haut débit, congestion, mode de transfert asynchrone, qualité de service, évaluation de performance, simulation à évènements discrets, contrôle d’admission. Abstract In a system with resource sharing, congestion is present when the demand for resources exceeds the quantity of available resources. Unexpectedly, new broadband technologies did nothing but worsen the congestion. Consequently, it is necessary to conceive new congestion control protocols which are appropriate to the characteristics of such networks. Congestion control consists in maintaining the system in lower part of the threshold of congestion, while optimizing the use of the resources by statistical multiplexing. It is generally carried out by several preventive and reactive means. The first aim to return the appearance of this phenomenon exceptional whereas the last make it possible to return to a normal situation when, despite everything, congestion occurs. This second class of methods is very used in ATM networks in order to guarantee quality of service (QoS) of already established connections. The aim of this thesis is to make a synthesis on the methods of congestion control in high speed networks. Thereafter, we will study in a more detailed way two algorithms of control admission (CAC) like examples of preventive control in ATM networks. . Keywords : high speed networks, congestion, asynchronous transfer mode, quality of service, performance evaluation, discrete event simulation, admission control.