Exact sampling for some multi-dimensional queueing models with renewal input

José Blanchet, Yanan Pei, Karl SigmanAdvances 2019 · DOI · arXiv

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

Abstract

Abstract Using a result of Blanchet and Wallwater (2015) for exactly simulating the maximum of a negative drift random walk queue endowed with independent and identically distributed (i.i.d.) increments, we extend it to a multi-dimensional setting and then we give a new algorithm for simulating exactly the stationary distribution of a first-in–first-out (FIFO) multi-server queue in which the arrival process is a general renewal process and the service times are i.i.d.: the FIFO GI/GI/ c queue with $ 2 \leq c \lt \infty$ . Our method utilizes dominated coupling from the past (DCFP) as well as the random assignment (RA) discipline, and complements the earlier work in which Poisson arrivals were assumed, such as the recent work of Connor and Kendall (2015). We also consider the models in continuous time, and show that with mild further assumptions, the exact simulation of those stationary distributions can also be achieved. We also give, using our FIFO algorithm, a new exact simulation algorithm for the stationary distribution of the infinite server case, the GI/GI/ $\infty$ model. Finally, we even show how to handle fork–join queues, in which each arriving customer brings c jobs, one for each server.
BibTeX
@inproceedings{blanchet2019exact,
  author = {José Blanchet and Yanan Pei and Karl Sigman},
  title = {{Exact sampling for some multi-dimensional queueing models with renewal input}},
  booktitle = {Advances},
  year = {2019},
  doi = {10.1017/apr.2019.45},
}
Figure