北郵排隊論作業(yè)

1、計算機通信基礎期末論文姓名學號2015141007時間2016年1月基于多服務窗損失制排隊模型的網(wǎng)絡管理系統(tǒng)摘要 對于一個普通的局域網(wǎng)，如果網(wǎng)絡中的某一個終端想連接互聯(lián)網(wǎng)，必須通過網(wǎng)絡管理系統(tǒng)的驗證，網(wǎng)絡管理系統(tǒng)負責分配一定數(shù)量的上網(wǎng)名額給終端。這個過程可以看做是一個多服務窗損失制排隊模型，本文分別從實際場景，排隊系統(tǒng)組成，排隊論在這個問題中的應用三個方面加以介紹。關鍵字 網(wǎng)絡管理 多服務窗損失制1 網(wǎng)絡管理系統(tǒng)實際場景介紹局域網(wǎng)的分布距離一般在數(shù)公里以內(nèi)，以基本特征是由某一個單位團體管理和使用。局域網(wǎng)的基本組成：ü 一個團體對于網(wǎng)絡應用的需求有幾個方面ü 文件共享，辦公管

2、理，郵件服務等ü 團體內(nèi)部人員可以在網(wǎng)絡中進行交流圖1 局域網(wǎng)簡單示意網(wǎng)絡管理用于控制和管理終端設備對于網(wǎng)絡的連接，資源分配，在就存在網(wǎng)絡運行是否有效率，資源分配是否合理的問題。網(wǎng)絡驗證為網(wǎng)絡管理的重要功能，將為用戶提供服務質(zhì)量保證。因特網(wǎng)主要根據(jù)IP協(xié)議通過IP包來實現(xiàn)數(shù)據(jù)在網(wǎng)絡上的傳送。與內(nèi)部網(wǎng)絡相連的計算機均有唯一的合法PI地址，用戶可通過這些計算機訪問因特網(wǎng)上的資源。由于一臺計算機同一時間只能由一個人使用。因此不管是擴充一個現(xiàn)有網(wǎng)絡的功能還是規(guī)劃一個待建的網(wǎng)絡，配置網(wǎng)絡管理系統(tǒng)的時候都要在滿足用戶使用需求的基礎上使網(wǎng)絡資源分配盡可能最優(yōu)。現(xiàn)對網(wǎng)絡管理系統(tǒng)的工作原理加以介紹：該

3、系統(tǒng)是一個網(wǎng)關設備，安裝在局域網(wǎng)網(wǎng)絡的出口上，其軟件系統(tǒng)對所有進出用戶的數(shù)據(jù)包進行進行驗證、授權、管理。描述網(wǎng)絡管理系統(tǒng)的性能指標除了硬件系統(tǒng)的指標之外，最重要的就是能同時提供多少個用戶登陸系統(tǒng)認證后,同時在線使用網(wǎng)絡，即系統(tǒng)容量。圖2 網(wǎng)絡拓撲圖一個終端連接網(wǎng)絡的行為可以描述為：l 任意時刻，終端都可能請求連接網(wǎng)絡。網(wǎng)絡管理系統(tǒng)接到上網(wǎng)請求后，檢查本系統(tǒng)是否飽和。如果飽和，拒絕連接，連接失敗。如果未飽和，允許連接，連接成功。l 任意時刻，終端都可以請求注銷連接。網(wǎng)絡管理系統(tǒng)接受到注銷請求時，斷開連接，并可以接受其他終端的連接?？紤]到局域網(wǎng)出口帶寬有限，使用網(wǎng)絡的用戶具有隨機性和不確定性，那么

