Las colas justas son una familia de algoritmos de programación utilizados en algunos programadores de procesos y redes . El algoritmo está diseñado para lograr equidad cuando se comparte un recurso limitado, por ejemplo, para evitar que flujos con paquetes grandes o procesos que generan trabajos pequeños consuman más rendimiento o tiempo de CPU que otros flujos o procesos.
La cola justa se implementa en algunos conmutadores y enrutadores de red avanzados .
El término cola justa fue acuñado por John Nagle en 1985 al proponer una programación por turnos en la puerta de enlace entre una red de área local e Internet para reducir la interrupción de la red provocada por hosts que se comportan mal. [1] [2] [3]
Alan Demers, Srinivasan Keshav y Scott Shenker propusieron una versión ponderada por bytes en 1989, y se basó en el anterior algoritmo de cola justa de Nagle. [4] [5] El algoritmo de cola justa ponderado por bytes tiene como objetivo imitar una multiplexación bit por bit calculando la fecha de salida teórica de cada paquete.
El concepto se ha desarrollado aún más en colas justas ponderadas y el concepto más general de configuración del tráfico , donde las prioridades de las colas se controlan dinámicamente para lograr los objetivos de calidad de servicio del flujo deseado o acelerar algunos flujos.
Las colas justas utilizan una cola por flujo de paquetes y las atienden en rotación, de modo que cada flujo pueda "obtener una fracción igual de los recursos". [1] [2]
La ventaja sobre el primero en entrar, primero en salir (FIFO) o las colas de prioridad es que un flujo de alta velocidad de datos, que consiste en paquetes grandes o muchos paquetes de datos, no puede tomar más que su parte justa de la capacidad del enlace.
Las colas justas se utilizan en enrutadores, conmutadores y multiplexores estadísticos que reenvían paquetes desde un búfer . El buffer funciona como un sistema de cola, donde los paquetes de datos se almacenan temporalmente hasta su transmisión.
Con una velocidad de datos de enlace de R , en cualquier momento dado los N flujos de datos activos (los que tienen colas no vacías) reciben servicio, cada uno de ellos con una velocidad de datos promedio de R/N . En un breve intervalo de tiempo, la velocidad de datos puede fluctuar alrededor de este valor, ya que los paquetes se entregan secuencialmente por turnos.
En el contexto de la programación de redes, la equidad tiene múltiples definiciones. El artículo de Nagel utiliza la programación de paquetes por turnos , [2] lo cual es justo en términos del número de paquetes, pero no en el uso del ancho de banda cuando los paquetes tienen diferentes tamaños. Se han definido varias nociones formales de medida de equidad , incluida la equidad máxima-mínima , la equidad en el peor de los casos , [6] y el índice de equidad . [7]
La idea inicial da a cada flujo el mismo caudal. Una extensión natural consiste en permitir al usuario especificar la porción de ancho de banda asignada a cada flujo, lo que lleva a una cola justa ponderada y a un uso compartido generalizado del procesador .
Este algoritmo intenta emular la equidad del intercambio bit a bit de recursos de enlace entre flujos en competencia. Sin embargo, los flujos basados en paquetes deben transmitirse por paquetes y en secuencia. El algoritmo de cola justa ponderado por bytes selecciona el orden de transmisión de los paquetes modelando el tiempo de finalización de cada paquete como si pudieran transmitirse por turnos bit a bit. El paquete con el tiempo de finalización más temprano según este modelo es el siguiente seleccionado para transmisión.
La complejidad del algoritmo es O(log(n)) , donde n es el número de colas/flujos.
El modelado del tiempo de finalización real, si bien es factible, requiere un uso intensivo de recursos computacionales. El modelo debe recalcularse sustancialmente cada vez que se selecciona un paquete para 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 que aumenta monótonamente. Si bien el tiempo virtual no modela con precisión el tiempo en que los paquetes completan sus transmisiones, sí modela con precisión el orden en que deben ocurrir las transmisiones para cumplir los objetivos del modelo con todas las funciones. Al utilizar el tiempo virtual, no es necesario volver a calcular el tiempo de finalización de los paquetes previamente en cola. Aunque el tiempo de finalización, en términos absolutos, para los paquetes existentes se ve potencialmente afectado por las nuevas llegadas, el tiempo de finalización en la línea de tiempo virtual no cambia: la línea de tiempo virtual se deforma con respecto al tiempo real para adaptarse a cualquier nueva transmisión.
El tiempo de finalización virtual para un paquete recién puesto en cola viene dado por la suma del tiempo de inicio virtual más el tamaño del paquete. El tiempo de inicio virtual es el máximo entre el tiempo de finalización virtual anterior de la misma cola y el instante actual.
Con un tiempo de finalización virtual de todos los paquetes candidatos (es decir, los paquetes al principio de todas las colas de flujo no vacías) calculado, la cola justa compara el tiempo de finalización virtual y selecciona el mínimo. Se transmite el paquete con el tiempo mínimo de finalización virtual.
La función recibir () se ejecuta cada vez que se recibe un paquete, y enviar () se ejecuta cada vez que se debe seleccionar un paquete a enviar, es decir, cuando el enlace está inactivo y las colas no están vacías. Este pseudocódigo supone que hay una función ahora () que devuelve la hora virtual actual y una función elegirQueue () que selecciona la cola donde se pone el paquete.
La función selectQueue () selecciona la cola con el tiempo de finalización virtual mínimo. Para facilitar la lectura, el pseudocódigo presentado aquí realiza una búsqueda lineal. Pero mantener una lista ordenada se puede implementar en tiempo logarítmico, lo que lleva a una complejidad O(log(n)) , pero con código más complejo.
Nagle presentó su "cola justa" esquema, en el que las puertas de enlace mantienen colas separadas para cada host de envío. De esta manera, los anfitriones con implementaciones patológicas no pueden usurpar más que su parte justa de los recursos de la puerta de enlace. Esto suscitó un debate animado e interesado.