Nalanda

Citation: Stoica, I., Shenker, S., and Zhang, H. 1998. Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks. SIGCOMM Comput. Commun. Rev. 28, 4 (Oct. 1998), 118-130. DOI= http://doi.acm.org/10.1145/285243.285273

This paper presents Core-Stateless Fair Queueing (CSFQ) an approach to implementing fairness in queueing, but without the expensive per-flow state that algorithms such as Fair Queueing require. Rather, the authors take advantage of network topology, implementing a distributed mechanism which can assure a reasonable approximation of fairness within an island of routers. To do this, they distinguish between edge routers and core routers in the island, having each perform different roles. Edge routers maintain per-flow state and insert per-flow information into packet headers, while core routers use this information in combination with aggregate knowledge of overall traffic flows to make probabilistic decisions about whether or not to drop packets. This approach recalls Chiu and Jain’s paper, as it seems to be a relaxation of the distributedness criterion that they introduced, which allows a separation of concerns between edge and core routers, and but also therefore requires some knowledge of network topology.

An initial prototype of an algorithm for estimation of the rates of individual flows, and the fair share of bandwidth on the output link, is presented: first as a bit-wise fluid model, and then generalised to handle packets by incorporating packet lengths. This algorithm is provided as a starting point; as the authors say, the overall intent of the paper is to present the concept of this new architecture. Using this algorithm, packets entering the island are labelled with their flow rates by the edge routers before they are forwarded on to the core routers. Particularly interesting was the discussion of how any estimation algorithm can be exploited, and how this one is vulnerable in the short run to flows attempting to gain more than their fair share of bandwidth, but is robust over longer time scales.

Inherent to this architecture is an assumption of trust within the island of routers. The authors suggest that islands would typically be restricted to the bounds of an ISP’s network, but given a degree of trust between ISPs, could extend across the bounds of cooperating ISPs’ networks. This does beg the question, though, of managing the complexity under such conditions; as we saw in our discussion of BGP, both the potential for misconfiguration as well as market conditions may well militate against such cooperation.

CSFQ is compared against a variety of other queueing algorithms - including FIFO, RED, FRED and DRR - in simulations to evaluate its efficacy. Of these, FRED and DRR attempt to provide a degree of fairness, while FIFO and RED do not. As the authors point out, CSFQ strikes a balance between these algorithms: edge routers have a complexity comparable to FRED, while core routers are more comparable to RED. The results indicate that CSFQ is closer in fairness to DRR, while its performs similarly to, and even outperforms, FRED in some cases.

The paper concludes with a discussion of why the authors believe fair bandwidth allocations are of overriding importance. They point out that end-to-end congestion control, such as that used in TCP, while successful, is based on the assumptions that flows are cooperative, and that the congestion control algorithms implemented by flows exhibit homogeneous behaviour. The authors’ assumption in writing this paper is that mechanisms are required to address the case where flows do not honour these assumptions, which they term the “unfriendly flow problem”. In their evaluation of approaches to identifying unfriendly flows, they conclude that the allocation approach, which they adopt, is the only currently (c. 1998) viable one. It would be interesting to revisit their analysis of fire-hose flows in today’s context of real-time VOIP and live video streams.

I enjoyed reading this paper for its analysis of the tradeoffs between engineered and ideal solutions, i.e., how some knowledge of network topology can help build a more realizable solution. I especially liked it as part of the sequence that we’ve already read, as it helps provides a unified picture of a particular trajectory of research; an insight into the process of how old research problems are addressed, and new ones uncovered.