Perfect Sampling of Queuing Networks with Complex Routing complexity and computational aspects
Résumé
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,...)