Fair Queueing Algorithm

The paper describes a fair queuing algorithm implemented at gateways
(routers) without any modification to Internet protocols. It was
written at at time when most gateways implemented First-Come First-Serve
queuing algorithms. FCFS is inappropriate because, for example, it does
not handle un-cooperative hosts which gain an unfair share of bandwidth
and promptness by disobeying flow control protocols. The authors argue
that queuing algorithms are a crucial component in effective congestion
control and that FCFS is insufficient. The algorithm also attempts to
allocate bandwidth, delay, and buffer space separately.

Three explicit objectives are defined: formulating a new fair queuing
algorithm, providing information on the performance of the algorithm,
and evaluating the algorithm in the context of real networks. One of
the central design considerations is the requirement that that bandwidth
and buffer space be allocated fairly. Controlling delay is also
desirable. The paper builds on Nagle's fair queuing algorithm by taking
into account packet lengths and explicitly taking into account
promptness. Fairness is defined using the max-min fairness criterion.
Fairness can be defined at many levels, but the paper chooses
source-destination pairs. The basic guideline chosen for regulating
delay is to give more promptness for streams which use less than their
fair share of bandwidth. This makes sense for applications such as
telnet. The algorithm is founded on a "bid formula" which determines
which packets are enqueued next by their relative bid value. The
benchmark simulation results are very encouraging: they show fair
distributions of bandwidth, control hostile users, eliminate
"winner/loser" segmentation, and reduce delays for streams which require
less bandwidth than their fair share. FQ is even more effective when
combined with other congestion avoidance algorithms.

The paper is well presented with the exception of some of the
mathematical derivations which distract the reader from quickly
absorbing the properties of the new algorithm. Additionally, the paper
neglected to model the effects of dynamic routing or to prove what
happens in a network of FQ gateways. I think it's interesting how the
authors have to motivate the need for gateways to handle un-cooperative
users, it is clear that the paper was written at a time when the
Internet had not yet been disrupted by abusive users on a large scale.
Received on Thu Sep 28 2006 - 00:45:05 EDT