Analysis and Simulation of a Fair Queueing Algorithm; Demers, Keshav, & Shenker

This paper sets out to describe a "new" fair queueing algorithm to be implemented at the gateway. (The authors spend copious amounts of time describing other similar work to their algorithm, which makes me question how different their work really is.) Three requirements for this queueing algorithm to fulfill include allocating buffer space and bandwidth fairly amongst a number of users, the ability to control promptness/delay somewhat independently of buffer space/bw, and continuity with the packet-scheduling scheme.

The paper defines fairness based on Jain's max-min fairness, where each user receives the minimum of either their requested amount of a resource or their fair share. It's tough to decide how to actually define a "user;" it could be done on a per-sender, per-receiver, per-sender-receiver pair, or per-process basis, each with possible drawbacks in terms of security and fairness. The authors select sender-receiver pairs (called "conversations") because it doesn't reward bad behavior or penalize a user due to malicious circumstances out of their control.

The algorithm for fair queueing is based on bit-by-bit round-robin. The authors created metrics for start and finish time that can be used to order packet's worth of bits by, and after start and finish times are assigned, we can use those metrics for whole packets without regard to how long the packets actually are. Using these finish times, there is one simple rule the algorithm follows: the next packet to go out has the lowest finish time. A more complicated flavor of this FQ algorithm introduces the concept of bid, a way to give less delay to users who use less than their fair share of BW. When the queue is full and a new packet arrives, simply drop the last packet of the conversation using the most buffer space.

Paired with a fair queueing algorithm, there also needs to be flow control. The progression of flow control over time began with a timeout mechanism and sliding window flow control and progressed to the Jacobson-Karels (JK) which added dynamic window size, and finally to DECbit which allows the gateway to send selective congestion signals to overagressive users. This third approach is an intriguing one, though I wonder if it ever got used (though presumably it did within DEC)?

Simulations combining different combos of flow control and queueing (generic, JK, or DEC flow control with FCFS or FQ): fair queueing needs good flow control to be effective. When ill-behaving users are added to the mix, the paper's FQ does a good job of letting well-behaved hosts' traffic through, minimizing the incentive for a user to misbehave. The simulations used benchmarks, not real workloads, though the benchmarks were meant to show a mix of different scenarios, using as applications Telnet and FTP. A question I have is how easy is FQ to modify to incorporate not just what a user's equal share would be but also how much of a resource something deserves? It seems difficult to come up with good generalized algorithms that can accommodate the different types of users (file servers vs. Telnet, etc.), though FQ seems to generalize well regardless of the type of traffic it sees.