Round robin de déficit

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. ${\displaystyle Q_{i}}$${\estilo de visualización i}$${\displaystyle Q_{i}}$${\estilo de visualización i}$${\displaystyle {\frac {Q_{i}}{(Q_{1}+Q_{2}+...+Q_{N})}}R}$${\estilo de visualización R}$

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. ${\estilo de visualización i}$

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]${\displaystyle Q_{i}}$

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]}

• Algoritmo de programación
• Colas justas
• Uso compartido generalizado del procesador
• Colas justas ponderadas
• Round robin ponderado
• Medida de equidad

• Conferencia EE122 de la UC Berkeley: Cola justa y eficiente utilizando round robin deficitario