A cache aware speedup algorithm for discrete event simulations

In this paper, a speedup event scheduling algorithm is proposed to benefit CPU caching for large scale networks simulations. A digest queue over a ring-typed array is introduced to classify discrete event list. The analysis of the proposed algorithm gives that the operation ENQUEUE complexity is near O(sqrt(n/10)) and DEQUEUE O(1), better than widely used calendar queue (CQ) algorithm and some improved. Experiments by NS2 are conducted to evaluate performance empirically for a network with 100 nodes and 9900 concurrent demands. It results in a speedup factor 37 in comparison with CQ.