Simultaneous Events

Discrete-event simulation is a widespread technique for the analysis and performance evaluation of systems. The simulated system is modeled by a set of state variables, activities are represented by events. Each event consists of a timestamp as well as an associated action. All future events are stored in an event list and are executed by a scheduler in the order of their timestamps.

A well-known challenge in discrete-event simulation is the problem of simultaneous events: If two or more events contain identical timestamps, their execution order is not clear. Moreover, different execution orders may lead to different states, and thus to different simulation results. Commonly, simultaneous events are handled by tie-breaking rules, which use priorities in order to enforce well-defined orderings and thus reproducible simulation results.

While tie-breaking rules are an accepted solution, they may be criticized as well: By choosing only execution order of simultaneous events, all others are implicitly labeled as irrelevant (or wrong). As a consequence, only one out of possibly many correct simulation results is selected without caring about the others. This questions the significance of simulation results. Therefore, in order to increase confidence in simulation results, it may be useful to have means of analyzing the effects of simultaneous events.

In the project Simultaneous Events in Discrete-event Simulation of Computer Networks, we have developed a branching mechanism which analyzes simultaneous events during run-time of the simulation. When different execution orders lead to different states, the simulation run is split into multiple branches, and a set of simulation results is computed. We implemented the branching mechanism for the simulation tool MOOSE. Thereby, we applied different techniques in order to restrict branching to cases the user is really interested in, and thus managed to make branching a practical method.

While MOOSE was initially developed as a sequential simulation tool, we examined various ways of parallelizing the simulation in the further course of the project. First of all, we extended MOOSE so that newly created branches may be distributed onto other hosts for computation. This can strongly reduce simulation run-times when analyzing simultaneous events. Our second approach was the extension of MOOSE to a real distributed simulation tool. In distributed simulation, a simulation run is partitioned into multiple logical processes and then distributed among the participating hosts. This way, all hosts jointly compute a single simulation scenario. For the synchronization of the logical processes, MOOSE provides both conservative and optimistic synchronization. Although the handling of simultaneous events is much more complex here (for example, already the efficient detection of simultaneous events proves hard), we successfully implemented the branching mechanism for distributed simulation, too. This constitutes an important contribution in the research area of distributed simulation.