Fair Queueing

The main observation that this paper makes is that if you have a set of different workloads presented to a router, the traditional FIFO or FCFS with tail drop policy don't perform very will in the face of congestion (when the demand for link bandwidth is greater then supply). The authors propose a new queuing scheme, where packet sources receive their fair share of the available bandwidth, which is defined to be 1/N, with N concurrent flows. Furthermore, they want to provide lower-latency service to flows which use less of their fair share.

To achieve this, they consider a bitwise FCFS model where each flow submits one bit at a time for transmission. They notice that this model has the properties they want; for instance, if a set of large packets and one small packet are all submitted at about the same time, the small packet will finish before the large ones. Since routers can't actually act on bits, they develop a packetized queuing scheme which has the property that packets are transmitted in the same order that they would be using the bitwise algorithm. They evaluate their new algorithm with theoretical results and simulation with microbenchmarks on a number of network topologies. The motivation of the simulations are twofold; one, they wish to show that their basic derivation has good properties and is worth the cost over other existing queuing algorithms. They also mention that they have been unable to prove properties about a network of gateways all using fare queuing, and so want to validate that there isn't a breakdown when more then one router uses this algorithm.

The basic idea underlying this queuing algorithm, that participants who are not greedy and use less then their share of a resource should be rewarded with better service, seems to have some generality; it is also used in many modern process schedulers (like MLFQ) to improve response time for interactive processes; a very similar goal to what the are trying to accomplish.

This one can be a bit of a slog, but they explain what is going on well in the text and the math is mostly understandable. I never did get a good sense of what the difference between "preemptive" and "nonpreemptive" versions of the algorithm were; the math on page 5 seems to bound the average response time, and in the preemptive case it is less... A table of constants might have helped, since there are a whole bunch of them. Fair queuing as a paper has some value, although it seems a bit hard to understand out of context. A big weakness of this work is the per-flow state; although I would have liked it if the authors had explicitly stated what state is kept for each flow.