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

Anne Bouillard 1, 2 Ana Bušic 1, 2 Christelle Rovetta 2, 1
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
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.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-01396074
Contributor : Ana Busic <>
Submitted on : Sunday, November 13, 2016 - 8:45:18 PM
Last modification on : Thursday, February 7, 2019 - 2:54:36 PM

Identifiers

Citation

Anne Bouillard, Ana Bušic, 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⟩

Share

Metrics

Record views

262