M∕M∕1∕K Queue Analysis

Farbod Shahinfar

June 19, 2024

Consider a queue receiving requests with exponential (memory-less) inter-arrival distribution and exponential service time. There is only one service node and the maximum buffer size is K. This system is represented with M∕M∕1∕K Kendall’s notation. The request are either received and placed in the queue or they are blocked. If the request are received, then they will not live the queue until they are serviced. In this post, a basic analysis of the system is performed.

1 Stationary Probabilities of M∕M∕1∕K

012.Kλμλμλμλμ..

Figure 1:This CTMC shows different states of M∕M∕1∕K system and transition rates.

We can write balance equation for this CTMC.

λπ0 = μπ1 =⇒ π1 = λ μ-π0
(λ + μ)π1 = λπ0 + μπ2 =⇒ π2 = λ -- μπ1
...
πi = λ μ-πi−1

According to equations, we can see that the stationary probability of state i is calculated as below.

λ i πi = (-) π0 μ
(1)

Sum of stationary probabilities should be one. By solving this equation we can figure out the value for π0. By knowing π0 we can calculate other πi (eq. 1).

∑K πi = 1 i=0
(2)

Steps for solving the eq. 2 are given below.

∑ i=0Kπ i = 1 =⇒
∑ i=0K(λ- μ)iπ 0 = 1 = ⇒
π0 ∑ i=0K(λ μ-)i = 1 = ⇒
π0( K+1 1−-(λμ)---- 1 − λ μ) = 1
π0 = μ−λ ----μ----- μK+1K−+λ1K+1 μ

Values for stationary probabilities are calculated as shown below.

i μ−λ- πi = (λ)-K+1μ-K+1- μ μ--μ−Kλ+1--
(3)

2 Blocking Probability of M∕M∕1∕K

Now that we know the stationary probability for M∕M∕1∕K queueing systems, we can calculate the probability of request arriving to a full queue. In this case the request are blocked (dropped) and not serviced.

--λK(μ-−-λ)- PBlock = πK = μK+1 − λK+1
(4)

3 Throughput of M∕M∕1∕K

The throughput of the system is same as the rate of request placed into the queue. If we discard the request that are blocked, the rest of requests will eventually exit the system.

Throughput = (1− P )λ Block
(5)

4 Expected Queue Size

E[N] = ∑ i=0Kiπ i
E[N] = ∑ i=0Ki(λ μ-)i μ−μλ- μK+1−λK+1- μK+1
E[N] = μ−μλ- μK+1−λK+1- μK+1 ∑ i=0Ki(λ μ-)i
E[N] = μ−μλ- μK+1−λK+1- μK+1 ×λ μ-∑ i=0Ki(λ μ-)i−1
ρ = λ- μ
E[N] = μ−μλ- μK+1−λK+1- μK+1 ×λ μ-∑ i=0Kd dρ(ρ)i
E[N] = μ−μλ- μK+1−λK+1- μK+1 ×λ μ- ×d dρ∑ i=0K(ρ)i
E[N] = μ−μλ- μK+1−λK+1- μK+1 ×λ μ- ×d dρ1− ρK+1 --1−-ρ--
E[N] = μ−μλ- μK+1−λK+1- μK+1 ×λ μ- ×− (K + 1)ρK(1− ρ)+ 1− ρK+1 ---------------2----------- (1− ρ)
…

5 Expected Request Response Time

Now that we have calculated the expected number of request in the queue we can use Little’s law to obtain the expected request response time. This rule simply states that the expected number of request in the system (expected size of the queue) is same as the rate of incoming requests to the queue times the expected time a request spend in the system.

λ′ = (1 − PBlock)λ
E[N] = λ′E[T]
E[N-] E [T] = λ′
(6)