Round robin de déficit

El algoritmo Deficit Round Robin ( DRR ), también conocido como 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 cuanto para cada flujo. Esta idea global es que, en cada ronda, el flujo puede enviar como máximo bytes, y el remanente, si lo hay, se informa a la siguiente ronda. De esta manera, la tasa mínima que ese flujo alcanzará a largo plazo es ; donde es la tasa de enlace.${\displaystyle Q_{i}}$${\displaystyle i}$${\displaystyle Q_{i}}$${\displaystyle i}$${\displaystyle {\frac {Q_{i}}{(Q_{1}+Q_{2}+...+Q_{N})}}R}$${\displaystyle 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 en su valor cuántico. El valor del contador de déficit representa la cantidad máxima de bytes que se pueden enviar en ese turno: si el contador de déficit es mayor que el tamaño del paquete al inicio de la cola (HoQ), este paquete se puede enviar y el valor del contador se decrementa en el tamaño del paquete. A continuación, se compara el tamaño del siguiente paquete con el valor del contador, y así sucesivamente. Una vez que la cola está vacía o el valor del contador es insuficiente, el planificador pasa a la siguiente cola. Si la cola está vacía, el valor del contador de déficit se restablece a 0.${\displaystyle i}$

Variables y constantes constante entero N // Número 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 planificación mientras sea verdadero hacer para i en 1..N hacer si no cola[i].vacía() entonces DC[i]:= DC[i] + Q[i] mientras ( no queue[i].empty() y DC[i] ≥ queue[i].head().size() ) hacer DC[i] := DC[i] − cola[i].cabeza().tamaño() enviar(cola[i].cabezal()) cola[i].desencola() fin mientras si cola[i].vacía() entonces DC[i] := 0 fin si fin si fin para fin mientras

Al igual que otros algoritmos de programación tipo GPS, la elección de los pesos queda a criterio del administrador de la red .

Al igual que WFQ, DRR ofrece una tasa mínima a cada flujo, independientemente del tamaño de los paquetes. En la programación round robin ponderada, la fracción de ancho de banda utilizada depende del tamaño de los paquetes.

En comparación con el planificador WFQ, cuya complejidad es O(log(n)) ( donde n es el número de flujos/colas activos ), la complejidad de DRR es O(1) , si el cuanto es mayor que el tamaño máximo del paquete de este flujo. Sin embargo, esta eficiencia tiene un coste: 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 de round robin de déficit para el kernel de Linux ^{[ 4 ]} y la publicó bajo la Licencia Pública General de GNU .

En los routers de Cisco y Juniper, se implementan versiones modificadas de DRR: dado que la latencia de DRR puede ser mayor para ciertas clases de tráfico, estas versiones modificadas dan mayor prioridad a algunas colas, mientras que las demás se atienden con el algoritmo DRR estándar. ^{[ 5 ] [ 6 ]}

• Algoritmo de planificación
• Filas justas
• Compartición generalizada del procesador
• Cola justa ponderada
• Round robin ponderado
• Medida de equidad

• Clase de EE122 de UC Berkeley: Cola justa y eficiente mediante round robin con déficit