# M/M/c/K

和 [M/M/1](/XvXWlqwTTAuFAXpscoWHVw) 以及 [M/M/c](/AqYQ-LLURnSRMRIS31N4GA) 一樣，由 Steady-state probability distribution 去推導出各個系統變量，像是系統平均人數（$L$）、顧客平均等待時間（$W_q$）等等，不同的地方在於 system capacity，現在系統總容量上限為 $K$，所以$p_n$ 在 $n\gt K$ 時會是 0。

首先我們要先跟據 Balanced Equation 去求出 Steady-state probability distribution。

$$p_n = \begin{cases} \frac{\lambda^n}{n!\mu^n} \cdot p_0,\ when\ 0 \le n \lt c \\
\frac{\lambda^n}{c^{n-c}c!\mu^n} \cdot p_0,\ when\ c \le n \le K \\
0,\ when\ n \gt K\end{cases}$$

$p_0$ 一樣用機率總和等於 $1$ 去求解，和 $M/M/c$ 不同的是，此處 $\rho = \frac{\lambda}{c\mu}$ 不需要小於一，因為等比級數是 finite 的，沒有收不收斂的問題。

我們先求出 $L_q$，和 $M/M/c$ 一樣，因為只需要考慮 n 大於 c 的狀況。

$$\begin{split} L_q &= \sum_{n=c+1}^k (n-c)p_n \\
&= \sum_{n=c+1}^k (n-c) \frac{r^n} {c^{n-c}c!}\cdot p_0 \\
&= \frac{p_0 r^c}{c!} \sum_{n=c+1}^k (n-c) \frac{r^{n-c}}{c^{n-c}} \\
&= \frac{p_0 r^c \rho}{c!} \sum_{n=c+1}^k (n-c) \rho^{n-c-1} \\
&= \frac{p_0 r^c \rho}{c!} \sum_{i=1}^{k-c} (i) \rho^{i-1} \\
&= \frac{p_0 r^c \rho}{c!} \frac{\partial}{\partial \rho}\sum_{i=1}^{k-c} \rho^{i} \\
&= \frac{p_0 r^c \rho}{c!} \frac{\partial}{\partial \rho}\frac{1 - \rho^{k-c+1}}{1-\rho} \\
&=\frac{p_0 r^c \rho}{c!(1-\rho)^2} \cdot (1 - \rho^{k-c+1} - (1-\rho)(k-c+1)\rho^{k-c}) \\
&=L_q \end{split}$$

$M/M/c/k$ 的重點在於 $\lambda_{eff}$（effective arrival rate），其他變量都可以由 $L_q$ 和 $\lambda_{eff}$ 用 Little's Formula 推導出來。

## Effective Arrival Rate

我們定義 effective arrival rate：

$$\lambda_{eff} = \lambda(1 - p_K)$$

直觀來想就是 server所看到的 arrival rate，（$1 - p_k$）就是 customer 不會被 block ，可以順利進入到system 的機率。

$$\begin{cases} L = L_q + \frac{\lambda_{eff}}{\mu} = L_q + r(1-p_K), \rho_{eff} = \frac{\lambda_{eff}}{c\mu} \\ W = \frac{L}{\lambda_{eff}}, W_q = \frac{L_q}{\lambda_{eff}} \end{cases}$$

### Special Case: M/M/1/k

:::info
when $c = 1$ 可以證明出 $L = L_q + (1 - p_0)$
$\therefore 1 - p_0 = \frac{\lambda(1- p_K)}{\mu}$
$\therefore \mu(1 - p_0) = \lambda(1- p_K)$，這等式代表的意思是，system effective output rate = system effective input rate，直觀來想也合理，因為現在系統只有一個 server，所以真正進去系統被server處理的，會等於被server處理（$1 - p_0$就是 server 不 idle，也就是在工作的機率）完之後離開系統的量。
:::

## Waiting Time Distribution

在求 $W_q(t)$ 之前，我們要先求出 Input Pattern $q_n$，因為 system capacity is limited（有 blocking），所以 input 不再是 Poisson。

我們定義 Arrival point probability

$$q_n = Pr(系統有n個人 | arrival即將發生)$$

並用 Bayes' Theorem 來解出其值。

