Round Robin ponderado

Algoritmo de programación de tareas o flujos de datos.

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

La operación por turnos ponderada ^[1] es una generalización de la programación por turnos . Sirve un conjunto de colas o tareas. Mientras que el round robin recorre las colas o tareas y brinda 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 al uso compartido generalizado de procesadores (GPS). Existen varias variaciones de WRR. ^[2] Los 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 programador de red por turnos ponderado tiene colas de entrada, . A cada cola se le asocia un número entero positivo, llamado peso . El planificador WRR tiene un comportamiento cíclico. En cada ciclo, cada cola tiene oportunidades de emisiones. ${\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 programador 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 entrelazado

Sea , el peso máximo. En IWRR, ^{[1] [5]} cada ciclo se divide en rondas. Una cola con peso puede emitir un paquete en ronda sólo 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 sus respectivos pesos . 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 . Supongamos que no llega más paquete. ${\displaystyle q_{1},q_{2},q_{3}}$ ${\displaystyle w_{1}=5,w_{2}=2,w_{3}=3}$

Con WRR clásico, en el primer ciclo, el planificador primero selecciona y transmite los cinco paquetes al principio de la cola, A,B,C,D,E (desde ), luego selecciona la segunda cola, y transmite los dos paquetes en cabeza de 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 from , seguido de W from . ${\displaystyle q_{1}}$ ${\displaystyle w_{1}=5}$ ${\displaystyle q_{2}}$ ${\displaystyle w_{2}=2}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$

Con WRR entrelazado, 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ía, solo se envía C de , y en la cuarta y quinta ronda, 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 forma similar a la programación de paquetes: cuando se considera un conjunto de tareas activas, se programan de forma cíclica, cada tarea obtiene una cantidad o una porción del tiempo del procesador. ^{[6] [7]} ${\displaystyle n}$ ${\displaystyle \tau _{i}}$ ${\displaystyle w_{i}}$

Propiedades

Al igual que la programación por turnos , la programación por turnos ponderada es simple, fácil de implementar, conserva el trabajo y no pasa hambre .

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 el GPS sirve cantidades infinitesimales de datos de cada cola no vacía y ofrecer 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 recibido por cada cola depende no sólo del peso sino también del tamaño de los paquetes.

Si se conoce un tamaño medio de paquetes para cada cola , cada cola recibirá una parte a largo plazo del ancho de banda igual a . Si el objetivo es darle a cada cola una porción de la capacidad del enlace (con ), se puede configurar . ${\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 más pequeños en el peor de los casos. ^[9]

Limitaciones y mejoras

La WRR para la programación de paquetes de red fue propuesta por primera vez por Katevenis, Sidiropoulos y Courcoubetis en 1991, ^[1] específicamente para la programación en redes ATM utilizando paquetes (celdas) de tamaño fijo. La principal limitación de las colas ponderadas por turnos es que proporciona el porcentaje correcto de ancho de banda para cada clase de servicio sólo si todos los paquetes en todas las colas son del mismo tamaño o cuando el tamaño medio de paquete se conoce de antemano. En el caso más general de redes IP con paquetes de tamaño variable, para aproximar el GPS, los factores de peso deben ajustarse en función del tamaño del paquete. Esto requiere una estimación del tamaño promedio de paquete, lo que hace que en la práctica sea difícil lograr una buena aproximación GPS con WRR. ^[1]

El round robin de déficit es una variación posterior de WRR que logra una mejor aproximación GPS sin conocer de antemano el tamaño medio de paquete de cada conexión. También se introdujeron disciplinas de programación más efectivas que manejan las limitaciones mencionadas anteriormente (por ejemplo, colas justas ponderadas ).

Ver también

• Cola justa
• Medida de equidad
• Compartir procesador
• Multiplexación estadística por división de tiempo

Referencias

1. Katevenis, M.; Sidgiropoulos, S.; Courcoubetis, C. (1991). "Multiplexación de células por turnos ponderadas en un chip de conmutador ATM de uso general". Revista IEEE sobre áreas seleccionadas de las 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 por turnos". Transacciones IEEE/ACM en 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 de colores". Conferencia IEEE 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. S2CID  6089006.
4. F. panadero; R. Pan (mayo de 2016). "2.2.2. Modelos por turnos". Sobre hacer cola, marcar y descartar (Informe técnico). IETF. RFC 7806.
5. Semeria, Chuck (2001). Respaldo de clases de servicios diferenciadas: disciplinas de programación de colas (PDF) (Reporte). 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 utilizando técnicas de round robin ponderadas mejoradas", publicado el 29 de agosto de 2019 
8. Otoño, Kevin (29 de abril de 1999). "EECS 122, "Introducción a las redes de comunicación", Conferencia 27, "Programación de conexiones garantizadas y con el mejor 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.