Perfect sampling for closed queueing networks

Speaker : Christelle Rovetta
Date: 11/02/2015
Time: 2:30 pm - 3:00 pm
Location: LINCS Meeting Room 40


We investigate coupling from the past (CFTP) algorithmsfor closed queueing networks. The stationary distribution has a productform only in a very limited number of particular cases when queue capacityis finite, and numerical algorithms are intractable due to the cardinalityof the state space. Moreover, closed networks do not exhibit any mono-tonic property enabling ecient CFTP. We derive a bounding chain forthe CFTP algorithm for closed queueing networks. This bounding chainis based on a compact representation of sets of states that enables exactsampling from the stationary distribution without considering all initialconditions in the CFTP. The coupling time of the bounding chain is al-most surely finite, and numerical experiments show that it is close to thecoupling time of the exact chain.