第三章 時延分析(二)-new

1、第三章 網(wǎng)絡時延分析趙永祥2006/11/16復習:Poisson過程定義 Poisson過程的三種互相等價定義 在很小的時間間隔內(nèi)只發(fā)生一件事情，概率為t。該事件的發(fā)生與t以外發(fā)生的事件無關 不同時間區(qū)間內(nèi)發(fā)生事件的次數(shù)互相獨立；在有限時間間隔t內(nèi)發(fā)生n個事件的概率為 事件發(fā)生的間隔互相獨立，且都服從參數(shù)為的負指數(shù)分布數(shù)學知識：Poisson過程性質給定時間區(qū)間(0,t)發(fā)生n個事件，則這n個時間在(0,t)獨立、均勻分布 產(chǎn)生Poisson過程的一個方法：首先根據(jù)計數(shù)過程產(chǎn)生(0,t)發(fā)生的事件次數(shù)N 在(0,t)產(chǎn)生N個均勻分布的隨機變量Poisson過程的疊加：Poisson過程的疊加

2、仍然是Poisson過程Poisson過程分裂Poisson過程的隨機分裂仍然是Poisson過程數(shù)學知識： Poisson過程性質 等車悖論 車之間的間隔10分鐘，負指數(shù)分布 顧客隨機到達路邊打車 等到下一輛車的平均等車時間？根據(jù)負指數(shù)的無記憶性，等車時間是負指數(shù)分布，平均時間10分鐘為什么不是5分鐘？等車人觀察到時間區(qū)間平均長度為20分鐘，出錯？數(shù)學知識： Poisson過程性質 原因在于：顧客隨機到達，以更大的概率落在區(qū)間長度更大的時間段內(nèi) 平均等車時間的推導Xi:車之間的時間間隔數(shù)學知識： Markov鏈 設狀態(tài)發(fā)生變化的時間為：t1,t2,t3,tn 時刻tn的狀態(tài)為xn Marko

3、v鏈有如下特點 給定當前時刻的狀態(tài)，未來的演變與過去無關。 如果轉移概率與時間n無關，則稱齊次Markov鏈|,.,|111111nnnnnnnnixixPixixixP數(shù)學知識： Markov鏈 一步轉移概率|1iXjXPPnnij210121110020100iiiPPPPPPPPPP 一步轉移概率矩陣數(shù)學知識： Markov鏈 平穩(wěn)概率 如果存在Pj,使得 Pj,定義為穩(wěn)態(tài)概率 穩(wěn)態(tài)概率也可以表示為從任意初始態(tài)出發(fā)最終轉入狀態(tài)i的概率 穩(wěn)態(tài)概率也可以表示為系統(tǒng)訪問狀態(tài)i的頻率1 , 00jPppiijij數(shù)學知識： Markov鏈 全局平衡方程式：從狀態(tài)i轉移出去的頻率等于轉移進狀態(tài)i的

