[Queueing theory]M/M/1 Model

在排隊理論中，M/M/1是一種基本的模型，可以用來模擬系統(Queue+Processor)的運作。其中個別代表的意思是：

1. M = Exponential Arrival Pattern
2. M = Exponential Service Pattern
3. 1 = One Server

因此一般來說，這個系統有下列的幾個特性：

• Arrival Rate為Poisson分布，參數為λ
• Service Time是Exponential分布，參數為μ
• 只有一個Server做服務
• 有無限大的Waiting Queue
• 不會有Overflow的問題
• 先到的先處理
• 不做Request Scheduling
• 在狀態的轉換上，皆遵守Exponential分布，
• 不會有自己到自己的狀況
• 不會有到達A State後，立刻跳到B State的狀況

針對一個系統來說：

• 事件的Arrival Rate(Request到達的機率)為λ
• 事件的Departure Rate(Request離開的機率)為μ
• ρ = λ/μ

因此，多個系統串聯的樣子如下：

在這個系統中，可以根據Arrival Rate和Departure Rate求得相關的系統狀況：

• 系統的平均Request數：
• 一個單位時間內，可完成的Request數：
• 在系統內平均「等待」的Request數：
• 即代表在系統的Queue內的Request數
• 一個Request平均在系統內的時間(Waiting + 接受Servive)：
• 一個Request平均在系統內等待的時間(Waiting)：

在M/M/1之中，有些特性使得在分析模擬時更方便，同時也是決定一個系統，是否使用M/M/1的架構來分析：

• Poisson Arrival Sees Time Average(Pasta)
  一般分析系統的時候，都是站在系統的觀點，觀察是否有Request進來，是否完成了這個Request。不過有時可以站在Request的觀點，看看甚麼時候會進去系統，且甚麼時候可以出來。
• M/M/1系統的Delay也是Exponential distribution
• M/M/1 Model的Departure Process也是屬於Poisson Process，搭配上其Arrival Rate也是Poisson Process，使得可以將多個M/M/1系統做串聯評估，如下圖：
  
• Time Reversibility(可逆時間)
  這個是Markov Chains的特性之一。在M/M/1系統中，時間往正向來看(0～t)與反向來看(t～0)，其呈現的分布皆為Poisson distribution，不過正向看是Arrival process，反向看則是Departure process。