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.

Citation: Demers, A., Keshav, S., and Shenker, S. 1989. Analysis and simulation of a fair queueing algorithm. In Symposium Proceedings on Communications Architectures & Protocols (Austin, Texas, United States, September 25 - 27, 1989). SIGCOMM ‘89. ACM, New York, NY, 1-12. DOI= http://doi.acm.org/10.1145/75246.75248

This paper presents and evaluates a technique for managing congestion control at gateways, rather than at sources. The paper’s focus is on queueing algorithms, since it is these which determine how packets from different sources interact with one another, and therefore contribute directly towards the “collective behaviour” of the collection of sources and gateways in a network.

The paper describes the fair queueing (FQ) algorithm, comparing it to the first-come-first-served (FCFS) queueing algorithm. FCFS pushes out packets on a first-come-first-served basis regardless of packet length, or the rate of packet ingress, resulting in greedy sources being favoured. FQ provides an elegant remedy to the problem of packet length: estimate the time at which a packet will finish transmission based on its arrival time and packet length, and dispatch packets with earlier estimated finish times. This allows for ordering of packets by time (like FCFS), while simultaneously favouring small packets over large. Additionally, FQ includes a mechanism to provide more promptness to sources using less than their fair share of bandwidth.

Through a series of simulations, the authors illustrate the differences in behaviour between FCFS and FQ gateways. These simulations illustrate two principal problems when using FCFS: unfair allocation of bandwidth (greedy sources are favoured), and a penalty applied to sources implementing smarter flow control mechanisms (i.e., that described by Jacobson and Karels). FQ, on the other hand, maintains fair allocation even under congested conditions, penalizing bandwidth hogs, and favours smart flow control sources over generic sources.

There may be one condition under which FQ will fail. What if a source is sending a number of small packets at a very high rate? For instance, a DoS SYN flood. From my reading of this paper, it seems as though FQ may fail to identify this kind of source as being badly behaved.

I found this paper really useful, especially as it addressed some of the questions that I raised with respect to other papers we’ve been reading: how well would these congestion avoidance algorithms function in the presence of badly-behaved sources? The FQ algorithm addresses this problem head-on, penalizing badly-behaved sources at the gateway, and favouring well-behaved ones. I was particularly intrigued by their reference to Nagle’s game theoretic work on how gateways might be redesigned to encourage good source behaviour.