Skip to Main content Skip to Navigation

Perfect sampling of Jackson Queueing Networks

Abstract : We consider open Jackson networks with losses with mixed finite and infinite queues and analyze the efficiency of sampling from their exact stationary distribution. We show that perfect sampling is possible, although the underlying Markov chain may have an infinite state space. The main idea is to use a Jackson network with infinite buffers (that has a product form stationary distribution) to bound the number of initial conditions to be considered in the coupling from the past scheme. We also provide bounds on the sampling time of this new perfect sampling algorithm for acyclic or hyperstable networks. These bounds show that the new algorithm is considerably more efficient than existing perfect samplers even in the case where all queues are finite. We illustrate this efficiency through numerical experiments. We also extend our approach to non-monotone networks such as queueing networks with negative customers.
Document type :
Complete list of metadata
Contributor : Florence Perronnin Connect in order to contact the contributor
Submitted on : Friday, April 4, 2014 - 4:16:52 PM
Last modification on : Sunday, June 26, 2022 - 4:59:39 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:08:54 AM


Files produced by the author(s)


  • HAL Id : hal-00851331, version 2


Ana Bušić, Stéphane Durand, Bruno Gaujal, Florence Perronnin. Perfect sampling of Jackson Queueing Networks. [Research Report] RR-8332, INRIA. 2013, pp.32. ⟨hal-00851331v2⟩



Record views


Files downloads