From: Michael J Cafarella (mjc@cs.washington.edu)
Date: Mon Oct 25 2004 - 01:06:09 PDT
Analysis and Simulation of a Fair Queueing Algorithm
By Alan Demers, Srinivasan Keshav, Scott Shenker
Review by Michael Cafarella
CSE561
October 25, 2004
The author discusses problems of gateway packet queueing. While
the queue algorithm may seem like a fairly obscure router detail,
it actually has a very large impact on how the network enforces
fair access among clients. The author describes how the current
system (FCFS) is unsatisfactory, and then goes on to introduce
a better one.
FCFS, or First-Come First-Serve, simply keeps a single queue of incoming
packets, and emits them in the order in which they arrived. This means
an aggressive sending host can monopolize the gateway's buffer and link
resources, and the expense of more fair-minded hosts.
Round-robin is another solution. In this scheme, we keep a separate
queue for every sender/destination/flow. The next outgoing packet
is always chosen from the head of the next queue. Although this seems
more fair than FCFS, it fails when confonted by packets of varying size.
Bit-by-bit round-robin, in which every queue sends a bit instead of
a packet, is more clearly fair, but obviously impractical. The author
then offers his own system for fair queueing, which is a packet-based
approximation of the bit-by-bit output.
Two very nice things about this paper are:
-- A general mathematical framework for discussion, which is often missing
in previous papers we've read
-- An analysis of the delay induced at each gateway by the queueing
algorithm. Although it's presented as being useful for Telnet and interactive
shell traffic, it seems just as helpful for streaming-media data today.
It's typical of papers of this time that security and packet-spoofing
are not discussed. That's a shame; the entire algorithm depends on easily
identifying host flows, which might not be so easy in practice.
This archive was generated by hypermail 2.1.6 : Mon Oct 25 2004 - 01:06:09 PDT