FLUID AND BROWNIAN APPROXIMATIONS FOR AN INTERNET CONGESTION CONTROL MODEL

W. Kang, F. P. Kelly, N. H. Lee and R. J. Williams
Abstract
We consider a stochastic model of Internet congestion control that represents the randomly varying number of flows present in a network where bandwidth is shared fairly amongst elastic document transfers. We focus on the heavy traffic regime in which the average load placed on each resource is approximately equal to its capacity. We first describe a fluid model (or functional law of large numbers approximation) for the stochastic model. We use the long time behavior of the solutions of this fluid model to establish a property called (multiplicative) state space collapse, which shows that in diffusion scale the flow count process can be approximately recovered as a continuous lifting of the workload process. Under proportional fair sharing of bandwidth and a mild condition, we show how state space collapse can be combined with a new invariance principle to establish a Brownian model as a diffusion approximation for the workload process and hence to yield an approximation for the flow count process. The workload diffusion behaves like Brownian motion in the interior of a polyhedral cone and is confined to the cone by reflection at the boundary, where the direction of reflection is constant on any given boundary face. We illustrate this approximation result for a simple linear network. Here the diffusion lives in a wedge that is a strict subset of the positive quadrant. This geometrically illustrates the entrainment of resources, whereby congestion at one resource may prevent another resource from working at full capacity.
Proceedings of the 43rd IEEE Conference on Decision and Control, December 2004, 3938-3943. For a copy of a preprint, for personal scientific non-commercial use, click here for postscript or here for pdf.
Last updated August 4, 2006.