La congestión de la red en la teoría de las redes de datos y las colas es la reducción de la calidad del servicio que se produce cuando un nodo o enlace de la red transporta más datos de los que puede manejar. Los efectos típicos incluyen demoras en la cola , pérdida de paquetes o bloqueo de nuevas conexiones. Una consecuencia de la congestión es que un aumento incremental en la carga ofrecida conduce a un pequeño aumento o incluso a una disminución en el rendimiento de la red . [1]
Los protocolos de red que utilizan retransmisiones agresivas para compensar la pérdida de paquetes debido a la congestión pueden aumentar la congestión, incluso después de que la carga inicial se haya reducido a un nivel que normalmente no habría inducido la congestión de la red. Dichas redes presentan dos estados estables bajo el mismo nivel de carga. El estado estable con bajo rendimiento se conoce como colapso congestivo .
Las redes utilizan técnicas de control y prevención de la congestión para intentar evitar el colapso. Estas incluyen: retroceso exponencial en protocolos como CSMA/CA en 802.11 y el similar CSMA/CD en el Ethernet original , reducción de ventana en TCP y colas justas en dispositivos como enrutadores y conmutadores de red . Otras técnicas que abordan la congestión incluyen esquemas de prioridad que transmiten algunos paquetes con mayor prioridad antes que otros y la asignación explícita de recursos de red a flujos específicos mediante el uso del control de admisión .
Los recursos de red son limitados, incluido el tiempo de procesamiento del enrutador y el rendimiento del enlace . La contención de recursos puede ocurrir en las redes en varias circunstancias comunes. Una LAN inalámbrica se llena fácilmente con una sola computadora personal. [2] Incluso en redes de computadoras rápidas, la red troncal puede congestionarse fácilmente con unos pocos servidores y PC cliente. Los ataques de denegación de servicio por parte de botnets son capaces de llenar incluso los enlaces de red troncal de Internet más grandes , lo que genera una congestión de red a gran escala. En las redes telefónicas, un evento de llamada masiva puede saturar los circuitos telefónicos digitales, en lo que de otro modo se puede definir como un ataque de denegación de servicio.
El colapso por congestión (o colapso por congestión) es la condición en la que la congestión impide o limita la comunicación útil. El colapso por congestión generalmente ocurre en los puntos de estrangulamiento de la red, donde el tráfico entrante excede el ancho de banda saliente. Los puntos de conexión entre una red de área local y una red de área amplia son puntos de estrangulamiento comunes. Cuando una red se encuentra en esta condición, se establece en un estado estable donde la demanda de tráfico es alta pero hay poco rendimiento útil disponible, durante el cual se producen demoras y pérdidas de paquetes y la calidad del servicio es extremadamente mala.
El colapso por congestión se identificó como un posible problema en 1984. [3] Se observó por primera vez en Internet en octubre de 1986, [4] cuando la red troncal de fase I de NSFNET cayó tres órdenes de magnitud de su capacidad de 32 kbit/s a 40 bit/s, [5] lo que continuó hasta que los nodos finales comenzaron a implementar el control de congestión de Van Jacobson y Sally Floyd entre 1987 y 1988. [6] Cuando se enviaban más paquetes de los que podían manejar los enrutadores intermedios, estos descartaban muchos paquetes, esperando que los puntos finales de la red retransmitieran la información. Sin embargo, las primeras implementaciones de TCP tenían un comportamiento de retransmisión deficiente. Cuando se producía esta pérdida de paquetes, los puntos finales enviaban paquetes adicionales que repetían la información perdida, duplicando la tasa de entrada.
El control de congestión modula la entrada de tráfico a una red de telecomunicaciones para evitar un colapso por congestión resultante de una sobredemanda. [7] Esto se logra generalmente reduciendo la tasa de paquetes. Mientras que el control de congestión evita que los remitentes saturen la red , el control de flujo evita que el remitente sature al receptor .
La teoría del control de la congestión fue desarrollada por Frank Kelly , quien aplicó la teoría microeconómica y la teoría de optimización convexa para describir cómo los individuos que controlan sus propias tarifas pueden interactuar para lograr una asignación óptima de tarifas en toda la red. Algunos ejemplos de asignación óptima de tarifas son la asignación justa de máximos y mínimos y la sugerencia de Kelly de una asignación proporcionalmente justa , aunque existen muchas otras posibilidades.
Sea la tasa de flujo , la capacidad del enlace , y 1 si el flujo utiliza el enlace y 0 en caso contrario. Sean , y los vectores y la matriz correspondientes. Sea una función creciente estrictamente cóncava , llamada utilidad , que mide cuánto beneficio obtiene un usuario al transmitir a una tasa . La asignación de tasa óptima satisface entonces
El dual de Lagrange de este problema se desacopla de modo que cada flujo fija su propia tasa, basándose únicamente en un precio señalado por la red. Cada capacidad de enlace impone una restricción, que da lugar a un multiplicador de Lagrange , . La suma de estos multiplicadores, es el precio al que responde el flujo.
El control de la congestión se convierte entonces en un algoritmo de optimización distribuida. Muchos algoritmos de control de la congestión actuales se pueden modelar en este marco, ya sea la probabilidad de pérdida o el retraso en la cola en el enlace . Una debilidad importante es que asigna el mismo precio a todos los flujos, mientras que el control de flujo de ventana deslizante provoca ráfagas que hacen que los diferentes flujos observen diferentes pérdidas o retrasos en un enlace determinado.
Entre las formas de clasificar los algoritmos de control de congestión se encuentran:
Se han inventado mecanismos para evitar la congestión de la red o para hacer frente a un colapso de la red:
El comportamiento correcto de los puntos finales suele ser repetir la información descartada, pero reducir progresivamente la velocidad de repetición. Si todos los puntos finales hacen esto, la congestión se alivia y la red reanuda su comportamiento normal. [ cita requerida ] Otras estrategias, como el inicio lento , garantizan que las nuevas conexiones no saturen el enrutador antes de que se inicie la detección de congestión.
Los mecanismos comunes para evitar la congestión del enrutador incluyen colas justas y otros algoritmos de programación , y detección temprana aleatoria (RED), donde los paquetes se descartan aleatoriamente cuando se detecta una congestión. Esto activa de manera proactiva los puntos finales para que reduzcan la velocidad de transmisión antes de que se produzca un colapso por congestión.
Algunos protocolos de extremo a extremo están diseñados para comportarse bien en condiciones de congestión; TCP es un ejemplo bien conocido. Las primeras implementaciones de TCP para manejar la congestión se describieron en 1984, [8] pero la inclusión de Van Jacobson de una solución de código abierto en la distribución estándar de UNIX de Berkeley (" BSD ") en 1988 fue la primera en proporcionar un buen comportamiento.
El protocolo UDP no controla la congestión. Los protocolos creados sobre el protocolo UDP deben gestionar la congestión de forma independiente. Los protocolos que transmiten a una velocidad fija, independientemente de la congestión, pueden ser problemáticos. Los protocolos de transmisión en tiempo real, incluidos muchos protocolos de voz sobre IP , tienen esta propiedad. Por lo tanto, se deben tomar medidas especiales, como la calidad del servicio, para evitar que se pierdan paquetes en presencia de congestión.
Los protocolos orientados a la conexión , como el ampliamente utilizado protocolo TCP, detectan la pérdida de paquetes o el retraso en la cola para ajustar su velocidad de transmisión. Varios procesos de prevención de la congestión de la red admiten diferentes compensaciones. [9]
El algoritmo de prevención de congestión TCP es la base principal para el control de la congestión en Internet. [10] [11] [12] [13] [14]
Los problemas ocurren cuando los flujos TCP simultáneos experimentan pérdidas de paquetes , especialmente cuando hay un bufferbloat . Esta pérdida de paquetes demorada interfiere con la prevención automática de congestión de TCP. Todos los flujos que experimentan esta pérdida de paquetes comienzan un reentrenamiento de TCP al mismo tiempo; esto se denomina sincronización global de TCP .
La gestión de colas activas (AQM) consiste en reordenar o descartar paquetes de red dentro de un búfer de transmisión asociado a un controlador de interfaz de red (NIC). Esta tarea la realiza el programador de red .
Una solución es utilizar la detección temprana aleatoria (RED) en la cola de salida del equipo de red. [15] [16] En los puertos de hardware de red con más de una cola de salida, se puede utilizar la detección temprana aleatoria ponderada (WRED).
RED envía señales indirectas al remitente y al receptor TCP descartando algunos paquetes, por ejemplo, cuando la longitud promedio de la cola es mayor que un umbral (por ejemplo, 50%) y elimina lineal o cúbicamente más paquetes, [17] hasta, por ejemplo, el 100%, a medida que la cola se llena más.
El algoritmo de detección temprana aleatoria robusta (RRED) se propuso para mejorar el rendimiento de TCP frente a ataques de denegación de servicio (DoS), en particular ataques de denegación de servicio de baja tasa (LDoS). Los experimentos confirmaron que los algoritmos similares a RED eran vulnerables a los ataques LDoS debido al tamaño oscilante de la cola TCP causado por los ataques. [18]
Algunos equipos de red están equipados con puertos que pueden seguir y medir cada flujo y, por lo tanto, pueden señalar un flujo de ancho de banda demasiado grande de acuerdo con alguna política de calidad de servicio. Una política podría entonces dividir el ancho de banda entre todos los flujos según ciertos criterios. [19]
Otro enfoque es utilizar la Notificación de Congestión Explícita (ECN). [20] La ECN se utiliza solo cuando dos hosts indican que quieren utilizarla. Con este método, se utiliza un bit de protocolo para indicar la congestión explícita. Esto es mejor que la notificación de congestión indirecta indicada por la pérdida de paquetes por los algoritmos RED/WRED, pero requiere el apoyo de ambos hosts. [21] [15]
Cuando un enrutador recibe un paquete marcado como compatible con ECN y prevé que habrá congestión, activa el indicador ECN, notificando al remitente sobre la congestión. El remitente debe responder disminuyendo su ancho de banda de transmisión, por ejemplo, disminuyendo su velocidad de envío al reducir el tamaño de la ventana TCP o por otros medios.
La reducción del tráfico puede evitar la congestión de forma eficaz. Cuando una aplicación solicita un archivo, gráfico o página web de gran tamaño, normalmente anuncia una ventana de entre 32 K y 64 K. Esto hace que el servidor envíe una ventana completa de datos (suponiendo que el archivo sea más grande que la ventana). Cuando muchas aplicaciones solicitan descargas simultáneamente, estos datos pueden crear un punto de congestión en un proveedor ascendente. Al reducir el anuncio de la ventana, los servidores remotos envían menos datos, lo que reduce la congestión. [22] [23]
El mecanismo de notificación de congestión de red (BECN) hacia atrás es otro mecanismo de notificación de congestión propuesto. Utiliza mensajes ICMP de extinción de origen como mecanismo de señalización IP para implementar un mecanismo ECN básico para redes IP, manteniendo las notificaciones de congestión en el nivel IP y sin requerir negociación entre los puntos finales de la red. Las notificaciones de congestión efectivas se pueden propagar a protocolos de capa de transporte, como TCP y UDP, para realizar los ajustes apropiados. [24]
Los protocolos que evitan el colapso por congestión generalmente suponen que la pérdida de datos se debe a la congestión. En las redes cableadas, los errores durante la transmisión son poco frecuentes. Las redes WiFi , 3G y otras redes con una capa de radio son susceptibles a la pérdida de datos debido a interferencias y pueden experimentar un rendimiento deficiente en algunos casos. Las conexiones TCP que se ejecutan sobre una capa física basada en radio detectan la pérdida de datos y tienden a creer erróneamente que se está produciendo una congestión.
El protocolo de inicio lento funciona mal en conexiones cortas. Los navegadores web más antiguos creaban muchas conexiones de corta duración y abrían y cerraban la conexión para cada archivo. Esto mantenía la mayoría de las conexiones en el modo de inicio lento. El rendimiento inicial puede ser deficiente y muchas conexiones nunca salen del régimen de inicio lento, lo que aumenta significativamente la latencia. Para evitar este problema, los navegadores modernos abren varias conexiones simultáneamente o reutilizan una conexión para todos los archivos solicitados desde un servidor en particular.
El control de admisión es cualquier sistema que requiere que los dispositivos reciban permiso antes de establecer nuevas conexiones de red. Si la nueva conexión corre el riesgo de crear congestión, se puede denegar el permiso. Algunos ejemplos incluyen las oportunidades de transmisión sin contención (CFTXOP) en el estándar ITU-T G.hn para redes domésticas sobre cableado tradicional, el protocolo de reserva de recursos para redes IP y el protocolo de reserva de flujo para Ethernet .
En octubre de 1986, Internet sufrió el primero de lo que se convirtió en una serie de "colapsos de congestión". Durante este período, el rendimiento de datos de LBL a UC Berkeley (sitios separados por 400 yardas y dos saltos IMP) cayó de 32 Kbps a 40 bps. Estábamos fascinados por esta caída repentina de un factor de mil en el ancho de banda y nos embarcamos en una investigación de por qué las cosas habían empeorado tanto. En particular, nos preguntamos si el TCP 4.3BSD (Berkeley UNIX) se estaba comportando mal o si se lo podía ajustar para que funcionara mejor en condiciones de red abismales. La respuesta a ambas preguntas fue "sí".
...La ventaja de esta función no radica solo en evitar fuertes oscilaciones, sino también en evitar la subutilización del enlace con cargas bajas. La aplicabilidad de la función derivada es independiente del rango de carga, no es necesario ajustar ningún parámetro. En comparación con la función de caída lineal original, la aplicabilidad se amplía considerablemente... Nuestro ejemplo con parámetros de sistema realistas proporciona una función de aproximación del cúbico del tamaño de la cola...
