Round robin ponderado ( 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 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 uno 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 de computadoras, 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 de uso compartido de procesador generalizado (GPS). Existen varias variaciones de WRR. [2] Los principales son el WRR clásico y el WRR intercalado .
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 ponderado por turnos tiene colas de entrada, . A cada cola está asociado , un número entero positivo, llamado peso . El programador WRR tiene un comportamiento cíclico. En cada ciclo, cada cola posee oportunidades de emisiones.
Los diferentes algoritmos WRR difieren en las distribuciones de estas oportunidades en el ciclo.
WRR clásico
En WRR clásico [2] [3] [4], el programador recorre las colas. Cuando una cola está seleccionado, el planificador enviará paquetes, hasta la emisión de paquete o al final de la cola.
Constantes y variables: const N // Nb de colas const weight [1..N] // peso de cada cola colas [1..N] // colas i // índice de cola c // contador de paquetes Instrucciones: mientras es verdadero, hacer para i en 1 .. N hacer c: = 0 while (no cola [i] .empty) y (c |
WRR intercalado
Dejar , sea el peso máximo. En IWRR, [1] [5] cada ciclo se divide enrondas. Una cola con peso puede emitir un paquete a la vuelta sólo si .
Constantes y variables: const N // Nb de colas const weight [1..N] // peso de cada cola const w_max colas [1..N] // colas i // índice de cola r // contador de vueltas Instrucciones: mientras que verdadero hacer para r en 1 .. w_max hacer para i en 1 .. N hacer si ( no cola [i]. vacío) y (peso [i]> = r) entonces enviar (cola [i] .head ()) cola [i] .dequeue () |
Ejemplo
Considere un sistema con tres colas y pesos respectivos . Considere una situación en la que son 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 de X, Y . Suponga que no llegan más paquetes.
Con WRR clásico, en el primer ciclo, el programador primero selecciona y transmite 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 se selecciona la tercera cola, que tiene un peso igual a 3, pero sólo 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 dese transmiten, seguidos de W desde.
Con WRR intercalado, el primer ciclo se divide en 5 rondas. 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 colas se les permite enviar un paquete, y ), pero desde está vacío, solo C dese envía, y en la cuarta y quinta rondas, solo D, E dese envían. Luego comienza el segundo ciclo, donde se envían F, W, G.
Programación de tareas
La programación de tareas o procesos se puede realizar en WRR de manera similar a la programación de paquetes: cuando se considera un conjunto de tareas activas, se programan de forma cíclica, cada tarea obtiene cuanto o porción de tiempo de procesador. [6] [7]
Propiedades
Al igual que el round robin , la programación round robin ponderada es simple, fácil de implementar, ahorra trabajo y no necesita hambre .
Al programar paquetes, si todos los paquetes tienen el mismo tamaño, entonces WRR e IWRR son una aproximación del uso compartido de procesador generalizado : [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.
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 un tamaño de paquete medio es conocido por todas las colas , 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 capacidad de enlace (con ), se puede establecer .
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 de tamaño fijo (celdas). La principal limitación de las colas de operación por turnos ponderadas es que proporciona el porcentaje correcto de ancho de banda para cada clase de servicio solo si todos los paquetes de 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 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. Eso requiere una estimación del tamaño medio del paquete, lo que hace que una buena aproximación de GPS sea difícil de lograr en la práctica con WRR. [1]
El round robin de déficit es una variación posterior de WRR que logra una mejor aproximación al GPS sin conocer el tamaño medio de paquete de cada conexión de antemano. También se introdujeron disciplinas de programación más efectivas que manejan las limitaciones mencionadas anteriormente (por ejemplo, colas equitativas ponderadas ).
Ver también
Referencias
- ↑ a b c d Katevenis, M .; Sidgiropoulos, S .; Courcoubetis, C. (1991). "Multiplexación de celdas round robin ponderada en un chip de conmutador ATM de propósito general". Revista IEEE sobre áreas seleccionadas en comunicaciones . 9 (8): 1265-1279. doi : 10.1109 / 49.105173 . ISSN 0733-8716 .
- ^ a b Chaskar, HM; Madhow, U. (2003). "Programación justa con latencia ajustable: un enfoque por turnos". Transacciones IEEE / ACM sobre redes . 11 (4): 592–601. doi : 10.1109 / TNET.2003.815290 . ISSN 1063-6692 .
- ^ 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": 667–674. doi : 10.1109 / ETFA.2006.355373 . Cite journal requiere
|journal=
( ayuda ) - ^ F. Baker; R. Pan (mayo de 2016). "2.2.2. Modelos Round-Robin". Sobre cola, marcado y descarte (informe técnico). IETF. RFC 7806.
- ^ Semeria, Chuck (2001). Apoyo a clases de servicios diferenciados: Disciplinas de programación de colas (PDF) (Informe). págs. 15-18 . Consultado el 4 de mayo de 2020 .
- ^ Beaulieu, Alain (invierno de 2017). "Sistemas operativos en tiempo real - Programación y programadores" (PDF) . Consultado el 4 de mayo de 2020 .
- ^ 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
- ^ Fall, Kevin (29 de abril de 1999). "EECS 122," Introducción a las redes de comunicación ", Clase 27," Programación del mejor esfuerzo y conexiones garantizadas " " . Consultado el 4 de mayo de 2020 .
- ^ Tabatabaee, Seyed Mohammadhossein; Le Boudec, Jean-Yves; Boyer, Marc (22-24 de septiembre de 2020). "Round-Robin ponderado intercalado: un análisis de cálculo de red" . Proc. de la 32ª Int. Congreso de Teletrafico (ITC 32) . doi : 10.1109 / ITC3249928.2020.00016 . Consultado el 14 de abril de 2021 .Mantenimiento CS1: formato de fecha ( enlace )