Lecture 08

IIT Kanpur July 201
20 followers
Oct 22, 2023
So, we were talking about call congestion and time congestion. So, in this whole process,
I told you in the last lecture, how we do analysis of Q through a Markov chain. In that,
how we compute average queuing time or average delay. After that, we took an M by N composite
switch. We will continue the same composite switch today. In that, we had M input and
N output. So, in this, the M incoming lines had a telephone call. When a line gets busy,
there could not be a call again. So, here we learned a new thing that my call arrival
rate is lambda above an empty line. Basically, when the call is over, when will the next
call come? The average value of the time gap in between that will be 1 by lambda. So, the
lambda arrival rate is exponentially distributed time and it is related to the Poisson distribution.
So, in Poisson, this is the lambda arrival rate. So, there, all our lines will be empty.
Suppose, you are in state i. So, M minus i lambda will be the arrival rate of the incoming
line. So, we had also made a Markov chain for this. And there, finally, we calculated
the probability of being in any state, especially when the value of N is less than M. Only then
can we calculate the probability of being in any state.
So, in this case, we found that the probability switch or the probability switch is in the
i th state. Its probability was M C i lambda by mu power i. And below, we added the probabilities
of all the states. Basically, if we write 1 in the denominator below, we will divide
it by this. So, this is the value of P 0. So, we calculated this for N. Here, N is less
than M. If M was here instead of N, then it will convert into a binomial expansion. We
saw this last time. So, its value is M C i lambda by mu i. So, we saw the state probability.
If the value of i is N, then my switch is in the blocking state. So, we can represent
the probability of blocking as M C i lambda by mu. We have made the value of i equal to
N. This is the probability of the composite switch blocking state. So, basically, on an
average, if you observe this for a very long time, then for how much fraction of time,
it will be in the blocking state, this formula shows that. So, this is called time congestion.
So, we have to find out the relation with call congestion. So, what we will do for the
relation of call congestion? There is a rule called Bayes rule. Everyone studies this
in probability. It is taught in 11th, 12th, and then in your B.Tech. So, in this, it
has two joint events, probability of X or Y. If you have to write this, then if the probability
X given Y, Y is there, then what is the probability of X? This is that probability. And what is
the probability of Y? This is equal to this. This is the Bayes rule. So, we can write
this in another way. So, this will come to us. We can write this in this way. So, we
will use this part, Bayes rule. This is used a lot in our daily life, if you want to
do it. So, people generally do not understand this rule or do not be able to visualize it.
So, sometimes they even get the wrong interpretation. So, what we have to do now? We have to find
out the probability that if I am in a blocked state. This is an independent probability.
So, at this time, a call comes. That means the call came and the call was blocked. These
are two events. If both these events are together, we have to find out the probability of that.
So, if I am in a blocked state, the probability will be that if a call comes when I am in a
blocked state. This is basically the probability that the call comes and the call is blocked.
Now, we can also write it in this way that if your call comes, after the call comes,
when the call comes, when the call reaches, what is its probability that it will be blocked?
So, this equation tells me how many calls have been blocked on an average in a long time.
I make a lot of calls. It basically tells me how many fractions of them have been blocked.
So, if a call is not coming, then it will not be blocked. Probability estimates it.
Whereas, this tells when a call is coming. If a call is not coming, then this value is
independent. So, we use this expression. So, we have found out what PB is. Now, the
second thing we have to find out is this. We are trying to find out this. This is called
call congestion. If I make a call, then the probability is that the call will be blocked.
I am trying to find out that. So, the first thing is that if I am in a blocked state,
then what will be the probability of call arrival? This means that I am in a blocked
state when I have n lines already occupied here. So, how many remaining lines do I have
which are empty? m minus n. So, how many calls will come? So, this P of probability of arrival
when the call is in a blocked state, it should be m minus n. We will multiply it by lambda.
This is the same as we read Markov chain in the last lecture. This comes from there.
So, I have found out PB. I have found out PA. What is PA? If I can find out PA, then I
can find out what is my probability of loss given arrival? What is call congestion? Then
we will be able to find out. So, to find out PA, but PA is the average arrival probability
of the switch. If I am in the ith state, then my arrival probability is m minus i into
lambda. This is changing and I need the arrival probability. So, this means that I can average
out this with every state probability. So, I will be able to find out the average arrival
probability. So, we use this principle. So, to find out P of A, we will use the switch
probability. What is the probability of being in any state of the switch and what is the
probability of arrival in that state? We can find out the average from this over all states.
How many states are there? From 0 to n states. So, this is our PA. We should get from this.
So, let us calculate this and see what our PA comes from this. So, we have already found
out this in the last class. This is PI. So, we use this PI here. So, I write down arrival
here. What will we write here? m C i lambda by mu raised to the power i. Here, I will
not use i index again because it is a different term and it is independent of i. It is not
dependent on i index. If you look at the formula behind, then we will use j here.
Many people make a mistake while deriving this. I have seen this in most of the students.
So, that is why I change this a little here. This will not cause confusion. This is our
probability of arrival, but we will have to solve this. So, let us solve this. So, let
us see what happens. This is m factorial, i factorial, mu raised to the power i. So,
m minus i factorial and here lambda by mu raised to the power i. We have m factorial,
j factorial, m minus j factorial, lambda to the power j. Now, we have to solve this.
So, we can write m minus i factorial as m minus i, m minus i minus 1, i plus 1. We
know the definition of factorial. So, we can write it here. We use this expression
here. So, this m minus i will cancel with this m i. So, we can remove this. We have
this. From this, we can write m as m times m minus 1. So, we do the same thing here.
So, we can write m as m minus 1. Similarly, we can do the same thing here. So, we take
out this m and lambda. So, we will have m lambda. Now, this is equal. This is the probability
of arrival. So, we have the probability of blocking and this is my arrival rate. We
can write m minus i factorial here. So, this is the probability of arrival. So, we have
m minus i factorial. So, we have m minus i factorial. So, we have m minus 1. Now, we
can write m minus i factorial here. So, we have m minus 1 factorial. So, we have m minus
i factorial. So, we have m minus 1 factorial. So, we have m minus 1 factorial. Now, we
can write m plus i factorial here. So, this is. So, this is my arrival rate. So, this
is m minus 1 factorial. So, we can write m minus i factorial here.
So, this is m plus i factorial. So, this is m plus i factorial. So, we have m minus
So, we can write this expression as m minus n divided by p a, where p a is equal to m
summation i equal to 0, m summation i equal to n.
So, we can write this expression as m minus n divided by p a, where p a is equal to m
summation i equal to n, m summation i equal to n, m summation i equal to n, m summation
i equal to n, m summation i equal to n, m summation i equal to n, m summation i equal
to n, m summation i equal to n, m summation i equal to n, m summation i equal to n, m
summation i equal to n, m summation i equal to n, m summation i equal to n, m summation
i equal to n, m summation i equal to n.
minus 1. If my switch is such that there is m minus 1 line and n output, then the probability
of locking is equal to m by n probability of L. These two are equal. This is for this
and this is for this. So we can write it like this. Here the value of n is less than m.
That is why there is a blocking. So we will use this expression further through the Karnaugh's
approach to find out the probability of blocking in a three-stage Clos network. We did it with
the Lease approximation last time, but we will not be able to understand this method
until we understand this thing. And even there, this principle comes from there, but
we will not prove it, but we can use it to find out an alternate expression, which will
tell us how much time congestion will be. How much call congestion will be if we know
the time congestion? So we are actually finding out call congestion through Karnaugh's approach.
So we will go there through Karnaugh's approach. In Karnaugh's approach, there are some important
things in it that there will be some switches in the first stage, as it was in Lease approximations,
this is called Karnaugh's approach. So there will be some middle stage switches in the middle.
We will have some switches here. There are three stages. I am connected to every middle
stage switch. I am connected to every switch here. This is true for all these switches.
Let us assume that this is coming from the definition of a Clos network. So, if I want
to join my input here and my output here, then the blocking probability in between them
that if I want to try a connection, but the connection is not possible, that blocking
probability will be the same if I want to join some connection here and some connection
here. This is called being equivalent. That is, if we take any input-output combination,
the situation is the same. If the switch looks the same, then it will be the same blocking
because the middle stage switch is the same. And this is also connected in the same way
as this input and this output are connected. This number we have, there is no difference
between this number and this number. This is because of the symmetry of the switch.
So, now when I want to set this connection, I erase this red one. We will focus a little
on this. So, these links are called input links. We represent this with x. These are
called output links. We represent this with y. Now, how many of these links are already
busy, their value is called x. How many of these links are busy, they are called y.
Because now what we have done is used the equivalence that we take this input-output
pair or take this one and this one or take this one and this one or take this one or
this one. There is no difference. They are all equal. So, if we do a full analysis for
one input or output, it is valid for everyone else. So, I can estimate the blocking probability
of the switch. So, I do not have to do it for everyone. So, we have simplified it in
this way. This is called the state reduction method basically. We have reduced the number
of states of the switch because they are equivalent states. Now, if x line is busy and y line
is busy, this also represents the state. So, we can say that sigma is a state which
is dependent on x and y. So, when we take any specific value of x and y, it becomes
one state. Suppose, one link is busy here and one link is here. The value of x and
x is 1 and the value of y is also 1. So, the value of x is 1 and the value of y is 1.
So, we can say that sigma is a state which is dependent on x and y. So, we have reduced
the number of states of the switch. So, if we do a full analysis for one switch, it
is valid for everyone. So, we can say that sigma is a state which is dependent on x and
one by one by understanding that, how we can get a final expression for blocking probability, for this particular switch configuration.
