1、第三章 Erlang拒絕和等待系統(tǒng)通信網(wǎng)實驗室2022/7/19/23.1 介紹在本章中將要對不同的交換系統(tǒng)建立起排隊系統(tǒng)模型，并進行性能分析。 首先，需要定義電話網(wǎng)中的各種基本指標，電話交換系統(tǒng)如圖3.1。電話交換系統(tǒng)s條圖3.1 電話交換系統(tǒng)2022/7/19/3定義3.1業(yè)務量：業(yè)務量描述了在一定時間內，該s條線路被占用的總時間 。如果第r條信道被占用Qr秒，則s條信道上的業(yè)務量為：如果換一種角度，上述業(yè)務量Q的計算可以表達為：其中t0為觀察起點,T為觀察時長，R(t)為時刻t被占用的信道數(shù)，這是一個取值在0到S之間的隨機變量。(T時長內被占用的中繼數(shù)總數(shù))業(yè)務量2022/7/19/4呼

2、叫量的單位 erl上述定義的業(yè)務量與觀察時長T密切相關，下面定義的呼叫量或話務量與觀察時長無關。呼叫量一般用來近似表達電話呼叫流的大小。定義3.2呼叫量 呼叫量的單位為erl，這是一個無量綱的單位。實際上，在圖3.1中，在一段時間T內通過的呼叫量就是該時段內被占用的平均中繼數(shù)。2022/7/19/5對于從外界到達交換系統(tǒng)的呼叫流有兩種：一種為無限話源，這種系統(tǒng)被稱為愛爾蘭（Erlang）系統(tǒng)；另一種為有限話源，這種系統(tǒng)被稱為恩格謝特（Engset）系統(tǒng)。Erlang vs. Engset2022/7/19/6時間阻塞率 vs. 呼叫阻塞率現(xiàn)在來考慮電話網(wǎng)的時間阻塞率和呼損，這是兩個重要的性能指

3、標，當圖3.1中的s條中繼線全部繁忙時，系統(tǒng)處于阻塞狀態(tài)。系統(tǒng)處于阻塞狀態(tài)的時間和觀察時間的比例稱為時間阻塞率，即：定義3.3 時間阻塞率 2022/7/19/7定義3.4 呼叫阻塞率或呼損 拒絕呼叫的次數(shù)占總呼叫次數(shù)的比例定義為呼叫阻塞率。一般 ，如果到達的呼叫流為Poisson過程，有 。 掌握計算局部的呼損的Erlang公式和Engset公式是本章的重要的目標。 呼叫阻塞率2022/7/19/8數(shù)據(jù)交換系統(tǒng) 下面對數(shù)據(jù)交換系統(tǒng)進行一些說明。 2022/7/19/9數(shù)據(jù)交換系統(tǒng)在圖3. 2中，有p條入線和q條出線。在數(shù)據(jù)網(wǎng)絡中，信息一般被截為變長分組，在每條入線上，有不同的到達率。分組包在

4、到達交換系統(tǒng)后，根據(jù)路由表完成交換到達相應的出口j。但是因為難以避免的出線沖突，會有不同的入口來的信息包希望同時去同一出線，產(chǎn)生競爭，這些包將在相應的出口排成一個隊列，依照次序輪流得到服務。2022/7/19/10時延數(shù)據(jù)包在穿越交換機時將經(jīng)歷一段延遲，其中包含交換時延，排隊時延和服務時延。交換時延一般固定且較小排隊時延可變服務時延與包長有關排隊時延和服務時延是時延中最重要的部分，它們的和稱為系統(tǒng)時間。對于數(shù)據(jù)網(wǎng)絡，首先需要分析數(shù)據(jù)包穿越一個交換機的系統(tǒng)時間。2022/7/19/11對于數(shù)據(jù)網(wǎng)絡，有不同的工作方式，包括面向連接和無連接兩種主要方式。將對面向連接的數(shù)據(jù)網(wǎng)絡，對其交換系統(tǒng)建立模型，

