WEBVTT
Kind: captions
Language: en
00:00:21.730 --> 00:00:30.270
This is stochastic processes model 5, Continuous-time
Markov Chain. In the lecture 1, we have discussed
00:00:30.270 --> 00:00:37.640
the definition, Kolmogorov differential equation,
infinitesimal generator matrix with examples.
00:00:37.640 --> 00:00:45.700
In the lecture 2, we have discussed birth
death processes. In the lecture 3, we have
00:00:45.700 --> 00:00:56.640
discussed Poisson processes. Lecture 4, we
have discussed M/M/1 queuing model.
00:00:56.640 --> 00:01:05.869
Simple Markovian queueing models with examples
is discussed in lecture 5. Queueing networks
00:01:05.869 --> 00:01:13.380
is discussed is discussed in lecture 6. Applications
in communication networks, simulation of simple
00:01:13.380 --> 00:01:21.789
Markovian queueing models with examples, I
have discussed in lecture 7. This is lecture
00:01:21.789 --> 00:01:26.420
8, stochastic petri nets.
00:01:26.420 --> 00:01:38.509
In this lecture, I am going to cover the definition,
simple examples followed by that stochastic
00:01:38.509 --> 00:01:44.860
petri nets, then generalised stochastic petri
nets, then finally stochastic reward nets.
00:01:44.860 --> 00:01:55.770
Petri nets
is a formal and graphical appealing language
00:01:55.770 --> 00:02:07.340
which is appropriate for modelling systems
with concurrency, Carl Adam Petri defined
00:02:07.340 --> 00:02:16.680
the language in 1962. Petri nets have proven
useful for modelling, analyzing and verifying
00:02:16.680 --> 00:02:25.540
protocols typically used in networks. It has
been under development since the beginning
00:02:25.540 --> 00:02:40.250
of the 60â€™ies. You can find the introduction
to petri nets in this website.
00:02:40.250 --> 00:02:48.599
Now we are going into the definition of petri
net. Petri net is a bipartite directed graph
00:02:48.599 --> 00:03:00.110
consisting of two kinds of nodes. The first
one is the places, the second one is transitions.
00:03:00.110 --> 00:03:09.739
Transitions that are connected by directed
edges or directed arcs. Arcs exist only between
00:03:09.739 --> 00:03:21.290
places and transitions that is there is no
arc between two places or two transitions.
00:03:21.290 --> 00:03:31.540
Places typically represent conditions within
the system being modelled; places typically
00:03:31.540 --> 00:03:37.290
represent conditions within the system being
modelled; they are denoted graphically as
00:03:37.290 --> 00:03:46.610
circles. Transitions represent events occurring
in the system that cause change in the conditions
00:03:46.610 --> 00:03:56.290
of the system; they are denoted graphically
as bars.
00:03:56.290 --> 00:04:06.421
See this diagram, here are the basic components
of a petri net. This is called input place
00:04:06.421 --> 00:04:16.579
and this arc is called input arc because the
arc is connecting from the place to transition
00:04:16.579 --> 00:04:26.070
and this is called, the line is called, this
bar is called a transition. The transition
00:04:26.070 --> 00:04:33.580
to the place that arc is called a output arc
and the corresponding place is called output
00:04:33.580 --> 00:04:44.810
place. The number of dots inside the place
is called tokens. Here input place has one
00:04:44.810 --> 00:04:53.190
token whereas this place has no token.
00:04:53.190 --> 00:05:03.351
The definition continues, input arcs, directed
arcs drawn from places to transitions; they
00:05:03.351 --> 00:05:12.290
represent the conditions that need to be satisfied
for the event to be activated. Output arcs
00:05:12.290 --> 00:05:20.060
are directed arcs drawn from transition to
places; they represent the conditions resulting
00:05:20.060 --> 00:05:29.740
from the occurrence of an event. The previous
diagram, this is the input arc because it
00:05:29.740 --> 00:05:36.730
connects place to the transition and this
is called output arc because it connects transition
00:05:36.730 --> 00:05:40.910
to place.
00:05:40.910 --> 00:05:47.170
Input places of a transition are the set of
places that are connected to the transition
00:05:47.170 --> 00:05:55.770
through input arcs. Output places of a transition
are the set of places to which output arcs
00:05:55.770 --> 00:06:06.740
exist from the transition. In this diagram
we have only one input place because the transition
00:06:06.740 --> 00:06:15.300
has only one input arc. With respect to the
same transition we have only one output place
00:06:15.300 --> 00:06:19.280
because we have one output arc.
00:06:19.280 --> 00:06:31.220
The definition continues, the tokens are dots
or integers associated with places; a place
00:06:31.220 --> 00:06:40.900
connecting tokens indicates that the corresponding
condition is active. That means, in the previous
00:06:40.900 --> 00:06:55.540
diagram, the one token deposited in the input
place means this transition can be activated.
00:06:55.540 --> 00:07:04.470
The place containing a tokens indicates that
the corresponding condition is active. Marking
00:07:04.470 --> 00:07:13.170
of a petri net is a vector listing the number
of tokens in each place of the net. That is
00:07:13.170 --> 00:07:14.320
called marking.
00:07:14.320 --> 00:07:25.610
When input places of a transition has a required
number of tokens then the transition is enabled.
00:07:25.610 --> 00:07:32.570
An enabled transition may fire, event happens
removing a specified number of tokens from
00:07:32.570 --> 00:07:43.730
each input place and depositing a specified
number of tokens in each of its output places.
00:07:43.730 --> 00:07:54.950
In the same example, before the transition
fires, one token in the input place, no token
00:07:54.950 --> 00:08:02.110
in the output place. Whenever there is a token
in the input place, then the condition is
00:08:02.110 --> 00:08:10.970
active. Then the transition first enabled,
after the transition enabled, it fires. After
00:08:10.970 --> 00:08:19.720
the transition fires the token will be removed
from the input place and the token will be
00:08:19.720 --> 00:08:23.060
deposited to the output places.
00:08:23.060 --> 00:08:29.990
So here we have only one input place and only
one output place therefore, after the transition
00:08:29.990 --> 00:08:37.380
fires, one token is removed from the input
place and one token is deposited in the output
00:08:37.380 --> 00:08:38.810
place.
00:08:38.810 --> 00:08:51.510
Now we will see another example, enabling
and firing of transitions. In this example,
00:08:51.510 --> 00:09:00.620
we have two places; here we have two places
one is called the place P on, the other place
00:09:00.620 --> 00:09:11.019
is called P off. Initially, two tokens deposited
in the place P on, no token in the place P
00:09:11.019 --> 00:09:20.790
off. We have two transitions one is the T
failure and the other one is T repair. Whenever
00:09:20.790 --> 00:09:32.740
the conditions are satisfied, then the transitions
will enable first and then it fires.
00:09:32.740 --> 00:09:42.699
Since two tokens are in the place P on, the
transition T failure enables whereas no token
00:09:42.699 --> 00:09:54.560
is in the place P off therefore the transition
T repair will not enable. If a T failure enables,
00:09:54.560 --> 00:10:02.329
then the required number of tokens will be
removed from the place P on and the required
00:10:02.329 --> 00:10:10.449
number of tokens will be deposited in the
place P off. So once the T failure enables
00:10:10.449 --> 00:10:13.959
and fires enabling and firing of transition.
00:10:13.959 --> 00:10:21.910
So when the T failure transition enables and
fires, one token will be removed from the
00:10:21.910 --> 00:10:29.220
place P on, one token will be deposited in
the place P off. Now the situation is this
00:10:29.220 --> 00:10:40.459
petri net. Since one token is in the place
P on as well as one token in the place P off,
00:10:40.459 --> 00:10:59.740
both the transitions T repair and T failure
enables. If T failure fires, then one token
00:10:59.740 --> 00:11:05.009
will be removed from the place P on and one
token will be deposited in the place P off.
00:11:05.009 --> 00:11:14.959
Already one token is in the place P off therefore
two tokens in the place P off and one token
00:11:14.959 --> 00:11:22.399
is removed from the place P on. Hence, zero
token in the place P on and two tokens in
00:11:22.399 --> 00:11:33.100
the place P off. Suppose at this stage, both
the T repair as well as the T failure enables
00:11:33.100 --> 00:11:47.959
but T repair fires, that means at this stage
if T repair fires then one token will be removed
00:11:47.959 --> 00:11:53.189
from the place P off and one token will be
deposited in the place P on.
00:11:53.189 --> 00:11:59.889
Therefore, when T repair fires then zero token
in the place P off, two tokens in the place
00:11:59.889 --> 00:12:09.309
P on. Similarly, in this situation no token
in the place P on, two tokens in the place
00:12:09.309 --> 00:12:17.779
P off, therefore, the T failure cannot enable,
the only enabling transition is a T repair
00:12:17.779 --> 00:12:25.379
therefore if this fires, T repair fires one
token will be removed from the place P off,
00:12:25.379 --> 00:12:32.041
one token will be deposited in the place P
on hence, one token in the place P off, one
00:12:32.041 --> 00:12:38.430
token in the place P on by T repair fires.
00:12:38.430 --> 00:12:46.149
So these are all the dynamics in the petri
net by enabling and firing of transitions.
00:12:46.149 --> 00:12:57.339
So this is a very simple example. We are going
to consider some more examples in this lecture.
00:12:57.339 --> 00:13:05.009
Now we are going to introduce another concept
called reachability analysis. Consider a petri
00:13:05.009 --> 00:13:18.470
net containing M places and N transitions.
A marking M(t) of a petri net is a M tuple
00:13:18.470 --> 00:13:27.559
with m1 of t, m2 of t, m3 of t and so on till
m suffix M of t because we have m places of
00:13:27.559 --> 00:13:37.790
non-negative integers where mi of t denotes
number of tokens in the place i at any time
00:13:37.790 --> 00:13:42.300
at any given instant of time t.
00:13:42.300 --> 00:13:49.180
We have m places therefore, if we make a m
table and number of tokens in each place at
00:13:49.180 --> 00:13:56.059
any given instant of time then that is called
a marking. For a given reference time t 0,
00:13:56.059 --> 00:14:05.749
M of t 0 is called an initial marking of the
petri net. M of t 0 is called as an initial
00:14:05.749 --> 00:14:15.160
marking of a petri net. A marking is reachable
from another marking if there exist a sequence
00:14:15.160 --> 00:14:22.540
of transition firings starting from the original
marking that result in the new marking.
00:14:22.540 --> 00:14:26.019
We will have some more concepts then we will
go for the examples.
00:14:26.019 --> 00:14:31.709
The reachability set of a petri net is a set
of all markings that are reachable from its
00:14:31.709 --> 00:14:41.240
initial marking through any possible firing
sequences of transitions. A reachability graph
00:14:41.240 --> 00:14:49.730
is a directed graph whose nodes are the markings
in the reachability set with directed arcs
00:14:49.730 --> 00:14:58.199
between the markings representing the marking
to marking transitions. The directed arcs
00:14:58.199 --> 00:15:05.110
are labelled with the corresponding transition
whose firing results in a change of the marking
00:15:05.110 --> 00:15:07.510
from the original marking to the new marking.