# M/M/c


如圖，$M/M/c$ 因為 server 數量變成 $c$，因此 service rate 會隨著當前系統人數而變動，不過最大就是 $c\mu$（$c$ 個 server 都為 busy 的狀態下）。

和 [M/M/1](/XvXWlqwTTAuFAXpscoWHVw) 一樣，由 Steady-state probability distribution 去推導出各個系統變量，像是系統平均人數（$L$）、顧客平均等待時間（$W_q$）等等。

首先我們要先跟據 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\ n \ge c\end{cases}$$

$p_0$ 一樣用機率和等於 1 去求解，當 $\rho = \frac{\lambda}{c\mu} \lt 1$ 時等比級數會收斂，有解：

$$\begin{split} p_0 &= [\sum_{n=0}^{c-1} \frac{\lambda^n}{n! \mu^n} + \sum_{n=c}^{\infty} \frac{\lambda^n}{c^{n-c}c!\mu^n}]^{-1} \\
&=[\sum_{n=0}^{c-1} \frac{\lambda^n}{n! \mu^n} + \frac{r^c}{c!} \sum_{n=c}^{\infty}(\frac{r}{c})^{n-c}]^{-1} \\
&=[\sum_{n=0}^{c-1} \frac{\lambda^n}{n! \mu^n} + \frac{r^c}{c!} \sum_{m=0}^{\infty} (\frac{r}{c})^{m}]^{-1} \\
&=[\sum_{n=0}^{c-1} \frac{\lambda^n}{n! \mu^n} + \frac{r^c}{c!}\cdot \frac{1}{1 - \frac{r}{c}}]^{-1}\end{split}$$

## Measures of Effectiveness

### Average Waiting Queue Size

先算$L_q$，因為只需要考慮 $n \gt c$ 的情況，比 $L$ 好算，算完 $L_q$ 之後再用 Little's Formula 求 $L$。

$$\begin{split} L_q &= \sum_{n=c+1}^{\infty} (n-c)p_n \\
&= \sum_{n=c+1}^{\infty} (n-c)\frac{\lambda^n}{c^{n-c}c!\mu^n} p_0 \\
&= \sum_{n=c+1}^{\infty} (n-c) \frac{r^n}{c^{n-c}c!} p_0 \\
&=\frac{p_0r^c}{c!} \sum_{n=c+1}^{\infty} (n-c) \frac{r^{n-c}}{c^{n-c}} \\
&=\frac{p_0r^c}{c!} \sum_{m = 1}^{\infty}m \rho^{m} \\
&=\frac{p_0r^c \rho}{c!} \sum_{m = 1}^{\infty}m \rho^{m-1} \\
&=\frac{p_0r^c \rho}{c!} \frac {\partial}{\partial \rho} \sum_{m = 1}^{\infty} \rho^{m} \\
&=\frac{p_0r^c \rho}{c!} \frac {\partial}{\partial \rho} \frac{\rho}{1 - \rho} \\
&=\frac{p_0r^c \rho}{c!} \frac{1}{(1 - \rho)^2} \\
&= \frac{r^c \rho}{c! (1 - \rho)^2} \cdot p_o\end{split}$$

### Average System Size

$$L = L_q + \frac{\lambda}{c\mu}\cdot c = L_q +\frac{\lambda}{\mu} = L_q + r$$

### Average Waiting Time

$$W = \frac{L}{\lambda} = W_q + \frac{1}{\mu}$$

### Average Queue Time

$$W_q = \frac{L_q}{\lambda} = \frac{r^c} {(c\mu)c! (1 - \rho)^2} \cdot p_o$$

## Congestion Measure

和 [M/M/1](/XvXWlqwTTAuFAXpscoWHVw) 的 waiting time distribution 一樣，定義 $T_q$ 為一個 random variable，表示在 steady state 時 customer 在系統裡等待的時間

$$W_q(t) = Pr(T_q \le t)$$

