Algorithme TCP
Il existe des algorithmes de TCP différents pour répondre à l'augmentation de la bande passante des liaisons : en effet les premiers algorithmes utilisés historiquement seraient incapables de faire monter le débit suffisamment rapidement pour saturer un lien réseau à 100 Mbit/s, débit typique des réseaux locaux dans les années 2000.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Les différents algorithmes TCP sont, parmi les plus connus :
- TCP tahoe
- TCP Reno
- TCP new Reno
- TCP Vegas
Il faut comprendre que l'algorithme TCP ne connait jamais le débit optimal à utiliser pour un lien : d'ailleurs il est difficile à estimer. IP, qui porte TCP, ne garantit pas que le chemin sera stable dans le temps à travers le réseau, d'où une impossibilité à prédire le débit à utiliser. De plus le débit est aussi conditionné par d'autres facteurs comme l'existence de flux concurrents sur une partie du chemin (par exemple vous pouvez avoir plusieurs téléchargements simultanés sur des serveurs ayant différents niveaux de performance).
C'est ainsi que TCP va essayer de deviner le meilleur débit à utiliser en essayant de toujours augmenter le débit jusqu'à la survenue d'une perte de paquet parce que le réseau n'arrive pas à absorber tout le débit. En effet, les réseaux informatiques sont conçus pour être les plus simples possibles et c'est la seule possibilité qu'a un réseau pour avertir les utilisateurs qu'il est saturé.
On distingue les algorithmes TCP par la forme du slow-start (démarrage lent) et leur façon d'utiliser la bande passante disponible. On parle parfois d'agressivité du protocole.
Glossaire modifier
- MSS (maximum segment size) : la taille maximum d'un segment (données TCP uniquement) ;
- awnd (advertised window) : fenêtre de réception ;
- cwnd (congestion window) : fenêtre de congestion ;
- swnd (sending window) : fenêtre d'émission (= min (cwnd, awnd));
- RTO (retransmit timeout) : temps de transmission maximal (souvent 2 fois le RTT) ;
- RTT (roundtrip time) : durée d'envoi puis de réception d'acquittement d'un paquet ;
- ssthresh (slow start threshold) : taille maximum d'une fenêtre d'émission en slow start ;
- LFN (long fat network) : réseau avec une grande bande passante mais aussi un long délai de réponse.
Les différentes phases basiques des algorithmes d'évitement de congestion modifier
L'ensemble des algorithmes présentés plus tard se basent sur ces techniques, ou une partie. Le principe de base d'évitement de congestion est de réagir en réduisant le débit de la connexion.
Les protocoles mesurent l’importance du problème en observant divers phénomènes comme l’augmentation du temps de réponse ou la duplication de messages de type ACK signifiant une perte de paquet par exemple.
Si le protocole ne réagit pas aux congestions, le nombre de retransmissions peut continuer à augmenter et aggraver ainsi la congestion. C’est la raison pour laquelle un algorithme de contrôle réduit le flux en cas de congestion.
Les différents algorithmes présentés ci-dessous doivent être implantés dans chaque appareil souhaitant l'utiliser. Il n'y a pas de système central d'évitement de congestion, chaque élément du réseau doit adapter son flux d'émission.
Slow Start modifier
Lors du démarrage d'une connexion, nous ne connaissons pas le lien qu'il y a entre nous et le destinataire, donc on va progressivement augmenter le nombre de paquets qu'on envoie.
Le but est donc de trouver la bande passante disponible, et utiliser toutes les ressources à disposition. On va alors utiliser une fenêtre d'émission (swnd), qui représente un nombre de paquets à envoyer sans attendre d'acquittement.
Cette fenêtre grandira au fur et à mesure que nous recevons des acquittements pour les paquets envoyés (chaque ACK fera augmenter cette fenêtre de 1, autrement dit, après chaque RTT la taille de la fenêtre doublera, tant qu'il n'y a pas de congestion).
Congestion Avoidance modifier
Au-delà d'une certaine limite de valeur de cwnd (slow start threshold, ssthresh), TCP passe en mode d'évitement de congestion. À partir de là, la valeur de cwnd augmente de façon linéaire et donc bien plus lentement qu'en slow start : cwnd s'incrémente de un MSS (= un paquet) à chaque RTT.
Dans ce mode de fonctionnement, l'algorithme détecte aussi rapidement que possible la perte d'un paquet : si nous recevons trois fois le ACK du même paquet, on n'attend pas la fin d'un timeout pour réagir.
En réaction à cette perte, on fait descendre la valeur de ssthresh ainsi que cwnd (on repasse éventuellement en mode de Slow Start). On utilise la technique de Fast Retransmit pour renvoyer rapidement les paquets perdus.
Fast Retransmit modifier
Comme expliqué plus tôt, on passe par cet algorithme en cas de détection de perte de segment(s) lorsque nous sommes en mode « Congestion Avoidance ».
Un ACK dupliqué s'explique par la manière dont les segments sont traités à la réception. En effet, si nous recevons un segment TCP qui n'est pas dans l'ordre attendu, on doit envoyer un ACK avec une valeur égale au numéro de segment qui était attendu.
S'il y a une perte de segment, le destinataire n'enverra plus que des ACK avec le numéro du segment perdu.
On peut donc pallier cette perte rapidement (après 3 ACK dupliqués généralement), sans attendre le timeout.
Fast Recovery modifier
Plutôt que repasser en mode Slow Start lors d'une duplication de ACK (et après un passage par le mode Fast Retransmit), nous renvoyons le segment perdu et on attend un ACK[Qui ?] pour toute la fenêtre transmise précédemment avant de retourner en mode Congestion Avoidance. Si on atteint le timeout, on repart en mode Slow Start.
Grâce à cette technique nous évitons de baisser le débit d'une façon trop brutale.
Les algorithmes historiques modifier
Les algorithmes qui ont (ou non) été utilisés, mais désormais obsolètes.
TCP tahoe modifier
La première implémentation d'algorithme d'évitement de congestion de TCP est TCP Tahoe. Elle est apparue pour la première fois dans le système BSD4.3.
C'est la plus simple et la moins efficace (tous types de problèmes confondus). Cette version utilise un système de slow start, avec une valeur initiale de cwnd à 1 et une valeur de cwnd maximum de ssthresh (avec une valeur par défaut de 65535).
La première fois qu'on effectue du slow start on arrive à une perte de paquet, dans ce cas la valeur de cwnd courante sera notre nouveau ssthresh puis on remet la valeur de cwnd à 1.
Une fois ssthresh atteint, on entre en Congestion Avoidance. À partir de là la valeur de cwnd augmente de façon linéaire et donc plus lentement qu'en Slow Start. Lorsqu'on reçoit trois fois le même ACK, il y a une congestion, on n'attend pas le timeout avant de renvoyer le paquet perdu (fast retransmit). Il n'y a pas de Fast Recovery, on passe la valeur de ssthresh à la moitié de cwnd courant, cwnd passe à 1 MSS et on retourne en Slow Start.
Un exemple de comportement de cet algorithme est illustré à la figure[1].
Reno modifier
La différence avec Tahoe est qu'il utilise le Fast Recovery. Une fois la réception de trois ACK dupliqués on diminue de moitié la valeur de cwnd, on met le seuil de ssthresh à la taille de cwnd, on fait un fast retransmit et on passe en Fast Recovery.
Si on a un timeout on repart en Slow Start comme avec Tahoe, avec la fenêtre de congestion à 1 MSS.
Reno permet donc de ne pas repartir en Slow Start (et avec un cwnd à 1) dès qu'il y a congestion. Les débits sont donc plus stables.
New Reno modifier
Cet algorithme s'appelle « NewReno » parce qu'il n'est qu'une modification légère (mais significative) de l'algorithme Reno. En effet, la modification s'opère au niveau de la phase de Fast Recovery : on reste dans ce mode tant que nous n'avons pas reçu les ACK de tous les paquets perdus.
Lorsqu'il y a une perte de plusieurs segments d'une même « rafale » envoyée, à la réception d'un acquittement partiel on renvoie le segment perdu suivant, sans sortir du mode Fast Recovery, contrairement à Reno qui sort de ce mode dès la réception d'un ACK non dupliqué.
Vegas modifier
Plutôt que d'attendre une perte de paquet, Vegas prend en compte le temps de réponse du destinataire (le RTT) afin d'en déduire le ratio auquel envoyer les paquets.
En fonction du temps de réponse, on est capable de supposer l'état des buffers des routeurs intermédiaires. Vegas modifie pour cela plusieurs algorithmes vus jusqu'ici (Slow Start, Congestion Avoidance, Fast Retransmit).
Grâce à cette technique Vegas a de meilleurs débits et moins de pertes de paquets que Reno. Cet algorithme permet d'atteindre un partage équitable des ressources. De même, il y a assez peu de pertes avec Vegas puisqu'à l'état stable, le débit correspond de près à la capacité du lien\cite{VEGAS}.
Puisque Vegas permet de s'adapter plus rapidement aux changements de disponibilité du lien, les performances se dégradent lorsqu'il est utilisé avec d'autres protocoles qui ne prennent pas en compte l'état du lien *avant* une perte de paquet.
Un inconvénient cependant, il nécessite une modification de la pile TCP pour l'émetteur et le récepteur.
Westwood(+) modifier
Westwood est une réécriture de New Reno côté émetteur pour avoir une meilleure gestion des LFN (Long Fat Network).
Il modifie les valeurs de ssthresh et de cwnd en fonction d'estimations qu'il fait sur la bande passante disponible. La première version faisant de mauvaises estimations, elle a été corrigée par la suite, d'où le nom Westwood+.
Ces estimations se basent comme pour Vegas sur le temps de réponse du destinataire (RTT), mais ces estimations sont utilisés différemment.
Il possède un mécanisme pour détecter qu'il n'y a pas de congestion (Persistent Non Congestion Detection, PNCD), ce qui lui permet de rapidement utiliser la bande passante disponible.
Westwood modifie le Slow Start (il devient moins agressif) en y ajoutant une phase : « Agile Probing », ce qui lui permet (avec les estimations via le RTT) d'avoir une phase d'accroissement du cwnd\cite{UCLA} quasi exponentielle puis de se stabiliser, puis d'accroître, puis de se stabiliser, , etc.
L'algorithme gagne beaucoup en efficacité, mais on perd en équité puisqu'en cas de pertes de paquets il ne s'adapte pas brutalement en divisant son cwnd par deux.
C'est ce qui fait également qu'il est adapté aux réseaux sans fils, qui ont des pertes aléatoires (et non forcément dues à des congestions).
SACK TCP modifier
Les algorithmes de Slow Start et de Congestion Avoidance sont les mêmes que pour TCP Reno.
Selective ACK TCP permet, lors d'une perte, de dire qu'on a reçu les paquets jusqu'à la séquence numéro N, mais aussi de préciser à l'émetteur qu'on a bien reçu certains des paquets suivant. L'émetteur n'a plus à renvoyer des segments déjà reçus.
SACK est une option qui se négocie à la connexion.
Cette option permet de gagner un peu de performances, lors de pertes de segments, mais il est nécessaire d'avoir les deux parties (émetteur et récepteur) qui l'implémentent.
Les implémentations actuelles modifier
Deux algorithmes d'évitement de congestion sont très présents dans les systèmes d'exploitation courants : CUBIC (Linux) et CTCP (Microsoft Windows).
Avant de voir leurs différences, on va regarder[style à revoir] l'algorithme dont CUBIC est hérité, BIC. Le but de ces algorithmes est de garder un débit aussi proche que possible de la bande passante disponible.
BIC modifier
Les algorithmes précédents ne sont pas adaptés pour des réseaux rapides et avec une importante bande passante (plusieurs gigabits par seconde). Ils laissent une certaine partie de la bande passante non utilisée.
BIC garde un bon débit, une bonne équité même avec les autres algo d'évitement de congestion de TCP.
Une version un peu simplifiée de l'algorithme pourrait être : lorsqu'il y a une perte, BIC réduit cwnd par un certain coefficient. Avant de réduire on va garder en mémoire la valeur de cwnd qui sera notre maximum (Wmax), et la nouvelle valeur sera notre valeur minimum (Wmin).
À partir de ces deux valeurs on va rechercher la valeur intermédiaire pour laquelle nous n'avons pas de pertes (recherche dichotomique).
L'algorithme fait attention à ne pas trop augmenter cwnd, aussi si lors de notre recherche on fait des sauts trop grands (défini par un certain seuil), on préfèrera[style à revoir] accroître cwnd de manière logarithmique. Une fois la différence amoindrie, on pourra repasser en recherche dichotomique jusqu'à arriver à Wmax.
À partir de là on recherche un nouveau maximum, avec une croissance linéaire : on cherche s'il y a un maximum proche.
Si après une certaine période on n'a pas de perte, alors on se dit que le maximum est bien plus loin et on augmente de nouveau la taille de la fenêtre de manière exponentielle.
BIC permet une bonne équité, il est stable en maintenant un haut débit et qu'il permet une bonne mise à l'échelle. Malgré ses qualités, il reste trop agressif durant sa phase montante. Mais surtout il provoque une inégalité avec les flux ayant des RTT longs.
Cet algorithme a été utilisé dans Linux, depuis on lui préfère sa variante plus élaborée : CUBIC.
CUBIC modifier
CUBIC a une phase montante plus douce que celle de BIC, ce qui le rend plus « amical » envers les autres versions de TCP. CUBIC est plus simple car ne possède qu'un seul algorithme pour sa phase montante, et n'utilise pas les acquittements pour augmenter la taille de la fenêtre, on préfèrera[style à revoir] parler d'évènement de congestion. C'est ce qui rend CUBIC plus efficace dans les réseaux à bas débit ou avec un RTT court.
Compound TCP modifier
Une des grandes particularités de CTCP est qu'il maintient deux fenêtres de congestion.
La première est la fenêtre qui augmente de façon linéaire mais décroît en cas de perte via un certain coefficient. La seconde fenêtre est liée au temps de réponse du destinataire.
On combine donc des méthodes liées à la perte de paquet (comme TCP Reno) et d'adaptation préventive à la congestion (comme TCP Vegas), d'où le nom « Compound » (composé).
La taille de la fenêtre réellement utilisée est la somme de ces deux fenêtres. Si le RTT est bas, alors la fenêtre basée sur le délai augmentera rapidement. Si une perte de segments survient, alors la fenêtre basée sur la perte de paquet diminuera rapidement afin de compenser l'augmentation de la fenêtre basée sur le délai.
Avec ce système, on cherchera à garder une valeur constante de la fenêtre d'émission effective, proche de celle estimée.
Le but de ce protocole est de maintenir de bonnes performances sur des réseaux avec un haut débit et avec un grand RTT.
Les critères d'évaluation modifier
Ces différents critères sont :
- augmentation linéaire/exponentielle du débit ;
- diminution linéaire/exponentielle du débit après un événement (perte de paquets, dépassement d'un seuil, …) ;
- l'existence de seuils de débit dans l'algorithme (par exemple l'augmentation peut devenir prudente une fois qu'elle arrive au niveau de sa dernière meilleure performance).
Il n'est pas aisé de parler de meilleure version TCP : il y a des versions adaptées aux réseaux très hauts débits, il y a des versions adaptées aux petits débits, il y a des versions adaptées aux réseaux qui font beaucoup d'erreurs.
Enfin, on observe que les algorithmes TCP sont tous compatibles entre eux (puisqu'il n'y a pas de modification du segment TCP mais seulement une variation sur leur vitesse d'arrivée). Par exemple, Windows Vista utilise Compound TCP alors que les noyaux Linux utilisent CUBIC TCP depuis la version 2.6.19.
Notes et références modifier
- Les Réseaux, Eyrolles, 2008, 6e édition
Liens externes modifier
- (en) BIC et CUBIC, consulté le ;
- (en) TCP Variations: Tahoe, Reno, New Reno, Vegas, Sack, consulté le ;
- (en) TCP Westwood+ site officiel, consulté le .
- (fr) Cours sur les contrôles de congestion dans TCP,consulté le ;
