Contrôle de congestion

La congestion commence lorsque le trafic atteint une partie du réseau plus vite qu’elle ne peut l’acheminer, pendant une période prolongée. Les paquets attendent dans un tampon de sortie du routeur, appelé file d’attente. Le goulot d’étranglement est la liaison dont la capacité disponible pour ce trafic est la plus faible sur son chemin.

Suivre le surplus

Supposons qu’un routeur reçoive 12 Mbps pour une liaison de sortie capable d’émettre à 10 Mbps. Il ne peut pas accélérer la sortie pour l’adapter à l’entrée. Chaque seconde, 2 mégabits restent en attente, soit 250 000 octets après division par 8. Initialement vide, un tampon de 1 000 000 d’octets se remplit en :

Un paquet qui rejoint la file derrière cette quantité de données attend que la liaison transmette les données qui le précèdent :

Une fois le tampon constamment plein, la sortie n’achemine toujours que 10 Mbps. Environ 2 Mbps sur les 12 Mbps entrants sont rejetés, soit un sixième du trafic offert. Ces calculs supposent des débits d’arrivée et de départ constants ; le rythme de chaque paquet ajoute de petites variations.

Déterminer si la file va se vider

Une courte rafale est différente d’une surcharge durable. Une file peut absorber une rafale et se vider lorsque le débit d’arrivée descend sous le débit de sortie. Si le débit d’arrivée est constant et égal au débit de sortie, une file existante persiste : chaque départ est remplacé par une arrivée. Un débit d’arrivée durablement supérieur au débit de sortie allonge la file jusqu’à ce que le tampon soit plein.

Le trafic réel est irrégulier. Même lorsque le taux d’utilisation moyen est inférieur à la pleine capacité, les rafales font attendre les paquets. Près de la capacité maximale, il reste peu de temps libre pour évacuer ces rafales ; le délai moyen augmente donc fortement. La congestion augmente surtout la composante d’attente en file du délai des paquets ; le traitement, la transmission et la propagation sont des composantes distinctes.

Nommer le débit considéré

Une différence de débit peut faire apparaître le goulot d’étranglement : un réseau local à 1 Gbps peut alimenter une liaison d’accès à 50 Mbps. L’agrégation a le même effet lorsque plusieurs entrées d’un routeur partagent une sortie. Le trafic d’une seule entrée peut sembler modeste alors que le trafic combiné des entrées surcharge cette sortie.

Choisir la bonne limite

Le contrôle de flux protège le tampon du récepteur à l’aide de la fenêtre de réception qu’il annonce. Le contrôle de congestion protège le chemin entre les extrémités. Un récepteur peut disposer de beaucoup de mémoire libre alors qu’un routeur sur le chemin rejette des paquets.

Un tampon de routeur plus grand peut accueillir une rafale plus longue, mais une surcharge durable remplit tout tampon de capacité finie et ajoute du temps d’attente. Une liaison goulot d’étranglement plus rapide supprime ce manque de capacité. Une autre liaison limite alors le chemin ; elle ne devient congestionnée que lorsque le trafic dépasse la capacité qui y est disponible.

Une liaison saturée n’est utile que si son trafic contribue à l’acheminement de nouvelles données. La congestion consomme de la capacité de différentes façons qui peuvent réduire l’acheminement utile alors même que le réseau reste occupé.

Compter les conséquences

Le délai d’attente en file arrive en premier. Un appel vidéo peut devenir difficile à suivre avant même que des paquets soient rejetés, parce que la parole arrive trop tard. La fiabilité seule ne peut pas corriger ce délai.

Les paquets perdus créent une deuxième conséquence : un émetteur assurant un transfert fiable les retransmet. Si une liaison à 10 Mbps achemine des paquets de même taille et que 20 % répètent des données déjà acheminées sur cette liaison, 8 Mbps au maximum transportent de nouvelles données :

Le débit utile de l’application est inférieur une fois pris en compte les en-têtes et les éventuelles pertes ailleurs. L’activité de la liaison surestime donc la progression de l’application.

Certaines retransmissions sont inutiles. Un paquet peut attendre dans une longue file lorsque le temporisateur de l’émetteur expire. Son remplaçant entre alors dans le même réseau chargé. Les deux copies peuvent arriver, mais le récepteur ne conserve les données qu’une seule fois. L’attente en file a transformé un problème de délai en charge offerte supplémentaire.

Regarder en amont d’un rejet

Un rejet près de la destination peut gaspiller le travail de plusieurs liaisons précédentes. Imagine un paquet qui traverse les liaisons A et B avant d’être rejeté dans la file pour C. Les transmissions sur A et B ont utilisé de la capacité sans acheminer ce paquet à destination. Lorsque cette situation se répète, il reste moins de capacité en amont pour le trafic qui aurait pu atteindre sa destination.

À mesure que la charge offerte augmente, le débit effectif augmente lui aussi au départ. Cependant, si les rejets en aval sont assez nombreux, augmenter la charge consacre davantage de trafic à un travail qui sera gaspillé. Le débit effectif de bout en bout peut atteindre un maximum puis diminuer. L’effondrement par congestion est le cas extrême : la charge offerte reste élevée tandis que le débit utile tend vers zéro.

En octobre 1986, le débit effectif entre Lawrence Berkeley Laboratory et UC Berkeley est passé de 32 kbps à 40 bps, soit une division par 800. Les travaux de Jacobson et Karels en 1988 ont introduit une réponse coordonnée : démarrage lent, évitement de congestion, meilleure estimation du temps aller-retour et recul exponentiel du temporisateur. Le contrôle de la fenêtre et des temporisateurs bien réglés agissent sur différentes parties de la boucle de rétroaction.

Trouver la plage de fonctionnement utile

Le coude et la falaise de Raj Jain décrivent deux limites. Au-delà du coude, une charge supplémentaire apporte peu de débit effectif mais beaucoup plus de délai. Au-delà de la falaise, le débit effectif baisse à mesure que les pertes et le travail gaspillé dominent. Le contrôle de congestion cherche à assurer un acheminement efficace près du coude tout en restant loin de l’effondrement.

Internet n’a pas de contrôleur central qui attribue un débit à chaque émetteur. Chaque émetteur doit réagir aux retours qu’il observe. Si l’un continue d’émettre à un débit élevé et fixe pendant que les autres ralentissent, il peut prendre leur capacité et aggraver la surcharge.

