Network Stability Under Alpha Fair Bandwidth Allocation With General File Size Distribution

• Published in: IEEE transactions on automatic control 2012-03, Vol.57 (3), p.579-591
• Main Authors: Paganini, F., Ao Tang, Ferragut, A., Andrew, L. L. H.
• Format: Article
• Language: English
• Subjects: Allocations; Applied sciences; Asymptotic stability; Computational fluid dynamics; Computer networks; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Dynamical systems; Dynamics; Exact sciences and technology; Fluid flow; Fluids; Internet; Load modeling; Lyapunov method; Mathematical model; Networks; Numerical stability; Partial differential equations; Resource management; Software; Stability analysis; Stochastic processes; Studies
• ISSN: 0018-9286; 1558-2523
• DOI: 10.1109/TAC.2011.2160013

Rate allocation among a fixed set of end-to-end connections in the Internet is carried out by congestion control, which has a well established model: it optimizes a concave network utility, a particular case of which is the alpha-fair bandwidth allocation. This paper studies the slower dynamics of connections themselves, that arrive randomly in the network and are served at the allocated rate. It has been shown that under the condition that the mean offered load at each link is less than its capacity, the resulting queueing system is stochastically stable, for the case of exponentially distributed file-sizes. The conjecture that the result holds for general file-size distributions has remained open, and is very relevant since heavy-tailed distributions are often the best models of Internet file sizes. In this paper, building on existing fluid models of the system, we use a partial differential equation to characterize the dynamics. The equation keeps track of residual file size and therefore is suitable for general file size distributions. For alpha fair bandwidth allocation, with any positive alpha parameter, a Lyapunov function is constructed with negative drift when the offered load is less than capacity. With this tool we answer the conjecture affirmatively in the fluid sense: we prove asymptotic convergence to zero of the fluid model for general file-size distributions of finite mean, and finite-time convergence for those of finite moment. In the stochastic sense, we build on recent work that relates fluid and stochastic stability subject to a certain light-tailed restriction. We further provide the supplementary fluid stability argument to establish the conjecture for this class that includes phase-type distributions. Results are supplemented by illustrative network simulations at the packet level.