From: Ethan Phelps-Goodman (ethanpg@cs.washington.edu)
Date: Sat Oct 23 2004 - 19:31:47 PDT
a Fair Queueing Algorithm
Demers et al.
This paper presents and evaluates a fair queueing algorithm for
gateways. At the time it was just being realized that queueing
algorithms, though not explicitly part of congestion control, still had
a big effect on network performance. A queueing algorithm is
responsible for how bandwidth is distributed, how delay is distributed,
and which flows suffer dropped packets. The traditional
first-come-first-served queueing algorithms don't attempt to manage
these quantities. Beyond the obvious inefficiencies of this mechanism,
there is the problem of gaming by a misbehaving source.
This paper address these issues with what is essentially a round-robin
scheduler. (It differs from previous proposals in that the scheduling
is round-robin in terms of amount of data sent, not number of packets.)
This ensures that each user gets its fair share of bandwidth. Over
users are punished by having their packets dropped, in contrast to
FCFS, which would drop arbitrary packets. It has the additional
advantage that low-bandwidth senders get low delay, which makes
particular sense in the setting of a telnet flow competing with and FTP
flow. They give a decent analytical evaluation, and extensive
simulation data against a variety of congestion schemes.
I was surprised that such a simple question as FCFS vs. round-robin
could have so many subtleties, such as defining fairness and defining a
user. The evaluation is also made a lot more complex by the fact that
the queueing scheme interacts in complicated ways with congestion
control schemes, and it must work well with the variety of existing
schemes. The paper clearly demonstrated that fair queueing is better
than FCFS, but it seems like this is all a bit of a hack to try and
give some sort of QoS guarantees. And as a QoS system, fair queueing is
still terribly inadequate.
Ethan
This archive was generated by hypermail 2.1.6 : Sat Oct 23 2004 - 19:31:56 PDT