Cuando los usuarios quieren enviar datos a través de Internet más rápido de lo que la red puede soportar, puede producirse una congestión, del mismo modo que el tráfico congestiona el viaje matutino a una gran ciudad.

Los ordenadores y dispositivos que transmiten datos por Internet los dividen en paquetes más pequeños y utilizan un algoritmo especial para decidir a qué velocidad enviar esos paquetes. Estos algoritmos de control de la congestión tratan de descubrir y utilizar plenamente la capacidad disponible de la red, compartiéndola de forma equitativa con otros usuarios que puedan estar compartiendo la misma red. Estos algoritmos tratan de minimizar el retraso causado por los datos que esperan en las colas de la red.

A lo largo de la última década, los investigadores de la industria y el mundo académico han desarrollado varios algoritmos que intentan alcanzar altas tasas y controlar los retrasos. Algunos de ellos, como el algoritmo BBR desarrollado por Google, son ahora ampliamente utilizados por muchos sitios web y aplicaciones.

Pero un equipo de investigadores del MIT ha descubierto que estos algoritmos pueden ser profundamente injustos. En un nuevo estudio, demuestran que siempre habrá un escenario de red en el que al menos un remitente no reciba casi nada de ancho de banda en comparación con otros remitentes; es decir, no se puede evitar un problema conocido como hambre.

"Lo realmente sorprendente de este trabajo y de los resultados es que, si se tiene en cuenta la complejidad de las rutas de red en el mundo real y todo lo que pueden hacer a los paquetes de datos, es básicamente imposible que los algoritmos de control de la congestión por retardo eviten la inanición con los métodos actuales", afirma Mohammad Alizadeh, profesor asociado de ingeniería eléctrica e informática (EECS).

Aunque Alizadeh y sus coautores no lograron encontrar un algoritmo de control de la congestión tradicional que pudiera evitar la inanición, es posible que haya algoritmos de una clase diferente que puedan evitar este problema. Su análisis también sugiere que cambiar el funcionamiento de estos algoritmos, de modo que permitan mayores variaciones de retardo, podría ayudar a evitar la inanición en algunas situaciones de red.

Alizadeh escribió el artículo con el primer autor y estudiante de posgrado de EECS, Venkat Arun, y con el autor principal, Hari Balakrishnan, profesor de Ciencias de la Computación e Inteligencia Artificial de Fujitsu. La investigación se presentará en la conferencia del ACM Special Interest Group on Data Communications (SIGCOMM).

Control de la congestión

El control de la congestión es un problema fundamental de las redes de comunicación que los investigadores llevan tratando de resolver desde la década de 1980.

El ordenador de un usuario no sabe a qué velocidad debe enviar paquetes de datos por la red porque carece de información, como la calidad de la conexión de red o cuántos otros remitentes están utilizando la red. El envío de paquetes demasiado lento hace un mal uso del ancho de banda disponible. Pero enviarlos demasiado rápido puede sobrecargar la red y, al hacerlo, los paquetes empezarán a perderse. Estos paquetes deben ser reenviados, lo que provoca mayores retrasos. Los retrasos también pueden deberse a que los paquetes esperan en las colas durante mucho tiempo.

Los algoritmos de control de la congestión utilizan las pérdidas de paquetes y los retrasos como señales para inferir la congestión y decidir a qué velocidad enviar los datos. Pero Internet es complicada, y los paquetes pueden retrasarse y perderse por razones no relacionadas con la congestión de la red. Por ejemplo, los datos pueden quedar retenidos en una cola en el camino y luego liberarse con una ráfaga de otros paquetes, o el acuse de recibo del receptor puede retrasarse. Los autores denominan "jitter" a los retrasos no causados por la congestión.

Incluso si un algoritmo de control de la congestión mide perfectamente el retraso, no puede distinguir entre el retraso causado por la congestión y el causado por el jitter. El retraso causado por el jitter es imprevisible y confunde al emisor. Debido a esta ambigüedad, los usuarios empiezan a estimar el retardo de forma diferente, lo que hace que envíen paquetes a ritmos desiguales. A la larga, esto lleva a una situación en la que se produce la inanición y alguien se queda completamente fuera, explica Arun.

"Empezamos el proyecto porque carecíamos de una comprensión teórica del comportamiento del control de la congestión en presencia de jitter. Para asentarlo sobre una base teórica más firme, construimos un modelo matemático lo suficientemente sencillo como para pensar en él, pero capaz de captar algunas de las complejidades de Internet. Ha sido muy gratificante que las matemáticas nos digan cosas que no sabíamos y que tienen relevancia práctica", afirma.

Estudiar la inanición

Los investigadores introdujeron su modelo matemático en un ordenador, le dieron una serie de algoritmos de control de congestión de uso común y le pidieron que encontrara un algoritmo que pudiera evitar la inanición, utilizando su modelo.

"No pudimos hacerlo. Probamos todos los algoritmos que conocemos y algunos nuevos que inventamos. Nada funcionó. El ordenador siempre encontraba una situación en la que algunas personas recibían todo el ancho de banda y al menos una persona no recibía básicamente nada", dice Arun.

A los investigadores les sorprendió este resultado, sobre todo porque se cree que estos algoritmos son razonablemente justos. Empezaron a sospechar que quizá no sea posible evitar la inanición, una forma extrema de injusticia. Esto les motivó a definir una clase de algoritmos que denominan "algoritmos convergentes en retardo" y que demostraron que siempre sufrirán inanición bajo su modelo de red. Todos los algoritmos de control de la congestión que controlan el retardo (que los investigadores conocen) son convergentes en retardo.

El hecho de que unos modos de fallo tan sencillos de estos algoritmos tan utilizados hayan permanecido desconocidos durante tanto tiempo ilustra lo difícil que es comprender los algoritmos únicamente mediante pruebas empíricas, añade Arun. Esto subraya la importancia de una sólida base teórica.

Pero no se han perdido todas las esperanzas. Aunque todos los algoritmos que probaron fracasaron, es posible que haya otros algoritmos que no sean convergentes en cuanto al retardo y que puedan evitar la inanición. Esto sugiere que una forma de solucionar el problema podría ser diseñar algoritmos de control de la congestión que varíen el rango de retardo de forma más amplia, de modo que el rango sea mayor que cualquier retardo que pueda producirse debido al jitter en la red.

"Para controlar los retrasos, los algoritmos han tratado de acotar también las variaciones de retardo en torno a un equilibrio deseado, pero no hay nada malo en crear potencialmente una mayor variación de retardo para obtener mejores mediciones de los retrasos por congestión. Es sólo una nueva filosofía de diseño que habría que adoptar", añade 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 modelización matemática y pruebas computacionales a otros problemas espinosos y sin resolver de los sistemas en red.

"Cada vez dependemos más de los sistemas informáticos para cosas muy críticas, y necesitamos que su fiabilidad tenga una base conceptual más firme. Hemos demostrado las cosas sorprendentes que se pueden descubrir cuando se dedica tiempo a elaborar estas especificaciones formales de lo que realmente es el problema", dice Alizadeh.

###

Escrito por Adam Zewe, MIT News Office