Efficiency of time segmentation parallel simulation of finite Markovian queueing networks
成果类型：
Article
署名作者：
Andradóttir, S; Hosseini-Nasab, M
署名单位：
University System of Georgia; Georgia Institute of Technology; AT&T
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.51.2.272.12778
发表日期：
2003
页码：
272-280
关键词：
摘要：
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.