From: Danny Wyatt (danny@cs.washington.edu)
Date: Sun Oct 24 2004 - 17:56:55 PDT
Analysis and Simulation of a Fair Queueing Algorithm
Alan Demers, Srinivasan Keshav, Scott Shenker
This paper presents an approximation of a bit-by-bit round robin
fair-queueing scheme. The approximation works by ordering packets based
on their expected finish time, which is a function of both their arrival
time (the only ordering criterion in earlier FQ schemes) and their
size. They further extend the scheme to consider a tunable window of
history for a flow when ordering its packets.
I appreciated the many simulations they performed. They gave good
empirical validation not just to their scheme, but also to the
"segregation" effect for generic flow control and the vulnerability of
Jacobson-Karels flow control to ill-behaved hosts. However, the
simulations can only go so far. They readily admit that there were
confusing simulations, but they also ask us to trust that none of those
confusing simulations provided any evidence against their scheme. This
points out a methodological limitation of not just there research, but
most networking (or, really, any other area of inquiry into complex,
real-world phenomena): it's just not possible to control all variables
or foresee all situations. That said, their simulations were nice, but
I have no feel for whether they are representative, fundamental, or just
the ones that made for the most compelling publication.
I also appreciate the game-theoretic approach to "host management" that
makes fair play the most rational host behavior. In fact, I am
surprised that such behavior can be enforced by just the routers in the
lightweight, stateless network. The very first paper we read stressed
that accountability was a low priority in the original internet design,
and I wonder whether it wasn't also assumed that all attached hosts (in
the military-only scenario) would play nice. Given that origin, this
solution is as elegant as the other practical solutions we've seen.
This archive was generated by hypermail 2.1.6 : Sun Oct 24 2004 - 17:57:32 PDT