Introduction
In queueing theory, understanding the "steady state" or stationary distribution of a system is critical for capacity planning and performance analysis. Traditionally, researchers have relied on Markov Chain Monte Carlo (MCMC) methods or long-run simulations to estimate these distributions. However, these methods suffer from "initialization bias," where the simulation's starting state influences the results for an unknown duration, necessitating a "warm-up" period. This paper presents a breakthrough in exact sampling (or perfect simulation) for the $GI/GI/c$ queue, providing a method to generate samples guaranteed to be drawn from the true stationary distribution without the need for a warm-up phase.
The Challenge of General Renewal Arrivals
While exact sampling has been previously achieved for systems with Poisson arrivals ($M/G/c$), general renewal processes ($GI$)—where the time between arrivals follows an arbitrary distribution—present significant mathematical hurdles. In these multi-server environments, the lack of the memoryless property makes it difficult to determine when a simulation has truly converged. This paper extends the work of Blanchet and Wallwater (2015) to a multi-dimensional setting to solve this problem for First-In-First-Out (FIFO) queues with $c$ servers ($2 \leq c < \infty$).
Methodology: Coupling and Bounding
The authors' approach rests on several sophisticated probabilistic techniques designed to "trap" the stationary state:
1. Dominated Coupling from the Past (DCFP)
DCFP is a technique that simulates a process backwards into the past. By identifying a point in history where the system's state at time zero becomes independent of its starting conditions, researchers can produce a perfectly stationary sample.
2. The Random Assignment (RA) Bound
A key innovation is the use of the Random Assignment discipline. In an RA model, arriving customers are assigned to one of $c$ servers at random rather than waiting for the next available server. The authors prove that the RA model acts as a "sample-path upper bound" for the standard FIFO system. Because the RA model is mathematically more tractable, it can be used to "dominate" or constrain the more complex FIFO process.
3. Multi-dimensional Random Walks
To implement the DCFP, the authors extended algorithms for simulating the maximum of negative-drift random walks into multiple dimensions. This allows for the simulation of the RA bounding process in reverse time, identifying the necessary "milestones" to ensure coalescence.
4. The Sandwiching Algorithm
To optimize efficiency, the authors employ a sandwiching technique. They simulate an upper-bound process (the RA model) and a lower-bound process (starting from an empty state). When these two processes meet—or "coalesce"—the state of the true FIFO queue is trapped between them, yielding an exact sample.
Key Results and Performance
The proposed algorithm is not only mathematically rigorous but also computationally efficient. The authors validated their method using synthetic simulations in Matlab and compared them against known benchmarks for $M/M/c$ and Erlang-distributed queues.
- Efficiency Gains: In high-traffic scenarios (intensity $\rho/c = 0.9$), the new sandwiching algorithm demonstrated a nearly 10x improvement over previous "vacation-based" exact sampling methods. For instance, the new method required simulating approximately 1,521 arrivals to reach coalescence, compared to 12,277 arrivals for older techniques.
- Versatility: Beyond the standard $GI/GI/c$ model, the paper demonstrates that this framework can be adapted for infinite-server models ($GI/GI/\infty$) and fork-join queues, where a single arrival triggers multiple jobs across all servers.
Limitations and Future Directions
Despite its robustness, the algorithm has specific requirements. It assumes that the service time distribution has a finite moment slightly greater than 2 ($E(S^{2+\epsilon}) < \infty$), which may limit its application for extremely heavy-tailed distributions. Additionally, while the method is efficient for a moderate number of servers, the computational complexity of $c$-dimensional random walks increases as the server count grows.
Future research may focus on extending these exact sampling techniques to more complex networks of multi-server queues, moving beyond single-station models to entire system architectures.
Summary updated