stringtranslate.com

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]

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.

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.

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]

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

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). "Deficit Round-Robin: un segundo análisis de cálculo de redes". 2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS) (PDF) . Nashville, TN, 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