NISSRI-MLL
Télécharger le fichier pdf d’un mémoire de fin d’études
Contrôle de Congestion
Le contrôle de congestion concerne l’allocation des ressources du réseau de manière à ce que celui-ci puisse encore opérer à un niveau de performance optimum quand les demandent excèdent sa capacité ou en sont très proches [3].
La congestion apparaît lorsque la monté du trafic entraîne une perte considérable de paquets dans le réseau de manière à ce que peu, ou aucun paquet soit arrivé à destination. Un cas ultime de congestion de réseau, que l’on appelait congestion collapse (ce qui signifie littéralement « effondrement du réseau dû à la congestion »), a été observé vers l’année 1987 dans le réseau ARPANET. En 1988, pour remédier à celle-ci, Van Jacobson [2] a amélioré le TCP (Transmission Control Protocol) de manière à ce que le débit de transmission soit ajusté suivant le niveau de congestion du réseau.
Ainsi, le control de congestion est devenu un problème crucial dans le développement de l’Internet. En effet, la congestion dans Internet pourrait causer un taux de pertes de paquets élevé, une augmentation du temps de latence de bout en bout, et dans le cas ultime, pourrait causer la congestion collapse similaire à celle qui a été observée en 1987. Ainsi, divers algorithmes pour le contrôle de congestion ont été intensivement étudiés ces dernières années, et le besoins de développer des algorithmes plus efficaces pour faire face à l’augmentation de trafics se fait toujours sentir.
Sur le réseau Internet, on peut distinguer deux principaux composants en matière de contrôle de congestion : les algorithmes sources, qui sont effectués par TCP, donc implémentés dans les équipements finaux tel qu’un ordinateurs d’un utilisateur ou un serveur; et les algorithmes de lien qui sont effectués par les Active Queue Management tels que le Drop Tail ou le RED Les algorithmes AQM sont implémentés dans les équipements réseaux, tel qu’un routeur ou un switch, pour maintenir un partage équitable de débit avec un taux de pertes de paquets réduit et un temps de latence minimal.
Problème principal de la congestion des réseaux
Une congestion apparaît dans le réseau lorsque le nombre de demandes de ressources est largement supérieur au nombre de ressources disponibles, ceci dû à des incohérences entre les débits des liaisons causées par le mélange de plusieurs réseaux hétérogènes utilisant des technologies différentes. Ce problème de congestion ne pourrait pas être résolu par une augmentation de la capacité de la file d’attente. Il est évident qu’un très fort trafic pourrait toujours amener à un débordement de la mémoire tampon siège de ladite file. Ce problème ne pourrait pas non plus être résolu par une mise à niveau des liaisons vers des liaisons à haut débit, ni la mise à niveau du processeur vers un processeur plus puissant. En effet, une liaison haut-débit connectée à un routeur doté d’un processeur très puissant qui va ensuite être connecté à une liaison bas-débit causera toujours une congestion au point d’interconnexion. Dans ce point de vu, nous dirons que les matériels ne sont que des facteurs constants et que leurs mises à niveau ne participent que très peu dans le contrôle de la congestion.
Finalement, la congestion est un problème dynamique et les contrôles statiques traditionnels (par exemple un surdimensionnement) ne pourront pas à eux seuls résoudre ce problème. Ainsi, un mécanisme de contrôle intelligent pourrait être déployé dans le réseau pour avoir une solution optimale au problème de congestion.
Conception d’un Contrôleur de Congestion
Dans le paragraphe précédent nous avons vu que la congestion est un problème dynamique et qu’une solution dynamique devrait être mise en place pour la résoudre. La question qui se pose sera donc : comment pourrait-on concevoir un mécanisme qui va automatiquement, et idéalement, ajuster le débit de transmission de la source pour éviter la congestion, ou bien d’en sortir? Pour répondre à cette question, nous allons examiner d’un peu plus près les éléments qui sont impliqués dans le processus de communication [4]:
En premier lieu, le trafic provient de la source ; donc c’est là qu’est faite la première décision (Quand envoyer les paquets ? Combien de paquets seront envoyés en même temps ? …)
Selon le scénario, chaque paquet traverse un certain nombre de nœuds intermédiaires. Ces nœuds sont typiquement dotés d’une file d’attente dans la taille croît en présence d’une congestion ; les paquets sont rejetés lorsque la longueur de la file dépasse la capacité de la mémoire tampon.
Eventuellement, le trafic atteint la destination. C’est ici que la performance du réseau ce fait sentir le plus. On rappelle que le but ultime de n’importe quel réseau de communication est de maximiser la satisfaction des utilisateurs. Ici, on suppose qu’il n’y a qu’une seule destination pour simplifier les choses.
Le trafic peut être contrôlé au niveau de la source et au niveau des nœuds intermédiaires tandis que la performance peut être mesurée par les nœuds intermédiaires et à la destination. Désignons donc les membres du premier groupe par contrôleurs et ceux du deuxième groupe par points de mesure. Ainsi, il nous faut au moins un contrôleur et un point de mesure pour mettre en place un schéma de contrôle de congestion impliquant une chaîne de retour ou rétroaction (feedback).
Commande en boucle fermée Vs Commande en boucle ouverte
En théorie des commandes, les systèmes qui utilisent des informations de retour sont appelés des systèmes en boucle fermée tandis que ceux qui n’en utilisent pas sont appelés des systèmes en boucle ouverte.
Un exemple de systèmes en boucle ouverte est un programmateur d’arrosage automatique qui ne prendrait pas en compte l’humidité du sol [2]. Ainsi, le programmateur automatique fonctionnerait même sous la pluie. Ce type de commande n’est pas un très bon choix lorsqu’il s’agit de contrôler les congestions dans les réseaux.
Dans les réseaux informatiques, appliquer une commande en boucle ouverte implique une connaissance a priori du réseau lui-même. Par exemple, une connaissance précise de la bande passante du goulet d’étranglement. Ainsi, un réseau qui se base seulement sur une commande en boucle ouverte serrait tenté d’utiliser une réservation de ressources. Cette dernière étant assurée par une entité qu’on appelle contrôleur d’admission. Cette manière de faire a été largement utilisée dans les réseaux téléphoniques traditionnels pour faire face aux congestions : quand un utilisateur veut appeler quelqu’un mais que le réseau est surchargé, l’appel est immédiatement rejeté par le contrôleur d’admission. Donc, historiquement, le contrôle d’admission dans les réseaux en mode connectés pourrait être vu comme le prédécesseur du contrôle de congestion dans les réseaux à commutation de paquets.
Les choses sont relativement simples dans les réseaux téléphoniques : un appel est supposé occuper une bande passante fixe, donc la capacité du lien peut être divisée par une valeur prédéfinie pour calculer le nombre d’appels admis par le système. Par contre, dans un réseau à service multiple tel qu’Internet, où diverse applications doivent être supportées, ni la bande passante ni le comportement des applications ne sont connus à l’avance. Donc, pour utiliser de manière efficace les ressources disponibles, il pourrait être nécessaire que le contrôleur d’admission fasse une mesure de la bande passante utilisée, puis mettre en place une chaîne de retour pour informer la source sur l’état de ladite bande passante. Enfin, il faut noter que la commande en boucle ouverte et la commande en boucle fermée ne s’excluent pas mutuellement, elles sont complémentaires.
Contrôle de congestion et contrôle de flux
Puisque les nœuds intermédiaires peuvent agir en même temps comme un contrôleur et un point de mesure, un schéma de contrôle de congestion pourrait théoriquement exister où ni la source ni le destinataire ne sont impliqués. Cependant, ce n’est pas un choix très pratique du fait que la majorité des technologies du réseau sont conçus pour opérer dans une large gamme d’environnements, incluant celui avec la configuration minimale où une source et un destinataire sont interconnectés via une seule liaison sans passer par de nœuds intermédiaires. Même si la congestion n’est pas réellement un grand problème dans ce scénario, il serait possible que le destinataire ait le besoin d’avoir des moyens pour dire à la source de diminuer la vitesse à laquelle elle envoie les données, ceci dû, par exemple, au fait que le destinataire soit occupé à effectuer des tâches plus pressantes ou bien que celui-ci ne soit pas suffisamment rapide. Cette fonctionnalité qui permet d’informer la source de réduire son débit de transmission est appelée contrôle de flux.
Le but principal du contrôle de flux est de protéger le destinataire face à la surcharge tandis que celui du contrôle de congestion est d’en protéger le réseau. Les deux techniques utilisent des mécanismes similaires : une information de retour (feedback) est utilisée pour ajuster le débit de transmission. Puisqu’il serait raisonnable de protéger à la fois le destinataire et le réseau de la surcharge, il est plus commode que la source utilise un débit de transmission obtenu par le minimum entre celui recommandé par le contrôle de flux et celui calculé par le contrôle de congestion. Ainsi, à cause de cette ressemblance, les deux termes « contrôle de congestion » et « contrôle de flux », sont utilisés de manière synonyme.
Contrôle adaptatif de congestion
D’après le paradigme de la théorie des contrôles adaptatifs, les informations obtenues par les mesures fait sur les états du réseau sont utilisées pour mettre à jour en temps réelle les paramètres du contrôleur [1]. Cette procédure d’ajustement est conçue pour assurer la stabilité, la convergence et la robustesse du système en boucle fermée et ceci malgré la présence d’un certain nombre de paramètres incertains et des perturbations externes. L’architecture d’un contrôle adaptative est illustrée sur la Figure 1.06.
Du fait que la représentation du système à contrôler considéré est de nature incertaine, un contrôle basé sur l’approximation serait d’une grande aide. Des exemples de ce type de contrôle sont les contrôles par logique floue ou par réseaux de neurone.
Comme il a été vu précédemment, le problème de contrôle de congestion peut être vu comme un problème de régulation. Ainsi, les outils mathématiques provenant de la théorie des commandes peuvent être empruntés pour mettre en place des solutions rigoureuses à la congestion.
Contrôle de congestion avec TCP
TCP est un protocole de la couche de transport du modèle en couches TCP/IP. La couche transport étant la couche qui définit comment les échanges de données vont se faire. Ainsi, TCP est le premier sur la pile de protocole à travailler de bout en bout (Figure 1.07).
TCP ajuste le débit de transmission de l’émetteur à ce lui demandé par le destinataire. Pour ce faire, ce dernier va utiliser un champ de 16 bit du segment ACK (acquittement) pour communiquer à l’émetteur la quantité maximale d’octets qu’il peut recevoir. Cette quantité demandée s’appelle advertised window et on le note par rwnd. Le rwnd limite le débit maximal de transmission étant donné que celui-ci indique la capacité du destinataire à accepter (taille de la mémoire tampon) et à traiter (vitesse de calcule) les données. La manière dont un émetteur envoie ces paquets avec TCP se fait selon le mécanisme de glissement de fenêtre (Figure 1.08). La fenêtre étant définie comme le nombre de paquets que l’on peut envoyer simultanément sans attendre l’arrivée d’un acquittement. La Figure 1.08 peut être décrite comme suit :
les segments compris dans la fenêtre sont candidats à la transmission ;
les segments en arrière (à gauche) de la fenêtre sont reçus et acquittés ;
les segments en avant (à droite) de la fenêtre ne sont pas encore envoyés et attendent que la fenêtre glisse vers eux pour qu’ils soient enfin transmis ;
La taille de la fenêtre est ajustée (augmentée) à chaque fois qu’un ACK ait été reçu.
Si on examine d’un peu plus près sont fonctionnement, TCP effectue des tâches plus ou moins contradictoire : d’un côté, celui-ci a pour raison d’existence d’assurer une communication fiable, avec un débit de transmission élevé, et ce qui va fort probablement conduire à une surcharge du réseau. Pourtant, d’un autre côté, TCP se doit de protéger le réseau contre les effets néfastes de la congestion. Pour gérer ce compromis, on a ajouté à TCP des algorithmes qui vont permettre de gérer la congestion. Ces algorithmes sont au nombre de quatre et sont :
Slow-start (démarrage en douceur)
Congestion avoidance (évitement de congestion)
Fast retransmit (retransmission rapide)
Fast recovery (récupération rapide)
On va voir brièvement un à un comment ces algorithmes fonctionnent.
Les algorithmes TCP
Slow-start
Cet algorithme est utilisé pour commencer la transmission des paquets tout en sondant la bande passante disponible. Le sondage doit être fait pour éviter de congestionner prématurément le réseau, suite à une transmission en rafale de données (qu’on appelle burst) par exemple. Ceci aussi du fait que la bande passante est une condition initiale non connu par l’émetteur.
Pour implémenter les algorithmes de contrôle de congestion TCP, deux variables supplémentaires ont été introduites : cwnd et ssthresh
cwnd : congestion window (fenêtre de congestion), limite la quantité de données que l’émetteur transmet à travers le réseau avant la réception d’un ACK.
ssthresh : slow-start threshold (seuil du démarrage en douceur), utilisé pour déterminer si le slow-start doit être activé ou arrêté.
D’après l’algorithme de la Figure1.10, on peut constater que slow-start assure une croissance exponentielle de cwnd.
La valeur de ssthresh peut être choisie arbitrairement élevée mais pourrait être réduit à la suite d’une détection de congestion. Dans certaines implémentations, ssthresh est initialisé à rwnd.
|
Table des matières
INTRODUCTION GENERALE
CHAPITRE 1 GENERALITE SUR LE CONTROLE DE CONGESTION ET LE TRAFIC INTERNET
1.1 Contexte actuel
1.1.1 Internet
1.1.2 Convergence IP
1.2 Contrôle de Congestion
1.2.1 Problème principal de la congestion des réseaux
1.2.2 Conception d’un Contrôleur de Congestion
1.2.3 Contrôle adaptatif de congestion
1.2.4 Contrôle de congestion avec TCP
1.3 Gestion du trafic Internet – Point de vue FAI
1.3.1 Nature du trafic Internet
1.3.2 Qualité de Service (QoS)
1.4 Conclusion
CHAPITRE 2 : LES ALGORITHMES AQM
2.1 Introduction
2.2 Conception d’un AQM basée sur la théorie des commandes
2.3 Drop Tail
2.3.2 Synchronisation globale
2.4 Random Early Detection
2.5 Variantes de RED
2.5.1 Adaptive RED (ARED)
2.5.2 Gentle RED (GRED)
2.5.3 Modified RED (MRED)
2.5.4 BLUE
2.6 Explicit Congestion Notification (ECN)
2.6.1 Mécanisme de l’ECN
2.6.2 Bénéfice de l’ECN
2.6.3 Lacune de l’ECN
2.7 Application des algorithmes AQM dans le cadre des réseaux sans fils
2.7.1 Quelques considérations spécifiques des AQM pour le sans fils
2.7.2 4G : Amélioration de la performance de TCP pendant le handover intra LTE
2.8 Conclusion
CHAPITRE 3 : MODELES MATHEMATIQUES TCP/AQM
3.1 Introduction
3.2 Modélisation des pertes de paquets
3.3 Modélisation du trafic
3.3.1 Propriétés d’un compteur de Poisson
3.3.2 Equation différentielle de la taille de fenêtre
3.4 Modèle linéaire d’un système TCP/AQM
3.4.2 Linéarisation
3.4.3 Spécification du problème de contrôleur AQM
3.4.4 Stabiliser la loi de commande AQM
3.5 Modèle d’un contrôleur RED (Random Early Detection)
3.5.2 Description de RED
3.5.3 Ajuster RED
3.6 AQM par Commande Proportionnelle P
3.7 AQM par Commande Proportionnelle-Intégrale (PI)
3.8 Conclusion
CHAPITRE 4 : GESTION ADAPTATIVE DE FILE D’ATTENTE
4.1 Introduction
4.2 Rappel sur l’algorithme PI AQM
4.3 Description de IAPI
4.3.1 Première idée : amélioration du taux de réponse
4.3.2 Deuxième idée : réduire le dépassement
4.3.3 Troisième idée : diminuer la fluctuation en régime permanente
4.3.4 Paramètres de l’algorithme IAPI
4.4 EVALUATION DE PERFORMANCES DE IAPI
4.4.1 Topologie à un seul goulet d’étranglement
4.4.2 Topologie à plusieurs goulets d’étranglement
4.5 Conclusion
CONCLUSION GENERALE
ANNEXE 1 : LINEARISATION DU MODELE FLUIDE DE TCP
ANNEXE 2 : PRESENTATION DE L’OUTIL DE SIMULATION NS2
ANNEXE 3 : CODE OTcl DES SIMULATIONS
BIBLIOGRAPHIE
