A PERFORMANCE COMPARISON OF EVENT CALENDAR ALGORITHMS - AN EMPIRICAL-APPROACH

We propose a suite of tests based on two-state Markov chains for exper imentally assessing the dynamic performance of a variety of simulation event calendar implementations. In contrast to previous studies based on the standard hold model for evaluation of performance statically, the proposed Markov hold model is more general and can be used to exam ine how different implementations respond dynamically to dependent seq uences of insertion and deletion requests. The Markov hold model is us ed to conduct tests based on random, stressed, and correlated input se quences of requests, with performance measures including completion ti mes, sensitivity to correlations, sensitivity to duplication, and effi ciency of data-handling. We apply these tests to fourteen different ev ent calendar implementations. To demonstrate the utility of the propos ed model, we also include a comparison of the event calendar algorithm s on a token ring protocol with bursty Markovian packet-traffic.