Las colas equitativas son una familia de algoritmos de programación que se utilizan en algunos programadores de procesos y redes . El algoritmo está diseñado para lograr la 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 puesta en cola justa 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 la 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 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 equitativa ponderada por bytes tiene como objetivo imitar una multiplexación bit por bit calculando la fecha de salida teórica para cada paquete.
El concepto se ha desarrollado aún más en colas equitativas 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 la calidad de flujo deseada de los objetivos de servicio o acelerar algunos flujos.
Principio
La puesta en cola justa utiliza una cola por flujo de paquetes y los atiende en rotación, de modo que cada flujo puede "obtener una fracción igual de los recursos". [1] [2]
La ventaja sobre el primero en entrar, primero en salir (FIFO) convencional o la 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 cola, donde los paquetes de datos se almacenan temporalmente hasta que se transmiten.
Con una tasa de datos de enlace de R , en cualquier momento dado la N flujos de datos activa (los que tienen colas no vacías) se limpian cada uno con una velocidad de datos promedio de R / N . En un intervalo de tiempo corto, la tasa de datos puede fluctuar alrededor de este valor, ya que los paquetes se entregan secuencialmente por turno.
Justicia
En el contexto de la programación de la red, 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 tamaños variables. Varios nociones formales de medida equidad se han definido incluyendo max-min equidad , peor de los casos equidad , [6] y índice de justicia . [7]
Generalización para compartir ponderado
La idea inicial le da a cada flujo el mismo ritmo. Una extensión natural consiste en permitir que el usuario especifique la porción de ancho de banda asignada a cada flujo, lo que conduce a una cola justa ponderada y a un procesador compartido generalizado .
Un algoritmo de cola justa ponderado por bytes
Este algoritmo intenta emular la equidad del intercambio de recursos de enlace por turnos bit a bit de los recursos de enlace entre los flujos en competencia. Sin embargo, los flujos basados en paquetes deben transmitirse por paquetes y en secuencia. El algoritmo de puesta en cola equitativa ponderada 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 la transmisión.
La complejidad del algoritmo es O (log (n)) , donde n es el número de colas / flujos.
Detalles del algoritmo
El modelado del tiempo de finalización real, si bien es factible, es computacionalmente intensivo. Es necesario volver a calcular sustancialmente 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 alternativa que aumenta monótonamente. Si bien el tiempo virtual no modela con precisión los paquetes de tiempo que completan sus transmisiones, modela con precisión el orden en el que deben ocurrir las transmisiones para cumplir con los objetivos del modelo con todas las funciones. Con el tiempo virtual, no es necesario volver a calcular el tiempo de finalización de los paquetes en cola previamente. 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. La hora de inicio virtual es el máximo entre la hora 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 a la cabeza de todas las colas de flujo no vacías) calculado, la puesta en 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.
Pseudocódigo
Variables compartidas const N // Nb de colas colas [1..N] // colas lastVirFinish [1..N] // último instante de finalización virtual | |
recibir (paquete) queueNum: = chooseQueue (paquete) colas [queueNum] .enqueue (paquete) updateTime (paquete, queueNum) | updateTime (paquete, queueNum) // virStart es el inicio virtual del servicio virStart: = max (ahora (), lastVirFinish [queueNum]) packet.virFinish: = packet.size + virStart lastVirFinish [queueNum]: = paquete.virFinish |
enviar() queueNum: = selectQueue () paquete: = colas [queueNum] .dequeue () paquete de devolución | selectQueue () es: = 1 minVirFinish = mientras que ≤ N hacer cola: = colas [it] si no es queue.empty y queue.head.virFinish |
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 asume que hay una función now () que devuelve el tiempo virtual actual, y una función chooseQueue () que selecciona la cola donde se coloca el paquete.
La función selectQueue () selecciona la cola con el tiempo de finalización virtual mínimo. En aras de la legibilidad, 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 un código más complejo.
Ver también
Referencias
- ^ a b John Nagle: "En conmutadores de paquetes con almacenamiento infinito", RFC 970, IETF , diciembre de 1985.
- ↑ a b c Nagle, JB (1987). "En conmutadores de paquetes con almacenamiento infinito". Transacciones IEEE sobre comunicaciones . 35 (4): 435–438. CiteSeerX 10.1.1.649.5380 . doi : 10.1109 / TCOM.1987.1096782 .
- ^ Phillip Gross (enero de 1986), Proceedings of the 16-17 de enero de 1986 DARPA Gateway Algorithms and Data Structures Task Force (PDF) , IETF , págs. 5, 98 , consultado el 4 de marzo de 2015 ,
Nagle presentó su esquema de "cola justa" , en el que las puertas de enlace mantienen colas separadas para cada host de envío. De esta manera, los hosts con implementaciones patológicas no pueden usurpar más que su parte justa de los recursos de la puerta de enlace. Esto provocó una discusión animada e interesada.
- ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Análisis y simulación de un algoritmo de colas justas". Revisión de comunicación informática ACM SIGCOMM . 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 cola justa" (PDF) . Internetworking: investigación y experiencia . 1 : 3-26.
- ^ Bennett, JCR; Hui Zhang (1996). "WF / sup 2 / Q: colas equitativas ponderadas en el peor de los casos". Actas de IEEE INFOCOM '96. Conferencia sobre Comunicaciones Informáticas . 1 . pag. 120. doi : 10.1109 / INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.
- ^ Ito, Y .; Tasaka, S .; Ishibashi, Y. (2002). "Colas de operación por turnos con ponderación variable para enrutadores IP principales". Actas de la conferencia de la IEEE International Performance, Computing, and Communications Conference (Cat. No.02CH37326) . pag. 159. doi : 10.1109 / IPCCC.2002.995147 . ISBN 978-0-7803-7371-6.