Round robin ponderado

Algoritmo de programación de tareas o flujos de datos

Weighted round robin ( WRR ) es un programador de red para flujos de datos, pero también se utiliza para programar procesos .

El round robin ponderado ^[1] es una generalización de la programación round robin . Sirve a un conjunto de colas o tareas. Mientras que el round robin recorre las colas o tareas y otorga una oportunidad de servicio por ciclo, el round robin ponderado ofrece a cada una un número fijo de oportunidades, según lo especificado por el peso configurado, que sirve para influir en la porción de capacidad recibida por cada cola o tarea. En las redes informáticas, una oportunidad de servicio es la emisión de un paquete, si la cola seleccionada no está vacía.

Si todos los paquetes tienen el mismo tamaño, WRR es la aproximación más simple del uso compartido generalizado de procesadores (GPS). Existen varias variaciones de WRR. ^[2] Las principales son el WRR clásico y el WRR entrelazado .

Algoritmo

Principios

WRR se presenta a continuación como un programador de red . También se puede utilizar para programar tareas de forma similar.

Un planificador de red round-robin ponderado tiene colas de entrada, . A cada cola se le asocia , un entero positivo, llamado peso . El planificador WRR tiene un comportamiento cíclico. En cada ciclo, cada cola tiene oportunidades de emisión. ${\displaystyle n}$ ${\displaystyle q_{1},...,q_{n}}$ ${\displaystyle q_{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle w_{i}}$

Los diferentes algoritmos WRR difieren en las distribuciones de estas oportunidades en el ciclo.

WRR clásico

En el WRR clásico ^{[2] [3] [4]} el planificador recorre las colas. Cuando se selecciona una cola, el planificador enviará paquetes hasta la emisión del paquete o el final de la cola. ${\displaystyle q_{i}}$ ${\displaystyle w_{i}}$

WRR intercalado

Sea , el peso máximo. En IWRR, ^{[1] [5]} cada ciclo se divide en rondas. Una cola con peso puede emitir un paquete por ronda solo si . ${\displaystyle w_{max}=\max\{w_{i}\}}$ ${\displaystyle w_{max}}$ ${\displaystyle w_{i}}$ ${\displaystyle r}$ ${\displaystyle r\leq w_{i}}$

Ejemplo

Ejemplo de programación para CWRR e IWRR

Considere un sistema con tres colas y pesos respectivos . Considere una situación en la que hay 7 paquetes en la primera cola, A, B, C, D, E, F, G , 3 en la segunda cola, U, V, W y 2 en la tercera cola X, Y. Suponga que no llegan más paquetes. ${\displaystyle q_{1},q_{2},q_{3}}$ ${\displaystyle w_{1}=5,w_{2}=2,w_{3}=3}$

Con el WRR clásico, en el primer ciclo, el planificador selecciona y transmite primero los cinco paquetes en la cabecera de la cola, A, B, C, D, E (desde ), luego selecciona la segunda cola, y transmite los dos paquetes en la cabecera de la cola, U, V (desde ), y por último selecciona la tercera cola, que tiene un peso igual a 3 pero solo dos paquetes, por lo que transmite X, Y . Inmediatamente después del final de la transmisión de Y , comienza el segundo ciclo y se transmiten F, G desde , seguidos de W desde . ${\displaystyle q_{1}}$ ${\displaystyle w_{1}=5}$ ${\displaystyle q_{2}}$ ${\displaystyle w_{2}=2}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$

Con WRR intercalado, el primer ciclo se divide en 5 rondas (desde ). En la primera ( r=1 ), se envía un paquete de cada cola ( A,U,X ), en la segunda ronda ( r=2 ), también se envía otro paquete de cada cola ( B,V,Y ), en la tercera ronda ( r=3 ), solo las colas pueden enviar un paquete ( , y ), pero como está vacío, solo se envía C de , y en la cuarta y quinta rondas, solo se envían D,E de . Luego comienza el segundo ciclo, donde se envían F,W,G . ${\displaystyle max(w_{1},w_{2},w_{3})=5}$ ${\displaystyle q_{1},q_{3}}$ ${\displaystyle w_{1}>=r}$ ${\displaystyle w_{2}<r}$ ${\displaystyle w_{3}>=r}$ ${\displaystyle q_{3}}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{1}}$

Programación de tareas

La programación de tareas o procesos se puede realizar en WRR de una manera similar a la programación de paquetes: cuando se considera un conjunto de tareas activas, se programan de manera cíclica, cada tarea obtiene un quantum o porción de tiempo de procesador. ^{[6] [7]} ${\displaystyle n}$ ${\displaystyle \tau _{i}}$ ${\displaystyle w_{i}}$

Propiedades

Al igual que el método round-robin , la programación round-robin ponderada es simple, fácil de implementar, ahorra trabajo y no genera escasez de trabajo .

