Analysis and Simulation of a Fair Queueing Algorithm

This paper introduces the idea of fair queueing, which has played a major role in quality of service research on the Internet. The key insight in fair queueing is to simulate an "ideal" router that can send one bit at a time, which serves to isolate flows from each other. The scheme proposed approximates this by computing when packets would have finished being sent in this ideal router, and scheduling them in that order. This is shown mathematically to approximate ideal fair queueing within some rather complex-looking bounds. The paper also includes a number of simulations showing how fair queueing would behave in real networks. Finally, it explains how the fair queueing model can be extended to support weighted shares as well as a "boost" for new flows to reduce their delay.

Fair queueing played a big role in design of QOS systems because it provides a simple and feasible primitive for isolating flows and guaranteeing capacity. A lot of the QOS work beyond this was on how to mark flows, how to admit them, how to implement weighted fair sharing more efficiently, etc. Fair queueing was is also used in some papers on proposed DOS prevention attacks (e.g. putting connection requests in one service class, and moving those flows into another service class only when the receiving host signifies it wants to accept them them).

The main problem with actually running fair queueing per source-destination flow is maintaining per-flow state. I believe this still isn't possible at high speeds in today's routers. Therefore, Internet routers still use FIFO. However, QOS schemes that require only a few service classes (and hence fewer flows to maintain state for) have also been proposed.