Los investigadores descubren un cuello de botella importante en la mitigación de la congestión de la red | noticias del MIT

Cuando los usuarios quieren enviar datos a través de Internet más rápido de lo que la red puede manejar, puede ocurrir una congestión, de la misma manera que los atascos de tráfico interrumpen su viaje matutino a una gran ciudad.

Las computadoras y los dispositivos que transmiten datos a través de Internet dividen los datos en paquetes más pequeños y usan un algoritmo especial para determinar qué tan rápido se pueden transmitir esos paquetes. Estos algoritmos de control de congestión buscan descubrir y aprovechar al máximo la capacidad de red disponible mientras la comparten equitativamente con otros usuarios que pueden compartir la misma red. Estos algoritmos intentan reducir el retraso causado por la espera de datos en las colas de la red.

Durante la última década, los investigadores de la industria y la academia han desarrollado muchos algoritmos que intentan alcanzar altas tasas mientras controlan los retrasos. Parte de este algoritmo, como el algoritmo BBR desarrollado por Google, ahora se usa ampliamente en muchos sitios web y aplicaciones.

Pero un equipo de investigadores del MIT descubrió que estos algoritmos pueden ser muy injustos. En un nuevo estudio, muestran que siempre habrá un escenario de red en el que al menos un transmisor casi no recibe ancho de banda en comparación con otros transmisores; Esto significa que no se puede evitar un problema conocido como inanición.

“Lo que es realmente sorprendente de este documento y los resultados es que cuando se tiene en cuenta la complejidad realista de las rutas de red y todas las cosas que se pueden hacer con los paquetes de datos, es esencialmente imposible evitar los algoritmos de control de congestión para controlar la demora. ”, dice Mohammad Alizadeh, profesor asociado de ingeniería eléctrica y Ciencias de la Computación (EECS): “Hambre utilizando métodos actuales”.

Si bien Alizadeh y sus colegas no han podido encontrar un algoritmo de control de congestión tradicional que pueda evitar la inanición, puede haber algoritmos en una clase diferente que puedan prevenir este problema. Su análisis también sugiere que cambiar la forma en que funcionan estos algoritmos, lo que permite cambios más grandes en la demora, podría ayudar a prevenir la inanición en algunas situaciones de red.

Alizadeh escribió la investigación con el primer autor y estudiante graduado de EECS Venkat Arun y el autor principal Harry Balakrishnan, profesor de Ciencias de la Computación e Inteligencia Artificial de Fujitsu. La investigación se presentará en la Conferencia del Grupo de Interés Especial de ACM sobre Comunicaciones de Datos (SIGCOMM).

control de congestión

El control de la congestión es un problema de red fundamental que los investigadores han tratado de abordar desde la década de 1980.

La computadora del usuario no sabe qué tan rápido se envían los paquetes de datos a través de la red porque carece de información, como la calidad de la conexión de red o la cantidad de otros remitentes que usan la red. El envío de paquetes con demasiada lentitud hace que se utilice incorrectamente el ancho de banda disponible. Pero enviarlo demasiado rápido puede sobrecargar la red y, al hacerlo, comenzará a perder paquetes. Estos paquetes deben reenviarse, lo que genera demoras más prolongadas. También pueden ocurrir retrasos debido a que los paquetes esperan en las colas durante mucho tiempo.

Los algoritmos de control de congestión utilizan las pérdidas de paquetes y los retrasos como señales para inferir la congestión y determinar qué tan rápido se pueden transmitir los datos. Pero Internet es complejo y los paquetes pueden retrasarse y perderse por motivos no relacionados con la congestión de la red. Por ejemplo, los datos pueden mantenerse en una cola a lo largo del camino y luego liberarse con un grupo de otros paquetes, o el reconocimiento del destinatario puede retrasarse. Los autores llaman “temblores” a los retrasos que no son causados ​​por la congestión.

Incluso si el algoritmo de control de congestión mide el retraso por completo, no puede distinguir entre el retraso inducido por la congestión y el retraso inducido por la fluctuación de fase. El retraso causado por el jitter es impredecible y confunde al remitente. Debido a esta ambigüedad, los usuarios comienzan a estimar la demora de manera diferente, lo que hace que envíen paquetes a velocidades desiguales. En última instancia, explica Aaron, esto conduce a una situación en la que se produce la inanición y la persona se cierra por completo.

“Comenzamos el proyecto porque carecíamos de una comprensión teórica del comportamiento de control de multitudes en presencia de tensión. Para ponerlo sobre una base teórica más estable, construimos un modelo matemático que era lo suficientemente simple como para pensar, pero capaz de capturar algunos de las complejidades de Internet. Fue muy gratificante para ti contarnos Matemáticas con cosas que no sabíamos que tienen una relevancia práctica”, dice.

Estudio del hambre

Los investigadores alimentaron su modelo matemático a una computadora, le dieron una serie de algoritmos de control de aglomeración de uso común y le pidieron a la computadora que encontrara un algoritmo que pudiera evitar la inanición usando su modelo.

“No pudimos hacer eso. Probamos todos los algoritmos que conocíamos y algunos algoritmos nuevos que inventamos. Nada funcionó. La computadora siempre encontró una situación en la que algunas personas obtienen el ancho de banda completo y al menos una persona no obtiene nada”. dice Arón.

Los investigadores se sorprendieron con este hallazgo, especialmente porque se cree que estos algoritmos son razonablemente justos. Comenzaron a sospechar que tal vez no sería posible evitar la hambruna, una forma extrema de injusticia. Esto los llevó a definir una clase de algoritmos que denominan “algoritmos de retardo convergente” que demostraron que siempre morirían de hambre bajo su modelo de red. Todos los algoritmos de control de congestión actuales que controlan el retraso (que los investigadores conocen) son convergentes.

Aaron agrega que el hecho de que los modos de falla simples de estos algoritmos ampliamente utilizados hayan permanecido desconocidos durante tanto tiempo demuestra lo difícil que es comprender los algoritmos solo a través de pruebas empíricas. Subraya la importancia de una base teórica sólida.

Pero la esperanza sigue perdida. Si bien todos los algoritmos probados fallaron, puede haber otros algoritmos no convergentes que podrían evitar la inanición. Esto sugiere que una forma de resolver el problema podría ser diseñar algoritmos de control de congestión que cambien el rango de retraso más ampliamente, por lo que The el rango es mayor que cualquier retraso que pueda ocurrir debido a la inestabilidad de la red.

“Para controlar los retrasos, los algoritmos también intentaron correlacionar las diferencias de retraso en torno al equilibrio deseado, pero no hay nada de malo en crear un contraste de retraso más grande para obtener mejores mediciones del retraso congestivo. Es solo una nueva filosofía de diseño que debe adoptar ”, agrega Balakrishnan.

Ahora, los investigadores quieren seguir presionando para ver si pueden encontrar o construir un algoritmo que elimine la inanición. También quieren aplicar este enfoque de modelado matemático y pruebas computacionales a otros problemas espinosos sin resolver en los sistemas de cuadrícula.

“Dependemos cada vez más de los sistemas informáticos para cosas críticas, y necesitamos poner su confiabilidad sobre una base conceptual más sólida. Hemos mostrado las cosas asombrosas que puede descubrir cuando se toma el tiempo para llegar a esta especificación formal de lo que el problema realmente es”, dice Alizadeh.

Leave a Reply

Your email address will not be published. Required fields are marked *