[PYTHON] Queuing theory part 3
Last time Consider M / M / N / N as previously announced. This time, [Queue theory (written by Shinichi Oishi)](https://www.amazon.co.jp/%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97% E7% 90% 86% E8% AB% 96-% E5% A4% A7% E7% 9F% B3-% E9% 80% B2% E4% B8% 80 / dp / 4339060739) is used as a reference.
What is M / M / N / N model?
The M / M / N / N model is a one-server model in which the client arrives according to the Poisson distribution and the service time follows the exponential distribution. The maximum length of the matrix is 0. This means that there is no matrix. The service discipline is omitted, but it is FCFS. This system is also known as Erlang's call loss rate system. This model is a basic idea for models that cannot be queued like this, so you should understand it. Also note that in this model the utilization is $ \ rho = \ frac {\ lambda} {N \ mu} $ by definition.
Probability of n people in the system
First, suppose the client comes according to the Poisson process. That is, assume that at most one client comes to the sufficiently short time interval $ \ Delta t $. At this time, if the average arrival rate is $ \ lambda $, the probability that one client will come can be expressed as $ \ lambda \ Delta t $. Here, the probability that there are k clients in the system at time t is $ P_k (t) $. We will describe the change of this probability after $ \ Delta t $. Similarly, the probability that a client will leave a server with an average service rate of $ \ mu $ is $ \ mu \ Delta t $.
Up to this point, it is the same as the previous assumption. This time, let's assume that the average service rate when the state k is $ 1 \ leq k \ leq n $ is $ k \ mu $. This means that there are k servers running with an average service rate of $ \ mu $. In the following, we will consider an equation (equation of state) that expresses the change in the number of clients in the system. However, as in the previous, consider the boundary by paying attention to the boundary $ k = 0, N $. If you calculate it assuming that it has reached a steady state after sufficient time
Average number of customers in the system L
Since L is the average value, that is, the expected value, it can be calculated from $ L = \ sum_ {k = 0} ^ {N} kP_k $. So $ L = \ sum_ {k = 0} ^ {N} kP_k $
Average waiting time in the system W
From Little's formula $ W = \ frac {L} {\ lambda} = \ frac {1-P_N} {\ mu} $
Average number of customers in the queue L_q
It will be 0 because there is no queue.
Average queue wait time W_q
It will be 0 because it will not be queued.
Call loss rate
The call loss rate is the percentage of people who cannot be queued and are evacuated. It is usually written as $ P_b $ or $ E_N (a) $, but here it is written as $ E_N (a) $. The call loss rate is equal to the probability that the server is full, so $ E_N (a) = P_N $. This is called the Erlang B formula because Mr. Ala found it. As an aside, it seems that there is even a C formula.
More interestingly, as a recurrence formula
Amount Y passed and amount a_l lost
The amount passed is the average number of customers in the system. That is, $ Y = a (1-P_N) = a (1-E_N (a)) $. From this, subtracting the amount passed from the overall average a to calculate the amount lost is $ a_l = a-Y = a E_N (a) $.
Relationship between a and N
Let B be $ E_N (a) = B $ with a constant value of 0 or more and 1 or less. At this time, the partial differential equation for a of $ E_N (a) $
Python:M_M_N_N.py
# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt
#Wasteful programs
def E_B(N, a):
#Calculate the Erlang B equation.
#N is the number of servers
#a is the traffic density
p=1
i=1
while i < N+1:
b = a * p
p = b / (i + b)
i += 1
return p
def make_list(n, b):
#n is the maximum number of servers
#b is the objective function E for solving by Newton's method_B(N, a)-Represents B of B and represents the call loss rate.
p = [0 for i in range(n+1)] # n+The first is E_B(N, a)Becomes
p[0] = 0 # a=s=Because 0 clearly holds
c = 1 # a_Determine the initial value c as 0.
for i in range(1, len(p)):
a = c
# E(N,a)=Find the value that becomes B by repeating about 20 times.
for j in range(20):
t = E_B(i, a)
a = a - (t-b) / ((i/a-1+t)*t)
p[i] = a
c=a #Update to a reasonable initial value for the next time
return p
#Draw and execute from here
n=50
b=0.01
p = make_list(n, b)
plt.figure()
plt.plot(range(n+1), p)
plt.xlabel("N")
plt.ylabel("a")
plt.title("E_N(a)=%.3f" % b)
plt.figure()
rho = [0]
for n, a in enumerate(p):
if n == 0:
continue
rho.append(a*(1-b)/n)
plt.plot(range(n+1), rho)
plt.xlabel("N")
plt.ylabel("rho_N(B)")
plt.title("E_N(a)=%.3f" % b)
plt.show()
According to this program, the relationship between traffic density a and number of servers N is
And the utilization rate $ \ rho_N (B) $ when B is the call loss rate is
Summary
Until now, this series was qiita, but there was no programming, so I added it. Please note that the calculation is done when $ 0 <\ rho <1 $, so if you calculate with any other value, it will be a strange value. And I'm still studying with the introductory book, so it could be wrong. What should I do next time?