Summary: Analysis and Simulation of a Fair Queueing Algorithm

This paper describes a fair queueing algorithm for use on gateways. The
authors argue that the network can be shared in a fair and efficient with
only simple FCFS queueing algorithms on the gateways, but only if all
end-hosts are well-behaved. Since end-hosts may be misconfigured or may
disobey the congestion protocol to put themselves at an advantage, we cannot
safely design a network around the assumption that end-hosts will always be
well-behaved. The authors suggest that with a carefully crafted queueing
algorithm running on the gateways, all hosts can be guaranteed a fair slice
of the available bandwidth, "promptness", and buffer space despite malicious
behaviour from other end-hosts.

A fair queueing algorithm proposed by Nagle is described. This algorithm
establishes a separate queue for each sender/receiver pair at every gateway.
Gateways service their queues with round-robin discipline. However, the
authors note that this algorithm is not fair, since packet sizes may vary.

The Nagle queueing algorithm is made bandwidth-fair by first analyzing how it
mathematically behaves if bits are dequeued one at a time (ie. packets have a
size of one). The authors discover that the mathematical description of the
algorithm is not dependant on the actual service time of the packets. They
therefore design their algorithm around the principle that the packet which
would be finished transmission first if the bit-by-bit algorithm were used is
the packet that should be serviced. This algorithm allocates bandwidth to
competing flows fairly; no flow may be further ahead than another by more
than the maximum packet size.

Having tackled bandwidth fairness, the authors next aim for promptness.
Instead of aiming to service all flows with equal delay, the proposed
algorithm gives less delay to packets from flows that are not using less than
their fair share of the bandwidth. They analytically derive the delay
performance of their algorithm by considering a gateway processing a number
of FTP flows and one Telnet flow.

In section 4, the authors simulate their gateway queueing algorithm alongside
various common end-host flow & congestion control algorithms. They compare
their algorithm against simulated gateways using FCFS discipline. In
particular, throughput, average roundtrip time, retransmitted packet count,
and dropped packet counts are examined.

The authors were very thorough and rigorous in their presentation. The
proposed fair queueing algorithm was mathematically justified. The authors
then used the mathematical definition of the algorithm in order to derive its
delay characteristics. Finally, the paper presents what would appear to be a
comprehensive set of measurements, although they were based on simulation.
Received on Thu Sep 28 2006 - 00:01:39 EDT