$W_q(0)$ 代表 customer 可以被立即服務的機率，而 $1 - W_q(0)$ 就代表 customer wait time 大於 0 的機率([Erlang-C ($C(c,r)$)](https://en.wikipedia.org/wiki/Erlang_(unit)#Erlang_C_formula))。

這裡的推導是很簡略的，我們只考慮單純的 $M/M/c$ queue，不考慮任何其他複雜狀況，例如：顧客等待一段時間決定不等了，或者掛斷電話又重打一次，以及 nonstationary arrival 等等。

$$\begin{split} W_q(0) &= Pr(T_q = 0) = Pr(系統人數不大於c-1) \\
&= \sum_0^{c-1} p_n \\
&= p_0\cdot \sum_0^{c-1}\frac{r^n}{n!}\end{split}$$

又已知

$$\begin{align}
&p_0 = [\sum_0^{c-1} \frac{r^n}{n!} + \frac{r^c}{c!}\cdot \frac{1}{1 - \frac{r}{c}}]^{-1} \\
&\Rightarrow \sum_0^{c-1} \frac{r^n}{n!} = \frac{1}{p_0} - \frac{r^c}{c!}\cdot \frac{1}{1 - \frac{r}{c}} = \frac{1}{p_0} - \frac{r^c}{c!(1 - \rho)}
\end{align}$$

所以
$$\begin{align} W_q(0) &= p_0\cdot (\frac{1}{p_0} - \frac{r^c}{c!(1 - \rho)})\\
&=1 - \frac{r^c p_0}{c!(1 - \rho)}
\end{align}$$

所以

$$\begin{split} \therefore 1 - W_q(0) &= \frac{r^c p_0}{c!(1 - \rho)} \\
&= \frac{r^c}{c!(1 - \rho)} \cdot \frac{1}{\sum_0^{c-1} \frac{r^n}{n!} + \frac{r^c}{c!}\cdot \frac{1}{1 - \frac{r}{c}}} \\
&= \frac{r^c}{c!(1 - \rho)} \cdot \frac{1}{\sum_0^{c-1} \frac{r^n}{n!} + \frac{r^c}{c!(1-\rho)}} \\
&=C(c,r)\end{split}$$

我們稱$C(c, r)$為 Erlang-C formula，當數字太大時很難計算時，可用[Erlang's Loss Formula(M/M/c/c) & M/M/無限大](/B9Rgdk_1SIeylYy-iHBJUw) 中介紹的 Erlang B 對於 Erlang C的遞迴公式去做計算。

## Waiting Time Distribution

:::info
$W_q, T_q$ 的關係是：若我們對 $T_q$ 取期望值，就會得到 $W_q$。

$W_q(t)$ 為 $T_q$ 的 cdf（$W_q(t) = Pr(T_q \le t)$），我們令 $T_q$ 的 pdf 為 $w_q(t)$，則 $T_q$ 的期望值可表示成:

$$\begin{align} &E[T_q] = \int_0^{\infty} w_q(t)\cdot t \ dt = \int_0^{\infty} w_q(t)\cdot (\int_0^{t} 1 \ dx) \ dt \\
&=\int_0^{\infty} \int_x^{\infty} w_q(t) \ dt \ dx \\
&=\int_0^{\infty} (1 - W_q(x)) \ dx
\end{align}$$
:::

$$\begin{split} W_q(t) &= Pr(T_q \le t) \\
&= W_q(0) + \sum_{n=c}^{\infty} Pr(n-c+1 個customer在t時間內被服務完畢|系統有n個customer) \cdot p_n \\
&= W_q(0) + \sum_{n=c}^{\infty} \frac{Pr(n-c+1 個customer在t時間內被服務完畢 \cap 系統有n個customer}{p_n} \cdot p_n \\
&= W_q(0) + \sum_{n=c}^{\infty} Pr(n-c+1 個customer在t時間內被服務完畢 \cap 系統有n個customer)\\
&= W_q(0) + \sum_{n=c}^{\infty} p_n \cdot Pr(n-c+1個customer在t時間內被服務完畢)\end{split}$$

因為system service rate 在system size 大於等於 $c$ 時是 $c \mu$，所以 $n-c+1$ 個人被服務完畢的 time distribution 可以用 Erlang type $n-c+1$ 來描述(積分)。

$$\begin{split} W_q(t) &= W_q(0) + \sum_{n=c}^{\infty} \frac{r^n}{c^{n-c}c!}p_0 \cdot \int_0^{t} \frac{(c\mu)^{n-c+1} \cdot x^{n-c}\cdot e^{-c \mu x}}{(n-c)!}dx \\
&= W_q(0) + \int_0^{t} \frac{r^n}{c^{n-c}c!}p_0 \cdot \sum_{n=c}^{\infty}\frac{(c\mu)^{n-c+1} \cdot x^{n-c}\cdot e^{-c \mu x}}{(n-c)!}dx \\
&= W_q(0) + \int_0^{t} \frac{r^c p_0}{(c-1)!} \cdot \mu e^{-c\mu x}\sum_{n=c}^{\infty}\frac{(\mu rx)^{n-c}}{(n-c)!}dx \\
&= W_q(0) + \int_0^{t} \frac{r^c p_0}{(c-1)!} \cdot \mu e^{-\mu x(c-r)}dx \\
&= W_q(0) + \frac{r^c p_0}{(c-1)!(c-r)} \int_0^{t} \cdot \mu (c-r) e^{-\mu (c-r)x}dx \\
&= W_q(0) + \frac{r^c p_0}{(c-1)!(c-r)} \cdot (1 - e^{-(c\mu - \lambda)t}) \\
&= 1 - \frac{r^c p_0}{c!(1 - \rho)} + \frac{r^c p_0}{(c-1)!(c-r)} \cdot (1 - e^{-(c\mu - \lambda)t})\\
&= 1 - \frac{r^c p_0}{(c-1)!(c-r)} + \frac{r^c p_0}{(c-1)!(c-r)} \cdot (1 - e^{-(c\mu - \lambda)t})\\
&= 1 - \frac{r^c p_0}{(c-1)!(c-r)}e^{-(c\mu - \lambda)t}\end{split}$$

而

$$W_q = E[T_q] = \int_0^{\infty} (1 - W_q(t)) dt = \frac{r^c}{(c\mu)c! (1 - \rho)^2} \cdot p_o$$

:::info
Note:
$Pr(T_q \gt t) = 1 - W_q(t) = \frac{r^c p_0}{(c-1)!(c-r)}e^{-(c\mu - \lambda)t}$

$Pr(T_q > t | T_q > 0) = e^{-(c\mu - \lambda)t}$
:::

## Choosing the number of servers in M/M/c

$c = r + \Delta$, server數量必須要比 offered load（$r$）大，要不然系統為unstable，$\Delta \gt 0$，可以是小數(使server數量為整數)

當arrival rate升高的時候，為了維持顧客滿意度，以及不要花太多成本建置新的server的考量下，到底應該增加多少台server呢?

以下提供三種考量的標準，分別為
1. Quality Domain: 維持同樣的 traffic intensity
2. Quality and Efficiency Domain:維持差不多的congestion measure，也就是找到最小的 $c$ 使得 $1 - W_q(0) \le \alpha$ where $\alpha$為 maximum desired fraction of callers delayed in the queue
3. Efficiency Domain: 維持同樣的 $\Delta$

> 一開始 $r = 9, c = 12$
> 後來 $r = 36$

QD 的作法會讓 system 的 delay 很小，但是缺點是太貴，而 ED的作法好處是很省錢，但是system會congested。

Quality and Efficiency Domain(QED) 最平衡，著重在維持相同service quality，在這個方法中，要計算出 c 比較麻煩，一個簡單的approximation為:

$$c = r + \beta \sqrt r$$

pf: