Des chercheurs découvrent un obstacle majeur à la réduction de la congestion du réseau

Des chercheurs découvrent un obstacle majeur à la réduction de la congestion du réseau

Lorsque les utilisateurs souhaitent envoyer 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 perturbent le trajet du matin vers une grande ville.

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 délai 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é divers 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 désormais 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 étonnant à propos de cet article et des résultats, c’est que lorsque vous tenez compte de la complexité réelle des chemins réseau et de tout ce qu’ils peuvent faire avec les paquets de données, il est fondamentalement impossible pour les algorithmes de contrôle de la congestion qui contrôlent le décalage d’éviter la famine en utilisant les méthodes actuelles, », explique Mohammad Alizadeh, professeur agrégé de génie électrique et 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 empêcher la famine, il peut y avoir des algorithmes dans une classe différente qui pourraient empêcher ce problème. Leur analyse suggère également que la modification du mode de 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ôle de la congestion

Le contrôle de la congestion est un problème fondamental dans les réseaux que les chercheurs tentent d’aborder 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 surcharger le réseau et, ce faisant, les paquets commenceront à se perdre. 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 la perte de paquets et le retard 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 conservé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 récepteur peut être retardé. Les auteurs appellent les retards qui ne sont pas dus à la congestion des “jitters”.

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 vitesses inégales. Finalement, cela conduit à une situation où la famine s’installe et quelqu’un est complètement laissé de côté, 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 fluctuations. Pour le mettre sur une base théorique plus solide, nous avons construit un modèle mathématique assez simple à penser, mais capable de capturer certaines des complexités d’Internet. C’est très gratifiant que les mathématiques nous disent des choses que nous ne savions pas et qui ont une pertinence pratique », dit-il.

étudier la faim

Les chercheurs ont introduit leur modèle mathématique dans 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 empêcher la famine, en utilisant leur modèle.

« Nous ne pouvions pas le faire. Nous avons testé tous les algorithmes que nous connaissions et quelques nouveaux que nous avons créé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 », explique Arun.

Les chercheurs ont été surpris par ce résultat, d’autant plus que ces algorithmes sont jugés raisonnablement équitables. Ils ont commencé à soupçonner qu’il n’était peut-être pas possible d’empêcher la famine, une forme extrême d’injustice. Cela les a motivés à définir une classe d’algorithmes qu’ils appellent “algorithmes convergents à retard”, ce qui a montré qu’ils mourraient toujours de faim sous leur modèle de réseau. Tous les algorithmes de contrôle de congestion existants qui contrôlent le délai (que les chercheurs connaissent) sont convergents vers le délai.

Le fait que les modes de défaillance très 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 convergent pas avec le retard et pourraient empêcher la famine. Cela suggère qu’une façon de contourner 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 supérieure à 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 aucun mal à créer potentiellement plus de variation de retard pour obtenir de meilleures mesures des retards congestifs. C’est juste une nouvelle philosophie de conception qu’il faudrait 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 test informatique à d’autres problèmes épineux et non résolus dans les systèmes en réseau.

« Nous nous appuyons de plus en plus sur des systèmes informatiques pour des choses très critiques, et nous devons asseoir leur fiabilité sur une base conceptuelle plus solide. Nous avons montré les choses incroyables que vous pouvez découvrir lorsque vous passez du temps à élaborer ces spécifications formelles de ce qu’est réellement le problème », déclare Alizadeh.

#Des #chercheurs #découvrent #obstacle #majeur #réduction #congestion #réseau

Leave a Comment

Your email address will not be published.