Summary: FQ Algorithm

The algorithm discusses gateway fair queuing algorithm and it's role
accompanied with transport protocol, in controlling congestion in packet
switched networks. The paper clearly distinguishes three different pieces
of a congestion control algorithm: source flow control, gateway routing
and queuing algorithm. queuing algorithms determine the way in which
packets from different sources interact with each other which in turn
affects the collective behavior of flow control algorithms. It brings out
the need to go beyond FCFS queuing in conjunction with source flow control
algorithms to control congestion effectively in non-cooperative
environments.

Any fair queuing algorithm should address three independent quantities: 1)
Allocate bandwidth in a fair manner 2) allocating buffer space in a fair
manner 3) Promptness control (delay). Pure round robin algorithm provides
a fair allocation of packets sent but fails to guarantee a fair
allocation of bandwidth because of variation in packet sizes. To address
this unfairness issues with bandwidth/buffer allocation, the paper
initially presents a bit-by-bit round robin(BR) algorithm then
extrapolates the algorithm to a practical packet by packet transmission
scheme. To address the promptness allocation, it uses a strategy in which
users who utilize the less than their fair share of bandwidth gets more
promptness(less delay). It uses something called as Delta to account for
this. In addition, FQ algorithm encourages to use of better source flow
control algorithm because it punishes misbehaving hosts. The performance
of FQ and FCFS is studied with different flow control algorithms such as
DECbit/JK/FQbit etc. All the results unanimously show that performance of
the FQ algorithm is much better than FCFS with any source flow control
algorithm. Finally, the paper discusses few problems with the queuing
router implementations such as economic feasibility of these queuing
routers considering the cost involved building them.

Overall, the paper is a marvel in the sense that it is the first paper to
bring out the real need for fair queuing in network gateways. The
criticism of the paper is FQ algorithm is studied to address congestion
avoidance but not congestion recovery(how quickly a network can recover
from congestion).
Received on Thu Sep 28 2006 - 11:08:35 EDT