Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Réseaux de télécommunication

TCP : fenêtre glissante, contrôle de congestion et équité

L'efficacité de l'arrêt-et-attente démontrée, la fenêtre glissante et le produit bande passante-délai, la connexion TCP et le contrôle de flux, le démarrage lent et l'AIMD, la formule de Mathis, l'équité démontrée, CUBIC, BBR et QUIC.

https://www.electronics-engineering.com/fr/tcp-fenetre-glissante-controle-de-congestion-aimd/

Pas encore de vote : soyez le premier à noter cette page.

IP livre les paquets au mieux (« best effort ») : ils peuvent être perdus, arriver dans le désordre ou être dupliqués. Par-dessus, TCP construit un flux d’octets fiable et ordonné entre deux programmes, et fait aussi quelque chose de plus délicat : il règle la vitesse de chaque émetteur pour que des millions de connexions partagent le réseau sans le faire s’effondrer. Dans cette leçon, nous regardons la transmission fiable avec la fenêtre glissante et la démonstration de son efficacité, la gestion de la connexion, le contrôle de congestion avec augmentation additive et diminution multiplicative, et la démonstration que ce mécanisme partage équitablement la bande passante.

L’efficacité de l’arrêt-et-attente

La façon la plus simple de transmettre de manière fiable : envoyer un paquet, attendre l’accusé de réception (ACK), puis envoyer le suivant, en retransmettant si l’accusé n’arrive pas avant un délai de garde.

Théorème. Avec des paquets de L bits, un débit R et un temps d’aller-retour RTT, la fraction du temps pendant laquelle la liaison transmet avec l’arrêt-et-attente est

    \[ U = \frac{L/R}{RTT + L/R} \]

Démonstration. L’émetteur met L/R pour envoyer le paquet ; le dernier bit arrive après le délai de propagation, et l’accusé revient après un autre : en tout, entre le début de la transmission et l’accusé, il s’écoule L/R + RTT (en négligeant la durée de l’accusé). Dans cet intervalle, la liaison n’est utilisée que pendant L/R. ∎

Avec 1 Gb/s, des paquets de 1500 octets (12 µs) et un RTT de 30 ms, U \approx 0.0004 : on n’utilise que 0,04 % de la liaison. La solution est la fenêtre glissante : on peut envoyer jusqu’à W octets sans attendre les accusés. Le débit maximal devient

    \[ \text{throughput} \le \frac{W}{RTT} \]

et pour remplir la liaison, la fenêtre doit être au moins égale au produit bande passante-délai R\cdot RTT (leçon sur l’architecture) : dans l’exemple 3,75 Mo. Si un paquet est perdu, on peut retransmettre tout ce qui suit (go-back-N) ou seulement le paquet perdu (répétition sélective, que TCP met en œuvre avec les accusés sélectifs, SACK).

La connexion TCP

TCP ouvre la connexion par la poignée de main en trois temps : SYN du client, SYN-ACK du serveur, ACK du client. Chaque octet a un numéro de séquence, et les accusés sont cumulatifs : « j’ai reçu tout jusqu’à l’octet n ». Le récepteur annonce combien de place il a dans son tampon (la fenêtre de réception) : c’est le contrôle de flux, qui empêche un émetteur rapide de submerger un récepteur lent. Le délai de retransmission s’adapte continuellement, en estimant la moyenne et la variabilité du RTT.

Le contrôle de congestion

Le contrôle de flux protège le récepteur ; le réseau doit être protégé séparément. Si tout le monde transmet trop, les files des routeurs se remplissent, des paquets sont perdus, les émetteurs retransmettent, et le réseau peut arriver à un effondrement par congestion : toute la capacité sert à des retransmissions inutiles. C’est vraiment arrivé sur Internet en 1986, et Van Jacobson a introduit le mécanisme qui, avec des variantes, est encore utilisé.

L’émetteur garde une fenêtre de congestion W, et la fenêtre utilisée est la plus petite de celle-ci et de la fenêtre de réception :

  • démarrage lent (slow start) : au début, W double à chaque RTT, pour trouver vite la capacité disponible ;
  • augmentation additive : au-delà d’un seuil, W croît d’un paquet par RTT, pour sonder prudemment s’il y a plus de place ;
  • diminution multiplicative : quand un paquet est perdu, signe qu’une file est pleine, W est divisée par deux.
Fenêtre de congestion TCP au cours du temps
Après le démarrage lent, à croissance exponentielle, la fenêtre croît linéairement jusqu’à provoquer une perte à sa valeur maximale, puis se divise par deux et recommence : la dent de scie caractéristique entre la moitié du maximum et le maximum.

En régime permanent, la fenêtre oscille en dents de scie entre W_{max}/2 et W_{max}, avec une valeur moyenne \frac{3}{4}W_{max}. On en tire la célèbre formule de Mathis : avec une probabilité de perte p, le débit est d’environ 1.22\cdot MSS/(RTT\sqrt{p}), où MSS est la taille du segment. Doubler la distance divise la vitesse par deux, et atteindre 10 Gb/s sur de longues distances exige des probabilités de perte minuscules.

L’équité

Pourquoi justement « augmentation additive, diminution multiplicative » (AIMD) ? Parce que c’est la combinaison qui conduit les connexions à se partager également la bande passante, sans que personne ne les coordonne.

Théorème. Deux connexions de même RTT qui partagent une liaison avec une politique AIMD convergent vers des débits égaux.

Démonstration. Soient x_1 et x_2 les deux débits et D = x_1 - x_2 la différence. Pendant l’augmentation additive, les deux croissent de la même quantité par RTT, donc D ne change pas. Quand la somme dépasse la capacité, les deux subissent une perte et se divisent par deux : D devient D/2. Après k pertes, la différence est D/2^k, qui tend vers zéro, tandis que la somme continue d’osciller autour de la capacité. ∎

Avec une augmentation multiplicative et une diminution additive, la différence croîtrait au lieu de diminuer. Les connexions de RTT différents ne sont pas traitées de façon égale : la plus proche croît plus vite et obtient davantage.

Les variantes modernes

Sur des réseaux rapides et lointains, une croissance d’un paquet par RTT est trop lente. CUBIC, par défaut dans Linux, fait croître la fenêtre comme une fonction cubique du temps écoulé depuis la dernière perte, indépendamment du RTT. BBR, développé par Google, n’attend pas les pertes : il estime la bande passante du goulot d’étranglement et le RTT minimal, et émet au débit estimé, en gardant les files courtes. Le protocole QUIC, sur lequel repose HTTP/3, apporte ces fonctions par-dessus UDP, avec le chiffrement, pour qu’elles puissent être mises à jour sans toucher au système d’exploitation.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x