4、頻率,.1 , 00jPppiijij10ijiP,.1 , 000jPpPpiijiijij全局平衡方程式物理意義01n+1n21111201)(PPP 全局平衡方程式：從狀態(tài)i轉移出去的頻率等于轉移進狀態(tài)i的頻率 寫出狀態(tài)0的全局方程式3.3 節(jié)：The M/M/1 Queue 到達過程是參數(shù)為的 Poisson 過程 服務時間獨立同分布：參數(shù)為 的負指數(shù)分布 服務時間和到達時間間隔互相獨立 一個服務器 無限等待空間 N(t): t時刻系統(tǒng)內(nèi)的顧客數(shù)目問題難點 到達過程是隨機過程，時多時少. 服務時間隨機變量，時快時慢。 結果，隊長也就時多時少 顧客等待時間也就時多時少排隊系統(tǒng)狀態(tài) 描述排

5、隊系統(tǒng)有三個變量：t時刻系統(tǒng)里的顧客數(shù)目N(t)，正在服務的顧客剩余服務時間，剩余到達時間 由于負指數(shù)的無記憶性，剩余到達時間、剩余服務時間的分布與原來相同。 系統(tǒng)的狀態(tài)只由N(t)決定. 系統(tǒng)未來的變化只與現(xiàn)在狀態(tài)有關,與隊長演變的歷史無關. M/M型排隊系統(tǒng)的隊長具有Markov性.因此我們可以采用Markov隨機過程的分析手段.分析步驟 寫轉移概率 畫狀態(tài)轉移圖 求平穩(wěn)概率M/M/1 Queue: Discrete-Time Approach 考察離散時間點0, , 2, (任意小) 研究離散時間點過程Nk = N(k)lim ( )lim ktkP N tnP Nn轉移概率計算ijpi

6、jitokijpekkijktPijipijitojkipketkjkiktPijipjitojetjtpjitottetptNttNPtpiiktiitkiitjtij1, 0)()()1 ()2(1, 01, 0)()(!)()2(1, 01, 0)(!)()(1, 0)()()0)(1)()(11,個到達個，個顧客到達內(nèi)服務完服務完個，個顧客服務完內(nèi)到達個顧客內(nèi)到達內(nèi)到達一個顧客轉移概率計算 i=0，j=1)()()0)(1)(tottetptNttNPt內(nèi)到達一個顧客 i=0，j1)(!)()(tojetjtptj個顧客內(nèi)到達轉移概率計算 i0，j=i+1)()()1 ()2(toki

7、jpekkijktPkt個到達個，個顧客到達內(nèi)服務完 i0，ji+1)()()21()(1,tottoetekkktPtPtpttii個顧客個顧客，服務完內(nèi)到開）受服務的顧客還沒有離內(nèi)到一個顧客而正在接轉移概率計算 i0，j=i-1)()()1 ()2(tokijpekkijktPkt個到達個，個顧客到達內(nèi)服務完 i0，ji-1)(1(!)()1 () 11()(1,totkPkteekkktPtPtpkttii個顧客）服務完個顧客個顧客，服務完內(nèi)到接受服務的顧客離開）內(nèi)沒有顧客到達而正在轉移概率計算)(1!)()1)(1 (!)()(1 (,()(tottkPketttkPketetkktP

8、tPtptktktuii個顧客離開）（有個顧客離開）（有個顧客離開）個顧客到達，有內(nèi)有（也沒有顧客離開）內(nèi)沒有顧客到達M/M/1 Queue: Discrete-Time Approach 離散時間生滅過程 0:Done!110( )( )( )( )( )( )nnnnn 00000( )limlimlim( )nnnnpp 01n+1n21111性能分析（一） 平穩(wěn)概率分布 平均隊長00011111, if 1nnnnppp (1),0,1,.nnpn10002(1)(1)1(1)(1)1nnnnnnNnpnnN 性能分析（二） 平均滯留時間 平均等待時間和平均等待顧客數(shù)目 對長超過N的概

9、率11NT1 and 12WNTWQ問題：如果是后到先服務，概率是什么？啟發(fā) =/: 利用率 服務器處于工作的狀態(tài)概率 =1-p0: 對任何 M/G/1 排隊系統(tǒng)成立 系統(tǒng)穩(wěn)定的條件: 1 達到速率應該小于服務速率隊長增加非線性例子1 路由器A每秒平均發(fā)送8個分組到路由器B,分組間隔服從負指數(shù)分布,分組長度服從均值為400字節(jié)的負指數(shù)分布.路由器A,B之間的鏈路速率為64kbit每秒.問: 路由器A的緩存里平均有多少分組等待發(fā)送? 路由器A的緩存里分組大于10的概率? 解: := 8 packets/s, = 64 kbit/s/(4008 bit/packet) = 20 packets/s

10、 ) , =/ = 8/20 = 0.4 EN = 0.4/(1 0.4) = 0.67. 緩存里分組大于10的概率=0.410 = 104.例子2/m/m/11/1/NNTW /11/( /)/NNNmTmTmmWmWmm M/M/1 :到達速率和服務速率同時降低 m 倍 利用率保持不變 平穩(wěn)分布不變，平均顧客數(shù)目不變 低速系統(tǒng)的時延增加 m 倍 隊列里面的平均顧客數(shù)目不變，但是第一個系統(tǒng)里的顧客移動更快教材例3.5 某校一部傳真機為2萬人服務。每個傳真需要的時間為負指數(shù)分布，平均傳輸時間3分鐘，并假定每個人傳真的可能性相同。如果希望平均排隊的隊長不大于5人，試問平均每個人平均間隔多少天才可

11、以發(fā)送一份傳真？概率知識復習 R階愛爾蘭分布的概率密度 平均值 ，方差 ，方差系數(shù) 設x1,x2.,xr服從參數(shù)為 負指數(shù)分布，這些隨機變量的和服從r階愛爾蘭分布 方差系數(shù)小于1，當N趨向于無窮大，則接近定長分布0)!1()()(1terttftrr2rr12均值方差等待時間概率分布（一） 假定先到先服務 假定某個顧客在時刻 到達隊列時發(fā)現(xiàn)系統(tǒng)里有N個顧客，則該顧客需要等到這N個顧客全部離開系統(tǒng)才能開始接受服務。 每個顧客的服務時間是一個負指數(shù)分布，則N個顧客全部離開需要的時間是一個N階愛爾蘭分布xykttdyekykNxWP01)!1()(0limt等待時間概率分布（二） 設W(x)為等待時

12、間分布函數(shù)，則 根據(jù)PASTA定理，到達時刻看見的隊列長度等于任意時刻看見的隊列長度)0()(lim1)0()0()()(1kNxWPkNPxWPWPxWPxWttkt等待時間概率分布（三） 因此有xxyxkykykxkkeedyekydyekyxW)1(0)1(0111011)1 (1)!1()()1 (1)!1()()1 (1)(這是什么分布？幾點說明 對于M/M/1排隊系統(tǒng),我們解出隊長分布為 求解過程中沒有要求調(diào)度規(guī)則,該隊長分布適用于FIFO,LIFO 同樣,平均滯留時間也與調(diào)度規(guī)則無關 但是,滯留時間、等待時間的分布與調(diào)度規(guī)則有關 在M/M/1 FIFO排隊系統(tǒng)里，隊長分布只與利用

13、率有關，與服務時間無關M/M/* 排隊系統(tǒng) Poisson到達過程 到達間隔: iid, exponential 服務時間: iid, exponential 服務時間和到達間隔:獨立 N(t): t 時刻系統(tǒng)里顧客數(shù)目(狀態(tài))N(t): t 0是一個連續(xù)時間Markov過程轉移速率取決于系統(tǒng)特征PASTA 定理成立M/M/c/c Queue: c個服務器的損失系統(tǒng) C個服務器, 沒有等待空間 新到的顧客發(fā)現(xiàn)所有服務器忙,則損失 平穩(wěn)分布: 阻塞概率(PASTA): 只與/的比值有關，與、本身的值無關結果對M/G/c/c queue 有效01c22c10( /)( /),0,1,.,!nkcn

14、kpncnk 10( /)( /)!ckcckpck 定義/=aM/M/c/c Queues (proof) 局部平衡方程式: 歸一化:11200()(1)(1)( /),0,1,.!nnnnnnnnppppppnnnnnppnn 100( /), for M/M/c/c!kckpk 01c22cM/M/c/c Queues Erlang-B公式的疊代算法01( )1( )( )1( )sssE aaE aEasE a 10(/)(/)!ckcckpck 定義/=aM/M/c/c QueuesM/M/c/c QueuesM/M/c/c QueuesM/M/1/K Queue 有限等待空間 系統(tǒng)

15、最多有 K個顧客 一個顧客到達時，發(fā)現(xiàn)系統(tǒng)里已經(jīng)有 K個顧客，則該顧客被丟棄 平穩(wěn)分布 平穩(wěn)條件: 總是穩(wěn)定即使1 丟失概率 利用 PASTA 定理:01KK-12001,1,2,.,11nnKppnKp1(1)loss ( )1KKPP N tKM/M/1/K Queue (proof)與 M/M/1 類似:歸一化:01KK-121000101111111 1KKKnnnnKpppp 0,1,2,.,nnppnKM/M/s Queue到達過程為參數(shù)為 的Poisson過程服務時間為參數(shù)為 的負指數(shù)分布s個服務器到達顧客發(fā)現(xiàn)系統(tǒng)里有n個顧客 n s:找一個空閑服務器開始接受服務 n s:如果所

16、有服務器空閑，進入緩存等待生滅過程,1,nnnssns01s+1s2s2M/M/s Queue01s+1s2s2s 詳細的平衡方程 歸一化10000001()1:,(1)!1 :!nnnnn csn snssnncsnspppppnnnnnsssnspppppssssss 11110010()()()()111!1ksksssk snnkk skssssppksks M/M/s Queue 排隊的概率 到達的顧客發(fā)現(xiàn)所有的服務器都在工作 Erlang-C 公式:用于電話和電路交換 呼叫以速率到達; 呼叫持續(xù)時間是參數(shù)為 1/的負指數(shù)分布 s條中繼線 如果呼叫發(fā)現(xiàn)所有 s 個電路都忙,則持續(xù)呼叫直到有一個空閑鏈路 “在隊列中等待” M/M/s/s Queue: s個服務器的損失系統(tǒng) 如果呼叫發(fā)現(xiàn)所有 s 個電路都忙,該呼叫被損失 Erlang-B 公式: 話務量工程中普遍使用00()()1(0)queueing! 1ssn snn sn sssMPpppssM/M/s Queue 平均等待顧客數(shù) 系統(tǒng)里沒有接受服務的顧客 平均等待時間 (排隊時間) 系統(tǒng)里滯留時間 (排隊時間 + 服務時間) 系統(tǒng)里平均顧客數(shù)目0022()()()()!(1)(0)(1)(0)(1)1ssn sqnn sn sssLns ppnspssMM/(0)(0)1