[Queueing theory]Birth-Death process(出生-死亡過程)

        這世界上可以分析的系統非常多，從乘客搭車、商店排隊、銀行辦事、工廠產出、流量分析...等等，但是可用的數學模型是有限的，因此在模擬時，為了使複雜度調整到可以處理的程度，因此會針對系統做些簡化。因此，逐漸產生了一些固定的模型供使用，其中Birth-Death process是一個相當著名的例子：

在這個Process中，State的轉換是符合連續時間下的馬可夫鍊(CTMC)，且已知：

• Arrival Rate: Poisson Distribution(l)
• l(k) = 在狀態K時，轉換到狀態k+1的機率
• Departure Rate: Poisson Distribution(m)
• m(k) = 在狀態K時，轉換到狀態K-1的機率
• 極短時機內，最多一人到達
• 每個客人到達時間互相獨立

根據以上，可以畫成以下狀態圖：

在這個系統中，由於沒有限定顧客的來源，因此在任意State下，其Arrival Rate皆相同：

l(k) = l

同理，由於沒有限定系統內的Buffer大小，因此每個客人都會被接受，其Departure Rate為：

m(k) = m

那在這個系統中的穩定態，基於「Flow in = Flow out」：
(Hint：P(0) = 在狀態0的機率)

• 狀態0：mP(1) = lP(0)
• 狀態1：lP(2) + mP(0) = lP(1) + mP(1)
• 狀態2：lP(3) + mP(1) = lP(2) + mP(2)
• ......
• 狀態n：lP(n-1) + mP(n+1) = lP(n) + mP(n)

上述關係式簡化後，會變成：

 P(n) = (l/m)^n * P(0)

P(0) = 1 - (l/m)

[Queueing theory]系統描述與一般性穩定態計算(General Equilibrium Solution)

是說最近在上Queueing Theory，除了概念要多想多模擬才能理解外，
最困擾的是基礎數學功力不夠呀！
果然出來混總是要還的

----------------------------碎碎念結束---------------------------

在一個系統中，不同狀態的轉換都是根據機率決定是否發生，
不過，要將一個系統轉換成數學可以處理的模式，
則需要我們「定義」這個系統，以便符合我們可用的數學模型，

以火車站為例：一個車站內會有很多人來搭火車，
乘客的目的是希望可以搭到車，就以「到車站 -> 等車 -> 上車」這個流程來看。
根據Kendall notation，我們可以定義：

• State(系統狀態)：車站內的人數
• Transition rate(狀態往前的機率)：乘客到車站的機率
• Departure rate(狀態往後的機率)：乘客上車的機率
• Queue Size/Buffer Size(系統內的上限)；車站可以容納等車人數的多寡
• Number of parallel server(同時有多少Server提供服務)：一次會有多少車來
• Queueing discipline(提供服務的順序)：大家上車的順序

當然，上述是簡化後的例子，實際情況會比描述得更為複雜，

不過這邊做一定程度的簡化，使其可以利用數學工具做一定程度的評估。

在上面的例子中，每個State代表車站內的人數，對於要關注這個系統的人來說，

我們感興趣的部分可能會有：

• 這個車站平均有多少人？
• 平均每個乘客要等多久？
• 車站大多數時候會有多少人在等車？
• 要如何調整發車才可以減少等候時間？
• ......

為了要計算這些，我們可以從「在某狀態下的機率」作為起點，

假設在一個穩定的系統中，單一狀態的機率在觀察時間夠長的話，

其機率會固定在一個特定的值，我們稱之為p_k

以上述式子來說，代表「狀態k機率的穩定態，其機率等於在無窮遠的時間下，得到之狀態k的機率」。

而我們假設，進入這個系統的機率是λ；離開這個系統的機率是µ，

以上面的例子(Birth-Death系統)為例，會有以下特性：

• 車站內的人數最小為0，不會有負數
• 
• 
• 所有狀態的機率和為1(表示所有狀況都考慮在內)
• 

而一個系統在穩定態時，系統的Flow in = Flow out，代表該系統進出的機率會是相同的，

這樣系統內的人數才會維持一定。也就是說：

Flow in = Flow out

→ 進入該狀態的機率 = 離開該狀態的機率

→前個狀態下的進入率+下個狀態的離開率 = 現在狀態下的進入率與離開率和

→ 

根據以上特性，我們可以推出在狀態K的機率為：

而狀態0的機率是：

利用這兩個關係式，就可以針對我們定義的系統，計算在不同情境下，在穩定態的機率。

根據這些機率，配合上Little's Law，就可以方便的算出相關的系統表現了！

參考資料：

1. Queueing Systems. Volume 1: Theory
2. Queueing theory -Wiki

[Queueing theory]Kendall notation - Queueing系統的描述方式

針對一個Queueing的系統，其中有許多的參數和特性，為了要有個簡單且明確的表示方法。這邊使用由Kendall提出的表示法：「Kendall notation」

這表示法是由一連串的「/」區分不同的特性，表示法如下：

A/B/X/Y/Z

其中個別代表的意思是：

• A：Arrival Pattern，Request到達系統的分布特性
• B：Service Pattern，Request離開系統的分布特性
• X：Number of parallel server，單一系統同時有幾個Server進行服務
• Y：System Capacity，系統內Buffer的大小
• Z：Queueing discipline，系統處理Request的方式

其中A和B可以有下列幾個類型：

• Exponential Distribution (M)
• Deterministic (D)
• General Distribution (G)
• Erlang type k (k=1,2,...) (Ek)
• Mixture of k expoenetials (Hk)
• Phase type (PH)

而X和Y則是給予數字，代表該系統的Buffer大小和可處理之Service數，

Z的部分則有：

• FCFS：first come, first served，先到先處理
• LCFS：last come, first served，後到先處理
• RSS：random selection for service，隨機取Buffer內的處理
• PR：priority，依優先權處理
• GD：general discipline

一般來說，系統大多是取前面的A/B/X做描述，這時候後面的Y和Z各自代表「系統內的Buffer Size無限大」和「採用FCFS處理」。

參考資料：

Wiki

Queue的標記法notation