Core-Stateless Fair Queueing

In this paper, a simpler queueing algorithm is proposed that divides routers into "core" and "edge" routers: the edge ones essentially are inter-AS while the core ones are within an AS. In this regime, only edge routers require per-connection state, and such routers insert some state into packets as they traverse into an AS (or, in this paper's terms, an "island" of routers). Core routers are stateless with respect to outside connections, but do queueing based on the information from the headers.

The basic outline of the algorithm uses flow arrival rates, estimated and weighted using exponential averages. This is interesting, but I am not clear on why it is the right thing to do, other than the authors asserting that using constant parameters results in wrong behavior.

The overall algorithm seems somewhat complicated, but since the edge routers are much fewer than the core routers, most routers can be implemented without having to do complicated state manipulation and computations. It is not as fair as the previous paper's algorithm, but requires less computation per packet. The algorithm does punish ill-behaved hosts, which is a good property.

In simulation, the CSFQ algorithm does quite well, and although it is not as fair as the more complicated WFQ, it behaves rather fairly. However, although some routers don't have to be super-complex, the edge ones do, requiring packet classification mechanisms. How much of an improvement this is over FQ is not clear. In addition, I believe Moore's Law outpaces bandwidth increases, so all the computation involved in FQ may not be a problem.