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.