Analysis and Simulation of a Fair Queueing Algorithm

Paper Review: Analysis and Simulation of a Fair Queueing Algorithm

The paper presents a fair queueing algorithm based on an earlier work
by Nagle. The algorithm is said to provide fair bandwidth allocation,
protection from malicious sources and low delay for sources using less
than their share of bandwidth which makes it supposedly more
attractive than simple FCFS queueing.

Queueing algorithms are often ignored when discussing congestion
avoidance schemes, however, they do determine the way in which packets
from different sources affect the collective operation of flow control
algorithms. Queueing algorithms attempt to allocate three quantities:
bandwidth, promptness and buffer space. With FCFS, the most common
queueing algorithm, the order of packet arrival determines allocation
of the three quantities.

Nagle proposed a fair queueing algorithm in which gateways maintained
a separate queue for packets from each individual source which were
then serviced in a round-robin fashion. When a source sends too many
packets, it suffers since its own queue grows.

The paper then moves into its three objectives:
- to describe a new fair queueing algorithm
- provide understanding of the performance of the algorithm
- evaluate the new queueing algorithm in the context of real networks

The new algorithm attempts to improve on the flaws found in Nagle?s
original idea. Nagle?s fair queueing considered packets rather than
data and thus ignored packet lengths. A source using long packets
could obtain more bandwidth. The paper describes a scheme which
emulates a theoretical bit-by-bit round robin scheduler. Also in the
new scheme, more promptness is allocated to users who utilize less
than their share of bandwidth. Hosts are penalized for throughput
that is wasted due to poor flow control.

In the analysis, the authors use two types of sources: FTP-like with
packets always ready and Telnet-like with intermittent packets. The
section describing the fair queueing seems to be unclear and perhaps
requires further explanation.

The authors then provide simulation results based on benchmark
scenarios, which are unrealistic but are chosen to illuminate certain
facets of their algorithm. They measure for throughput, average rtt,
number of retransmissions and number of dropped packets. They
simulate an underloaded gateway, overloaded gateway, ill-behaved
source, mixed protocols, multihop path and complicated network

They conclude by discussing the simulation results which seem to
generally indicate that fair queueing improves performance and allows
for independent tuning of bandwidth, promptness and buffer space.
However the concluding remarks leave the reader with a less than
promising outlook. The authors state that fair queueing may require
gateways which are both ?smart? and ?fast? and are unsure whether the
technology exists to make these new gateways operate at bandwidths
comparable to fiber and if they do whether or not it is economically
feasible. At the same time it?s a new idea and something to consider
since it brings up the notion of implementing more complex decision
making in gateways. Although this seems to violate the end-to-end
argument, certain congestion avoidance mechanisms, perhaps, may only
be logically implemented in the gateways as there is a limit on the
amount of useful information the end-systems can obtain from the
network.

-- Nadeem Abji
Received on Thu Sep 28 2006 - 04:32:35 EDT