信息網(wǎng)理論基礎(chǔ)第三章 時(shí)延分析(二)

1、第三章 網(wǎng)絡(luò)時(shí)延分析趙永祥2005/3/17The M/M/1 Queue 到達(dá)過(guò)程是參數(shù)為的 Poisson 過(guò)程 服務(wù)時(shí)間獨(dú)立同分布：參數(shù)為 的負(fù)指數(shù)分布 服務(wù)時(shí)間和到達(dá)時(shí)間間隔互相獨(dú)立 一個(gè)服務(wù)器 無(wú)限等待空間 N(t): t時(shí)刻系統(tǒng)內(nèi)的顧客數(shù)目排隊(duì)系統(tǒng)狀態(tài) 描述排隊(duì)系統(tǒng)有三個(gè)變量：t時(shí)刻系統(tǒng)里的顧客數(shù)目N(t)，正在服務(wù)的顧客剩余服務(wù)時(shí)間，剩余到達(dá)時(shí)間 由于負(fù)指數(shù)的無(wú)記憶性，剩余到達(dá)時(shí)間、剩余服務(wù)時(shí)間的分布與原來(lái)相同。 系統(tǒng)的狀態(tài)只由N(t)決定. 系統(tǒng)未來(lái)的變化只與現(xiàn)在狀態(tài)有關(guān),與隊(duì)長(zhǎng)演變的歷史無(wú)關(guān). M/M型排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)具有Markov性.因此我們可以采用Markov隨機(jī)過(guò)程的分

