Perfect Sampling of GI/GI/c Queues (with J. Dong and Y. Pei).

Summary:

This paper develops a Dominated Coupling From The Past (DCFTP) algorithm for simulation without bias (i.e. exact sampling) from the steady-state distribution of a non-Markovian multiserver queue. The algorithm uses as a dominating process a vacation system, that is, a system in which servers take vacations whenever they see an empty queue (the vacations are iid copies of the service times). This algorithm takes advantage of the exact sampler for the single server queue obtained in Blanchet and Wallwater (2014). The algorithm can also be easily adapted to deal with time in-homogeneous and Markov modulated input (similarly as in the Blanchet and Chen (2014)). The coupling consists in having each customer bring his own service time and it is performed in continuous time. We find a way to simulate in stationarity and backwards in time the vacation system. This simulation procedure contains a nice trick which is explained in the section corresponding to what we call “Fact I” of the paper (basically we split a complicated process which contains c+1 components into c+1 simpler processes that are be simulated using the procedure in Blanchet and Wallwater (2014) . Also, matching the service times to the arrivals is interesting and showing that the coupling indeed recovers an iid sequence of service times leads to a nice connection to “tetris games”!

Bibtex:

@Article{BlaDongPei,

author = { J. Blanchet and J. Dong and Y. Pei},

title = {Perfect Sampling of GI/GI/c Queues},

journal = {Submitted},

year = { },

volume = {},

pages = {}

}