Authors: Jose Blanchet and Xuhui Chen
Abstract
We provide the first perfect sampling algorithm for a Generalized Jackson Network of FIFO queues under arbitrary topology and non-Markovian assumptions on the input of the network. We assume (in addition to stability) that the interarrival and service times of customers have finite moment generating function in a neighborhood of the origin, and the interarrival times have unbounded support.
Introduction
In queueing theory, the Jackson network serves as a foundational model for understanding how entities move through interconnected service stations. However, standard Jackson networks rely on restrictive Markovian assumptions: arrivals must follow a Poisson process and service times must be exponentially distributed. In real-world applications—ranging from telecommunications to manufacturing—these assumptions rarely hold.
Generalized Jackson Networks (GJNs) offer a more realistic alternative by allowing for arbitrary renewal arrival processes and non-exponential service times. While more flexible, GJNs are significantly harder to analyze. Traditionally, researchers have relied on long-run simulations to estimate steady-state behavior. This approach is plagued by "initialization bias," where the choice of the starting state influences the results unless a sufficiently long "warm-up" period is used. This paper presents a breakthrough: the first algorithm capable of "perfect sampling," providing unbiased samples directly from the steady-state distribution of a GJN.
The Challenge of Non-Monotonicity
Perfect sampling typically relies on a technique called Coupling From The Past (CFTP). The goal of CFTP is to start a simulation far enough in the past so that all possible starting states have converged (coalesced) to the same state by time zero. For this to be computationally feasible, the system usually needs to be "monotone"—meaning that if you start with more customers in the system, you will always have at least as many customers at any future point.
GJNs are notoriously non-monotone. A single departure at one station can trigger an arrival at another, potentially changing the order of events in a way that breaks simple monotonicity. To overcome this, Blanchet and Chen utilize Dominated Coupling From The Past (DCFTP), which uses a simpler, monotone "bounding process" to sandwich the complex target process.
The Proposed Algorithm
The core innovation of the paper is the construction of a hierarchy of processes that allows the authors to bound the non-monotone GJN within a manageable framework:
- The Target GJN ($\mathcal{N}$): The actual system under study.
- The Auxiliary GJN ($\mathcal{N}^0$): A modified version with slightly slower service rates, designed to ensure it dominates the original system.
- The Vacation System ($\mathcal{N}^+$): A system where servers take "vacations" when their queue is empty. Crucially, this system is monotone, making it easier to bound.
- The Autonomous System ($\mathcal{N}'$): A system where departures are independent of the actual queue length. This acts as the ultimate dominating process that can be efficiently simulated backwards in time.
By simulating the Autonomous System backwards until it reaches a "coalescence time," the authors can determine a state that is guaranteed to bound the target GJN regardless of its infinite past. They then evolve the target system forward from this point to time zero to obtain a perfect sample.
Theoretical and Numerical Validation
The authors prove that their algorithm produces an unbiased sample from the steady-state distribution and, importantly, that the expected time required to terminate the algorithm is finite. This ensures the algorithm is not just a theoretical curiosity but a practical tool.
To validate the method, the authors tested it on a 2-station Jackson network. Because standard Jackson networks have known closed-form solutions (Jackson's Theorem), they served as a perfect benchmark. The algorithm generated 10,000 samples, and the resulting histograms showed a near-perfect match with the theoretical steady-state distributions. Furthermore, the simulation accurately captured the correlations between stations, confirming that the algorithm respects the complex interdependencies of the network topology.
Requirements and Limitations
While the algorithm is a significant advancement, it operates under specific conditions:
- Stability: The system must be stable (arrival rates must be less than service rates).
- Light-Tail Assumption: The inter-arrival and service times must have finite moment generating functions. This means the algorithm cannot currently handle "heavy-tailed" distributions, which are common in some modern data networks.
- Unbounded Support: The interarrival times must have unbounded support to ensure the system eventually empties, facilitating the coupling process.
Conclusion
Blanchet and Chen have provided a powerful new tool for the exact simulation of complex queueing systems. By successfully applying DCFTP to Generalized Jackson Networks, they have eliminated the need for arbitrary warm-up periods and the associated initialization bias. Future research may extend this logic to handle heavy-tailed distributions or different queueing disciplines beyond First-In-First-Out (FIFO), further expanding the reach of perfect sampling in stochastic modeling.
Summary updated