From: Chandrika Jayant (cjayant@cs.washington.edu)
Date: Sun Oct 24 2004 - 16:44:06 PDT
"Analysis and Simulation of a Fair Queuing Algorithm"
Written by Alan Demers
Reviewed by Chandrika Jayant
This paper proposes a gateway router fair queuing algorithm to help
avoid network congestion. It is important to note that this algorithm
does not attempt to improve on congestion control itself (after the
fact). This algorithm is similar to Nagle's FQ algorithm but it uses
bit by bit round robin instead of packet round robin. This makes
bandwidth allocation fair in that users who aren't using their full
bandwidth share have lower delay, and does not give users with larger
packet size any advantage. In the FQ algorithm each user has its own
queue at the gateway so malicious users have a harder time taking over
bandwidth.
I like how Demers logically separates the quantities of bandwidth,
promptness, and buffer space. In FCFS these quantities become more
dependent on each other and are hard to attack separately (providing no
protection against malicious/greedy users). In regard to his FQ
algorithm, Demers first defines his idea of "fairness" as the max-min
fairness criterion and "user" as a particular source-destination pair.
It seems clear that with an expanding network and many different
services provided, more testing needs to be done with different fairness
and user criteria. Also, FQ and the flow control algorithms from the
hosts will need to communicate properly and be able to adapt to many
different definitions of both of those terms, not an easy task.
The paper gives an algorithm which claims to provide fair bandwidth
allocation, protection from malicious sources, and lower delay for
sources using less than their full bandwidth share. I am pretty
convinced of the advantages of the method compared to FCFS and Nagle's
FQ algorithm. However, there were a few gaps in the paper. Demers only
considered a restricted class of arrival streams to show (FTP and
Telnet). They do span different transfer scenarios (large file transfer
vs intermittent packet sending), but I am not convinced how well this
algorithm would work with different types of service (media streams,
etc). Also, the simulations and comparison part of the paper was so
complicated and messy (not enough graphs) that it was hard to follow.
The paper moves a step up in terms of quality of service. However more
evidently needs to be tested out with different streams, higher loads,
different flow control algorithms, and more needs to be thought about
how this would fit in with the existing network. The paper also brings
up the end to end argument again by showing what might be good to do at
the hosts versus the gateways. As networks were rapidly growing in the
80s this paper is timely and is a good next step at improving congestion
avoidance, but could have been a lot more solid.
This archive was generated by hypermail 2.1.6 : Sun Oct 24 2004 - 16:44:24 PDT