La retransmission rend un flux d’octets fiable, mais elle ne rend pas les pertes gratuites. La récupération consomme de la capacité et retarde l’acheminement des données manquantes ; attendre un temporisateur de retransmission peut bloquer la connexion bien plus longtemps que la récupération rapide.

Un émetteur ne voit pas directement toutes les files des routeurs sur son chemin. Le contrôle de congestion est un processus de rétroaction : observer l’acheminement, déterminer le sens des observations, puis ajuster la quantité ou le débit du trafic entrant dans le réseau.

Identifier l’origine du retour

Dans le contrôle de bout en bout, les extrémités déduisent la congestion des pertes ou des délais sans message explicite des routeurs. Reno utilise les pertes. Vegas utilise les changements du temps aller-retour. BBR construit un modèle du chemin à partir de mesures du débit d’acheminement et du RTT.

Dans le contrôle assisté par le réseau, un routeur fournit un retour explicite. ECN marque un paquet en route vers le récepteur, qui rapporte le marquage dans son acquittement. D’anciennes méthodes ATM pouvaient indiquer explicitement un débit autorisé. Un routeur peut aussi envoyer directement à l’émetteur un message appelé paquet de limitation. Le message ICMP Source Quench d’Internet utilisait cette approche et a été déclaré obsolète en 2012.

Interpréter les signaux avec soin

Avec les files à rejet en fin de file, la perte survient normalement une fois le tampon plein. La gestion active des files d’attente peut rejeter ou marquer les paquets plus tôt. Cela change le moment où le signal arrive, mais l’émetteur doit toujours y réagir.

Le RTT minimal observé est utile car il représente approximativement un chemin avec peu d’attente en file. Un RTT supérieur à ce minimum suggère une attente, mais une extrémité doit interpréter les mesures au fil du temps. Ni une seule mesure bruitée ni chaque paquet perdu sur une liaison sans fil ne permettent d’identifier la cause avec certitude.

Contrôler une fenêtre ou un débit

Un émetteur qui utilise un contrôle par fenêtre plafonne les données en vol non acquittées. À mesure que les acquittements reviennent, de la place se libère pour de nouvelles données. Un émetteur qui utilise un contrôle par débit fixe un débit cible et utilise généralement le cadencement des paquets, en les espaçant dans le temps. Les contrôles sont liés :

Par exemple, 100 000 octets par 50 ms correspondent à 2 000 000 d’octets/s, soit 16 Mbps, lorsque la fenêtre est la limite active. Un contrôleur par débit peut aussi utiliser une fenêtre comme borne supérieure des données en attente d’acquittement.

Équilibrer plusieurs objectifs

L’efficacité consiste à maintenir occupée la capacité disponible du goulot d’étranglement. L’équité concerne son partage entre les flux concurrents. Un faible délai exige des files courtes ; la stabilité évite de grandes oscillations répétées ; la réactivité consiste à s’adapter aux changements de capacité ou de concurrence. Une règle qui remplit rapidement un chemin peut malgré tout mal maintenir un faible délai ou mal partager la capacité avec d’autres algorithmes.

Le contrôleur de TCP fonctionne généralement dans le système d’exploitation. Celui de QUIC fonctionne généralement dans une bibliothèque applicative. UDP ne fournit aucun contrôleur ; les applications qui l’utilisent doivent donc assurer elles-mêmes le contrôle de congestion. Le protocole qui transporte les données ne supprime pas l’obligation de réagir à la congestion.

La fenêtre de congestion, cwnd, est une limite fixée par l’émetteur sur les données en vol non acquittées. Elle est mesurée en octets, même si les suivis comptent souvent les segments de taille maximale. Ce n’est pas un champ d’en-tête TCP. Le récepteur annonce une autre limite, la fenêtre de réception rwnd.

Appliquer les deux limites

Les nouvelles transmissions doivent respecter à la fois le contrôle de flux et le contrôle de congestion. La limite utilisable est :

Si cwnd vaut 30 000 octets et rwnd 18 000 octets, la limite du récepteur s’applique. Avec 12 000 octets encore en attente d’acquittement, l’émetteur peut envoyer 6 000 octets supplémentaires. Après une réduction de la fenêtre de congestion, les données déjà envoyées peuvent dépasser la nouvelle limite ; l’émetteur attend des acquittements avant d’en ajouter.

La taille maximale de segment, MSS, compte les données applicatives, sans les en-têtes. Une MTU Ethernet de 1 500 octets moins les en-têtes IPv4 de 20 octets et TCP de 20 octets laisse 1 460 octets, sans options. Les normes utilisent SMSS pour la MSS de l’émetteur.

Convertir une fenêtre en débit

Un émetteur limité par sa fenêtre transmet environ une fenêtre par RTT. Pour une cwnd de 65 536 octets et un RTT de 50 ms :

Multiplie par 8 pour obtenir environ 10,5 Mbps. Cette estimation suppose aussi assez de données applicatives, une fenêtre de réception au moins aussi grande et un chemin capable d’acheminer le débit obtenu.

Remplir le chemin sans remplir sa file

Le produit débit-délai, BDP, est le débit du goulot d’étranglement multiplié par le RTT minimal, sans attente en file. Pour 100 Mbps et 40 ms :

La division par 8 donne 500 000 octets, soit environ 342 segments de 1 460 octets. Un BDP en vol maintient ce goulot d’étranglement idéalisé occupé sans file d’attente persistante. Moins de données laissent de la capacité inutilisée ; les données supplémentaires attendent et augmentent le RTT mesuré. Calculer le BDP à partir d’un RTT déjà augmenté revient à prendre les données en attente pour des données dont le chemin a besoin.

Le cadencement par les acquittements aide à maintenir le rythme. Lorsque les paquets quittent le goulot d’étranglement, les acquittements reviennent et libèrent de la place pour leurs remplaçants. En régime stable, les départs contribuent donc à régler le moment des nouvelles arrivées. C’est l’idée de conservation des paquets qui sous-tend l’autocadencement de TCP.

Fixer le point de départ et le seuil

La fenêtre initiale de la RFC 5681 va de deux à quatre segments selon la SMSS : quatre jusqu’à 1 095 octets, trois jusqu’à 2 190 octets et deux au-delà. La RFC 6928 autorise une fenêtre initiale allant jusqu’à dix segments. Un suivi qui commence à un segment est utile pour enseigner, mais ne signifie pas que toutes les nouvelles connexions commencent à cette valeur.

