Review: Analysis and Simulation of a Fair Queuing Algorithm

The paper presents gateway queuing algorithms as a mechanism for congestion
control algorithms in datagram networks and compares them to source
congestion control algorithms. The queuing algorithms just control the order
in which packets are sent and the usage of buffer space, and hence do not
directly change the total traffic leaving a gateway. However, they do
determine the way packets from different sources interact with each other
and thus affect the collective behaviour of flow control algorithms.
The paper identifies that queuing algorithms must handle fair allocation of
bandwidth, buffer space and promptness (delay). They define fair allocation
as:
(1) no user receives more than requested.
(2) no other allocation scheme has a higher minimum allocation.
(3) the above 2 should remain true even if the user with the minimum
allocation is removed and the total resource is reduced accordingly.
Furthermore, they define the user to be a source-destination pair, which
appears to be the best tradeoff between security and efficiency.
The paper proposes that a fair queuing algorthim which fulfills these
requirements works as follows: whenever a packet finishes transmission, the
next packet to be transmitted is the one that will
finish being sent the earliest (in the non pre-emptive case). In order to
account for promptness, they suggest giving less delay to users who utilize
less that their fair share of bandwidth. This, they argue, gives lower
queuing delay to lower throughput sources. They present a delay-throughput
curve to show the fairness of this queuing algorithm over the
First-Come-First-Serve (FCFS) algorithm (delay tends to infinity as
throughput reaches 100% of available bandwidth for fair queuing but not for
FCFS). They also show that the delay is lower for a low throughput source
with fair queuing as compared to FCFS.
The authors then briefly describe several flow control algorthims used at
the source and present simulations of using these algorithms in conjuction
with fair queuing and FCFS. The simulations show the throughput, average RTT
of packets, number of packets retransmitted, and number of packets dropped
for each combination of flow control and queuing algorithms, and for each of
the six scenarios simulated (including underloaded gateway, overloaded
gateway, ill-behaved source, mixed flow control algorthims, multihop path,
and more complicated but underloaded network). They concluded that overall
fair queuing always performed better that FCFS in terms of fair allocation
of bandwidth and buffer space, and in terms of delay. Furthermore, fair
queuing shuts out ill-behaved sources (thus acting as a firewall) and also
encourages the use of more intelligent, self-optimizing flow control
algorthims at the source resulting in fair, protective, nonmanipable and
stable networks.
The paper ends by talking about two objections to their approach: (1) some
source-destination pairs need more that their fair share of bandwidth (for
which they introduced a simple modification to their algorithm) and (2)
deployemnt issues due to the requirement of fast and smart gateways (which
they question themselves and leave as futur work to determine).
The paper presents the arguments clearly, but it is limited in its
comparison to only one other queuing algorithm and in its evaluation to only
a few small networks. Also, they simplify the flow control algorthims quite
a bit, especially the explicit binary feedback algorthim for which they
simplify the signalling criteria.
Received on Wed Sep 27 2006 - 22:42:43 EDT