Validity of Heavy Traffic Steady-State Approximations in Open Queueing Networks

David Gamarnik, Assaf Zeevi

Abstract

We consider a single class open queueing network, also known as a generalized Jackson network (GJN). A classical result in heavy traffic theory asserts that the sequence of normalized queue length processes of the GJN converge weakly to a reflected Brownian motion (RBM) in the orthant, as the traffic intensity approaches unity. However, barring simple instances, it is still not known whether the stationary distribution of RBM provides a valid approximation for the steady-state of the original network. In this paper we resolve this open problem by proving that the re-scaled stationary distribution of the GJN converges to the stationary distribution of the RBM, thus validating a so-called “interchange-of-limits” for this class of networks. Our method of proof involves a combination of Lyapunov function techniques, strong approximations and tail probability bounds that yield tightness of the sequence of stationary distributions of the GJN.

Introduction

In the study of queueing systems, Generalized Jackson Networks (GJN) represent a significant class of models where arrival and service times can follow arbitrary distributions. While classical Jackson networks—which assume exponential distributions—offer elegant "product-form" solutions for steady-state behavior, GJNs are often mathematically intractable. To analyze these complex systems, researchers frequently turn to heavy traffic theory.

A foundational result in this field, established by Reiman (1984), demonstrates that as a network's traffic intensity approaches capacity ($n \to \infty$), the queue length process converges to a Reflected Brownian Motion (RBM). However, a critical theoretical gap remained: does the long-term steady-state of the actual network converge to the steady-state of the RBM approximation?

The Interchange of Limits Problem

The core challenge addressed in this research is the "interchange-of-limits" problem. As illustrated in Figure 1, there are two distinct paths to analyzing a network's behavior under heavy traffic:

  1. Process Limit then Steady State: First, take the heavy traffic limit ($n \to \infty$) to obtain the RBM process $Z(t)$, then find its stationary distribution $Z(\infty)$.
  2. Steady State then Heavy Traffic Limit: First, find the stationary distribution of the actual network $Q^n(\infty)$, then take the heavy traffic limit ($n \to \infty$).
Figure 1: The commuting diagram for the interchange of limits in heavy traffic theory.

Proving that these two paths lead to the same result is essential for validating the use of RBM-based steady-state approximations in real-world engineering and operations research. Without this proof, such approximations remain heuristic.

Methodology

The authors establish this convergence through a rigorous framework involving three primary pillars:

  • Lyapunov Functions: The proof utilizes a "fluid-scale" linear Lyapunov function based on the network's workload. This function allows the researchers to characterize system stability and derive necessary tail probability bounds.
  • Strong Approximations: Coupling techniques are employed to bound the deviation between discrete stochastic processes (arrivals and services) and their continuous Brownian counterparts.
  • Tightness Arguments: The most significant technical hurdle was proving "tightness"—ensuring that the sequence of stationary distributions does not "escape to infinity" as traffic intensity nears 1. Establishing tightness guarantees the existence of a weak limit, which is then identified as the unique stationary distribution of the RBM.

It is important to note that this proof assumes the existence of finite conditional exponential moments for arrival and service times. While stricter than the standard finite second-moment requirement, this assumption is crucial for deriving the exponential tail bounds needed for the proof.

Key Results

The paper provides several landmark results for queueing theory:

  • Theorem 8 (Main Result): Formally proves that the re-scaled stationary distribution of a GJN converges weakly to the unique stationary distribution of the associated RBM as traffic intensity approaches unity.
  • Uniform Integrability (Corollary 2): Establishes that the $p$-th moments (e.g., mean, variance) of the normalized queue lengths also converge to the moments of the RBM.
  • Snapshot Principle Validation: The results extend to "sojourn times" (the time a job spends in the system), validating Reiman’s "snapshot principle" for steady-state conditions.
  • Explicit Product-Forms (Theorem 12): Provides an explicit product-form expression for the limiting steady-state distribution in cases satisfying a "skew symmetry" condition.

Limitations and Future Directions

While this work resolves a major open problem, it also highlights areas for further research. The requirement for exponential moments is a strong condition; future work may adapt the Lyapunov approach to provide polynomial tail bounds under weaker moment assumptions. Additionally, the proof relies on the Lipschitz continuity of the Skorohod mapping, which currently limits its application to more complex "multiclass" networks. Finally, while convergence is proven, deriving explicit error bounds for practitioners operating at sub-heavy traffic loads (e.g., 80-90% capacity) remains an ongoing challenge.

Summary updated

Abstract

We consider a single class open queueing network, also known as a generalized Jackson network (GJN). A classical result in heavytraffic theory asserts that the sequence of normalized queue length processes of the GJN converge weakly to a reflected Brownian motion (RBM) in the orthant, as the traffic intensity approaches unity. However, barring simple instances, it is still not known whether the stationary distribution of RBM provides a valid approximation for the steady-state of the original network. In this paper we resolve this open problem by proving that the re-scaled stationary distribution of the GJN converges to the stationary distribution of the RBM, thus validating a so-called “interchange-of-limits” for this class of networks. Our method of proof involves a combination of Lyapunov function techniques, strong approximations and tail probability bounds that yield tightness of the sequence of stationary distributions of the GJN.
BibTeX
@article{gamarnik2006validity,
  author = {David Gamarnik and Assaf Zeevi},
  title = {{Validity of Heavy Traffic Steady-State Approximations in Open Queueing Networks}},
  journal = {The Annals of Applied Probability},
  year = {2006},
  doi = {10.1214/105051605000000638},
}
Figure