Algorithme TCP

• 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));
• RTT (roundtrip time) : durée d'envoi puis de réception d'acquittement d'un paquet ;
• RTO (retransmit timeout) : temps de transmission maximal (souvent 2 fois le RTT) ;
• 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.

Summarize Fact Check

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.

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).

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.

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.

Plutôt que repasser en mode Slow Start lors d'une duplication de ACK (et après un passage par le mode Fast Retransmit), le segment perdu est réémis et son ACK est attendu 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.

Summarize Top Qs Fact Check

Les algorithmes qui ont (ou non) été utilisés, mais désormais obsolètes.

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].

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.

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é.

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 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).

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.