Hispanopedia Wiki
Articulo de referencia

Round robin ponderado

El algoritmo Weighted Round Robin ( WRR ) es un planificador de red para flujos de datos, pero también se utiliza para planificar procesos . El round robin ponderado [ 1 ] es un...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo Weighted Round Robin ( WRR ) es un planificador de red para flujos de datos, pero también se utiliza para planificar procesos .

El round robin ponderado [ 1 ] es una generalización de la planificación round-robin . Atiende a un conjunto de colas o tareas. Mientras que round-robin recorre las colas o tareas y ofrece 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 influye en la porción de capacidad que recibe cada cola o tarea. En 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 del procesador (GPS). Existen varias variantes de WRR. [ 2 ] Las principales son el WRR clásico y el WRR entrelazado .

Algoritmo

Principios

A continuación, se presenta WRR como un planificador de red . También puede utilizarse para programar tareas de forma similar.

Un planificador de red round-robin ponderado tienenorte{\displaystyle n}colas de entrada,q1,...,qnorte{\displaystyle q_{1},...,q_{n}}. A cada colaqi{\displaystyle q_{i}}está asociadowi{\displaystyle w_{i}}, un entero positivo, llamado peso . El planificador WRR tiene un comportamiento cíclico. En cada ciclo, cada cola qi{\displaystyle q_{i}}tienewi{\displaystyle w_{i}}oportunidades de emisiones.

Los distintos algoritmos WRR difieren en la distribución de estas oportunidades en el ciclo.

WRR clásico

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

WRR intercalado

Dejarwmetroaincógnita=máximo{wi}{\displaystyle w_{max}=\max\{w_{i}\}}, sea el peso máximo. En IWRR, [ 1 ] [ 5 ] cada ciclo se divide enwmetroaincógnita{\displaystyle w_{max}}rondas. Una cola con pesowi{\displaystyle w_{i}}puede emitir un paquete en rondar{\displaystyle r}solo sir≤wi{\displaystyle r\leq w_{i}}.

Ejemplo

Ejemplo de programación para CWRR e IWRR

Consideremos un sistema con tres colas.q1,q2,q3{\displaystyle q_{1},q_{2},q_{3}}y pesos respectivosw1=5,w2=2,w3=3{\displaystyle w_{1}=5,w_{2}=2,w_{3}=3}Consideremos 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 llegan más paquetes.

Con WRR clásico, en el primer ciclo, el planificador primero seleccionaq1{\displaystyle q_{1}}y transmite los cinco paquetes en la cabecera de la cola, A, B, C, D, E (ya quew1=5{\displaystyle w_{1}=5}), luego selecciona la segunda cola, q2{\displaystyle q_{2}}y transmite los dos paquetes en la cabecera de la cola, U,V (ya quew2=2{\displaystyle w_{2}=2}), 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 F,G deq1{\displaystyle q_{1}}se transmiten, seguidos de W desdeq2{\displaystyle q_{2}}.

Con WRR intercalado, el primer ciclo se divide en 5 rondas (ya quemetroaincógnita(w1,w2,w3)=5{\ Displaystyle max (w_ {1}, w_ {2}, w_ {3}) = 5}). 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 se envían las colas q1,q3{\displaystyle q_{1},q_{3}}Se permite enviar un paquete (w1>=r{\displaystyle w_{1}>=r},w2<r{\displaystyle w_{2}<r}yw3>=r{\displaystyle w_{3}>=r}), pero dado queq3{\displaystyle q_{3}}está vacío, solo C de q1{\displaystyle q_{1}}se envía, y en la cuarta y quinta ronda, solo D,E de q1{\displaystyle q_{1}}se envían. Luego comienza el segundo ciclo, donde se envían F, W, G.

Programación de tareas

La planificación de tareas o procesos se puede realizar en WRR de una manera similar a la planificación de paquetes: al considerar un conjunto denorte{\displaystyle n}tareas activas, se programan de forma cíclica, cada tareaτi{\displaystyle \tau _{i}}obtienewi{\displaystyle w_{i}}cuanto o segmento de tiempo de procesador. [ 6 ] [ 7 ]

Propiedades

Al igual que el algoritmo round-robin , la planificación round-robin ponderada es sencilla, fácil de implementar, conserva el trabajo y evita la inanición .