2、析手段.分析步驟 寫(xiě)轉(zhuǎn)移概率 畫(huà)狀態(tài)轉(zhuǎn)移圖 求平穩(wěn)概率M/M/1 Queue: Discrete-Time Approach 考察離散時(shí)間點(diǎn)0, d, 2d, (d任意小) 研究離散時(shí)間點(diǎn)過(guò)程N(yùn)k = N(dk)lim ( )lim ktkP N tnP Nn轉(zhuǎn)移概率計(jì)算ijpijitokijpekkijktPijipijitojkipketkjkiktPijipjitojetjtpjitottetptNttNPtpiiktiitkiitjtij1, 0)()()1 ()2(1, 01, 0)()(!)()2(1, 01, 0)(!)()(1, 0)()()0)(1)()(11,個(gè)到達(dá)個(gè)，個(gè)顧

3、客到達(dá)內(nèi)服務(wù)完服務(wù)完個(gè)，個(gè)顧客服務(wù)完內(nèi)到達(dá)個(gè)顧客內(nèi)到達(dá)內(nèi)到達(dá)一個(gè)顧客轉(zhuǎn)移概率計(jì)算)()()21()(1,tottoetekkktPtPtpttii個(gè)顧客個(gè)顧客，服務(wù)完內(nèi)到開(kāi)）受服務(wù)的顧客還沒(méi)有離內(nèi)到一個(gè)顧客而正在接)(1(!)()1 () 11()(1,totkPkteekkktPtPtpkttii個(gè)顧客）服務(wù)完個(gè)顧客個(gè)顧客，服務(wù)完內(nèi)到接受服務(wù)的顧客離開(kāi)）內(nèi)沒(méi)有顧客到達(dá)而正在)(1!)()1)(1 (!)()(1 (,()(tottkPketttkPketetkktPtPtptktktuii個(gè)顧客離開(kāi)）（有個(gè)顧客離開(kāi)）（有個(gè)顧客離開(kāi)）個(gè)顧客到達(dá)，有內(nèi)有（也沒(méi)有顧客離開(kāi)）內(nèi)沒(méi)有顧客到達(dá)M/M/1

4、 Queue: Discrete-Time Approach 離散時(shí)間生滅過(guò)程 d0:Done!110( )( )( )( )( )( )nnnnnd dd dd dd dd dd d00000( )limlimlim( )nnnnppdddd dd d01n+1n2dddddddd1dd1dd1dd1d性能分析（一） 平穩(wěn)概率分布 平均隊(duì)長(zhǎng)00011111, if 1nnnnppp (1),0,1,.nnpn10002(1)(1)1(1)(1)1nnnnnnNnpnnN 性能分析（二） 平均滯留時(shí)間 平均等待時(shí)間和平均等待顧客數(shù)目 對(duì)長(zhǎng)超過(guò)N的概率11NT1 and 12WNTWQ問(wèn)題：如果

5、是后到先服務(wù)，概率是什么？啟發(fā) =/: 利用率 服務(wù)器處于工作的狀態(tài)概率 =1-p0: 對(duì)任何 M/G/1 排隊(duì)系統(tǒng)成立 系統(tǒng)穩(wěn)定的條件: =10的概率? 解: := 8 packets/s, = 64 kbit/s/(4008 bit/packet) = 20 packets/s ) , =/ = 8/20 = 0.4 EN = 0.4/(1 0.4) = 0.67. 緩存里分組數(shù)目=10的概率=0.410 = 104.例子2/m/m/11/1/NNTW /11/( /)/NNNmTmTmmWmWmm M/M/1 :到達(dá)速率和服務(wù)速率同時(shí)降低 m 倍 利用率保持不變 平穩(wěn)分布不變，平均顧客數(shù)

6、目不變 低速系統(tǒng)的時(shí)延增加 m 倍 隊(duì)列里面的平均顧客數(shù)目不變，但是第一個(gè)系統(tǒng)里的顧客移動(dòng)更快概率知識(shí)復(fù)習(xí) R階愛(ài)爾蘭分布的概率密度 平均值 ，方差 ，方差系數(shù) 設(shè)x1,x2.,xr服從參數(shù)為 負(fù)指數(shù)分布，這些隨機(jī)變量的和服從r階愛(ài)爾蘭分布 方差系數(shù)小于1，當(dāng)N趨向于無(wú)窮大，則接近定長(zhǎng)分布0)!1()()(1terttftrr2rr12均值方差等待時(shí)間概率分布（一） 假定先到先服務(wù) 假定某個(gè)顧客在時(shí)刻 到達(dá)隊(duì)列時(shí)發(fā)現(xiàn)系統(tǒng)里有N個(gè)顧客，則該顧客需要等到這N個(gè)顧客全部離開(kāi)系統(tǒng)才能開(kāi)始接受服務(wù)。 每個(gè)顧客的服務(wù)時(shí)間是一個(gè)負(fù)指數(shù)分布，則N個(gè)顧客全部離開(kāi)需要的時(shí)間是一個(gè)N階愛(ài)爾蘭分布xykttdyeky

7、kNxWP01)!1()(0limt等待時(shí)間概率分布（二） 設(shè)W(x)為等待時(shí)間分布函數(shù)，則 根據(jù)PASTA定理，到達(dá)時(shí)刻看見(jiàn)的隊(duì)列長(zhǎng)度等于任意時(shí)刻看見(jiàn)的隊(duì)列長(zhǎng)度)0()(lim1)0()0()()(1kNxWPkNPxWPWPxWPxWttkt等待時(shí)間概率分布（三） 因此有xxyxkykykxkkeedyekydyekyxW)1(0)1(0111011)1 (1)!1()()1 (1)!1()()1 (1)(這是什么分布？幾點(diǎn)說(shuō)明 對(duì)于M/M/1排隊(duì)系統(tǒng),我們解出隊(duì)長(zhǎng)分布為 求解過(guò)程中沒(méi)有要求調(diào)度規(guī)則,該隊(duì)長(zhǎng)分布適用于FIFO,LIFO 同樣,平均滯留時(shí)間也與調(diào)度規(guī)則無(wú)關(guān) 但是,滯留時(shí)間、等

8、待時(shí)間的分布與調(diào)度規(guī)則有關(guān) 在M/M/1 FIFO排隊(duì)系統(tǒng)里，隊(duì)長(zhǎng)分布只與利用率有關(guān)，與服務(wù)時(shí)間無(wú)關(guān)M/M/* 排隊(duì)系統(tǒng) Poisson到達(dá)過(guò)程 到達(dá)間隔: iid, exponential 服務(wù)時(shí)間: iid, exponential 服務(wù)時(shí)間和到達(dá)間隔:獨(dú)立 N(t): t 時(shí)刻系統(tǒng)里顧客數(shù)目(狀態(tài))N(t): t 0是一個(gè)連續(xù)時(shí)間Markov過(guò)程轉(zhuǎn)移速率取決于系統(tǒng)特征PASTA 定理成立M/M/c/c Queue: c個(gè)服務(wù)器的損失系統(tǒng) C個(gè)服務(wù)器, 沒(méi)有等待空間 新到的顧客發(fā)現(xiàn)所有服務(wù)器忙,則損失 平穩(wěn)分布: 阻塞概率(PASTA): 只與/的比值有關(guān)，與、本身的值無(wú)關(guān)結(jié)果對(duì)M/G/c/c queue 有效01c22c10( /)( /),0,1,.,!nkcnkpncnk 10( /)( /)!ckcckpck 定義/=aM/M/c/c Queues (proof) 局部平衡方程式: 歸一化:11200()(1)(1)( /),0,1,.!nnnnnnnnppppppnnnnnppnn 1