Structural properties of proportional fairness: stability and insensitivity

Abstract

In this article we provide a novel characterization of the proportionally fair bandwidth allocation of network capacities, in terms of the Fenchel--Legendre transform of the network capacity region. We use this characterization to prove stability (i.e., ergodicity) of network dynamics under proportionally fair sharing, by exhibiting a suitable Lyapunov function. Our stability result extends previously known results to a more general model including Markovian users routing. In particular, it implies that the stability condition previously known under exponential service time distributions remains valid under so-called phase-type service time distributions. We then exhibit a modification of proportional fairness, which coincides with it in some asymptotic sense, is reversible (and thus insensitive), and has explicit stationary distribution. Finally we show that the stationary distributions under modified proportional fairness and balanced fairness, a sharing criterion proposed because of its insensitivity properties, admit the same large deviations characteristics. These results show that proportional fairness is an attractive bandwidth allocation criterion, combining the desirable properties of ease of implementation with performance and insensitivity.

Published at http://dx.doi.org/10.1214/105051606000000907 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Fluid model for a network operating under a fair bandwidth-sharing policy

Cited by in corpus (20)

• State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy
• Interacting multi-class transmissions in large stochastic networks
• Fluid limits for networks with bandwidth sharing and general document size distributions
• Spatial Birth-Death Wireless Networks
• Proportional fairness and its relationship with multi-class queueing networks
• Generalized Proportional Allocation Policies for Robust Control of Dynamical Flow Networks
• Fairness in overloaded parallel queues
• On rate of convergence for infinite server Erlang-Sevastyanov's problem
• Network stability under max--min fair bandwidth sharing
• On the Well-Posedness of Dynamical Flow Networks With Feedback-Controlled Outflows
• Large deviations of the stationary measure of networks under proportional fair allocations
• Heavy-Traffic Insensitive Bounds for Weighted Proportionally Fair Bandwidth Sharing Policies
• Proportional switching in FIFO networks
• Stability Properties of Networks with Interacting TCP Flows
• Centralized Congestion Control and Scheduling in a Datacenter
• Stability of multi-dimensional birth-and-death processes with state-dependent 0-homogeneous jumps
• Store-Forward and its implications for Proportional Scheduling
• Stability of MaxWeight-(α,g)
• Processor Sharing Queues with Impatience
• Fluid Limits for Bandwidth-Sharing Networks with Rate Constraints