Comment le contrôle de congestion de TCP a sauvé Internet

Approche systémique Avec la conférence annuelle SIGCOMM qui a lieu ce mois-ci, nous avons observé que le contrôle de la congestion occupe encore une heure dans le programme, 35 ans après la publication du premier article sur le contrôle de la congestion TCP. Le moment semble donc bien choisi pour comprendre à quel point le succès d’Internet dépend de son approche de la gestion de la congestion.

Suite à mon récent discours et article sur 60 ans de réseautage, presque entièrement axé sur Internet et ARPANET, j’ai reçu de nombreux commentaires sur diverses technologies de réseautage qui rivalisaient en même temps pour l’ascendant.

Ceux-ci incluaient la pile OSI (quelqu’un se souvient de CLNP et TP4 ?), les protocoles Colored Book (y compris le Cambridge Ring) et bien sûr ATM (Asynchronous Transfer Mode) qui était en fait le premier protocole réseau sur lequel j’ai travaillé en profondeur. C’est difficile à comprendre aujourd’hui, mais dans les années 1980, j’étais l’une des nombreuses personnes qui pensaient que l’ATM pourrait être la technologie de commutation de paquets qui conquérirait le monde.

Je considère le contrôle de la congestion comme l’un des facteurs clés qui ont permis à Internet de passer d’une échelle modérée à une échelle mondiale.

Les partisans de l’ATM faisaient autrefois référence aux technologies existantes telles qu’Ethernet et TCP/IP comme étant des protocoles existants qui pourraient, si nécessaire, être acheminés sur le réseau ATM mondial une fois celui-ci établi. L’un de mes bons souvenirs de cette époque est celui de Steve Deering (un pionnier des réseaux IP) déclarant avec audace (et à juste titre) que l’ATM ne connaîtrait jamais suffisamment de succès pour ne serait-ce qu’être un protocole existant.

L’une des raisons pour lesquelles j’ai ignoré ces autres protocoles lorsque j’ai raconté plus tôt l’histoire des réseaux était simplement pour économiser de l’espace. C’est un fait peu connu que mon collègue de l’approche systémique Larry Peterson et moi visons la concision, d’autant plus que nous avons reçu une critique d’une étoile sur Amazon qui a appelé notre livre un mur de texte. Mais je me suis également concentré sur la façon dont nous sommes arrivés à l’Internet d’aujourd’hui, où TCP/IP a effectivement surpassé les autres suites de protocoles pour parvenir à une pénétration mondiale (ou quasi-mondiale).

Il existe de nombreuses théories expliquant pourquoi TCP/IP a connu plus de succès que ses contemporains, et elles ne sont pas facilement testables. Très probablement, de nombreux facteurs ont joué dans le succès des protocoles Internet. Mais je considère le contrôle de la congestion comme l’un des facteurs clés qui ont permis à Internet de passer d’une échelle modérée à une échelle mondiale.

Il s’agit également d’une étude intéressante sur la manière dont les choix architecturaux particuliers faits dans les années 1970 se sont révélés efficaces au cours des décennies suivantes.

Gestion des ressources distribuées

Dans l’article de David Clark [PDF] La philosophie de conception des protocoles Internet DARPA », un objectif de conception déclaré est le suivant : l’architecture Internet doit permettre une gestion distribuée de ses ressources. Cet objectif a de nombreuses implications différentes, mais la manière dont Jacobson et Karels [PDF] Le premier contrôle de congestion implémenté dans TCP est un bon exemple de prise en compte de ce principe.

Leur approche englobe également un autre objectif de conception d’Internet : s’adapter à de nombreux types de réseaux différents. Pris ensemble, ces principes excluent quasiment la possibilité de toute sorte de contrôle d’admission basé sur le réseau, ce qui contraste fortement avec les réseaux tels que ATM, qui supposaient qu’une demande de ressources serait faite d’un système final au réseau avant que les données ne soient transmises. pourrait couler.

Une partie de la philosophie d’adaptation à de nombreux types de réseaux est que vous ne pouvez pas supposer que tous les réseaux disposent d’un contrôle d’admission. Ajoutez à cela une gestion distribuée des ressources et vous vous retrouvez avec le contrôle de la congestion comme quelque chose que les systèmes finaux doivent gérer, ce qui est exactement ce que Jacobson et Karels ont fait avec leurs modifications initiales de TCP.

Nous essayons d’amener des millions de systèmes finaux à partager de manière coopérative et équitable la bande passante des liens goulots d’étranglement.

L’histoire du contrôle de la congestion TCP est suffisamment longue pour remplir un livre (et nous l’avons fait), mais les travaux effectués à Berkeley, en Californie, de 1986 à 1998, jettent une ombre longue, l’article SIGCOMM de Jacobson de 1988 se classant parmi les articles sur les réseaux les plus cités de tous. temps.

