Nalanda

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.