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 analysis of stochastic networks—such as data centers, manufacturing lines, or telecommunications—researchers frequently rely on "Heavy Traffic" approximations. When a system is pushed toward its capacity (utilization near 100%), its complex, discrete behavior begins to resemble a smoother, continuous process known as Reflected Brownian Motion (RBM).
While it has been known for decades that the path of a network converges to RBM over time, a significant theoretical gap remained: Does the long-term average (steady-state) of the network actually match the steady-state of the RBM? This paper provides the rigorous proof that it does for Generalized Jackson Networks (GJN).
The Interchange of Limits Problem
The core issue is a classic mathematical "order of operations" problem. In queueing theory, we are often interested in two distinct limits:
- The Steady-State Limit ($t \to \infty$): The behavior of the system after running for a very long time.
- The Heavy Traffic Limit ($n \to \infty$): The behavior as the arrival rate of jobs approaches the service capacity.
For a GJN—a realistic model where arrival and service times can follow various distributions—calculating the steady-state directly is often impossible. Instead, engineers use a shortcut: they take the heavy traffic limit first to derive an RBM, and then analyze the RBM's steady-state. This paper proves that for GJNs, these two operations can be swapped, validating the use of RBM to predict long-term performance in real-world systems.
Methodology
The authors employ a sophisticated toolkit from probability theory to bridge this gap:
- Lyapunov Functions: To prove that the stationary distributions don't "blow up" or drift to infinity as traffic increases (a property called tightness), the authors constructed a linear Lyapunov function based on the "fluid work" in the system.
- Strong Approximations: They used coupling techniques to place the discrete network processes and the continuous Brownian motions on the same probability space, allowing for precise error bounds between the two.
- Tail Probability Bounds: By deriving exponential bounds on the stationary distribution of the GJN, they ensured that the sequence of distributions remained well-behaved enough to converge to the RBM's stationary distribution.
Key Results and Insights
- The Main Result (Theorem 8): The paper formally proves that the rescaled stationary distribution of the GJN converges weakly to the unique stationary distribution of the associated RBM as traffic intensity approaches unity.
- Moment Convergence: The proof extends beyond the shape of the distributions to the moments (such as average queue length or variance). This is crucial for engineering applications where average wait times are the primary metric of interest.
- Validation of the "Snapshot Principle": The results extend to sojourn times (the duration a job stays in the system), validating Reiman’s "snapshot principle" for steady-state systems.
- Product Form (Theorem 12): For networks meeting a "skew symmetry" condition, the authors provide an explicit, simple exponential formula for the limiting steady-state distribution.
Limitations and Future Work
Despite the breakthrough, several areas remain for future exploration:
- Exponential Moment Assumption: The current proof requires interarrival and service times to have "light tails" (finite exponential moments), which does not yet cover "heavy-tailed" distributions common in modern internet traffic.
- Non-Explicit Bounds: While the paper proves convergence exists, it does not provide an explicit rate of convergence to tell an engineer exactly how accurate the approximation is at specific utilization levels (e.g., 95% vs. 99%).
- Multiclass Networks: This study focuses on single-class networks. Extending this to multiclass networks—where different job types have different priorities—remains a significantly harder problem due to potential instabilities even at sub-100% utilization.
Summary updated