On the efficiency of perfect simulation in monotone queueing networks

Jonatha Anselmi 1 Bruno Gaujal 2
1 BCAM - Basque Center for Applied Mathematics
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We consider Jackson queueing networks (JQN) with finite capacity constraints and analyze the temporal computational complexity of sampling from their stationary distribution. In the context of perfect sampling, the monotonicity of JQNs ensures that it is the coupling time of extremal sample-paths. In the context of approximate sampling, it is given by the mixing time. We give a sufficient condition to prove that the coupling time of JQNs with M queues is O(M ∑Mi=1 Ci), where Ci denotes the capacity (buffer size) of queue i. This condition lets us deal with networks having arbitrary topology, for which the best bound known is exponential in the Ci's or in M. Then, we use this result to show that the mixing time of JQNs is log2 1/∈ O(M ∑Mi=1 Ci), where ∈ is a precision threshold. The main idea of our proof relies on a recursive formula on the coupling times of special sample-paths and provides a methodology for analyzing the coupling and mixing times of several monotone Markovian networks.
Type de document :
Communication dans un congrès
IFIP Performance: 29th International Symposium on Computer Performance, Modeling, Measurements and Evaluation, 2011, Amsterdam, Netherlands. ACM, 39, pp.56-58, 2011, ACM Performance Evaluation Review. 〈10.1145/2034832.2034847〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00788800
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 11:16:44
Dernière modification le : mercredi 11 avril 2018 - 01:55:11

Identifiants

Collections

INRIA | UGA | TDS-MACS | LIG | LIG_SRCPR | INRIA-RENGRE

Citation

Jonatha Anselmi, Bruno Gaujal. On the efficiency of perfect simulation in monotone queueing networks. IFIP Performance: 29th International Symposium on Computer Performance, Modeling, Measurements and Evaluation, 2011, Amsterdam, Netherlands. ACM, 39, pp.56-58, 2011, ACM Performance Evaluation Review. 〈10.1145/2034832.2034847〉. 〈hal-00788800〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

133

Contact


archive-ouverte@inria.fr