WEBVTT
Kind: captions
Language: en
00:00:05.200 --> 00:00:15.980
Now we are moving into Generalized Stochastic
Petri Nets.
00:00:15.980 --> 00:00:19.860
In other words, it's called GSPN.
00:00:19.860 --> 00:00:28.800
In GSPN, transitions are allowed to be either
timed or immediate.
00:00:28.800 --> 00:00:36.629
If you recall in the Petri Nets, the transitions
are immediate whereas in the stochastic Petri
00:00:36.629 --> 00:00:49.690
net the transitions are timed and we assume
that each time the transition is exponential
00:00:49.690 --> 00:00:59.110
distribution whereas in GSPN, the transitions
are allowed to be either timed or immediate.
00:00:59.110 --> 00:01:05.570
That means you have the combination of few
transitions could be timed, few transitions
00:01:05.570 --> 00:01:08.810
could be immediate also.
00:01:08.810 --> 00:01:14.479
Transitions with zero firing time, that is
nothing but the immediate transitions (drawn
00:01:14.479 --> 00:01:20.659
as thin black bars) are called immediate transitions.
00:01:20.659 --> 00:01:29.580
Immediate transitions have higher priority
over timed transitions.
00:01:29.580 --> 00:01:35.560
If several immediate transitions compete for
firing, firing probabilities should be specified
00:01:35.560 --> 00:01:41.310
to resolve these conflicts.
00:01:41.310 --> 00:01:47.389
Now let us consider an example for the GSPN.
00:01:47.389 --> 00:01:53.529
Consider M/M/1/5 queueing system.
00:01:53.529 --> 00:01:58.969
Here arrival follows a Poisson process with
the rate lambda.
00:01:58.969 --> 00:02:05.899
Service time is exponential distribution with
the rate µ; one server serving one job at
00:02:05.899 --> 00:02:13.890
a time; not more than five jobs permitted
in the whole system.
00:02:13.890 --> 00:02:30.220
So let us draw the stochastic, let us draw
the GSPN for the M/M/1/5 queueing system.
00:02:30.220 --> 00:02:36.610
M/M/1/5.
00:02:36.610 --> 00:02:44.200
We can use the stochastic Petri net which
we have drawn for M/M/1 queuing system.
00:02:44.200 --> 00:02:52.739
From that we can develop the M/M/1/5 queueing
system.
00:02:52.739 --> 00:02:55.049
That is the easy one.
00:02:55.049 --> 00:02:59.590
That is the advantage with the stochastic
Petri net GSPN and so on.
00:02:59.590 --> 00:03:04.120
From one model, you can always add some more
features to get the another model.
00:03:04.120 --> 00:03:11.030
So here we have a restriction with not more
than five jobs permitted in the whole system.
00:03:11.030 --> 00:03:21.130
So we can go for the M/M/1 queueing system
first.
00:03:21.130 --> 00:03:30.019
Then we can add, we can include the feature
of finite capacity.
00:03:30.019 --> 00:03:33.269
So this is M/M/1 queueing system.
00:03:33.269 --> 00:03:42.799
Now I have to make a restriction maximum 5
tokens in the place Psystem.
00:03:42.799 --> 00:03:54.540
So what I can do, I can draw two arcs.
00:03:54.540 --> 00:04:05.150
Whenever six tokens in the place Psystem,
all six tokens will be removed at the same
00:04:05.150 --> 00:04:07.409
time.
00:04:07.409 --> 00:04:16.340
Immediately, five tokens will be deposited
to the place Psystem.
00:04:16.340 --> 00:04:25.060
That means the latest token, when it comes
whenever the system size is five, the sixth
00:04:25.060 --> 00:04:34.700
token comes, then all six tokens will be removed
and in turn five tokens will be deposited.
00:04:34.700 --> 00:04:37.570
Therefore, one token is removed.
00:04:37.570 --> 00:04:41.480
So this transition is called tloss.
00:04:41.480 --> 00:04:46.140
So whenever I write small t, that means that
is the immediate transition.
00:04:46.140 --> 00:04:51.200
Whenever we write capital T, that means it
is a timed transition.
00:04:51.200 --> 00:04:57.950
So this timed transition with the empty rectangle
bar, that means it is exponential distribution.
00:04:57.950 --> 00:05:03.660
Sometimes we can write, we can draw the rectangle
bar with the shaded one.
00:05:03.660 --> 00:05:09.060
That is called the timed transition with the
constant time.
00:05:09.060 --> 00:05:21.330
So here this is the GSPN of M/M/1/5 queuing
system with the one place and two timed transitions
00:05:21.330 --> 00:05:26.440
and one immediate transition.
00:05:26.440 --> 00:05:34.800
If you see the reachability graph for this
GSPN, the possible number of tokens in the
00:05:34.800 --> 00:05:39.340
places, we have only one places, therefore,
the number of tokens in the places will be
00:05:39.340 --> 00:05:47.470
0, 1, 2, 3, 4 and 5.
00:05:47.470 --> 00:05:55.000
The markings can be possible with the transition
firing with the rate lambda, with the rate
00:05:55.000 --> 00:06:14.500
lambda and so on whereas 5 to 4, 4 to 3, 3
to 2, 2 to 1, 1 to 0, the transition firing
00:06:14.500 --> 00:06:16.160
with the rate µ.
00:06:16.160 --> 00:06:26.220
So this is the reachability graph for the
G -- the above GSPN, and this is same as the
00:06:26.220 --> 00:06:32.210
continuous-time Markov chain of M/M/1/5 queueing
system.
00:06:32.210 --> 00:06:40.410
Suppose your interest is to find out what
is the steady-state probability that the system
00:06:40.410 --> 00:06:42.470
is empty?
00:06:42.470 --> 00:06:49.800
That means what is the probability that the
system is empty, that is p0 in steady state?
00:06:49.800 --> 00:06:57.030
That is same as what is the probability that
-- what is the steady-state probability that
00:06:57.030 --> 00:07:01.020
the place Psystem has no tokens?
00:07:01.020 --> 00:07:04.080
Both are one and the same.
00:07:04.080 --> 00:07:11.650
In the CTMC, what is the probability that
the system is in the state 0 in steady state?
00:07:11.650 --> 00:07:20.940
That is same as what is the probability that
in steady state, the place Psystem has no
00:07:20.940 --> 00:07:22.730
tokens?
00:07:22.730 --> 00:07:31.870
Therefore, whatever the measures you wanted
for the system instead of making a continuous-time
00:07:31.870 --> 00:07:41.300
Markov chain, you can make a stochastic Petri
net or GSPN and get the measures in the Petri
00:07:41.300 --> 00:07:49.970
net level instead of the state in the Markov
chain whenever you are able to get the underlying
00:07:49.970 --> 00:07:57.660
reachability graph is isomorphic to the continuous-time
Markov chain.
00:07:57.660 --> 00:08:05.280
Now we are moving into the another extension
of Petri Net.
00:08:05.280 --> 00:08:07.900
We started with the Petri Net.
00:08:07.900 --> 00:08:12.720
Then we discussed stochastic Petri Net.
00:08:12.720 --> 00:08:16.550
Then we have discussed generalized stochastic
Petri Net.
00:08:16.550 --> 00:08:23.580
Now we are going to discuss Stochastic Reward
Nets.
00:08:23.580 --> 00:08:30.330
A marking M(t) in a Stochastic Petri Net is
called vanishing if at least one immediate
00:08:30.330 --> 00:08:36.169
transition is enabled at time t.
00:08:36.169 --> 00:08:43.380
A marking which is not vanishing is called
tangible markings.
00:08:43.380 --> 00:08:48.990
Let M¯(t) be the set of all possible markings
at time t.
00:08:48.990 --> 00:08:55.580
A guard function g(t) associated with the
transition T is a Boolean function defined
00:08:55.580 --> 00:09:07.270
over M¯(t) such that the transition T does
not fire if the gT(t) is equal to 0.
00:09:07.270 --> 00:09:16.080
That means even if it enabled and not inhibited,
and it fires, if it is enabled and not inhibited,
00:09:16.080 --> 00:09:20.410
and g(t) is equal to 1.
00:09:20.410 --> 00:09:27.520
A reward is a non-negative weight associated
with each markings.
00:09:27.520 --> 00:09:32.630
So we are first defining what is the reward
and what is a guard function.
00:09:32.630 --> 00:09:37.250
Along with the reward and the guard function,
we are going to define the Stochastic Reward
00:09:37.250 --> 00:09:39.890
Nets.
00:09:39.890 --> 00:09:46.440
A stochastic reward net is an extension of
generalized stochastic Petri Net that allows
00:09:46.440 --> 00:09:53.710
extensive marking dependency and expresses
complex enabling or disabling conditions for
00:09:53.710 --> 00:10:03.420
transitions through guard functions, or by
assigning one or more reward rates to each
00:10:03.420 --> 00:10:05.110
tangible marking.
00:10:05.110 --> 00:10:08.750
That means you should know what is tangible
marking and you should know what is guard
00:10:08.750 --> 00:10:13.490
function and also you should know what is
reward rates.
00:10:13.490 --> 00:10:21.950
By using these three concepts, the extension
of GSPN will be called stochastic reward nets
00:10:21.950 --> 00:10:27.870
or in other words, it is SRN.
00:10:27.870 --> 00:10:36.680
For a given SPN or SRN, an extended reachability
graph is a directed graph with the marking
00:10:36.680 --> 00:10:45.130
of the reachability set as the nodes and a
directed edge from node M1(t) to M2(t) if
00:10:45.130 --> 00:10:54.640
M2(t+T) can be obtained from M1(t) by firing
a single transition capital T.
00:10:54.640 --> 00:11:06.720
To each edge in an extended reachability graph,
some stochastic information is attached.
00:11:06.720 --> 00:11:13.630
The stochastic information could be the multiplicative
inverse of the mean firing time of the transition
00:11:13.630 --> 00:11:17.279
or could be the probability of firing of the
transition.
00:11:17.279 --> 00:11:25.020
If the expected number of transitions that
fires in a finite time is finite, then it
00:11:25.020 --> 00:11:32.470
can be shown that a given extended reachability
graph can be reduced to a homogeneous continuous-time
00:11:32.470 --> 00:11:35.910
Markov chain.
00:11:35.910 --> 00:11:41.690
Not all the extended reachability graph will
be reduced into the homogeneous Markov chain.
00:11:41.690 --> 00:11:47.980
Whenever the condition of expected number
of transitions that fire in a finite time
00:11:47.980 --> 00:11:55.550
is finite, then only the extended reachability
graph can be reduced to the homogeneous continuous-time
00:11:55.550 --> 00:11:58.020
Markov chain.
00:11:58.020 --> 00:12:03.910
To get the throughput, delay or any other
performance measures of the system, which
00:12:03.910 --> 00:12:10.750
you are considering, appropriate rewards rates
are assigned to the markings of the SRN.
00:12:10.750 --> 00:12:12.690
You know the meaning of marking.
00:12:12.690 --> 00:12:18.510
So when you assign reward rates to the marking,
then you can find out the measures of your
00:12:18.510 --> 00:12:19.510
interest.
00:12:19.510 --> 00:12:28.720
As SRN is automatically transformed into the
Markov reward model and the required measures
00:12:28.720 --> 00:12:36.250
of the SRN can be obtained by either a steady-state
analysis or transient analysis of the underlying
00:12:36.250 --> 00:12:42.779
Markov reward model.
00:12:42.779 --> 00:12:52.720
So by assigning proper reward rates, you can
study the Markov chain with the rewards called
00:12:52.720 --> 00:12:55.520
the Markov model, Markov reward model.
00:12:55.520 --> 00:13:04.940
The same way here the stochastic Petri Net
along with the assigning reward rates, you
00:13:04.940 --> 00:13:09.810
can call it as a stochastic reward nets.
00:13:09.810 --> 00:13:21.840
Let's see the simple example of a stochastic
reward net.
00:13:21.840 --> 00:13:36.770
Consider the Example 6 with the two places
Pon and Poff and the two transitions, one
00:13:36.770 --> 00:13:46.670
is called a Tfailure and the other transition
is called Trepair.
00:13:46.670 --> 00:13:52.940
This transition is an input ard and this is
the output arc.
00:13:52.940 --> 00:14:00.220
Similarly, this is the input arc and this
is the output arc.
00:14:00.220 --> 00:14:07.550
Assume that Tfailure is exponential distribution
with the parameter lambda.
00:14:07.550 --> 00:14:18.300
The Trepair, that is also exponential distributed
with the parameter µ.
00:14:18.300 --> 00:14:26.740
We assume that we have two components.
00:14:26.740 --> 00:14:30.770
We have two components in the system.
00:14:30.770 --> 00:14:35.050
Each component failure is exponential distribution
with the rate lambda.
00:14:35.050 --> 00:14:40.360
Therefore, there is another symbol called
asterisk.
00:14:40.360 --> 00:14:46.800
If the two tokens in the place Pon, then the
rate will be 2?.
00:14:46.800 --> 00:14:54.150
If one token in the place Pon, then the rate
will be ?. For that we have used the asterisk.
00:14:54.150 --> 00:15:04.190
That means the actual rate of this transition
will be ? times number of tokens in the input
00:15:04.190 --> 00:15:08.540
place corresponding to the input arc.
00:15:08.540 --> 00:15:19.660
So here if two tokens in the place Pon, then
the transition Tfailure has a rate 2?.
00:15:19.660 --> 00:15:36.900
Otherwise, it is ?. Therefore, the reachability
graph will be (2, 0), (1, 1), (0, 2) and the
00:15:36.900 --> 00:15:50.210
corresponding transitions are 2?, ?, (0, 2)
to (1, 1) that is µ, (1, 1) to (2, 0) that
00:15:50.210 --> 00:15:52.580
is µ.
00:15:52.580 --> 00:16:00.280
So this is same as the time-homogeneous continuous-time
Markov chain.
00:16:00.280 --> 00:16:04.210
Suppose my interest is to find out the availability.
00:16:04.210 --> 00:16:10.550
Whenever two tokens in the place Pon or one
token in the place Pon, that means the system
00:16:10.550 --> 00:16:11.990
is available.
00:16:11.990 --> 00:16:19.560
So by assigning the reward rate ri is equal
to 1 for the number of tokens in the place
00:16:19.560 --> 00:16:26.339
Pon, if it is greater than or equal to 1,
that is 1 or if it is 0, number of tokens
00:16:26.339 --> 00:16:34.100
in the place Pon, that is equal to 0, that
reward rate is 0, then the availability is
00:16:34.100 --> 00:16:44.790
nothing but summation ri pi(t) where i is
nothing but the marking.
00:16:44.790 --> 00:16:48.670
So i is nothing but this is the marking.
00:16:48.670 --> 00:16:53.730
Suppose you treat this as a marking 2 and
you treat this as a marking 2 and this is
00:16:53.730 --> 00:16:58.850
as a marking 3, therefore, here i is running
from 1 to the.
00:16:58.850 --> 00:17:06.220
So by assigning a proper reward rates ri's,
you can get the availability.
00:17:06.220 --> 00:17:13.350
The further extensions of the stochastic Petri
nets are Markov Regenerative Stochastic Petri
00:17:13.350 --> 00:17:19.169
Net, Fluid Stochastic Petri Nets and Coloured
Petri Nets.
00:17:19.169 --> 00:17:35.679
These are all the references.