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: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 2: George S. Fishman, Discrete-event simulation, Springer-Verlag, London, 2001
• 3: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 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: Roger McHaney, Computer simulation: a practical perspective, Academic Press Professional, Inc., San Diego, CA, 1991
• 6: Janche Sang , Ke-Hsiung Chung , Vernon Rego, Efficient algorithms for simulating service disciplines, Simulation Practice and Theory, v.1 n.5, p.223-244, May 16, 1994 [doi>10.1016/0928-4869(94)90012-4]
• 7: Herb Schwetman, Using CSIM to model complex systems, Proceedings of the 20th conference on Winter simulation, p.246-253, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318197]