Perfect Sampling of Queuing Networks with Complex Routing complexity and computational aspects

Jean-Marc Vincent 1
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : The statistical control of discrete event simulations is usually based on empirical procedures to determine a \"burn-in\" time period and an estimation period based on the time correlation properties of the studied system. Recent works in simulation of interacting systems of particles provide new algorithms, perfect samplers, that sample directly according the stationary distribution of the system. These algorithms provide independent samples of steady-state and so avoid the \"burn-in\" time and time correlation problems. These techniques has been successfully applied in the domain of queueing networks with finite capacities and complex routing protocols. The aim of this short course is to introduce the perfect sampling technique for Markovian models. The focus will be on the complexity of the simulation process and the time reduction obtained by the monotonicity properties of the system. In particular, index routing policies (Bernoulli routing, overflow, join the shortest queue, etc.) are monotone and the performance of the sampler is sufficient to reach low probability events estimation by \"brute force\". These samplers have been implemented in a general simulation framework PSI2 and applied in various contexts (queueing networks, job scheduling, call centers, brokering,...)
Type de document :
Communication dans un congrès
RESCOM (tutorial), 2009, La Palmyre, 2009
Liste complète des métadonnées
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 13:46:49
Dernière modification le : mardi 22 mars 2016 - 01:27:08


  • HAL Id : hal-00788936, version 1



Jean-Marc Vincent. Perfect Sampling of Queuing Networks with Complex Routing complexity and computational aspects. RESCOM (tutorial), 2009, La Palmyre, 2009. <hal-00788936>



Consultations de la notice