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

第三章網(wǎng)絡(luò)時延分析趙永祥2005/3/17TheM/M/1Queue到達(dá)過程是參數(shù)為λ的Poisson過程服務(wù)時間獨立同分布：參數(shù)為μ的負(fù)指數(shù)分布服務(wù)時間和到達(dá)時間間隔互相獨立一個服務(wù)器無限等待空間N(t):t時刻系統(tǒng)內(nèi)的顧客數(shù)目排隊系統(tǒng)狀態(tài)描述排隊系統(tǒng)有三個變量：t時刻系統(tǒng)里的顧客數(shù)目N(t)，正在服務(wù)的顧客剩余服務(wù)時間，剩余到達(dá)時間由于負(fù)指數(shù)的無記憶性，剩余到達(dá)時間、剩余服務(wù)時間的分布與原來相同。系統(tǒng)的狀態(tài)只由N(t)決定.系統(tǒng)未來的變化只與現(xiàn)在狀態(tài)有關(guān),與隊長演變的歷史無關(guān).M/M型排隊系統(tǒng)的隊長具有Markov性.因此我們可以采用Markov隨機(jī)過程的分析手段.分析步驟寫轉(zhuǎn)移概率畫狀態(tài)轉(zhuǎn)移圖求平穩(wěn)概率M/M/1Queue:Discrete-TimeApproach考察離散時間點0,d,2d,…(d任意小)研究離散時間點過程Nk=N(dk)轉(zhuǎn)移概率計算轉(zhuǎn)移概率計算M/M/1Queue:Discrete-TimeApproach離散時間生滅過程d→0:Done!01n+1n2性能分析（一）平穩(wěn)概率分布平均隊長性能分析（二）平均滯留時間平均等待時間和平均等待顧客數(shù)目對長超過N的概率問題：如果是后到先服務(wù)，概率是什么？啟發(fā)ρ=λ/μ:利用率服務(wù)器處于工作的狀態(tài)概率ρ=1-p0:對任何M/G/1排隊系統(tǒng)成立系統(tǒng)穩(wěn)定的條件:ρ<1達(dá)到速率應(yīng)該小于服務(wù)速率隊長增加非線性例子1路由器A每秒平均發(fā)送8個分組到路由器B,分組間隔服從負(fù)指數(shù)分布,分組長度服從均值為400字節(jié)的負(fù)指數(shù)分布.路由器A,B之間的鏈路速率為64kbit每秒.問:路由器A的緩存里平均有多少分組等待發(fā)送?路由器A的緩存里分組數(shù)目>=10的概率?解::λ=8packets/s,μ=64kbit/s/(400×8bit/packet)=20packets/s),ρ=λ/μ=8/20=0.4E[N]=0.4/(1?0.4)=0.67.緩存里分組數(shù)目>=10的概率=0.410=10?4.例子2M/M/1:到達(dá)速率和服務(wù)速率同時降低m倍利用率保持不變?平穩(wěn)分布不變，平均顧客數(shù)目不變低速系統(tǒng)的時延增加m倍隊列里面的平均顧客數(shù)目不變，但是第一個系統(tǒng)里的顧客移動更快概率知識復(fù)習(xí)R階愛爾蘭分布的概率密度平均值，方差，方差系數(shù)設(shè)x1,x2…..,xr服從參數(shù)為負(fù)指數(shù)分布，這些隨機(jī)變量的和服從r階愛爾蘭分布方差系數(shù)小于1，當(dāng)N趨向于無窮大，則接近定長分布等待時間概率分布（一）假定先到先服務(wù)假定某個顧客在時刻到達(dá)隊列時發(fā)現(xiàn)系統(tǒng)里有N個顧客，則該顧客需要等到這N個顧客全部離開系統(tǒng)才能開始接受服務(wù)。每個顧客的服務(wù)時間是一個負(fù)指數(shù)分布，則N個顧客全部離開需要的時間是一個N階愛爾蘭分布等待時間概率分布（二）設(shè)W(x)為等待時間分布函數(shù)，則根據(jù)PASTA定理，到達(dá)時刻看見的隊列長度等于任意時刻看見的隊列長度等待時間概率分布（三）因此有這是什么分布？幾點說明對于M/M/1排隊系統(tǒng),我們解出隊長分布為求解過程中沒有要求調(diào)度規(guī)則,該隊長分布適用于FIFO,LIFO同樣,平均滯留時間也與調(diào)度規(guī)則無關(guān)但是,滯留時間、等待時間的分布與調(diào)度規(guī)則有關(guān)在M/M/1FIFO排隊系統(tǒng)里，隊長分布只與利用率有關(guān)，與服務(wù)時間無關(guān)M/M/*排隊系統(tǒng)Poisson到達(dá)過程到達(dá)間隔:iid,exponential服務(wù)時間:iid,exponential服務(wù)時間和到達(dá)間隔:獨立N(t):t時刻系統(tǒng)里顧客數(shù)目(狀態(tài)){N(t):t≥0}是一個連續(xù)時間Markov過程轉(zhuǎn)移速率取決于系統(tǒng)特征PASTA定理成立M/M/c/cQueue:c個服務(wù)器的損失系統(tǒng)C個服務(wù)器,沒有等待空間新到的顧客發(fā)現(xiàn)所有服務(wù)器忙,則損失平穩(wěn)分布:阻塞概率(PASTA):只與λ/μ的比值有關(guān)，與λ、μ本身的值無關(guān)結(jié)果對M/G/c/cqueue

有效01c2定義λ/μ=aM/M/c/cQueues(proof