ssthresh, le seuil de démarrage lent, détermine le mode de croissance. En dessous, TCP utilise le démarrage lent ; au-dessus, l’évitement de congestion. À égalité, la RFC 5681 autorise l’un ou l’autre. Un seuil initial élevé permet à un nouvel émetteur de découvrir la capacité par le démarrage lent.

TCP doit d’abord découvrir quelle quantité de trafic le chemin peut acheminer. Le démarrage lent augmente rapidement la fenêtre à partir d’une petite valeur initiale. L’évitement de congestion sonde ensuite la capacité plus prudemment une fois le seuil de démarrage lent atteint.

Compter les acquittements pendant le démarrage lent

La RFC 5681 augmente cwnd d’au plus une SMSS pour chaque acquittement de nouvelles données :

où N est le nombre d’octets nouvellement acquittés. Avec un acquittement par segment complet et assez de données pour remplir chaque fenêtre, chaque segment envoyé fait place à deux segments au tour suivant : un remplaçant et un autre grâce à l’augmentation de la fenêtre.

En partant de 1 MSS, les valeurs successives sont 1, 2, 4, 8, 16, 32 et 64 MSS. Il faut six RTT pour atteindre 64 MSS. À 100 ms par RTT, cela représente 0,6 s. Le nom évoque un démarrage plus prudent que l’envoi immédiat d’une fenêtre de réception entière ; la croissance elle-même est exponentielle.

Les acquittements différés changent le compte. Si le récepteur envoie un acquittement pour deux segments complets, la règle simple appliquée à chaque acquittement donne une multiplication par environ 1,5 par RTT. Le comptage approprié des octets, décrit dans la RFC 3465, utilise les octets nouvellement acquittés pour remédier à la dépendance à la fréquence des acquittements.

Changer de mode de croissance

Pour un suivi avec une cwnd initiale de 1 MSS et un ssthresh de 8 MSS, choisis l’évitement de congestion à égalité. Le suivi devient :

Les trois premiers changements doublent la fenêtre. Les changements suivants ajoutent une MSS par RTT. Une perte peut interrompre l’une ou l’autre phase. Les implémentations utilisant HyStart++ (RFC 9406) peuvent aussi quitter le démarrage lent plus tôt lorsque le délai augmente.

Expliquer l’augmentation additive

Une règle courante appliquée à chaque acquittement pendant l’évitement de congestion est :

À 10 MSS, un acquittement ajoute environ 0,1 MSS. Environ dix acquittements arrivent pendant le tour ; l’augmentation totale est donc d’environ une MSS. L’ajout par acquittement diminue à mesure que cwnd augmente, ce qui maintient une augmentation à peu près constante d’un tour à l’autre.

Cette différence compte sur un grand chemin. Passer de 16 à 32 MSS prend un RTT en démarrage lent idéal, mais seize RTT en évitement de congestion. La croissance plus lente réduit les dépassements soudains une fois que l’émetteur dispose d’une estimation utile de la capacité.

Reconnaître un redémarrage

Le démarrage lent ne se limite pas au début d’une connexion. L’expiration d’un délai de retransmission ramène cwnd à un segment. Une période d’inactivité supérieure au délai de retransmission impose aussi de redémarrer avec au plus la fenêtre initiale, car le cadencement antérieur par les acquittements et l’estimation de capacité peuvent ne plus convenir au chemin.

L’évitement de congestion ne maintient pas cwnd à une valeur fixe sans danger. Il continue d’augmenter la fenêtre jusqu’à l’arrivée d’un retour sur la congestion. Sur un chemin à rejet en fin de file, ce sondage continu tend à créer une file d’attente persistante avant qu’une perte ne signale à l’émetteur de ralentir.

TCP peut déduire qu’un segment manque à partir d’un temporisateur ou d’acquittements dupliqués. La distinction compte : l’expiration d’un délai prouve moins que trois acquittements dupliqués que le réseau continue d’acheminer du trafic.

Fixer le nouveau seuil

Reno utilise la quantité effectivement en attente d’acquittement, FlightSize, pour fixer :

FlightSize est souvent proche de cwnd pendant un transfert pleinement actif, mais ces valeurs ne sont pas nécessairement égales lorsque l’application envoie peu de données. La borne inférieure empêche le seuil de descendre sous deux segments.

Après l’expiration d’un délai, l’émetteur retransmet, fixe cwnd à une SMSS et recommence le démarrage lent. Des expirations répétées pour les mêmes données doublent le délai du temporisateur de retransmission. Ce recul exponentiel empêche une défaillance persistante de produire un flux tout aussi persistant de nouvelles tentatives.

Récupérer avant l’expiration du temporisateur

Trois acquittements dupliqués montrent que trois segments ultérieurs sont arrivés après un segment manquant. Ils ne signifient pas que trois segments ont été perdus. Un ou deux doublons peuvent provenir d’une arrivée dans le désordre ; TCP attend donc le troisième avant que la retransmission rapide n’envoie le segment manquant.

Reno entre alors en récupération rapide. Supposons que FlightSize vaille 12 MSS. Le nouveau seuil est de 6 MSS, et Reno fixe temporairement :

Les trois segments supplémentaires tiennent compte des paquets dont on sait qu’ils ont quitté le réseau. Chaque acquittement dupliqué supplémentaire gonfle cwnd d’une MSS, ce qui permet de continuer à envoyer lorsque la fenêtre le permet. Lorsqu’un acquittement fait avancer l’acquittement cumulatif, Reno dégonfle cwnd à 6 MSS et reprend l’évitement de congestion.

Avec une fenêtre initiale de 1 MSS et un ssthresh de 8 MSS, cwnd augmente selon 1, 2, 4, 8, 9, 10, 11, 12 MSS avant la perte. Reno continue finalement à 6, 7, 8, 9. Tahoe redémarre à 1, 2, 4, atteint le nouveau seuil de 6, puis continue à 7, 8.

Combler plusieurs manques dans une fenêtre

Reno classique quitte la récupération au premier acquittement de nouvelles données. Si cet acquittement ne couvre qu’une partie des données initialement en vol, un autre manque subsiste. Reno peut réduire à nouveau sa fenêtre ou subir l’expiration du délai.

