Perfect Sampling of Networks with Finite and Infinite Capacity Queues

Ana Busic 1 Bruno Gaujal 2 Florence Perronnin 3
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 MESCAL - Middleware efficiently scalable
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes
Abstract : We consider open Jackson queueing networks with mixed finite and infinite buffers and analyze the efficiency of sampling from their exact stationary distribution. We show that perfect sampling is possible, although the underlying Markov chain has a large or even 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 under hyper-stability conditions (to be defined in the paper) for each queue. 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.
Type de document :
Communication dans un congrès
Khalid Al-Begain and Dieter Fiems and Jean-Marc Vincent. 19th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA) 2012, 2012, Grenoble, France. Springer, 7314, pp.136-149, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30782-9_10〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788003
Contributeur : Arnaud Legrand <>
Soumis le : mercredi 13 février 2013 - 14:57:30
Dernière modification le : vendredi 25 mai 2018 - 12:02:04

Identifiants

Collections

Citation

Ana Busic, Bruno Gaujal, Florence Perronnin. Perfect Sampling of Networks with Finite and Infinite Capacity Queues. Khalid Al-Begain and Dieter Fiems and Jean-Marc Vincent. 19th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA) 2012, 2012, Grenoble, France. Springer, 7314, pp.136-149, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30782-9_10〉. 〈hal-00788003〉

Partager

Métriques

Consultations de la notice

355