Resumen

  • El round robin por paquetes iguala oportunidades, no bytes. DRR entrega un quantum a cada cola, descuenta el tamaño de los paquetes completos y conserva el saldo cuando el siguiente paquete no cabe y la cola continúa activa.
  • La garantía pertenece al caudal de las colas y pesos configurados. DRR básico no limita por sí solo la espera de cada paquete, no define quién comparte una cola, no controla congestión y no sustituye shaping, admisión ni AQM.

El error cabe dentro del paquete

Un puntero circular ofrece una imagen limpia de imparcialidad: visita la primera cola, transmite un paquete, avanza a la segunda y vuelve al principio. El procedimiento es barato y ninguna cola obtiene dos visitas mientras otra permanece activa esperando su primera.

La imagen cuenta turnos, pero el enlace consume bytes. Con paquetes de longitudes variables, un turno puede valer tres o diez veces otro. En el ejemplo de 1.500 y 500 bytes, ambas colas despachan un paquete por ronda; la primera ocupa tres cuartas partes de los bytes transmitidos. Round robin no ha roto su regla. La regla eligió la unidad equivocada para la finalidad declarada.

M. Shreedhar y George Varghese partieron de esa tensión en el informe de Washington University y en el artículo “Efficient Fair Queuing Using Deficit Round-Robin”. Los algoritmos cercanos al reparto fluido ideal podían exigir más trabajo de selección; las aproximaciones cíclicas eran veloces y sencillas, pero sensibles al tamaño de los paquetes. DRR debía retener la sencillez sin olvidar el servicio que una cola no había podido gastar.

Una cuenta que cruza la frontera de la ronda

Cada cola i tiene un quantum Q_i y un contador DC_i. Al visitar una cola activa, el planificador suma el quantum al contador. Si el paquete de cabecera cabe en el saldo, lo transmite entero y resta su longitud. Repite la operación hasta que la cola se vacía o el siguiente paquete supera el crédito restante.

En ese último caso no fragmenta el paquete ni borra el saldo. Si la cola sigue ocupada, guarda el déficit y la devuelve a la lista activa. En la siguiente ronda añade otro quantum. Un paquete de 1.500 bytes con un quantum de 1.000 puede no salir en la primera visita, reunir 2.000 en la segunda, transmitirse y dejar 500 para lo que venga detrás.

El contador registra crédito de servicio dentro de esta disciplina, no una deuda jurídica ni la frustración de un usuario. Cuando la cola queda vacía, vuelve a cero; una fuente dormida no puede ahorrar indefinidamente para irrumpir más tarde con una ráfaga privilegiada. La memoria existe mientras hay trabajo pendiente.

Los pesos están escritos en los quanta

Quanta iguales buscan participaciones iguales entre colas continuamente ocupadas. Quanta distintos implementan proporciones: una cola con el doble de quantum puede aspirar aproximadamente al doble de servicio de largo plazo, según el conjunto activo y el error inevitable de transmitir paquetes indivisibles.

El trabajo original acota los bytes servidos alrededor del número de oportunidades multiplicado por el quantum, con un margen ligado al tamaño máximo de paquete. Es una definición de equidad más sobria que “todos reciben lo mismo siempre”. Durante un intervalo breve una cola puede adelantarse al enviar un paquete grande. El crédito retenido compensa esa granularidad en rondas posteriores.

La estructura también evita ordenar globalmente todas las colas. Mantiene una lista activa y realiza sumas, comparaciones y restas. Shreedhar y Varghese presentaron un coste de procesamiento O(1) por paquete, casi perfecta equidad de caudal y una implementación suficientemente sencilla para hardware, bajo sus condiciones de quantum y tamaño.

O(1) describe cómo escala la operación; no afirma que toda jerarquía, ASIC o clasificador cueste exactamente los mismos ciclos. La aproximación tampoco convierte un paquete entero en el fluido infinitamente divisible del modelo ideal.

