Core-Stateless Fair Queueing

This paper solves one of the main issues with fair queueing - the cost of maintaining per-flow state - by showing that it is sufficient to maintain state at the edge routers and have the larger core routers run a stateless algorithm. This would enable much wider deployment of fair queueing because the border routers that maintain per-flow state don't need to be nearly as fast as the central ones. The core-stateless fair queueing algorithm achieves this by approximating the behavior that would occur with fair sharing. First, edge routers compute a rate of arrival for each flow, and mark packets from it with this rate. Second, core routers use FIFO queueing and a probabilistic drop algorithm to drop packets based on the proportion of packets that would have been dropped from each flow under a fair sharing discipline. There are a number of mathematical heuristics used to approximate this, but in the end, the process appears to work reasonably well, showing sensible results in simulations.

This work is interesting both because it enables something that previously seemed intractable (fast fair sharing) and because the general idea, minimizing logic in the core of the network, is powerful and perhaps more widely applicable. The idea in CSFQ is somewhat reminiscent of the end-to-end principle, except that trusted network nodes (the edge routers) take the roles of endpoints for the purpose of congestion control, and the reason for removing logic from the center is performance, not just good design. However, some of the design advantages are there - for example, the edge routers can be reprogrammed to support a variety of forms of sharing based on different definitions of flow, without modifying the core routers. Similar marking schemes have been proposed for security in the Internet (identifying sources of malicions flows and preventing DOS attacks).

The paper is lacking a bit in the evaluation section, first because CSFQ sometimes does poorly and it would be nice to characterize exactly when this happens, and second because there is no implementation. I'm not sure how easy it would have been to use Click or NetFPGA at the time this was written, but having a demo of CSFQ at "line rates" would have been very convinging. The work also does not address one of the issues that has really plagued QOS research, namely deployment, though it makes design of QOS-supporting routers more feasible.

The math in the paper also includes a number of approximations, and there's a risk that these may interact poorly. Because the system is pretty complex, the only way to really be sure is to run more simulations, perhaps trying different estimaton algorithms, drop algorithms, etc.