The TechGlider

Learning and sharing about Computer Science, programming, research & technology

Feb 14, 2017 - 2 minute read - Comments - review

Analysis and Simulation of a Fair Queueing Algorithm

Paper Title

Analysis and Simulation of a Fair Queueing Algorithm


Alan Demers, Srinivasan Keshav and Scott Shenker


September 1989. Symposium proceedings on Communications architectures & protocols (SIGCOMM ‘89).

Novel Idea / Main Result(s)

The paper presents an improved version of the fair queueing algorithm first proposed by Nagle, discusses limitations of congestion control with FCFS queuing, presents mathematical foundation behind their algorithm and finally, discusses the performance of this new algorithm in various real world scenarios with the help of simulations.


This was the first time that performance implications of a fair queuing algorithm were studied in detail and published. Network scheduling / queue management became an active area of networks research with several other algorithms proposed later.

Further, this paper identifies flow (called conversations in this paper) as a good criterion for bandwidth & buffer allocations, which has become a standard concept in the Software-Defined Networking research.


The authors come up with a methodology to emulate bit-wise round robin scheduling (which is intuitive to fairness but impractical for implementation) and provide both rigorous mathematical analysis and empirical analysis (with the help of network simulation experiments in various scenario) to justify their results. The evidence is, hence, quite convincing.


Yes, the description is enough, with a lot of work and resources


Primarily, I wonder, (as the authors point out in conclusion) whether technology has matured enough in past 30 years that we can have a true implementation of a fair queuing (for a reasonable definition of “fair”)?


I found the mathematics covered in ยง2.3 fairly hard to follow and perhaps it could have used further explanation. This is in contrast to the scenario diagrams presented in a later section which were both self-descriptive and had major observations pointed out in prose.

Ideas for further work


Review Template Credits: Prof. Rodrigo Fonseca