Discrete Event Simulation with Event Graphs

We give a bried introduction to the Event Graph syntax for describing discrete event simulations (DES) and give a few examples for illustration.

Objectives:

• How does the Event Graph syntax work?

• What are the limitations of Event Graphs?

• Why are there no modern simulators for Event Graphs?

Background¶

Event graphs (EGs), sometimes also called simulation graphs, is a graphical model description language for DES models (see Discrete-Event Simulation - Basics). It was developed in 1983 by Lee Schruben together with the corresponding SIGMA simulator which is specifically designed for simulation EG models Schruben (1983),Schruben (1992). The EG notation provides a good introduction to DES model description forms, as it provides a good balance between flexibility (there are no restrictions on the application area) and simplicity (the syntax is easy to read and does not require any deeper mathematics).

Event Graph Syntax¶

Figure 1 depicts a minimalist EG which already contains (almost) everything one needs to know to understand the syntax.

• The nodes of the directed graph represent the event types (here $A$ and $B$) and underneath the nodes one finds how an event with the corresponding type updates the state. In the given example, an occurrence of an event of type $A$ causes the state variable $x$ to be changed to the value of $y$. Using a leftarrow $\leftarrow$ for variable assignment is common, using $:=$ as assignment operator is also possible. Also using “$++$” or “$--$” to specify increments/decrements by one is common. The absence of such a description means that the event does not cause any state changes.

• The edges, usually called scheduling edges in EGs, illustrate how events schedule each other. An arrow out of one node into another node means that an occurrence of an event of the prior type causes scheduling of an event of the latter type. Note that a scheduling edge could also leave and enter the same node if an occurrence of the node should re-schedule itself. In the depicted minimalist example, an occurrence of an event of type $A$ schedules an event of type $B$. To define the exact details of the scheduling, there are two further features of the edge:

• Any variable written next to an outgoing scheduling edge desribes the time delay in which the event should be scheduled. In the given example, the event of type $B$ will always be scheduled $t$ time-instance after the occurrence of the $A$-type event. In case this number is stochastic, it is usual to write the corresponding distribution at this place, e.g. $\Gamma(a,b)$, when the delay should follow a Gamma distrbution with parameters $a$ and $b$. In the absence of such a variable, a delay of 0 will be applied.

