Core-Stateless Fair Queuing

CSFQ makes the important contribution of making Fair Queuing, with all its desirable properties, practical. The biggest problem with FQ was that the routers had to maintain per-flow state. The authors show that state maintenance can be pushed to the edges of the network to allow the core routers to be stateless. The authors motivate their work in the context of an “island” with a combination of edge and core routers (typically an ISP’s AS). This identification of the fact that all routers aren’t equal (in both capacity and loads handled), seems valuable for a whole bunch of QoS related ideas.

CSFQ approximates the behavior of FQ. Edge routers compute the rate of arrival for each flow and mark packets representing this rate. Core routers use FIFO queuing and probabilistically drop packets based on the proportion of packets that would have been dropped with fair sharing. Simulations show that CSFQ does almost as well as Deficit Round Robin, and of course provides intelligently designed state management.

In terms of presentation, I really liked the fact that the authors cautiously mention that their work is useful if storing state at routers “were” impossible, and not “are”. Overall, I really liked this paper and should be retained in the reading list.