第三章-4 排隊網(wǎng)絡(luò)

排隊網(wǎng)絡(luò)排隊網(wǎng)絡(luò)前面我們討論的都是單個隊列，并且假定到達過程和服務(wù)間隔相互獨立，而在實際的數(shù)據(jù)通信網(wǎng)中，每節(jié)點都有一個隊列，各節(jié)點的隊列組成一個排隊的網(wǎng)絡(luò)。排隊網(wǎng)絡(luò)排隊網(wǎng)絡(luò)假設(shè)有兩個節(jié)點組成一個串行的網(wǎng)絡(luò)，排隊網(wǎng)絡(luò)節(jié)點1的隊列可用M/D/1來描述。第一個隊列數(shù)據(jù)分組的服務(wù)時間1/

平均等待時間用P-K公式求取第二個隊列到達間隔大于（分組的傳輸時間），不可能有等待隊列到達過程完全取決于第一個節(jié)點隊列的輸出，到達過程與服務(wù)過程相互獨立的假設(shè)不成立，無法應(yīng)用前面的時延分析方法排隊網(wǎng)絡(luò)假定節(jié)點1的輸入是到達率為的Possion過程。第二個節(jié)點到達過程完全取決于第一個節(jié)點隊列的輸出，假定在前一個分組傳輸結(jié)束以后的一個時刻有一個長分組到達。在該長分組傳輸時間有一個短分組到達，則長分組在第二個隊列中等待的時間較短，不能用M/M/1分析Kleinrock獨立性近似Kleinrock獨立性近似對于任一個網(wǎng)絡(luò)來說，假定進入網(wǎng)絡(luò)的分組流是服從Possion分布，經(jīng)過網(wǎng)絡(luò)傳輸后，后繼節(jié)點輸入過程的到達間隔與前一節(jié)點分組傳輸間隔緊密相關(guān)，從而破壞了該節(jié)點到達過程和服務(wù)間隔相互獨立的假設(shè)，這樣就不能使用前面分析的M/M/1隊列的有關(guān)結(jié)果，為了解決該問題，我們需要采用Kleinrock建議的獨立性近似方法。

Kleinrock獨立性近似分組流（某一虛電路上的分組）用s來表示，對于經(jīng)過任一條鏈路（i,j）的分組到達率由經(jīng)過該鏈路的各分組流的到達率組成，即Kleinrock獨立性近似數(shù)據(jù)報網(wǎng)絡(luò)：分組流s的到達率（分組/秒）分組流s經(jīng)過（i,j）鏈路的分組比例Kleinrock獨立性近似Kleinrock建議，幾條分組流合成的一個分組流，類似于部分恢復(fù)了到達間隔和分組長度的獨立性。如果合成的分組流數(shù)目n較大，則到達間隔與分組長度的依賴性將很弱。這樣就可以采用M/M/1模型來描述每條鏈路，而不管這條鏈路上的業(yè)務(wù)與其他鏈路上業(yè)務(wù)的相互作用，這就是Kleinrock獨立性近似，對于中等到重負荷的網(wǎng)絡(luò)是一個很好的近似。Kleinrock獨立性近似利用M/M/1模型，在鏈路（i,j）上的平均分組數(shù)為網(wǎng)絡(luò)中的平均分組數(shù)為Kleinrock獨立性近似應(yīng)用Little公式，可得平均分組時延為這里，為系統(tǒng)總的到達率，即Kleinrock獨立性近似如果各鏈路的處理時延和傳播時延之和是不可忽略的，則上式需改寫為對于任給一條路經(jīng)p，在該路徑中的總的平均時延為式中，括號內(nèi)的第一項是等待時間，第二項是傳輸時延，第三項是處理時延和傳播時延之和。Kleinrock獨立性近似例：假定A沿兩條鏈路L1和L2向B發(fā)送數(shù)據(jù)分組，鏈路的服務(wù)速率為。節(jié)點A的分組到達過程是速率為的Possion過程，分組長度服從指數(shù)分布，且與到達間隔相互獨立。試問應(yīng)如何在A和B之間的兩條鏈路上分配業(yè)務(wù)流？

Kleinrock獨立性近似假定采用兩種方法：一是隨機的方式（Randomization），即A通過扔硬幣的方法來分配分組流；二是采用計量的方法（Metering），節(jié)點A將分組送入比特長度最短的隊列（它等于各排隊分組比特長度之和）。Kleinrock獨立性近似在隨機方式中，很容易證明L1和L2上的分組到達流都是Poisson流，且與分組長度無關(guān)。這樣每一條鏈路都是到達率為

