Core-Stateless Fair Queueing

Summary
This paper describes a way of approximating fair queuing (FQ) that does not require routers in the middle of the network to classify packets into a particular flow. It is called Core-Stateless Fair Queuing (CSFQ) as routers in the core of the network need to maintain no per-flow state. This reduces the processing requirements on these core routers, while still providing more fair service than first-come-first-served and coming close to the performance of the much more expensive FQ.

Packets must still be classified, but this is only done at the edges of the network, where we can (maybe) assume flows will be slower and smaller. In addition the arrival rate of the flow is computed using exponential averaging. Packets are annotated with the results of these computations and a computation of the links fair rate estimation.

At core (or inner) routers this information is used to compute a constant time algorithm which probabilistically drops packets. This is done using the annoations of the arrival rate and fair share rate. Intuitively, the more a flow's arrival rate is above its fair share rate, the more likely it is to have a packet dropped. The authors bound the divergence from optimal their strategy can experience.

The authors run a number of simulations with various queing algorithms and show that CSFQ is much better than most other algorithms, and that is very close to deficit round robin, an efficient (but more expensive than CSFQ) FQ algorithm.

The paper also contains a fairly sizable discussion on what to do about misbehaving receivers. They argue that TCP-unfriendly flows should be managed, by something as simple as restricting them all the way up to dropping all their packets. The argument for dropping unresponsive (to dropped packets) flows is that there exist applications that don't care how many packets they loose (so-called fire-hose applications) that will simply flood the network no matter what scheme is in use, unless that scheme actively punishes them for their behaviour.

Thoughts
This was a very nicely argued paper. The authors clearly state their assumptions (even admitting that FQ might not even be necessary but asserting that if it is, their work is vital) and work forward from there. While I didn't check the details of the math in the paper, but I assume it is correct, and the results they derive seem reasonable.

It is a pity this scheme requires partitioning of routers in the network into edge and core. I suspect this would be difficult. Furthermore, any core would have to disallow any edge router than was not annotating, meaning a gradual upgrade to this scheme would be difficult if not impossible.

I also liked the discussion on misbehaving senders. This seems a real problem and I think active dissuasion is a good model for routers lest we end up with a million TCP stacks out there purporting to provide faster network access.

This paper was a bit heavy going at times, but a valuable read and one I would keep on the reading list.