i. The fair allocation of bandwidth amongst multiple users,
ii. Reducing packet delay for light (presumably interactive) users, and
iii. Reducing the ability of an "ill-behaved source" to impact the performance of other users.
* The primary problem with FCFS in a busy environment is that the queue is constantly full. When this happens, busy users consume an increasingly high percentage of bandwidth, while the light users are starved of the bandwidth they need and deserve. The busy users ("winners") view the ACKs they receive as an indication that it's OK to send again, while the light users ("losers") spend most of their time retransmitting dropped or delayed packets.
* It was observed that a single "ill-behaved source" (malicious or malfunctioning) could generate enough traffic to prevent all other users from obtaining acceptable performance. However, it is somewhat difficult for a queuing algorithm to differentiate between a popular (busy) server, which should generate a large amount of traffic, and an out-of-control source, which should be throttled back.
* Nagle's FQ algorithm ignores packet length, which rewards users who generate long packets and penalizes those who generate short packets. The biggest problem that I forsee with this is that long packets obviously take longer to queue and transmit, and are generally (but not always) less time-sensitive than small packets, which are typically found in interactive applications like on-line gaming and telnet.
* The new FQ algorithm builds on Nagle's work, and preserves the notion of servicing a number of queues in a round-robin fashion. The real beauty of FQ is that a given source can only extend its own queue length, and can't squeeze out competing users. This is also a limitation, though, for a very busy server competing for bandwidth with (possibly less important) client machines. (How badly, for example, does NFS performance suffer on a busy network with FQ? Is it worthwhile to essentially choke back a mission-critical server to benefit a few interactive clients?)
* The authors of this paper suggest the problem just described is best addressed by tracking the number of "conversations" (source-destination pairs) and weighting the allocation accordingly. This gives busy servers (with large number of client connections) more bandwidth than those that are not as busy, but creates yet another problem: A malicious host can spew packets at numerous hosts, consuming an "unlimited amount of bandwidth" and defeating all three of the primary goals stated above.
* One definite result of the FQ algorithm is that telnet users experienced significantly lower delay than those in the FCFS scenario, in both unloaded and loaded networks. Throughput of the network is increased significantly with FQ simply by granting ACK packets (which are small) priority over large packets.
* Although the results obtained by the authors were promising, they argue that simply improving the queuing algorithm alone isn't enough, and that making flow control algorithms smarter is necessary. In fact, using FQ gives incentive to those who use smart flow control, instead of penalizing them [as FCFS does]. While this may be viewed as a means of "social engineering" on the Internet, it certainly works towards the goals outlined above.
* The two primary objections to FQ outlined in the paper are as follows:
i. FQ ignores the fact that some machines really need more bandwidth than others, and
ii. FQ requires significantly more computational power on the router.
The authors argue that "FQ is no worse than" FCFS on the first point, which seems like a weak argument. They hint at the idea of modifying the algorithm to "allow for arbitrary bandwidth priorities," which opens up an entirely new can of works.
The authors failed to mention Moore's Law and the advances made in ASIC technology on the second point, although they do pose an interesting question: "Can [one] build FQ gateways that can match the bandwidth of fibers?" Given the incredible advances in fiber utilization the past few years (think DWDM), it's a very valid question, and one I don't believe we really have an answer to... yet. :)
>-> Jared Reimer, System Admin
<-< oz.net Internet Services
>-> (206) 443-8000 || (888) SENSE-80