Review - Fair Queue

Review of the paper "Analysis and Simulation of a Fair Queueing Algorithm"
by Ivan Hernandez

This paper describes a new fair queueing algorithm that provides
protection (so that ill-behaved sources can only have a limited
negative impact on well behaved sources). This algorithm solution
allocates bandwidth and buffer space fairly, and also is able to
control the promptness allocation of the packets.

The paper describes the most common queueing algorithm
First-Come-First-Serve (FCFS) and how this one fails in provide the
above mention characteristics, since to algorithm just decides based
on the order of arrival of packets. Next, the authors take as a
foundation Nagle's "fair queueing" (FQ) algorithm in which gateways
maintain separate queues for packets from each individual source, then
the queues are serviced in a round-robin manner. The major flaw of
this algorithm is its consideration of packet lengths, which results
in unfairness in bandwidth allocation.

The authors define technically fair and the allocation of bandwidth
and buffer on the basis of source destination pairs. Next, in order to
achieve fairness transmission, the transmission will occur in a
bit-by-bit round robin manner, this assumption allows the authors to
figure out an analytical model to work, and the translate the results
to a packet-by-packet transmission scheme. Then the authors describe
the promptness allocation strategy: to give more promptness to users
who utilize less than their fair share of bandwidth. Finally, fair
buffer allocation is easy, the algorithm just has to drop the packets,
when necessary from the conversation with the longest queue.

Finally, the authors present three classes of flow control algorithms
that will use in the simulations. In all simulations the new algorithm
was better than FCFS. The simulations results show how the new
algorithm achieves fairness throughput disregard the flow control
algorithm used. Furthermore, the new algorithm punishes ill-behaved
users, this users will get much less than its fair share, this measure
protect well-behaved in the network.

This paper is a good one. I shows how the routers can help to achieve
avoidance congestion and fairness just with the layer three information
that they can obtain from the network, and just with a modification in
its queueing processing. The solution does not add any additional
traffic and is not CPU intensive. Furthermore, this solution does not
set any requirements on the endpoints.
Received on Wed Sep 27 2006 - 21:57:17 EDT