Time-segmentation parallel simulation of networks of queues with loss or communication blocking

ABSTRACT

This article is concerned with the efficient simulation of communication systems on parallel processors. In most of the article, we assume that the communication system under study can be modeled as a system of finite exponential queues with a general topology (in particular, the system need not be acyclic) and with either loss or communication blocking. We also assume that to estimate the performance measures of interest, it is necessary to generate long sample paths of the system. This is the case in both steady-state simulations and in long transient simulations. The approach involves applying each processor to simulate the entire system for a part of the time horizon of interest. We present theory guaranteeing the validity of the proposed approach, and numerical results proving the viability of the approach. The proof of the validity of the approach uses the fact that the queueing systems considered are continuous time Markov chains. An essential part of the argument is a proof that sample paths starting from different initial states eventually will couple (i.e., become identical), and a simple method for recognizing the time when a sample path has become independent of the original starting state (i.e., when all sample paths have coupled, regardless of the initial state). Finally, we discuss how our approach can be used for parallel trace-driven simulations of certain nonMarkovian systems, and state the implications of this research for the initialization bias problem in steady-state simulation.

REFERENCES

• 1: CALVIN, J. M. 1994. Return-state independent quantities in regenerative simulation. Oper. Res. 42, 531-542.
• 2: CHANDY, K.'M. AND SHERMAN, R. 1989. Space-time and simulation. Distrib. Simul., 53-57.
• 3: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 4: FUJIMGTO, R. M. 1993. Parallel discrete event simulation: will the field survive? ORSA J. Comput. 5, 213-230.
• 5: FUJIMOTO, R. IV{., NIKOLAIDIS, I., AND COOPER, A. 1995. Parallel simulation of statistical multiplexers. J. DEDS 5, 115-140.
• 6: Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Algorithms for unboundedly parallel simulations, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.201-221, Aug. 1991 [doi>10.1145/128738.128739]
• 7: Peter W. Glynn , Philip Heidelberger, Analysis of parallel replicated simulations under a completion time constraint, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.3-23, Jan. 1991 [doi>10.1145/102810.102811]
• 8: Philip Heidelberger , Harold S. Stone, Parallel trace-driven cache simulation by time partitioning, Proceedings of the 22nd conference on Winter simulation, p.734-737, December 09-12, 1990, New Orleans, Louisiana, United States
• 9: Yu-Chi Ho , C. G. Cassandras , M. Makhlouf, Parallel simulation of real-time systems via the Standard Clock approach, Mathematics and Computers in Simulation, v.35 n.1, p.33-41, Feb. 1993 [doi>10.1016/0378-4754(93)90035-S]
• 10: KELTON, W. D. AND LAW, A.M. 1984. An analytical evaluation of alternative strategies in steady-state simulation. Oper. Res. 32, 169-184.
• 11: LIN, Y.-B. 1993a. Parallel trace-driven simulation for packet loss in finite-buffered voice multiplexes. Parallel Comput. 19,219-228.
• 12: Yi-Bing Lin, Parallel trace-driven simulation of packet-switched multiplexer under priority scheduling policy, Information Processing Letters, v.47 n.4, p.197-201, Sept. 27, 1993 [doi>10.1016/0020-0190(93)90032-5]
• 13: VAKILI, P. 1991. Using a standard clock technique for efficient simulation. Oper. Res. Lett. 10, 445-452.
• 14: Jain J. Wang , Marc Abrams, Determining initial states for time-parallel simulations, Proceedings of the seventh workshop on Parallel and distributed simulation, p.19-26, May 16-19, 1993, San Diego, California, United States
• 15: WANG, J. J. AND ABRAMS, M. 1994. Massively time-parallel, approximate simulation of loss queueing systems. Ann. Oper. Res. 53, 553-576.
• 16: Ward Whitt, The efficiency of one long run versus independent replication in steady-state simulation, Management Science, v.37 n.6, p.645-666, June 1991 [doi>10.1287/mnsc.37.6.645]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Systems theory

General Terms:
Algorithms, Design, Experimentation, Theory, Verification

Keywords:
communication blocking, communication systems, coupling, initialization bias problem, loss, parallel simulation, queueing systems, time segmentation, trace-driven simulation