NewReno (RFC 6582) reste en récupération après un tel acquittement partiel et retransmet le segment manquant suivant. Il quitte la récupération lorsque toutes les données en attente à l’entrée en récupération sont acquittées. SACK indique explicitement les blocs reçus ; la récupération fondée sur SACK peut repérer et combler plusieurs manques en un aller-retour.

Un épisode de congestion ne devrait normalement provoquer qu’une réduction, même si plusieurs paquets sont perdus. NewReno et la récupération fondée sur SACK gèrent cela de manière plus fiable que Reno classique. CUBIC utilise un facteur de réduction différent pour les signaux de congestion ordinaires et conserve 70 %, mais redémarre lui aussi à un segment après l’expiration d’un délai.

Reno classique augmente sa fenêtre de façon répétée et la réduit après une congestion. Les dents de scie qui en résultent fournissent une estimation utile en régime stable lorsque le RTT est à peu près constant, que la retransmission rapide détecte les pertes et qu’il n’y a ni expiration de délai ni démarrage lent.

Calculer la fenêtre moyenne

Soit W la fenêtre maximale en segments. Une division par deux produit une plage allant de W/2 à W, dont la moyenne est 0,75 W. Multiplie par la MSS pour obtenir des octets par aller-retour, puis divise par le RTT :

Pour W de 24 segments, une MSS de 1 460 octets et un RTT de 80 ms, le débit maximal est de 3,504 Mbps. La moyenne est d’environ 2,63 Mbps. Une fenêtre exprimée en segments doit être multipliée par la taille d’un segment ; ce n’est pas nécessaire pour une fenêtre déjà exprimée en octets.

Relier le débit effectif aux pertes

L’approximation de Mathis exprime ce même comportement de type Reno à l’aide de la proportion de pertes L :

Si la MSS est en octets et le RTT en secondes, T est en octets/s. Avec une MSS de 1 460 octets, un RTT de 0,1 s et une proportion de pertes de 0,0001, le dénominateur est de 0,001 s. Le résultat est de 1 781 200 octets/s, soit environ 14,25 Mbps après multiplication par 8.

À proportion de pertes fixe, doubler le RTT divise le débit effectif par deux. À RTT fixe, doubler le débit effectif exige de diviser les pertes par quatre, car le dénominateur contient leur racine carrée. Une proportion de pertes de 0,0001 signifie 0,01 %, pas 0,0001 %.

Comprendre le problème du haut débit

Un chemin à 10 Gbps avec un RTT sans attente en file de 100 ms nécessite 1 milliard de bits, soit 125 000 000 d’octets, en vol pour être pleinement utilisé. Avec des segments de 1 500 octets, cela donne environ 83 333 segments. Après division de cette fenêtre par deux, il reste environ 41 667 segments à regagner. Reno en ajoute un par RTT : les regagner prend donc environ 4 167 s, soit près de 70 minutes.

Cette valeur de 83 333 segments est la fenêtre nécessaire pour émettre à 10 Gbps à un instant donné. Des dents de scie Reno donnant une moyenne de 10 Gbps nécessiteraient un maximum plus élevé, car leur fenêtre moyenne ne vaut que les trois quarts de leur maximum. La formule fondée sur le taux de perte estime que maintenir une moyenne de 10 Gbps avec cette MSS et ce RTT exige environ une perte de segment sur 4,7 milliards.

Vérifier les autres limites

Un contrôleur ne peut pas acheminer les données plus vite que le goulot d’étranglement, et une petite fenêtre de réception peut devenir limitante avant cwnd. Utilise la plus petite limite applicable. Les expirations de délai réduisent le débit sous celui du modèle simple, et le transfert d’un petit objet peut se terminer entièrement pendant le démarrage lent. Son temps d’achèvement dépend fortement des tours de démarrage et de la fenêtre initiale ; la formule pour un transfert de longue durée le décrit donc mal.

Une liaison d’accès plus rapide n’aide donc que si elle supprime une limite active. Un RTT long, des pertes ou une petite fenêtre peuvent maintenir une connexion unique bien en dessous de la capacité de la liaison améliorée.

Si K flux actifs veulent tous plus de capacité qu’un goulot d’étranglement ne peut leur en fournir, une part égale par flux est R/K, où R est le débit disponible. L’efficacité concerne le fait que la somme de leurs débits atteigne R. L’équité concerne l’égalité de leur partage.

Placer deux débits sur un diagramme

Dans un diagramme de Chiu–Jain, les coordonnées horizontale et verticale sont les débits des deux flux. La droite d’efficacité est :

La droite d’équité est la diagonale où les débits sont égaux. Leur intersection correspond à une allocation équitable qui utilise pleinement la liaison. Sur une liaison à 10 Mbps, elle est de 5 Mbps par flux. Les points sous la droite d’efficacité laissent de la capacité inutilisée ; les points au-dessus offrent plus de trafic que la liaison ne peut en acheminer.

Distinguer les deux ajustements

L’augmentation additive ajoute la même quantité à chaque débit. En partant de 8 et 1 Mbps, ajouter 0,5 Mbps à chacun donne 8,5 et 1,5 Mbps. La différence reste de 7 Mbps, mais le plus petit flux gagne davantage par rapport à son débit initial. Sur le diagramme, le point se déplace parallèlement à la diagonale d’égalité.

La diminution multiplicative multiplie les deux débits par le même facteur. Diviser 9 et 2 Mbps par deux donne 4,5 et 1 Mbps. Leur rapport ne change pas, tandis que la différence absolue passe de 7 à 3,5 Mbps. Le point se déplace vers l’origine et supprime rapidement la surcharge.

Ces améliorations ont des sens différents : une addition égale améliore l’équilibre relatif ; une réduction proportionnelle réduit l’écart absolu. Répéter les deux empêche l’écart de s’accroître à nouveau pendant que la capacité est de nouveau sondée.

Suivre plusieurs cycles

Pars de 8 et 1 Mbps sur la liaison à 10 Mbps. Ajoute 0,5 Mbps par flux à chaque étape et ne réduis les débits qu’une fois le total supérieur à la capacité. Après deux augmentations, les débits sont de 9 et 2, soit 11 au total. La division par deux donne 4,5 et 1.

