WEBVTT
Kind: captions
Language: en
00:00:00.130 --> 00:00:07.540
Now I am moving into M/M/c/K model. So here
the change is instead of one server in the
00:00:07.540 --> 00:00:20.150
M/M/1 model you have more than one servers
c and you have a finite capacity that is K,
00:00:20.150 --> 00:00:26.460
capacity of the system. So the arrival follows
the Poisson process, service is exponential,
00:00:26.460 --> 00:00:34.700
we have c identical servers. The capacity
is K and this is the scenario in which whenever
00:00:34.700 --> 00:00:40.070
the system size is less than c it will be
routed into the ideal server.
00:00:40.070 --> 00:00:45.280
And if it is greater than or equal to c, that
means all the servers are busy that means
00:00:45.280 --> 00:00:53.760
the customer has to wait. But if the system
size is full, that means c customers are under
00:00:53.760 --> 00:01:01.370
service and K minus c customers are waiting
in the queue for the service and then whoever
00:01:01.370 --> 00:01:05.969
comes it will be rejected force to leave the
system.
00:01:05.969 --> 00:01:13.329
And therefore you have a waiting as well as
blocking because it is a finite capacity there
00:01:13.329 --> 00:01:22.380
is blocking and since you have, always we
choose K such that it is K is always greater
00:01:22.380 --> 00:01:28.600
than or equal to c. If K is equal to c, then
it is a loss system and then if K is greater
00:01:28.600 --> 00:01:36.369
than c, then K minus c customers maximum can
wait in the system, in the queue.
00:01:36.369 --> 00:01:42.799
Therefore, the underlying stochastic process,
here the stochastic process is again number
00:01:42.799 --> 00:01:49.930
of customers in the system at any time t.
Therefore, this stochastic process is also
00:01:49.930 --> 00:01:57.399
going to be a continuous time Markov chain
because of these assumptions, inter arrivals
00:01:57.399 --> 00:02:04.280
are exponential distribution service, each
service by each server is exponentially distributed
00:02:04.280 --> 00:02:06.599
and all are independent and so on.
00:02:06.599 --> 00:02:14.770
So with these assumptions these stochastic
processes is a continuous time Markov chain
00:02:14.770 --> 00:02:20.890
and at any time only, only one forward or
only one backward the system can move. Therefore,
00:02:20.890 --> 00:02:25.850
it is going to be a birth death process also
and the birth rates are lambda because it
00:02:25.850 --> 00:02:31.880
is a infinite source population, so all the
lambda n are going to be lambda, whereas the
00:02:31.880 --> 00:02:34.330
death rates are state dependent.
00:02:34.330 --> 00:02:40.550
That is going to be n times mu, lies between
1 to c, from c to k onwards it is going to
00:02:40.550 --> 00:02:50.180
be c mu. I have not drawn the state transition
diagram for M/M/c/K, but you can visualize
00:02:50.180 --> 00:02:57.290
the way we have M/M/1/N and M/M/c model, so
it is a combination of that, that is going
00:02:57.290 --> 00:03:05.900
to be the state transition diagram. Since
it is a finite capacity model, it is easy
00:03:05.900 --> 00:03:09.260
to get the steady state and the equilibrium
solution.
00:03:09.260 --> 00:03:16.170
So first you solve pi Q is equal to zero that
means you write pi n in terms of pi 0 and
00:03:16.170 --> 00:03:20.630
use a normalizing constant summation of pi
i is equal to one, using that you will get
00:03:20.630 --> 00:03:28.320
pi 0. So I have not written here. So use the
normalizing constant summation of pi i is
00:03:28.320 --> 00:03:33.270
equal to one, get the pi 0, then substitute
pi 0 here therefore you will get pi n in terms
00:03:33.270 --> 00:03:36.870
of pi 0 completely.
00:03:36.870 --> 00:03:45.400
After that you can get all other average measures,
the way I have explained M/M/1/N and the M/M/c
00:03:45.400 --> 00:03:50.040
infinity, the combination of that you can
get the average number of customers in the
00:03:50.040 --> 00:03:59.100
system, average number of customers in the
queue. That is n minus c times pi n, combination,
00:03:59.100 --> 00:04:05.040
the summation goes from c to K and the average
time spend in this system.
00:04:05.040 --> 00:04:09.700
Since it is a finite capacity you have to
find out the lambda effective, effective arrival
00:04:09.700 --> 00:04:16.680
rate, that his one minus, its capacity is
capital K, therefore one minus pi K and that
00:04:16.680 --> 00:04:21.320
is the probably that the system is not full.
So the effective arrival rate is lambda times
00:04:21.320 --> 00:04:28.510
one minus pi K, substitute here and get the
average time spent in the system and similarly
00:04:28.510 --> 00:04:37.660
you can find out the average time spent in
the queue also using the little’s formula.
00:04:37.660 --> 00:04:48.040
Now I am moving into the fourth simple Markovian
queuing model. First I started with the M/M/c
00:04:48.040 --> 00:04:54.750
infinity, M/M/1/N, then I did M/M/c/K and
now I am going for K is equal to c that is
00:04:54.750 --> 00:05:02.350
loss system. It is not a queuing system because
we have c servers and the capacity of the
00:05:02.350 --> 00:05:04.970
system is also c.
00:05:04.970 --> 00:05:11.810
Example is you can think of parking lot which
has some c parking lots and the cars coming
00:05:11.810 --> 00:05:17.970
into the system that is if you make the assumption
is inter arrival time is exponentially distributed
00:05:17.970 --> 00:05:24.460
and the car spending time in each parking
lot that is exponentially distributed then
00:05:24.460 --> 00:05:35.220
the parking lot problem can be visualized
as the M/M/c loses too. So here we have c
00:05:35.220 --> 00:05:40.790
identical servers, no waiting room.
00:05:40.790 --> 00:05:47.560
So since it is c capacity and c waiting room
you think of self service with the capacity
00:05:47.560 --> 00:05:54.020
c, that also you can visualize. So here the
inter arrival times are exponentially distributed
00:05:54.020 --> 00:05:59.710
and service by each server, that is exponentially
distributed with the parameter mu therefore
00:05:59.710 --> 00:06:06.900
the system goes from two to one, one to zero,
so on, it is going to be how many customers
00:06:06.900 --> 00:06:08.889
in the system and completing their service.
00:06:08.889 --> 00:06:18.460
Therefore, the time is exponentially distributed
with the sum of those parameters accordingly.
00:06:18.460 --> 00:06:27.840
Therefore, it is going to be 1mu, 2 mu till
c mu. Since it is a finite capacity and so
00:06:27.840 --> 00:06:34.449
on, it is a reducible model, positive recurrent.
So this listed probability exists, limiting
00:06:34.449 --> 00:06:39.760
probability also exists and that is same as
the equilibrium probabilities also. Therefore,
00:06:39.760 --> 00:06:47.960
by using pQ is equal to zero and summation
of p i is equal to one you can get the steady
00:06:47.960 --> 00:06:53.220
state or the equilibrium probabilities, that
is p n.
00:06:53.220 --> 00:07:00.350
The p suffix c, that is nothing but the probability
that the system is full and that is same known
00:07:00.350 --> 00:07:08.400
as the Erlang B formula. So this is also useful
to design the system for a given or what is
00:07:08.400 --> 00:07:17.860
the optimal c such that you can minimize the
probability that the system is full, for that
00:07:17.860 --> 00:07:25.540
you need this formula therefore to do the
optimization problem over the c and here we
00:07:25.540 --> 00:07:33.669
denote p suffix c, that is Erlang B formula.
Whereas Erlang C formula comes from the M/M/c/K
00:07:33.669 --> 00:07:39.370
model for the last system we will get the
Erlang B formula.
00:07:39.370 --> 00:07:47.910
The fifth model, that is M/M/∞, it is not
a queuing model, because servers are infinite
00:07:47.910 --> 00:07:55.830
and limited servers in the system and therefore
the customers whoever enters he will get it
00:07:55.830 --> 00:08:01.169
immediately serviced. The service will be
started immediately whereas the service time
00:08:01.169 --> 00:08:09.800
is exponentially distributed with the parameter
mu by each server, all the servers are identical.
00:08:09.800 --> 00:08:16.730
The number of servers are infinite here. Therefore,
you will have the underlying stochastic process
00:08:16.730 --> 00:08:22.830
for the system size that is a birth death
process with the birth rates are lambda because
00:08:22.830 --> 00:08:29.400
the population is from the infinite source,
the death rates are 1 mu, 2 mu and so on because
00:08:29.400 --> 00:08:38.750
the number of servers are infinite. So the
model which I have discussed in today’s
00:08:38.750 --> 00:08:44.550
lecture, all the five models are the underlying
stochastic processes, birth death process.
00:08:44.550 --> 00:08:49.600
This is simplest Markovian queuing models.
00:08:49.600 --> 00:08:58.990
You can get the steady state distribution,
use the same theory of birth death process
00:08:58.990 --> 00:09:05.310
and if you observe these steady state probabilities
is of the same Poisson, it is of the form
00:09:05.310 --> 00:09:10.850
that is probability mass function of a Poisson
distribution. Therefore, you can conclude
00:09:10.850 --> 00:09:15.560
in a steady state, number of customers in
the system that is Poisson distributed with
00:09:15.560 --> 00:09:20.500
the parameter lambda by mu.
00:09:20.500 --> 00:09:25.730
Because the probability mass function for
the pi n is same as the probability mass function
00:09:25.730 --> 00:09:30.890
of exponentially distributed random variable
with the parameter lambda by mu.