Efficiency of Time Segmentation Parallel Simulation of Finite Markovian Queueing Networks

We present an approach for using parallel processors to simulate long sample paths of Markovian queueing networks with finite buffers and both loss and blocking stations. Parallelism is achieved by distributing the available processors among segments of the time domain of the simulation. We conduct the simulation in such a way that all sample paths of the system will eventually couple (i.e., become identical), regardless of their starting states. This coupling property is exploited to generate valid sample paths of the system by combining the information collected on consecutive time segments of the simulation. The efficiency of our approach depends heavily on the magnitude of the coupling times of the sample paths. We study how the expected coupling times depend on the system parameters through a variety of theoretical and numerical results. Our main results give conditions under which the expected coupling times grow slowly (no faster than linearly) with respect to the number of stations and buffer capacities in the system. These results suggest that our time segmentation approach is likely to perform well on a substantial class of finite Markovian queueing networks.