Les algorithmes conçus pour garantir que plusieurs utilisateurs partagent équitablement un réseau ne peuvent pas empêcher certains utilisateurs de monopoliser toute la bande passante. —

Les ordinateurs et les appareils qui transmettent des données sur Internet divisent les données en paquets plus petits et utilisent un algorithme spécial pour décider à quelle vitesse envoyer ces paquets. Ces algorithmes de contrôle de congestion cherchent à découvrir et à utiliser pleinement la capacité de réseau disponible tout en la partageant équitablement avec d’autres utilisateurs qui peuvent partager le même réseau. Ces algorithmes tentent de minimiser le retard causé par les données en attente dans les files d’attente du réseau.

Au cours de la dernière décennie, les chercheurs de l’industrie et du milieu universitaire ont développé plusieurs algorithmes qui tentent d’atteindre des taux élevés tout en contrôlant les retards. Certains d’entre eux, comme l’algorithme BBR développé par Google, sont maintenant largement utilisés par de nombreux sites Web et applications.

Mais une équipe de chercheurs du MIT a découvert que ces algorithmes peuvent être profondément injustes. Dans une nouvelle étude, ils montrent qu’il y aura toujours un scénario de réseau où au moins un expéditeur ne reçoit presque pas de bande passante par rapport aux autres expéditeurs ; c’est-à-dire qu’un problème connu sous le nom de famine ne peut être évité.

“Ce qui est vraiment surprenant à propos de cet article et des résultats, c’est que lorsque vous tenez compte de la complexité réelle des chemins de réseau et de tout ce qu’ils peuvent faire pour les paquets de données, il est fondamentalement impossible pour les algorithmes de contrôle de la congestion de contrôler les délais d’éviter la famine en utilisant les méthodes actuelles », explique Mohammad Alizadeh, professeur agrégé de génie électrique et d’informatique (EECS).

Alors qu’Alizadeh et ses co-auteurs n’ont pas été en mesure de trouver un algorithme traditionnel de contrôle de la congestion qui pourrait éviter la famine, il peut y avoir des algorithmes dans une classe différente qui pourraient prévenir ce problème. Leur analyse suggère également que la modification du fonctionnement de ces algorithmes, afin qu’ils permettent de plus grandes variations de délai, pourrait aider à prévenir la famine dans certaines situations de réseau.

Alizadeh a écrit l’article avec le premier auteur et étudiant diplômé de l’EECS Venkat Arun et l’auteur principal Hari Balakrishnan, professeur Fujitsu d’informatique et d’intelligence artificielle. La recherche sera présentée à la conférence ACM Special Interest Group on Data Communications (SIGCOMM).

Contrôler la congestion

Le contrôle de la congestion est un problème fondamental dans les réseaux que les chercheurs tentent de résoudre depuis les années 1980.

L’ordinateur d’un utilisateur ne sait pas à quelle vitesse envoyer des paquets de données sur le réseau car il manque d’informations, telles que la qualité de la connexion réseau ou le nombre d’autres expéditeurs utilisant le réseau. L’envoi de paquets trop lent fait un mauvais usage de la bande passante disponible. Mais les envoyer trop rapidement peut submerger le réseau et, ce faisant, les paquets commenceront à être abandonnés. Ces paquets doivent être renvoyés, ce qui entraîne des délais plus longs. Les retards peuvent également être causés par des paquets qui attendent dans les files d’attente pendant une longue période.

Les algorithmes de contrôle de la congestion utilisent les pertes de paquets et les retards comme signaux pour déduire la congestion et décider de la vitesse d’envoi des données. Mais Internet est compliqué et les paquets peuvent être retardés et perdus pour des raisons sans rapport avec la congestion du réseau. Par exemple, les données peuvent être bloquées dans une file d’attente en cours de route, puis libérées avec une rafale d’autres paquets, ou l’accusé de réception du destinataire peut être retardé. Les auteurs appellent les retards qui ne sont pas causés par la congestion « gigue ».

