Perfect sampling for infinite server and loss systems

José Blanchet, Jing Dong

TL;DR

This paper introduces the first exact simulation algorithms for the steady-state distribution of non-Markovian loss systems, a significant advancement for analyzing complex queueing networks. The authors achieve this by cleverly using a variation of "Dominated Coupling From The Past" and analyzing the performance in heavy-traffic regimes, demonstrating sub-exponential complexity and near-optimal convergence rates in certain scenarios.

What Problem Does This Paper Address?

Analyzing the steady-state behavior of complex queueing systems, particularly those with non-Markovian arrival or service times and a large number of servers (many-server systems), is a challenging problem. Traditional simulation methods can be biased or computationally intractable. Specifically, for "loss systems" (where exceeding capacity leads to lost customers), obtaining unbiased samples from the steady-state distribution has been difficult, especially in heavy-traffic conditions where the system is near capacity. Existing exact simulation techniques like Coupling From The Past (CFTP) often require strong assumptions (e.g., geometric ergodicity) or are limited to simpler models. This paper aims to bridge this gap by developing exact simulation algorithms for non-Markovian loss networks, with a focus on performance analysis in heavy-traffic scenarios.

Methods

The core of the paper's methodology lies in a variation of Dominated Coupling From The Past (DCFTP). The general idea of DCFTP is to simulate a "dominating" process (an upper bound) backwards in time from stationarity, and then use this to reconstruct the process of interest.

Here's a breakdown of their approach:

  • Infinite Server Queue as a Dominating Process: They use a stationary infinite server queue (GI/GI/∞) as an upper bound for the loss system. This is a crucial choice because in an infinite server queue, no customer is ever lost, making it a natural upper bound for a loss system.
  • Backward Simulation: The simulation is performed by running the infinite server queue process backwards in time. This is a standard technique in CFTP-based methods to find a common ancestor state.
  • Coalescence Detection: A key innovation is how they detect "coalescence." This is the point in time (going backwards) where the state of the loss system can be perfectly identified from the state of the infinite server queue. They achieve this by finding a time $\tau$ such that the infinite server queue has fewer than $C$ customers (where $C$ is the number of servers in the loss system) over a specific interval. This bypasses the need for a separate lower-bound process, simplifying the algorithm and improving efficiency.
  • Truncation for Heavy Tails: For interarrival times with heavy tails, they employ a truncation technique. This involves modifying the interarrival times to have finite exponential moments, allowing the application of their core algorithms, and then relating the results back to the original heavy-tailed case.
  • Asymptotic Analysis: The performance of their algorithms is analyzed in two heavy-traffic regimes:
  • Quality-Driven (QD) regime: Where the traffic intensity is strictly less than 1.
  • Quality-and-Efficiency-Driven (QED) regime (Halfin-Whitt): Where the traffic intensity approaches 1 at a square-root speed.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Infinite Server Queue as a Universal Dominator: The insight that a simple infinite server queue can serve as a powerful and tractable upper bound for complex loss systems is central. This simplifies the problem by allowing the use of well-understood backward simulation techniques.
  • Efficient Coalescence Detection: Bypassing the traditional need for both upper and lower bounding processes by cleverly using the infinite server queue's state to detect coalescence is a significant algorithmic improvement. This directly impacts the running time.
  • Bridging Non-Markovian and Heavy-Traffic: The paper successfully combines techniques for handling non-Markovian distributions (renewal arrivals, general service times) with the challenging regime of heavy traffic, which is common in real-world systems.
  • Sub-Exponential Complexity: Demonstrating sub-exponential complexity for exact simulation in these complex scenarios is a major theoretical achievement, suggesting practical feasibility for larger systems.

Key Results

  • First Exact Simulation for Non-Markovian Loss Networks: The paper presents the first class of exact simulation algorithms for the steady-state distribution of non-Markovian loss networks.
  • Performance in Heavy Traffic:
    • In the Quality-Driven (QD) regime, the algorithm achieves near-optimal running time, essentially linear in the arrival rate.
  • In the Quality-and-Efficiency-Driven (QED) regime, the algorithm achieves sub-exponential running time.
  • Algorithm Complexity: The running time of the algorithms is shown to be sub-exponential as both the number of servers and the arrival rate increase.
  • Theoretical Guarantees: The paper provides theoretical bounds and proofs for the termination time and performance of the proposed algorithms under various assumptions on arrival and service time distributions.

Limitations and Future Work

  • Moment Conditions: While the algorithms handle non-Markovian distributions, they do impose moment conditions on arrival and service times for the running time analysis (e.g., finite mean, finite $q$-th moment, or finite exponential moments). The paper notes that these conditions cover many practical distributions like log-normal.
  • Generalization to Loss Networks: The paper extends the results to generalized loss networks with multiple stations and routing, but the analysis becomes more complex.
  • Practical Implementation Details: While the algorithms are described, the paper focuses on theoretical analysis. The practical implementation of these algorithms, especially for very large systems, might still present computational challenges.
  • Future Work: The paper lays the groundwork for further research into exact simulation for more complex queueing systems and networks. The authors suggest extensions to more general network structures and analysis under different traffic conditions.

Summary updated

Abstract

We present the first class of perfect sampling (also known as exact simulation) algorithms for the steady-state distribution of non-Markovian loss systems. We use a variation of dominated coupling from the past. We first simulate a stationary infinite server system backwards in time and analyze the running time in heavy traffic. In particular, we are able to simulate stationary renewal marked point processes in unbounded regions. We then use the infinite server system as an upper bound process to simulate the loss system. The running time analysis of our perfect sampling algorithm for loss systems is performed in the quality-driven (QD) and the quality-and-efficiency-driven regimes. In both cases, we show that our algorithm achieves subexponential complexity as both the number of servers and the arrival rate increase. Moreover, in the QD regime, our algorithm achieves a nearly optimal rate of complexity.
BibTeX
@inproceedings{blanchet2015perfect,
  author = {José Blanchet and Jing Dong},
  title = {{Perfect sampling for infinite server and loss systems}},
  booktitle = {Advances},
  year = {2015},
  doi = {10.1239/aap/1444308881},
}
Figure