I. Stoica, S. Shenker, H. Zhang, “Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks,” ACM SIGCOMM, (August 1998). [PDF]
Summary
Fair resource (bandwidth, buffer etc.) allocation algorithms (e.g., Fair Queueing) in routers usually need to manage large number of states, buffers, and has to do packet scheduling on a per flow basis which makes it economically infeasible to implement them on production routers. This paper proposes an architecture that significantly reduces the overheads by completely eliminating per-flow states from the core routers, yet manages to achieve approximately fair bandwidth allocation. The end result is a simplified queueing algorithm that provides performance comparable to its counterparts, but is better suited for incremental deployment in the existing Internet.
The authors question the necessity, complexity, and adaptabilty of fair allocation allocation mechanisms and base their contributions on two basic assumptions:
- Fair allocation is necessary, or at least important, for congestion control, and
- Complexity of then-existing fair allocation schemes is a substantial hindrance to their adoption.
In its core, CSFQ (Core-Stateless Fair Queueing) divides the whole Internet into islands of routers. Each island is considered to have edge routers that maintain per-flow states and label packets with fair rates as they enter in an island; whereas, core routers process packets based on the labels attached by the edge routers using FIFO queueing in conjunction with probabilistic dropping. Two primary challenges in this mechanism is to estimate arrival rates for labeling and to estimate fair share based on arrival rates. CSFQ uses aggregate based estimates using exponential averaging for both cases and uses heuristics to fix possible discrepancies in estimations. Finally, when packets leave an island labels are rewritten with updated fair rates. Theoretical bounds and detailed algorithms can be found in the paper.
Through simulations, CSFQ is shown to be performing better than simplistic FIFO and RED, in par with FRED, and worse than more complex and state-full DRR. However, the authors seem undecided about what to make of the outcomes!
In the end, the authors discuss problems with unfriendly/malicious flows, two possible approaches (allocation and identification) to handle them, and end up proposing a penalizing scheme for unfriendliness which is a compound of (first) allocation and (then) identification approaches.
Critique
This paper is a great read in terms of concept, delivery, clarity, and mostly honesty of the authors. However, it is not comforting to find that the authors are undecided about almost everything discussed in the paper!
The simulation section is rigorous and impressive. Even though they mention several times that they couldn’t put everything for the lack of space, the authors end up with providing a pretty much full-proof simulation results.
The use and derivation of the heuristic to adjust estimations seemed arbitrary. There is no clear reasoning about how the authors came up with those certain constants and percentages.
One of the assumptions, considered as an architectural consideration, in the paper is: “all packets in the same flow must follow the same path within the core of an island“. How valid is that?
In the current Internet, the vast majority of packets do indeed follow the same path. This was not so true in the time frame of the mid-90s as the flaws — mostly in the implementation — of BGP were being tracked down. It is not an unreasonable assumption, although it would have been nice to evaluated the effect of it being incorrect on the results.