CoDel ( Controlled Delay ; pronunciado "coddle") es un algoritmo de gestión de colas activas (AQM) en enrutamiento de red , desarrollado por Van Jacobson y Kathleen Nichols y publicado como RFC8289. [1] Está diseñado para superar el bufferbloat en el hardware de red , como los enrutadores , al establecer límites en el retraso que experimentan los paquetes de red a medida que pasan a través de los buffers en este equipo. CoDel tiene como objetivo mejorar el rendimiento general del algoritmo de detección temprana aleatoria (RED) al abordar algunos de sus conceptos erróneos fundamentales, según lo percibido por Jacobson, y al ser más fácil de administrar.
En 2012, Dave Täht y Eric Dumazet escribieron una implementación de CoDel para el núcleo Linux y la licencia dual GNU General Public License y la licencia BSD de 3 cláusulas . La mejora de Dumazet en CoDel se llama FQ-CoDel , que significa "Fair/Flow Queue CoDel"; se adoptó por primera vez como la solución estándar de AQM y programación de paquetes en 2014 en la versión OpenWrt 14.07 llamada "Barrier Breaker". A partir de allí, CoDel y FQ-CoDel han migrado a varios proyectos posteriores como Tomato , dd-wrt , OPNsense y la función "Smart Queues" de Ubiquiti .
CoDel se basa en observaciones del comportamiento de los paquetes en redes de conmutación de paquetes bajo la influencia de los buffers de datos . Algunas de estas observaciones se refieren a la naturaleza fundamental de las colas y las causas del bufferbloat , mientras que otras se relacionan con las debilidades de los algoritmos alternativos de gestión de colas. CoDel se desarrolló como un intento de abordar el problema del bufferbloat. [2]
El flujo de paquetes se ralentiza al viajar a través de un enlace de red entre una red rápida y una lenta, especialmente al comienzo de una sesión TCP , cuando hay una ráfaga repentina de paquetes y la red más lenta puede no ser capaz de aceptar la ráfaga con la suficiente rapidez. Los buffers existen para aliviar este problema al proporcionar a la red rápida un lugar para almacenar paquetes que la red más lenta leerá a su propio ritmo. [3] En otras palabras, los buffers actúan como amortiguadores para convertir las llegadas en ráfagas en salidas suaves y constantes. Sin embargo, un buffer tiene una capacidad limitada. El tamaño ideal del buffer es tal que puede manejar una ráfaga repentina de comunicación y hacer coincidir la velocidad de esa ráfaga con la velocidad de la red más lenta. Idealmente, la situación de absorción de impactos se caracteriza por un retraso temporal de los paquetes en el buffer durante la ráfaga de transmisión, después del cual el retraso desaparece rápidamente y la red alcanza un equilibrio en la oferta y el manejo de paquetes. [3]
El algoritmo de control de congestión TCP se basa en la pérdida de paquetes para determinar el ancho de banda disponible entre dos dispositivos que se comunican. Acelera la transferencia de datos hasta que los paquetes comienzan a perderse y luego reduce la velocidad de transmisión. Lo ideal es que siga aumentando y disminuyendo la velocidad hasta encontrar el equilibrio en la velocidad del enlace. Para que esto funcione, las pérdidas de paquetes deben ocurrir de manera oportuna para que el algoritmo pueda seleccionar de manera responsable una velocidad de transferencia adecuada. Con paquetes almacenados en un búfer demasiado grande, los paquetes llegarán a su destino pero con una latencia más alta , pero no se perderán paquetes, por lo que TCP no se ralentizará. En estas condiciones, TCP puede incluso decidir que la ruta de la conexión ha cambiado y repetir la búsqueda de un nuevo equilibrio. [4] [5]
Tener un búfer grande y constantemente lleno que provoca mayores demoras en la transmisión y reduce la interactividad, especialmente cuando se analizan dos o más transmisiones simultáneas en el mismo canal, se denomina búfer inflado. El ancho de banda del canal disponible también puede terminar sin usarse, ya que es posible que no se pueda llegar a algunos destinos rápidos debido a que los búferes están obstruidos con datos que esperan ser entregados a destinos lentos.
CoDel distingue entre dos tipos de colas: [3] [6] Una buena cola es aquella que no presenta saturación del búfer. Las ráfagas de comunicación no causan más que un aumento temporal en el retraso de la cola. Se maximiza la utilización del enlace de red. Una mala cola presenta saturación del búfer. Las ráfagas de comunicación hacen que el búfer se llene y permanezca lleno, lo que da como resultado una baja utilización y un retraso del búfer constantemente alto. Para ser eficaz contra la saturación del búfer, una solución en forma de un algoritmo de gestión de colas activa (AQM) debe ser capaz de reconocer una ocurrencia de saturación del búfer y reaccionar implementando contramedidas efectivas.
En 2006, Van Jacobson afirmó que los algoritmos existentes han estado utilizando medios incorrectos para reconocer el bufferbloat. [5] Algoritmos como RED miden la longitud promedio de la cola y lo consideran un caso de bufferbloat si el promedio crece demasiado. Jacobson demostró en 2006 que esta medida no es una buena métrica, ya que la longitud promedio de la cola aumenta bruscamente en el caso de una ráfaga de comunicaciones. La cola puede entonces disiparse rápidamente (buena cola) o convertirse en una cola permanente (mala cola). Otros factores en el tráfico de la red también pueden causar falsos positivos o negativos, lo que hace que se implementen contramedidas innecesariamente. Jacobson sugirió que la longitud promedio de la cola en realidad no contiene información alguna sobre la demanda de paquetes o la carga de la red. [3] [5] Sugirió que una mejor métrica podría ser la longitud mínima de la cola durante una ventana de tiempo deslizante. [3]
Basándose en la idea de Jacobson de 2006, CoDel se desarrolló para gestionar colas bajo el control del retraso mínimo que experimentan los paquetes en la ventana del búfer en ejecución. El objetivo es mantener este retraso mínimo por debajo de los 5 milisegundos. Si el retraso mínimo aumenta a un valor demasiado alto, los paquetes se eliminan de la cola hasta que el retraso cae por debajo del nivel máximo. [3] Nichols y Jacobson citan varias ventajas de utilizar únicamente esta métrica: [3]
CoDel no hace nada para administrar el buffer si el retraso mínimo para la ventana del buffer está por debajo del valor máximo permitido. Tampoco hace nada si el buffer está relativamente vacío (si hay menos de un MTU de bytes en el buffer). [3] Si estas condiciones no se cumplen, CoDel descarta paquetes de manera probabilística. [3]
El algoritmo se calcula de forma independiente en cada salto de red . El algoritmo funciona en un intervalo , inicialmente de 100 milisegundos. El retraso de puesta en cola por paquete se supervisa a lo largo del salto. A medida que se saca de la cola cada paquete para su reenvío , se calcula el retraso de puesta en cola (la cantidad de tiempo que el paquete pasó esperando en la cola). Se almacena el retraso de puesta en cola más bajo para el intervalo. Cuando se saca de la cola el último paquete del intervalo, si el retraso de puesta en cola más bajo para el intervalo es mayor que 5 milisegundos, este único paquete se descarta y el intervalo utilizado para el siguiente grupo de paquetes se acorta. Si el retraso de puesta en cola más bajo para el intervalo es menor que 5 milisegundos, el paquete se reenvía y el intervalo se restablece a 100 milisegundos.
Cuando se acorta el intervalo, se hace de acuerdo con la raíz cuadrada inversa del número de intervalos sucesivos en los que se descartaron paquetes debido a un retraso excesivo en la cola. La secuencia de intervalos es , , , , ...
CoDel ha sido probado en pruebas de simulación por Nichols y Jacobson, en diferentes MTU y velocidades de enlace y otras variaciones de condiciones. En general, los resultados indican: [3] [7]
La simulación también fue realizada por Greg White y Joey Padden en CableLabs . [8]
En mayo de 2012 se realizó una implementación completa de CoDel y se puso a disposición como software de código abierto . [3] Se implementó dentro del núcleo Linux (comenzando con la línea principal 3.5). [9] Dave Täht incorporó CoDel al núcleo Linux 3.3 para el proyecto CeroWrt , que se ocupa entre otras cosas del bufferbloat, [10] donde se probó exhaustivamente. CoDel comenzó a aparecer como una opción en algunas plataformas de gestión de ancho de banda propietarias/llave en mano en 2013. [11] FreeBSD integró CoDel en las ramas de código 11.x [12] y 10.x [13] en 2016. [14] Se distribuye una implementación con OpenBSD desde la versión 6.2. [15]
Fair/Flow Queue CoDel (FQ-CoDel; fq_codel en código Linux) agrega colas de flujo a CoDel para que diferencie entre múltiples conexiones simultáneas y funcione de manera justa. Da prioridad al primer paquete en cada flujo, de modo que los flujos pequeños puedan comenzar y finalizar rápidamente para un mejor uso de los recursos de la red. El coautor de CoDel, Van Jacobson, recomienda el uso de fq_codel en lugar de codel cuando esté disponible. [16] FQ-CoDel se publicó como RFC8290. Fue escrito por T. Hoeiland-Joergensen, P. McKenney, D. Täht, J. Gettys y E. Dumazet, todos miembros del "proyecto bufferbloat". [17]
Common Applications Kept Enhanced (CAKE; sch_cake en código Linux) es un modelador de tráfico combinado y un algoritmo AQM presentado por el proyecto bufferbloat en 2018. Se basa en la experiencia de usar fq_codel con el modelador de tráfico HTB (Hierarchy Token Bucket) . Mejora la implementación htb+fq_codel de Linux al reducir las colisiones de hash entre flujos, reducir la utilización de CPU en el modelado de tráfico y de algunas otras maneras. [18]
En 2022, Dave Täht revisó el estado de las implementaciones de fq_codel y sch_cake en la práctica. Descubrió que, si bien muchos sistemas han cambiado a cualquiera de ellos como AQM predeterminado, varias implementaciones tienen desviaciones dudosas del estándar. Por ejemplo, la implementación de fq_codel de Apple (predeterminada en iOS) tiene una gran cantidad de usuarios pero no tiene el componente "codel". Täht también señala la falta general de descarga de hardware, que se volvió más importante por el aumento del tráfico de red provocado por la pandemia de COVID-19 . [19]
