Analysis and Simulation of a Fair Queueing Algorithm
- State the problem the paper is trying to solve.
The main problem the memo is trying to solve is how to improve on gateway
- State the main contribution of the paper: solving a new problem, proposing a
new algorithm, or presenting a new evaluation (analysis). If a new problem, why
was the problem important? Is the problem still important today? Will the
problem be important tomorrow? If a new algorithm or new
evaluation (analysis), what are the improvements over previous algorithms or
evaluations? How do they come up with the new algorithm or evaluation?
The main contribution of this paper is that it proposes a new gateway
queueing algorithm called the fair queueing algorithm. This problem is
still important today as we consider how flow control changes at the
source and how this will affect developments at the gateway level and how
to maintain properties like fairness and efficiency.
- Summarize the (at most) 3 key main ideas (each in 1 sentence.)
The three 3 key main ideas are:
(1) The fair queueing (FQ) algorithm provied several important advantages
over the traditional first-come-first-serve (FCFS) algorithm: fair
allocation of bandwidth, lower delay for services using less than their
full share of bandwidth, and protection from ill-behaved sources.
(2) Fair queuing gateways by themselves do not provide adequate congestion
control; they must be conbined with intelligent flow control algorithms at
(3) The FQ algorithm was tested by simulating these algorithms at the
packet level using a network simulator built on the Nest network
- Critique the main contribution
- Rate the significance of the paper on a scale of 5
(breakthrough), 4 (significant contribution), 3 (modest contribution), 2
(incremental contribution), 1 (no contribution or negative contribution).
Explain your rating in a sentence or two.
I give this paper a rating of 4 because it presents a clear case of how
FCFS queueing algorithms have failed and how their FQ algorithm attempts
to compensate for these failures with an alternate queueing scheme.
- Rate how convincing the methodology is: how do the authors justify the solution
approach or evaluation? Do the authors use arguments, analyses, experiments,
simulations, or a combination of them? Do the claims and conclusions follow from the
arguments, analyses or experiments? Are the assumptions realistic (at the time of the
research)? Are the assumptions still valid today? Are the experiments well designed?
Are there different experiments that would be more convincing? Are there other
alternatives the authors should have considered? (And, of course, is the paper free of
The authors' methodology was to present a number of problems with the
usual FCFS queueing algorithm and to show how their improved FQ algorithm
corrects for all these cases. They proved the improvements of their
solution by simulating the FQ algorithm against the FCFS algorithm in a
simulator based on the Nest network simulation tool in a variety of
situations where the FCFS algorithm fails and using various congestion
control mechanisms. This is an effective first address of the problem but
it would be more convincing in the current day to recompare the two
schemes in the face of newew congestion control mechanisms (i.e. TCP Vegas
and TCP-friendly protocols) and with newer, more accurate network
- What is the most important limitation of the approach?
The most important limitation of their approach is that since they arrived at
their results using experiments run on a simulator, their results are only as
good as their simulator. In addition, their results are limited by the number of
samples they took and it would have been more convincing if they displayed the
confidence intervals of their results which they mentioned not including.
- What lessons should researchers and builders take away from this work. What
(if any) questions does this work leave open?
The lessons that researchers should take away from this work are that improving
gateway queueing algorithms can lead to improved fairness and efficiency in a
network. Much work has been done on congestion control mechanisms but
improvements can also be made at the gateway queue level that can made fairness
between streams with different requirements such as FTP streams versus Telnet
streams. Question this work leaves open are how the state of gateway queueing
algorithms are today and the performance of FQ under more realistic load
conditions, on larger networks, and interacting with routing algorithms.