Hispanopedia WikiLa cola justa es una familia de algoritmos de planificación utilizados en algunos planificadores de procesos y redes . El algoritmo está diseñado para lograr equidad cuando se comparte un recurso limitado, por ejemplo, para evitar que los flujos con paquetes grandes o los procesos que generan tareas pequeñas consuman más rendimiento o tiempo de CPU que otros flujos o procesos.
La gestión equitativa de colas se implementa en algunos conmutadores y enrutadores de red avanzados .
Historia
El término cola justa fue acuñado por John Nagle en 1985 al proponer una programación round-robin en la puerta de enlace entre una red de área local e Internet para reducir la interrupción de la red causada por hosts con mal comportamiento. [ 1 ] [ 2 ] [ 3 ]
Alan Demers, Srinivasan Keshav y Scott Shenker propusieron una versión ponderada por bytes en 1989, basada en el algoritmo de cola justa de Nagle. [ 4 ] [ 5 ] El algoritmo de cola justa ponderada por bytes busca imitar la multiplexación bit a bit calculando la fecha de salida teórica para cada paquete.
El concepto se ha desarrollado aún más en el sistema de colas equitativas ponderadas y en el concepto más general de modelado del tráfico , donde las prioridades de las colas se controlan dinámicamente para lograr los objetivos de calidad de servicio de flujo deseados o acelerar algunos flujos.
Principio
El sistema de colas equitativas utiliza una cola por flujo de paquetes y las atiende de forma rotativa, de modo que cada flujo pueda "obtener una fracción igual de los recursos". [ 1 ] [ 2 ]
La ventaja sobre el sistema convencional de primero en entrar, primero en salir (FIFO) o la cola de prioridad es que un flujo de datos de alta velocidad, compuesto por paquetes grandes o muchos paquetes de datos, no puede consumir más de la parte que le corresponde de la capacidad del enlace.
El encolamiento equitativo se utiliza en enrutadores, conmutadores y multiplexores estadísticos que reenvían paquetes desde un búfer . El búfer funciona como un sistema de colas, donde los paquetes de datos se almacenan temporalmente hasta que se transmiten.
Con una velocidad de datos de enlace de R , en cualquier momento dado, los N flujos de datos activos (aquellos con colas no vacías) se procesan cada uno con una velocidad de datos promedio de R/N . En un intervalo de tiempo corto, la velocidad de datos puede fluctuar alrededor de este valor, ya que los paquetes se entregan secuencialmente.
Justicia
En el contexto de la planificación de redes, la equidad tiene múltiples definiciones. El artículo de Nagle utiliza la planificación round-robin de paquetes, [ 2 ] que es equitativa en términos del número de paquetes, pero no en cuanto al uso del ancho de banda cuando los paquetes tienen tamaños variables. Se han definido varias nociones formales de medida de equidad, incluyendo la equidad max-min , la equidad en el peor de los casos , [ 6 ] y el índice de equidad . [ 7 ]
Generalización al reparto ponderado
La idea inicial asigna la misma tasa a cada flujo. Una extensión natural consiste en permitir que el usuario especifique la porción de ancho de banda asignada a cada flujo, lo que da lugar a una cola equitativa ponderada y a un uso compartido generalizado del procesador .
Un algoritmo de cola justa ponderada por bytes
Este algoritmo intenta emular la equidad del reparto de recursos de enlace mediante el algoritmo round-robin bit a bit entre flujos concurrentes. Sin embargo, los flujos basados en paquetes deben transmitirse paquete a paquete y en secuencia. El algoritmo de cola justa ponderada por bytes selecciona el orden de transmisión de los paquetes modelando el tiempo de finalización de cada uno como si se transmitieran mediante round-robin bit a bit. El paquete con el tiempo de finalización más temprano, según este modelo, es el siguiente en ser seleccionado para su transmisión.
La complejidad del algoritmo es O(log(n)) , donde n es el número de colas/flujos.
Detalles del algoritmo
Si bien es factible modelar el tiempo real de finalización, requiere una gran capacidad de cálculo. El modelo debe recalcularse sustancialmente cada vez que se selecciona un paquete para su transmisión y cada vez que llega un nuevo paquete a cualquier cola.
Para reducir la carga computacional, se introduce el concepto de tiempo virtual . El tiempo de finalización de cada paquete se calcula en esta escala de tiempo virtual alternativa y monótonamente creciente. Si bien el tiempo virtual no modela con precisión el tiempo que tardan los paquetes en completar sus transmisiones, sí modela con precisión el orden en que deben ocurrir las transmisiones para cumplir con los objetivos del modelo completo. Al usar el tiempo virtual, no es necesario recalcular el tiempo de finalización de los paquetes previamente en cola. Aunque el tiempo de finalización, en términos absolutos, de los paquetes existentes puede verse afectado por nuevas llegadas, el tiempo de finalización en la línea de tiempo virtual permanece inalterado: la línea de tiempo virtual se deforma con respecto al tiempo real para dar cabida a cualquier nueva transmisión.
El tiempo de finalización virtual de un paquete recién agregado a la cola se obtiene sumando el tiempo de inicio virtual y el tamaño del paquete. El tiempo de inicio virtual es el valor máximo entre el tiempo de finalización virtual anterior de la misma cola y el instante actual.
Una vez calculado el tiempo de finalización virtual de todos los paquetes candidatos (es decir, los paquetes que se encuentran al inicio de todas las colas de flujo no vacías), el sistema de colas equitativa compara estos tiempos de finalización virtuales y selecciona el mínimo. El paquete con el tiempo de finalización virtual mínimo es el que se transmite.
Pseudocódigo
La función receive () se ejecuta cada vez que se recibe un paquete, y send () se ejecuta cada vez que se debe seleccionar un paquete para enviar, es decir, cuando el enlace está inactivo y las colas no están vacías. Este pseudocódigo asume que existe una función now () que devuelve el tiempo virtual actual y una función chooseQueue () que selecciona la cola donde se encola el paquete.
La función selectQueue () selecciona la cola con el tiempo de finalización virtual mínimo. Para mayor claridad, el pseudocódigo presentado aquí realiza una búsqueda lineal. Sin embargo, mantener una lista ordenada puede implementarse en tiempo logarítmico, lo que resulta en una complejidad de O(log(n)) , pero con un código más complejo.
Véase también
Referencias
- 1 2 John Nagle: "Sobre conmutadores de paquetes con almacenamiento infinito", RFC 970, IETF , diciembre de 1985.
- 1 2 3 Nagle, JB (1987). "Sobre conmutadores de paquetes con almacenamiento infinito". IEEE Transactions on Communications . 35 (4): 435– 438. CiteSeerX 10.1.1.649.5380 . doi : 10.1109/TCOM.1987.1096782 .
- ↑ Phillip Gross (enero de 1986), Actas del Grupo de Trabajo sobre Algoritmos y Estructuras de Datos de Puertas de Enlace de DARPA del 16 al 17 de enero de 1986 (PDF) , IETF , págs. 5, 98 , recuperado el 4 de marzo de 2015 ,
Nagle presentó su esquema de "colas justas", en el que las puertas de enlace mantienen colas separadas para cada host emisor. De esta manera, los hosts con implementaciones patológicas no pueden usurpar más de su parte justa de los recursos de la puerta de enlace. Esto provocó una discusión animada e interesante.
- ↑ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Análisis y simulación de un algoritmo de colas equitativo" . ACM SIGCOMM Computer Communication Review . 19 (4): 1– 12. doi : 10.1145/75247.75248 .
- ↑ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "Análisis y simulación de un algoritmo de colas equitativo" (PDF) . Interconexión de redes: investigación y experiencia . 1 : 3–26 .
- ↑ Bennett, JCR; Hui Zhang (1996). "WF/sup 2/Q: Colas justas ponderadas en el peor de los casos". Actas de IEEE INFOCOM '96. Conferencia sobre Comunicaciones Informáticas . Vol. 1. pág. 120. doi : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4. S2CID 17558577 .
- ↑ Ito, Y.; Tasaka, S.; Ishibashi, Y. (2002). "Cola round robin con ponderación variable para enrutadores IP centrales". Actas de la Conferencia Internacional de Rendimiento, Computación y Comunicaciones del IEEE (Cat. No. 02CH37326) . pág. 159. doi : 10.1109/IPCCC.2002.995147 . ISBN 978-0-7803-7371-6. S2CID 60787008 .
- Algoritmos de planificación de red