4、問題就轉(zhuǎn)化為固定的資源分配給盡可能多的終端使用，充分利用網(wǎng)絡資源。通過分析網(wǎng)絡管理系統(tǒng)的工作原理和終端使用情況，建立數(shù)學模型，對該服務系統(tǒng)的服務強度和損失率等指標的研究，達到優(yōu)化系統(tǒng)、提高網(wǎng)絡使用效率和服務質(zhì)量的目的。2 排隊系統(tǒng)的組成2.1 輸入過程輸入過程具有如下屬性：（1） 顧客總體可以有限或無限。（2） 顧客到達系統(tǒng)的方式可以逐個或成批。（3） 顧客相繼到來時間間隔可分為確定型和隨機性。（4） 顧客到達系統(tǒng)可以是獨立的或相關的。2.2排隊過程排隊規(guī)則可分為三種制式：（1） 損失制顧客到達系統(tǒng)時，如果系統(tǒng)中所有服務窗均被占用，則到達的客隨即離去，比如打電話時遇到占線，用戶即擱置重打或離去

5、另找地方或過些時候再打。（2） 等待制顧客到達系統(tǒng)時，雖然發(fā)現(xiàn)服務窗均忙著，但系統(tǒng)設有場地供顧客排隊等候之用，于是到達系統(tǒng)之顧客按先后順序進行排隊等候服務。通常的服務規(guī)則有先到先服務，后到先服務（比如倉庫中同種物品堆壘后的出庫過程），隨機服務，優(yōu)先服務（比如郵政中的快件與特快轉(zhuǎn)遞業(yè)務，重危病人的急診，交通中讓救火（護）車、警車及迎賓車隊優(yōu)先通過）等。（3） 混合制它是損失制與等待制混合組成的排隊系統(tǒng)，此系統(tǒng)僅允許有限個顧客等候排隊，其余顧客只好離去；或者顧客中有的見到排隊隊伍長而不愿費時等候，當隊伍短時愿排隊等候服務；也有排隊等候的顧客當?shù)群驎r間超過某個時間就離隊而去均屬這種系統(tǒng)。2.3 服務

6、窗系統(tǒng)可以一個窗口或多個窗口為顧客進行服務：（1） 在多個服務窗情形，顧客排隊可以平行多隊排列，串列或并串同時存在的混合排隊。（2） 一個服務窗可以為單個顧客或成批顧客進行服務。（3） 各窗口的服務時間可為確定型或隨機型。服務時間往往假定是平穩(wěn)的。2.4排隊系統(tǒng)的目標參量（1） 絕對通過能力，它為單位時間內(nèi)被服務完顧客的均值。（2） 相對通過能力，它為單位時間內(nèi)被服務完顧客數(shù)與請求服務顧客數(shù)之比值。（3） 系統(tǒng)排隊均值，它即是系統(tǒng)內(nèi)顧客數(shù)的均值。（4） 排隊等候顧客的平均隊列長度，它即是系統(tǒng)內(nèi)排隊等候顧客的均值。（5） 顧客在系統(tǒng)內(nèi)逗留時間的均值；顧客排隊等候服務的時間的均值；服務時間的均值為

7、，顯然有。（6） 服務窗連續(xù)繁忙的時間長度，即忙期。（7） 系統(tǒng)的損失概率，即系統(tǒng)滿員概率。3 M/M/n/n在網(wǎng)絡管理中的應用假定系統(tǒng)內(nèi)有n個服務窗，顧客按泊松流到達系統(tǒng)，其強度為。倘若顧客到達系統(tǒng)時發(fā)現(xiàn)n個服務窗均忙著，他立即離開系統(tǒng)。又設各服務窗的服務時間服從負指數(shù)分布，強度為。這種系統(tǒng)就是多服務窗損失制排隊模型M/M/n/n。例如沒有多條電話線路的電話交換系統(tǒng)。不許排隊等候空位的街頭停車場等均屬此類排隊模型。根據(jù)排隊論中排隊系統(tǒng)的組成，對網(wǎng)絡管理系統(tǒng)作如下假設：l 在一定時期內(nèi)，用戶可以反復多次請求系統(tǒng)，因此將用戶看作是無限的。l 假設用戶隨機到達，每一次相互獨立，而且在觀察期間平穩(wěn)，

