Weighted fair queueing

Weighted fair queueing, or WFQ, is a network scheduling algorithm that decides which packet a link sends next when several traffic flows compete for it. It is a packet-based implementation of the generalized processor sharing policy and a natural extension of fair queueing: where fair queueing divides the link capacity into equal parts, WFQ lets an administrator give each flow its own weight, so that a flow gets its weight divided by the sum of all weights times the link rate. It is also called packet-by-packet generalized processor sharing, because it approximates the ideal policy to within one packet transmission time whatever the arrival pattern. For each packet it computes a virtual finish time and, whenever the output link is idle, sends the packet with the smallest one. This selection gives it logarithmic complexity in the number of flows. Worst-case Fair Weighted Fair Queueing and deficit round robin are later refinements and approximations.