Fair queuing

Fair queuing is a scheduling algorithm used in computer and telecommunications networks to allow multiple packet flows to fairly share the link capacity. The advantage over conventional first in first out (FIFO) queuing is that a high-data-rate flow, consisting of large or many data packets, cannot take more than its fair share of the link capacity. Fair queuing can be interpreted as a packet approximation of generalized processor sharing (GPS). It was proposed by John Nagle in 1985 [John Nagle: [http://www.rfc-archive.org/getrfc.php?rfc=970 "On packet switches with infinite storage,"] RFC 970, IETF, December 1985.] [John Nagle: [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1096782&isnumber=24018 "On packet switches with infinite storage."] IEEE Transactions on Communications, 35(4):435–438, April 1987.] and has since been one of the most studied scheduling algorithms.

Properties

Fair queuing is used in routers, switches, and statistical multiplexers that forward packets from a buffer. The buffer works as a queuing system, where the data packets are stored temporarily until they are transmitted. The buffer space is divided into many queues, each of which is used to hold the packets of one flow, defined for instance by source and destination IP addresses.

With a link data-rate of "R", at any given time the "N" active data flows (the ones with non-empty queues) are serviced each with an average data rate of "R" / "N". In a short time interval the data rate may be fluctuating around this value since the packets are delivered sequentially.

Fair queuing achieves max-min fairness, i.e., its first priority is to maximize the minimum data rate that any of the active data flows experiences, the second priority is to maximize the second minimum data rate, etc. This results in lower throughput (lower system spectrum efficiency in wireless networks) than maximum throughput scheduling, but scheduling starvation of expensive flows is avoided. In contrast to round-robin scheduling, fair queuing takes into account data packet sizes to ensure each flow is given equal opportunity to transmit an equal amount of data. A weighted version of fair queuing is called weighted fair queuing (sometimes referred to as fair queuing). Weighting is achieved by multiplying the packet size considered by the fair queuing algorithm with the inverse of a weight for the associated queue. Fair queuing is a special case of weighted fair queuing with equal weights for all queues.

Algorithm

Fair queuing attempts to emulate the fairness of bitwise round-robin sharing of link resources among competing flows. Packet-based flows, however, must be transmitted packetwise and in sequence. Fair queuing selects transmission order for the packets by modeling finish time for each packet as if they could be transmitted bitwise round robin. The packet with the earliest finish time according to this modeling is the next selected for transmission.

Modeling of actual finish time, while feasible, is computationally intensive. The model needs to be substantially recomputed every time a packet is selected for transmission and every time a new packet arrives into any queue.

To reduce computational load, the concept of "virtual time" is introduced. Finish time for each packet is computed on this alternate monotonically increasing virtual timescale. While virtual time does not accurately model the time packets complete their transmissions, it does accurately model the order in which the transmissions must occur to meet the objectives of the full-featured model. Using virtual time, it is unnecessary to recompute finish time for previously queued packets. Although finish time, in absolute terms, for existing packets is potentially affected by new arrivals, finish time on the virtual time line is unchanged - the virtual time line warps with respect to real time to accommodate any new transmission.

The virtual finish time for a newly queued packet is given by the finish time of the packet queued ahead of it for its flow plus its own size. If there are no packets queued for the flow, the virtual finish time is given by current virtual time plus the packet's size where current virtual time is the assigned virtual finish time for the packet which most recently completed transmission plus progress on the current transmission (if any).

With a virtual finishing time of all candidate packets (i.e., the packets at the head of all non-empty flow queues) computed, fair queuing compares the virtual finishing time and selects the minimum one. The packet with the minimum virtual finishing time is transmitted.

References

See also

* Scheduling (computing)
* Scheduling algorithm
* Max-min fairness
* Weighted fair queuing
* Deficit round robin
* Weighted round robin
* Statistical multiplexing