TimeNet - Examples of Extended Deterministic

and Stochastic Petri Nets

Christoph Hellfritsch
February 2, 2009

Abstract
TimeNet is a toolkit for the performability evaluation of Petri nets.
Performability is a composite measure of the performance of a system and
it’s dependability. This software provides the graphical and interactive
modeling of stochastic Petri nets and stochastic colored Petri nets. This
document was written in the course of an advanced seminar. It contains
four examples of stochastic Petri nets and some results of the analysis and
simulation with TimeNet. Examples of stochastic colored Petri nets can
be find in [Meis09].

1 Queue
In this chapter a M/M/1/K Markovian queue is modeled. We assume that there
are K clients and only one server. The server provides an exclusive service. That
means only one client can use this service at the same time. So when two users
want to use the service simultaneously one have to wait till the other has finished.
The rate of the incoming requests from the servers point of view is the arrival
rate λ. The reciprocal of the time the server needs to serve one client is called
the service rate µ. Both rates are exponential distributed. To keep the system
alive, we assume that λ < µ. In this model we define that every 60 seconds a
request arrives (1/λ = 60s) and the server needs 50 seconds to treat a request
(1/µ = 50s).
The Petri net in Fig. 1 models the behavior above. This net consists of two
places and two transitions. The place idle corresponds to the clients that are
working on their own. The initial marking is users which is defined on the
right hand side in the figure. The place queue contains these clients which want
to use the service from the server. But the server can handle only one client
simultaneous. So the other tokens in this place have to wait. The transition
arrival is an exponential transition with a mean delay of 60 seconds. It models
the firing rate of the requests for the service. The transition service models the
working time for the service which the server provides. This transition is also
exponential distributed with a mean delay of 50 seconds.

1
 Figure 1: TimeNet model of a queue

Let’s assume that there were 100 users in the model (users = 100). Refer to
the model in Fig. 1 there were 101 states. In the first state are all tokens in the
place idle. Then one token is taken from idle and put in queue until all tokens
are in the place queue. TimeNet provides a function to calculate the statespace
of a model. Fig. 2 shows a screenshot of the result of the statespace estimation
with 100 users. And Fig. 3 shows the result of the structure check.

Figure 2: Result of a statespace estimation

In [BGMT06] and [Seit08] the utilization ρ, mean queue length Q̄ and the
mean waiting time in the system W̄ are defined as follows:
mean service time arrival rate λ
ρ= = =
mean interarrival time service rate µ

ρ2 Q̄
Q̄ = and W̄ = .
1−ρ λ
These values have been computed by definition as well as by the stationary
analysis of TimeNet. The theoretical values are substantiated by the analysis.
Tab. 1 shows the results of the model with 100 users (M/M/1/100 queue).

2
 Figure 3: Result of a structure check

The utilization and thus the mean queue length and waiting time depend
on the numbers of users in the queue. TimeNet has the ability to modify one
parameter of the model. This is possible during a stationary analysis or a
stationary simulation and called experiment. The data of an experiment were
saved in the file queue.expresults in the model directory. In the left hand side of
Fig. 4 the parameter users has been modified during a stationary simulation.
It shows the results of the three measurements defined above as a function of
the number of users in the system.

Value TimeNet results

ρ 0.833
Q̄ 4.167
W̄ 250.0

Table 1: Queue: theoretical values and results of the TimeNet analysis

TimeNet also provides the opportunity for a transient analysis of the model.
This results in one curve per defined measurement as a function of the model
time. The computed data is saved in the file queue.curves in the model directory.
The right part of Fig. 4 depict the transient analysis of the measurements.

3
Figure 4: Left: results of the experiment; Right: results of the transient analysis

