# CHAPTER 1 - INTRODUCTION

## What is Queueing Theory used for?

Queueing theory was developed to provide **models** to **predict the behavior of systems** that attempt to provide service for **randomly arising demands**

Most real problems do not correspond exactly to a mathematical model, and increasing attention is being paid to complex computational analysis, approximate solutions, sensitivity analyses, and the like. The development of the practice of queueing theory **must not be restricted by a lack of closed-form solutions**, and problem solvers must be able to **put the developed theory to good use**.

排隊理論（Queueing Theory），是一套用來分析系統效能的數學工具，可以應用在生活中的很多地方，從電腦 CPU 到疫苗注射站都可以，只要系統具有 Input、Ouput、以及負責處理 Input/Output 的中央處理器，都可以被排隊理論來分析。

想像今天你要規劃在台北市的哪些據點設置疫苗注射站，以及每個注射站要配置多少醫護人員，這樣民眾才可以順利打到疫苗，這時後就可以用排隊理論來分析，就可以預估民眾的等待時間，以及注射站的壅塞狀況等等，最後再搭配預算、人力等限制條件，配合最佳化演算法來做出最佳決策。

## Review of Poisson Process

- [A quick recap on Poisson Process & Exponential Distribution](/5a0BMBLqTdaOrjxfoeqdEg)

## Review of Markov Chain

- [Markov Chain](/K5BCWNpnQGii-DjMMuHnCQ)

## Notation

$$A / B / X / Y / Z$$

以疫苗注射站當作例子。
- A: arrival process distribution（民眾抵達的機率分佈）
- B: probability distribution of service time（醫護人員幫民眾注射疫苗的機率分佈）
- X: number of parallel service channel（施打櫃檯的數量，可同時幫多少民眾打疫苗）
- Y: system capacity（注射站最多可以容納的民眾數量）
- Z: service discipline（施打疫苗的順序，例如先到先打）


> Ex: M/D/2 is a queueing system with exponential input, deterministic(constant) service, 2 servers, no limit on system capacity(default), FCFS(default).
>
> Ex: M/M/2/1 is a queueing system with exponential input, exponential service time, 2 servers, system capacity of 1, FCFS(default).

## System Performance

Queueing Theory 是一套分析系統表現的工具，而要描述系統的表現，且比較不同系統的效能，我們必須先定義一些指標。

以下假設這個系統的有 $c$ 個 server，arrival rate = $\lambda$ ，service rate = $\mu$，system capacity = $\infty$ (If the system has finite capacity, define $P_b$ as the probability of a arriving customer being blocked).

- Offered Traffic Load $r$

The amount of work load arrived per unit time.

$\begin{cases}
r = \lambda \cdot \frac{1}{\mu} = \frac{\lambda}{\mu},\ if\ c = \infty\\
r = \lambda \cdot \frac{1-P_b}{\mu} = \frac{\lambda(1-P_b)}{\mu},\ if\ c \neq \infty \\
\end{cases}$

- Traffic Intensity(Server utilization) $\rho$

$\begin{cases}
\rho = r \cdot \frac{1}{c} = \frac{\lambda}{c \mu},\ if\ c = \infty\\
\rho = r \cdot \frac{1}{c} = \frac{\lambda(1-P_b)}{c \mu},\ if\ c \neq \infty \\
\end{cases}$

- System Steady State Stability

$\begin{cases}
\rho > 1: overload \\
\rho < 1: stable \\
\rho = 1: unstable,\ unless\ in\ D/D/c \\
\end{cases}$

Reason for no steady state for traffic intensity equals 1 unless in $D/D/c$ is that the **randomness will prevent the queue from ever emptying out** and allowing the servers to catch up, thus causing the queue to grow without bound.

### Some Examples

$\lambda = 1, \mu = 2$ for systems listed below.

* $M/M/1$

traffic load = server utilization(only 1 server, c = 1) = $\frac{\lambda}{\mu} = \frac{1}{2} = 50\%$

* $M/M/1/1$

