Review: Analysis and Simulation of a Fair Queueing Algorithm

Paper: Analysis and Simulation of a Fair Queueing Algorithm

Name: Robert Danek.
Course: CS2209, Fall '06.

    This paper highlights the drawbacks of regular FCFS
(first-come-first-served) queueing algorithms in gateways, and proposes
a Fair Queueing algorithm that is a modification of Nagle's algorithm.

    One of the main drawbacks with FCFS algorithms is that they do not
allocate bandwidth fairly. If some malicious host decides to send lots
of data into the network, it can gain more bandwidth on the network
compared to other hosts.

    To resolve this problem, Nagle came up with an algorithm in which
sources are maintained in separate queues in a gateway. Packets, upon
arrival, are added to the appropriate queue. Choosing which packet to
send next is done in a round-robin fashion across the different queues.
Unfortunately, this scheme still provides an unfair amount of bandwidth
to hosts that use large packets.

    One of the things that the paper struggles with is defining who is a
"user" of a network. In order to allocate bandwidth fairly to users, one
first must know who the "users" are. The alternatives suggested include
defining the user as: the sender, individual processes running in the
sender, or the source-destination pair. All of these schemes have
drawbacks, and the paper settles on defining a user as a
source-destination pair (a "conversation", as they call it).

    The paper goes on to provide a modification to Nagle's algorithm
that fixes the issue it has with large packet sizes. In the idealized
algorithm the authors present, called "Bit-by-bit round robin" (BR), one
bit is sent at a time from each queue, selecting the next bit to send in
a round-robin fashion. The authors present a variant of this scheme to
make it more realistic, since bit-by-bit round-robin would not work in
practice.

    The authors perform a number of simulations on their algorithm.
These simulations are done across a number of different "benchmark"
scenarios. As the authors themselves point out, these scenarios are
unrealistic but are intended to explore different aspects of network
congestion. They also point out that there are other scenarios, which
had confusing results and were not presented in the paper.

    Overall the paper was good, but it would have been interesting to
see the simulation results that the authors claim were "confusing".
Rather than do this, it seems like the authors brushed the confusing
results under the rug.
   
Received on Wed Sep 27 2006 - 22:16:54 EDT