/2的M/M/1隊列。利用M/M/1隊列結(jié)果，可得分組的平均時延為這種情況與Kleinrock的獨立性近似是一致的。Kleinrock獨立性近似在計量的方式中，到達的分組進入比特長度最短的隊列，這時系統(tǒng)相當(dāng)于一個M/M/2的系統(tǒng)，總的到達率為，每條鏈路是一個服務(wù)員，利用前面的結(jié)果得分組的平均時延為式中，Kleinrock獨立性近似采用計量的方法，可使時延減少到隨機方式的1/(1+

），這也進一步反映了統(tǒng)計復(fù)用的好處。如果在實際系統(tǒng)中，要將一個比特流分解成幾個可選的路由，應(yīng)當(dāng)采用計量的方法。但是，采用計量的方法，破壞了各個隊列的Poisson特性，這時每條鏈路的到達間隔不再是指數(shù)分布，且與前面的分組長度相關(guān)。這時，我們看到，若采用M/M/1的近似，其準確度較差。上述例題說明，采用不同的服務(wù)法則，可能會影響采用Kleinrock獨立性近似的準確度。

Burke定理Burke定理對具有到達率為的M/M/1，M/M/m,M/M/∞系統(tǒng)，假定系統(tǒng)開始時就處于穩(wěn)態(tài)（或初始狀態(tài)是根據(jù)穩(wěn)態(tài)分布而選定的），有下列結(jié)論：系統(tǒng)的離開過程是速率為的Poisson過程。在時刻t,系統(tǒng)中顧客數(shù)獨立于t時刻以前用戶離開系統(tǒng)的時間序列。

Burke定理該定理說明了該類排隊系統(tǒng)的兩個特性：一是輸出過程（或離開過程）仍服從Poisson過程；二是系統(tǒng)中當(dāng)前顧客數(shù)與離開系統(tǒng)的顧客流之間的關(guān)系，它們之間相互獨立。Burke定理我們可能會認為：系統(tǒng)最近有一個非常繁忙的離開流，意味著系統(tǒng)現(xiàn)在會有大量顧客在排隊，是一個繁忙系統(tǒng)。然而，Burke定理表明這是不正確的，該定理指出一個繁忙的離開流，沒有說明任何當(dāng)前系統(tǒng)的狀態(tài)信息。

Burke定理求解兩個M/M/1隊列串聯(lián)后系統(tǒng)的狀態(tài)概率。該系統(tǒng)的到達過程是到達率為的Poisson過程。這兩個隊列的服務(wù)時間相互獨立（即相同的分組在兩個節(jié)點的服務(wù)時間不同），服務(wù)時間與到達過程相互獨立，

Burke定理由于隊列1是M/M/1隊列，因此在該隊列中，用戶數(shù)為n的概率為由Burke定理可知，隊列1的輸出是速率的Poisson過程，并根據(jù)假定知，隊列2的服務(wù)時間與到達過程獨立，因此隊列2可以看成為孤立的M/M/1隊列，因而有隊列2中用戶數(shù)為m的概率為Burke定理由Burke定理知，隊列1當(dāng)前的用戶數(shù)與過去的離開過程相互獨立，也就是與隊列2的過去到達過程無關(guān)。所以,隊列1當(dāng)前的用戶數(shù)與隊列2當(dāng)前的用戶數(shù)無關(guān)。因此有：系統(tǒng)中隊列1有n個用戶，隊列2有m個用戶的概率為P{隊列1中有n個用戶，隊列2中有m個用戶}=P{隊列1中用n個用戶}

P{隊列2中用m個用戶}=Burke定理該公式告訴我們，兩個串聯(lián)的隊列，只要滿足獨立性的要求，就可以看成是兩個完全獨立的具有相同到達率的M/M/1隊列。Jackson定理Jackson定理由前面的討論可知，當(dāng)一個分組的到達過程通過網(wǎng)絡(luò)的第一個隊列以后，分組到達將與它們的長度相關(guān)。如果這種相關(guān)性可以消除或采用隨機的方法將分組分成若干個不同的路由，那么系統(tǒng)中的平均分組數(shù)可以通過將網(wǎng)絡(luò)中的每個隊列看成是M/M/1隊列而導(dǎo)出。這是Jackson定理的基本結(jié)果。Jackson定理Jackson定理說明了若排隊網(wǎng)絡(luò)滿足下列兩個條件：①進入網(wǎng)絡(luò)的到達過程是Poisson過程；②各隊列的服務(wù)時間是獨立的指數(shù)分布，則在數(shù)值上系統(tǒng)的顧客數(shù)由k個獨立的M/M/1隊列決定。注意該定理并沒有要求到達各隊列的到達過程是獨立的Poisson過程。Jackson定理求圖所示計算機系統(tǒng)的總?cè)蝿?wù)數(shù)N和任務(wù)的平均時延T。該系統(tǒng)是一個具有輸入/輸出（I/O）反饋的中心處理器（CPU）系統(tǒng)。任務(wù)到達過程是速率為的Poisson過程。假定所有的服務(wù)時間相互獨立，包括相同的任務(wù)再次經(jīng)過（CPU）和I/O的時間也是相互獨立的。CPU處理完的任務(wù)以概率p1離開系統(tǒng)。Jackson定理Jackson定理Jackson定理Jackson定理Jackson定理

Jackson定理表明了在求解系統(tǒng)中的顧客數(shù)時，可以把系統(tǒng)看成k個獨立的M/M/1隊列。它要求進入網(wǎng)絡(luò)的到達過程是Poisson過程，但是每一個隊列的總到達過程不一定需要是Poisson過程。例如：如圖所示，外部到達過程是速率為的Poisson過程，隊列的服務(wù)速率Jackson定理Jackson定理經(jīng)過隊列的分組以1-p的概率離開系統(tǒng)。假定p接近于1。對于隊列而言，當(dāng)有一個到達后，將會以很大的概率，在很短的時間內(nèi)又有一個到達（反饋到達）。對于網(wǎng)絡(luò)而言，當(dāng)有一個到達后，在很短的時間內(nèi)又有新到達的概率非常小。也就是說，由于隊列輸出反饋到隊列輸入的概率很高，網(wǎng)絡(luò)的一個到達，將觸發(fā)隊列有一批到達（或者說一個突發(fā)的到達串），顯然，隊列的到達間隔不是獨立的，其總的到達過程不是Poisson到達。小結(jié)本章主要討論了信息網(wǎng)絡(luò)中常用的時延模型，這些模型常用于多種網(wǎng)絡(luò)的性能分析和評估。首先討論了排隊系統(tǒng)中的基本定理

Little定理及其多種變形表示和應(yīng)用。小結(jié)小結(jié)接著討論了單一排隊模型。包括兩類排隊模型：一類是M/M/1，M/M/m，