Antes del contador hay una decisión de identidad

El planificador solo distribuye entre las colas que recibe. Una cola puede representar un flujo, varios flujos agrupados por hash, un cliente, una clase o un subplanificador. Si diez aplicaciones caen en la misma cola y otra recibe una cola privada, DRR reparte entre dos identidades visibles. No entra en la primera para separar las diez ocultas.

Por eso, “equidad por flujo” empieza en el clasificador. Alguien elige las claves, el número de colas, el tratamiento de colisiones y el quantum. Un reparto matemáticamente correcto puede producir una política absurda si la población quedó mal agrupada. DRR ejecuta el peso; no decide si ese peso era legítimo.

También hay que conservar la distribución de tamaños. El ejemplo 1.500/500 explica el sesgo, pero no procede de una medición de Cisco, UCLA ni un backbone. En una auditoría real importan el máximo esperado, la mezcla, el tiempo durante el que cada cola estuvo backlogged y quién componía la lista activa.

El caudal puede ser justo y la espera mala

El artículo declara que DRR básico ofrece equidad de throughput pero no límites de latencia, y después estudia una ampliación. Una cola puede recibir la proporción debida durante una ventana larga mientras un paquete concreto espera las visitas de muchas colas. El número de competidores, el quantum, los tamaños y la jerarquía controlan esa espera.

Tampoco es DRR quien decide si la carga debía entrar. La admisión acepta trabajo; el shaping regula ritmo; AQM marca o descarta para gestionar la cola; el control de congestión modifica el emisor. RFC 7567 menciona DRR entre los planificadores de fair queuing, pero mantiene separada la tarea de gestión activa de colas.

Una instalación puede combinar todas esas piezas. Sus métricas no son intercambiables. Un déficit alto no demuestra congestión posterior; uno bajo no demuestra baja latencia. Bytes equilibrados entre clases no son usuarios satisfechos, y haber sacado un paquete de una cola no prueba su entrega final.

George Varghese y el método de network algorithmics

UCLA Samueli identifica a George Varghese como Distinguished Professor of Computer Science y titular de la Jonathan B. Postel Chair in Networking. Sus intereses incluyen network algorithmics y verificación: observar el cuello de botella del camino rápido y diseñar una solución que respete tanto al algoritmo como al hardware. Llegó a UCLA en 2016 después de Microsoft Research y de plazas en UC San Diego y Washington University in St. Louis.

ACM SIGCOMM le concedió en 2014 su premio por contribuciones sostenidas y diversas a network algorithmics con impacto académico e industrial. El Internet Hall of Fame, al incorporarlo en 2021, destacó DRR y su uso histórico en Cisco GSR.

Pero la autoría del mecanismo es inequívocamente conjunta. La publicación nombra primero a M. Shreedhar y después a George Varghese. Centrar un perfil en Varghese permite examinar el método —identificar la unidad escasa, preservar una estructura barata y añadir el estado justo—, no convertir a un coautor en inventor único.

Qué puede certificar el rastro

Un registro de quantum, contador, tamaños y dequeues permite reconstruir por qué una cola transmitió o esperó. Para traducir esa cola en cliente o aplicación se necesita la versión del clasificador. Para hablar de congestión aguas abajo, experiencia o entrega, hacen falta otras mediciones.

La prueba operativa conserva lista activa, ocupación, cabecera, crédito arrastrado y bytes enviados. Las marcas ECN, pérdidas, shaping y cambios de clasificación llevan sus propios recibos. Si la participación en bytes permanece cerca del objetivo mientras crece la cola de latencia, no hay paradoja: la equidad de caudal y la demora son variables diferentes.

Ese es el legado del contador. La justicia de un scheduler no reside en que el puntero dibuje un círculo perfecto. Depende de la unidad que cuenta, de la historia que no borra y de las identidades que el operador coloca detrás de cada saldo. DRR corrigió la aritmética del paquete; no abolió la política de nombrar una cola.

Fuentes