Low complexity state space representation and algorithms for closed queueing networks exact sampling - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Performance Evaluation Année : 2016

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-01396074 , version 1 (13-11-2016)

Identifiants

Citer

Anne Bouillard, Ana Bušić, Christelle Rovetta. Low complexity state space representation and algorithms for closed queueing networks exact sampling. Performance Evaluation, 2016, 103, pp.2-22. ⟨10.1016/j.peva.2016.06.006⟩. ⟨hal-01396074⟩
173 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More