Dynamic lazy calendar queue: An event list for network simulation

Seung Hyun Oh, Jong Suk Ahn

Research output: Contribution to conferencePaperpeer-review

3 Scopus citations

Abstract

This paper proposes a new calendar queue which can improve the conventional calendar queue's performance over uneven event distributions. A calendar queue is a multi-list priority queue frequently employed in discrete event simulations as the global event list since its performance shows O(1) time complexity. For O(1) performance, calendar queues maintain only a small number of events at each list of their multi-list by constantly adjusting their multi-list size depending on the number of enqueued events and redistributing events over the newly resized multi-list. Calendar queues, however, perform poorly over skewed event distributions. Our proposed calendar queue can reduce this conventional calendar queue's sensitivity to event distributions by adding two new mechanisms; The first mechanism constantly measures the event distribution and according to the measured metrics reconfigures calendar queues' multi-list to maintain O(1) performance even for uneven distributions. The second mechanism adopts an additional data structure to save the time wasted for frequent resizing calendar queues. Our conducted experiments show that our calendar queue can achieve more than 10-time speedup for uneven event distributions while maintaining the same performance for other distributions.

Original languageEnglish
Pages254-265
Number of pages12
StatePublished - 1997
EventProceedings of the 1997 2nd High Performance Computing on the Information Superhighway, HPC Asia'97 - Seoul, South Korea
Duration: 28 Apr 19972 May 1997

Conference

ConferenceProceedings of the 1997 2nd High Performance Computing on the Information Superhighway, HPC Asia'97
CitySeoul, South Korea
Period28/04/972/05/97

Fingerprint

Dive into the research topics of 'Dynamic lazy calendar queue: An event list for network simulation'. Together they form a unique fingerprint.

Cite this