Cinq augmentations supplémentaires donnent 7 et 3,5, soit 10,5 au total. La division par deux donne 3,5 et 1,75. Les écarts successifs sont de 7, 3,5 et 1,75 Mbps. Une nouvelle division par deux synchronisée porte l’écart suivant à 0,875 Mbps. Les flux se rapprochent de parts égales tandis que leur total continue d’osciller autour de la capacité disponible.

Comparer d’autres règles d’ajustement

Cette convergence suppose des RTT égaux, des retours sur la congestion synchronisés, des réactions identiques et des flux qui restent actifs assez longtemps. Le pas additif de Reno est d’environ une MSS par RTT et son facteur de diminution est de moitié. D’autres pas additifs positifs et facteurs de diminution compris entre zéro et un donnent le même raisonnement général de convergence. Les flux réels ne vérifient pas nécessairement toutes ces hypothèses ; deux débits inégaux à un instant donné ne montrent donc pas à eux seuls un échec de l’AIMD.

Les parts égales constituent une référence utile, mais les flux réels peuvent différer par leur demande, leur RTT, leur nombre de connexions et leur contrôleur de congestion. Pour parler d’équité, il faut répondre clairement à « équité entre quels flux ? »

Calculer l’indice de Jain

Pour des débits de flux positifs ou nuls dont le total est non nul, l’indice de Jain est :

Des débits de 8 et 2 Mbps donnent une somme de 10 et une somme des carrés de 68 ; l’indice est donc d’environ 0,735. Des débits égaux donnent 1. Si un des n flux reçoit tout, l’indice est de 1/n.

L’indice mesure l’égalité, pas l’utilisation. Deux flux à 1 Mbps chacun et deux flux à 5 Mbps chacun ont tous deux un indice de 1, même s’ils utilisent des parts différentes d’une liaison à 10 Mbps. Vérifie séparément le débit total.

Tenir compte d’une demande limitée

L’équité max-min donne aux flux à faible demande ce dont ils ont besoin, puis partage la capacité restante entre les flux qui en demandent encore. Sur une liaison à 12 Mbps, trois flux veulent 2, 8 et 10 Mbps. La part égale initiale est de 4 Mbps. Le premier n’a besoin que de 2, ce qui laisse 10 Mbps aux deux autres. L’allocation est donc de 2, 5 et 5 Mbps.

Augmenter l’un des débits les plus élevés exigerait de réduire le débit d’un flux déjà égal ou inférieur. Cette propriété définit l’équité max-min. Son allocation inégale peut être appropriée même si la mesure d’égalité de Jain descend sous 1.

Repérer les avantages entre flux

Reno augmente sa fenêtre une fois par RTT. À proportion de pertes égale, son débit effectif approximatif est inversement proportionnel au RTT : un flux à 20 ms peut atteindre environ quatre fois le débit d’un flux à 80 ms. Un accès au même goulot d’étranglement n’efface pas cet avantage lié au temps.

Le partage s’effectue aussi par connexion. Avec neuf connexions existantes, une application qui en ajoute une pourrait recevoir environ un dixième de la liaison. Si elle ajoute plutôt onze connexions comparables, sa part devient onze vingtièmes, soit 55 %. HTTP/2 et HTTP/3 multiplexent de nombreuses requêtes sur une connexion, tandis que les clients HTTP/1.1 ouvrent souvent plusieurs connexions.

Une application UDP à débit fixe peut continuer d’envoyer pendant que les flux TCP ralentissent. UDP ne fournit aucun contrôleur ; la RFC 8085 demande aux applications d’ajouter un contrôle de congestion adapté. Un flux respectueux de TCP n’utilise pas plus de capacité qu’un trafic TCP comparable dans les mêmes conditions. TFRC utilise l’équation du débit effectif de TCP pour obtenir un débit plus régulier.

Tenir compte de la file et de l’algorithme

Une file premier entré, premier sorti ne garantit pas des parts égales aux flux. Le résultat dépend du comportement des émetteurs. L’ordonnancement équitable, notamment l’ordonnancement par flux de FQ-CoDel, donne aux flux des files séparées et des occasions d’être servis.

Les croissances de CUBIC et de Reno diffèrent sur les chemins à grand BDP. Le partage entre BBR et CUBIC dépend aussi de la version et de la taille du tampon ; les premières versions de BBR pouvaient être agressives avec de petits tampons. Aucun calcul d’égalité isolé ne prouve que différents contrôleurs coexisteront équitablement sur tous les chemins.

Une file à rejet en fin de file accepte les paquets jusqu’à ce que son tampon soit plein, puis rejette les nouvelles arrivées. Les émetteurs fondés sur les pertes continuent d’augmenter leur débit jusqu’à recevoir un signal de congestion. Avec un grand tampon à rejet en fin de file, ce signal ne peut arriver qu’après la formation d’une longue file.

Calculer le délai caché dans un tampon

Un tampon de 2 000 000 d’octets devant une liaison montante à 20 Mbps contient 16 millions de bits. S’il est plein, un paquet placé derrière ces données attend :

Un transfert montant peut donc maintenir un débit effectif élevé tout en ajoutant près d’une seconde au délai d’un appel qui partage la liaison montante. Le bufferbloat désigne un délai excessif et persistant causé par de grands tampons et par le comportement du trafic qui les maintient occupés.

La mise en mémoire tampon conserve néanmoins son utilité : les courtes rafales doivent pouvoir attendre quelque part. Dans le modèle simple à un seul flux Reno, un tampon d’environ un BDP peut maintenir la liaison occupée immédiatement après une division de la fenêtre par deux. Un tampon bien plus grand ajoute de l’attente sans augmenter le débit de transmission de la liaison.

Signaler la congestion avant le débordement

La gestion active des files d’attente, AQM, rejette ou marque les paquets de façon anticipée pour signaler aux émetteurs qu’ils doivent réduire leur charge. Le débordement physique n’est plus le seul moyen d’annoncer la congestion. La RFC 7567 recommande un large déploiement de l’AQM.

La détection précoce aléatoire, RED, surveille une moyenne mobile de la longueur de la file. Sous un seuil minimal, elle n’émet aucun signal. Entre deux seuils, elle rejette ou marque avec une probabilité croissante. Au-dessus du seuil maximal, elle émet un signal à chaque arrivée. La moyenne empêche qu’une seule courte rafale ressemble à une surcharge persistante, mais il est difficile de choisir des seuils adaptés à différents débits et charges.

