Simulation of large scale networks III: an improved computational algorithm for round-robin service

ABSTRACT

We present an efficient algorithm for effecting round-robin service in discrete-event simulation systems. The approach generalizes and improves upon a previous approach in which a single arrival and a single departure event is considered and handled at a time; further, the previous approach is already an improvement over naive round-robin scheduling currently in use in simulation libraries. The prior proposal offered a run-time complexity of <i>O(n</i>²), because the processing of each event required an entire traversal of the job pool. We propose a generalized algorithm which includes the previous case and also accommodates burst arrivals and batch departures, further reducing run-time complexity to <i>O (n</i> log <i>n</i>). This is achieved through a detailed but efficient computation of multiple departure times, while simultaneously obviating the need for a job pool update with each departure. Empirical results are presented to compare performance with previously proposed algorithms.

References

1. Cormen, T., C. Leiserson, R. Rives, and C. Stein. 2001. Introduction to Algorithms, Chapter 14: Augmenting Data Structures. 2d ed. Boston, MA: McGraw-Hill.
2. Fishman, G. S. 2001. Discrete-Event Simulation. New York: Springer-Verlag.
3. Law, A. and W. D. Kelton. 2000. Simulation Modeling and Analysis. 3d ed. Boston, MA: McGraw-Hill.
4. Mascarenhas, E. and V. Rego. 1996. Ariadne: Architecture of a Portable Threads system supporting Thread Migration. Software - Practice and Experience 26(3):327--357.
5. McHaney, R. 1991. Computer Simulation: A practical perspective. San Diego, CA: Academic Press. 1991.
6. Sang, J., K. Chung, and V. Rego. 1994. Efficient algorithms for simulating service disciplines. Simulation Practice & Theory 1:223--244.
7. Schwetman, H. D. 1988. Using CSIM to model complex systems. In Proceedings of the 1988 Winter Simulation Conference, ed. M. Abrams, P. Haigh, and J. Comfort, 246 - 253. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.