La congestión de la red en la teoría de colas y redes de datos es la calidad reducida 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 retrasos 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 sólo 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. Estas 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 evitación de la congestión para intentar evitar el colapso. Estos incluyen: retroceso exponencial en protocolos como CSMA/CA en 802.11 y CSMA/CD similar en el Ethernet original , reducción de ventana en TCP y cola justa 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 de control de admisión .
Los recursos de la 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 puede llenar fácilmente con una sola computadora personal. [2] Incluso en redes informáticas rápidas, la red troncal puede verse fácilmente congestionada por unos pocos servidores y PC cliente. Los ataques de denegación de servicio por parte de botnets son capaces de llenar incluso los enlaces más grandes de la red troncal de Internet , generando una congestión de la 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 podría definirse como un ataque de denegación de servicio .
El colapso congestivo (o colapso de la congestión) es la condición en la que la congestión impide o limita la comunicación útil. El colapso de la congestión generalmente ocurre en puntos críticos 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 extensa 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 retrasos y pérdidas de paquetes y la calidad del servicio es extremadamente pobre.
El colapso congestivo se identificó como un posible problema en 1984. [3] Se observó por primera vez en los inicios de Internet en octubre de 1986, [4] cuando la red troncal de fase I de NSFNET cayó tres órdenes de magnitud desde su capacidad de 32 kbit/s a 40 bit/s, [5] 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 enviaron más paquetes de los que podían manejar los enrutadores intermedios, los enrutadores intermedios descartaron muchos paquetes, esperando que los puntos finales de la red retransmitan la información. Sin embargo, las primeras implementaciones de TCP tenían un comportamiento de retransmisión deficiente. Cuando se produjo esta pérdida de paquetes, los puntos finales enviaron paquetes adicionales que repetían la información perdida, duplicando la tasa de entrada.
El control de la congestión modula la entrada del tráfico a una red de telecomunicaciones para evitar el colapso congestivo resultante de la sobresuscripción. [7] Esto normalmente se logra reduciendo la tasa de paquetes. Mientras que el control de congestión evita que los remitentes abrumen la red , el control de flujo evita que el remitente abrume al receptor .
La teoría del control de la congestión fue iniciada 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 de tarifas óptima en toda la red. Ejemplos de asignación de tasas óptima son la asignación justa máxima-mínima y la sugerencia de Kelly de asignación proporcionalmente justa , aunque son posibles muchas otras.
Sea la tasa de flujo , la capacidad del enlace y sea 1 si el flujo usa 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 velocidad . La asignación de tasas óptima entonces satisface
El dual de Lagrange de este problema se desacopla de modo que cada flujo fija su propia tarifa, basándose únicamente en un precio señalado por la red. La capacidad de cada enlace impone una restricción, lo 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 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 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 prevenir la congestión de la red o hacer frente a un colapso de la red:
El comportamiento correcto del punto final suele ser repetir la información eliminada, pero reducir progresivamente la tasa de repetición. Siempre que todos los puntos finales hagan esto, la congestión desaparece y la red reanuda su comportamiento normal. [ cita necesaria ] Otras estrategias, como el inicio lento , garantizan que las nuevas conexiones no abrumen al enrutador antes de que se inicie la detección de congestión.
Los mecanismos comunes para evitar la congestión de los enrutadores incluyen colas justas y otros algoritmos de programación , y detección temprana aleatoria (RED), donde los paquetes se descartan aleatoriamente cuando se detecta la congestión. Esto activa de forma proactiva que los puntos finales reduzcan la transmisión antes de que se produzca un colapso de la 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 Berkeley Standard Distribution UNIX (" BSD ") en 1988 proporcionó por primera vez un buen comportamiento.
UDP no controla la congestión. Los protocolos creados sobre UDP deben manejar la congestión de forma independiente. Los protocolos que transmiten a una velocidad fija, independientemente de la congestión, pueden resultar 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 los paquetes se caigan en presencia de congestión.
Los protocolos orientados a la conexión , como el ampliamente utilizado protocolo TCP, vigilan la pérdida de paquetes o el retraso en la cola para ajustar su velocidad de transmisión. Varios procesos para evitar la congestión de la red respaldan diferentes compensaciones. [9]
El algoritmo para evitar la congestión de 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 caídas de cola , especialmente cuando hay bufferbloat . Esta pérdida retrasada de paquetes interfiere con la prevención automática de la congestión de TCP. Todos los flujos que experimentan esta pérdida de paquetes comienzan un reentrenamiento de TCP en el mismo momento; esto se denomina sincronización global de TCP .
La gestión de colas activas (AQM) es la reordenación o eliminación de paquetes de red dentro de un búfer de transmisión asociado con un controlador de interfaz de red (NIC). Esta tarea la realiza el programador de red .
Una solución es utilizar detección temprana aleatoria (RED) en la cola de salida del equipo de red. [15] [16] En 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 superior a 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 robusto algoritmo de detección temprana aleatoria (RRED) se propuso para mejorar el rendimiento de TCP contra ataques de denegación de servicio (DoS), particularmente ataques de denegación de servicio (LDoS) de baja tasa. Los experimentos confirmaron que los algoritmos tipo 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 algunos criterios. [19]
Otro enfoque es utilizar la notificación de congestión explícita (ECN). [20] ECN se utiliza sólo cuando dos hosts indican que quieren utilizarlo. Con este método, se utiliza un bit de protocolo para señalar una congestión explícita. Esto es mejor que la notificación de congestión indirecta señalada por la pérdida de paquetes mediante los algoritmos RED/WRED, pero requiere soporte por parte de ambos hosts. [21] [15]
Cuando un enrutador recibe un paquete marcado como compatible con ECN y anticipa la congestión, establece el indicador ECN y notifica al remitente sobre la congestión. El remitente debería responder disminuyendo su ancho de banda de transmisión, por ejemplo, disminuyendo su velocidad de envío reduciendo el tamaño de la ventana TCP o por otros medios.
La prevención de la congestión se puede lograr de manera eficiente reduciendo el tráfico. Cuando una aplicación solicita un archivo, gráfico o página web de gran tamaño, normalmente anuncia una ventana de entre 32K y 64K. Esto da como resultado 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 la publicidad en la ventana, los servidores remotos envían menos datos, reduciendo así la congestión. [22] [23]
ECN hacia atrás (BECN) es otro mecanismo de notificación de congestión propuesto. Utiliza mensajes de extinción de origen ICMP 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. Se pueden propagar notificaciones de congestión efectivas a protocolos de capa de transporte, como TCP y UDP, para realizar los ajustes apropiados. [24]
Los protocolos que evitan el colapso congestivo generalmente asumen que la pérdida de datos es causada por la congestión. En las redes cableadas, los errores durante la transmisión son raros. 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 a través de una capa física basada en radio ven 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 para 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 mantuvo 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. Los ejemplos incluyen Oportunidades de transmisión libre de contención (CFTXOP) en el estándar ITU-T G.hn para redes domésticas a través de cableado heredado, Protocolo de reserva de recursos para redes IP y Protocolo de reserva de flujo para Ethernet .
En octubre de 1986, Internet experimentó el primero de lo que se convirtió en una serie de "colapsos de congestión". Durante este período, el rendimiento de datos desde LBL hasta UC Berkeley (sitios separados por 400 yardas y dos saltos IMP) cayó de 32 Kbps a 40 bps. Nos fascinó esta repentina caída de miles de veces 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 podía ajustar para que funcionara mejor en condiciones abismales de red. La respuesta a ambas preguntas fue "sí".
... La ventaja de esta función radica no 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 cubo del tamaño de la cola...
