From: Tyler Robison (trobison@cs.washington.edu)
Date: Mon Oct 25 2004 - 01:17:39 PDT
The paper describes flaws in the First Come First Serve algorithm,
and in Nagle's fair queueing algorithm, and then proposes an algorithm
based on Nagle's which fixes these problems. FCFS queueing can be
exploited by sending large amounts of data to gateway, and tying it up.
Nagle's algorithm is fair in terms of the number of packets, but since
packets can vary in size, it can be exploited by using larger packets and
thus more bandwidth. The algorithm proposed here uses a function of the
packet size, arrival time, and the finishing time of the previous packet
from that user to determine who goes next. It favors smaller packets in
general, but also takes into account how long its been since that user had
a packet go through, and how long the packet has been waiting.
The paper seems fairly solid; the algorithm is founded in theory,
and was built taking into account the weaknesses of other possibilities.
Furthermore, the simulations show that it works fairly well. In terms of
simulated performance, the proposed algorithm is only really impressive
when an ill-behaved source is involved, but there it shows quite an
advantage in this area. It also appears that this algorithm would be
strongly resistant to numerous simple attacks which could easily work on
FCFS gateways. In addition, it helps to highlight how easy it could be to
congest/exploit FCFS as it is, and thus how important it is to fix this.
That said, the only results shown are from simulations, which may
not be indicative of the true algorithm performance. Furthermore, this
algorithm still leaves the gateway vulnerable to attacks in which a single
source can act as multiple users either by sending to different
destinations or by sending with different source addresses (assuming the
sender-receiver pair is the definition of a user). In addition, there may
be circumstances in which multiple computers share a source address
(perhaps due to a firewall), and so this notion of fairness may not be
fair in a very real sense unless a stronger definition of 'user' is found.
Overall, this algorithm does address important issues, but does not
completely solve the problem of fairness.
This archive was generated by hypermail 2.1.6 : Mon Oct 25 2004 - 01:17:40 PDT