CoDel

CoDel ( Controlled Delay ; pronunciado " coddle ") es un algoritmo de gestión activa de colas (AQM) en enrutamiento de red , desarrollado por Van Jacobson y Kathleen Nichols y publicado como RFC8289. ^{[ 1 ]} Está diseñado para superar la saturación de búferes en el hardware de red , como los enrutadores , estableciendo límites al retardo que experimentan los paquetes de red al pasar por los búferes en este equipo. CoDel busca mejorar el rendimiento general del algoritmo de detección temprana aleatoria (RED) abordando algunos de sus conceptos erróneos fundamentales, según Jacobson, y siendo más fácil de gestionar.

En 2012, Dave Täht y Eric Dumazet desarrollaron una implementación de CoDel para el kernel de Linux , con doble licencia: la Licencia Pública General de GNU y la licencia BSD de 3 cláusulas . La mejora de Dumazet sobre CoDel se denomina FQ-CoDel , acrónimo de "Fair/Flow Queue CoDel" (CoDel de Cola Justa/Flujo). Fue adoptada por primera vez como solución estándar de AQM y programación de paquetes en 2014, en la versión OpenWrt 14.07 denominada "Barrier Breaker". A partir de ahí, CoDel y FQ-CoDel se han integrado en diversos proyectos derivados, 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 búferes de datos . Algunas de estas observaciones se refieren a la naturaleza fundamental de las colas y las causas de la saturación de búferes , 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 de la saturación de búferes. ^{[ 2 ]}

Basándose en la idea de Jacobson de 2006, CoDel se desarrolló para gestionar colas controlando el retardo mínimo experimentado por los paquetes en la ventana del búfer en ejecución. El objetivo es mantener este retardo mínimo por debajo de 5 milisegundos. Si el retardo mínimo aumenta a un valor demasiado alto, los paquetes se descartan de la cola hasta que el retardo cae por debajo del nivel máximo. ^{[ 3 ]} Nichols y Jacobson citan varias ventajas de utilizar únicamente esta métrica: ^{[ 3 ]}

• CoDel no tiene parámetros. Una de las debilidades del algoritmo RED (según Jacobson) es que resulta demasiado difícil de configurar, especialmente en un entorno con velocidades de enlace dinámicas.
• CoDel trata de forma diferente las colas buenas y las colas malas. Una cola buena tiene, por naturaleza, baja latencia, por lo que el algoritmo de gestión puede ignorarla, mientras que una cola mala está sujeta a la intervención del sistema de gestión, que consiste en descartar paquetes.
• CoDel funciona a partir de un parámetro que se determina completamente de forma local; es independiente de los retrasos de ida y vuelta, las velocidades de enlace, las cargas de tráfico y otros factores que no pueden ser controlados o predichos por el búfer local.
• El retardo mínimo local solo se puede determinar cuando un paquete sale del búfer, por lo que no se necesita ningún retardo adicional para ejecutar la cola y recopilar estadísticas para administrarla.
• CoDel se adapta a las tasas de enlace que cambian dinámicamente sin ningún impacto negativo en la utilización.
• La implementación de CoDel es relativamente sencilla y, por lo tanto, puede abarcar todo el espectro, desde routers domésticos de gama baja hasta soluciones de enrutamiento de gama alta.

CoDel no gestiona el búfer si el retardo mínimo para la ventana del búfer es inferior al valor máximo permitido. Tampoco gestiona el búfer si está relativamente vacío (si contiene menos bytes equivalentes a una MTU ). ^{[ 3 ]} Si estas condiciones no se cumplen, CoDel descarta los paquetes de forma probabilística. ^{[ 3 ]}

El algoritmo se calcula de forma independiente en cada salto de red . El algoritmo opera durante un intervalo , inicialmente de 100 milisegundos. Se monitoriza el retardo de cola por paquete a través del salto. A medida que se extrae cada paquete de la cola para su reenvío , se calcula el retardo de cola (el tiempo que el paquete permaneció en espera). Se almacena el retardo de cola más bajo del intervalo. Cuando se extrae el último paquete del intervalo, si el retardo de cola más bajo del intervalo es mayor que 5 milisegundos, este paquete se descarta y se acorta el intervalo utilizado para el siguiente grupo de paquetes. Si el retardo de cola más bajo del 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 perdieron paquetes debido a un retraso excesivo en la cola. La secuencia de intervalos es${\displaystyle 100}$,${\displaystyle {100 \over {\sqrt {2}}}}$,${\displaystyle {100 \over {\sqrt {3}}}}$,${\displaystyle {100 \over {\sqrt {4}}}}$,${\displaystyle {100 \over {\sqrt {5}}}}$...

CoDel ha sido probado en simulaciones por Nichols y Jacobson, con diferentes MTU y velocidades de enlace y otras variaciones de condiciones. En general, los resultados indican: ^{[ 3 ] [ 7 ]}

• En comparación con RED, CoDel mantiene el retardo de los paquetes más cerca del valor objetivo en todo el rango de anchos de banda (de 3 a 100  Mbit/s). La utilización del enlace medida se mantiene consistentemente cerca del 100 % del ancho de banda del enlace.
• Con una MTU más baja, los retrasos de los paquetes son menores que con una MTU más alta. Una MTU más alta resulta en una buena utilización del enlace, mientras que una MTU más baja resulta en una buena utilización del enlace con un ancho de banda bajo, degradándose a una utilización aceptable con un ancho de banda alto.

Greg White y Joey Padden de CableLabs también realizaron simulaciones . ^{[ 8 ]}

Una implementación completa de CoDel se realizó en mayo de 2012 y se puso a disposición como software de código abierto . ^{[ 3 ]} Se implementó dentro del kernel de Linux (a partir de la línea principal 3.5). ^{[ 9 ]} Dave Täht realizó una retroportación de CoDel al kernel de Linux 3.3 para el proyecto CeroWrt , que se ocupa, entre otras cosas, de 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 tenía CoDel integrado en las ramas de código 11.x ^{[ 12 ]} y 10.x ^{[ 13 ]} en 2016. ^{[ 14 ]} Una implementación se distribuye con OpenBSD desde la versión 6.2. ^{[ 15 ]}

Fair/Flow Queue CoDel (FQ-CoDel; fq_codel en el código Linux) añade colas de flujo a CoDel para que diferencie entre múltiples conexiones simultáneas y funcione de manera equitativa. Da prioridad al primer paquete de cada flujo, de modo que los flujos pequeños puedan comenzar y terminar 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 publica 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 el código Linux) es un algoritmo combinado de modelado de tráfico y 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 de Linux htb+fq_codel al reducir las colisiones de hash entre flujos, disminuir la utilización de la CPU en el modelado de tráfico y en otros aspectos. ^{[ 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 habían adoptado alguna de ellas como AQM predeterminado, varias implementaciones presentaban desviaciones dudosas del estándar. Por ejemplo, la implementación de fq_codel de Apple (predeterminada en iOS) cuenta con un gran número de usuarios, pero carece del componente "codel". Täht también señala la falta general de descarga de hardware, un problema que se agudizó debido al aumento del tráfico de red provocado por la pandemia de COVID-19 . ^{[ 19 ]}

• Protocolo de ventana deslizante
• Ajuste de TCP

• pseudocódigo de CoDel
• Progreso fundamental en la solución del problema de la sobrecarga de búfer