Ioanis Nikolaidis
ABSTRACT
The multiplexing of several lightly loaded links onto a more heavily loaded output link is a problem of considerable importance to the design and traffic engineering of many types of packet-oriented telecommunications equipment, including that used in Asynchronous Transfer Mode (ATM) networks. Network configurations generally require the cascaded operation of such multiplexers and switches. Important objectives to achieve small cell loss ratios while maintaining efficient utilization of the transmission links. The small cell loss ratio objective results in extremely long simulation runs. To address this problem, we propose a new technique that relies on a compact description for the arriving/departing traffic at the multiplexers and a time-parallel scheme without fix-up phases for effective parallelization. The technique does not make assumptions about the analytical nature of the arrival process, thereby allowing trace-driven simulations to be performed as well. We demonstrate the method for a number of configurations and traffic scenarios, and observe that it yields one to two orders of magnitude speedup on a 32 processor Kendall Square Research KSR-1 multiprocessor compared to an efficient cell-level simulation executing on a Sparc-10 workstation.
- 1.The ATM Forum, "ATM User-Network Interface Specification, Version 3.0," Mountain View, California, October 29, 1993. Google Scholar
Digital Library
- 2.E Baccelli and M. Canales, "Parallel Simulation of Stochastic Petri Nets Using Recurrence Equations," Performance Evaluation Review, vol. 20, no. 1, pp. 257-258, June 1992. Google ScholarDigital Library
- 3.Bellcore, "Synchronous Optical Network (SONET) Transport Systems: Common Generic Criteria," Document Number TR-NWT-000253, Issue 2, December 1991.Google Scholar
- 4.CCITT Study Group XVIII, "Recommendations Drafted by Working Party XVIII/8 (General B-ISDN Aspects) to be Approved in 1990," Document Number COM XVIII-R 34-E, Geneva, June 1990.Google Scholar
- 5.K. M. Chandy and J. Misra, "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs," IEEE Trans. on Software Engineering, vol. SE-5, no. 5, pp. 440-452, September 1979.Google ScholarDigital Library
- 6.D. Cohen and D. Heyman, "A Simulation Study of Video Teleconferencing Traffic in ATM Networks," Proc. IEEE INFOCOM '93, pp. 894-901, 1993.Google Scholar
- 7.C.A. Cooper and T. Eliazov, "A Study of the Statistical Multiplexing Efficiencies Achievable with Variable Bit Rate Traffic on a BISDN," Internal Bellcore Technical Memorandum, 1991.Google Scholar
- 8.R. M. Fujimoto, "Parallel Discrete Event Simulation", Comm. ACM, vol. 33, no. 10, pp. 30-53, October 1990. Google ScholarDigital Library
- 9.A. G. Greenberg, B. D. Lubachevsky and I. Mitrani, "Algorithms for Unboundedly Parallel Simulations", ACM TOCS, vol. 9, no. 3, August 1991, pp. 201-221. Google ScholarDigital Library
- 10.H. Heffes and D. M. Lucantoni, "A Markov Modulated Characterization of Packetized Voice and Data Traffic and Related Statistical Multiplexer Performance," IEEE JSAC, vol. SAC-4, no. 6, pp. 856-868, September 1986.Google ScholarDigital Library
- 11.P. Heidelberger and H. S. Stone, "Parallel Trace-Driven Cache Simulation by Time Partitioning," Proc. 1990 Winter Simulation Conference, pp. 734-737, 1990. Google ScholarDigital Library
- 12.P. Heidelberger, "Fast Simulation of Rare Events in Queueing and Reliability Models", Tutorial Proceedings, Performance '93, Springer-Verlag, 1993. Google ScholarDigital Library
- 13.D. R. Jefferson, "Virtual Time," ACM Transactions on Programming Languages and Systems, vol. 7, no. 3, July 1985, pp. 404-425, July 1985. Google ScholarDigital Library
- 14.Y.-B. Lin and E. D. Lazowska, "A Time-Division Algorithm for Parallel Simulation," ACM Trans. Modeling and Computer Simulation, vol. 1, no. 1, pp. 73-83, January 1991. Google ScholarDigital Library
- 15.Y.-B. Lin, "Parallel Trace-Driven Simulation for Packet Loss in Finite-Buffered Voice Multiplexers," Parallel Computing, vol. 19, no. 2, pp. 219-228, February 1993.Google ScholarCross Ref
- 16.I. Nikolaidis, R. M. Fujimoto, C. A. Cooper, "Parallel Simulation of High-Speed Network Multiplexers," in Proc. of the 32nd IEEE Control and Decision Conference, pp. 2224-2229, San Antonio, TX, 1993.Google ScholarCross Ref
- 17.S. Parekh and J. Walrand, "A Quick Simulation Method for Excessive Backlogs in Networks of Queues", IEEE Trans. Automatic Control, vol. 34, no. 1, pp. 54-66, January 1989.Google ScholarCross Ref
- 18.Ph.D. thesis of the first author, under preparation, College of Computing, Georgia Tech.Google Scholar
- 19.J. J. Wang and M. Abrams, "Approximate Time- Parallel Simulation of Queuing Systems with Losses," Proc. 1992 Winter Simulation Conference, pp. 700-708, 1992. Google ScholarDigital Library
- 20.J. J. Wang and M. Abrams, "Determining Initial States, , th for Time-Parallel Simulations, Proc. 7 Workshop on Parallel and Distributed Simulation, pp. 19-26, 1992. Google ScholarDigital Library
Index Terms
- Time-parallel simulation of cascaded statistical multiplexers
Recommendations
Time-parallel simulation of cascaded statistical multiplexers
The multiplexing of several lightly loaded links onto a more heavily loaded output link is a problem of considerable importance to the design and traffic engineering of many types of packet-oriented telecommunications equipment, including that used in ...
A parallel packet switch with multiplexors containing virtual input queues
A packet switch with parallel switching planes is a parallel packet switch (PPS). A PPS can scale-up to faster line speeds than can a single-plane switch. It is an open problem to design a PPS that is feasible to implement using existing low-cost ...
Demultiplexing considerations for statistical multiplexors
Proceedings of the ACM second symposium on Problems in the optimizations of data communications systemsDemultiplexing serves as an important function for statistical multiplexors. Its purpose is to reassemble the received message and distribute it to the appropriate destination. The demultiplexing buffer can be modeled as a finite waiting room queuing ...
Comments