Deficit Round Robin ( DRR ), también Deficit Weighted Round Robin ( DWRR ), es un algoritmo de planificación para el planificador de red . DRR es, al igual que Weighted Fair Queuing (WFQ), una implementación basada en paquetes de la política ideal de Generalized Processor Sharing (GPS). Fue propuesto por M. Shreedhar y G. Varghese en 1995 como un algoritmo eficiente (con complejidad O(1) ) y justo. [1]
En DRR, un planificador que maneja N flujos [a] se configura con un quantum para cada flujo. Esta idea global es que, en cada ronda, el flujo puede enviar como máximo bytes, y el resto, si lo hay, se informa a la siguiente ronda. De esta manera, la tasa mínima que alcanzará el flujo a largo plazo es ; donde es la tasa de enlace.
El DRR escanea todas las colas no vacías en secuencia. Cuando se selecciona una cola no vacía, su contador de déficit se incrementa según su valor cuántico. Luego, el valor del contador de déficit es un número máximo de bytes que se pueden enviar en este turno: si el contador de déficit es mayor que el tamaño del paquete en la cabecera de la cola (HoQ), este paquete se puede enviar y el valor del contador se reduce según el tamaño del paquete. Luego, el tamaño del siguiente paquete se compara con el valor del contador, etc. Una vez que la cola está vacía o el valor del contador es insuficiente, el programador saltará a la siguiente cola. Si la cola está vacía, el valor del contador de déficit se restablece a 0.
Variables y constantes constante entero N // Nb de colas const entero Q[1..N] // Por cuanto de cola entero DC[1..N] // Contador de déficit por cola cola cola[1..N] // Las colas
Bucle de programación mientras sea verdadero hacer para i en 1..N hacer si no cola[i].empty() entonces CC[i]:= CC[i] + Q[i] mientras ( no queue[i].empty() y DC[i] ≥ queue[i].head().size() ) lo hacen DC[i] := DC[i] − cola[i].cabeza().tamaño() enviar( cola[i].head() ) cola[i].dequeue() fin mientras si cola[i].empty() entonces CC[i] := 0 fin si fin si fin para fin mientras
Al igual que otros algoritmos de programación similares al GPS, la elección de los pesos queda en manos del administrador de la red.
Al igual que WFQ, DRR ofrece una tasa mínima para cada flujo, independientemente del tamaño de los paquetes. En la programación por turnos ponderada, la fracción de ancho de banda utilizada depende del tamaño de los paquetes.
En comparación con el planificador WFQ, que tiene una complejidad de O(log(n)) ( n es el número de flujos/colas activos ), la complejidad de DRR es O(1) , si el quantum es mayor que el tamaño máximo de paquete de este flujo. Sin embargo, esta eficiencia tiene un costo: la latencia, es decir, la distancia al GPS ideal, es mayor en DRR que en WFQ. [2] Puede encontrar más información sobre las latencias en el peor de los casos aquí. [3]
Patrick McHardy escribió una implementación del algoritmo round robin de déficit para el kernel de Linux [4] y la publicó bajo la Licencia Pública General de GNU .
En los enrutadores Cisco y Juniper, se implementan versiones modificadas de DRR: dado que la latencia de DRR puede ser mayor para alguna clase de tráfico, estas versiones modificadas otorgan mayor prioridad a algunas colas, mientras que las otras se atienden con el algoritmo DRR estándar. [5] [6]