Al programar paquetes, si todos los paquetes tienen el mismo tamaño, entonces WRR e IWRR son una aproximación de la compartición generalizada del procesador : [ 8 ] una colaqi{\displaystyle q_{i}}recibirá una parte a largo plazo del ancho de banda igual awi∑j=1nortewj{\displaystyle {\frac {w_{i}}{\sum _{j=1}^{n}w_{j}}}}(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.

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

Si el tamaño medio de los paquetessi{\displaystyle s_{i}}es conocido por cada colaqi{\displaystyle q_{i}}, cada cola recibirá una parte a largo plazo del ancho de banda igual a si×wi∑j=1nortesj×wj{\displaystyle {\frac {s_{i}\times w_{i}}{\sum _{j=1}^{n}s_{j}\times w_{j}}}}. Si el objetivo es dar a cada colaqi{\displaystyle q_{i}}una porciónρi{\displaystyle \rho _{i}}de capacidad de enlace (con∑i=1norteρi=1{\displaystyle \sum _{i=1}^{n}\rho _{i}=1}), uno puede establecer wi=ρisi{\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 más pequeños. [ 9 ]

Limitaciones y mejoras

El algoritmo WRR para la programación de paquetes de red fue propuesto por primera vez por Katevenis, Sidiropoulos y Courcoubetis en 1991, [ 1 ] específicamente para la programación en redes ATM que utilizan paquetes (celdas) de tamaño fijo. La principal limitación del algoritmo de colas round-robin ponderado 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 si se conoce de antemano el tamaño medio de los paquetes. En el caso más general de redes IP con paquetes de tamaño variable, para aproximar el GPS, los factores de ponderación deben ajustarse en función del tamaño del paquete. Esto requiere la estimación del tamaño medio de los paquetes, lo que dificulta lograr una buena aproximación del GPS en la práctica con WRR. [ 1 ]

El algoritmo Deficit Round Robin es una variante posterior de 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 gestionan las limitaciones mencionadas anteriormente (por ejemplo, la cola justa ponderada ).

Uso en sistemas operativos en tiempo real

El algoritmo round robin ponderado ha sido adoptado por varios sistemas operativos en tiempo real (RTOS) como estrategia de planificación de tareas, donde los pesos de las tareas determinan la proporción de tiempo de CPU asignada a cada hilo.

Entre los ejemplos más destacados se encuentra SuperTinyKernel RTOS , un RTOS de C++ para sistemas embebidos que implementa una estrategia Smooth Weighted Round Robin (SWRR). SWRR es una variante mejorada del WRR clásico que distribuye el tiempo de CPU proporcionalmente a la carga de las tareas, evitando deliberadamente las ráfagas de ejecución. Esto garantiza que las tareas de alta carga no monopolicen el procesador en un único ciclo de planificación, sino que sus cuantos de tiempo adicionales se distribuyan uniformemente a lo largo del ciclo. Esto resulta en una utilización de CPU más uniforme y una menor fluctuación de la planificación en comparación con el WRR clásico, a costa de un cálculo de planificación ligeramente más complejo por cambio de contexto . [ 10 ]

Véase también

Referencias

  1. 1 2 3 4 Katevenis, M.; Sidgiropoulos, S.; Courcoubetis, C. (1991). "Multiplexación de celdas round-robin ponderada en un chip de conmutación ATM de propósito general". IEEE Journal on Selected Areas in Communications . 9 (8): 1265– 1279. Bibcode : 1991IJSAC...9.1265K . doi : 10.1109/49.105173 . ISSN 0733-8716 . 
  2. 1 2 Chaskar, HM; Madhow, U. (2003). "Programación justa con latencia ajustable: un enfoque round-robin". IEEE/ACM Transactions on Networking . 11 (4): 592– 601. Bibcode : 2003ITNet..11..592C . 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 planificació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. S2CID 6089006 . 
  4. ↑ F. Baker; R. Pan (mayo de 2016). "2.2.2. Modelos Round-Robin". Sobre colas, marcado y descarte (Informe técnico). IETF. RFC 7806.
  5. ↑ Semeria, Chuck (2001). Supporting Differentiated Service Classes: Queue Scheduling Disciplines (PDF) (Informe). pp. 15–18 . Recuperado el 4 de mayo de 2020 . 
  6. ↑ Beaulieu, Alain (Invierno 2017). "Sistemas Operativos en Tiempo Real: Planificación y Planificadores" (PDF) . Consultado el 4 de mayo de 2020 .
  7. ↑ Estados Unidos 20190266019 , Philip D. Hirsch, "Programación de tareas mediante técnicas mejoradas de Round Robin ponderado", 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 de mejor esfuerzo y garantizadas"" . 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 .
  10. ^ "SuperTinyKernel™ (STK)" . stk.neutroncode.com . Consultado el 22 de febrero de 2026 .