Fair queuing (FQ) has important advantages over first-come-first-serve (FCFS) packet routing, but comes at a cost: FQ requires considerably more state and per-packet computation than FCFS. This paper proposes “core-stateless fair queuing” (CSFQ) to solve this problem—the goal is to approximate the fairness offered by FQ at a much-reduced computational cost.
The paper begins by describing a simple probabilistic dropping scheme that approximates a fair allocation of bandwidth. The scheme requires calculating two variables:
- the “fair share rate” is the maximum per-flow output rate allowed by a fair bandwidth allocation; flows whose arrival rate exceeds the fair share rate will have data dropped in a fair queueing scheme
- the arrival rate of each flow
The essence of the probabilistic dropping scheme is to drop data from a flow with a probability proportional to the difference between each flow’s arrival rate and the fair share rate. That is, the more that a flow’s input rate exceeds the “fair” rate, the more likely that data belonging to that flow will be dropped.
To implement this scheme in practice, packets must be annotated with three pieces of data:
- The flow to which the packet belongs
- The current arrival rate of the flow
- The current fair share rate
The paper proposes an architecture of “islands,” in which “edge routers” label incoming packets with this data, and “core routers” use the labels to apply the probabilistic dropping scheme. This pushes more work to the edge routers: labeling packets requires classifying packets into flows, which is expensive. In contrast, all the information required by the core routers is directly available from the packet labels. This architecture assumes that edge routers operate at a slower speed, because they are connected to a relatively slow link; therefore core routing throughput is likely to be the bottleneck, which is what this paper optimizes for.
The paper then discusses how the edge routers can approximate the per-flow arrival rate and the fair share rate, and then validates the approach with a detailed simulation.
I liked the honesty of the paper’s introduction: they were careful to state that it isn’t clear whether fair allocation is even important, or whether FQ is in fact too expensive to implement on core routers.
It seems clumsy to me to divide the work the between “edge routers” and “core routers” in such a fixed way — there might be many networks in which the bottlenecks are not as envisioned by this paper. For example, perhaps the edge routers are underprovisioned, so they don’t have a lot of spare computational capacity. Or perhaps there is not such a neat distinction between “edge routers” on slow links and “core routers” on fast links. In such a network, a more equal division of work among the routers might be more desirable: e.g. you could partition the flows among the routers, assigning some routers to label packets for flow X and other routers to label packets for flow Y. It would be interesting to explore a generalization of this work in which the workload could be shifted dynamically among the routers.
I thought this paper was a nice piece of technical work: given a pretty simple idea, their analysis was careful and precise, and their simulations were rigorous. It is somewhat limited in scope, but nevertheless worth keeping in the syllabus.