School Seminars and Colloquia

FLUID AND BROWNIAN MODELS OF CONGESTION AT FLOW LEVEL

Complex Systems

by Prof R. J. Williams


Institution: University of California at San Diego
Date: Fri 10th September 2004
Time: 3:15 PM
Location: Theatre 2, Ground Floor, ICT Building (111 Barry St, Carlton)

Abstract: We consider a stochastic model of congestion control, introduced by Massoulie and Roberts, 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. Under an additional condition on the parameters, this diffusion has a product form invariant distribution. We illustrate the diffusion approximation result for a simple linear network. Here the diffusion lives in a cone that is a strict subset of the positive orthant. This geometrically illustrates the entrainment of resources, whereby congestion at some resources may prevent other resources from working at full capacity.

This talk is based on joint work with Frank Kelly, Weining Kang and Nam Lee.

For More Information: Emma Lockwood: http://www.complex.org.au Tel: +61 3 8344 1617, Email: emmal@ms.unimelb.edu.au