# M/M/1

> [image source](http://programmingpaul.blogspot.com/2013/04/queueing-theorymm1-model.html)

$M/M/1$ 是一個 arrival rate $= \lambda$，service rate $=\mu$，server 數量為 1，system capacity 為 $\infty$ 的 queue。

在 [Birth-Death Processes](/oN9Xfs1HTvmVN726XA8jdA) 中我們學到：

分析各種 queue 的第一步就是搞清楚 state transition，畫出各個 state 之間的 arrival & departure(service) rate（如 Figure 2.1），然後運用下面會介紹的 Balanced Equations 求出 steady state probability($p_n$) ，有了 steady state probability($p_n$) 就可以進一步分析 queue 的各種 metrics，像是 average system size $L$，以及 average waiting time $W$ 等等。

所以說，我們要先跟據 Balanced Equation 去求出 Steady-state probability distribution，求解的過程在 [Birth-Death Processes](https://hackmd.io/oN9Xfs1HTvmVN726XA8jdA#Steady-State-Probability) 有詳細說明。

這裡使用 iterative 方法來求解：

已知：

$$p_n =\frac{\lambda_{n-1}\lambda_{n-2}\cdot\cdot\cdot\lambda_{0}}{\mu_n\mu_{n-1}\cdot\cdot\cdot\mu_1} \cdot p_0 = (\frac{\lambda}{\mu})^np_0 = \rho^n p_0$$

利用機率合為一求解 $p_0$：

$$\begin{align} &\sum_0^{\infty} p_n = \sum_0^{\infty}\rho^np_0 = p_0\sum_0^{\infty}\rho^n = 1 \\ &\Rightarrow p_0 = \frac{1}{\sum_0^{\infty} \rho^n} = 1 - \rho\ (\ given \ \rho \lt 1)\\ &\therefore p_n = p_0 \rho^n = (1 - \rho) \rho^n \end{align}$$

$p_0 = 1 - \rho$，直觀來想也合理，$p_0$就是 system idle probability，而 $\rho$ 為系統使用率，也是系統 busy 的機率，所以用 1 減去系統忙碌的機率，剩下的就會是系統不忙碌（idle）的機率，而知道 $p_0, p_n$ 之後就可以求出以下系統變量（$e.g. L, W, \cdots$）。

## Measures of Effectiveness

### Average System Size

在求 L 時可以利用將等比級數表示成其close form的微分來化簡式子

$$\begin{split} L &= E[N] \\
&= \sum_0^{\infty} np_n \\
&= (1 - \rho) \sum_0^{\infty} n \rho^n \\
&= (1 - \rho) \rho \sum_0^{\infty} n \rho^{n-1} \\
&= (1 - \rho) \rho \sum_0^{\infty}\frac{\partial}{\partial \rho} \rho^n \\
&= (1 - \rho) \rho \frac{\partial}{\partial \rho}\frac{1}{1 - \rho} \\
&= \frac{(1 - \rho)\rho}{(1 - \rho)^2} \\
&= \frac{\rho}{1 - \rho} \\
&= \frac{\lambda}{\mu - \lambda}\end{split}$$

$L$ 也可以用 Little's Formulas 來求得:

$W$ 是顧客在系統裡面等待的時間，會等於自己被服務的平均時間（$\frac{1}{\mu}$）加上自己進到系統前就已經在系統裡面的顧客被服務完所需要的時間（$L\cdot \frac{1}{\mu}$）：

$$\begin{align}
&W = \frac{1}{\mu} + L\cdot \frac{1}{\mu} = \frac{1}{\mu} + \lambda W\cdot \frac{1}{\mu} = \frac{1 + \lambda W}{ \mu} \\
&\Rightarrow W = \frac{1}{\mu - \lambda} \\
&\Rightarrow L = \lambda W = \frac{\lambda}{\mu - \lambda}
\end{align}$$

### Average Waiting Queue Size

$L_q$ 代表 waiting queue 的 average size（不包括正在被 server 服務的那個 customer，所以 sigma 是從 1 開始，且是用 $(n-1)$ 去乘 $p_n$ ）。

$$\begin{split} L_q &= \sum_1^{\infty} (n-1)p_n \\
&= \sum_1^{\infty} np_n - \sum_1^{\infty} p_n \\
&= L - (1 - p_0) \\
&= \frac{\rho^2}{1 - \rho} \\
&= \frac{\lambda^2}{\mu (\mu - \lambda)}\end{split}$$

有了 $L, L_q$，可用 Little's Formulas 導出 $W, W_q$

### Average Waiting Time

$$W = \frac{L}{\lambda} = \frac{\lambda}{(\mu - \lambda) \lambda} = \frac{1}{\mu - \lambda}$$

### Average Queue Time

$$W_q = \frac{L_q}{\lambda} = \frac{\lambda^2}{\mu (\mu - \lambda) \lambda} = \frac{\lambda}{\mu (\mu - \lambda)}$$

### System Size Probability

$$\begin{split} Pr(N \ge k) &= \sum_{ n = k}^{\infty} p_n \\
&= \sum_{ n = k}^{\infty} (1 - \rho) \rho^n \\
&= (1-\rho)\rho^k\sum_{ n = k}^{\infty} \rho^{n-k} \\
&= (1-\rho)\rho^k\sum_{m=0}^{\infty} \rho^{m} \\
&= \rho^k \end{split}$$

### The Expected Non-empty Queue Size

$n = 0, 1$這兩個case 我們不計算，因為這時候queue都是empty的( 因為 server 數量 = 1)

而 given queue is not empty 的 conditional probability 為：

$$\frac{P(n \ge 2 且系統裡面有n個人)}{P(n \ge 2)} = \frac{p_n}{\rho^2}$$

有了 conditional probability ，即可算期望值：

$$\begin{split} L'_q &= \sum_{n=2}^{\infty} (n-1) \cdot \frac{p_n}{\rho^2} \\
&= \frac{1}{\rho^2} \cdot (p_2 + 2p_3 + 3p_4+ \cdots) \\
&= \frac{1}{\rho^2} \cdot (L - (1-p_0)) \\
&= \frac{1}{\rho^2} \cdot (\frac{\rho}{1 - \rho} - (1-(1 - \rho))) \\
&= \frac{1}{1 - \rho}\end{split}$$

## Waiting Time Distribution

令 $W_q(t)$ 為 Waiting Time Distribution。

time($t$) dependent 的 waiting queue size 推導，會用到 [Erlang distribution](https://en.wikipedia.org/wiki/Erlang_distribution)。

$W_q(t)$和 $W_q$不同的地方在於，$W_q$ 是 system 在 steady state 的 average 統計數字，和特定時間點($t$)沒有關係。

因為 $W_q(t)$ 和時間有關，也就是和 customer 如何被服務有關，所以導出來的結果是 discipline-dependent 的，也就是說今天是 FCFS 或者 LCFS，結果可能會不一樣，但是， M/M/1 的其他 average measurement 例如 $L, W,...$等等都是 discipline-independent，因為這些變量的推導過程都沒有用到特定 discipline 的假設，所以適用於任何 $M/M/1$。

:::info
Erlang distribution 的 probability density function為
$$f(x;k, \lambda) = \frac{\lambda^k \cdot x^{k-1} \cdot e^{-\lambda x}}{(k-1)!}$$ 用來表示 k 個獨立的 exponential r.v.(with mean $\frac{1}{\lambda}$) 的集合在一起的機率分布。

常見的應用有: 一個Poisson Process中 k 個arrival 的waiting time（做積分），以及 probability of packet loss or delay, according to various assumptions made about whether blocked calls are aborted (Erlang B formula) or queued until served (Erlang C formula). The Erlang-B and C formulae are still in everyday use for traffic modeling for applications such as the design of call centers.

Erlang-B 會在 [Erlang's Loss Formula(M/M/c/c) & M/M/無限大](/B9Rgdk_1SIeylYy-iHBJUw) 中介紹， Erlang-C 則會在 [M/M/c](/AqYQ-LLURnSRMRIS31N4GA) 中介紹。
:::

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

:::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}$$
:::

推導的一些細節與技巧：

1. 因為system service rate 是 $\mu$，且是一個exponential r.v.，而每個人被服務的時間都是 exponentially distributed，且互相獨立，所以 $n$ 個人在 $t$ 時間內被服務完畢的機率可以用 Erlang 來描述
2. 在滿足收斂條件的情況下，積分和sigma可以互換
3. 積分的對象是[exponential r.v.](https://en.wikipedia.org/wiki/Exponential_distribution)的pdf(with mean $\frac{1-\rho}{\mu}$)時可將整串積分用 exponential r.v. 的 CDF 表示

### 推導

$$\begin{split} W_q(t) &= Pr(T_q \le t) \\
&= W_q(0) + \sum_{n=1}^{\infty} Pr(n個customer在t時間內被服務完|抵達的customer發現系統裡已經有n個customer) \cdot p_n \\
&= W_q(0) + \sum_{n=1}^{\infty} \frac{Pr(n個customer在t時間內被服務完 \cap 系統有n個customer)}{p_n} \cdot p_n \\
&= W_q(0) + \sum_{n=1}^{\infty} Pr(n個customer在t時間內被服完 \cap 系統有n個customer) \\
&= W_q(0) + \sum_{n=1}^{\infty} p_n \cdot Pr(n個customer在t時間內被服務完)\\
&= (1-\rho) + \sum_{n=1}^{\infty} p_0\rho^n \cdot \int_0^{t} \frac{\mu^n \cdot x^{n-1}\cdot e^{-\mu x}}{(n-1)!}dx \\
&= (1-\rho) + \sum_{n=1}^{\infty} (1-\rho)\rho^n \cdot \int_0^{t} \frac{\mu^n \cdot x^{n-1}\cdot e^{-\mu x}}{(n-1)!}dx \\
&= (1-\rho) + \int_{x=0}^{t} (1-\rho)\rho^n \cdot \sum_{n=1}^{\infty} \frac{\mu^n \cdot x^{n-1}\cdot e^{-\mu x}}{(n-1)!}dx \\
&= (1-\rho) + \rho \int_{x=0}^{t} (1-\rho)\mu \cdot e^{-\mu x} \sum_{n=1}^{\infty} \frac{(\mu \rho x)^{n-1}}{(n-1)!}dx \\
&= (1-\rho) + \rho \int_{x=0}^{t} (1-\rho)\mu \cdot e^{-\mu x} e^{\mu \rho x}dx \\
&= (1-\rho) + \rho \int_{x=0}^{t} (1-\rho)\mu \cdot e^{-(1-\rho)\mu x}dx \\
&= (1- \rho) + \rho(1 - e^{-(1-\rho)\mu t}) \\
&= 1- \rho e^{-(\mu - \lambda) t}, (t \ge 0) \end{split}$$

求出 $W_q(t)$ 後，即可對 $T_q$ 求期望值：

$$\begin{split} W_q &= \int_0^{\infty} [1 - W_q(t)] dt \\
&= \int_0^{\infty} \rho e^{-(\mu - \lambda) t} dt \\
&= \frac{\rho}{\mu - \lambda} \\
&= \frac{\lambda}{\mu (\mu - \lambda)}\end{split}$$

此結果和用 Little's Formulas 所推導出來的結果是一樣的，因為是同一個物理系統，只是觀察的角度不一樣。


## Busy Period Analysis

詳見 [Busy-Period Analysis: Take M/M/1 as an Example](/1CiLXdwCS_uqCVx-WQqXmw)

## Comparison between two different $M/M/1$ Queueing System


Arrval $\lambda '$ in both system are equal to $k \lambda$.

### System 1

arrival split into $k\ M/M/1$ queue, each with $\lambda$, and service rate $\mu$.

in each M/M/1 queue:

$$L = \frac{\rho}{1 - \rho}, W = \frac{1}{\mu - \lambda}$$

at system level:

$$L_1 = \frac{k\rho}{1 - \rho}, W_1 = \frac{1}{\mu - \lambda}$$

### System 2

one M/M/1 queue, service rate is $k \mu$.

$$\rho_2 = \frac{k\lambda}{k\mu} = \rho$$

$$L_2 = \frac{\rho}{1 - \rho}, W_2 = \frac{1}{k(\mu - \lambda)} \lt W_1$$

$\Rightarrow$ System 2 is a faster solution, system 1 has more diversity, more robust, but slower.

## Output Process of MM1 queue

The departure rate from a **stable** $M/M/1$ queue is $\lambda$.（Flow conservation law）

直觀來想，In the long term 一定會和 arrival rate 一樣等於 $\lambda$，因為如果比 $\lambda$ 大，那麼會供不應求（arrival 不夠快），如果比 $\lambda$ 小，代表出去的比進來的少，那麼 queue 長期來說會爆掉（not stable）。

It can be shown（via [Time Reversibility - BURKE'S THEOREM](/l9D_-oTqTvq_QYmVXBn_Fw)）that the output process of a stable $M/M/1$ in a Poisson Process。