WEBVTT
Kind: captions
Language: en
00:00:00.340 --> 00:00:08.149
Now I am moving into the last part of model
5 Continuous-time Markov Chain. In this I
00:00:08.149 --> 00:00:15.480
am going to discuss the simulation of queueing
systems. So the model 5 Continuous-time Markov
00:00:15.480 --> 00:00:20.220
Chain started with a definition and properties
and so on then I discussed the birth death
00:00:20.220 --> 00:00:26.380
process, then I discussed the application
of a birth death process in simple Markovian
00:00:26.380 --> 00:00:28.810
queueing models.
00:00:28.810 --> 00:00:37.800
Then I also have discussed the queueing networks
that is also multidimensional Continuous-time
00:00:37.800 --> 00:00:46.649
Markov Chain as application and finally I
have given few practical applications in cellular
00:00:46.649 --> 00:00:55.480
networks for the performance analysis. Now
I am going to discuss the discrete event simulation
00:00:55.480 --> 00:01:05.830
of a simple Markovian queueing systems.
00:01:05.830 --> 00:01:13.469
So in this queueing network modelling lab,
one can do discrete event stimulation.
00:01:13.469 --> 00:01:19.299
And the discrete event simulation for the
queueing network involves Markovian queues,
00:01:19.299 --> 00:01:25.409
we can do some experiment over the Markovian
queues and you can do the discrete event simulation
00:01:25.409 --> 00:01:27.590
for the non-Markovian queues.
00:01:27.590 --> 00:01:33.569
And one can do the discrete event simulation
for the queueing network also and finally
00:01:33.569 --> 00:01:39.630
one can do the fluid queues also. One can
simulate but since I have discussed only Continuous-time
00:01:39.630 --> 00:01:47.069
Markov Chain till now I am going to do discrete
event simulation for the Markovian queues.
00:01:47.069 --> 00:01:52.849
So that is the first three experiments. The
other three experiments are related to the
00:01:52.849 --> 00:01:59.909
non-Markovian queues.
00:01:59.909 --> 00:02:05.419
The first experiment consists of a simulation
of a M/M/1 queue, single server queue and
00:02:05.419 --> 00:02:12.790
M/M/c finite server queues and the infinite
server queue. So in the last sometime I have
00:02:12.790 --> 00:02:24.000
done the discrete event simulation of a M/M/1
queue. So let me go to M/M/c finite server
00:02:24.000 --> 00:02:25.870
queue.
00:02:25.870 --> 00:02:33.299
So in this you need the input of arrival rate,
input of the departure rate and the number
00:02:33.299 --> 00:02:39.969
of servers, is the multi server infinite capacity
model. So suppose you choose the arrival rate
00:02:39.969 --> 00:02:48.260
is 2 and the service rate is 3 and the number
of servers are 2 that means it is a M/M/2
00:02:48.260 --> 00:02:54.629
infinity model with arrival rate 2 and the
service rate is 3.
00:02:54.629 --> 00:03:03.549
So one can start the discrete event simulation
by clicking the start. Then you will get the
00:03:03.549 --> 00:03:12.439
window of, so this is the sample path over
the time what is the system size. So at this
00:03:12.439 --> 00:03:18.620
time point one arrival comes, then two, then
service is completed and so on. So this is
00:03:18.620 --> 00:03:22.319
a sample path over the time.
00:03:22.319 --> 00:03:26.389
And here you can get the performance measure.
So whatever I have discussed the performance
00:03:26.389 --> 00:03:32.560
measures of a steady state distribution and
all other performance measure, one can get
00:03:32.560 --> 00:03:39.900
it with the theoretical results in the third
column whereas the second column gives the
00:03:39.900 --> 00:03:49.310
running time till the discrete event simulation
runs for 15-time unit and what is the result
00:03:49.310 --> 00:03:56.189
for the mean number of system and so on and
this will converge to this value for t tends
00:03:56.189 --> 00:03:57.189
to infinity.
00:03:57.189 --> 00:04:03.060
So I make sure that this arrival and departure
rates are satisfying the condition so that
00:04:03.060 --> 00:04:07.680
the steady state distribution exist, therefore
as t tends to infinity this will reaches the
00:04:07.680 --> 00:04:13.629
steady state theoretical result. If you change
the value, arrival rate and the departure
00:04:13.629 --> 00:04:20.140
rate something else then there is a possibility
if the conditions for the stationary distribution
00:04:20.140 --> 00:04:26.720
are not satisfied then still the runtime results
you will get, but that will not converge to
00:04:26.720 --> 00:04:31.240
the theoretical and also this steady state
so only possible.
00:04:31.240 --> 00:04:39.230
It will be dash here, so as long as the steady
state distribution those conditions are satisfied,
00:04:39.230 --> 00:04:44.030
then you will have the results in the third
column, otherwise you will not have the results
00:04:44.030 --> 00:04:50.819
here. So now you can see the throughput till
this much time, you are getting 2.0 whereas
00:04:50.819 --> 00:04:58.389
the steady state throughput is 2. Throughput
is nothing but the number of customers served
00:04:58.389 --> 00:05:01.530
per unit time.
00:05:01.530 --> 00:05:10.840
Let that one can get the throughput utilization,
average response time or mean sojourn time
00:05:10.840 --> 00:05:16.160
and mean waiting time in the queue so using
Little's formula used to find out this quantity,
00:05:16.160 --> 00:05:21.819
so this quantity you can get it from the discrete
event simulation at any time as well as the
00:05:21.819 --> 00:05:27.840
theoretical result and this is the mean number
of customers in the system that is E[N] and
00:05:27.840 --> 00:05:32.100
the mean number of customers in the queue
that is E[Q] which we got it.
00:05:32.100 --> 00:05:38.160
So this result, one can see the discrete event
simulation as well as a t tends to infinity,
00:05:38.160 --> 00:05:43.490
what is the theoretical result if the conditions
for the stationary for the stationary distribution
00:05:43.490 --> 00:05:44.889
satisfied.
00:05:44.889 --> 00:05:49.039
And here this information is how many calls
are entered, how many customers enter into
00:05:49.039 --> 00:05:54.979
the system and how many all served and how
many customers are blocked. Here there is
00:05:54.979 --> 00:06:00.789
no blocking because it is an infinite capacitive
system. And we are considering the retrial
00:06:00.789 --> 00:06:07.210
orbit and so on therefore here it says number
of orbit customers is zero. This is not necessary.
00:06:07.210 --> 00:06:18.009
This is irrelevant information in the M/M/c
queueing model. Now let me go back and do
00:06:18.009 --> 00:06:21.969
the live simulation o f M / M / ".
( R e f e r S l i d e T i m e : 0 6 : 2 5
00:06:21.969 --> 00:06:22.969
)
00:06:22.969 --> 00:06:25.860
S o h e r e w e h a v e t o p r o v i d e
o n l y t h e a r r i v a l r a t e a n d
00:06:25.860 --> 00:06:29.710
t h e s e r v i c e r a t e b e c a u s e
t h e n u m b e r o f s e r v e r s a r e
00:06:29.710 --> 00:06:32.469
i n f i n i t e , t h i s h e l p s s e r
v i c e s y s t e m .
00:06:32.469 --> 00:06:34.130
( R e f e r S l i d e T i m e : 0 6 : 3 0
)
00:06:34.130 --> 00:06:37.979
Y o u c a n c r o s s c h e c k t h e t h
e o r e t i c a l r e s u l t s a r e c orrect
00:06:37.979 --> 00:06:45.080
and so on. So here I am getting this steady
state result based on the theory whereas this
00:06:45.080 --> 00:06:57.760
is a run time results. There is no blocking
probability because this system infinite capacity.
00:06:57.760 --> 00:07:02.879
Mean number of customers in the queue that
is zero and here also zero because it is an
00:07:02.879 --> 00:07:09.380
infinite server therefore, customers who enter
into the system immediately will get the service.
00:07:09.380 --> 00:07:15.159
Therefore, the queue average number of customers
in the queue that is zero and the average
00:07:15.159 --> 00:07:22.250
time spending in the queue that is also zero,
it is correct. There is no blocking and utilization
00:07:22.250 --> 00:07:34.060
is, what is the probability that the servers
are utilised. Now let me go the next experiment
00:07:34.060 --> 00:07:40.199
that is the second experiment for the finite
capacity queueing model whereas the first
00:07:40.199 --> 00:07:42.349
experiment is the infinite capacity queueing
model.
00:07:42.349 --> 00:07:54.080
So in this we have, we need to give the arrival
rate, service and the number of servers we
00:07:54.080 --> 00:08:05.719
can go for the multi-server M/M/c/N model,
you can give one also. You can give infinite
00:08:05.719 --> 00:08:13.830
servers also can give. So here the number
of servers you fix it 3 and the capacity is
00:08:13.830 --> 00:08:25.099
4. You can do the simulation.
00:08:25.099 --> 00:08:31.520
So the blocking probability the run time there
is, at this time it does not cross the number
00:08:31.520 --> 00:08:36.810
4, therefore the blocking probability is zero
is zero and the run time result whereas the
00:08:36.810 --> 00:08:44.510
theoretical steady state results is the blocking
probability 0.005. So whenever the system
00:08:44.510 --> 00:08:48.860
touches 5 then you will have the blocking
probability in the run time, so this is a
00:08:48.860 --> 00:08:50.500
discrete event simulation.
00:08:50.500 --> 00:08:56.150
So the number of customers blocked is till
now is zero therefore you are getting the
00:08:56.150 --> 00:09:01.110
blocking probability zero at this run time.
Suppose you run it again let us see.
00:09:01.110 --> 00:09:20.790
Now I will show you it
does not crosses the system size by two, so
00:09:20.790 --> 00:09:29.530
maybe I can reset with the number of servers
I can put 2 and capacity is 3.
00:09:29.530 --> 00:09:50.650
So the blocking probability is this much,
the capacity of the system. So there is no
00:09:50.650 --> 00:09:56.720
arrival after crossing the first still you
are getting the blocking probability zero
00:09:56.720 --> 00:10:07.140
whereas the steady state theoretical results
is 0.037. So one can simulate with the different
00:10:07.140 --> 00:10:19.780
parameters and you can see the sample path.
So this is a sample path for M/M/2/3 queueing
00:10:19.780 --> 00:10:26.400
system with the arrival rate 2 and the service
rate is 3. Now we are getting the blocking
00:10:26.400 --> 00:10:36.460
probability because the system crosses, it
touches capacity 3 therefore some calls are
00:10:36.460 --> 00:10:41.710
blocked, some customers are blocked therefore
the blocking so you can find out from here.
00:10:41.710 --> 00:10:48.290
Number of customers 44 entered and 4 are blocked
therefore that ratio will be the blocking
00:10:48.290 --> 00:10:58.330
probability because it is a discrete event
simulation. Now let me go back and go to the
00:10:58.330 --> 00:11:01.490
experiment 3.
00:11:01.490 --> 00:11:08.790
Experiment 3, we have a retrial model with
the bulk arrival and bulk service. So now
00:11:08.790 --> 00:11:13.710
it is no more birth death process simulation.
This is a non-birth death process because
00:11:13.710 --> 00:11:19.770
you have bulk arrival and the bulk service
as possible and the retrial therefore, let
00:11:19.770 --> 00:11:22.990
me show the simulation.
00:11:22.990 --> 00:11:31.011
You need some more information. So what is
a arrival rate we have to supply. Suppose
00:11:31.011 --> 00:11:35.990
if it is a bulk arrival and then you should
say what is the distribution, whether the
00:11:35.990 --> 00:11:44.791
bulk arrival comes in a bulk or some constant
number or it comes in some distribution. You
00:11:44.791 --> 00:11:55.250
can choose its geometrically distributed.
And the parameter for the bulk arrival parameter
00:11:55.250 --> 00:11:58.710
you can choose some 0.5.
00:11:58.710 --> 00:12:06.670
Then the departure rate, you can choose a
departure rate, it can be a bulk departure
00:12:06.670 --> 00:12:14.810
or bulk so either you can choose bulk arrival
or bulk departure or you can choose both also.
00:12:14.810 --> 00:12:18.880
The number of servers in the system, suppose
there are two servers in the system and the
00:12:18.880 --> 00:12:30.571
capacity of system is 4 or you can choose
the infinite capacity of the system also.
00:12:30.571 --> 00:12:36.480
And if you need orbit then you have to click
for orbit and if you are changing the queueing
00:12:36.480 --> 00:12:41.980
discipline, the first come first served, last
come first served are random order, you can
00:12:41.980 --> 00:12:46.500
choose the queueing discipline also accordingly
the discrete event simulation goes. So this
00:12:46.500 --> 00:12:58.620
is not a birth death process, this is a Continuous-time
Markov Chain simulation with a different queueing
00:12:58.620 --> 00:13:02.630
discipline also one can go for it.
00:13:02.630 --> 00:13:12.180
Now once you start the simulation, since it
is a bulk, we have made a bulk arrival whereas
00:13:12.180 --> 00:13:18.160
we made, we did not click for the bulk departure,
therefore the customers keep going by one
00:13:18.160 --> 00:13:24.540
by one whenever the service is over but since
it is a bulk arrival with the arrival distribution
00:13:24.540 --> 00:13:34.570
is a the number of arrivals that is a geometrically
distributed. Therefore, it just jumped with
00:13:34.570 --> 00:13:39.300
the bulk arrival whereas the departure is
by one by one.
00:13:39.300 --> 00:13:44.520
And here is the performance measures is the
run time performance measures and till now
00:13:44.520 --> 00:13:51.800
we did not supply the theoretic steady state
or the theoretical results for this model.
00:13:51.800 --> 00:13:57.130
And these are all the different results with
over the run time. And similarly one can go
00:13:57.130 --> 00:14:13.330
with the bulk departure and you can change
the queueing discipline also. So this is a
00:14:13.330 --> 00:14:18.670
discrete event simulation sample path for
this scenario.
00:14:18.670 --> 00:14:30.260
So I can reset and if I do not want the bulk
arrival, and if I choose the capacity of the
00:14:30.260 --> 00:14:39.190
system is 4, so this will be a no bulk arrival,
no bulk departure, therefore this is a M/M/2/4
00:14:39.190 --> 00:14:43.680
system at the first come first served. And
I can go for instead of first come first out
00:14:43.680 --> 00:14:51.720
I can for the last come first out also.
00:14:51.720 --> 00:14:58.120
The customers are last entered, he is getting
the service first. So this is a steady state
00:14:58.120 --> 00:15:07.580
and this is a time dependent result. And I
can change again this until that means it
00:15:07.580 --> 00:15:18.210
is a two servers infinite capacity model with
the first come first served.
00:15:18.210 --> 00:15:22.920
Still this is the testing phase, so some of
the things should be removed, some of the
00:15:22.920 --> 00:15:29.190
things has to be edited. So is still it is
in the testing phase. So this is the performance
00:15:29.190 --> 00:15:38.660
measures for the M/M/2 infinity model. So
that means in this experiment also you can
00:15:38.660 --> 00:15:45.690
remove the bulk arrival and the bulk departure
part and so on you can try the simplest, simple
00:15:45.690 --> 00:15:50.760
Markovian queueing model. Also one can do
the discrete event simulation of that.
00:15:50.760 --> 00:15:57.820
And since it is a infinite capacity model,
the blocking probability is zero. And the
00:15:57.820 --> 00:16:05.080
steady state throughput is 2, one can find
out from the formula also whereas the run
00:16:05.080 --> 00:16:13.520
time is this. So if this discrete event simulation
runs for a longer time then this will converge,
00:16:13.520 --> 00:16:17.950
like that you can discuss all other results
also. All the results will become converges
00:16:17.950 --> 00:16:30.000
to the steady state theoretical probability
with the theoretical results.
00:16:30.000 --> 00:16:38.620
So with this let me complete the discrete
event simulation of a simple Markovian queueing
00:16:38.620 --> 00:16:44.490
model because we have discussed in this under
the title of a application of Continuous-time
00:16:44.490 --> 00:16:51.420
Markov Chain. Therefore, I discuss only the
Markovian queues. There are some non-Markovian
00:16:51.420 --> 00:16:53.320
queues and so on.
00:16:53.320 --> 00:16:58.520
So I am not discussing the non-Markovian queues
at this stage. After I discussed the renewal
00:16:58.520 --> 00:17:05.100
theorem and Markov regenerative process and
a semi Markov process and so on, I will be
00:17:05.100 --> 00:17:11.159
discussing the non-Markovian queueing systems
also. So here we have discussed only a simple
00:17:11.159 --> 00:17:16.879
Markovian queueing system that is nothing
but the applications of a Continuous-time
00:17:16.879 --> 00:17:18.970
Markov Chain.
00:17:18.970 --> 00:17:30.039
As a summary, the last seven lectures we have
discussed the Continuous-time Markov Chain
00:17:30.039 --> 00:17:37.110
from the definition and properties and a few
simple Continuous-time Markov Chain starting
00:17:37.110 --> 00:17:43.470
with the Poisson process, birth death process,
pure birth process, pure death process, then
00:17:43.470 --> 00:17:48.370
application of CTMC in the queueing models
starting with the M/M/1 queue and other simple
00:17:48.370 --> 00:17:50.210
Markovian queues.
00:17:50.210 --> 00:17:56.140
Then we discussed a few queueing networks
which has the product solution. Then in the
00:17:56.140 --> 00:18:05.210
last this lecture we have discussed the applications
of CTMC in second generation cellular networks
00:18:05.210 --> 00:18:11.350
as well as the third generations cellular
networks and application of CTMC in the 2G
00:18:11.350 --> 00:18:16.830
network is the birth death process whereas
the applications of CTMC in 3G cellular networks
00:18:16.830 --> 00:18:19.010
is the quasi birth death process.
00:18:19.010 --> 00:18:24.800
Even though I have not discussed in detailed
the complete modelling, one can see it from
00:18:24.800 --> 00:18:32.360
the paper. My intention here is to explain
the quasi birth death process through the
00:18:32.360 --> 00:18:38.830
applications and we discussed the stationary
distribution and all other performance measures
00:18:38.830 --> 00:18:44.620
for the birth death process comes in the second
generation networks and the quasi birth death
00:18:44.620 --> 00:18:48.080
in the third generation networks.
00:18:48.080 --> 00:18:53.179
And finally I have given the discrete event
simulation for simple Markovian queueing systems
00:18:53.179 --> 00:19:16.220
only whereas some more non-Markovian queueing
systems so that I will discuss with the other
00:19:16.220 --> 00:19:23.679
models.