2 Shared Memory
Here we regard a simple shared memory system as shown in [BaSi98]. Two
processors want to access a common shared memory. Both of them have the
same behavior. They work locally for some time, then they request the access to
the shared memory and finally they access it. The shared memory is an exclusive
and not revocable resource. While one processor accesses the shared memory
the other one has to wait till the first has finished it’s access. So the time for one
cycle of a processor is the sum of the local working time, the memory accessing
time and the time the processor has to wait for accessing the shared memory.
The net consists of seven places and six transitions. We define that if the shared
memory is not in use one processor can access immediately. Because of this two
transitions are immediate transitions and the others are exponential transitions.
Fig. 5 depicts this model.
In the initial marking the two processors p1 and p2 are in the local work-
ing process and the shared memory is in idle state. The places processor p1,
processor p2 and shared memory idle contain each one token. The delays
of the two processors are defined in the middle of Fig. 5. They are named
local working time p1 for processor p1 and local working time p2 for proces-
sor p2 respectively and belong to the transitions request p1 and request p2
respectively. According to these delays in the next step processor p2 request
the shared memory. The transition request p2 fires, the token contained in
processor p2 is removed and a token is added in the place wait p2. While
the shared memory is idle the processor p2 can acquire the memory immedi-
ately. Transition acquire p2 fires, the token in wait p2 is removed and a token
is added in access p2. Now processor p2 accesses the shared memory for the

4
 Figure 5: TimeNet model of a shared memory

time memory access time p2. After this time the transition f ree p2 fires and
the net return to it’s initial state. Another case is that while processor p2 ac-
cesses the shared memory processor p1 ends it’s local activities and requests
the shared memory. This means that transition request p1 fires, the token con-
tained in processor p1 is removed and a token is added in the place wait p1.
Now the shared memory is not available to processor p1. So p1 has to wait till
processor p2 has finished it’s access to the memory (till transition f ree p2 fires).

Measurement Result
utilization (shared memory) 0.369
utilization (p1) 0.802
throughput (p1) 0.032
waiting time (p1) 0.755

Table 2: Shared Memory: results of the TimeNet analysis

For demonstration some measurements have been taken. The utilization of

the shared memory and processor p1, the throughput of processor p1 and the
waiting time of processor p1. All these measurements are defined in the lower
part of Fig. 5. Tab. 2 shows the results of the TimeNet stationary analysis with
standard values.

5
3 AGV
In this section a model of an automated guided vehicle system (AGV) is consid-
ered. This AGV is part of an flexible manufacturing system (FMS). This model
is similar to that described in [Zimm08]. The FMS consists of three machines
(M1, M2 and M3) and two products (A and B).
At this point the FMS will be determined as follows. Product A has to pass
the machines M1 and M3 and product B has to pass machine M2. There are
three transportation operations needed. The raw product has to delivered to
the beginning of the machines and the manufactured product has to be taken
from the end of the machines. The third required transportation is only for
product A between the machines M1 and M2. All products are transported on
pallets. Fig. 6 shows the according Petri net. In initial state the place idleAGV
consists of one token and in the place emptyP are as many tokens as pallets
in the system. The exponential transition loadP models the loading time of a
pallet with a delay of 4. The loaded pallet is waiting in place loadedP until
the AGV is idle. The AGV can transport only one pallet at the same time.
The transportation operation is modeled as follows. The pallet has to wait till
the AGV is idle (place idleAGV has a token). Then the transition waitAGV 1
fires immediately so this is a immediate transition. Now the pallet is in the
AGV (place inAGV 1) for the time defined in the exponential transition AGV 1.
Here the transportation delay is defined in the variable AGV delay. The other
transportation operations are modeled analogue.

Figure 6: AGV: the early incomplete TimeNet model

Now the part is at the beginning of the manufacturing process in the place
choice. Now it has to be chosen if it should become a part of type A or B. This
is done by the immediate transitions partA and partB. Two weights probA
and probB are defined on the lower left corner of the model. They belong
to the transitions partA and partB respectively. The ratio of these weights
is also the ratio of the manufactured parts. The pass of a part through a

6
machine is modeled as follows. Assumed that the raw product should become
a product of type B. So the token is in the place BwaitM 2. Here the part
has to wait till machine M2 is ready. Then transition BsM 2 fires immediately.
The manufacturing process in machine M2 take some amount of time which is
modeled by the exponential transition M 2. Now the production is finished and
the AGV take the product from the machine. The manufacture of product A is
analogue but with two machines and another transportation operation between
them.
The model is not complete yet. Actual machine M2 can do the same man-
ufacturing steps as machine M3 and vice versa. So product A and product B
can be either manufactured in machine M2 or in M3. So an incorporation of
the two machines has to be modeled. Fig. 7 shows the complete model.

