Weighted fair queueing

Weighted fair queueing (WFQ) is a data packet scheduling algorithm used by network schedulers. WFQ is both a packet based implementation of the generalized processor sharing policy (GPS), and a natural generalization of fair queuing (FQ): whereas FQ shares the link's capacity in equal subparts, WFQ allows to specify, for each flow, which fraction of the capacity will be given.

Weighted fair queuing (WFQ) is also known as Packet-by-Packet GPS (PGPS or P-GPS) since it approximates generalized processor sharing "to within one packet transmission time, regardless of the arrival patterns."^[1]

In WFQ, a scheduler handling $N$ flows is configured with one weight $w_{i}$ for each flow. Then, the flow of number $i$ will achieve an average data rate of ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ (where R is the link rate). A WFQ scheduler where all weights are equals is a FQ scheduler.

Like all fair-queuing schedulers, each flow is protected from the others, and it can be proven that if a data flow is leaky bucket constrained, an end-to-end delay bound can be guaranteed.^[2]

Parametrisation and Fairness

Like other GPS-like scheduling algorithm, the choice of the weights is left to the network administrator.

By regulating the WFQ weights dynamically, WFQ can be utilized for controlling the quality of service, for example to achieve guaranteed data rate.

As presented for fair queueing, there is no unique definition on what is "fair".

Proportional fairness can be achieved by setting the weights to $w_{i}=1/c_{i}$ , where $c_{i}$ is the cost per data bit of data flow $i$ . For example in CDMA spread spectrum cellular networks, the cost may be the required energy (the interference level), and in dynamic channel allocation systems, the cost may be the number of nearby base station sites that can not use the same frequency channel, in view to avoid co-channel interference.

Algorithm

The algorithm of WFQ is very similar to the one of FQ. For each packet, a virtual theoretical departure date will be computed, defined as the departure date if the scheduler was a perfect GPS scheduler. Then, each time the output link is idle, the packet with the smallest date is selected for emission.

The pseudo code can be obtained simply from the one of FQ by replacing the computation of the virtual departure time by

packet.virFinish= virStart + packet.size / Ri

with $Ri:={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ .

WFQ as a GPS approximation

WFQ, under the name PGPS, has been designed as "an excellent approximation to GPS", and its has been proved that it approximates GPS "to within one packet transmission time, regardless of the arrival patterns."^[1]

Since WFQ implementation is similar to fair queuing, is has the same O(log(n)) complexity, where n is the number of flows. This complexity comes from the need to select the queue with the smallest virtual finish time each time a packet is sent.

After WFQ, several others implementations of GPS have been defined.

Even if WFQ is a most "one packet" late w.r.t. the ideal GPS policy, it can be arbitrary ahead. The Worst-case Fair Weighted Fair Queueing (WF2Q) fixes it by adding a virtual start of service to each packet, and selects a packet only if its virtual start of service is not less than the current time.^[3]
The selection of the queue with minimal virtual finish time can be hard to implement at wire speed. Then, other approximations of GPS has been defined with smaller complexity, like deficit round robin.

History

The introduction of parameters to share the bandwidth in an arbitrary way in mentioned at the end of ^[4] as a possible extension to FQ. The term weighted first appears in.^[1]

References

^ ^a ^b ^c Parekh, A. K.; Gallager, R. G. (1993). "A generalized processor sharing approach to flow control in integrated services networks: The single-node case" (PDF). IEEE/ACM Transactions on Networking. 1 (3): 344. doi:10.1109/90.234856.
^ Stiliadis, D.; Varma, A. (1998). "Latency-rate servers: A general model for analysis of traffic scheduling algorithms" (PDF). IEEE/ACM Transactions on Networking. 6 (5): 611. doi:10.1109/90.731196.
^ Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN 0-8186-7293-5.
^ Demers, A.; Keshav, S.; Shenker, S. (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1. doi:10.1145/75247.75248.

[GPS-1] Parekh, A. K.; Gallager, R. G. (1993). "A generalized processor sharing approach to flow control in integrated services networks: The single-node case" (PDF). IEEE/ACM Transactions on Networking. 1 (3): 344. doi:10.1109/90.234856.

[2] Stiliadis, D.; Varma, A. (1998). "Latency-rate servers: A general model for analysis of traffic scheduling algorithms" (PDF). IEEE/ACM Transactions on Networking. 6 (5): 611. doi:10.1109/90.731196.

[WF2Q-3] Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN 0-8186-7293-5.

[FQ-4] Demers, A.; Keshav, S.; Shenker, S. (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1. doi:10.1145/75247.75248.

[1]

[2]

[3]

[4]

Parametrisation and Fairness

Algorithm

WFQ as a GPS approximation

History

See also

References