Des scientifiques découvrent un goulot d’étranglement majeur dans la réduction de la congestion du réseau

Lorsque les utilisateurs souhaitent transférer des données sur Internet plus rapidement que le réseau ne peut le faire, des embouteillages peuvent survenir – de la même manière que les embouteillages se rendent dans une grande ville le matin.

Les ordinateurs et les appareils qui envoient des données sur Internet les divisent en paquets plus petits et utilisent un algorithme spécial pour déterminer la vitesse à laquelle ces paquets peuvent voyager. Ces algorithmes de contrôle de congestion tentent de découvrir et d’utiliser pleinement la bande passante réseau disponible tout en la partageant équitablement avec d’autres utilisateurs qui peuvent partager le même réseau. Ces algorithmes tentent de réduire la latence causée par la mise en file d’attente des données sur le réseau.

Au cours de la dernière décennie, des scientifiques de l’industrie et du milieu universitaire ont développé de nombreux algorithmes qui tentent d’atteindre des taux élevés tout en contrôlant la latence. Certains de ces algorithmes, tels que l’algorithme BBR développé par Google, sont aujourd’hui largement utilisés dans de nombreux sites Web et applications.

Cependant, une équipe de chercheurs du MIT a découvert que ces algorithmes peuvent être très injustes. Dans la nouvelle étude, ils montrent qu’il y aura toujours un scénario de réseau où au moins un émetteur ne reçoit presque aucune bande passante par rapport aux autres émetteurs ; Cela signifie qu’il existe un problème inévitable appelé la faim.

« Ce qui est vraiment surprenant à propos de cet article et des résultats, c’est qu’étant donné la complexité réelle des chemins de réseau et tout ce qui peut être fait avec les paquets de données, il est fondamentalement impossible d’éviter les algorithmes de contrôle de la congestion pour contrôler la latence », déclare Mohammad Alizadeh , Professeur agrégé de génie électrique et informatique (EECS) : « Famine par les méthodes actuelles ».

Bien qu’Alizadeh et ses collègues n’aient pas été en mesure de trouver un algorithme de contrôle de congestion traditionnel qui puisse éviter la famine, il peut y avoir des algorithmes d’une autre classe qui peuvent prévenir ce problème. Leur analyse suggère également que la modification du fonctionnement de ces algorithmes, permettant des changements de latence plus importants, peut aider à prévenir la famine dans certaines situations de réseau.

Alizadeh a écrit l’article avec le premier auteur et diplômé de l’EECS Venkat Arun et l’auteur principal Harry Balakrishnan, professeur Fujitsu d’informatique et d’intelligence artificielle. Les résultats de la recherche seront présentés lors de la conférence du Groupe d’intérêt spécial sur les communications de données (SIGCOMM) de l’ACM.

contrôle de la congestion

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

L’ordinateur de l’utilisateur ne sait pas à quelle vitesse les paquets de données voyagent sur le réseau car il lui manque des 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 conduit à une utilisation inappropriée de la bande passante disponible. Mais un envoi trop rapide peut submerger le réseau et commencer à perdre des paquets. Ces paquets doivent être renvoyés, ce qui entraîne des délais plus longs. Des retards peuvent également survenir en raison de colis qui attendent longtemps dans la file d’attente.

Les algorithmes de contrôle de la congestion utilisent la perte de paquets et le retard comme signaux pour déduire la congestion et déterminer le débit de données. Cependant, Internet est complexe 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 mises en file d’attente en cours de route puis libérées avec un groupe d’autres paquets, ou l’accusé de réception du destinataire peut être retardé. Les auteurs appellent « jitter » les retards qui ne sont pas causés par la congestion.

Bien que l’algorithme de contrôle de congestion mesure entièrement le délai, il ne peut pas faire la distinction entre le délai de congestion et le délai de gigue. Le délai de gigue est imprévisible et source de confusion pour 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 vitesses inégales. Finalement, explique Aaron, cela conduit à une situation où la faim s’installe et la personne est complètement fermée.

« Nous avons lancé le projet parce que nous manquions d’une compréhension théorique du comportement de contrôle des foules en présence de tension. Pour le mettre sur une base théorique plus solide, nous avons construit un modèle mathématique assez simple à penser, mais qui pourrait capturer certaines des subtilités d’Internet. Ce fut un grand plaisir pour vous de nous parler de mathématiques à propos de choses dont nous ne savions pas qu’elles avaient une importance pratique – dit-il.

Étudier la faim

Les chercheurs ont transféré leur modèle mathématique sur un ordinateur, l’ont alimenté avec une série d’algorithmes courants de contrôle de la congestion et ont demandé à l’ordinateur de trouver un algorithme qui pourrait éviter la famine en utilisant leur modèle.

« Nous ne pouvions pas le faire. Nous avons essayé tous les algorithmes que nous connaissions et quelques nouveaux algorithmes que nous avons trouvés. Rien n’a fonctionné. L’ordinateur a toujours trouvé une situation où certaines personnes obtiennent une bande passante complète, ou au moins une personne n’obtient rien », explique Aaron.

Les scientifiques ont été surpris par cette découverte, d’autant plus que ces algorithmes sont considérés comme assez justes. Ils ont commencé à soupçonner que la faim, forme extrême d’injustice, ne pouvait être évitée. Cela les a incités à définir une classe d’algorithmes qu’ils ont appelés « algorithmes de retard convergents » dont ils ont prouvé qu’ils seraient toujours affamés dans leur modèle de réseau. Tous les algorithmes actuels de contrôle de la congestion qui contrôlent la latence (dont les chercheurs sont conscients) sont convergents.

Aaron ajoute que le fait que les modes de défaillance simples de ces algorithmes largement utilisés soient restés inconnus pendant si longtemps montre à quel point il est difficile de comprendre les algorithmes à partir de tests purement empiriques. Il souligne l’importance d’une base théorique solide.

Mais l’espoir est toujours perdu. Bien que tous les algorithmes que nous avons testés aient échoué, il peut y avoir d’autres algorithmes non convergents qui pourraient é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 modifient plus largement la plage de retard. la couverture est supérieure à tout retard pouvant survenir en raison de l’instabilité du réseau.

« Pour contrôler les retards, les algorithmes ont également essayé de combler les différences de retard autour d’un équilibre souhaité, mais il n’y a rien de mal à créer un contraste de retard plus élevé pour obtenir de meilleures mesures du retard stagnant. C’est juste une nouvelle philosophie de conception que vous devez adopter », ajoute Balakrishnan.

Maintenant, les scientifiques veulent continuer à essayer de voir s’ils peuvent trouver ou construire un algorithme qui éliminera la faim. 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 de réseau.

« Nous comptons de plus en plus sur les systèmes informatiques pour les problèmes critiques et devons construire leur fiabilité sur une base conceptuelle plus solide. » Nous avons montré des choses incroyables que vous pouvez découvrir lorsque vous prenez le temps de développer cette spécification formelle de ce qu’est réellement le problème », déclare Alizadeh.

Posted in web

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.