• A large hook symbol on top of the edge illustrates that there is a condition under which the event schould (or should not) be scheduled. The corresponding condition is written right above (or next) to the hook. In the given minimalist example, conditon $c$ must be fulfilled to allow scheduling. In case the condition is not fulfilled, the scheduling edge is ignored. Usually the conditions refer to the current values of the states, and randomness can be introduced by adding random variables. E.g. writing $U<0.5$ would usually imply that a coinflip decides about the scheduling (a $U(0,1)$ uniformly distributed random variable $U$ is smaller than 0.5 in $50\%$ of the cases. The absence of a hook is interpreted as unconditioned scheduling.

Summarising, the minimalist example in Figure 1 reads as follows: An occurrence of an event with type $A$ changes the state of the system variable $x$ to $y$ and leads to scheduling of an event of type $B$ with a time delay of $t$. For the sake of completeness, the occurrence of an event of type $B$ does not cause any state changes and no further events to be scheduled.

Since a DES model cannot start with an empty event list, it is necessary to specify an event type to be used as entry point for the model. Conventionally, this event type is called Run (or Start) and is used to initialise the state variables and start the chain of model events.

Case-Study: Arrival Process - Event Graph¶

The EG depicted in Figure 2 is a very typical figure in discrete event modelling. It shows the so called arrival process and models the buildup of a queue, e.g. tourists queuing in front of a museum before it opens. Hereby, entities enter the system from outside the system boundaries and start queueing. Therefore, the event causes a queue length to increment by one. Since the origins of the event lie outside the system boundaries, the event must necessarily re-schedule itself to model a continuous stream of new entities. Using an exponential distribution with parameter $\lambda_a$ for the time between arrivals (also called interarrival time) the event graph depicts a Poisson process in which, on average, $\lambda_a$ new entities enter the system per time unit. In case the entities entering the system are independent and nothing is known about their entry times, ths process is usually the best modelling choice due to its property of being memoryless.

Case-Study: Arrival Process - Implementation¶

At this point we could use the same strategy for the implementation as we did in Discrete-Event Simulation - Basics. However, to keep the focus of this notebook on the conceptual modelling and not on the implementation, we will use a simple library we have written ourselves, which allows us to simulate event graphs almost direcly. Nodes and edges can be added to the EventGraph object analogous to other network implementations (e.g. networkx). State changes, scheduling times, and conditions are added in form of functions depending on two variables:

• an instance of a random number generator to generate random variables of arbitrary distributions (rng)

• a dictionary containing the current states (state)

State change functions must alter the state dict, scheduling time functions must return a positive float as scheduling delay and conditons must return a bool variable to speficy if the condition is fulfilled. In case they are easy enough, the latter two can usually be implemented inline as lambda functions.

The graph is run using the corresponding command passing a desired end-time and a random number seed which makes the generation of random elements reproducible.

We see how the queue builds up continuously with time. Due to the lam=1 expected arrivals per time it is expected to hold $t$ entities at time $t$. One also sees one of the fundamental properties of the exponential distribution, namely that the intrervals between events can, in principle, get arbitrarily long. Whilst most events follow on from one another in very quick succession, there are a few events where the intervals between them are really long, for example, between event 3 and 4 in the simulation run with seed=12346.

Case-Study: Single Server Queue¶

We already know of the arrival process to generate entities and put them into a queue. Now it is time to do something with the queueing objects to help them to not wait forever. For this purpose, we define a so-called server which, provided it is free, removes one object at a time from the queue and processes it. This so called single server queue system models, e.g. a cashier desk in a supermarket or at a job shop in a manufacturing hall.

Similar to the interarrival time, hereafter denoted as $t_a$, a so-called service time $t_s$ must be defined for this purpose, which indicates how long the server takes to process the entity. For now, we continue with $t_a\sim Exp(\lambda_a)$ and have $t_s$ follow the same distribution, i.e. $t_s\sim Exp(\lambda_s)$.

We with to model this system as a straightforward extension of the arrival process. One version is depicted in Figure 3. Here, we add a boolean-valued second state $S$ defining whether the server is idle ($true$) or busy ($false$) and define, that an arriving entity may immediately trigger the service to start in case the server is idle (conditioned scheduling edge between Arrival and Start Service). The Start Service event renders the server busy ($S\leftarrow false$), and it remains busy until the service is completed (scheduling edge between Start Service and End Service). The latter event renders the server idle again.

However intuitive this image may be, it is unfortunately incorrect. We will explain why by looking at some example simulation results.

It is clear at first glance that the model itself cannot be entirely correct. Although there are still entities in the queue, the server often switches to idle mode for a while. The reason for this is that in the current model version the Start Service event can only be triggered by an Arrival event. However, the event should also be triggered in case the server becomes idle and there are still entities in the queue. This leads to the correct version of the single-server queue displayed in Figure 4.

The corrected model finally shows the expected behaviour. Look at the event-log and see that the EndService events are almost always instantaneously followed by StartService events in the correct model which is not the case in the incorrect version.

This result teaches us an important lesson in event-driven modelling: scheduling for interactions between entities and resources must be bidirectional. Just as an entity must request a resource, a resource that has become available must also check whether it is needed by an entity. However, the fact that active actions must also be defined for objects that are intuitively perceived as passive can be seen as a weakness of the Event Graph formalism.

Case-Study: Multiple Server Queue¶

With the extension of S from a boolean-valued state to an integer-valued state, the model described above instantly becomes a system with multiple servers. All conditions and state changes extend naturally (see Figure 5). This so called multiple server queue is one of the most important building blocks of discrete event simulation in general.

As said, the multiple server queue is one of the most important model in discrete event simulation and occurs frequently as building block in larger models. We refer to Case Study: Multiple-Server Queue for a more in-depth case study on the system and put our focus now on more fundamental problems/propertiees of EG and DES.

Case-Study: Multiple Server Queue - Simultaneous Events¶

Below, one finds an implementation of the multiple server queue with deterministic interarrival and service times ($k=1,t_a=1,t_s=2.5$). We argue that something goes wrong here, however it is not intutitvely clear what.

So the bad stuff apparently happens at $t=6$ where suddenly the number of available servers $S$ drops below 0. Looking at the event-log we find that there is a lot going on at this point in time, in particular an EndServive and an Arrival event take place at the same time. While it is not unusual that multiple events take place at the same time, in particular when one event schedules the other with delay 0) this situation is different now: both events were scheduled from different sources (the Arrival event was scheduled by another Arrival event and the EndService by a StartService event) and both notices have been queued in the event list at the same time. It is coincidental that they occur at the same time and there is ad hoc no logical reasoning to decide which of the two should be executed first. In this case, the simulator simply sorts the events by creation index which, in this case, ranks the Arrival in fron of the other.

In most situations, conicidentally simultaneous occurrence of events does not cause any conflicts, however, in this case it makes a huge difference. We resolve the problematic situation:

1. At $t=6$, before execution of any event, there are entities waiting in the queue $Q>0$ and no server is idle $S=0$.

2. With the EndService event at $t=6$, a server becomes available ($S\leftarrow 1$) and looks for entities to serve. Since there are, indeed, entities waiting, it schedules a StartService event.

3. At the same time, an entity starts queueing and looks for an idle server. Due to the previously executed EndService event, there is indeed $S>0$ and another StartService event is scheduled.

4. Now, the harm is done with two scheduled StartService events for one idle server.

Of course, the problem could have been prevented with a different execution order. Suppose, the Arrival event was executed before the EndService, it would find $S=0$ and would not schedule a new service. Alternatively, if StartService (scheduled directly from EndService) was executed before the Arrival event, we would have the same situation. This is also visualised in Figure 6.

