Weighted fair queueing (WFQ) is a
network scheduling
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an Arbiter (electronics), arbiter on a Node (networking), node in a packet switching communication network. It manages the sequence of netwo ...
algorithm. WFQ is both a packet-based implementation of the
generalized processor sharing Generalized processor sharing (GPS) is an ideal scheduling algorithm for scheduling (computing), process schedulers and network schedulers. It is related to the Fair queuing#FQ Principle, fair-queuing principle which groups packets into classes and ...
(GPS) policy, and a natural extension of
fair queuing (FQ). Whereas FQ shares the link's capacity in equal subparts, WFQ allows schedulers to specify, for each flow, which fraction of the capacity will be given.
Weighted fair queuing 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."
Parametrization and fairness
Like other GPS-like scheduling algorithms, the choice of the weights is left to the network administrator. There is no unique definition of what is "fair" (see for further discussion).
By regulating the WFQ weights dynamically, WFQ can be utilized for controlling the
quality of service
Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...
, for example, to achieve guaranteed data rate.
Proportionally fair
Proportional-fair scheduling is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize total throughput of the network (wired or not) while at the same time allowing all ...
behavior can be achieved by setting the weights to
, where
is the cost per data bit of data flow
. For example in
CDMA
Code-division multiple access (CDMA) is a channel access method used by various radio communication technologies. CDMA is an example of multiple access, where several transmitters can send information simultaneously over a single communication ...
spread spectrum cellular networks, the cost may be the required energy (the interference level), and in
dynamic channel allocation
In radio resource management for wireless and cellular networks, channel allocation schemes allocate bandwidth and communication channels to base stations, access points and terminal equipment. The objective is to achieve maximum system spectral e ...
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
In WFQ, a scheduler handling flows is configured with one weight
for each flow. Then, the flow of number
will achieve an average data rate of
, where
is the link rate. A WFQ scheduler where all weights are equal is a FQ scheduler.
Like all fair-queuing schedulers, each flow is protected from the others, and it can be proved that if a data flow is
leaky bucket
The leaky bucket is an algorithm based on an analogy of how a bucket with a constant leak will overflow if either the average rate at which water is poured in exceeds the rate at which the bucket leaks or if more water than the capacity of the ...
constrained, an end-to-end delay bound can be guaranteed.
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
.
WFQ as a GPS approximation
WFQ, under the name PGPS, has been designed as "an excellent approximation to GPS", and it has been proved that it approximates GPS "to within one packet transmission time, regardless of the arrival patterns."
Since WFQ implementation is similar to
fair queuing, it 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 other implementations of GPS have been defined.
* Even if WFQ is at most "one packet" late w.r.t. the ideal GPS policy, it can be arbitrarily 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.
* The selection of the queue with minimal virtual finish time can be hard to implement at wire speed. Then, other approximations of GPS have been defined with less complexity, like
deficit round robin
Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) poli ...
.
History
The introduction of parameters to share the bandwidth in an arbitrary way in mentioned at the end of
as a possible extension to FQ. The term ''weighted'' first appears in.
See also
*
Deficit round robin
Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) poli ...
*
Fairness measure Fairness measures or metrics are used in network engineering to determine whether users or applications are receiving a fair share of system resources. There are several mathematical and conceptual definitions of fairness.
TCP fairness
Congestion ...
*
Max-min fairness
In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessari ...
*
Scheduling algorithm
In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows.
The scheduling activity is c ...
*
Statistical time division multiplexing
Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation (DBA). In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bitrate digital channels or ...
*
Weighted round robin
Weighted round robin (WRR) is a network scheduler for data flows, but also used to schedule processes.
Weighted round robin is a generalisation of round-robin scheduling. It serves a set of queues or tasks. Whereas round-robin cycles over the ...
References
{{reflist
Network scheduling algorithms
Fair division protocols