Low complexity state space representation and algorithms for closed queueing networks exact sampling

Anne Bouillard 1, 2 Ana Busic 1, 2 Christelle Rovetta 2, 1
2 DYOGENE - Dynamics of Geometric Networks
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : We consider exact sampling from the stationary distribution of a closed queueing network with finite capacities. In a recent work a compact representation of sets of states was proposed that enables exact sampling from the stationary distribution without considering all initial conditions in the coupling from the past (CFTP) scheme.This representation reduces the complexity of the one-step transition in the CFTP algorithm to O(KM^2), where K is the number of queues and M the total number of customers; while the cardinality of the state space is exponential in the number of queues. In this paper, we extend these previous results to the multiserver case. The main focus and the contribution of this paper is on the algorithmic and the implementation issues. We propose a new representation, that leads to one-step transition complexity of the CFTP algorithm that is in O(KM). We provide a detailed description of our matrix-based implementation. Matlab toolbox Clones (CLOsed queueing Networks Exact Sampling) can be downloaded at http://www.di.ens.fr/~rovetta/Clones.
Type de document :
Article dans une revue
Performance Evaluation, Elsevier, 2016, 103, pp.2-22. 〈10.1016/j.peva.2016.06.006〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01396074
Contributeur : Ana Busic <>
Soumis le : dimanche 13 novembre 2016 - 20:45:18
Dernière modification le : vendredi 31 août 2018 - 09:12:07

Identifiants

Collections

Citation

Anne Bouillard, Ana Busic, Christelle Rovetta. Low complexity state space representation and algorithms for closed queueing networks exact sampling. Performance Evaluation, Elsevier, 2016, 103, pp.2-22. 〈10.1016/j.peva.2016.06.006〉. 〈hal-01396074〉

Partager

Métriques

Consultations de la notice

242