$$\begin{align} &Pr(系統有n個人 | arrival即將發生) \\
&= Pr(arrival即將發生 |系統有n個人) \cdot \frac{Pr(系統有n個人)}{Pr(arrival即將發生)} \\
&= Pr(arrival即將發生 |系統有n個人) \cdot \frac{p_n}{\sum_{n=0}^K Pr(arrival即將發生 | 系統有n個人) \cdot p_n} \\
&= \lim_{\Delta t \to 0}\frac{(\lambda \Delta t + o(\Delta t))\cdot p_n}{\sum_{n=0}^{K-1}(\lambda \Delta t + o(\Delta t))\cdot p_n} \\
&= \lim_{\Delta t \to 0} \frac{\frac{\lambda \Delta t + o(\Delta t)}{\Delta t}\cdot p_n}{\sum_{n=0}^{K-1}\frac{\lambda \Delta t + o(\Delta t)}{\Delta t}\cdot p_n} \\
&= \frac{\lambda p_n}{\lambda \sum_{n=0}^{K-1} p_n} \\
&= \frac{p_n}{1 - p_K},\ where\ n \le K - 1
\end{align}$$

:::info
記得在 [Poisson Process & Exponential Distribution](/5a0BMBLqTdaOrjxfoeqdEg) 中有學到 Poisson Process 的推導過程：

$$\begin{cases} Pr(there's\ an\ arrival\ between\ T\ and\ T + \Delta t) = \lambda * \Delta t + o(\Delta t) \\ Pr(more\ than\ one\ arrival\ between\ T\ and\ T + \Delta t) = o(\Delta t) \\ \frac{lim_{\Delta t \to 0}\ o(\Delta t)}{\Delta t} = 0 \end{cases}$$

我們使用 $\lambda \Delta t + o(\Delta t)$ 來表示 $Pr(arrival即將發生 | 系統有n個人)$。

在系統已經有 $K$ 個人的情況下，$Pr(arrival即將發生 | 系統有n個人) = 0$（會被 Block）。
:::

當 K 趨近於無限大時， $M/M/c/K$ 就會變成 $M/M/c/\infty$，這時 $p_K$ 就會變成 $0$，且$q_n = p_n$

## Waiting Time Distribution

以下分析的過程和 [M/M/1](/XvXWlqwTTAuFAXpscoWHVw) 的 $W_q(t)$ 類似，只是將 $p_n$ 換成 $q_n$，以及當一個 customer 抵達一個已經有 $n$ 個 customer 的系統時，$M/M/1$ 需要等待的是 $n$ 個人被服務完成，而 $M/M/c/k$ 需要等待的是 $n-c+1$ 個人被服務完成，因為系統裡目前有 $c$ 個人正在被 server 服務，以及 $n - c$ 個人在等待，所以目前 arrive 的這個customer 只需要等待 $1 + (n-c)$ 個人被服務完就可以輪到他。

因為 system service rate 是 $\mu$，且是一個exponential r.v.，而每個人被服務的時間都是 exponentially distributed，且互相獨立，所以 $n-c+1$ 個人被服務完畢所需要的時間可以用 Erlang 來描述，又因為這裡要求的是要在時間長度 $t$ 以內完成，所以用積分來算。

定義 $T_q$ 為一個 random variable，表示在steady state 時 customer 在系統裡等待的時間。

$$\begin{split} W_q(t) &= Pr(T_q \le t) \\
&= W_q(0) + \sum_{n=c}^{k-1} Pr(n-c+1個customer在t內被服務完|系統有n個customer) \cdot q_n \\
&= W_q(0) + \sum_{n=c}^{k-1} \frac{Pr(n-c+1個customer在t內被服務完畢 \cap 系統有n個customer)}{q_n} \cdot q_n \\
&= W_q(0) + \sum_{n=c}^{k-1} Pr(n-c+1個customer在t內被服務完畢 \cap 系統有n個customer) \\
&= W_q(0) + \sum_{n=c}^{k-1} q_n \cdot Pr(n-c+1個customer在t內被服務完畢) \\
&= W_q(0) + \sum_{n=c}^{k-1} q_n \cdot \int_0^{t} \frac{c\mu^{n-c+1} \cdot x^{n-c}\cdot e^{-c \mu x}}{(n-c)!}dx \end{split}$$