WEBVTT
Kind: captions
Language: en
00:00:00.450 --> 00:00:05.351
The tandem queueing networks is a special
case of open queueing network in which all
00:00:05.351 --> 00:00:11.010
the nodes or queues are interconnected in
series.
00:00:11.010 --> 00:00:22.780
Let me start with a very simplest tandem queueing
networks with two nodes or two queueing system
00:00:22.780 --> 00:00:24.650
connected in series.
00:00:24.650 --> 00:00:32.540
We are going to relate the queueing network
with a stochastic process and so on.
00:00:32.540 --> 00:00:40.630
Therefore, let me start with random variable
X(t) and Y(t), X(t) denotes number of jobs
00:00:40.630 --> 00:00:45.010
or customers in the node 1 at any time t.
00:00:45.010 --> 00:00:47.680
Node 1 or first queue both are the same.
00:00:47.680 --> 00:00:55.190
Y(t) another random variable that denotes
the number of jobs in the second queue at
00:00:55.190 --> 00:00:57.640
time t.
00:00:57.640 --> 00:01:07.950
Therefore, together X(t) and Y(t), you can
think of a vector as T is equal to X(t) and
00:01:07.950 --> 00:01:13.999
Y(t), that vector is a random vector at any
time t.
00:01:13.999 --> 00:01:17.729
And if you collect over the t, then that is
going to be a stochastic process.
00:01:17.729 --> 00:01:23.979
So this stochastic process instead of one
random variable, it has two random variables
00:01:23.979 --> 00:01:28.310
X(t) and Y(t), that with the vector.
00:01:28.310 --> 00:01:35.029
So that is a stochastic process, X(t), Y(t)
for t greater than or equal to zero, that
00:01:35.029 --> 00:01:37.049
is stochastic process.
00:01:37.049 --> 00:01:42.310
Since X(t) or Y(t) are the number of jobs
in the first queue and the second queue and
00:01:42.310 --> 00:01:44.210
you are observing over the time.
00:01:44.210 --> 00:01:48.369
How many customers in the first node and how
many customers in the second node at any time
00:01:48.369 --> 00:01:55.560
t, therefore this is a discrete state continuous
time stochastic process.
00:01:55.560 --> 00:02:07.649
Also, you assume that infinite capacity in
both the nodes, both the queues.
00:02:07.649 --> 00:02:14.330
That means after the service is over in the
first node, it will immediately arrive into
00:02:14.330 --> 00:02:20.489
the second node and if no customer in the
system at that time, then he will get the
00:02:20.489 --> 00:02:24.580
service immediately, service will be started
immediately.
00:02:24.580 --> 00:02:32.110
Otherwise the customer who comes after completing
the service in the first node, he has to wait
00:02:32.110 --> 00:02:34.580
till his service starts.
00:02:34.580 --> 00:02:43.890
So I am making one by one assumption, so that
the underlying stochastic process is going
00:02:43.890 --> 00:02:46.849
to be a continuous time Markov chain.
00:02:46.849 --> 00:02:50.170
That is my objective.
00:02:50.170 --> 00:03:02.129
So for that, now I am making the first assumption,
the inter-arrival time of a customer entering
00:03:02.129 --> 00:03:07.900
into the first node, that is exponentially
distributed with a parameter lambda or the
00:03:07.900 --> 00:03:14.689
arrival process into the first queue is a
Poisson process with a parameter lambda.
00:03:14.689 --> 00:03:21.430
So the population is infinite, the customers,
or jobs or packets for example, packets for
00:03:21.430 --> 00:03:27.530
the telecommunication system or any communication
system, so the customers are entering into
00:03:27.530 --> 00:03:36.420
the node 1, their process is Poisson process
with a parameter lambda.
00:03:36.420 --> 00:03:38.400
Now I am making the assumption for service.
00:03:38.400 --> 00:03:45.129
I make the assumption for the service time
that is also exponentially distributed with
00:03:45.129 --> 00:03:57.560
the parameter, mu 1 for the first node and
mu 2 for the second node, other than the inter-arrivals
00:03:57.560 --> 00:04:02.150
are exponential distribution, I made the other
assumptions that is the service time for the
00:04:02.150 --> 00:04:07.609
first node and service time for the second
node, both are exponentially distributed with
00:04:07.609 --> 00:04:12.180
the parameters, mu 1 and mu 2 respectively.
00:04:12.180 --> 00:04:20.860
So, ultimately I want this has to behave as
a M/M/1 queue and this also has to be as M/M/1
00:04:20.860 --> 00:04:22.410
queue independently.
00:04:22.410 --> 00:04:28.630
Therefore, I make all the assumptions the
inter-arrival times are independent with the
00:04:28.630 --> 00:04:34.100
service for the first node, similarly this
one is the arrival for the second node is
00:04:34.100 --> 00:04:38.000
independent of the service of the second node
and so on.
00:04:38.000 --> 00:04:44.840
So with that assumption, each queue in this
queueing network is going to behave as a M/M/1
00:04:44.840 --> 00:04:54.660
queue and the departure of the first node
that will be input for the second node.
00:04:54.660 --> 00:05:00.190
And here you can use the Burke’s theorem,
this is the M/M/1 queue model, therefore using
00:05:00.190 --> 00:05:04.910
the Burke’s theorem, you can conclude the
departure process is also Poisson process
00:05:04.910 --> 00:05:15.580
because the arrival process of Poisson, the
service rate is mu 1 using the Burke’s theorem,
00:05:15.580 --> 00:05:23.370
you can conclude the departure process is
also Poisson process with the same parameter
00:05:23.370 --> 00:05:25.340
of the arrival process.
00:05:25.340 --> 00:05:35.850
Therefore, here the arrival process for the
node 2 is also Poisson process with the same
00:05:35.850 --> 00:05:37.070
parameter lambda.
00:05:37.070 --> 00:05:41.580
It is independent of the service.
00:05:41.580 --> 00:05:49.300
Not only that, the departure process is independent
of the number of customers in this system
00:05:49.300 --> 00:05:55.310
and so on and the inter-arrival, therefore,
you will have two independent M/M/1 queue
00:05:55.310 --> 00:05:59.030
using the Burke’s theorem.
00:05:59.030 --> 00:06:05.520
Now this will separately act as M/M/1 queue
because the arrival process is Poisson with
00:06:05.520 --> 00:06:10.360
the parameter lambda and already we made the
assumptions arrivals are independent with
00:06:10.360 --> 00:06:11.500
the service.
00:06:11.500 --> 00:06:14.740
Service is exponentially distributed with
the parameter mu 2.
00:06:14.740 --> 00:06:17.930
After the service is over, the customers leave
the system.
00:06:17.930 --> 00:06:22.930
Therefore, this is a separate M/M/1 queue
because we made an infinite capacity in both
00:06:22.930 --> 00:06:24.020
the queues.
00:06:24.020 --> 00:06:39.740
Therefore, the two queues tandem queue the
underlying stochastic process, X(t), Y(t)
00:06:39.740 --> 00:06:49.390
going to be the continuous time Markov chain.
00:06:49.390 --> 00:06:58.010
So now I am going to formulate the CTMC from
that two queues tandem queueing network.
00:06:58.010 --> 00:07:03.040
The transition is due to arrival or departure
of jobs in each que.
00:07:03.040 --> 00:07:09.500
Based on this, I can make straight up the
system X(t), Y(t) and that is going to be
00:07:09.500 --> 00:07:13.230
a continuous time Markov chain.
00:07:13.230 --> 00:07:20.530
This is not going to be a birth-death process
because you have two random variable X(t)
00:07:20.530 --> 00:07:26.690
and Y(t) and each one independently M/M/1
queue.
00:07:26.690 --> 00:07:33.620
The M/M/1 queue is the underlying stochastic
process for the M/M/1 queue that is a birth-death
00:07:33.620 --> 00:07:37.590
process, whereas here you have together X(t),
Y(t).
00:07:37.590 --> 00:07:40.150
Therefore, this is not going to be a birth-death
process.
00:07:40.150 --> 00:07:48.740
It will be a general continuous time Markov
chain.
00:07:48.740 --> 00:07:53.340
So once you identify this as a continuous
time Markov chain because the Markov property
00:07:53.340 --> 00:08:03.350
is satisfied by the stochastic process X(t),
Y(t), I can go for drawing the state transition
00:08:03.350 --> 00:08:05.500
diagram.
00:08:05.500 --> 00:08:14.380
It is Markov in nature because the two queues
act independently and are themselves M/M/1
00:08:14.380 --> 00:08:18.750
queueing system which satisfies the Markov
property.
00:08:18.750 --> 00:08:24.470
The first index is for the number of customers
in the first node and second index is for
00:08:24.470 --> 00:08:31.070
the number of customers in the second node,
so 0,0 means in both the queues, no one in
00:08:31.070 --> 00:08:32.640
the system.
00:08:32.640 --> 00:08:40.590
If one arrival comes into the first node,
arrival cannot come into the second node.
00:08:40.590 --> 00:08:45.010
Only the arrival come to the first node, the
inter-arrival is exponential distribution.
00:08:45.010 --> 00:08:52.190
Therefore, the rate of moving from 0, 0 to
1, 0 that is lambda.
00:08:52.190 --> 00:08:58.240
Similarly, there is a possibility of one more
customer entering into the system when one
00:08:58.240 --> 00:09:01.960
customer in the first queue.
00:09:01.960 --> 00:09:07.020
So it will be a parameter lambda, therefore
the rate will be lambda for the arc moving
00:09:07.020 --> 00:09:13.630
from 0, 0 to 1, 0; 1, 0 to 2, 0 and so on.
00:09:13.630 --> 00:09:23.730
Whereas after one customer already in the
first node, the server in the first node would
00:09:23.730 --> 00:09:29.160
have completed the service before one more
arrival into the first node.
00:09:29.160 --> 00:09:34.990
Therefore, the service is exponential distribution
with a parameter mu 1, therefore the system
00:09:34.990 --> 00:09:41.000
goes from 1, 0 to 0, 1 that means, the customer
was under the service.
00:09:41.000 --> 00:09:45.380
That service is over, therefore, he moved
into the second queue.
00:09:45.380 --> 00:09:51.550
Now the first node has zero customer and the
second node has one customer in the system
00:09:51.550 --> 00:09:56.810
and his service will start once he enter into
the second node.
00:09:56.810 --> 00:09:59.690
This rare will be mu 1.
00:09:59.690 --> 00:10:10.481
Now the situations are either one more arrival,
one arrival to the first node or the customer
00:10:10.481 --> 00:10:15.120
who is in the second node, he would have completed
his service.
00:10:15.120 --> 00:10:19.380
So that service is over, therefore that rate
is mu 2.
00:10:19.380 --> 00:10:29.170
Then the system goes to 0, 0 or it will go
to 1, 1 with the rate lambda.
00:10:29.170 --> 00:10:33.930
So the same way, one can discuss for 1, 1
also that means one customer in the first
00:10:33.930 --> 00:10:42.020
node, one customer in the second node, so
the one possibility is the first customer’s
00:10:42.020 --> 00:10:43.390
service is over.
00:10:43.390 --> 00:10:48.610
Therefore, it will be a 0, 2 with the rate
mu 1.
00:10:48.610 --> 00:10:57.370
Or one more arrival takes place, therefore,
it will be a 2, 1 with the rate lambda or
00:10:57.370 --> 00:10:59.760
the second service would have been finished.
00:10:59.760 --> 00:11:01.800
So that rate is mu 2.
00:11:01.800 --> 00:11:08.529
Therefore, it is 1, 1 to 1, 0.
00:11:08.529 --> 00:11:15.960
So these are all the possibilities, the system
can move from 1, 1 to other states 0, 2; 1,
00:11:15.960 --> 00:11:21.630
2 or 1, 0 and so on.
00:11:21.630 --> 00:11:30.680
This is the way you can visualize the different
transition arcs under the corresponding rates.
00:11:30.680 --> 00:11:38.950
So this is the state transition diagram for
two queues, tandem queueing network.
00:11:38.950 --> 00:11:43.730
Obviously from this diagram itself we can
say that this is not a birth-death process.
00:11:43.730 --> 00:11:48.870
If it is a birth-death process, then the system
has to move forward one step or backward one
00:11:48.870 --> 00:11:51.770
step, no other moves.
00:11:51.770 --> 00:11:57.160
So here you have a two-dimensional Markov
chain, therefore this is not a birth-death
00:11:57.160 --> 00:11:58.160
process.
00:11:58.160 --> 00:12:01.190
It is a continuous time Markov chain.