Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks; Stoica, Shenker, & Zhang

This paper starts out with the conjectures that fair allocation is very important and/or necessary to congestion control and that current fair allocation implementations are too complex to become widespread. As such, they present an algorithm to give approximately fair bandwidth allocation in which edge routers in some contiguous set of "island" routers calculate per-flow rates and encode flow rate into packet headers, information which can then be used by "island" core nodes without the core nodes needing to maintain any state.

They also simplify the fair queueing mechanism by not separating scheduling and buffering out per flow, opting instead for a FIFO and probabilistic packet dropping, in which a flow's drop probability is based on how much more traffic than its fair share it's trying to send. The authors also describe a method of giving different weights to different flows grouped by islands.

They then run a number of simulations in ns-2 that compares CSFQ against a number of queueing algorithms: FIFO and RED (no per-flow separation) and FRED and DRR (which do allocate on a per-flow basis). These simulations include mixes of UDP and TCP flows, some of which send packets at much larger rates than their fair share, layered multicast traffic, and large propagation delays. CSFQ outperforms FIFO and RED, which do not attempt to fairly allocate, and performs on par with FRED but without requiring any special per-flow treatment. It does not perform as well as DRR, but the authors are optimistic about improvements that can be made to it.

Overall this sounds like a good algorithm for achieving approximate fair allocation, with the real savings being in the lack of state required in all the routers. Since the paper was an overview of a proposed architecture, there weren't huge amounts of detail about how large "islands" should be and hence how much complexity would be cut by having stateless core routers. Also, high-speed packet classification is still an actively-researched problem, and one that the authors would benefit from having a good solution for, as their algorithm requires classifying to flows.