×

Parallel simulation of statistical multiplexers. (English) Zbl 0843.68037

The simulation of high-speed telecommunication systems such as ATM (Asynchronous Transfer Mode) networks has generally required excessivley 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: (i) the derivation of low-level (cell level) statistics from a higher level (burst level) simulation and (ii) parallel execution of the burst level simulation program. For the latter, a time-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 in to standard models for source traffic. An analysis of this technique is described, indicating that it offers great potential for delivering good performance.

MSC:

68W10 Parallel algorithms in computer science
68U20 Simulation (MSC2010)
68W15 Distributed algorithms
90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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.
[2] Ammar, H., and Deng, S. 1992. Time warp simulation using time scale decomposition.ACM Transactions on Modeling and Computer Simulation 2(2): 158-177. · Zbl 0842.68107 · doi:10.1145/137926.137959
[3] 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. · Zbl 0842.68050 · doi:10.1145/151527.151545
[4] 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. · Zbl 0842.68101 · doi:10.1145/130611.130614
[5] 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. · Zbl 0531.93064 · doi:10.1109/TAC.1983.1103345
[6] 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.
[7] 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. · Zbl 05341658 · doi:10.1109/TSE.1979.230182
[8] Chandy, K. M., and Misra, J. 1981. Asynchronous distributed simulation via a sequence of parallel computations.Communications of the ACM 24(4): 198-205. · doi:10.1145/358598.358613
[9] Dickens, P., and Reynolds, P., Jr. 1990. SRADS with local rollback.Distributed Simulation 22(2): 161-164.
[10] 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. · Zbl 0839.94015 · doi:10.1145/159737.159744
[11] Frater, M. R. 1992. Application of fast simulation techniques to systems with correlated noise.Proc. 1992 Winter Simulation Conference pp. 448-452.
[12] Fujimoto, R. M. 1990. Parallel discrete event simulation.Communications of the ACM 33(10): 30-53. · doi:10.1145/84537.84545
[13] 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. · doi:10.1006/jpdc.1993.1079
[14] Greenberg, A. G., Lubachevsky, B. D., and Mitrani, I. 1991. Algorithms for unboundedly parallel simulations.ACM Transactions on Computer Systems 9(3): 201-221. · doi:10.1145/128738.128739
[15] 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. · doi:10.1109/TCOM.1982.1095514
[16] 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. · doi:10.1109/49.103545
[17] Heidelberger, P. 1988. Discrete event simulations and parallel processing: Statistical properties.SIAM Journal on Scientific and Statistical Computing 9(6): 1114-1132. · Zbl 0661.68115 · doi:10.1137/0909077
[18] 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. · Zbl 05107519 · doi:10.1109/71.238625
[19] Heidelberger, P., and Stone, H. 1990. Parallel trace-driven cache simulation by time partitioning.Proc. 1990 Winter Simulation Conference New Orleans, pp. 734-737.
[20] Hui, J. Y. 1989. Resource allocation for broadband networks.IEEE Journal on Selected Areas in Communications 6(9): 1598-1608. · doi:10.1109/49.12887
[21] Jefferson, D. R. 1985. Virtual time.ACM Transactions on Programming Languages and Systems 7(3): 404-425. · doi:10.1145/3916.3988
[22] Lin, Y.-B. 1993. Parallel trace-driven simulation for packet loss in finite-buffered voice multiplexers.Parallel Computing 19(2): 219-228. · Zbl 0794.68008 · doi:10.1016/0167-8191(93)90051-L
[23] 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. · Zbl 0842.68094 · doi:10.1145/102810.214307
[24] 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.
[25] Nicol, D. M., and Fujimoto, R. M. 1995. Parallel simulation today.Annals of Operations Research, to appear. · Zbl 0822.65134
[26] 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.
[27] 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. · Zbl 0661.60110 · doi:10.1109/9.8649
[28] 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.
[29] Wang, J. J., and Abrams, M. 1992. Approximate time-parallel simulation of queueing systems with losses.Proc. 1992 Winter Simulation Conference pp. 700-708.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.