Abstract
Closed queueing networks with finite capacities are critical for modeling complex systems in manufacturing and computing. However, the presence of blocking mechanisms typically destroys the product-form property of stationary distributions, rendering exact analysis computationally intractable due to exponential state space growth. This paper presents Clones, a Matlab toolbox that implements exact sampling via "Coupling From The Past" (CFTP). By utilizing a novel "gap-free diagram" representation, the authors reduce the one-step transition complexity to $O(KM)$, matching the efficiency of classical algorithms for simpler networks. We evaluate the toolbox's performance on synthetic networks, demonstrating its scalability and practical utility for large-scale systems.
Introduction
Closed queueing networks are fundamental tools for performance evaluation. While infinite-capacity networks often admit simple product-form solutions, real-world constraints impose finite capacities, leading to blocking. In such scenarios, the stationary distribution is difficult to compute. Traditional Markov Chain Monte Carlo (MCMC) methods provide approximate samples but lack definitive convergence guarantees. Perfect sampling, specifically CFTP, offers exact samples but is hindered by the "curse of dimensionality" as the state space grows exponentially with the number of queues ($K$) and customers ($M$).
Methods
The Clones toolbox addresses this challenge by employing structured state representations. The authors transition from a naive State Space (PSS) approach to a Diagram-based (PSD) approach, where sets of states are represented as paths in a directed graph. This reduces complexity to $O(KM^2)$.
The primary innovation is the introduction of Gap-free Diagrams (PSF). This compact subclass of diagrams tracks only the minimal and maximal possible arcs for each queue, further reducing complexity to $O(KM)$. This complexity parity with Buzen’s algorithm—the standard for product-form networks—marks a significant advancement in the field.
Results
Evaluation on synthetic networks with varying customer counts ($M$) reveals that while PSS runtime scales exponentially, PSD and PSF scale polynomially. Interestingly, for $M < 60$, the $O(KM^2)$ PSD approach outperforms PSF in Matlab due to better alignment with sparse matrix optimizations. However, for larger $M$, the $O(KM)$ PSF algorithm demonstrates superior scalability, successfully producing samples guaranteed to be distributed according to the true stationary distribution.
Conclusion
Clones provides a robust framework for exact sampling in finite-capacity networks. Future work will focus on optimizing the PSF implementation for Matlab's engine and extending these diagrammatic techniques to broader classes of queueing models beyond the RS-RD (repetitive service – random destination) blocking model.
Summary updated