Figure 7: AGV: the complete TimeNet model

After passing machine M1 there is a token in the place AwaitM 2M 3. Now

the system has to decide whether the part of type A should be transported to
machine M2 or M3. Machine M3 is optimized for the manufacture of product
A and machine M2 is optimized for product B. So product A has a longer
manufacturing time in machine M2 than in M3, product B vice versa. So the
part of type A is transported to machine M3 if it’s idle, and only to machine M2
if machine M3 is busy and machine M2 is idle. The immediate transitions AsM 3,
AsM 2 and the places idleM 3, idleM 2 model this behavior. So if product A
arrives in AwaitM 2M 3 and machine M3 is idle (token in idleM 3) then transition
AsM 3 fires. But if machine M3 is busy transition AsM 2 is treated. This
transition can only fire if product A is waiting (token in AwaitM 2M 3), machine
M3 is busy (no token in idleM 3), machine M2 is idle (token in idleM 2) and no
part of type B is waiting (no token in BwaitM 2M 3).
Places AinM 3, BinM 3, AinM 2, BinM 2 and the transitions M 3A, M 3B,
M 2A, M 2B models the actual manufacturing steps. The delays of all exponen-

7
 Transition Delay
loadP 4
AGV1/AGV2/AGV3 AGVDelay
M1 10
M3A 10
M3B 30
M2A 15
M2B 20

Table 3: AGV: delays of all exponential transitions

tial transitions are listed in Tab. 3. Every immediate transition has the priority
one.
Some typical measurements have been taken. There is only one AGV in
the system. The utilization of it is an important factor in the model. The
measurement utilization AGV corresponds to it and can be computed by the
probability P (place idleAGV has no token).
The mean number of pallets that are not in use corresponds with the mean
number of tokens in the place emptyP . The measurement empty pallets com-
putes this value.
The utilization of machine M1 corresponds to the probability P (place AinM 1
has a token). For machines M2 and M3 the probabilities P (place idleM 2 has no
token) and P (place idleM 3 has no token) respectively are computed because
these machines are in use if there is no token in the ”idle” place.
Further on the throughputs of the machines are measured. For example the
throughput of machine M1 represents the production of parts of type A. This
is computed by utilization of machine M1 divided by the manufacturing time of
one part in machine M1 (delay of transition M 1). The throughput of transition
M 1 is equal to the sum of the throughputs of transitions M 2A and M 3A. The
simulation with TimeNet confirms this fact. Thus the production of part B is
represented by the added throughputs of transitions M 2B and M 3B.

Measurement Result
utilization of AGV 0.330
number of empty pallets 0.645
utilization of M1 0.517
utilization of M2 0.906
utilization of M3 0.896
throughput of M1 0.052
throughput of M3A 0.035
throughput of M3B 0.018
throughput of M2A 0.016
throughput of M2B 0.033

Table 4: AGV: results of the simulation

8
 For the calculation of these measurements (which are defined below the
model in Fig. 7) a simulation with TimeNet has been run. The results are
shown in Tab. 4. The parameter of the simulation are the standard ones except
for the ”maximum relative error” and the ”permitted difference for probability
measures close to 0.0 or 1.0”. These two values has been chosen to one. Further
informations to the simulation parameters can be found in the TimeNet manual.

4 GSM-R
This is an example of an GSM-R (Global System for Mobile Communications –
Rail(way) as in [Zimm08]). In GSM-R three main failures can occur. The first
is a transmission error. Your transmissions get lost but the connection is still
established. This can occur because of a temporarily bad radio signal condition.
The second is a complete loss of the connection. This is detected by the train
hardware after some timeout. A new connection has to be established. In few
cases the establishment failed so that it has to be started again. The third
failure are handovers. They occure when the train passes the border between
two neighbored communication cells. Then the trains hardware has to connect
to the next base transceiver station (BTS).
The behavior described above is modeled in the Petri net in Fig. 8. The
transitions delays have been chosen as in [Zimm08]. One second in real time
is equivalent to one unit of model time. All firing delays has a technical back-
ground.

Figure 8: TimeNet model of a GSM-R

