Paper Review: Analysis and Simulation of a Fair Queueing algorithm

Reviewer: Kenneth Chin

This paper is introducing a Fair Queuing Algorithm based on the previous work by Nagle. It pointed out the deficiencies of Nagle's algorithm; 1) it doesn't take the packet lengths into account and so one using long packets gets more bandwidth then one using short packets. 2) there is no explicit promptness allocation. The authors were then motivated by the idea of having a queueing algorithm that should function well in the presence of ill-behaved sources, so they modify Nagle's algorithm to achieve the goal. The algorithm is thought to have fair bandwidth allocation, fair buffer space allocation and promptness. Fair bandwidth allocation can be achieved by taking in the length of the packets. Fair buffer space is achieved by simply dropping the packets. Promptness is a little bit tricker, but essentially is controlled by bid.

There are some drawbacks in the paper:
  1. Fair queueing requires that the ideal bit-by-bit round robin (BR) scheme be simulated too. It requires complex hardware and it is still an open question.
  2. It seems that the authors mix up the concept of congestion control and flow control.
  3. Only a few flow control algorithms are put to test and only FCFS queueing algorithm is compared with fair queueing algorithm. The analysis is not general enough for other combinations of flow control algorithms and queuing algorithms.
Basically, there are two things I learn from the algorithm.
  1. By using a separate queue for a conversation (source-destination pair) and round-robin service discipline, malicious users are not able to gain advantage over other users in terms of bandwidth allocation.
  2. Separating the promptness allocation from the bandwidth allocation by introducing a parameter such that the sending order is determined by bid, but not the finish time of the packet, while the asymptotic bandwidth allocation is independent of bid, but the finish time of the packet.
This paper has a good contribution to queueing schemes used in routers, so it is a 3rd-grade paper.