Même si un algorithme de contrôle de congestion mesure parfaitement le retard, il ne peut pas faire la différence entre le retard causé par la congestion et le retard causé par la gigue. Le retard causé par la gigue est imprévisible et confond l’expéditeur. En raison de cette ambiguïté, les utilisateurs commencent à estimer le délai différemment, ce qui les amène à envoyer des paquets à des débits inégaux. Finalement, cela conduit à une situation où la famine se produit et quelqu’un est complètement exclu, explique Arun.

“Nous avons lancé le projet parce que nous manquions de compréhension théorique du comportement du contrôle de la congestion en présence de gigue. Pour le placer sur une base théorique plus solide, nous avons construit un modèle mathématique suffisamment simple à penser, mais capable de capturer certaines des complexités d’Internet. Cela a été très gratifiant de voir les mathématiques nous dire des choses que nous ne savions pas et qui ont une pertinence pratique », dit-il.

Étudier la famine

Les chercheurs ont transmis leur modèle mathématique à un ordinateur, lui ont donné une série d’algorithmes de contrôle de la congestion couramment utilisés et ont demandé à l’ordinateur de trouver un algorithme qui pourrait éviter la famine, en utilisant leur modèle.

“Nous n’avons pas pu le faire. Nous avons essayé tous les algorithmes que nous connaissions, et quelques nouveaux que nous avons inventés. Rien n’a fonctionné. L’ordinateur a toujours trouvé une situation où certaines personnes obtiennent toute la bande passante et au moins une personne n’obtient pratiquement rien “, dit Arun.

Les chercheurs ont été surpris par ce résultat, d’autant plus que ces algorithmes sont largement considérés comme raisonnablement justes. Ils ont commencé à soupçonner qu’il n’était peut-être pas possible d’éviter la famine, une forme extrême d’injustice. Cela les a motivés à définir une classe d’algorithmes qu’ils appellent “algorithmes à convergence retardée” dont ils ont prouvé qu’ils souffriraient toujours de la famine sous leur modèle de réseau. Tous les algorithmes de contrôle de congestion existants qui contrôlent le délai (dont les chercheurs sont conscients) sont à convergence de délai.

Le fait que des modes de défaillance aussi simples de ces algorithmes largement utilisés soient restés inconnus pendant si longtemps illustre à quel point il est difficile de comprendre les algorithmes uniquement par des tests empiriques, ajoute Arun. Il souligne l’importance d’une base théorique solide.

Mais tout espoir n’est pas perdu. Bien que tous les algorithmes qu’ils ont testés aient échoué, il peut y avoir d’autres algorithmes qui ne sont pas à convergence de retard qui pourraient être en mesure d’éviter la famine. Cela suggère qu’une façon de résoudre le problème pourrait être de concevoir des algorithmes de contrôle de congestion qui varient plus largement la plage de retard, la plage est donc plus grande que tout retard pouvant survenir en raison de la gigue dans le réseau.

“Pour contrôler les retards, les algorithmes ont également essayé de limiter les variations de retard autour d’un équilibre souhaité, mais il n’y a rien de mal à créer potentiellement une plus grande variation de retard pour obtenir de meilleures mesures des retards congestifs. C’est juste une nouvelle philosophie de conception que vous auriez à adopter », ajoute Balakrishnan.

Maintenant, les chercheurs veulent continuer à pousser pour voir s’ils peuvent trouver ou construire un algorithme qui éliminera la famine. Ils souhaitent également appliquer cette approche de modélisation mathématique et de preuves informatiques à d’autres problèmes épineux non résolus dans les systèmes en réseau.

“Nous dépendons de plus en plus des systèmes informatiques pour des choses très critiques, et nous devons établir leur fiabilité sur une base conceptuelle plus solide. Nous avons montré les choses surprenantes que vous pouvez découvrir lorsque vous prenez le temps d’élaborer ces spécifications formelles de quel est réellement le problème », dit Alizadeh.