The Petri net can be seen as a state machine. At the beginning only the
place connected has one token. This means that the GSM-R link is established
correctly.

9
 The upper left branch of Fig. 8 models the transmission errors. The expo-
nential transition startburst models the beginning of an burst. It’s required
that the mean time of the occurrence of a transmission error is greater than or
equal 7 seconds in 95% of all cases. The density function and the distribution
function of the exponential distribution are

f (x) = λe−λx and F (x) = 1 − e−λx .

Hence the parameter λ can be calculated to

ln p
λ=− ≈ 0.00733 with probability p = 0.95 and x = 7
x
and implicates a mean delay of 1/λ = 136.47 seconds for transition startburst.
Transmission errors takes less than 1 second in 95% of all cases. So the delay
of transition endburst is set to 0.333 because of
1 x
=− ≈ 0.333 with probability p = 0.05 and x = 1.
λ ln p
The lower left branch of Fig. 8 models a handover. Under the assumption
that the mean distance between two BTS is 7 km and the train speeds up to 500
km/h a handover occurs every 50.4 seconds. The transition cellborder models
the crossing of the cell border. It’s an exponential transition with the mean
delay of 50.4. The reconnection is modeled with the deterministic transition
reconnect. It is specified that this takes 300 ms.
The right part of Fig. 8 models the complete loss of the connection. This
occurs only 2.77 ∗ 10−8 times per second or every 36101083 seconds. The ex-
ponential transition loss models this delay. To indicate the loss requires circa
one second but not more than one second. The deterministic transition indicate
models this behavior. Now the connection loss is indicated and the trains hard-
ware tries to reconnect the system immediately. This succeeds in 99.9% of
all cases. Otherwise the re-establishment is canceled after 7.5 seconds and re-
tried. The weights of the immediate transitions estp (weight = 999) and f ailp
(weight = 1) models the probabilities of the success/fail of reconnection. The
waiting time in fault is modeled by the deterministic transition f ail with a delay
of 7.5. If the establishment succeeds it takes a random time to reconnect to the
BTS but less than 5 seconds in 95% of all cases. Therefor the transition connect
is exponential distributed with a delay of 0.6.
Tab. 5 shows the result computed by the stationary analysis of this Petri net
with TimeNet. The calculation equations of all measurements are situated in
the lower part of the model in Fig. 8. The values of the TimeNet analysis have
only 7 significant digits. So the measurements m loss indication, m establish
and m estf ail can not be taken as a reference. The exact values can be taken
from [Zimm08, p. 297].

10
 Place/State Numerical Probability Simulated Probability
Connected 0.99166 0.99167
Burst 2.4305 ∗ 10−3 2.427 ∗ 10−3
Handover 5.9027 ∗ 10−3 5.9028 ∗ 10−3
Loss indication 2.7546 ∗ 10−8 0.0
Establish 4.5910 ∗ 10−8 0.0
Estfail 2.0680 ∗ 10−10 0.0

Table 5: GSM: comparison of numerical and simulated results

5 Summary
This document describes four examples of stochastic Petri nets: a queue, a
shared memory, an AGV and a GSM-R system. These Petri nets were modeled
in TimeNet and some analytical methods of TimeNet has been tested on them.
[Meis09] discuss some examples of stochastic colored Petri nets.

A Literature
References
[BaSi98] G. Balbo und M. Silva. Performance Models for Discrete Event Sys-
tems with Synchronisations: Formalisms and Analysis Techniques,
1998.
[BGMT06] Gunter Bolch, Stefan Greiner, Hermann de Meer und Kishor S.
Trivedi. Queueing Networks and Markov Chains: Modeling and
Performance Evaluation with Computer Science Applications, 2006.
[Meis09] Andreas Meister. TimeNet - Examples of stochastic coloured Petri
Nets, Institut für Technische Informatik und Ingenieurinformatik,
FG System- und Software-Engineering, 2009.
[Seit08] Jochen Seitz. Computersimulation nachrichtentechnischer Systeme,
Institut für Informationstechnik, FG Kommunikationsnetze, 2008.

[Zimm08] Armin Zimmermann. Stochastic Discrete Event Systems: Modeling,

Evaluation, Applications, 2008.

11