Round robin de déficit

Algoritmo de programación para el programador de red

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]

Detalles

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

Algoritmo

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. ${\displaystyle 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

Rendimiento: imparcialidad, complejidad y latencia

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

Implementaciones

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

Véase también

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

Notas

1. Los flujos también pueden llamarse colas, clases o sesiones.

Referencias

1. Shreedhar, M.; Varghese, G. (octubre de 1995). "Colas justas y eficientes utilizando round robin deficitario". ACM SIGCOMM Computer Communication Review . 25 (4): 231. doi :10.1145/217391.217453. ISSN  0146-4833.
2. Lenzini, L.; Mingozzi, E.; Stea, G. (2002). "Aliquem: Una nueva implementación de DRR para lograr mejor latencia y equidad en complejidad O(1)". IEEE 2002 Décimo taller internacional IEEE sobre calidad de servicio (Cat. No.02EX564) . págs. 77–86. doi :10.1109/IWQoS.2002.1006576. ISBN 978-0-7803-7426-3.S2CID62158653  .​
3. Tabatabaee, Seyed Mohammadhossein; Le Boudec, Jean-Yves (mayo de 2021). "Déficit Round-Robin: un segundo análisis de cálculo de red". 2021 IEEE 27.º Simposio de aplicaciones y tecnología integrada y en tiempo real (RTAS) (PDF) . Nashville, Tennessee, EE.UU.: IEEE. págs. 171–183. doi :10.1109/RTAS52030.2021.00022. ISBN 978-1-6654-0386-3. Número de identificación del sujeto  235294011.
4. "Módulo de programación de red del kernel de Linux DRR". kernel.org . Consultado el 7 de septiembre de 2013 .
5. Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2007). "Análisis de rendimiento de planificadores de déficit modificados". IOS Journal of High Speed ​​Networks . 16 (4): 399–422.
6. Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2006). Análisis de rendimiento de los programadores Round Robin de déficit modificado (Informe técnico). Dipartimento di Ingegneria della Informazione, Universidad de Pisa.

Enlaces externos

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