5、分析其系統(tǒng)時間，進而計算網(wǎng)絡任意端對端的時延，然后全網(wǎng)的平均系統(tǒng)時間或平均時延。面向連接的數(shù)據(jù)網(wǎng)絡2022/7/19/12全網(wǎng)性能分析電話網(wǎng)絡和面向連接的數(shù)據(jù)網(wǎng)絡分別使用平均呼損和平均時延作為性能評估的重要指標。關于它們的計算可以做如下簡單考慮：2022/7/19/13網(wǎng)絡用圖 表示， 如果任意兩點之間的呼叫量為它們之間的呼損為： 電話網(wǎng)全網(wǎng)平均呼損2022/7/19/14如果任意兩點之間信息包的到達率為： 它們之間的延遲為： 數(shù)據(jù)網(wǎng)全網(wǎng)平均延遲2022/7/19/153.2 Erlang即時拒絕系統(tǒng) 2022/7/19/16現(xiàn)在假設電話呼叫流的到來服從Poisson過程，每個呼叫的持續(xù)時間服

6、從參數(shù)的負指數(shù)分布。系統(tǒng)有s條中繼線，如果沒有空閑的中繼線，就拒絕新來的呼叫，并且該呼叫不再進入系統(tǒng)。在這樣的情況下，該系統(tǒng)的排隊系統(tǒng)模型為2022/7/19/17M/M/s(s) 的 狀態(tài)轉移圖 2022/7/19/18這樣該生滅過程的達到率和離去率分別如下 :2022/7/19/19根據(jù)生滅過程的穩(wěn)態(tài)分布 規(guī)律：令根據(jù)概率歸一性， ，解得：2022/7/19/20Erlang公式 穩(wěn)態(tài)分布為： 特別，當ks 時， 表達了中繼線全忙的概率，這個概率為系統(tǒng)的時間阻塞率，記為 Erlang B公式2022/7/19/21例3.1 計算M/M/排隊系統(tǒng)的平均隊長。解：M/M/為一個虛擬系統(tǒng)，有個中

7、繼線。到達的呼叫流是參數(shù)的Poisson過程，呼叫持續(xù)時間服從參數(shù)為的負指數(shù)分布。由于有個服務員或中繼線，系統(tǒng)一定有穩(wěn)態(tài)分布，取系統(tǒng)中的呼叫數(shù)為狀態(tài)變量，這個排隊系統(tǒng)是一個生滅過程。狀態(tài)轉移圖如圖3.4所示。 例3.1 2022/7/19/22各狀態(tài)的到達率和離去率如下： 例3.1 狀態(tài)轉移圖2022/7/19/23由生滅過程，設 ，則：根據(jù)概率歸一性， ，則從而穩(wěn)態(tài)分布為上式中的服從參數(shù)為a的泊松分布，如果為系統(tǒng)中的呼叫數(shù)，則其平均隊長EN和方差VarN同為a。平均隊長為a表明通過的呼叫量為a。例3.1 求解過程2022/7/19/24例3.2 計算圖3.1中的通過呼叫量。解：通過的呼叫量是

8、被占用的平均中繼線數(shù)?？紤]到穩(wěn)態(tài)分布為：通過的呼叫量：例3.2 M/M/s(s)的通過呼叫量2022/7/19/25結果的直觀意義，如圖3.5。 a為到達的總呼叫量，a為通過的呼叫量，a和a的關系可以由 來決定。每條中繼線平均承載的呼叫量為電話交換系統(tǒng)aa圖3.5通過的呼叫量例3.2 結論2022/7/19/26根據(jù)Erlang公式計算得， ， 。如果時間阻塞率為0.02，30條中繼線可以承載21.9erl的呼叫量，而10條中繼線可以承載5.08erl的呼叫量。顯然后者承載的呼叫量遠小于前者的1/3。在同樣時間阻塞率下，分散的中繼線群承載的總呼叫量小于中繼線集中后承載的呼叫量。在實踐中，將這種

9、集中效應稱為大群化效應 例3.3 大群化效應2022/7/19/27例3.3中的兩種情況下，效率是不一樣的。在同樣的呼損下，小中繼線群效率較低。效率高的中繼線群對呼叫量的波動更加敏感習題3.3例3.2 大群化效應效率2022/7/19/28在圖3.1的中繼線群中，如果將中繼線依次編號為1，2，s，并且嚴格按順序使用。請計算每條中繼線的通過呼叫量。解：對任意k(1ks)，根據(jù)中繼線的使用規(guī)則，在1，2，k這k條中繼線上的溢出呼叫量將由k1，k2，s這些中繼線來承載。例3.4 M/M/S(S)順序使用2022/7/19/291，2，k1這k1條中繼線通過的呼叫量為1，2，k這k條中繼線上通過的呼叫

