第三章Erlang拒絕和等待系統(tǒng)ppt課件

1、信息工程學(xué)院信息論教研室信息工程學(xué)院信息論教研室BUPT Information Theory & Technology Education & Research Center 第三章 Erlang回絕和等待系統(tǒng)通訊網(wǎng)實驗室cnl.sie.bupt/ BUPT Information Theory & Technology Education & Research Center 3.1 引見n在本章中將要對不同的交換系統(tǒng)建立起排隊系統(tǒng)模型，并進展性能分析。 n首先，需求定義網(wǎng)中的各種根本目的，交換系統(tǒng)如圖3.1。交換系統(tǒng)s條圖3.1 交換系統(tǒng)BUPT Infor

2、mation Theory & Technology Education & Research Center n定義3.1業(yè)務(wù)量：業(yè)務(wù)量描畫了在一定時間內(nèi)，該s條線路被占用的總時間 。n假設(shè)第r條信道被占用Qr秒，那么s條信道上的業(yè)務(wù)量為：n假設(shè)換一種角度，上述業(yè)務(wù)量Q的計算可以表達為：n其中t0為察看起點,T為察看時長，R(t)為時辰t被占用的信道數(shù)，這是一個取值在0到S之間的隨機變量。(T時長內(nèi)被占用的中繼數(shù)總數(shù))srrQQ1TttdttRQ00)(業(yè)務(wù)量BUPT Information Theory & Technology Education & Res

3、earch Center 呼叫量的單位 erln上述定義的業(yè)務(wù)量與察看時長T親密相關(guān)，下面定義的呼叫量或話務(wù)量與察看時長無關(guān)。呼叫量普通用來近似表達呼叫流的大小。n定義3.2呼叫量 n呼叫量的單位為erl，這是一個無量綱的單位。n實踐上，在圖3.1中，在一段時間T內(nèi)經(jīng)過的呼叫量就是該時段內(nèi)被占用的平均中繼數(shù)。TQ觀察時間業(yè)務(wù)量呼叫量BUPT Information Theory & Technology Education & Research Center n對于從外界到達交換系統(tǒng)的呼叫流有兩種：n一種為無限話源，這種系統(tǒng)被稱為愛爾蘭Erlang系統(tǒng)；n另一種為有限話源，這種

4、系統(tǒng)被稱為恩格謝特Engset系統(tǒng)。Erlang vs. EngsetBUPT Information Theory & Technology Education & Research Center 時間阻塞率 vs. 呼叫阻塞率n如今來思索網(wǎng)的時間阻塞率和呼損，這是兩個重要的性能目的，當(dāng)圖3.1中的s條中繼線全部忙碌時，系統(tǒng)處于阻塞形狀。n系統(tǒng)處于阻塞形狀的時間和察看時間的比例稱為時間阻塞率，即：n定義3.3 時間阻塞率 觀察時間阻塞時間spBUPT Information Theory & Technology Education & Research Ce

5、nter n定義3.4 呼叫阻塞率或呼損 回絕呼叫的次數(shù)占總呼叫次數(shù)的比例定義為呼叫阻塞率。n普通 ，假設(shè)到達的呼叫流為Poisson過程，有 。 n掌握計算部分的呼損的Erlang公式和Engset公式是本章的重要的目的。 總呼叫次數(shù)被拒絕的呼叫次數(shù)cpcspp cspp 呼叫阻塞率BUPT Information Theory & Technology Education & Research Center 數(shù)據(jù)交換系統(tǒng) n下面對數(shù)據(jù)交換系統(tǒng)進展一些闡明。 BUPT Information Theory & Technology Education & Re

6、search Center 數(shù)據(jù)交換系統(tǒng)n在圖3. 2中，有p條入線和q條出線。n在數(shù)據(jù)網(wǎng)絡(luò)中，信息普通被截為變長分組，在每條入線上，有不同的到達率。n分組包在到達交換系統(tǒng)后，根據(jù)路由表完成交換到達相應(yīng)的出口j。n但是由于難以防止的出線沖突，會有不同的入口來的信息包希望同時去同一出線，產(chǎn)生競爭，這些包將在相應(yīng)的出口排成一個隊列，按照次序輪番得到效力。BUPT Information Theory & Technology Education & Research Center 時延n數(shù)據(jù)包在穿越交換機時將閱歷一段延遲，其中包含交換時延，排隊時延和效力時延。n交換時延普通固定且較

7、小n排隊時延可變n效力時延與包長有關(guān)n排隊時延和效力時延是時延中最重要的部分，它們的和稱為系統(tǒng)時間。n對于數(shù)據(jù)網(wǎng)絡(luò)，首先需求分析數(shù)據(jù)包穿越一個交換機的系統(tǒng)時間。BUPT Information Theory & Technology Education & Research Center n對于數(shù)據(jù)網(wǎng)絡(luò)，有不同的任務(wù)方式，包括面向銜接和無銜接兩種主要方式。n將對面向銜接的數(shù)據(jù)網(wǎng)絡(luò)，對其交換系統(tǒng)建立模型，分析其系統(tǒng)時間，進而計算網(wǎng)絡(luò)恣意端對端的時延，然后全網(wǎng)的平均系統(tǒng)時間或平均時延。面向銜接的數(shù)據(jù)網(wǎng)絡(luò)BUPT Information Theory & Technology

8、 Education & Research Center 全網(wǎng)性能分析n網(wǎng)絡(luò)和面向銜接的數(shù)據(jù)網(wǎng)絡(luò)分別運用平均呼損和平均時延作為性能評價的重要目的。n關(guān)于它們的計算可以做如下簡單思索：BUPT Information Theory & Technology Education & Research Center n網(wǎng)絡(luò)用圖 表示， n假設(shè)恣意兩點之間的呼叫量為n它們之間的呼損為： n ),(EVG mEnV| ,|njiaji ,1,njipji ,1,iji jijijija Pa全網(wǎng)平均呼損網(wǎng)全網(wǎng)平均呼損BUPT Information Theory & Te

9、chnology Education & Research Center n假設(shè)恣意兩點之間信息包的到達率為： n它們之間的延遲為： njiji ,1,njiTji ,1,ijijijijijT全網(wǎng)平均延遲數(shù)據(jù)網(wǎng)全網(wǎng)平均延遲BUPT Information Theory & Technology Education & Research Center 3.2 Erlang即時回絕系統(tǒng) BUPT Information Theory & Technology Education & Research Center n如今假設(shè)呼叫流的到來服從Poisson過

10、程，每個呼叫的繼續(xù)時間服從參數(shù)的負(fù)指數(shù)分布。n系統(tǒng)有s條中繼線，假設(shè)沒有空閑的中繼線，就回絕新來的呼叫，并且該呼叫不再進入系統(tǒng)。n在這樣的情況下，該系統(tǒng)的排隊系統(tǒng)模型為)(/ssMM)(/ssMMBUPT Information Theory & Technology Education & Research Center M/M/s(s) 的 形狀轉(zhuǎn)移圖 BUPT Information Theory & Technology Education & Research Center n這樣該生滅過程的到達率和離去率分別如下 :sksk1, 1 , 00sksk

11、kk0., 1BUPT Information Theory & Technology Education & Research Center n根據(jù)生滅過程的穩(wěn)態(tài)分布 規(guī)律：n令n根據(jù)概率歸一性， ，解得：01,2, .1!kkpkspka10skkpsrrrap00!1BUPT Information Theory & Technology Education & Research Center Erlang公式 n穩(wěn)態(tài)分布為： n特別，當(dāng)ks 時， 表達了中繼線全忙的概率，這個概率為系統(tǒng)的時間阻塞率，記為 nErlang B公式., 2 , 1 , 0!/

12、0skrakapsrrkk.,!/),(0arasaasBsrrsspBUPT Information Theory & Technology Education & Research Center n例例3.1 計算計算M/M/排隊系統(tǒng)的平均隊長。排隊系統(tǒng)的平均隊長。n解：解：M/M/為一個虛擬系統(tǒng)，有為一個虛擬系統(tǒng)，有個中繼個中繼線。到達的呼叫流是參數(shù)線。到達的呼叫流是參數(shù)的的Poisson過程，過程，呼叫繼續(xù)時間服從參數(shù)為呼叫繼續(xù)時間服從參數(shù)為的負(fù)指數(shù)分布。的負(fù)指數(shù)分布。n由于有由于有個效力員或中繼線，系一致定有個效力員或中繼線，系一致定有穩(wěn)態(tài)分布，取系統(tǒng)中的呼叫數(shù)為形狀

13、變量，穩(wěn)態(tài)分布，取系統(tǒng)中的呼叫數(shù)為形狀變量，這個排隊系統(tǒng)是一個生滅過程。形狀轉(zhuǎn)移這個排隊系統(tǒng)是一個生滅過程。形狀轉(zhuǎn)移圖如圖圖如圖3.4所示。所示。 例3.1 BUPT Information Theory & Technology Education & Research Center n各形狀的到達率和離去率如下：nn 0,kk1kkk例3.1 形狀轉(zhuǎn)移圖BUPT Information Theory & Technology Education & Research Center n由生滅過程，設(shè) ，那么：n根據(jù)概率歸一性， ，那么n從而穩(wěn)態(tài)分布為n上式中的

14、服從參數(shù)為a的泊松分布，假設(shè)為系統(tǒng)中的呼叫數(shù)，那么其平均隊長EN和方差VarN同為a。n平均隊長為a闡明經(jīng)過的呼叫量為a。a0011!kkkapppkkk01kkp0ape0!kekapakk例3.1 求解過程BUPT Information Theory & Technology Education & Research Center n例3.2 計算圖3.1中的經(jīng)過呼叫量。n解：經(jīng)過的呼叫量是被占用的平均中繼線數(shù)。n思索到穩(wěn)態(tài)分布為：n經(jīng)過的呼叫量：srrkkrakap0!/110(1)!1( ,(1)!)ksskkskskkaB s aakak papak例3.2 M/M

15、/s(s)的經(jīng)過呼叫量BUPT Information Theory & Technology Education & Research Center n結(jié)果的直觀意義，如圖3.5。 na為到達的總呼叫量，a為經(jīng)過的呼叫量，a和a的關(guān)系可以由 來決議。n每條中繼線平均承載的呼叫量為交換系統(tǒng)aa圖3.5經(jīng)過的呼叫量),(1 asBaasas例3.2 結(jié)論BUPT Information Theory & Technology Education & Research Center n根據(jù)Erlang公式計算得， ， n 。n假設(shè)時間阻塞率為0.02，30條中繼線可

16、以承載21.9erl的呼叫量，而10條中繼線可以承載5.08erl的呼叫量。顯然后者承載的呼叫量遠(yuǎn)小于前者的1/3。n在同樣時間阻塞率下，分散的中繼線群承載的總呼叫量小于中繼線集中后承載的呼叫量。n在實際中，將這種集中效應(yīng)稱為大群化效應(yīng) 02. 0)9 .21,30(B02. 0)08. 5 ,10(B例3.3 大群化效應(yīng)BUPT Information Theory & Technology Education & Research Center n例3.3中的兩種情況下，效率是不一樣的。n在同樣的呼損下，小中繼線群效率較低。n效率高的中繼線群對呼叫量的動搖更加敏感習(xí)題3.3

17、線愛爾蘭7154. 030)02. 01 (9 .2130線愛爾蘭4978. 010)02. 01 (08. 510例3.2 大群化效應(yīng)效率BUPT Information Theory & Technology Education & Research Center n在圖3.1的中繼線群中，假設(shè)將中繼線依次編號為1，2，s，并且嚴(yán)厲按順序運用。請計算每條中繼線的經(jīng)過呼叫量。n解：對恣意k(1ks)，根據(jù)中繼線的運用規(guī)那么，在1，2，k這k條中繼線上的溢出呼叫量將由k1，k2，s這些中繼線來承載。例3.4 M/M/S(S)順序運用BUPT Information Theory

18、 & Technology Education & Research Center n1，2，k1這k1條中繼線經(jīng)過的呼叫量為n1，2，k這k條中繼線上經(jīng)過的呼叫量為 n所以，第k條中繼線經(jīng)過的呼叫量 n這樣，第k條中繼線經(jīng)過的呼叫量1(1, )aB ka1( , )aB k a1( , )1(1, )kaaB k aaB ka (1, )( , ),1,(0, )1kaa B kaB k aksBa且例3.4 求解BUPT Information Theory & Technology Education & Research Center 例3.5 主備線即

19、時回絕系統(tǒng)BUPT Information Theory & Technology Education & Research Center 3.3 Erlang等待制系統(tǒng) n假設(shè)呼叫流的到來服從參數(shù)為的Poisson過程n每個呼叫的繼續(xù)時間服從參數(shù)為的負(fù)指數(shù)分布。n系統(tǒng)有s條中繼線n假設(shè)呼叫到來時系統(tǒng)中沒有空閑的中繼線，該呼叫并不被回絕，而是等待。n假設(shè)這個系統(tǒng)的等待位置可以是，那么該系統(tǒng)的模型為M/M/s。 BUPT Information Theory & Technology Education & Research Center 3.3 等待制系統(tǒng)n對于

20、這個系統(tǒng)的分析目的n首先需求計算穩(wěn)態(tài)分布n然后計算一個呼叫到來時需求等待的概率n再次需求了解等待時間的均值、分布等。 BUPT Information Theory & Technology Education & Research Center 等待制系統(tǒng)形狀轉(zhuǎn)移圖 BUPT Information Theory & Technology Education & Research Center n該生滅過程各個形狀的到達率和離去率如下 sksskkkkk1, 2 , 12 , 1 , 0,等待制系統(tǒng)分析 BUPT Information Theory &

21、; Technology Education & Research Center n假設(shè) 為穩(wěn)態(tài)分布， ，那么n根據(jù)概率歸一性，那么 kpa00!0!kkkk ss sapkskpapkss100)(!1ksksskksasakap等待制系統(tǒng)分析-pk BUPT Information Theory & Technology Education & Research Center n在a0。 n思索呼叫到達系統(tǒng)的瞬間，不算該呼叫，系統(tǒng)的形狀分布為 。普通來說， 與 是不同的，但是假設(shè)到達的呼叫流為Poisson過程，那么 100/11!1sksksasakapkkkp,

22、.2 , 1,kpkk等待制系統(tǒng)分析-p0 BUPT Information Theory & Technology Education & Research Center n一個呼叫到來時，當(dāng)系統(tǒng)處于形狀 時，呼叫需求等待，需求等待的概率計算如下：n上式普通被記為： n這個公式普通被稱為Erlang C公式，用來計算一個呼叫需求等待的概率 skk,00!k sskkk sk sk saap wppss0( , )!1/sapC s asa s等待制系統(tǒng)分析-等待概率 0!1/sapassa sBUPT Information Theory & Technology E

23、ducation & Research Center 例3.5 M/M/s系統(tǒng)的經(jīng)過呼叫量n例3.5 計算在as的條件下，M/M/s系統(tǒng)的經(jīng)過呼叫量。n解：經(jīng)過呼叫量11011(1)!ksskkkkk skk saakpsppspk01210!ksskkkkkk sk sssaapapppkapsp1()skk sapspaa1skppa代入和的表達式，整理消去BUPT Information Theory & Technology Education & Research Center n下面經(jīng)過Little公式計算平均等待時間Ew 。n系統(tǒng)中的平均呼叫數(shù)01000!

24、psskapkakkpNEskskkskkkk( , )( , )11C s aC sEsaaN例3.5 M/M/s系統(tǒng)的EwnEN為系統(tǒng)中的平均呼叫數(shù)，由被效力的平均呼叫數(shù)和等待的平均呼叫數(shù)組成BUPT Information Theory & Technology Education & Research Center E(N)結(jié)果的推導(dǎo)001skkkkkk sE Nkpkpkp 001111!kkkkk sk sk sk sk sk saaspkpspkps ss s 1101!sk skk skaasapskssss 111011skkkkkkk sk skkssksk

25、spkpspkppkspa BUPT Information Theory & Technology Education & Research Center E(N)結(jié)果的推導(dǎo)(2)nEN為系統(tǒng)中的平均呼叫數(shù)，由被效力的平均呼叫數(shù)和等待的平均呼叫數(shù)組成10211010(1)1!1!(11)!1assk skkksssssspssssapsapsaasks 令( , )1C s a( , )1E NaC s aBUPT Information Theory & Technology Education & Research Center n經(jīng)過的呼叫量為a，即系統(tǒng)

26、中忙的中繼線的平均數(shù)為a，所以 為等待隊列中的平均呼叫數(shù)。n根據(jù)Little公式，平均等待時間),(1asC( , ) ( , )/1(1)C s aE wC s as例3.5 M/M/s系統(tǒng)的Ew(續(xù))BUPT Information Theory & Technology Education & Research Center n 假設(shè)a25erl，呼損 n 需求多少中繼線？平均每條線的經(jīng)過呼叫量為多少？回絕的呼叫量為多少？n n 假設(shè)Cs，a0.01，每個呼叫平均繼續(xù)時間1/180秒，需求多少條中繼線？平均每條線經(jīng)過的呼叫量為多少？平均等待時間為多少？01. 0),(as

27、B例3.6 Erlang公式運用舉例BUPT Information Theory & Technology Education & Research Center n解：na25erl， 計算或者查表得s36 n回絕的呼叫量250.010.25erl n平均每條線經(jīng)過的呼叫量na/s2510.01/360.69。n假設(shè)a25erl， 計算或者查表得s39n平均每條線經(jīng)過的呼叫量na/s25/390.64 01. 0),(asB01. 0),(asC例3.6 求解BUPT Information Theory & Technology Education & R

28、esearch Center n系統(tǒng)中的平均呼叫數(shù)為 n平均等待時間為 0.64( , )0.012525.0111 0.64E NC s aa個( , )( , 0.010.128139(1 0)(1)(1).64)180C s aC s asE wS 例3.6 求解續(xù)BUPT Information Theory & Technology Education & Research Center 例3.7 分組交換系統(tǒng)的時間分析BUPT Information Theory & Technology Education & Research Center n數(shù)

29、據(jù)分組流服從參數(shù)的泊松過程nc表示線路速率n數(shù)據(jù)包長度為變長，平均包長為b，假設(shè)包長度服從負(fù)指數(shù)分布n效力時間也就服從負(fù)指數(shù)分布，且平均效力時間cb1BUPT Information Theory & Technology Education & Research Center n數(shù)據(jù)業(yè)務(wù)對語義透明性要求較高，在網(wǎng)絡(luò)正常任務(wù)時，圖3.8中的存儲器溢出概率很小，可以近似以為存儲器無限大。n交換機的每個出線可以用一個M/M/1系統(tǒng)模擬。根據(jù)定理2.5，M/M/1的系統(tǒng)時間s，可以由下面公式計算 bcsE/11)(例3.7 求解BUPT Information Theory &

30、; Technology Education & Research Center n包在穿過交換機時，上式中的s將是數(shù)據(jù)包閱歷的主要時間。需求留意的是在上式中，沒有思索包的開銷對時間的影響。n假設(shè)為了對數(shù)據(jù)包進展過失控制，要閱歷逐段反響重發(fā)，包閱歷的時間延遲的計算會比較復(fù)雜。 例3.7 結(jié)果分析BUPT Information Theory & Technology Education & Research Center 3.4.1 的穩(wěn)態(tài)分布n如今思索普通的排隊系統(tǒng)，這個系統(tǒng)有s個效力員，但系統(tǒng)的容量為n。n呼叫在到達系統(tǒng)時，假設(shè)有任何一個空閑的中繼線，可以立刻得到效

31、力，而系統(tǒng)假設(shè)已有n個呼叫，新到的呼叫會被回絕。n假設(shè)到達的呼叫流為參數(shù)的Poisson過程，效力時間服從參數(shù)為的負(fù)指數(shù)分布，這個系統(tǒng)是一個生滅過程。 )(/nsMMBUPT Information Theory & Technology Education & Research Center 00kknknnknkssskkk013.4.1 M/M/s(n) 的形狀轉(zhuǎn)移圖BUPT Information Theory & Technology Education & Research Center n從而根據(jù)2.7，穩(wěn)態(tài)分布n根據(jù)概率歸一性，求得 nkspss

32、askpkapskkkk00!0!110011 ( )!kssn skaaapksasss M/M/s(n)分析-pkBUPT Information Theory & Technology Education & Research Center M/M/s(n)分析時間阻塞率pnn呼叫需求等待的概率：n時間阻塞率為：0( , )np wC s a0!),(pssaasBpsnnnn101 ( )!snn skk sasapps sas BUPT Information Theory & Technology Education & Research Cente

33、r n當(dāng)ns 時， 。n 排隊系統(tǒng)是一個混合系統(tǒng)，既可以允許呼叫等待，又有一定的容量限制，隨著系統(tǒng)中s和n取不同的值，會得到不同的排隊系統(tǒng)。),(),(asBasBn)(/nsMMM/M/s(n)分析-結(jié)論BUPT Information Theory & Technology Education & Research Center M/M/s(n) 等待時間的分布 n n 表示呼叫到達時系統(tǒng)中有k個顧客的情況下等待時間的概率。n在時間t內(nèi)分開的呼叫數(shù)小于等于ks這個事件與事件 等價 k01kknP wtpwttwpkwtBUPT Information Theory &

34、; Technology Education & Research Center 001k01()!krk ss trkk snknk sapspwts tewrptP wtsM/M/s(n) 等待時間的分布續(xù)100()!1 ( / )1!( / )srn ssrn s rtatepsaa srs 0110()!n snrk r sksrs tas taepsrs 積分換序BUPT Information Theory & Technology Education & Research Center 3.5* Engset系統(tǒng) n思索圖3.12中的Engset系統(tǒng)，系統(tǒng)

35、中有s條中繼線，系統(tǒng)的輸入是n個同樣的信源。假設(shè)每個信源的輸入是參數(shù)為的Poisson過程。 nEngset系統(tǒng)的輸入流的強度取決于空閑信源的個數(shù)，輸入過程不是平穩(wěn)的。BUPT Information Theory & Technology Education & Research Center Engset系統(tǒng)圖3.12 Engset系統(tǒng)snBUPT Information Theory & Technology Education & Research Center n假設(shè)當(dāng)s個中繼線全滿時，就回絕新來的呼叫，這樣的系統(tǒng)稱為Engset回絕系統(tǒng)；假設(shè)當(dāng)s個中

36、繼線全滿時，允許呼叫等待，這樣的系統(tǒng)就稱為Engset等待系統(tǒng)。n下面思索Engset回絕系統(tǒng) 。BUPT Information Theory & Technology Education & Research Center n系統(tǒng)的中繼線數(shù)目sn，每個呼叫的繼續(xù)時間服從參數(shù)為的負(fù)指數(shù)分布，令 表示一個空閑信源所能提供的呼叫量。圖3.13為Engset系統(tǒng)的形狀轉(zhuǎn)移圖。n形狀變量BUPT Information Theory & Technology Education & Research Center nEngset回絕系統(tǒng)有 個形狀，這是一個生滅過程，各個形狀的到達率和離去