Mesurer directement le temps d’attente

CoDel mesure le temps de séjour d’un paquet : le temps qu’il passe dans la file. Sa cible standard est de 5 ms et son intervalle de 100 ms. Si même le temps de séjour minimal observé reste au-dessus de la cible pendant un intervalle, une file persistante existe. CoDel rejette alors des paquets ou les marque avec ECN, en augmentant la fréquence des signaux tant que le délai excessif persiste.

Le minimum sur un intervalle est important. Une rafale peut produire brièvement un délai élevé puis se résorber rapidement ; une file dont le délai ne devient jamais faible nécessite une intervention. La mesure du délai permet aux réglages par défaut de CoDel de fonctionner pour une large gamme de débits de liaison.

FQ-CoDel associe des files séparées par flux à CoDel. La séparation des flux aide à éviter que chaque petit paquet interactif attende derrière les données en attente d’un transfert volumineux.

Des signaux précoces peuvent aussi réduire la synchronisation globale, lorsque de nombreux flux perdent des paquets ensemble, divisent leur débit par deux ensemble et laissent temporairement la liaison sous-utilisée. Des signaux précoces aléatoires répartissent les réactions dans le temps. Avec un trafic compatible ECN, une gestion active des files d’attente peut transmettre son avertissement par un marquage tout en acheminant le paquet.

La notification explicite de congestion, ECN, permet à un routeur d’acheminer un paquet tout en avertissant qu’une congestion se développe. Le marquage change le comportement de l’émetteur sans créer de données manquantes à retransmettre.

Lire la valeur du champ IP

Le champ ECN comprend deux bits dans l’octet Type of Service d’IPv4 ou le champ Traffic Class d’IPv6.

Dans la négociation TCP classique de la RFC 3168, le SYN du client active ECE et CWR. Le SYN-ACK d’un serveur qui accepte active ECE. Après négociation, TCP classique marque les paquets de données ECT(0).

Suivre la boucle de rétroaction

Une gestion active des files d’attente qui rejetterait un paquet compatible ECN pour avertir d’une congestion peut remplacer sa valeur par CE et le transférer. Un paquet Not-ECT ne peut pas porter cet avertissement et est rejeté lorsque la gestion active doit émettre un signal. Un tampon entièrement plein rejette toujours les paquets, y compris ceux compatibles ECN.

Le récepteur fait écho à CE en activant ECE, écho ECN, dans ses acquittements. Il continue jusqu’à recevoir de l’émetteur CWR, fenêtre de congestion réduite. Ces drapeaux rapportent le signal et accusent réception de la réponse ; leur présence ne signifie pas que des données ont été perdues.

Pour un ECN classique de type Reno, pars d’une cwnd de 20 MSS. Après l’arrivée d’ECE, l’émetteur réduit cwnd à 10 MSS et place CWR sur son prochain segment de nouvelles données. Le récepteur cesse de faire écho lorsque CWR arrive. Des échos répétés provenant de la même fenêtre n’exigent pas de divisions répétées par deux. L’avertissement revient par le chemin des acquittements ; la réponse est donc soumise au délai de retour.

ECN définit le signal ; l’algorithme de congestion fournit la règle de réduction. Reno divise la fenêtre par deux, tandis que CUBIC en conserve normalement 70 % lors d’un événement ECN. Les deux extrémités et le goulot d’étranglement qui effectue le marquage doivent prendre en charge ECN pour que cette boucle fonctionne.

Utiliser la proportion de marquages

DCTCP, Data Center TCP, utilise des marquages fréquents dans un environnement contrôlé. Il estime la proportion d’octets marqués à l’aide d’une valeur alpha lissée :

où M est la proportion récemment marquée. Certaines implémentations utilisent g égal à 1/16. Il réduit la fenêtre selon :

Avec alpha égal à 0,2, une fenêtre de 100 devient 90 ; avec alpha égal à 1, elle est divisée par deux. DCTCP nécessite un marquage et un retour compatibles. Le mélanger à TCP classique dans une file ordinaire peut produire des parts inéquitables.

L4S, l’architecture expérimentale des RFC 9330 à 9332, apporte une réponse extensible apparentée aux chemins Internet. ECT(1) identifie le trafic extensible et une gestion active couplée à deux files le sépare du trafic classique tout en coordonnant leur traitement. Des marquages fréquents dès que la file est courte visent un délai d’attente en file de l’ordre de la milliseconde. ECT(1) seul ne garantit pas ce délai : le contrôleur et le comportement du goulot d’étranglement complètent le dispositif.

CUBIC répond à la lenteur de croissance de Reno sur les chemins rapides et de longue distance. Sa fenêtre suit le temps écoulé depuis une réduction due à la congestion, ce qui lui donne une réponse différente d’une augmentation fixe d’un segment à chaque RTT. La RFC 9438 définit CUBIC ; il est utilisé par défaut dans les principales piles TCP de Linux, Windows et Apple.

Mémoriser le dernier point de congestion

Lors d’une perte ordinaire ou d’un événement de congestion ECN, CUBIC enregistre sa fenêtre sous le nom Wmax. Lorsque la fenêtre est pleinement utilisée, son facteur de diminution de 0,7 conserve 70 % de la quantité de données en vol. Reno en conserverait la moitié. L’expiration d’un délai de retransmission est différente : CUBIC suit Reno en revenant à une fenêtre d’un segment et au démarrage lent, tout en fixant son seuil avec le facteur de diminution de CUBIC.

Pour la phase cubique de base après une réduction, la fenêtre cible en segments est :

Le temps t est en secondes. Lorsque la fenêtre réduite vaut 0,7 Wmax, le temps de retour à l’ancien maximum est :

Étudier la courbe

Avec Wmax égal à 100 segments, la fenêtre réduite vaut 70. La valeur sous la racine cubique est 75, donc K est d’environ 4,22 s. À une seconde, la courbe vaut environ 86,7 segments ; à deux secondes, 95,6 ; à trois secondes, 99,3. Elle atteint 100 à l’instant K.

Sous l’ancien maximum, la croissance est d’abord rapide puis ralentit. Cette région concave approche prudemment un point où une congestion s’est déjà produite. Près du maximum se trouve un plateau relativement plat. Au-dessus, la région convexe accélère pour sonder la capacité qui pourrait désormais être disponible. À sept secondes, la courbe de l’exemple atteint environ 108,6 segments.

