Fair queuing
From Wikipedia, the free encyclopedia
Fair queuing (FQ), is a scheduling scheme used in computer networks and statistical multiplexing to allow several data 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 bursts of 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 popular scheduling schemes being studied.
As a scheduling scheme, FQ is usually used in routers, switches or multiplexors 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 destined for or from a particular user or users, signified by a single or range of 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 and the number of users who are sharing the buffer. Then FQ compares the virtual finishing time and selects the minimum one. The packet with the minimum "virtual" finishing time is forwarded.
With a link data rate of R, at any given time the N active data flows (the ones with non-empty queues) are serviced simultaneously, each at an average data rate of R / N. However, in the short run the data rate may be fluctuating around this value since the packets are delivered asynchronously (in a non-repetitive order).
FQ resembles to 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. If all queues have the same weight, WFQ becomes a regular FQ.