先計算 $P_b = \frac{\frac{1}{\mu}}{\frac{1}{\lambda} + \frac{1}{\mu}} = \frac{1}{3}$（server 平均服務一位顧客的時間是 $\frac{1}{\mu}$，而系統沒有在服務顧客（在等待顧客來）的平均時間是 $\frac{1}{\lambda}$。）

carried traffic load = $\frac{\lambda (1-P_b)}{\mu} = \frac{1}{3} =$ server utilization ($c = 1$)

可觀察到 server utilization 和 $P_b$ 相等，這不是巧合而是必然，因為當系統為 busy，即系統在服務顧客的時候（being utilized），就是他無法接受新顧客（system capacity = $1$）的時候（新顧客被block）。

## Little's Formulas

$$L = \lambda \cdot W$$

Little's Formulas describe the relation between **Steady-state mean system size(L)** & **Steady-state average customer waiting time(W).**

If system can reach **steady state**, and there is **no blocking**, then Little's Formulas can be applied to a large variety of **G/G/1 & G/G/c queues**

在下面的證明會看到，這個定理沒有什麼先驗假設，所以 Little's Formulas 的應用範圍很廣，使我們可以很容易的對一個系統（不論是什麼系統）做快速的初步分析。

在開始證明這個定理，搞懂$L, W$ 到底代表什麼意思以前，我們必須先定義一些符號。

* $L$ 是什麼

$N(t)$: #customers in the system at time t

$N_q(t)$: #customers waiting in queue

$N_s(t)$: #customers in service

$\Rightarrow N(t) = N_q(t) + N_s(t)$, at steady state t is arbitrary, so $N = N_q + N_s$

$p_n(t) = Pr(N(t) = n)$, $P_n = Pr(N = n)$ (in steady state)

$L = E[N] = \sum_0^{\infty} np_n$

$L_q = E[N_q] = \sum_{c+1}^{\infty} (n-c)p_n$

* $W$ 是什麼

$T$: total time customer spends in system

$T_q$: total time customer wait in queue

$S$: service time

$\Rightarrow T = T_q + S$

$W = E[T]$: mean waiting time in system

$W_q = E[T_q]$: mean waiting time in queue

$E[T] = E[T_q] + E[S]$

$W = W_q + \frac{1}{\mu}$ (Mean service time)

### 證明 1



consider the system at time $t, t \to \infty$:

$L = E[N] = \sum_0^{\infty} np_n = \frac{1}{t}\int_0^{t} N(t)\ dt = \frac{1}{t} \cdot$ area under the curve

$W = E[T] = \frac{1}{\lambda t}\int_0^{t} N(t)\ dt =\frac{1}{\lambda t}\cdot$ area under the curve

關於 $L$，$L$ 代表的是系統在 $t$ 時的平均人數，所以對 $N(t)$ 做積分再除以總時間長 $t$。而 $W$ 是系統在 $t$ 時每個顧客的平均等待時長，在這裡可把圖橫向分割成長方形，代表每個顧客留在系統內的時間，每個顧客的長方形高都會是 1，如果我們把這些長方形切一切然後上下左右平移，必定可以填滿 area under the curve，最後再除以在 $0$ 到 $t$ 間來到系統的顧客總人數，也就是 $\lambda t$，就會得到顧客平均留在系統內的時間$W$。

由上面兩式可知 $Lt = W\lambda t$，故可證出$L= \lambda W$。

### 證明 2

在這裡提供另一個證明方式，注意 Notation 有些不同（因應不同原文書可能會使用不同的符號），且這樣可以幫助我們了解定理背後的核心概念，而不是死背符號以及公式，讓讀者對於這個定理的了解可以更加深刻。

首先定義：

$N(t)$: number of customers in the system at time t

$\alpha(t)$: number of arrivals during $(0, t)$

$T_i$: the time spent in system by $i_{th}$ customer

$\frac{1}{t} \int_0^t N(x) dx = \frac{1}{t} \sum_{i=1}^{\alpha(t)} T_i = \frac{\alpha(t)}{t} \cdot \frac{\sum_{i=1}^{\alpha(t)}T_i}{\alpha(t)}$
> 積分面積 = 所有小長方形的面積合

