La cola justa es una familia de algoritmos de programación que se utilizan 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 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 enrutadores y conmutadores 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 las interrupciones de la red causadas por hosts con mal comportamiento. [1] [2] [3]
Alan Demers, Srinivasan Keshav y Scott Shenker propusieron una versión ponderada por bytes en 1989, que se basaba en el algoritmo de cola justa de Nagle anterior. [4] [5] El algoritmo de cola justa ponderado por bytes tiene como objetivo imitar una multiplexación bit a bit calculando la fecha de salida teórica de cada paquete.
El concepto se ha desarrollado aún más hasta convertirse en colas justas ponderadas y en el concepto más general de modelado de 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.
La cola justa utiliza una cola por flujo de paquetes y los atiende en rotación, 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 cola de prioridad es que un flujo de alta velocidad de datos, que consiste en paquetes grandes o muchos paquetes de datos, no puede ocupar más que su parte justa de la capacidad del enlace.
La cola justa 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) son atendidos 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 uno por uno.
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] que es justa en términos de la cantidad de paquetes, pero no en el uso del ancho de banda cuando los paquetes tienen un tamaño variable. Se han definido varias nociones formales de medida de equidad , incluidas la equidad máxima-mínima , la equidad en el peor de los casos , [6] y el índice de equidad . [7]
La idea inicial es otorgar a cada flujo la misma velocidad. Una extensión natural consiste en permitir al usuario especificar la porción de ancho de banda asignada a cada flujo, lo que conduce a una cola de espera equitativa ponderada y a un uso compartido generalizado del procesador .
Este algoritmo intenta emular la equidad de la compartición de recursos de enlace entre flujos en competencia mediante un método de intercambio de bits. Sin embargo, los flujos basados en paquetes deben transmitirse en forma de paquetes y en secuencia. El algoritmo de cola justa ponderada por bytes selecciona el orden de transmisión de los paquetes mediante el modelado del tiempo de finalización de cada paquete como si pudieran transmitirse mediante un método de intercambio de bits. El paquete con el tiempo de finalización más temprano según este modelado es el siguiente que se selecciona para la transmisión.
La complejidad del algoritmo es O(log(n)) , donde n es el número de colas/flujos.
Si bien es posible, el modelado del tiempo de finalización real requiere un gran esfuerzo computacional. Es necesario volver a calcular el modelo 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 alternada que aumenta de forma monótona. 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 con 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 que se habían puesto en cola anteriormente. Si bien el tiempo de finalización, en términos absolutos, de 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 de un paquete recién puesto en cola se obtiene sumando el 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.
Una vez calculado el tiempo de finalización virtual de todos los paquetes candidatos (es decir, los paquetes que encabezan todas las colas de flujo no vacías), la cola justa compara el tiempo de finalización virtual y selecciona el mínimo. Se transmite el paquete con el tiempo de finalización virtual mínimo.
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 para enviar, es decir , cuando el enlace está inactivo y las colas no están vacías. Este pseudocódigo supone que existe una función now () que devuelve el tiempo virtual actual, y una función chooseQueue () que selecciona la cola donde se encuentra encolado 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 que se presenta aquí realiza una búsqueda lineal. Sin embargo, el mantenimiento de una lista ordenada se puede implementar en tiempo logarítmico, lo que genera una complejidad O(log(n)) , pero con un código más complejo.
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ó un debate animado e interesado.