From: Charles Reis (creis@cs.washington.edu)
Date: Mon Oct 25 2004 - 00:25:36 PDT
Analysis and Simulation of a Fair Queueing Algorithm
Demers, Keshav, Shenker, 1989
The authors evaluate a variation on Nagle's fair queueing algorithm, both from a mathematical perspective and through simulation. Their variations include practical considerations, such as packet length and delay, that are necessary if fair queueing is to displace first-come first-serve. The paper derives the equations and variables to model fair queueing, such that bandwidth-sensitive and delay-sensitive flows can coexist, and it uses carefully chosen simulation scenarios to demonstrate fair queueing's advantages. It is worth noting that queueing algorithms cannot just be chosen on their own, but rather depend on the flow control algorithms at the endpoints as well, as shown by the simulation results.
From the simulations, the authors show their version of fair queueing is quite effective for bandwidth allocation and for providing low delay when desired. The most interesting aspect is perhaps its robustness against malicious senders, who are naturally discriminated against when they flood the network without the need for extra mechanisms in the gateways.
However, it is not clear if the proposed algorithm allows for other, more flexible delay policies besides giving low bandwidth flows low delay. It was also difficult to see how the algorithm was implemented in simulation, given only the derived equations, and even the authors mentioned they did not fully understand many of the simulation results. Finally, even if such hardware were economically feasible, it would have been useful to have more discussion of incremental deployment of fair queueing and its effects on other gateways and end hosts.
Overall, the work suggests that there are notable benefits to using more intelligent queueing algorithms in the core of the network, but experience seems to indicate that keeping the core simple is still the dominant approach (or at least has too much momentum to change easily).
This archive was generated by hypermail 2.1.6 : Mon Oct 25 2004 - 00:25:33 PDT