# Busy-Period Analysis: Take M/M/1 as an Example


## 名詞定義

* idle period: 從系統**離開**busy state到下一次系統**進入**busy state為止

* busy period: 從系統**離開**idle state到下一次系統**進入**idle state為止

* busy cycle: 從系統**進入**busy state 到下一次系統再次**進入** busy state

## 分析

我們關注的分別是上述三個定義的period 其長度的期望值，即：$E(T_{idle}), E(T_{bp}), E(T_{bc})$。

### idle period

idle period 的長度期望值可由 Poisson process 兩個 arrival 中間的 waiting time 為 exponentially distributed 這個性質就可以推導出來

$$E(T_{idle}) = \frac{1}{\lambda}$$

### busy period

首先觀察到一個重要insight，就是每一段 busy period 中，第一個進入 system 的 customer 他所看到的系統是一個 empty system(他是第一個，他前面沒有人在等待或被服務)，而根據 [PASTA property](https://zhuanlan.zhihu.com/p/95170684)，**任選一個**customer，這個 customer 觀察到一個 empty system(system population = 0)的機率為

$$\frac{1}{E(N_{bp})}$$

其中 $N_{bp}$ 為一個 random variable，代表在一段busy period當中，系統所服務的總人數。

而我們知道，**第一個**進入 system 的 customer 看到 empty system的機率是

$$p_0 = 1 - \rho$$

因此

$$p_0 = 1 - \rho = \frac{1}{E(N_{bp})} \therefore E(N_{bp}) = \frac{1}{1 - \rho}$$

而 busy period 的平均長度，就可以用平均人數（$E(N_{bp})$）乘上平均服務一個顧客所需要的時間（mean service time, 即 $\frac{1}{\mu}$）求出：

$$E(T_{bp}) = \frac{1}{\mu} \cdot E(N_{bp}) = \frac{1}{\mu (1 - \rho)}$$

### busy cycle

有了 idle period 和 busy period，根據定義，即可推導出

$$\begin{aligned} E(T_{bc}) &= E(T_{idle}) + E(T_{bp}) \newline
&= \frac{1}{\mu(1 - \rho)} + \frac{1}{\lambda} \newline
&= \frac{1}{\mu - \lambda} + \frac{1}{\lambda} \end{aligned}$$

最後驗算 idle period 佔 busy cycle的比例：

$$\frac{\frac{1}{\lambda}}{\frac{1}{\mu - \lambda} + \frac{1}{\lambda}} = 1 - \rho = p_0$$

和系統 idle 的機率 $p_0$相等，這符合我們的預期，因為是對同一個物理系統做觀察。

注意以上結論可以用在 $M/G/1$，只要該系統的 mean service time 為 $\frac{1}{\mu}$ 即可，因為我們在推導的過程中並沒有用到 service 的機率分布為 exponentially distributed 這個假設。

同樣的，我們也沒有用到 service discipline 是否為 FCFS，LCFS 等等，所以以上結論對任何 service discipline 都成立。

## Busy Period With Initial Workload

Assume that the first customer in a busy period $n$ with the workload $I$, (i.e. the service time requirement is $I$). Other customers still require $\frac{1}{\mu}$ mean service time.

我們的目標是求出 $E(T_{bp} | I)$，也就是給定初始剩餘工作量（第一位 Customer 還要多久才會被服務完）$I$ 時，整個 busy period 的期望值。


首先，為了方便分析，假設 service discipline is LCFS，我們可得：

$$E(T_{bp} | I) = E(I) + E(N|I) E(T_{bp}, i)$$

其中 $N, E(N|I), E(T_{bp}, i)$ 的意思如下：

當系統還在服務第一個顧客（work load $I$）時，會有新的顧客 arrive，新來顧客數量為一個 random variable 我們定為 $N$。

$E(N|I)$ 代表給定第一個顧客的 wordload 為 $I$，在服務完這個顧客的期間，系統新的 arrival 數量的期望值。

而因為 LCFS，所以每個新來的顧客都會使系統繼續保持忙碌，**產生一個新的 Busy period**，而 $E(T_{bp}, i)$ 代表的就是這些新來的顧客中第 $i$ 個到的顧客所引發（增加）的 busy period（此 busy period 和上面分析的 [$M/M/1$ busy period](https://hackmd.io/@JJLIN/rJXaIVXOF#busy-period) 是一樣的） 的期望值。

我們知道 $M/M/1$ 的 busy period 為

$$ E(T_{bp}, i) = \frac{\frac{1}{\mu}}{1 - \rho}$$

而 $$E(N) = \lambda \cdot E[I]$$

所以

$$\begin{aligned}
E(T_{bp} | I) &= E(I) + E(N)E(T_{bp}, i) \newline
&= E(I) + \lambda E(I) \frac{\frac{1}{\mu}}{1 - \rho} \newline
&= \frac{E(I)}{1 - \rho}
\end{aligned}$$

當 $E(I) = \frac{1}{\mu}$ 時結果就會原本的結果相同

$$E(T_{bp} | I) = \frac{1}{\mu (1 - \rho)}$$