Al programar paquetes, si todos los paquetes tienen el mismo tamaño, entonces WRR e IWRR son una aproximación del uso compartido generalizado del procesador : ^[8] una cola recibirá una parte a largo plazo del ancho de banda igual a (si todas las colas están activas) mientras que el GPS sirve cantidades infinitesimales de datos de cada cola no vacía y ofrece esta parte en cualquier intervalo. ${\displaystyle q_{i}}$ ${\displaystyle {\frac {w_{i}}{\sum _{j=1}^{n}w_{j}}}}$

Si las colas tienen paquetes de longitud variable, la parte del ancho de banda que recibe cada cola depende no sólo de los pesos sino también del tamaño de los paquetes.

Si se conoce un tamaño de paquete medio para cada cola , cada cola recibirá una parte a largo plazo del ancho de banda igual a . Si el objetivo es dar a cada cola una parte de la capacidad del enlace (con ), se puede establecer . ${\displaystyle s_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle {\frac {s_{i}\times w_{i}}{\sum _{j=1}^{n}s_{j}\times w_{j}}}}$ ${\displaystyle q_{i}}$ ${\displaystyle \rho _{i}}$ ${\displaystyle \sum _{i=1}^{n}\rho _{i}=1}$ ${\displaystyle w_{i}={\frac {\rho _{i}}{s_{i}}}}$

Dado que IWRR tiene ráfagas por clase más pequeñas que WRR, implica retrasos en el peor de los casos menores. ^[9]

Limitaciones y mejoras

Katevenis, Sidiropoulos y Courcoubetis propusieron por primera vez el método WRR para la programación de paquetes de red en 1991 ^[1] , específicamente para la programación en redes ATM que utilizan paquetes de tamaño fijo (celdas). La principal limitación de la cola round-robin ponderada es que proporciona el porcentaje correcto de ancho de banda a cada clase de servicio solo si todos los paquetes en todas las colas tienen el mismo tamaño o cuando el tamaño medio de los paquetes se conoce de antemano. En el caso más general de las redes IP con paquetes de tamaño variable, para aproximarse al GPS, los factores de ponderación deben ajustarse en función del tamaño del paquete. Eso requiere la estimación del tamaño medio de los paquetes, lo que hace que una buena aproximación al GPS sea difícil de lograr en la práctica con WRR ^{[1] .}

El round robin deficitario es una variante posterior del WRR que logra una mejor aproximación GPS sin conocer de antemano el tamaño medio de los paquetes de cada conexión. También se introdujeron disciplinas de programación más eficaces que abordan las limitaciones mencionadas anteriormente (por ejemplo, colas justas ponderadas ).

Véase también

• Colas justas
• Medida de equidad
• Uso compartido del procesador
• Multiplexación estadística por división de tiempo

Referencias

1. Katevenis, M.; Sidgiropoulos, S.; Courcoubetis, C. (1991). "Multiplexación de celdas por turnos ponderada en un chip de conmutación ATM de propósito general". Revista IEEE sobre áreas seleccionadas en comunicaciones . 9 (8): 1265–1279. doi :10.1109/49.105173. ISSN  0733-8716.
2. Chaskar, HM; Madhow, U. (2003). "Programación justa con latencia ajustable: un enfoque round-robin". Transacciones IEEE/ACM sobre redes . 11 (4): 592–601. doi :10.1109/TNET.2003.815290. ISSN  1063-6692. S2CID  8010108.
3. Brahimi, B.; Aubrun, C.; Rondeau, E. (2006). "Modelado y simulación de políticas de programación implementadas en conmutadores Ethernet mediante redes de Petri coloreadas". Conferencia IEEE de 2006 sobre tecnologías emergentes y automatización de fábricas . págs. 667–674. doi :10.1109/ETFA.2006.355373. ISBN 0-7803-9758-4.S2CID6089006  .​
4. F. Baker; R. Pan (mayo de 2016). "2.2.2. Modelos round-robin". Sobre colas, marcado y eliminación (informe técnico). IETF. RFC 7806.
5. Semeria, Chuck (2001). Supporting Differentiated Service Classes: Queue Scheduling Disciplines (PDF) (Informe). págs. 15–18 . Consultado el 4 de mayo de 2020 .
6. Beaulieu, Alain (invierno de 2017). «Sistemas operativos en tiempo real: programación y programadores» (PDF) . Consultado el 4 de mayo de 2020 .^{[ enlace muerto permanente ]}
7. Estados Unidos 20190266019, Philip D. Hirsch, "Programación de tareas mediante técnicas mejoradas de asignación por turnos ponderada", publicado el 29 de agosto de 2019 
8. Fall, Kevin (29 de abril de 1999). "EECS 122, "Introducción a las redes de comunicación", Lección 27, "Programación de conexiones garantizadas y de máximo esfuerzo"" . Consultado el 4 de mayo de 2020 .
9. Tabatabaee, Seyed Mohammadhossein; Le Boudec, Jean-Yves; Boyer, Marc (22 al 24 de septiembre de 2020). "Round-Robin ponderado entrelazado: un análisis de cálculo de red". Proc. del 32° Int. Congreso Teletráfico (ITC 32) . arXiv : 2003.08372 . doi :10.1109/ITC3249928.2020.00016.