10、量為 所以，第k條中繼線通過的呼叫量 這樣，第k條中繼線通過的呼叫量例3.4 求解2022/7/19/30例3.5 主備線即時拒絕系統(tǒng)2022/7/19/313.3 Erlang等待制系統(tǒng) 假設呼叫流的到來服從參數(shù)為的Poisson過程每個呼叫的持續(xù)時間服從參數(shù)為的負指數(shù)分布。系統(tǒng)有s條中繼線如果呼叫到來時系統(tǒng)中沒有空閑的中繼線，該呼叫并不被拒絕，而是等待。假設這個系統(tǒng)的等待位置可以是，則該系統(tǒng)的模型為M/M/s。 2022/7/19/323.3 等待制系統(tǒng)對于這個系統(tǒng)的分析目標首先需要計算穩(wěn)態(tài)分布然后計算一個呼叫到來時需要等待的概率再次需要了解等待時間的均值、分布等。 2022/7/19/3

11、3等待制系統(tǒng)狀態(tài)轉移圖 2022/7/19/34該生滅過程各個狀態(tài)的到達率和離去率如下 等待制系統(tǒng)分析 2022/7/19/35假設 為穩(wěn)態(tài)分布， ，則根據(jù)概率歸一性，則 等待制系統(tǒng)分析-pk 2022/7/19/36在a0。 考慮呼叫到達系統(tǒng)的瞬間，不算該呼叫，系統(tǒng)的狀態(tài)分布為 。一般來說， 與 是不同的，但是如果到達的呼叫流為Poisson過程，則 等待制系統(tǒng)分析-p0 2022/7/19/37一個呼叫到來時，當系統(tǒng)處于狀態(tài) 時，呼叫需要等待，需要等待的概率計算如下：上式一般被記為： 這個公式一般被稱為Erlang C公式，用來計算一個呼叫需要等待的概率 等待制系統(tǒng)分析-等待概率 2022

12、/7/19/38例3.5 M/M/s系統(tǒng)的通過呼叫量例3.5 計算在as的條件下，M/M/s系統(tǒng)的通過呼叫量。解：通過呼叫量2022/7/19/39下面通過Little公式計算平均等待時間Ew 。系統(tǒng)中的平均呼叫數(shù)例3.5 M/M/s系統(tǒng)的EwEN為系統(tǒng)中的平均呼叫數(shù)，由被服務的平均呼叫數(shù)和等待的平均呼叫數(shù)組成2022/7/19/40E(N)結果的推導2022/7/19/41E(N)結果的推導(2)EN為系統(tǒng)中的平均呼叫數(shù)，由被服務的平均呼叫數(shù)和等待的平均呼叫數(shù)組成2022/7/19/42通過的呼叫量為a，即系統(tǒng)中忙的中繼線的平均數(shù)為a，所以 為等待隊列中的平均呼叫數(shù)。根據(jù)Little公式，平

13、均等待時間例3.5 M/M/s系統(tǒng)的Ew(續(xù))2022/7/19/43 如果a25erl，呼損 需要多少中繼線？平均每條線的通過呼叫量為多少？拒絕的呼叫量為多少？ 如果C（s，a）0.01，每個呼叫平均持續(xù)時間1/180秒，需要多少條中繼線？平均每條線通過的呼叫量為多少？平均等待時間為多少？例3.6 Erlang公式應用舉例2022/7/19/44解：a25erl， 計算或者查表得s36 拒絕的呼叫量250.010.25erl 平均每條線通過的呼叫量a/s25（10.01）/360.69。若a25erl， 計算或者查表得s39平均每條線通過的呼叫量a/s25/390.64 例3.6 求解202

14、2/7/19/45系統(tǒng)中的平均呼叫數(shù)為 平均等待時間為 例3.6 求解（續(xù)）2022/7/19/46M/M/s 等待時間的分布 表示呼叫到達時系統(tǒng)中有k個顧客的情況下等待時間的概率。在時間t內離開的呼叫數(shù)小于等于ks這個事件與事件 等價 2022/7/19/47M/M/s 等待時間的分布（續(xù)）等待時間的分布均值為等待時間的分布混合分布：離散+連續(xù)2022/7/19482022/7/19/49數(shù)據(jù)分組流服從參數(shù)的泊松過程c表示線路速率數(shù)據(jù)包長度為變長，平均包長為b，假設包長度服從負指數(shù)分布服務時間也就服從負指數(shù)分布，且平均服務時間例3.7 分組交換系統(tǒng)的時間分析2022/7/19/50分組交換系

