Abstract
The simulation of high-speed telecommunication systems such as ATM (Asynchronous Transfer Mode) networks has generally required excessively long run times. This paper reviews alternative approaches using parallelism to speed up simulations of discrete event systems, and telecommunication networks in particular. Subsequently, a new simulation method is introduced for the fast parallel simulation of a common network element, namely, a work-conserving finite capacity statistical multiplexer of bursty ON/OFF sources arriving on input links of equal peak rate. The primary performance measure of interest is the cell loss ratio, due to buffer overflows. The proposed method is based on two principal techniques: (1) the derivation of low-level (cell level) statistics from a higher level (burst level) simulation and (2) parallel execution of the burst level simulation program. For the latter, atime-division parallel simulation method is used where simulations operating at different intervals of simulated time are executed concurrently on different processors. Both techniques contribute to the overall speedup. Furthermore, these techniques support simulations that are driven by traces of actual network traffic (trace-driven simulation), in addition to standard models for source traffic. An analysis of this technique is described, indicating that it offers excellent potential for delivering good performance. Measurements of an implementation running on a 32 processor KSR-2 multiprocessor demonstrate that, for certain model parameter settings, the simulator is able to simulate up to 10 billion cell arrivals per second of wallclock time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akyildiz, I. F., Chen, L., Das, S. R., Fujimoto, R. M., and Serfozo, R. 1992. Performance analysis of Time Warp with limited memory.Proc. 1992 ACM SIGMETRICS Conference on Measuring and Modeling Computer Systems pp. 213–224.
Ammar, H., and Deng, S. 1992. Time warp simulation using time scale decomposition.ACM Transactions on Modeling and Computer Simulation 2(2): 158–177.
Baccelli, F., and Canales, M. 1993. Parallel simulation of stochastic petri nets using recurrence equations.ACM Transactions on Modeling and Computer Simulation 3(1): 20–41.
Bagrodia, R., Liao, W.-T., and Chandy, K. M. 1991. A unifying framework for distributed simulation.ACM Transactions on Modeling and Computer Simulation 1(4): 348–385.
Cottrell, M., Fort, J.-C., and Malgouyres, G. 1983. Large deviations and rare events in the study of stochastic algorithms.IEEE Transactions on Automatic Control AC-28(9): 907–920.
Chang, C.-S., Heidelberger, P., Juneja, S., and Shahabuddin, P. 1992. Effective bandwidth and fast simulation of ATM intree networks. IBM T. J. Watson Research Center, Technical Report RC 18586.
Chandy, K. M., and Misra, J. 1979. Distributed simulation: A case study in design and verification of distributed programs.IEEE Transactions on Software Engineering SE-5(5): 440–452.
Chandy, K. M., and Misra, J. 1981. Asynchronous distributed simulation via a sequence of parallel computations.Communications of the ACM 24(4): 198–205.
Dickens, P., and Reynolds, P., Jr. 1990. SRADS with local rollback.Distributed Simulation 22(2): 161–164.
Eick, S. G., Greenberg, A. G., Lubachevsky, B. D., and Weiss, A. 1993. Synchronous relaxation for parallel simulations with applications to circuit switched networks.ACM Transactions on Modeling and Computer Simulation 3(4): 287–314.
Frater, M. R. 1992. Application of fast simulation techniques to systems with correlated noise.Proc. 1992 Winter Simulation Conference pp. 448–452.
Fujimoto, R. M. 1990. Parallel discrete event simulation.Communications of the ACM 33(10): 30–53.
Gaujal, B., Greenberg, A. G., and Nicol, D. M. 1993. A sweep algorithm for massively parallel simulation of circuit-switched networks.Journal of Parallel and Distributed Computing 18(4): 484–500.
Greenberg, A. G., Lubachevsky, B. D., and Mitrani, I. 1991. Algorithms for unboundedly parallel simulations.ACM Transactions on Computer Systems 9(3): 201–221.
Gruber, J. G. 1982. A comparison of measured and calculated speech temporal parameters relevant to speech activity detection.IEEE Transactions on Communications COM-30(4): 728–738.
Guérin, R., Ahmadi, H., and Naghshineh, M. 1991. Equivalent capacity and its application to bandwidth allocation in high-speed networks.IEEE Journal on Selected Areas in Communications 9(7): 968–981.
Heidelberger, P. 1988. Discrete event simulations and parallel processing: Statistical properties.SIAM Journal on Scientific and Statistical Computing 9(6): 1114–1132.
Heidelberger, P., and Nicol, D. M. 1993. Conservative parallel simulation of continuous time Markov chains using uniformization.IEEE Transactions on Parallel and Distributed Systems 4(8): 906–921.
Heidelberger, P., and Stone, H. 1990. Parallel trace-driven cache simulation by time partitioning.Proc. 1990 Winter Simulation Conference New Orleans, pp. 734–737.
Hui, J. Y. 1989. Resource allocation for broadband networks.IEEE Journal on Selected Areas in Communications 6(9): 1598–1608.
Jefferson, D. R. 1985. Virtual time.ACM Transactions on Programming Languages and Systems 7(3): 404–425.
Lin, Y.-B. 1993. Parallel trace-driven simulation for packet loss in finite-buffered voice multiplexers.Parallel Computing 19(2): 219–228.
Lin, Y.-B., and Lazowska, E. D. 1991. A time-division algorithm for parallel simulation.ACM Transactions on Modeling and Computer Simulation 1(1): 73–83.
Leland, W. E., Willinger, W., Taqqu, M. S., and Wilson, D. V. 1993. On the self-similar nature of ethernet traffic.Proc. 1993 ACM SIGCOMM Conference pp. 183–193.
Nicol, D. M., and Fujimoto, R. M. 1995. Parallel simulation today.Annals of Operations Research, to appear.
Nicol, D., Greenberg, A., Lubachevsky, B., and Roy, S. 1992. Massively parallel algorithms for trace-driven cache simulation.6th Workshop on Parallel and Distributed Simulation, volume 24, pp. 3–11. SCS Simulation Series.
Parekh, S., and Walrand, J. 1989. A quick simulation method for excessive backlogs in networks of queues.IEEE Transactions on Automatic Control 34(1): 54–66.
Sokol, L. M., Briscoe, D. P., and Wieland, A. P. 1988. MTW: A strategy for scheduling discrete simulation events for concurrent execution.Proc. SCS Multiconference on Distributed Simulation 19: 34–42. SCS Simulation Series.
Wang, J. J., and Abrams, M. 1992. Approximate time-parallel simulation of queueing systems with losses.Proc. 1992 Winter Simulation Conference pp. 700–708.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Fujimoto, R.M., Nikolaidis, I. & Cooper, C.A. Parallel simulation of statistical multiplexers. Discrete Event Dyn Syst 5, 115–140 (1995). https://doi.org/10.1007/BF01439037
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01439037