A Parallel Simulation Methodology for Speedup and Obtaining Performance Estimates with Specific Accuracy: Experiences of its Application in Studies of Metropolitan Area Networks

Abstract

Performance measures obtained by stochastic simula tion are estimates, and one must consider the precision of the estimates before making any constructive con clusions about the investigated systems. This paper applies an automated distributed simulation method, called Spectral Analysis in Parallel Time Streams, to speed up production of performance estimates, and for run-length determination in the simulation of High- speed Metropolitan Area Networks (MANs). This method makes sequential simulators suitable for par allel execution on multiprocessors and/or networked computers. At runtime it estimates the information content of observations generated during simulation, generates a point estimate and confidence interval, and directs the run to continue until an estimate is obtained that achieves or exceeds our required level of precision. The application of this methodology for studying high-speed MANs, the speedup, intermachine communication and "warm-up" overhead, and the run lengths needed to produce estimates with a specific level of precision, are reported for each of the param eters investigated. Practical implications are discussed.

Keywords

Distributed simulation speedup pre cision spectral analysis bandwidth multiuse distributed queue dual bus delay initial transient

Get full access to this article

View all access options for this article.

References

Pawlikowski, K. "Steady-state Simulation of Queueing Processes : A Survey of Problems and Solutions." ACM Computing Surveys , No. 2, pp 124-170, June 1990.

Pawlikowski, K. and Yau, V. "Independent Replications Versus Spectral Analysis in Steady-State Simulation of High Speed Data Networks." Proceedings of ATRS'91, Nov. 1991, Wollongong, Australia, pp 182-190.

Pawlikowski, K. "Simulation Studies of Telecommunication Networks and Their Credibility." Proceedings of the European Simulation Multiconference (ESM'99), Warsaw, June 1999, Society for Computer Simulation, 1999.

Pawlikowski, K. , Ewing, G. and McNickle, D. "Coverage of Confidence Intervals in Sequential Steady-State Simulation." Journal of Simulation Practise and Theory, Vol. 6, No. 3, pp 255-267, 1998.

Pawlikowski, K. , Ewing, G. and McNickle, D. "Performance Evaluation of Industrial Processes in Computer Network Environments." Proceedings of 1998 European Conference on Concurrent Engineering, Erlangen, Germany, April 1998, Society for Computer Simulation, pp 160-164, 1998.

Yau, V. and Pawlikowski, K. "A Conflict-free Traffic Assignment Algorithm Using Forward Planning ." IEEE INFOCOM'96, IEEE Comm. Press, Vol. 3, pp 1277-1284.

Yau, V. and Pawlikowski, K. "AKAROA: A Package for Automating Generation and Process Control of Parallel Stochastic Simulation." Proceedings of the 16th Australian Computer Science Conference, G. Gopal, et al. (eds.), Australian Computer Science Communications , 1993, pp 71 -83.

Yau, V. "Optical WDMA Network Design and Function Placement." Computer Networks Journal, Vol. 31, No. 22, pp 2411-2427, Dec. 1999.

Yau, V. and Pawlikowski, K. "CA-STAR: A Centrally-Arbitrated Passive Broadcast-and-Select Star Architecture for Lightwave Networks." Journal of High Speed Networks, Vol. 8, No. 3, pp 1-21, 1999.

10.

Yau, V. and Pawlikowski, K. "An Algorithm that Uses Forward Planning to Expedite Conflict-Free Traffic Assignment in Time-Multiples Switching Systems." IEEE Transactions on Communications, Vol. 47, No. 11, pp 1757-1765, Nov. 1999.

11.

Heidelberger and Welch. " A Spectral Method for Confidence Interval Generation and Run Length Control in Simulations." Communications of the ACM, Vol. 24, pp 233-245, April 1982.

12.

Yau, V. "Automating Parallel Simulation Using Parallel Time Streams." Accepted for publication in ACM Transactions on Modelling and Computer Simulation.

13.

Yau, V. "Automating Parallel and Distributed Quantitative Stochastic Simulation ." Technical Report No. COSC 05/96, Sept. 1996, Dept. of Computer Science, University of Canterbury, New Zealand, pg 118.

14.

Pawlikowski, K. , Yau, V. and McNickle, D. "Distributed Stochastic Discrete-Event Simulation in Parallel Time Streams." Proceedings of the 1994 Winter Simulation Conference, IEEE Press, pp 723-730.

15.

"ISO/IEC ANSI/IEEE Standard 802.6 LAN/MAN Standards DQDB Access Method Package." IEEE, ISBN 1559375760, 1994.

16.

Atkins, J. and Norris, M. Total Area Networking: ATM, IP, Frame Relay, and SMDS Explained. John Wiley and Sons, ISBN 0471984647, 1999.

17.

Huang, N.-F. and Liu, H.-I. "A Study of Isochronous Channel Reuse in DQD13 Metropolitan Area Networks." IEEE/ACM Transactions on Networking, Vol. 6, No. 4, pp 475-484, 1998.

18.

Yang, Y. , Lai, T.-H. and Liu, M.-T. "Isonchronous Bandwidth Utilization Improvement in Distributed Queue Dual Bus-Based Personal Communicatin Networks." Computer Communications , Vol. 21, pp 1420-1433, 1998.

19.

Sharon, O. "A Proof for Lack of Starvation in DQDB with and without Slot Reuse." IEEE/ACM Transactions on Networking , Vol. 5, No. 3, pp 410-419, 1997.

20.

Hairong, S. , Ke, H. and Lemin, L. "Performance Analysis of the Constant Bit-rate Services in an ATM DQDB MAN." Computer Communications, Vol. 21, pp 186-194, 1998.

21.

Dong, X. and Lai, T. "An Efficient Protocol for Call Setup and Path Migration in IEEE 802.6 based Personal Communication Networks." IEEE Transactions on Computers, Vol. 46, No. 3, pp 252-259, 1997.

22.

Orozco-Barbosa, L. and Ahmed, N.U. "Dynamic Modelling of the IEEE 802.6 Medium Access Mechanism." Proceedings of the 18th Biennial Symposium on Communication, pp 21-24,1996.

23.

Wu, J.S. and Hsieh, Y.T. "Improving Access Delay Fairness of DQDB MANs under Overload Condition." Computer Communications, Vol. 19, pp 571-579, 1996.

24.

Yau, V. and Pawlikowski, K. "Analysis of Dual Bus Metropolitan Area Networks Using Distributed Quantitative Stochastic Simulation." SIMULATION, Vol. 75, No. 3, September 2000.

25.

Gafarian, A.V. , Ancker, C.J. and Morisaku, T. "Evaluation of Commonly Used Rules for Detecting Steady State in Computer Simulation." Naval Research Logistics Quarterly, Vol. 8, pp 511-529, 1978.

26.

Schruben, L.W. , Singh, H. and Tierney L. "Optimal Tests for Initialisation Bias In Simulation Output." Operations Research, Vol. 31, pp 1167-1178, 1983.