Paper Info
Title
Efficiency of Time Segmentation Parallel Simulation of Finite Markovian Queueing Networks
Abstract
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.
Year
DOI
Venue
2003
10.1287/opre.51.2.272.12778
Operations Research
Keywords
Field
DocType
time domain,system parameter,time segmentation approach,consecutive time segment,valid sample path,coupling property,time segmentation parallel simulation,coupling time,sample path,finite markovian queueing networks,long sample path,expected coupling time,simulation
Time domain,Magnitude (mathematics),Mathematical optimization,Parallel simulation,Markov process,Coupling,Computer science,Segmentation,Queue,Queueing theory
Journal
Volume
Issue
ISSN
51
2
0030-364X
Citations 
PageRank 
References 
5
0.68
12
Authors
2
Name
Order
Citations
PageRank
Sigrún Andradóttir154855.09
Mehdi Hosseini-Nasab2111.19