Expliquer l’avantage lié au RTT et sa limite

Reno a besoin de 50 RTT pour remonter de 50 à 100 segments : 5 s avec un RTT de 100 ms et 10 s avec un RTT de 200 ms. Le temps de retour de la courbe cubique dépend du maximum enregistré et du temps écoulé ; son retour en 4,22 s ne dépend donc pas directement du nombre d’acquittements.

CUBIC calcule aussi une estimation compatible avec Reno. Il utilise une augmentation AIMD équivalente d’environ 0,53 segment par RTT avec un facteur de diminution de 0,7, et retient cette estimation lorsqu’elle dépasse la cible cubique. Les chemins à RTT court peuvent donc récupérer plus tôt que ne l’indique le temps de retour purement cubique. La croissance fondée sur le temps réduit une source majeure de biais lié au RTT ; elle ne rend pas chaque allocation réelle indépendante du RTT.

Ajuster le maximum mémorisé

Si la congestion se reproduit sous le maximum précédent, la convergence rapide de CUBIC abaisse le Wmax mémorisé. Un nouvel événement à 90 segments après un maximum précédent de 100 donne :

La fenêtre immédiatement réduite vaut 63 segments. Le maximum mémorisé et la nouvelle fenêtre courante ont des rôles différents : l’un détermine la croissance future, tandis que l’autre limite l’émission actuelle.

CUBIC reste fondé sur les pertes, avec ECN comme signal alternatif. Il peut créer une file persistante sur un chemin à rejet en fin de file. Une récupération plus rapide et une réduction ordinaire plus modérée améliorent l’utilisation des chemins à grand BDP, mais aucune des deux ne garantit à elle seule un faible délai d’attente en file.

La perte n’est pas le seul signe d’un chemin encombré. Le délai peut révéler des données en attente, tandis que les mesures d’acheminement peuvent estimer le débit fourni par le chemin. Vegas et BBR utilisent ces observations de façons différentes.

Estimer les données en attente avec Vegas

Vegas compare un débit attendu fondé sur le RTT minimal, ou RTT de référence, au débit réel fondé sur le RTT mesuré. Leur différence, multipliée par le RTT de référence, estime les données du flux en attente.

Avec une cwnd de 50 segments, un RTT de référence de 40 ms et un RTT mesuré de 50 ms, le débit d’acheminement attendu est de 1 250 segments/s et le débit réel de 1 000 segments/s. L’estimation de la file est :

Vegas augmente sa fenêtre sous un seuil bas et la réduit au-dessus d’un seuil haut. Si un trafic fondé sur les pertes continue de remplir leur file commune, Vegas constate sans cesse le délai et ralentit, ce qui peut lui laisser une petite part.

Construire le modèle de BBR en deux parties

BBR estime le débit du goulot d’étranglement à partir des débits maximaux d’acheminement récents et le RTT minimal sur une période de 10 s. Leur produit estime le BDP. Sa cible idéale est une liaison pleinement utilisée avec environ un BDP en vol et peu de données en attente.

Un débit estimé de 50 Mbps et un RTT minimal de 30 ms donnent 1,5 million de bits, soit 187 500 octets, par BDP. Un gain de fenêtre de congestion habituel de 2 plafonne les données en attente d’acquittement autour de 375 000 octets. Le débit de cadencement est un contrôle distinct : le gain de cadencement multiplié par le débit estimé. Un plafond autorise des données en vol ; il n’oblige pas l’émetteur à émettre au double du débit.

Suivre les états de la version 3 de BBR

Le critère de croissance de Startup est une augmentation du débit d’acheminement inférieure à 25 % pendant trois tours. ProbeRTT est programmé au maximum environ une fois toutes les 5 s. Sur le chemin de l’exemple, ProbeBW vise 62,5 Mbps en Up et 45 Mbps en Down. Ces détails de la version 3 sont définis dans le projet Internet BBR, pas dans une RFC BBR publiée.

Comparer les retours et les compromis

Reno et CUBIC augmentent leur fenêtre jusqu’à ce qu’une perte ou ECN signale une congestion. BBR cadence à partir d’un modèle du débit et du RTT. Il crée volontairement une file brièvement pendant Startup et ProbeBW Up : « fondé sur un modèle » ne signifie donc pas « ne crée jamais de file ».

La version 1 de BBR ignorait largement les pertes. La version 3 utilise les pertes importantes, environ 2 % pendant un tour, pour limiter les dépassements et améliorer la coexistence. Elle peut maintenir un débit effectif supérieur sur de longs chemins présentant des pertes aléatoires, mais ne peut pas déterminer parfaitement pourquoi un paquet a été perdu. Sa réponse précise à ECN reste ouverte dans le projet ; toute connexion déclarant prendre en charge ECN doit réagir à CE comme à une congestion. La taille du tampon, le RTT, la version et les algorithmes concurrents continuent d’influer sur l’équité.

Un protocole s’ossifie lorsque les équipements déployés dépendent si fortement de sa forme actuelle que les modifications deviennent difficiles à déployer. Les équipements intermédiaires inspectent les en-têtes TCP et peuvent rejeter des options ou des drapeaux inconnus. Les implémentations dans le noyau diffusent aussi les nouveaux comportements par les mises à jour des systèmes d’exploitation, souvent lentement.

Identifier les coûts auxquels QUIC répond

TCP a évolué grâce à SACK, ECN, la mise à l’échelle de la fenêtre et de nouveaux contrôleurs de congestion. Pourtant, sa structure reste importante pour le trafic web. Une nouvelle connexion classique TCP avec TLS nécessite la négociation TCP avant la négociation TLS. Son flux d’octets ordonné unique signifie aussi qu’un segment manquant bloque l’acheminement des octets suivants, y compris les données de requêtes sans lien. C’est le blocage en tête de file au niveau du transport.

Les adresses et les ports d’une connexion peuvent créer un autre obstacle lorsqu’un appareil passe d’un réseau à un autre. QUIC, normalisé dans la RFC 9000, modifie ces aspects de la conception du transport tout en acheminant ses paquets sur UDP. HTTP/3 fonctionne sur QUIC.

Combiner les négociations

