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 la puesta en cola equitativa ponderada (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]
Detalles
En DRR, un planificador que maneja N flujos [a] está configurado con un cuantopara 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 velocidad mínima de datos a largo plazo de, dónde es la tasa de enlace.
Algoritmo
El DRR escanea todas las colas no vacías en secuencia. Cuando una cola no vacíase selecciona, 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 sea 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 const entero N // Nb de colas const entero Q [1..N] // Por cuanto de cola integer DC [1..N] // Contador de déficit por cola queue queue [1..N] // Las colas
Bucle de programación mientras es verdadero hacer para i en 1..N hacer si no hacer cola [i] .empty () entonces DC [i]: = DC [i] + Q [i] while (no cola [i] .empty () y DC [i] ≥ cola [i] .head (). size ()) hacer DC [i]: = DC [i] - cola [i] .head (). Size () enviar (cola [i] .head ()) cola [i] .dequeue () end while if cola [i] .empty () entonces DC [i]: = 0 fin si fin si fin por fin mientras
Actuaciones: equidad, complejidad
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 valor cuánticoes 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]
Implementaciones
Patrick McHardy escribió una implementación del algoritmo round robin de déficit para el kernel de Linux [3] y la publicó bajo la Licencia Pública General GNU .
En los routers 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 dan mayor prioridad a algunas colas, mientras que las otras se sirven con el algoritmo DRR estándar. [4] [5]
Ver también
Notas
- ^ Los flujos también pueden denominarse colas, clases o sesiones.
Referencias
- ^ Shreedhar, M .; Varghese, G. (Octubre de 1995). "Colas justas eficientes usando round robin deficitario" . Revisión de comunicación informática ACM SIGCOMM . 25 (4): 231. doi : 10.1145 / 217391.217453 . ISSN 0146-4833 .
- ^ Lenzini, L .; Mingozzi, E .; Stea, G. (2002). "Aliquem: una implementación novedosa de RRD para lograr una mejor latencia y equidad en la complejidad O (1)". IEEE 2002 Décimo Taller Internacional IEEE sobre Calidad de Servicio (Cat. No.02EX564) . pag. 77. doi : 10.1109 / IWQoS.2002.1006576 . ISBN 978-0-7803-7426-3. S2CID 62158653 .
- ^ "Módulo programador de red del kernel de Linux DRR" . kernel.org . Consultado el 7 de septiembre de 2013 .
- ^ Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2007). "Análisis de rendimiento de programadores de round robin de déficit modificado" . Revista IOS de redes de alta velocidad .
- ^ Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2006). Análisis de desempeño de programadores de round robin de déficit modificado (informe técnico). Dipartimento di Ingegneria della Informazione, Universidad de Pisa.