From: Seth Cooper (scooper@cs.washington.edu)
Date: Sun Oct 24 2004 - 15:28:49 PDT
This paper presents an algorithm for Fair Queuing (FQ) at gateway
routers in the Internet. It extends an earlier algorithm that was
packet based, and was not fair because users sending larger packets
would get more bandwidth. The new algorithm is takes into account the
size of the packets, so that even when faced with users sending large
packets the resulting division of bandwidth will be fair. The algorithm
also allows for users who are using less than their fair share of
bandwidth to receive low latency. The algorithm attempts to separate
three resources that routers must share: bandwidth, promptness, and
buffer space. These resources are not separable in a first come, first
served queuing algorithm (FCFS).
A strength of the FQ algorithm presented is that it does achieve better
max-min fairness than the previous FQ algorithm. By sending out packets
in the order of when they will finish service, a user who sends a large
number of small packets will get the same amount of bandwidth as a user
who send out a few large packets, if the packets all add up to the same
size. This also achieves the effect of giving users who are not
consuming all of their fair share of bandwidth a lower latency, which
allows users to exchange bandwidth for promptness. This is useful for
applications like Telnet, where a low latency is usually desired over
high bandwidth.
Another strength of the new FQ algorithm is that it encourages better
flow control at end hosts. With FCFS, a user can attempt to consume all
the bandwidth and buffer space at a router, taking it away from other
users also using that router. In FQ, however, such a malicious user
will only be taking away their own buffer space, and eventually dropping
their own packets. Thus it is in the best interest of all users to do
what is in the best interest of the network as a whole, and only use
their fair share of bandwidth.
The paper was weak in its presentation of the simulation results. It
would have been better if there had been a more graphical representation
of the results. A few bar graphs might have been better than tables
after tables of numbers.
This paper is relevant today because allocation of resources in the
network is an important part of Quality of Service (QoS). The paper
makes many interesting points on what exactly fairness is, how a user
should be defined, and how the network can try to be fair to users. As
QoS becomes more of an issue, the network will have to support different
kinds of "fairness" for different users.
This archive was generated by hypermail 2.1.6 : Sun Oct 24 2004 - 15:29:05 PDT