Fair queuing
From Wikipedia, the free encyclopedia
Fair queuing (FQ), is a scheduling scheme used in computer networks and statistical multiplexing to allow several packet flows to fairly share the link capacity. The advantage over conventional first in first out (FIFO) queuing, is that an ill-behaved flow, consisting of large data packets or unfairly many packets, will only punish itself and not other flows. FQ can be interpreted as a packet approximation of Generalized Processor Sharing (GPS). Since it was proposed by John Nagle [1][2] in 1985 it has been one of the most studied scheduling schemes.
[edit] Algorithm
FQ is used in routers, switches or multiplexers that forward packets from a buffer. The buffer works as a queuing system, where the data packets are stored temporarily until they are sent out. 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 or destination IP addresses. In order to decide which packet should be forwarded first, FQ estimates a virtual finishing time of all candidate packets (i.e., the packets at the head of all non-empty queues) based on the arrival time of the packet, the packet size, and the number of queues. Then FQ compares the virtual finishing time and selects the minimum one. The packet with the minimum virtual finishing time is forwarded.
[edit] Properties
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. However, in a short time interval the data rate may be fluctuating around this value since the packets are delivered sequentially.
FQ resembles round-robin scheduling, but in the latter case the average data rate that a flow achieves is affected by the data packet size.
FQ 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.
A weighted version of FQ is called weighted fair queuing (WFQ). Sometimes people also call WFQ FQ in short. Regular FQ is a special case of WFQ for equal weights of the queues.
