From: Kate Everitt (kteveritt@yahoo.com)
Date: Sun Oct 24 2004 - 20:53:09 PDT
Fair Queueing
Review: Katherine Everitt
This paper discusses the design and implementation of
a fair queuing algorithm for network traffic. They
define fair as meaning fair allocation of bandwidth,
protection from badly behaved hosts, and lower delay
for low traffic sources.
The approach presented in the paper decouples
bandwidth, buffer allocation, and packet waiting /
when the packets get transmitted. It allocates these
resources based on conversations, which are source
destination pairs. Fair Queuing, or FQ, fixes two
problems with previous approaches. Unlike FCFS (first
come first serve), it does not drop packets based on
last packet in. In FCFS, ill-behaved hosts can take
over and fill up the buffers, causing problems for
other hosts. (One observation I found really
interesting in this paper was the idea that the ack
from a packet can clue in a heavy sender that the
queue is has a space, thus giving it an advantage over
endpoints that send packets randomly.) The other
problem FQ solved occurs with round robin queue
scheduler. In this case, the problem of ill behaved
hosts is partially solved, as bad hosts just fill up
their own buffer. However, differing packet sizes can
cause an unfair advantage, as everybody gets one
packet per round robin schedule.
FQ is very effective at solving these problems because
it not only imposes an extra cost on ill behaved
endpoints, it gives an advantage to services which
don’t need as many resources. At one point I
thought it might be valuable to tell the router if you
wanted a particular class of service, ie send quickly
but I won’t send much traffic, but then I
realized this was implicit in FQ. If you send more
traffic, it will be slower, if you need speed, send
less.
My only concerns with FQ are that it seems difficult
to roll out gradually, because hosts may need to know
what kind of scheduler they are dealing with to make
sending decisions. Also, the paper presented a lot of
results in table format, which made it very difficult
to identify what was important. Graphs or statistics
would have be more valuable.
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
This archive was generated by hypermail 2.1.6 : Sun Oct 24 2004 - 20:53:15 PDT