Efficient parallel queuing system simulation
Pages 1020 - 1027
Abstract
Queuing systems are an important building block for performance evaluation in various application areas, due to their powerful, yet simple nature. Although it is often possible to perform an analytical evaluation of a queuing model, simulation of queuing systems remains an important technique in the context of performance evaluation. In order to speed up queuing simulation executions, parallel and distributed simulation techniques have been devised. Unfortunately, existing methods are complex in nature, leading to increased development costs. Moreover, most of these approaches have been developed for tightly coupled parallel processing machines. Consequently, they are not suited for a distributed computing environment. This paper investigates an alternative approach based on the technique of time-parallel simulation with fix-up computations. The salient features of this novel approach are its simplicity and its suitability for execution in a distributed environment.
References
[1]
Andradóttir, S., and T. J. Ott. 1995. Time-segmentation parallel simulation of networks of queues with loss or communication blocking. ACM Transactions on Modeling and Computer Simulation 5 (4): 269--305.
[2]
Chandy, K., and R. Sherman. 1989. Space-time and simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, 53--57.
[3]
Chen, L. 1997. Parallel simulation by multi-instruction, longest-path algorithms. Queueing Systems 27 (1--2): 37--54.
[4]
Foster, I., C. Kesselman, and S. Tuecke. 2001. The anatomy of the grid: Enabling scalable virtual organizations. International Journal of High Performance Computing Applications 15 (3): 200--222.
[5]
Fujimoto, R. M. 2000. Parallel and distributed simulation systems. New York: John Wiley & Sons.
[6]
Greenberg, A. G., B. D. Lubachevsky, and I. Mitrani. 1991. Algorithms for unboundedly parallel simulations. ACM Transactions on Computer Systems 9 (3): 201--221.
[7]
Heidelberger, P. 1986. Statistical analysis of parallel simulations. In Proceedings of the 1986 Winter Simulation Conference, 290--295.
[8]
Heidelberger, P., and H. S. Stone. 1990. Parallel trace-driven cache simulation by time partitioning. In Proceedings of the 1990 Winter Simulation Conference, 734--737.
[9]
Kiesling, T. 2005. Using approximation with time-parallel simulation. SIMULATION 81 (4): 255--266.
[10]
Kiesling, T., and S. Pohl. 2004. Time-parallel simulation with approximative state matching. In Proceedings of the 18th Workshop on Parallel and Distributed Simulation, 195--202.
[11]
Krivulin, N. K. 1994. Recursive equations based models of queueing systems. In Proceedings of the 1994 European Simulation Symposium, 252--256.
[12]
Kruskal, C. P., L. Rudolph, and M. Snir. 1985. The power of parallel prefix. IEEE Transactions on Computers 34 (10): 965--968.
[13]
Lin, Y., and E. Lazowska. 1991. A time-division algorithm for parallel simulation. ACM Transactions on Modeling and Computer Simulation 1 (1): 73--83.
[14]
Prabhu, N. U. 1965. Queues and inventories. J. Wiley & Sons.
[15]
Rohatgi, V. K. 1976. An introduction to probability theory and mathematical statistics. John Wiley & Sons.
[16]
Saaty, T. L. 1961. Elements of queueing theory with applications. McGraw-Hill.
[17]
Wagner, D. B., and E. D. Lazowska. 1989. Parallel simulation of queueing networks: Limitations and potentials. In SIGMETRICS, 146--155.
[18]
Wang, J. J., and M. Abrams. 1992. Approximate time-parallel simulation of queueing systems with losses. In Proceedings of the 1992 Winter Simulation Conference, 700--708.
- Efficient parallel queuing system simulation
Recommendations
Parallel simulation of queueing networks: limitations and potentials
This paper concerns the parallel simulation of queueing network models (QNMs) using the conservative (Chandy-Misra) paradigm. Most empirical studies of conservative parallel simulation have used QNMs as benchmarks. For the most part, these studies ...
Parallel simulation of queueing networks: limitations and potentials
SIGMETRICS '89: Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systemsThis paper concerns the parallel simulation of queueing network models (QNMs) using the conservative (Chandy-Misra) paradigm. Most empirical studies of conservative parallel simulation have used QNMs as benchmarks. For the most part, these studies ...
Conservative Parallel Simulation of Priority Class Queuing Networks
A conservative synchronization protocol for the parallel simulation of queuing networkshaving C job priority classes, where a job's class is fixed, is described. This problem has long vexed designers of conservative synchronization protocols because of ...
Comments
Information & Contributors
Information
Published In
December 2006
2429 pages
ISBN:1424405017
- Editors:
- L. Felipe Perrone,
- Barry G. Lawson,
- Jason Liu,
- Frederick P. Wieland,
- General Chair:
- David Nicol,
- Program Chair:
- Richard Fujimoto
Sponsors
- IIE: Institute of Industrial Engineers
- ASA: American Statistical Association
- IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
- IEEE-CS\DATC: The IEEE Computer Society
- SIGSIM: ACM Special Interest Group on Simulation and Modeling
- NIST: National Institute of Standards and Technology
- (SCS): The Society for Modeling and Simulation International
- INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation
Publisher
Winter Simulation Conference
Publication History
Published: 03 December 2006
Check for updates
Qualifiers
- Article
Conference
WSC06
Sponsor:
- IIE
- ASA
- IEICE ESS
- IEEE-CS\DATC
- SIGSIM
- NIST
- (SCS)
- INFORMS-CS
Acceptance Rates
WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;
Overall Acceptance Rate 3,413 of 5,075 submissions, 67%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 283Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in