Qualitative properties of $\alpha$-fair policies in bandwidth-sharing networks

Devavrat Shah, John N. Tsitsiklis, Yimin ZhongThe Annals of Applied Probability 2014 · DOI

Abstract

This paper investigates the flow-level dynamics of communication networks operating under $\alpha$-fair bandwidth-sharing policies. While the stability of such networks is well-established for loads below capacity, this work provides a deeper qualitative analysis of both transient and steady-state behaviors. For $\alpha \geq 1$, we derive bounds on the maximum number of flows over a finite horizon and establish full state space collapse. For all $\alpha > 0$, we provide explicit exponential tail bounds for the steady-state distribution using a normed Lyapunov function. Finally, we validate the diffusion approximation for the case of proportional fairness ($\alpha = 1$) under local traffic conditions.

Introduction

In modern communication networks, bandwidth-sharing policies dictate how resources are allocated among competing flows. The family of $\alpha$-fair policies, introduced by Roberts and Massoulié, provides a versatile framework that encompasses proportional fairness ($\alpha=1$) and max-min fairness ($\alpha \to \infty$). While these policies are known to be stable under sub-critical loads, engineering robust networks requires a more granular understanding of flow-level fluctuations.

This research addresses three critical gaps: characterizing transient spikes in flow counts, determining the probability of extreme congestion in steady state, and justifying the use of continuous diffusion approximations to model discrete, stochastic network behavior.

Methodology: The Power of Normed Lyapunov Functions

The core of the analysis relies on Lyapunov drift conditions, a standard technique for proving the stability of stochastic processes. However, traditional approaches often employ quadratic Lyapunov functions, which are insufficient for deriving tight tail bounds in this context.

The authors introduce a normed Lyapunov function—a function that scales linearly, similar to a weighted norm. This function possesses Lipschitz continuity, which allows for the application of advanced probabilistic tools, such as Hajek’s results on hitting times. For transient analysis, the authors combine Lyapunov drift inequalities with an extension of Doob’s maximal inequality for supermartingales to bound the "maximal excursion" (the largest spike in flow counts) over a finite time horizon.

Transient Behavior and State Space Collapse

A significant contribution of this work is the transition from "multiplicative" to full state space collapse for $\alpha \geq 1$. State space collapse occurs when the multi-dimensional state of a network (the number of flows on every route) effectively concentrates near a lower-dimensional manifold defined by the network's constraints. This provides a much tighter characterization of network behavior than previous models.

Theorem 3.1 provides a formal bound on the maximum number of flows $N^*(T)$ over a time horizon $T$. For $\alpha \geq 1$, the probability that $N^*(T)$ exceeds a threshold $b$ is bounded by: $$P(N^*(T) > b) \leq \frac{KT}{\epsilon^{\alpha-1} b^{\alpha+1}}$$ where $\epsilon$ represents the capacity margin. This result ensures that the network state remains tightly controlled even during transient periods.

Steady-State Analysis and Tail Bounds

In the long run, the steady-state distribution of flows determines the frequency of congestion events. By utilizing the normed Lyapunov function, the authors prove that the steady-state number of flows exhibits exponential tails for any $\alpha > 0$.

Theorem 3.2 establishes that the probability of the flow count exceeding a high threshold decays exponentially. This implies that all moments of the steady-state distribution are finite, ruling out "heavy-tailed" behavior that could lead to unpredictable and frequent outages. The decay exponent is shown to be proportional to the load factor $(1 - L(\rho))$, matching the intuitive behavior of simpler queueing systems.

Bridging the Gap: Diffusion Approximations

A long-standing challenge in heavy-traffic theory is the "interchange of limits" problem: whether the steady state of a sequence of discrete models actually matches the steady state of the continuous "diffusion approximation" used in heavy-traffic theory.

This paper provides a definitive answer for the case of proportional fairness ($\alpha=1$). Under a "local traffic" condition—where each resource serves some traffic exclusive to it—the authors validate the diffusion approximation developed by Kang et al. This justifies the use of continuous Brownian motion models to predict the long-term behavior of complex, discrete flow-level networks.

Conclusion and Future Directions

This work provides a rigorous mathematical foundation for $\alpha$-fair policies, offering tighter bounds and more robust theoretical justifications for network performance metrics. However, several areas for future research remain:

  • Generalizing Diffusion Approximations: Extending the steady-state validity of diffusion approximations to cases where $\alpha \neq 1$.
  • Topology Constraints: Relaxing the "local traffic" technical condition to encompass more general network architectures.
  • Non-Exponential Workloads: Moving beyond the assumption of exponentially distributed flow sizes to accommodate more realistic, general traffic distributions (non-Poisson arrivals).

By bridging the gap between discrete flow models and continuous approximations, this research provides essential tools for the design and analysis of fair, efficient communication networks.

Summary updated

Abstract

We consider a flow-level model of a network operating under an $\alpha$-fair bandwidth sharing policy (with $\alpha>0$) proposed by Roberts and Massoulié [Telecomunication Systems 15 (2000) 185–201]. This is a probabilistic model that captures the long-term aspects of bandwidth sharing between users or flows in a communication network. We study the transient properties as well as the steady-state distribution of the model. In particular, for $\alpha\geq1$, we obtain bounds on the maximum number of flows in the network over a given time horizon, by means of a maximal inequality derived from the standard Lyapunov drift condition. As a corollary, we establish the full state space collapse property for all $\alpha\geq1$. For the steady-state distribution, we obtain explicit exponential tail bounds on the number of flows, for any $\alpha>0$, by relying on a norm-like Lyapunov function. As a corollary, we establish the validity of the diffusion approximation developed by Kang et al. [Ann. Appl. Probab. 19 (2009) 1719–1780], in steady state, for the case where $\alpha=1$ and under a local traffic condition.
BibTeX
@article{shah2014qualitative,
  author = {Devavrat Shah and John N. Tsitsiklis and Yimin Zhong},
  title = {{Qualitative properties of $\textbackslash\{\}alpha$-fair policies in bandwidth-sharing networks}},
  journal = {The Annals of Applied Probability},
  year = {2014},
  doi = {10.1214/12-aap915},
}
Figure