動機
補完當年的queuing thoery
一言以蔽之，這到底在幹嘛
- 替queue建模
- 用random variable說話(設計每個queue的部分)
- 其實queuing thoery應該要另外開一堂專門介紹怎麼操作random variable才對
複習機率
Random variable到底是什麼
高級的random，可以生出對應的output。 可以把Random variable當成疊加態，等到去用時才會確定一個值，所以可以對這個RV算機率、期望值等等性質
連續與離散
連續與離散就是看這個高級的random丟出來的值的range是可數還是不可數
同時連續與離散的RV也有不同的術語
- 連續
- Cumulative Distribution Function
- pdf的積分，可以得到小於等於某個值的機率
- Probability density function
- cdf的微分，就是圖上的那條線 (不是機率!!)
- 因為pdf的output可能超過1
- cdf的微分，就是圖上的那條線 (不是機率!!)
- Cumulative Distribution Function
- 離散
- probability mass function
- 就是機率
- Cumulative Distribution Function
- pmf的總和，可以得到小於等於某個值的機率
- probability mass function
期望數 & 變異數
- 期望數: output與pdf/pmf的加權總合
E(aY+bX) = aE(Y) + bE(X)E(g(X)) = sum(g(x)*pmf_or_pdf(x))- 這個很重要，之後會對X上一堆函數，需要這個才知道發生什麼事
- 如果有獨立的話，
E(X & Y) = E(X) * E(Y)- 這個也很重要
- 變異數: output與期望數的差距平方 (就是懶得算sqrt)
- 標準差: 給變異數上sqrt
conditional probability
就是重新取scope，在Y中X的機率，所以把分母改成Y，分子改成X&Y
P(X | Y) = P(X & Y) / P(Y)
配合獨立，P(X | Y) = P(X)
貝氏: P(X | Y) = P(Y | X) * (P(X) / P(Y))
X與Y的and可以透過條件機率換出來，P(X | Y) * P(Y) = P(X & Y) = P(Y | X) * P(X)
Conditional Independence
就是在這個scope中兩RV是獨立的，但沒這個scope，它們不一定獨立
P(X & Y | Z) = P(X | Z) * P(Y | Z)
Conditional Independence — The Backbone of Bayesian Networks
新Random variable的推導
Poisson Distribution
詳細推導可以看這邊Poisson Distribution — Intuition, Examples, and Derivation
如果想知道
- try n次 時
- 某事件 成功/失敗 的機率
可以用二項式分布，但是
- 我們要知道次數
- 只能看 成功/失敗 的機率 (可以把成功當成事件發生的機率)
然而更多時候我們只知道某一段時間中的事件發生的平均值而已 所以需要把二項式分布改造一下
把事件發生的機率還原成事件發生的平均值 / 總次數
接著把n拉到無限大，當成做很多次實驗
之後處理前面那一坨
所以Poisson Distribution就是n拉到無限大的結果，這樣也讓他有一些使用上的假設
- 每個單位時間的事件發生的機率都是一樣的
- 事件是獨立的
Exponential Distribution
詳細推導可以看這邊Exponential Distribution — Intuition, Derivation, and Applications
現在想要看從一個事件發生後，要多久才會有下一個事件
如果沿用Poisson Distribution就是看分布之間的機率
how?
事件發生後，要多久才會有下一個事件，也就是沒事件的時間有多久，所以把Poisson Distribution帶0
但是Poisson Distribution看的是每個單位時間，但我們需要的是一段時間
一次不夠，可以乘好幾次(獨立)，e^(-λt)
這樣是在t後開始出現下一次事件的機率，in math
P(T > t) = e^(-λt)
注意到這裡的時間默默變成RV了
之後就是用機率的終極定理，機率加總等於1 只要用1去減，就可以得出cdf，之後微分就是pdf
memoryless
P(T > a + b | T > a) = P(T > b)
Poisson Process
process其實就是RV多加一個time的參數，所以公式與exp dist很像，但是可以指定某時間區段中發生k次
怎麼推導新的Random variable
詳細推導可以看這邊Sum of Exponential Random Variables
利用獨立與Marginal distribution (就像是對其中一個RV做微分)
下面是兩個exp dist相加的cdf
之後就可以求pdf
這就是Erlang distribution
queuing model
怎麼叫queue
queue長這樣
有這些元素 (會給的與要算的)
n是數量，分成在queue與在server w是waiting time s是service time r是residual time (sojourn time, response time)，在整個系統中的逗留時間 λ(速度) µ是service的rate(速度)
把queue的特性寫下來
接下去?
做下面3件事
- 對每個部位用不同的Random variable去描述
- 把queue的東西換一換
- 組合1與2
之後看怎麼把他們組合在一起
通常有兩個觀察者
- global (time)
- user
Random variable有自己的特性，每個queue model也有自己的特性 不要搞混，不論何時都要想到現在探討的東西與queue之間的意義
classic queue model
適用於所有queue的law G/G/m
- Stability Condition:
λ < m*µ - Little’s law:
n_queue = λ * 平均waiting_timen = λ * 平均response_time
m/m/1
- Poisson arrivals (λ)
- Exponential service times (µ)
- 1 server
- 無限buffer
- FIFO
在這個時候system有多少人
從N(t) → N(t + ∆t)會有3種case
- 1 arrival
- λ∆t
- 1 service
- µ∆t
- no arrival, no service
- 1 − (λ + µ)∆t
in math
Steady-state analysis: 如果把t設成無限大(微掉t)?
把Chapman Kolmogorov equation調成微掉t
解偏微分 (列遞迴加總等於1)
stable
λ < m*µ m帶1
所以λ/µ(這邊叫ρ, traffic intensity or load)要小於1
一些元素
Markov Chains
Discrete-time Markov Chains
Markov Chains的重點是只依據目前的狀態轉到下一個狀態
寫成matrix
在這個時候system有多少人
兩個版本，一個算式版，一個matrix版
Steady-state analysis : 把n去掉
先是算式版
把上螢光的部分丟到左邊去
另一個matrix版
總input == 總output
ergodicity: a unique positive steady-state distribution
ergodicity 中文叫遍歷性，不管系統的初始狀態如何，在經歷了一段時間以後，系統就會處於統計平衡狀態
有三個條件
irreducible: From any state, it is possible to get to any state
- 整個圖是個SC，不管從哪邊開始，都可以走到graph的任意一點
- 沒有的話
- lose positivity, and possibly uniqueness, of the steady-state distribution
positive recurrent: The expected return time to any state is finite
- 應該叫deterministic
- graoh的node的量是有限的
- 沒有負環
- 沒有的話
- 這樣有些state無法到達穩定 (就是unstable)
- 應該叫deterministic
Aperiodicity: There is no T ≥ 2 such that paths from a state to itself can only take multiples of T steps
- 可以把no T ≥ 2換成T < 2，也就是最多一步
- 從自己到自己最多只有1步
- 如果有period在，這樣在算這一點的機率時
- 在自己的點，可以產生無限多條從自己開始的path，這樣就不用算了
- 沒有的話
- 這樣在算state時會看到
- P_ii * P_ii的詭異畫面
- 這樣在算state時會看到
- 可以把no T ≥ 2換成T < 2，也就是最多一步
Continuous-time Markov Chains
定義
大概長這樣
同樣的事件轉移機率，同樣的從system中i人，變成j人
不同的是現在是看arrival與service done(departure)誰先發生
寫成matrix
這裡定義了新東西: Transition rates
為了符合當初的機率加總等於1，所以把自己到自己設成-λ
在這個時候，system在什麼狀態
Steady-state analysis : 把t去掉
總input == 總output
特化的例子: Birth-death processes
只有兩個方向，往前或往後
Local balance == global balance equations
Special matrix: Triangular system
Stationary distribution
例子: M/M/1 queue with balking
看到有人可能client就直接走人
Stationary distribution
例子: M/M/1/K
Stationary distribution
Loss probability & Blocking probability & Ergodic
- Blocking probability: 是在t時刻整個system已經滿了
- 剛好等於整個system處於滿的時間總和對上觀察區間的比值
- 剛好等於整個system處於滿的時間總和對上觀察區間的比值
- Loss probability: 是在client到system時整個system已經滿了
之後有一個特性是描述這兩個可以是等於的!!
- Ergodic theorem
- 遍歷性
- 表現出來會是: 從時間上觀察，與從user的角度觀察，結果是一樣的
- 時間均值等於空間均值
- 例如要得出一個城市A、B兩座公園哪一個更受歡迎，有兩種辦法
- 第一種辦法是在一定的時間段考察兩個公園的人數，人數多的為更受歡迎公園
- 第二種辦法，隨機選擇一名市民，跟蹤足夠長的時間來統計他去兩個公園的次數，去得多的為更受歡迎公園
- 表現出來會是: 從時間上觀察，與從user的角度觀察，結果是一樣的
- 遍歷性
因為現在client是Poisson process，所以可以用Poisson Arrivals See Time Averages，其實就是遍歷性
這樣就可以用前面的Stationary distribution直接求Loss probability
Multi-server systems
M/M/C/C: Pure-Loss System
長這樣
user不會retry
狀態圖
同時開C台server，所以service的RV是Exp(k*µ)，k是看現在有多少台正在跑
Steady-State Distribution
Blocking Probability a.k.a Erlang-B
Steady-State Distribution帶C 與 PASTA
M/M/C/∞: Waiting System
長這樣
現在有queue了!!
Stability: ρ < C
狀態圖
Steady-State Distribution
waiting probability a.k.a Erlang-C
Steady-State Distribution帶C 與 PASTA
一些元素
Steady-State Distribution 與 little law導平均有多少人在system
之後，把service time與waiting time相加就是residual time
注意這裡的service time只有一台server
multi-cpu 與 multi-core
