Stability and Fairness of Explicit Congestion Control with Small Buffers

Frank Kelly, Gaurav Raina, and Thomas Voice
Appears in: 
CCR July 2008

Rate control protocols that utilise explicit feedback from routers are able to achieve fast convergence to an equilibrium which approximates processor-sharing on a single bottleneck link, and hence such protocols allow short flows to complete quickly. For a network, however, processor-sharing is not uniquely defined but corresponds with a choice of fairness criteria, and proportional fairness has a reasonable claim to be the network generalization of processor-sharing.

In this paper, we develop a variant of RCP (rate control protocol) that achieves alpha-fairness when buffers are small, including proportional fairness as the case alpha = 1. At the level of theoretical abstraction treated, our model incorporates a general network topology, and heterogeneous propagation delays. For our variant of the RCP algorithm, we establish a simple decentralized sufficient condition for local stability.

Public Review By: 
Darryl Veitch

This paper is a pleasure to read, a clearly written and solid contribution to the literature on flow/congestion control in networks. It is centered about the Rate Control Protocol (RCP) class, where explicit router feedback, incorporating both rate mis-match and queue size information, is passed to sources to promote fast convergence according to a chosen rate allocation scheme. The distinction between this work and prior work on RCP is first of all on the chosen sub-class: the consideration of alpha-fair rate allocation together with a focus on the small buffer regime.
Using both analysis and discrete simulations the paper makes a number of contributions, including introducing a new variant based on a coarser view of queueing dynamics with provable stability even in a general network topology, insight into the effects of excluding queue size terms from the dynamics, and a new idea on how the hunt for equilibrium following the introduction of new flows can be ‘kick started,’ thereby avoiding the disadvantages of slow start approaches or transients damaging to performance.
It is extremely important, when introducing new variants of protocols, to motivate the suggested changes well, otherwise our conferences and journals will be littered with a bewildering variety of variations which will not only be hard to distinguish from each other, but many may not make sense.
The paper does a good job of this. First, it motivates the replacement of detailed queue size dynamics by an average queue size by noting that when buffers are small compared to rates, we cannot hope to control queue size in any case. This simplifies the equations, and probably contributes to their stability as well, which would in turn assist in the relevance of the continuous time theory to the ‘real’ discrete dynamics. Second, the adoption of alpha-fairness is not only well motivated in terms of its documented good properties, it is also a parametric class which includes other choices such as max-min as special cases, constituting therefore not so much a variant as a generalization. Moreover, the investigation of the case where queue size feedback is removed altogether is again not an ad-hoc variation, but merely a special case of the parameters controlling the class under study.
There are two comments regarding the broader picture which are worth noting. First, even though the paper is about “explicit rate control,” mathematically the model is essentially the same as a conventional TCP/AQM model where the resources adjust prices and the sources adjust rates. Second, since RCP is to some extent defined by the introduction of a queue size term into the rate-based feedback, the conclusion that better performance can be achieved by dropping such terms makes one wonder if this work should really be called a ‘RCP variant.’ Of course, more work is certainly needed before one could conclude that queue size terms are inadvisable, and under what circumstances.