15、統(tǒng)的排隊模型2022/7/19/51數(shù)據(jù)業(yè)務對語義透明性要求較高，在網(wǎng)絡正常工作時，圖3.8中的存儲器溢出概率很小，可以近似認為存儲器無限大。交換機的每個出線可以用一個M/M/1系統(tǒng)模擬。根據(jù)定理2.5，M/M/1的系統(tǒng)時間s，可以由下面公式計算 例3.7 求解2022/7/19/52包在穿過交換機時，上式中的s將是數(shù)據(jù)包經(jīng)歷的主要時間。需要注意的是在上式中，沒有考慮包的開銷對時間的影響。如果為了對數(shù)據(jù)包進行差錯控制，要經(jīng)歷逐段反饋重發(fā)，包經(jīng)歷的時間延遲的計算會比較復雜。 例3.7 結果分析2022/7/19/533.4.1 的穩(wěn)態(tài)分布現(xiàn)在考慮一般的排隊系統(tǒng)，這個系統(tǒng)有s個服務員，但系統(tǒng)的容量

16、為n。呼叫在到達系統(tǒng)時，如果有任何一個空閑的中繼線，可以立刻得到服務，而系統(tǒng)如果已有n個呼叫，新到的呼叫會被拒絕。如果到達的呼叫流為參數(shù)的Poisson過程，服務時間服從參數(shù)為的負指數(shù)分布，這個系統(tǒng)是一個生滅過程。 2022/7/19/543.4.1 M/M/s(n) 的狀態(tài)轉移圖2022/7/19/55從而根據(jù)（2.7），穩(wěn)態(tài)分布根據(jù)概率歸一性，求得 M/M/s(n)分析-pk2022/7/19/56M/M/s(n)分析時間阻塞率pn呼叫需要等待的概率：時間阻塞率為：2022/7/19/57當ns 時， 。 排隊系統(tǒng)是一個混合系統(tǒng)，既可以允許呼叫等待，又有一定的容量限制，隨著系統(tǒng)中s和n取不

17、同的值，會得到不同的排隊系統(tǒng)。M/M/s(n)分析-結論2022/7/19/58M/M/s(n) 等待時間的分布 表示呼叫到達時系統(tǒng)中有k個顧客的情況下等待時間的概率。在時間t內離開的呼叫數(shù)小于等于ks這個事件與事件 等價 2022/7/19/59M/M/s(n) 等待時間的分布（續(xù)）603.5* Engset系統(tǒng) Engset系統(tǒng)圖3.12 Engset系統(tǒng)sn2022/7/1961系統(tǒng)中有s條中繼線，系統(tǒng)的輸入是n個同樣的信源。假設每個信源的輸入是參數(shù)為的Poisson過程。 Engset系統(tǒng)的輸入流的強度取決于空閑信源的個數(shù)，輸入過程不是平穩(wěn)的。如果當s個中繼線全滿時，就拒絕新來的呼叫，

18、這樣的系統(tǒng)稱為Engset拒絕系統(tǒng)；如果當s個中繼線全滿時，允許呼叫等待，這樣的系統(tǒng)就稱為Engset等待系統(tǒng)。Engset系統(tǒng) 2022/7/1962系統(tǒng)的中繼線數(shù)目sn，每個呼叫的持續(xù)時間服從參數(shù)為的負指數(shù)分布，令 表示一個空閑信源所能提供的呼叫量。圖3.13為Engset系統(tǒng)的狀態(tài)轉移圖。狀態(tài)變量Engset系統(tǒng) 2022/7/19/63Engset拒絕系統(tǒng)有 個狀態(tài)，這是一個生滅過程，各個狀態(tài)的到達率和離去率分別為：Engset系統(tǒng)的生滅過程 2022/7/19/64穩(wěn)態(tài)分布為：根據(jù)概率歸一性有 Engset系統(tǒng)的穩(wěn)態(tài)分布 2022/7/19/65令 則其中 表示了系統(tǒng)的時間阻塞率 。時間阻塞率 2022/7/19/66呼損 是呼叫到來時，系統(tǒng)中有k個呼叫的概率；根據(jù)定義 2022/7/19/67特別，當ks時， 表示了Engset系統(tǒng)的呼損 這個公