La cola equitativa ponderada ( WFQ ) es un algoritmo de programación de red . WFQ es tanto una implementación basada en paquetes de la política de uso compartido de procesadores generalizados (GPS) como una extensión natural de la 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 dará.
La cola equitativa 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 del tiempo de transmisión de un paquete, independientemente de los patrones de llegada". [1]
Parametrización y equidad
Al igual que otros algoritmos de programación similares al GPS, la elección de los pesos se deja al administrador de la red. No existe una definición única de lo que es "justo" (consulte Colas justas § Equidad para una discusión más detallada).
Al regular los pesos de WFQ de forma dinámica, 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, dónde es 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 el número de sitios de estaciones base cercanas que no pueden usar el mismo canal de frecuencia, en vista para evitar interferencias co-canal.
Algoritmo
En WFQ, un programador que maneja N flujos se configura con un pesopara cada flujo. Entonces, el flujo del número alcanzará una tasa de datos promedio de , dónde es la tasa de enlace. Un programador WFQ donde todos los pesos son iguales es un programador FQ.
Como todos los programadores de colas equitativas, cada flujo está protegido de los demás, y se puede demostrar que si un flujo de datos está restringido por un 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 calculará una fecha de salida teórica virtual, definida como la fecha de salida si el programador era un programador GPS perfecto. Luego, cada vez que el enlace de salida está inactivo, se selecciona para su 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
packet.virFinish = virStart + packet.size / Ri
con .
WFQ como aproximación de GPS
WFQ, bajo el nombre 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 proviene 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 está a lo sumo "un paquete" retrasado con respecto a la política de GPS ideal, puede adelantarse arbitrariamente. La cola equitativa ponderada justa en el peor de los casos (WF2Q) lo corrige agregando un inicio de servicio virtual a cada paquete y selecciona un paquete solo si su inicio de servicio virtual no es menor que el tiempo actual. [3]
- La selección de la cola con un tiempo de acabado virtual mínimo puede ser difícil de implementar a la velocidad del cable. Luego, se han definido otras aproximaciones de GPS con menor complejidad, como el round robin de déficit .
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 primero en. [1]
Ver también
Referencias
- ^ a b c Parekh, AK; Gallager, RG (1993). "Un enfoque de uso compartido de procesador generalizado 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 .
- ^ 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) . Transacciones IEEE / ACM sobre redes . 6 (5): 611. doi : 10.1109 / 90.731196 .
- ^ 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.
- ^ Demers, A .; Keshav, S .; Shenker, S. (1989). "Análisis y simulación de un algoritmo de colas justas". Revisión de comunicación informática ACM SIGCOMM . 19 (4): 1. doi : 10.1145 / 75247.75248 .