La 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 de las colas justas (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 entregará.
La cola justa ponderada también se conoce como GPS paquete por paquete (PGPS o P-GPS), ya que aproxima el uso compartido generalizado del procesador "dentro del tiempo de transmisión de un paquete, independientemente de los patrones de llegada". [1]
Al igual que otros algoritmos de programación similares a GPS, la elección de los pesos se deja en manos del administrador de la red. No existe una definición única de lo que es "justo" (consulte 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 necesaria ]
Se puede lograr un comportamiento proporcionalmente justo estableciendo los pesos en , donde está el costo por bit de datos del flujo de datos . Por ejemplo, en las redes celulares de espectro ensanchado CDMA , el costo puede ser la energía requerida (el nivel de interferencia), y en los sistemas de asignación dinámica de canales , el costo puede ser la cantidad de sitios de estaciones base cercanas que no pueden usar el mismo canal de frecuencia. para evitar interferencias cocanal.
En WFQ, un programador que maneja N flujos está configurado con un peso para cada flujo. Entonces, el flujo de números alcanzará una velocidad de datos promedio de , donde está la velocidad de enlace. Un programador WFQ donde todos los pesos son iguales es un programador FQ.
Como todos los programadores de colas justas, cada flujo está protegido de los demás y se puede demostrar que si un flujo de datos tiene restricciones de depósito con fugas , se puede garantizar un límite de retraso de un extremo a otro. [2]
El algoritmo de WFQ es muy similar al de FQ . Para cada paquete se computará 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 selecciona para emisión el paquete con la fecha más pequeña.
El pseudocódigo se puede obtener simplemente del de FQ reemplazando el cálculo de la hora de salida virtual por
paquete.virFinish = virStart + paquete.tamaño / Ri
con .
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 "dentro del tiempo de transmisión de un 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 el número 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.
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]
