Weighted fair queuing
Encyclopedia
Weighted fair queuing is a data packet scheduling
technique allowing different scheduling priorities to statistically multiplexed
data flows
.
WFQ is a generalization of fair queuing (FQ). Both in WFQ and FQ, each data flow has a separate FIFO
queue. In FQ, with a link data rate of
, at any given time the 
active data flows (the ones with non-empty queues) are serviced simultaneously, each at an average data rate of 
. Since each data flow has its own queue, an ill-behaved flow (who has sent larger packets or more packets per second than the others since it became active) will only punish itself and not other sessions.
Contrary to FQ, WFQ allows different sessions to have different service shares. If
data flows currently are active, with weights 
data flow number 
will achieve an average data rate of
It can be proven that when using a network with WFQ switches and a data flow that is leaky bucket
constrained, an end-to-end delay bound can be guaranteed. By regulating the WFQ weights dynamically, WFQ can be utilized for controlling the quality of service
, for example to achieve guaranteed data rate.
Proportional fairness can be achieved by setting the weights to
, where 
is the cost per data bit of data flow 
. 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.
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
technique allowing different scheduling priorities to statistically multiplexed
Statistical multiplexing
Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation . In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bit-rate digital channels or data streams. The link sharing is adapted to the...
data flows
Flow (computer networking)
In packet switching networks, traffic flow, packet flow or network flow is a sequence of packets from a source computer to a destination, which may be another host, a multicast group, or a broadcast domain...
.
WFQ is a generalization of fair queuing (FQ). Both in WFQ and FQ, each data flow has a separate FIFO
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
queue. In FQ, with a link data rate of
, at any given time the active data flows (the ones with non-empty queues) are serviced simultaneously, each at an average data rate of . Since each data flow has its own queue, an ill-behaved flow (who has sent larger packets or more packets per second than the others since it became active) will only punish itself and not other sessions.Contrary to FQ, WFQ allows different sessions to have different service shares. If
data flows currently are active, with weights data flow number will achieve an average data rate ofIt can be proven that when using a network with WFQ switches and a data flow that is leaky bucket
Leaky bucket
The leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions conform to defined limits on bandwidth and burstiness . The leaky bucket algorithm is also used in leaky bucket counters, e.g...
constrained, an end-to-end delay bound can be guaranteed. By regulating the WFQ weights dynamically, WFQ can be utilized for controlling the quality of service
Quality of service
The quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...
, for example to achieve guaranteed data rate.
Proportional fairness can be achieved by setting the weights to
, where is the cost per data bit of data flow . For example in CDMA spread spectrum cellular networks, the cost may be the required energy (the interference level), and in dynamic channel allocationChannel allocation schemes
In radio resource management for wireless and cellular network, channel allocation schemes are required to allocate bandwidth and communication channels to base stations, access points and terminal equipment...
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.
See also
- Statistical multiplexingStatistical multiplexingStatistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation . In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bit-rate digital channels or data streams. The link sharing is adapted to the...
- Computing scheduling disciplines
- Scheduling algorithm
- Deficit round robinDeficit round robinDeficit round robin , also deficit weighted round robin , is a modified weighted round robin scheduling discipline. DRR was proposed by M. Shreedhar and G. Varghese in 1995. It can handle packets of variable size without knowing their mean size...
- Weighted round robinWeighted round robinWeighted round robin is a scheduling discipline. Each packet flow or connection has its own packet queue in a network interface card. It is the simplest approximation of generalized processor sharing...
- Fair Queuing
- Max-min fairnessMax-min fairnessIn communication networks and multiplexing, a division of the bandwidth resources is said to be max-min fair when: firstly, the minimum data rate that a dataflow achieves is maximized; secondly, the second lowest data rate that a dataflow achieves is maximized, etc.In best-effort statistical...
- Proportional fairness