Paper review : Analysis and Simulation of a Fair Queueing Algorithm (DKS89)

• Goal
  To provide a gateway queueing algorithm which can protrect the fair allocation of network resources from the ill-behaved sources.

• Contribution
  This paper presents a new practical fair queueing algorithm, with some rigorous understanding of the performance of this algorithm.

• Main ideas
  • The old FCFS algoirthm cannot deal with ill-behaved sources effectively, which implies that it cannot provide genuine fairness among sources.
  • The fair queueing algorithm proposed in this paper provides fair allocation of bandwidth, lower delay for not fully-served resources, and protects from ill-behaved sources.
  • This algorithm interacts well with the current flow control algorirhms.

• Evaluation
  • Significance rating: 4
    This paper gives a realistic fair queueing algorithm with careful considerations on several aspects. This opens the door leading to applying control machanisms to the gateway in order for the congestion control in datagram networks.

  • Convincing rating
    The authors analysis the shortcoming of the primitive FCFS queueing algorithms and the Nagle's earlier proposal, hence provide a bit-by-bit round robin algorithm with its improvement which is applied per packet and is more realistic. Then some simulation results are given where the queueing algorithm was combined with several prominent flow control algorithms. The results depict that this algorithm provide a fairly good solution w.r.t. fairness, where especially it prevents ill-behaved sources to grab more resources.

  • Limitation
    First, this algorithm requires the gateways to record the states with some computations for each conversation, and I am wondering the scalability of this algorithm.
    The simulation data shows that the Telnet sources are in disadvantage when they coexist with the FTP conversations. This shows the algorithm give a bias on the bandwidth allocation rather than the average delay.

• Conclusion
  How to provide the fairness among the conversations is an interesting problem. Control the resources at the gateways seems like a better way than the control machanisms at end-host. However, it still interacts with the flow control algorirhms, hence the good behavior when cooperate with the latter is important.

  11/7/01