taking $t \to \infty$, $\frac{1}{t} \int_0^t N(x) dx \to N, \frac{\alpha(t)}{t} \to \lambda, \frac{\sum_{i=1}^{\alpha(t)}T_i}{\alpha(t)} \to T$

$\Rightarrow N = \lambda T$

注意上面證明沒有用到 FCFS 等 queuing discipline，也就是說 Little's Formulas 可以用在絕大部分的 queue，例外是當這個 queue 為 non-work conserving時，non-work conserving的例子像是工作若被中斷要重頭開始做起，或者系統切換工作時有 context-switch overhead等等，這些都會改變 $N(t)$，也就會改變曲線下面積，使得上面利用面積的證明不成立。

### Some Examples

* M/M/1/${\infty}$/FCFS

首先觀察到：$W = \frac{1}{\mu} + L\frac{1}{\mu} =$ 自己被服務的時間 + 在你前面的人（$L$）被服務的時間，這裡用到 [Poisson process的 PASTA性質](https://zhuanlan.zhihu.com/p/95170684)，也就是一個customer arrive的時候看到的是 system average，也就是會看到有$L = E[N]$排在他前面等著被服務，而這 $L$個人每個人平均被服務的時間都是 $\frac{1}{\mu}$。

使用 Little's Formulas，得 $W = \frac{1}{\mu} + \lambda W\frac{1}{\mu} \Rightarrow W = \frac{\frac{1}{\mu}}{1 - \frac{\lambda}{\mu}} = \frac{1}{\mu - \lambda}$，接著再代一次 Little's Formulas 可得 $L = \lambda W = \frac{\lambda}{\mu - \lambda}$

* M/G/${\infty}$

一間百貨公司，平均每分鐘進來 m 人，人均停留時間為 90分鐘，求百貨公司平均顧客負載量($L$)？

解：給定 $\lambda = m$，$W = 90$，則$L = 90W = 90m$

* M/D/${\infty}$

Assume a 1 Gbps fiber providing throughput at 800 Mbps, suppose packet size is 10000 bits/packet and propagation delay is 100ms, what is the number of packets on this fiber（在fiber上跑的，已經出發但尚未抵達）?

解：$L = \lambda W = (800 \cdot 10^6(\frac{bits}{second}))\cdot 0.1(second) = 8\cdot 10^7(bits) = 8000(packets)$

* Window flow control(in transportation system)

卡車車隊有 16 輛，來回一趟要 20 分鐘，求每小時載貨量?

解：$\lambda = \frac{L}{W} = \frac{16}{\frac{1}{3}} = 48$ (箱貨物/小時)。

* Estimation throughput in a Time sharing system

> $\lambda$ 及為在 B 點的 arrival rate，也就是 job 被送進 CPU 的速度。也可以類比成物流系統，把 Terminal 改成卸貨卡車， CPU 改成卸貨地點，很多工人在卸貨地點幫忙卸貨，類似 time sharing system。

$R$: reflection time (time before generate a job(task), send it to CPU)
$p$: processomg time per task(with single job)

when there are $n$ tasks in the time-sharing system, the maximum processing delay becomes $np$(each only obtain $\frac{1}{n}$ processing capacity, so one has to wait for the other $n-1$ jobs)

Let $T$ be the response time in average, $R+ p \le T \le R + NP$


Since $\frac{N}{T} = \lambda$, and the population $N$ is fixed, then $\lambda$(the task generation rate) satisfies $\frac{N}{R + NP} \lt \lambda \lt \frac{N}{R + P}$, also notice that $\lambda \lt \frac{1}{p}$, since the time require to process a job is $p$, so $\frac{N}{R + NP} \lt \lambda \lt min(\frac{1}{p},\frac{N}{R + P})$，如下圖，可看到中間灰色區域即是 throughput 的範圍。

> 斜直線為 $\frac{N}{R + P}$, 曲線為$\frac{N}{R + NP}$