Colas justas y ponderadas

El algoritmo de cola justa ponderada ( WFQ ) es un algoritmo de programación de red . WFQ es a la vez una implementación basada en paquetes de la política de uso compartido generalizado de procesadores (GPS) y una extensión natural del algoritmo de cola justa (FQ). Mientras que FQ comparte la capacidad del enlace en subpartes iguales, WFQ permite a los programadores especificar, para cada flujo, qué fracción de la capacidad se asignará.

La cola justa ponderada también se conoce como GPS paquete por paquete (PGPS o P-GPS) ya que se aproxima al uso compartido generalizado del procesador "dentro de un tiempo de transmisión de paquete, independientemente de los patrones de llegada". ^[1]

Parametrización y equidad

Al igual que otros algoritmos de programación similares a GPS, la elección de los pesos queda en manos del administrador de la red. No existe una definición única de lo que es "justo" (consulte la sección Cola justa § Equidad para obtener más información).

Al regular dinámicamente los pesos de WFQ, WFQ se puede utilizar para controlar la calidad del servicio , por ejemplo, para lograr una velocidad de datos garantizada. ^{[ cita requerida ]}

Se puede lograr un comportamiento proporcionalmente justo estableciendo los pesos en , donde es el costo por bit de datos del flujo de datos . Por ejemplo, en redes celulares de espectro ensanchado CDMA , el costo puede ser la energía requerida (el nivel de interferencia), y en sistemas de asignación dinámica de canales , el costo puede ser la cantidad de sitios de estaciones base cercanos que no pueden usar el mismo canal de frecuencia, con el fin de evitar interferencias entre canales. $w_{i}=1/c_{i}$ $Estilo de visualización c_{i}}$ ${\estilo de visualización i}$

Algoritmo

En WFQ, un programador que maneja $N$ flujos se configura con un peso para cada flujo. Entonces, el flujo de número alcanzará una tasa de datos promedio de , donde es la tasa de enlace. Un programador WFQ donde todos los pesos son iguales es un programador FQ. $estilo de visualización w_{i}}$ ${\estilo de visualización i}$ ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ ${\estilo de visualización R}$

Al igual que todos los programadores de colas justas, cada flujo está protegido de los demás, y se puede demostrar que si un flujo de datos está restringido por un contenedor con fugas , se puede garantizar un límite de retraso de extremo a extremo. ^[2]

El algoritmo de WFQ es muy similar al de FQ . Para cada paquete, se calculará una fecha de salida teórica virtual, definida como la fecha de salida si el planificador fuera un planificador GPS perfecto. Luego, cada vez que el enlace de salida esté inactivo, se seleccionará para su emisión el paquete con la fecha más pequeña.

El pseudocódigo se puede obtener simplemente a partir del de FQ reemplazando el cálculo del tiempo de salida virtual por

paquete.virFinish = virStart + paquete.size / Ri

con . $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$

WFQ como aproximación GPS

WFQ, bajo el nombre de PGPS, ha sido diseñado como "una excelente aproximación al GPS", y se ha demostrado que se aproxima al GPS "con una precisión de un tiempo de transmisión de paquete, independientemente de los patrones de llegada". ^[1]

Dado que la implementación de WFQ es similar a la cola justa , tiene la misma complejidad O(log(n)) , donde n es la cantidad de flujos. Esta complejidad surge de la necesidad de seleccionar la cola con el menor tiempo de finalización virtual cada vez que se envía un paquete.

Después de WFQ, se han definido varias otras implementaciones de GPS.

Incluso si WFQ se retrasa como máximo "un paquete" con respecto a la política GPS ideal, puede adelantarse arbitrariamente. La cola justa ponderada en el peor de los casos (WF2Q) lo soluciona añadiendo un inicio de servicio virtual a cada paquete y selecciona un paquete solo si su inicio de servicio virtual no es anterior a la hora actual. ^[3]
La selección de la cola con un tiempo de finalización virtual mínimo puede ser difícil de implementar a velocidad de cable. Por ello, se han definido otras aproximaciones de GPS con menor complejidad, como el round robin deficitario .

Historia

La introducción de parámetros para compartir el ancho de banda de forma arbitraria se menciona al final de ^[4] como una posible extensión de FQ. El término ponderado aparece por primera vez en ^{[1] .}

Véase también

Referencias

^ abc Parekh, AK; Gallager, RG (1993). "Un enfoque generalizado de compartición de procesadores para el control de flujo en redes de servicios integrados: el caso de un solo nodo" (PDF) . Transacciones IEEE/ACM sobre redes . 1 (3): 344. doi :10.1109/90.234856. S2CID 52808341.
^ Stiliadis, D.; Varma, A. (1998). "Servidores de tasa de latencia: un modelo general para el análisis de algoritmos de programación de tráfico" (PDF) . IEEE/ACM Transactions on Networking . 6 (5): 611. doi :10.1109/90.731196.
^ Bennett, JCR; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Actas de IEEE INFOCOM '96. Conferencia sobre comunicaciones informáticas . Vol. 1. p. 120. doi :10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4.ID S2C 17558577.
^ Demers, A.; Keshav, S.; Shenker, S. (1989). "Análisis y simulación de un algoritmo de cola justa". ACM SIGCOMM Computer Communication Review . 19 (4): 1. doi : 10.1145/75247.75248 .