Déficit round robin
Déficit Round Robin ( DRR ), también Deficit Weighted Round Robin ( DWRR ), es un algoritmo de programación para el programador de red . La DRR es, como las colas equitativas ponderadas (WFQ), una implementación basada en paquetes de la política ideal de uso compartido de procesadores generalizados (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] está configurado con un cuanto 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, el flujo del número i logrará una tasa de datos a largo plazo mínima de , 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 en su valor cuántico. Entonces, el valor del contador de déficit es una cantidad máxima de bytes que se pueden enviar en este turno: si el contador de déficit es mayor que el tamaño del paquete al principio de la cola (HoQ), este paquete se puede enviar y el valor del contador se reduce por 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.
Al igual que otros algoritmos de programación tipo GPS, la elección de los pesos se deja al administrador de la red.
Al igual que WFQ, DRR ofrece una tasa mínima para cada flujo, sea cual sea el tamaño de los paquetes. En la programación por turnos ponderados, la fracción de ancho de banda utilizada depende del tamaño del paquete.
En comparación con el programador 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 cuanto 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 del peor de los casos aquí. [3]