Perfect sampling of Jackson queueing networks

Ana Busic 1, 2, 3 Stéphane Durand 4 Bruno Gaujal 5 Florence Perronnin 4
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
5 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
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 hyper-stable 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 variable service times and non-monotone networks such as queueing networks with negative customers.
Type de document :
Article dans une revue
Queueing Systems, Springer Verlag, 2015, 80 (3), pp.37. 〈10.1007/s11134-015-9436-z〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01236542
Contributeur : Bruno Gaujal <>
Soumis le : mardi 1 décembre 2015 - 20:10:04
Dernière modification le : mercredi 29 novembre 2017 - 15:25:09

Identifiants

Collections

Citation

Ana Busic, Stéphane Durand, Bruno Gaujal, Florence Perronnin. Perfect sampling of Jackson queueing networks. Queueing Systems, Springer Verlag, 2015, 80 (3), pp.37. 〈10.1007/s11134-015-9436-z〉. 〈hal-01236542〉

Partager

Métriques

Consultations de la notice

222