STATE SPACE COLLAPSE AND DIFFUSION APPROXIMATIONFOR A NETWORK OPERATING UNDER A FAIR BANDWIDTHSHARING POLICY

摘要

We consider a connection-level model of Internet congestion control, in-troduced by Massoulie and Roberts [Telecommunication Systems 15 (2000)185-201], that represents the randomly varying number of flows present ina network. Here, bandwidth is shared fairly among elastic document trans-fers according to a weighted a-fair bandwidth sharing policy introduced byMo and Walrand [IEEE/ACM Transactions on Networking 8 (2000) 556-567][α∈ (0, ∞)].Assuming Poisson arrivals and exponentially distributed docu-ment sizes, we focus on the heavy traffic regime in which the average loadplaced on each resource is approximately equal to its capacity. A fluid model(or functional law of large numbers approximation) for this stochastic modelwas derived and analyzed in a prior work [Ann. Appl. Probab. 14 (2004)1055-1083] by two of the authors. Here, we use the long-time behavior ofthe solutions of the fluid model established in that paper to derive a propertycalled multiplicative state space collapse, which, loosely speaking, showsthat in diffusion scale, the flow count process for the stochastic model can beapproximately recovered as a continuous lifting of the workload process. Under weighted proportional fair sharing of bandwidth (a = 1) and a mildlocal traffic condition, we show how multiplicative state space collapse canbe combined with uniqueness in law and an invariance principle for the diffu-sion [Theory Probab. Appl. 40 (1995) 1-40], [Ann. Appl. Probab. 17 (2007)741-779] to establish a diffusion approximation for the workload process andhence to yield an approximation for the flow count process. In this case, theworkload diffusion behaves like Brownian motion in the interior of a polyhe-dral cone and is confined to the cone by reflection at the boundary, where thedirection of reflection is constant on any given boundary face. When all ofthe weights are equal (proportional fair sharing), this diffusion has a productform invariant measure. If the latter is integrable, it yields the unique station-ary distribution for the diffusion which has a strikingly simple interpretationin terms of independent dual random variables, one for each of the resources of the network. We are able to extend this product form result to the casewhere document sizes are distributed as finite mixtures of exponentials andto models that include multi-path routing. We indicate some difficulties re-lated to extending the diffusion approximation result to values of α≠1. We illustrate our approximation results for a few simple networks. In par-ticular, for a two-resource linear network, the diffusion lives in a wedge thatis a strict subset of the positive quadrant. This geometrically illustrates theentrainment of resources, whereby congestion at one resource may preventanother resource from working at full capacity. For a four-resource networkwith multi-path routing, the product form result under proportional fair shar-ing is expressed in terms of independent dual random variables, one for eachof a set of generalized cut constraints.