8、忽略高峰與低谷。l 將用戶到達的序列看做輸入流。假設用戶到達的時間服從參數(shù)為的負指數(shù)分布，在（0，t）時間到達的用戶數(shù)N(t)就是一個泊松過程。將需要登錄上網(wǎng)的用戶視為顧客，將網(wǎng)絡管理平臺視為服務窗，網(wǎng)絡管理平臺驗證一次終端用戶，完成一次服務。網(wǎng)絡管理平臺管理固定多的可上網(wǎng)名額，可以視為有n個服務窗，終端用戶按照泊松流到達，強度為。如果用戶發(fā)現(xiàn)已經(jīng)沒有名額了，上網(wǎng)名額都被占著，也就相當于n個服務窗均忙著，此用戶放棄登錄，也就是離開系統(tǒng)。又設用戶對上網(wǎng)名額的占用時間服從負指數(shù)分布，強度為。因此，在一個局域網(wǎng)中，終端對網(wǎng)絡管理平臺進行訪問，請求上網(wǎng)名額，在合理的假設下符合多服務窗損失制排隊模型M/

9、M/n/n。圖3 多服務窗損失制排隊模型示意對于多服務窗損失制排隊模型，設X(t)表示時刻t系統(tǒng)中的顧客數(shù)，則是狀態(tài)空間且生率為：滅率為：這里0狀態(tài)表示個服務窗均空閑著，系統(tǒng)內(nèi)沒有顧客到達；狀態(tài)則表示系統(tǒng)內(nèi)已有個顧客，且正在某個服務窗口前被服務著，而有個服務窗空閑著。由于一旦n個服務窗口均忙著，那么新到達的顧客不得不離去另尋服務，這對系統(tǒng)來說是一個損失，稱為損失制。當系統(tǒng)處于狀態(tài)，即有某個服務窗正為個顧客服務，一旦其中一個顧客被服務畢離開系統(tǒng)時，系統(tǒng)便處于狀態(tài)，由于個正被服務的顧客均有先被服務畢的可能（或個服務窗從忙到閑的可能性是均等的），故從狀態(tài)轉(zhuǎn)變到狀態(tài)的轉(zhuǎn)移強度為。每個服務窗的平均服務率

10、相同且為。上網(wǎng)用戶到達率與系統(tǒng)狀態(tài)轉(zhuǎn)換無關，始終為。于是，畫出該模型的狀態(tài)流圖（瞬時轉(zhuǎn)移強度圖）。圖4 M/M/n/n排隊模型狀態(tài)流圖于是，平衡條件下的K氏方程為：對0狀態(tài)有，故有；對1狀態(tài)有， 故有；對k-1狀態(tài)有 ， 故有；對n-1狀態(tài)有 ， 故有。利用正則性條件，可以得到由此得到相應的值由此得到相應的目標參量（1）損失概率（2）單位時間內(nèi)平均損失的顧客數(shù)與平均進入系統(tǒng)的顧客數(shù)（3）系統(tǒng)的相對通過能力與絕對通過能力（4）系統(tǒng)在單位時間內(nèi)占用服務窗的均值因為，故上式也等于。（5）系統(tǒng)服務窗的效率（6）顧客在系統(tǒng)內(nèi)平均逗留時間等于顧客被服務時間，即這些指標對應于之前的網(wǎng)絡管理系統(tǒng)。損失概率指局域網(wǎng)內(nèi)的用戶沒有通過系統(tǒng)驗證而選擇離開的概率，系統(tǒng)在單位時間內(nèi)占用服務窗的均值指系統(tǒng)在單位時間內(nèi)用戶使用上網(wǎng)名額的均值，服務窗效率也就是系統(tǒng)的服務效率。通過這些指標可以較為全面地評估網(wǎng)絡管理系統(tǒng)的服務能力。參考文獻【1】