From: Erika Rice (erice@cs.washington.edu)
Date: Sun Oct 24 2004 - 20:16:24 PDT
"Analysis and Simulation of a Fair Queueing Algorithm" by Alan Demers,
Srinivasan Keshav, and Scott Shenker:
The paper "Analysis and Simulation of a Fair Queueing Algorithm" by Alan
Demers, Srinivasan Keshav, and Scott Shenker describes a queueing
algorithm to replace first come first serve queueing. Their algorithm
is based on Nagle's proposal where routers have queues for each source;
these queues are serviced in a round robin manner.
Two contributions of their paper were the observation queueing
algorithms allocate three fairly independent quantities (bandwith,
promptness, and packet dropping) and the observation that a packet based
round robin scheme does not preserve fairness (a source sending larger
packets would get an unfair amount of resources.
Although the authors do not completely separate bandwith allocation,
promptness, and packet dropping in their algorithm, the fact that they
make explicit the separate nature of these issues is significant.
Separation allows the issues to be addressed separately, and, therefore,
each issue can be addressed in an appropriate and possibly more
effective manner.
The second observation was the heart of their algorithm. The authors
realized that the round robin algorithm would be more fair if each queue
had one bit delivered from it at a time. Since this is impossible, they
intoduced a way to approximate this.
One shortcoming of this paper was that the authors did not give
sufficient space to the issue of how this algorithm would behave in a
heterogenous network. If only a small number of routers used their
method, would it make a difference? Would it make performance worse?
Such observations would have been valuable to the reader.
This archive was generated by hypermail 2.1.6 : Sun Oct 24 2004 - 20:16:24 PDT