第三章-4 排队网络

排队网络排队网络前面我们讨论的都是单个队列，并且假定到达过程和服务间隔相互独立，而在实际的数据通信网中，每节点都有一个队列，各节点的队列组成一个排队的网络。排队网络排队网络假设有两个节点组成一个串行的网络，排队网络节点1的队列可用M/D/1来描述。第一个队列数据分组的服务时间1/

平均等待时间用P-K公式求取第二个队列到达间隔大于（分组的传输时间），不可能有等待队列到达过程完全取决于第一个节点队列的输出，到达过程与服务过程相互独立的假设不成立，无法应用前面的时延分析方法排队网络假定节点1的输入是到达率为的Possion过程。第二个节点到达过程完全取决于第一个节点队列的输出，假定在前一个分组传输结束以后的一个时刻有一个长分组到达。在该长分组传输时间有一个短分组到达，则长分组在第二个队列中等待的时间较短，不能用M/M/1分析Kleinrock独立性近似Kleinrock独立性近似对于任一个网络来说，假定进入网络的分组流是服从Possion分布，经过网络传输后，后继节点输入过程的到达间隔与前一节点分组传输间隔紧密相关，从而破坏了该节点到达过程和服务间隔相互独立的假设，这样就不能使用前面分析的M/M/1队列的有关结果，为了解决该问题，我们需要采用Kleinrock建议的独立性近似方法。

Kleinrock独立性近似分组流（某一虚电路上的分组）用s来表示，对于经过任一条链路（i,j）的分组到达率由经过该链路的各分组流的到达率组成，即Kleinrock独立性近似数据报网络：分组流s的到达率（分组/秒）分组流s经过（i,j）链路的分组比例Kleinrock独立性近似Kleinrock建议，几条分组流合成的一个分组流，类似于部分恢复了到达间隔和分组长度的独立性。如果合成的分组流数目n较大，则到达间隔与分组长度的依赖性将很弱。这样就可以采用M/M/1模型来描述每条链路，而不管这条链路上的业务与其他链路上业务的相互作用，这就是Kleinrock独立性近似，对于中等到重负荷的网络是一个很好的近似。Kleinrock独立性近似利用M/M/1模型，在链路（i,j）上的平均分组数为网络中的平均分组数为Kleinrock独立性近似应用Little公式，可得平均分组时延为这里，为系统总的到达率，即Kleinrock独立性近似如果各链路的处理时延和传播时延之和是不可忽略的，则上式需改写为对于任给一条路经p，在该路径中的总的平均时延为式中，括号内的第一项是等待时间，第二项是传输时延，第三项是处理时延和传播时延之和。Kleinrock独立性近似例：假定A沿两条链路L1和L2向B发送数据分组，链路的服务速率为。节点A的分组到达过程是速率为的Possion过程，分组长度服从指数分布，且与到达间隔相互独立。试问应如何在A和B之间的两条链路上分配业务流？

Kleinrock独立性近似假定采用两种方法：一是随机的方式（Randomization），即A通过扔硬币的方法来分配分组流；二是采用计量的方法（Metering），节点A将分组送入比特长度最短的队列（它等于各排队分组比特长度之和）。Kleinrock独立性近似在随机方式中，很容易证明L1和L2上的分组到达流都是Poisson流，且与分组长度无关。这样每一条链路都是到达率为