Le démarrage lent, l’AIMD (augmentation additive, diminution multiplicative), l’estimation RTT et l’utilisation de la perte de paquets comme signal de congestion figuraient tous dans cet article, jetant les bases des décennies suivantes de recherche sur le contrôle de la congestion. L’une des raisons de l’influence de ce document, je crois, est que les bases qu’il a posées étaient solides, tout en laissant beaucoup de place à des améliorations futures, comme le montrent les efforts continus visant à améliorer le contrôle des embouteillages aujourd’hui.

Et le problème est fondamentalement difficile : nous essayons d’amener des millions de systèmes finaux qui n’ont pas de contact direct les uns avec les autres à partager de manière coopérative la bande passante des liens à goulot d’étranglement d’une manière modérément équitable en utilisant uniquement les informations qui peuvent être glanées en envoyant des paquets dans le réseau. réseau et observer quand et s’ils atteignent leur destination.

L’un des plus grands progrès après 1988 a sans doute été la prise de conscience par Brakmo et Peterson (oui, ce type) que la perte de paquets n’était pas le seul signal de congestion : il en était de même pour l’augmentation des délais. C’était la base de l’article TCP Vegas de 1994, et l’idée d’utiliser le délai plutôt que la seule perte était assez controversée à l’époque.

Cependant, Vegas a lancé une nouvelle tendance dans la recherche sur le contrôle de la congestion, inspirant de nombreux autres efforts visant à prendre en compte les délais comme indicateur précoce de la congestion avant que les pertes ne surviennent. Le centre de données TCP (DCTCP) et le BBR de Google en sont deux exemples.

L’une des raisons pour lesquelles j’accorde du crédit aux algorithmes de contrôle de la congestion pour expliquer le succès d’Internet est que le chemin vers l’échec d’Internet était clairement visible en 1986. Jacobson décrit certains des premiers épisodes d’effondrement de la congestion, qui ont vu le débit chuter de trois ordres. d’ampleur.

Lorsque j’ai rejoint Cisco en 1995, nous entendions encore des témoignages de clients concernant des épisodes de congestion catastrophiques. La même année, Bob Metcalfe, inventeur d’Ethernet et récent lauréat du prix Turing, a prédit qu’Internet s’effondrerait à mesure que l’accès des consommateurs à Internet et l’essor du Web entraîneraient une croissance rapide du trafic. Ce n’est pas le cas.

Le contrôle de la congestion a continué d’évoluer, le protocole QUIC, par exemple, offrant à la fois de meilleurs mécanismes de détection de la congestion et la possibilité d’expérimenter plusieurs algorithmes de contrôle de la congestion. Et certains contrôles de congestion ont été déplacés vers la couche application, par exemple : Dynamic Adaptive Streaming over HTTP (DASH).

Un effet secondaire intéressant des épisodes de congestion des années 1980 et 1990 a été que nous avons observé que de petites zones tampons étaient parfois à l’origine d’un effondrement de la congestion. Un article influent de Villamizar et Song a montré que les performances de TCP diminuaient lorsque la quantité de mise en mémoire tampon était inférieure au produit moyen de bande passante de retard des flux.

Malheureusement, le résultat n’était valable que pour un très petit nombre de flux (comme cela était reconnu dans l’article), mais il a été largement interprété comme une règle inviolable qui a influencé les années suivantes de conception de routeurs.

Ceci a finalement été démystifié par le travail de dimensionnement des tampons d’Appenzeller. et autres en 2004, mais pas avant que le phénomène malheureux de Bufferbloat, des tailles de tampon vraiment excessives conduisant à des retards massifs dans les files d’attente, ne se soient répandus dans des millions de routeurs bas de gamme. L’autotest de Bufferbloat dans votre réseau domestique vaut le détour.

Ainsi, même si nous n’avons pas la possibilité de revenir en arrière et de mener des expériences contrôlées pour voir exactement comment Internet a réussi alors que d’autres suites de protocoles ont été laissées de côté, nous pouvons au moins voir qu’Internet a évité une défaillance potentielle grâce à la manière opportune dont le contrôle de la congestion a été mis en place. ajoutée.

En 1986, il était relativement facile d’expérimenter de nouvelles idées en peaufinant le code de quelques systèmes finaux, puis d’étendre la solution efficace à un large éventail de systèmes. Rien à l’intérieur du réseau ne devait changer. Le fait que l’ensemble des systèmes d’exploitation qui devaient être modifiés et la communauté de personnes capables d’effectuer ces changements soient suffisamment petits pour permettre un déploiement généralisé des algorithmes initiaux basés sur BSD de Jacobson et Karels a certainement aidé.

Il semble clair qu’il n’existe pas d’approche parfaite en matière de contrôle de la congestion, c’est pourquoi nous continuons de voir de nouveaux articles sur le sujet 35 ans après Jacobsons. Mais l’architecture d’Internet a favorisé un environnement dans lequel des solutions efficaces peuvent être testées et déployées pour parvenir à une gestion distribuée des ressources partagées.

À mon avis, c’est un grand témoignage de la qualité de cette architecture.