Prioritisation¶

The solution to the described problem is given by the idea of prioritisation. Hereby we tell the simulator which order of execution is, in case of simultaneous events, the causally correct one. Hereby, every event notice (event type) is given a certain priority whereas, in case of equal scheduling times, notices with higher priority are executed first.

Case-Study: Multiple Server Queue - Prioritisation¶

For the multiple server queue, the most logical problem solution would be to make sure that the StartService event is always executed right after the event which scheduled it. This way we make sure that ressources are directly spent after they are allocated. That means, this event type will be given a higher priority than the others.

In the implementation it is sufficient to set it’s priority to 1 since 0 is the default priority of a node.

The specification of a higher priority did the trick. The StartService at time $t=6$ was executed right after the EndService event. The Arrival event already found that the server was busy again ($S=0$) and did not schedule anything (except from a new arrival).

Event Graph Extension - Parametrised Events¶

In some situations, the EG notation introduced so far reaches the limits of what can be described. One example is that the concept of note types is essentially “memoryless” in the sense that an executed event contains no information about which other event scheduled it. Consequently, it cannot use this information to update the state change. One strategy to circmvent this problem is the idea of parametrised events which we are going to illustate on another case study.

Case-Study: Tandem Server Queue - Classic vs. Parametrised¶

The tandemo server queue is defined by two sequential multiple server queues. In this system, entities who left the first server start queueing at a second server. This system is depicted in Figure 7 using classic EG syntax. The system now has a 4-dimensional state with two servers $S1$ and $S2$ and a third parameter, that is, the parameter of the service time at the second server.

The event graph uses the same structure twice without adding any more logic. Suppose the system should be extended even further, the overall picture would become unreasonably large and crowded.

Using a parameter in an event makes it possible to reuse the same event type for something more specific. Figure 8 shows the same system, however, only one sequence of Start Servive and End Service event is depicted. Instead, the two event types are parametrised by the loop index: 1 referring to the first server, 2 referring to the second one. Together with a new Start Queuing event, which became necessary due to the new structure of the event graph, the sequence forms a loop which is entered with the Arrival event with index $i=1$. After two iterations, the loop is broken due to the conditon $i\leq 2$. It is clear, that this stucture is extremely flexible for adding e.g. a third or fourth server.

Note how events, wich use or pass-on parameters are marked with a $(i)$ symbol, and how scheduling edges which should pass on a parameter are labelled with a boxed parameter. Conventionally, the parameter update is computed first, before any new events are scheduled. Therefore, before starting the third iteration, the parameter update $i++$ already made $i=3$ before the condition $i\leq 2$ is checked.

Event Graph Extension - Cancelling Edges¶

Another event graph extension is given by the idea of cancelling edges. Instead of creating a new event notice of a certain type and adding it to the event list, these kind of nodes remove the next occurrence of a scheduled event with the given type from the list. We explain this on another case study.

Case-Study: Multiple Server Queue with Failure Probability¶

In the regarded system, the servers model machines with a certain proabability $p_f$ of breaking when in use. In case of such a failure, the machine would have to cancel its current service and wait for being repaired. Let $t_r\sim Exp(\lambda_r)$ be the time until a broken machine is repaired and ready to be used again, then, Figure 9 displays a model for the corresponding system using a parametrised EG. The idea is, that the Start Service event is parametrised with a uniformly distributed random number $u\sim U(0,1)$. In case $u$ is smaller than the failure probability $p_f$ then the Start Service will schedule the Failure event, otherwise it will regularly schedule the End Service event. The prior puts the entity back into the queue and the schedules a Fixed event with a time delay of $t_r$. This event behaves analogous to the End Service since the server becomes available again.

Although the use of parameterised events is correct here, the implementation of the system is, however, rather counterintuitive. The concept of cancelling edges, as discussed, offers an alternative. In Figure 10 a so-called cancelling edge is used to cancel the incorrectly scheduled End Service event. As a result, we do not necessarily have to define a random parameter $u$ anymore, but may instead use the more intuitive syntax $U<p_f$ to specifiy that the event is scheduled with a given likelihood.

As soon as a cancelling edge is activated, the event list is searched for the next occurrence of an event notice with the given type (and, if provided, the given parameter) and cancels it. Note that these edges only cancel one event notice with the given type and not all of them.

It should be noted, that scheduling and cancelling of the End Service event will consume a random number for the delay. Therefore it is impssible to get entirely identical results with the two implementations. To be fully precise, the results are not even equivalent in theory, since the scheduling edge will cancel the next occurrence of the event which is not necessarily the one which has just been scheduled by the Start Service.

Anyway, as noted in Discrete-Event Simulation - Basics, removal or modification of event should generally be avoided in discrete event simulation for performance reasons. As a result, cancelling edges should only be used in case there are no (or only very complicated) alternatives.