# Queueing Theory - 3.3 Multiserver Queues (M/M/c)

contributed by <[`kaeteyaruyo`](https://github.com/kaeteyaruyo)>

###### tags: `Queueing Theory`

> Figure 3.6 Rate transition diagram for the M/M/c queue.

* M/M/c 是一種規律的排隊模型，跟 M/M/1 很相似，差別只在 M/M/1 只有一個 server，但是 M/M/c 有 c 個 server
* Fig. 3.6 是 M/M/c 的 Rate transition diagram，跟 M/M/1 的圖長的很像，但值得注意的是， M/M/c 的**服務率會跟系統中的人數有關**，並不是一個定值
* 顧客的到達率是定值， $\lambda_n = \lambda$
* 單一一個 server 的服務率依然是 $\mu$，但整個系統的服務率會跟系統中的人數有關
$$
\mu_n =
\begin{cases}
n \mu, & \; (1 \leq n < c) \\
c \mu, & \; (n \geq c) \\
\end{cases}
$$
* M/M/c 模型的 global balance equation 跟 M/M/1 的列法是一樣的，因此我們不需要再重新解一次 global balance equation，只要用 M/M/1 解出來的結果，並且把 $\mu$ 的部份用適當的 $\mu_n$ 替換掉，就可以直接得知 M/M/c 的 steady-state distribution
$$
p_n =
\begin{cases}
\frac{\lambda^n}{n!\mu^n}p_0, (1 \leq n < c) \\
\frac{\lambda^n}{c^{n-c}c!\mu^n}p_0, (n \geq c)
\end{cases}
$$
* 上式中還有 $p_0$ 這個未知數，可以利用 $\sum p_n = 1$ 的 boundary condition 求得
$$
p_0 = \Big(\sum_{n=0}^{c-1}\frac{r^n}{n!} + \sum_{n=c}^{\infty}\frac{r^n}{c^{n-c}c!}\Big)^{-1}, \text{ where } r = \frac{\lambda}{\mu}, \rho = \frac{r}{c}
$$
* 上式中的 $\sum_{n=c}^{\infty}\frac{r^n}{c^{n-c}c!}$ 可以再進一步化簡
$$
\begin{align}
\sum_{n=c}^{\infty}\frac{r^n}{c^{n-c}c!} &= \frac{r^c}{c!} \sum_{n=c}^{\infty}\Big(\frac{r}{c}\Big)^{n-c} \\
&= \frac{r^c}{c!} \sum_{m=0}^{\infty}\Big(\frac{r}{c}\Big)^{m} \\
&= \frac{r^c}{c!}\frac{1}{1 - \rho}
\end{align}
$$
因此 $p_0$ 可以再簡寫成
$$
p_0 = \Big(\frac{r^c}{c!(1 - \rho)} + \sum_{n=0}^{c-1}\frac{r^n}{n!}\Big)^{-1}
$$
* M/M/c 的效能指標
* Mean queue size: 在 M/M/c 系統當中，只有 c 個 server 都滿載了的情況下，才會有開始有人排隊的現象。所以計算 M/M/c 系統的 mean queue size 時，不需要考慮系統人數 $n < c$ 時的狀況，計算起來會算 mean system size 還要容易。 M/M/c 的 mean queue size 為
$$
\begin{align}
L_q &= \sum_{n=c+1}^{\infty} (n-c)p_n \\
&= \sum_{n=c+1}^{\infty} (n-c) \frac{r^n}{c^{n-c}c!} p_0 \\
&= \frac{r^c p_0}{c!} \sum_{n=c+1}^{\infty} (n-c) \rho^{n-c} \\
&= \frac{r^c p_0}{c!} \sum_{m=1}^{\infty} m \rho^m = \frac{r^c \rho p_0}{c!(1-\rho)^2}
\end{align}
$$
記得要將 $p_0$ 代入才算是 closed form
* 知道 $L_q$ 之後，就可以利用 Little's Law 來求取 $L$, $W_q$ 和 $W$
$$
\begin{align}
& L_q = \frac{r^c \rho p_0}{c!(1-\rho)^2} \\
& \Rightarrow W_q = \frac{L_q}{\lambda} = \Big(\frac{r^c}{c!(c\mu)(1-\rho)^2}\Big)p_0 \\
& \Rightarrow W = \frac{1}{\mu} + W_q = \frac{1}{\mu} + \Big(\frac{r^c}{c!(c\mu)(1-\rho)^2}\Big)p_0 \\
& \Rightarrow L = r + L_q = r + \frac{r^c \rho p_0}{c!(1-\rho)^2}
\end{align}
$$
* 上面算的都只是效能指標的平均值，但有時候我們依然需要 M/M/c 那些跟時間有關的效能指標的分佈函數。這些分佈函數的求取方式跟在 M/M/1 時是差不多的，但是在步驟上會因為 M/M/c 有 c 個 server 的關係變得更複雜一點
* Waiting time: 求取方法跟 M/M/1 的情況差不多，分成一定不用等和一定要等的兩個情況討論。在這裡我們不重寫各變數的意義，請參考 [3.2.5](https://hackmd.io/Hc0O0v8CRFO5pEOxBuH3Fw?view#325-Waiting-time-distribution) 中的定義
* $t=0$ 的時候，系統沒半個人，一定是不用等的。事實上，當系統內的人數未達 c 個人的時候，都是不需要等待的
$$
\begin{align}
W_q(0) &= Pr\{T_q = 0\} = Pr\{\leq c-1 \text{ in system}\} \\
&= \sum_{n=0}^{c-1} p_n = p_0 \sum_{n=0}^{c-1} \frac{r^n}{n!} \\
&= 1 - \frac{r^c p_0}{c!(1-\rho)}
\end{align}
$$
* 可以注意到，最後解出來的東西會是一個 1 減掉某個東西的長相。我們原本在計算的東西是 $Pr\{T_q = 0\}$ 的**機率**， 1 - 機率值就是該機率值所描述的事件的互斥事件發生的機率，也就是說
$$
Pr\{T_q = 0\} = 1 - Pr\{T_q > 0\} = 1 - \frac{r^c p_0}{c!(1-\rho)} \\
\Rightarrow Pr\{T_q > 0\} = \frac{r^c p_0}{c!(1-\rho)}
$$
這條式子稍後在計算 system time 的時候會用到
* $t > 0$ 的時候，要分成一定要等跟一定不用等的兩種狀況討論。不用等的部份就是上面算的，而一定要等的狀況，就只有在系統中人數達到 c 個人的時候才會發生
$$
\begin{align}
W_q(t) &= Pr\{T_q \leq 0\} \\
&= \sum_{n=c}^{\infty} Pr\{n - c + 1 \text{ completions } \leq t |\text{arrival found n in system}\} \cdot p_n + W_q(0) \\
&= \sum_{n=c}^{\infty} \frac{r^n}{c^{n-c}c!}p_0 \cdot \int_0^t \frac{c \mu (c \mu x)^{n-c}}{(n-c)!}e^{-c \mu x} dx + W_q(0) \\
&= \frac{r^c p_0}{(c-1)!} \int_0^t \mu e^{-c \mu x}\sum_{n=c}^{\infty} \frac{(\mu r x)^{n-c}}{(n-c)!} dx + W_q(0) \\
&= \frac{r^c p_0}{(c-1)!} \int_0^t \mu e^{-\mu x (c-r)} dx + W_q(0) \\
&= \frac{r^c p_0}{(c-1)!(c-r)} \int_0^t \mu (c-r) e^{-\mu x (c-r)} dx + W_q(0) \\
&= \frac{r^c p_0}{c!(1-\rho)} [1-e^{-\mu(c-r)t}] + W_q(0) \\
&= \frac{r^c p_0}{c!(1-\rho)} [1-e^{-\mu(c-r)t}] + \Big(1 - \frac{r^c p_0}{c!(1-\rho)} \Big) \\
&= 1 - \frac{r^c p_0}{c!(1-\rho)}e^{-(c \mu - \lambda)t}
\end{align}
$$
* 在 M/M/c 系統當中，當某個顧客進入系統時看見有 $n$ 個人在裏面，他必須要等待到**系統裏面只剩下 $c - 1$ 個人**才會有 server 可以服務他，因此他必須等待前面 $n-(c-1)$ 個人被服務完才可以停止等待
* 在 M/M/c 系統當中，因為每個顧客的服務時間都呈現指數分佈，所以「前 $n-c+1$ 個人的服務時間加總」，就是在加總 $n-c+1$ 個指數分佈的隨機變數，也就是 Erlang-type **n-c** 的分佈
* 在把該消的消掉，把跟 $n$ 無關的項提出級數和後，為了得到 $e^{\mu r x}$ 的泰勒展開式 $\sum_{n=c}^{\infty}\frac{(\mu r x)^{n-c}}{(n-c)!}$，我們必須要把 $r^n$ 分出 $n-c$ 個乘入級數和內，所以外面剩下 $r^c$
* 為了把積分式喬成指數分佈的 PDF 的形式（這樣積分就可以不用算，直接用指數分佈的 CDF），我們必須在積分裏面多乘一個 $(c-r)$，而在外面要把他除掉
* 算完積分之後發現前面剩下的項跟 $W_q(0)$ 裏面 1 扣掉的那個東西長的一樣，所以可以把 $W_q(0)$ 代入，該消的對消掉後就得到答案
* 算出答案後發現他也是一個 1 減掉什麼東西，就如同我們剛剛在算 $W_q(0)$ 的時候一樣，我們也可以得到他的互斥事件的機率
$$
Pr\{T_q \leq t\} = 1 - Pr\{T_q > t\} = 1 - \frac{r^c p_0}{c!(1-\rho)}e^{-(c \mu - \lambda)t} \\
\Rightarrow Pr\{T_q > t\} = \frac{r^c p_0}{c!(1-\rho)}e^{-(c \mu - \lambda)t}
$$
* 現在我們把剛剛算 $W_q(0)$ 和 $W_q(t)$ 時算出來的副產物給湊起來，變成一個「在一定要等的前提下，等待時間會超過 $t$ 的機率」的條件機率，會得知
$$
Pr\{T_q > t | T_q > 0\} = \frac{Pr\{T_q > t, T_q > 0\}}{Pr\{T_q > 0\}} \\
= \frac{Pr\{T_q > t\}}{Pr\{T_q > 0\}} = \frac{\frac{r^c p_0}{c!(1-\rho)}e^{-(c \mu - \lambda)t}}{\frac{r^c p_0}{c!(1-\rho)}} = e^{-(c \mu - \lambda)t}
$$
* 利用這個條件機率，我們可以反過來求「在一定要等的前提下，等待時間不超過 $t$ 的機率」，也就是
$$
Pr\{T_q \leq t | T_q > 0\} = 1 - e^{-(c \mu - \lambda)t}
$$
會發現這是一個指數分佈的 CDF，因此我們可以知道，在一定要等待的前提下，等待時間不超過 $t$ 的機率是呈指數分佈的。這個特性在求取 system time 的時候會用到
* System time（待補充）