From: Andrew Putnam (aputnam@cs.washington.edu)
Date: Mon Oct 25 2004 - 00:07:47 PDT
Analysis and Simulation of a Fair Queueing Algorithm
Alan Demers, Srinivasan Keshavt, and Scott Shenker
Summary: Using the prior work of Nagle that suggested fair queue
management as an essential component of effective congestion control,
the authors attempt to devise an algorithm for implementing fair
queueing. Their algorithm seeks to separate promptness, bandwidth
allocation, and buffer management so that each can be separately
controlled. The algorithm is shown to perform much better on various
network topologies when combined with DEC flow control.
The primary contribution of this paper is a defined fair queueing
algorithm that works given static routing and advanced flow control.
The algorithm provides parameters for adjusting promptness, bandwidth
allocation, and buffer allocation independently. This allows
adjustability to handle the unique workloads of each network without
requiring a customized algorithm. This algorithm also provides
protection of outside networks from inside ill-behaved sources, and
encourages sources to use the most effective flow control available.
The authors make the claim that packetized bandwidth allocation
algorithms approach the fairness of bitwise algorithms for sufficiently
long conversations. There is no evidence given to indicate how long a
conversation has to be to be "sufficiently long". Given the short
duration and burstiness of network traffic, I would be surprised if
these bandwidth allocation schemes turned out to truly be fair. It
would have been nice to instead compare the authors scheme to the
perfect bitwise scheme in order to evaluate the algorithm.
Though the paper deals primarily with congestion control, many of
the issues that the paper raised deal with quality of service (QoS)
issues. For example, the authors are concerned about the promptness
with which a packet makes it through the gateway. Promptness is not
strictly a concern of congestion control, but is necessary for
interactive sessions such as Telnet/SSH connections. However, the
discussion is appropriate since fair queueing enables promptness
control,
The authors concern with promptness is particularly important when
dealing with an acknowledgment transport protocol such as TCP. When
destinations send the ACK back to the source, the response should be
prompt so that the minimal amount of unnecessary retransmitted data
enters the network. This also gives the source a better value for RTT
when transmitting through gateways that receive data faster than they
send data (a common configuration for many small networks). An accurate
RTT is essential for congestion control and effective bandwidth
allocation.
The authors indicate that Nagle's packet round-robin approach is
unfair because it does not account for packet length. This is certainly
true from the perspective of bit-by-bit fairness, but there is a
certain amount of overhead associated with sending any packet
regardless of the packet length. Depending on the extent of this
overhead, it is not as unfair to send long packets as the increased
number of bits would lead one to believe. Unfortunately, any
measurement of the per-packet overhead relative to packet length would
be technology dependent, and therefore tough to account for in a
general algorithm.
While the algorithm provides a number of solid benefits, the
algorithm appears to be rather complicated to implement in hardware
without resorting to the use of the processor for each packet. Since
routers can rarely afford to spend processing time on each packet, any
routing algorithm that requires a large number of CPU cycles will not
be practical to deploy. The authors recognize that the algorithm may
not be technologically feasible, and I find it hard to imagine that it
is feasible even with current generation technology.
This archive was generated by hypermail 2.1.6 : Mon Oct 25 2004 - 00:07:49 PDT