QUIC intègre TLS 1.3 à sa négociation de transport. Dans un échange simple avec un RTT de 80 ms, un traitement négligeable et aucune perte, une nouvelle connexion TCP avec TLS 1.3 envoie la requête après deux RTT et reçoit les premiers octets de la réponse après trois : 240 ms. Une nouvelle connexion QUIC peut les recevoir après deux RTT : 160 ms.

Une connexion QUIC reprise peut envoyer des données applicatives précoces dès son premier envoi, appelé 0-RTT. La première réponse peut alors arriver après un RTT, soit 80 ms dans cet exemple. Les données précoces peuvent être rejouées ; les applications les réservent donc aux actions qui peuvent être répétées sans danger. Le terme 0-RTT décrit le moment où l’envoi peut commencer, pas une réponse instantanée.

Séparer les flux sans supprimer toutes les limites communes

QUIC transporte des flux d’octets ordonnés indépendants. Si un paquet contient des données pour l’image 1, sa perte ne bloque pas l’acheminement des données déjà reçues pour les images 2 et 3 dans des flux séparés. Un paquet qui transporte plusieurs flux peut affecter chacun de ceux qu’il transporte. Tous les flux partagent toujours le contrôleur de congestion de la connexion ; une perte peut donc réduire leur débit total disponible.

QUIC assure un acheminement fiable des flux au-dessus d’UDP. Il fournit aussi un contrôle de flux par flux et par connexion. UDP est le support, pas un substitut à ces fonctions de transport.

Protéger les détails susceptibles de changer

QUIC chiffre les charges utiles des paquets, y compris toutes les trames de transport. La protection de l’en-tête couvre les numéros de paquet et certains bits du premier octet. Les champs nécessaires au routage et à la négociation, comme les identifiants de connexion et la version, restent visibles. Masquer les détails de transport susceptibles de changer laisse moins de comportements dont les équipements intermédiaires peuvent devenir dépendants.

Les identifiants de connexion désignent une connexion indépendamment des adresses IP et des ports actuels. Après validation du chemin, une connexion peut migrer lorsqu’un téléphone passe du Wi-Fi à un accès cellulaire, sans établir une connexion entièrement nouvelle.

QUIC est généralement une bibliothèque en espace utilisateur. Une mise à jour de l’application peut donc apporter une amélioration du transport sans attendre la modification de chaque noyau de système d’exploitation. Cette souplesse confie aussi à l’application la responsabilité d’assurer correctement la détection des pertes, la sécurité, le contrôle de flux et le contrôle de congestion.

QUIC améliore ce qu’un émetteur peut apprendre des acquittements, mais doit toujours éviter de surcharger le chemin. La RFC 9002 définit la détection des pertes et un contrôleur par défaut proche de NewReno. Les implémentations peuvent utiliser d’autres algorithmes adaptés, notamment CUBIC ou BBR.

Identifier chaque transmission

Les numéros de paquet augmentent et ne se répètent jamais dans un même espace de numérotation. Les données renvoyées circulent dans des trames à l’intérieur d’un nouveau paquet portant un nouveau numéro. Un acquittement peut donc identifier la transmission arrivée, ce qui évite l’ambiguïté de TCP entre un segment initial et sa retransmission.

Les trames ACK indiquent les plages reçues et le délai d’acquittement du récepteur. Après la négociation, l’émetteur utilise un délai d’acquittement validé et borné pour ajuster ses estimations du RTT ; il ne soustrait pas aveuglément un délai arbitraire du récepteur de chaque mesure.

QUIC déclare un paquet perdu lorsqu’un paquet portant un numéro supérieur d’au moins trois a été acquitté, ou au moyen de son seuil temporel une fois qu’un paquet ultérieur est acquitté. Le seuil temporel recommandé est de 9/8 de la plus grande des deux valeurs entre le dernier RTT mesuré et le RTT lissé. Un délai de sondage, PTO, déclenche l’envoi de sondes destinées à susciter des acquittements. L’expiration du PTO ne réduit pas à elle seule cwnd au minimum.

Fixer les limites de fenêtre en octets

Pour une taille maximale de datagramme d, la fenêtre initiale de la RFC 9002 est :

Avec d égal à 1 200 octets, le résultat est de 12 000 octets. Avec d égal à 1 500 octets, il est de 14 720 octets. La fenêtre de congestion minimale est de deux datagrammes de taille maximale ; ces chemins ont donc des minima respectifs de 2 400 et 3 000 octets.

Dans le contrôleur par défaut, une perte ou un nouveau signal de congestion CE divise cwnd par deux, sans descendre sous le minimum, et fixe ssthresh à la fenêtre réduite. Une période de récupération empêche une nouvelle réduction pour les pertes supplémentaires de paquets envoyés avant le début de la récupération. L’acquittement d’un paquet envoyé pendant la récupération met fin à cette période. L’émetteur reprend alors sa croissance normale.

Reconnaître une défaillance durable

Une congestion persistante constitue une preuve plus forte qu’une seule expiration de temporisateur. Elle exige une série suffisamment longue de pertes de paquets suscitant un acquittement, sans acquittement d’un paquet intermédiaire et avec une mesure préalable du RTT. Son seuil de durée est :

Avec un RTT lissé de 100 ms, une variation de 10 ms, un délai maximal d’acquittement de 25 ms et une granularité du temporisateur négligeable, le seuil est de 495 ms. L’intervalle de pertes répondant aux critères doit dépasser cette valeur. Le contrôleur ramène alors cwnd à deux datagrammes, sa fenêtre minimale.

Préserver l’utilité des retours et du rythme d’envoi

Les acquittements QUIC peuvent indiquer les nombres cumulés d’ECT(0), d’ECT(1) et de CE. Après validation du fonctionnement d’ECN sur le chemin, l’émetteur traite une nouvelle augmentation de CE comme un événement de congestion sans nécessiter de perte de paquet.

Le cadencement espace les transmissions. Une approche suggérée utilise un débit d’environ 1,25 fois cwnd divisée par le RTT lissé ; des limites de rafale peuvent servir le même objectif. Envoyer une fenêtre entière en une fois crée une rafale même lorsque le débit moyen est acceptable. Le déploiement en espace utilisateur facilite la diffusion de nouveaux contrôleurs, mais chaque pile doit toujours partager la capacité de manière responsable.