To realize the benefits of fair queueing without globally incurring these costs, Stoica et al. propose an "island" based approach in which edge routers implement FQ and core routers (in "stateless core" fashion) infer state from packets annotated at the edge routers. The core queueing algorithm is basically FCFS (FIFO), with a probability (a function of the state and the packet) of dropping the packet before enqueueing. As did Demers et al., the authors begin with a clear description of the kernel of their algorithm in an idealized setting: a bitwise, bufferless router. With knowledge of the outgoing link speed and flow arrival rates, and assuming we can estimate a "fair share" rate, constructing a per-bit drop probability is straightforward. Exponential averaging is used at the edge routers both to estimate aggregate traffic and per-flow rates, and to estimate the link fair rate: all three will be used by the core routers' probabilistic function.
This is a great paper. The island construct, as the authors hint, is very broad: in its most narrow sense, compressed onto every router, it is basically Fair Queueing. At the opposite end of the spectrum, at the endpoints (if we go even further than "all-core", at the ISP boundaries), it begins to resemble flow control generally. Placed where it is in islands of core routers embodies the compromise between fairness and scalability that the paper argues. I would have like to have read more about precisely why packet classification is considered so daunting a task. The extended discussion towards the end of the paper of unfriendly flows, the identification technique as an alternative to the allocation technique, and punishment mechanisms is pretty prophetic.
No comments:
Post a Comment