/2的M/M/1队列。利用M/M/1队列结果，可得分组的平均时延为这种情况与Kleinrock的独立性近似是一致的。Kleinrock独立性近似在计量的方式中，到达的分组进入比特长度最短的队列，这时系统相当于一个M/M/2的系统，总的到达率为，每条链路是一个服务员，利用前面的结果得分组的平均时延为式中，Kleinrock独立性近似采用计量的方法，可使时延减少到随机方式的1/(1+

），这也进一步反映了统计复用的好处。如果在实际系统中，要将一个比特流分解成几个可选的路由，应当采用计量的方法。但是，采用计量的方法，破坏了各个队列的Poisson特性，这时每条链路的到达间隔不再是指数分布，且与前面的分组长度相关。这时，我们看到，若采用M/M/1的近似，其准确度较差。上述例题说明，采用不同的服务法则，可能会影响采用Kleinrock独立性近似的准确度。

Burke定理Burke定理对具有到达率为的M/M/1，M/M/m,M/M/∞系统，假定系统开始时就处于稳态（或初始状态是根据稳态分布而选定的），有下列结论：系统的离开过程是速率为的Poisson过程。在时刻t,系统中顾客数独立于t时刻以前用户离开系统的时间序列。

Burke定理该定理说明了该类排队系统的两个特性：一是输出过程（或离开过程）仍服从Poisson过程；二是系统中当前顾客数与离开系统的顾客流之间的关系，它们之间相互独立。Burke定理我们可能会认为：系统最近有一个非常繁忙的离开流，意味着系统现在会有大量顾客在排队，是一个繁忙系统。然而，Burke定理表明这是不正确的，该定理指出一个繁忙的离开流，没有说明任何当前系统的状态信息。

Burke定理求解两个M/M/1队列串联后系统的状态概率。该系统的到达过程是到达率为的Poisson过程。这两个队列的服务时间相互独立（即相同的分组在两个节点的服务时间不同），服务时间与到达过程相互独立，

Burke定理由于队列1是M/M/1队列，因此在该队列中，用户数为n的概率为由Burke定理可知，队列1的输出是速率的Poisson过程，并根据假定知，队列2的服务时间与到达过程独立，因此队列2可以看成为孤立的M/M/1队列，因而有队列2中用户数为m的概率为Burke定理由Burke定理知，队列1当前的用户数与过去的离开过程相互独立，也就是与队列2的过去到达过程无关。所以,队列1当前的用户数与队列2当前的用户数无关。因此有：系统中队列1有n个用户，队列2有m个用户的概率为P{队列1中有n个用户，队列2中有m个用户}=P{队列1中用n个用户}

P{队列2中用m个用户}=Burke定理该公式告诉我们，两个串联的队列，只要满足独立性的要求，就可以看成是两个完全独立的具有相同到达率的M/M/1队列。Jackson定理Jackson定理由前面的讨论可知，当一个分组的到达过程通过网络的第一个队列以后，分组到达将与它们的长度相关。如果这种相关性可以消除或采用随机的方法将分组分成若干个不同的路由，那么系统中的平均分组数可以通过将网络中的每个队列看成是M/M/1队列而导出。这是Jackson定理的基本结果。Jackson定理Jackson定理说明了若排队网络满足下列两个条件：①进入网络的到达过程是Poisson过程；②各队列的服务时间是独立的指数分布，则在数值上系统的顾客数由k个独立的M/M/1队列决定。注意该定理并没有要求到达各队列的到达过程是独立的Poisson过程。Jackson定理求图所示计算机系统的总任务数N和任务的平均时延T。该系统是一个具有输入/输出（I/O）反馈的中心处理器（CPU）系统。任务到达过程是速率为的Poisson过程。假定所有的服务时间相互独立，包括相同的任务再次经过（CPU）和I/O的时间也是相互独立的。CPU处理完的任务以概率p1离开系统。Jackson定理Jackson定理Jackson定理Jackson定理Jackson定理

Jackson定理表明了在求解系统中的顾客数时，可以把系统看成k个独立的M/M/1队列。它要求进入网络的到达过程是Poisson过程，但是每一个队列的总到达过程不一定需要是Poisson过程。例如：如图所示，外部到达过程是速率为的Poisson过程，队列的服务速率Jackson定理Jackson定理经过队列的分组以1-p的概率离开系统。假定p接近于1。对于队列而言，当有一个到达后，将会以很大的概率，在很短的时间内又有一个到达（反馈到达）。对于网络而言，当有一个到达后，在很短的时间内又有新到达的概率非常小。也就是说，由于队列输出反馈到队列输入的概率很高，网络的一个到达，将触发队列有一批到达（或者说一个突发的到达串），显然，队列的到达间隔不是独立的，其总的到达过程不是Poisson到达。小结本章主要讨论了信息网络中常用的时延模型，这些模型常用于多种网络的性能分析和评估。首先讨论了排队系统中的基本定理

Little定理及其多种变形表示和应用。小结小结接着讨论了单一排队模型。包括两类排队模型：一类是M/M/1，M/M/m，