【文档说明】计算机网络-第2章课件新版.ppt，共(120)页，1.669 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76960.html

以下为本文档部分文字说明：

计算机网络第2章网络排队模型及其应用西南交通大学第2章网络排队模型及其应用•2.1排队模型概述•2.1.1网络性能指标•2.1.2排队模型•2.2M/M/1排队模型•2.2.1报文到达及发送过程•2.2.2排队系统参数分析•2.2.3利特尔定律•2.3M/D/1排队模型•2.4

计算机网络优化设计研究•2.4.1计算机网络设计问题•2.4.2计算机网络链路容量优化设计•2.4.3设计举例网络排队模型是计算机网络设计、建模、性能分析和预测的有力工具，经过近百年的发展，已建立起稳固的理论基础，并已成功地应

用于实际，解决了很多问题。本章介绍网络排队模型及其在计算机网络链路容量优化设计中的应用。•2.1排队模型概述•2.1.1网络性能指标•2.1.2排队模型•2.1.2.1排队系统•2.1.2.2排队系统的描述格式•2.1.2.

3计算机网络结点中的排队模型2.1.1网络性能指标常用来描述网络的性能指标有费用、时延、吞吐量及可靠性等，具体描述如下：•费用——满足一定技术要求（时延、吞吐量、可靠性等）下，费用尽可能小；•时延——各种报文在网中传输的平均时间（越小越好）；•吞吐量——单位时

间内，网络实际传输的报文量或数据单元数（与时延有关）；•可靠性——表现为网络的连通性。吞吐量相关概念：①=吞吐率（throughput）②S（网络能传输一个报文的时间内，实际传输的报文数，显然小于1），S在局域网中经常

被使用①②均是通信能力的利用率上述性能（费用、时延、吞吐量及可靠性等）与网络中各个节点处的排队有关（特别是时延、吞吐量等）。2.1.2排队模型2.1.2.1排队系统•排队系统可用图2-1所示的模型描述

图2-1排队系统模型在排队系统中，主要考虑的因素有：1）输入过程输入过程描述的是顾客到达过程的特性，用“到达间隔”（两个连续到达发生的时刻间的时间间隔）表示。主要的输入过程如下。•规则到达（不常见，自动线上、进料问题近似它）。•完全随机到达——Poisson（泊松）到达过程，到达间隔

为指数分布，各个间隔为相同分布而互相独立的随机变量，数学推演简单，也颇符合实际，被普遍采用；其到达是完全随机的，任何时刻，一个到达（一个事件）发生的机会完全相同，而两个或两个以上到达同时发生的可能性极低。一般相同而独立的到达也称为更新

到达过程，各个到达间隔为相互独立、相同分布的随机变量，但不一定是指数分布。正常情况下，机器故障常用这类假设。成批到达例：工厂、商店，一次性进货多件，到达的批量可以为常数，也可以为随机数。非平稳到达到达频率因时而异，如电话

、交通等，在上班时拥挤。依态到达到达频率依系统的状态而定，例如生意清淡的饭店，难以吸引顾客，高朋满座的地方也会使人不耐久侯而转往他家。连续到达流体就是连续到达的实例。在排队分析中，可把实际生活中的离散流假定为连续到达，如高速公路上车辆川流不息，数量庞大，因而可当成流体处理。2

)服务时间特性服务时间是随机变量。若a表示随机变量，x为随机变量的取值，则随机变量a的分布特性如下：连续随机变量的分布特性用分布函数描述：分布函数F（x）=P[a≤x]；离散随机变量的分布特性用分布律描述：分布律P（x）=P[a=x]。计算机网络中的报文长度分布的例子有常数分布、指数分布以及

别的分布。当服务机构的能力固定时，则服务时间的分布与报文长度的分布相同。3)排队规则排队规则分为等待制和损失制，进一步的区分如下：损失制：服务台不空，顾客自动离开，永不再来。例如，常用的损失制电话系统，一次呼叫，若不通，再拨，就视为另一次呼叫。2.1.2

.2排队系统的描述格式在排队论中，为了完整地描述排队模型，采用下述格式：A/B/C：D/E/F其中•A：顾客到达过程特性由于泊松过程是无记忆过程（Memoryless），因此，用M代表泊松过程（Poissio

n到达）。对于泊松过程，当t0时的状态确定后，t1时的状态就与t0前无关，就象微分方程的初值问题一样，微分方程的解与t0前状态无关。其到达间隔是指数分布的。E代表爱尔兰（Erlang）过程。Ek代表K阶爱尔兰过程，对于K阶爱尔兰输入，它的到达间隔相互独立，具有相同的K阶爱尔兰概率密度当

k=1，即为一阶爱尔兰过程E1，其概率密度就是Poission过程的概率密度，其到达间隔是指数分布的。•B：服务时间的分布函数M代表指数分布，意味着发送过程是泊松过程。G代表任意分布(General，一般）。D代表确定性分

布(Determinate有限、确定、固定)。•C：服务员数目•D：服务规则（排队规则）•E：缓冲器（buffer）容量•F：顾客来源容量其中，D、E、F三个参数一般省略不写，可用文字说明，不另说明，则是先来先服务、buffer无限、顾客来源无限。于是，M/M/1指的就是:泊松到达/服务时间为指

数分布/一个服务员。对排队系统，最重要的数量指标有三个：等待时间，忙期，队长。这些数量指标都是随机变量，在排队分析中，一般考虑其平均值（数学期望）。2.1.2.3计算机网络结点中的排队模型•当报文进入网络结点后，结点先要对报文进行缓冲处理，随后再转发。•通常情况下，网络结点（IMP，Route

r）对收到的报文进行缓冲处理（校验、拆包、选路、封包…）所需的时间可忽略。因此，报文在IMP中的排队时延tq，由等待线路空闲的时间（tw）和线路服务时间（ts，即发送时间）组成，即tw+ts=tq。•E（q）表示等待队长，E（n）表示平均队长[E（q）+正

服务的]。一般情况下，计算机网络结点中的排队模型如图2-2所示：图2-2计算机网络结点中的排队模型为简化排队模型，通常将(1)的一般情况（多入口，多出口）抽象成多个单入口，单出口的排队系统，如(2)所示，最后，讨论(2)中的单个简化的单入口、单出口排队系统，其简化模型

如(3)所示。•2.2M/M/1排队模型•2.2.1报文到达及发送过程•2.2.1.1随机过程概念•2.2.1.2M/M/1的到达及发送过程•2.2.2排队系统参数分析•2.2.3利特尔定律•2.2.3.1利特尔定律的表述•2.2.3.2利特尔定律的普遍适用性•2.2.3.3有用

的关系2.2.1报文到达及发送过程2.2.1.1随机过程概念•事物变化过程可分为两类，一类是确定性过程，另一类是随机过程。•确定性过程指的是，事物变化过程可用（一个或几个）时间t的函数描述。例如自由落体运动下落的距离

x（t）即可用下列时间t的函数描述：•随机过程指的是，事物变化过程不能用一个或几个（有限个）时间t的确定的函数加以描述。•换句话说，对事物变化的全过程进行一次观测的结果是一个时间t的函数，但对同一事物的变化过程独立地重复进行多次观测所得的结果是不相

同的（可以有无穷多个）。•例如，图2-3所示的热噪声电压就是一个随机过程。对热噪声电压变化的全过程进行一次观测的结果是一个时间t的函数，但对热噪声电压变化过程独立地重复进行多次观测所得的结果则是不相同的，可以有无穷多个时间t的函数。图2-3热噪声电压（随机过程

）泊松（Poisson）过程定义：•①在不相重迭的时间段内，事件的出现是相互独立的。即在不相重迭的各时间段中，事件出现互不影响，如图2-4所示。图2-4不相重迭时间段内事件的出现相互独立•②在充分小的时间段△t内，事件出现一次的概率

为λ△t，P1（t，t+△t）=P{N（t，t+△t）=1}=λ△t+O(△t)。其中：λ是泊松过程的强度（单位时间内事件出现次数的均值）；当△t→0时，O(△t)是关于△t的高阶无穷小；•③在充分小的时间段△t内，事件不出现的概率为（1-λ△t）。在充分小的时间段△t内，

不同次数出现所对应的事件是互斥的，即：P（0次+1次+2次+…）=（1-λ△t）（0次）+λ△t（1次）+…=1显然，在充分小的时间段△t内，事件出现一次以上的概率为0。称由泊松过程产生的流为Poisson流。Poisson过程的性质：•Poisson过程N（t），t≥0，λ>0为Pois

son过程N（t）的强度（常数），则在T>0时间段内，事件出现K次的概率为：P[N（0，T）=K]=PK（T）=K=0，1，2，…（2-1）)(!)(KPKTeKT2.2.1.2M/M/1的到达及发送过程M/M/1：报文到达是参数为λ（λ为每秒到达平均数）的泊松过

程（Poissonprocess），报文相继到达之间的间隔（是一个随机变量）服从指数分布：T内到达K个报文的概率是!)()(keTkPTkef)(它的概率密度是P[间隔≤]=1―=F（）e服务时间

服从参数为μ的指数分布（exponentialdistribution）：因为出线速率C是固定的，故服务时间的概率分布与报文长度的概率分布相同。当报文长是指数分布时，服务时间也就是指数分布。设为平均报文长，c为出线速率（即线路容量），为发送一个报文的平均时间，则μc是每秒平均发送的报文

个数，将c隐含在μ中，则μ就是每秒平均发送的报文个数。若一直有报文在连续地发送，则服务完毕之间的时间间隔就是服务时间，服从指数分布：1c1P[间隔（即相继服务完成之间的时间）≤ts]=1―=F（ts）tse其概率密度是：f（ts）=tse

dtstsdF)(注意：图2-5显示了这样的一个M/M/1模型。报文平均到达率为λ（报文/秒），线路容量为C（比特/秒），平均报文长为1/μ（比特/报文）。图2-5一个M/M/1模型令ρ==csbit

messagebitsmessage///ρ（0≤ρ<1，无量纲）表示线路发送能力被利用的程度。通常称ρ为线路利用率、报文密度系数,也称为通信量强度或业务量强度。泊松到达过程的特性（也适用于泊松服务过程）：

001!)()(kkTTkTeekTekp（2-2）①②设k为时间T内到达个数（随机变量），则k的数学期望E（k）为：00!)()()(kkTkekTkkkPkE

111)!1()()!1()(kkTkTkkTTekeT=（设k-1=n，当k=1，则n=0）TeTenTTeTTnnT0!)(=单位时间内的平均值为，λ就是报文的平均到达率。TkE)(③方差（Variance

）22)]([kEkEkTTTTk222)()(（2-4）④!)()(keTkPTkk=0，1，2，…（2-1）证明：基于Poisson过程的三个定义条件（见2.2.1.1）。详细过程从略⑤

报文相继到达之间的时间（间隔），是指数分布的随机变量，其概率密度函数为：ef)(0证明：考虑图2-7所示报文到达间隔≤的情况：图2-7报文到达间隔≤的情况报文到达间隔（随机变量）的概率分布为：间隔≤]=P[0，之间有到达][)(PF=1―P[0，之间无到

达]=1―e则eddFf)()(﹟证毕⑥服务时间的分布泊松到达过程与指数间隔之间的紧密联系可以用于讨论指数服务时间分布的性质。M/M/1的到达过程，λ指单位时间平均到达个数；指报文到达间隔平均值

；到达间隔的概率密度：。M/M/1的发送（输出）过程如图2-8所示。1ef)(图2-8M/M/1的发送（输出）过程图2-8中，r为输出完成之间的时间（随机变量），只要服务一个接一个地进行，这就是服务时间（假定有大量的报文要发，无空闲）。与⑤对比，报文相继到达的时间为指数分布

，平均值1/λ，到达间隔的概率密度为:ef)(在M/M/1的发送（输出）过程中，服务时间r是指数分布，设平均值为E（r）=（c隐含在其中），1所以服务时间的概率密度：f（r）=rer≥0。已知，到达之间的间隔服从指数分布，且到达是Poisson过程（⑤）。将M/M/1的到达过程

（⑤）与M/M/1的发送（输出）过程比较，因为输出完成之间的时间r也服从指数分布，易知：服务完成的发生必定代表一个Poisson过程，即发送报文的过程也是Poisson过程，故可以得出结论：一个随机过程是Poisson过程的充要条件是，该随机

过程中事件发生的间隔是指数分布。即在M/M/1模型中，把对每个报文的服务完成看作一个事件的发生，服务时间服从参数为μ的指数分布（即事件发生的间隔是指数分布），则这个过程就是一个泊松过程，即M/M/1中，发送过程（服务

、输出）也是Poisson过程。⑦泊松过程的另一性质Poisson的合流仍然保持poisson性质，这个性质很重要，即Poisson流的合流还是Poisson流。Poisson流分割开，每个子流也还是Poisson流。在一个网络中，有多个结点、也有多条链

路，在每一个节点都要进行路由选择，于是报文流会不断分合，如图2-9所示。图2-9网络中流的分合2.2.2排队系统参数分析以下仅对无限缓冲区容量的M/M/l排队系统进行参数分析1）M/M/l模型的平衡方程M/M/l排队系统模型如图(1)所示，到达（）过程、发送（，隐含c）过程都是p

oisson过程。排队时延（等待（等人家服务完）+服务（自己被服务的时间））=队长（n）·服务时间+服务时间(2-7)式(2-7)中，自己被服务的时间指到达的这个报文的服务时间，在排队论中，取平均值（服务时间）；队长指一个报文到达时看到的系统中的

报文个数，其值为（等待的+正服务的）。•设时刻，排队系统中有n个报文（等待的+正发送的），其概率为。从t到，状态转移的发生有三种可能的情况（互不相容，概率加），模型如图（2）所示。tt)(ttPntt发送和接收均为Poisson过程，当时，内事件最多发生一次,可得:0

tt11()()[(1)]()[(1)(1)]()[(1)]nnnnpttptttptttttpttt•，及以上项是的高阶无穷小量，可略去，得•移到左边，两边同除以，可得

0t2)(tt11()[1()]()()()nnnnptttpttpttpt)(tPnt)()()()()()(11tPtptpttpttpnnnnn

•因为，•上式可写为0t)()()()()(11tPtPtPdttdPnnnn)()()()()()(11tPtptpttpttpnnnnn•当（即运行了很长时间

），系统将趋于稳定（进入平衡状态），则有极限（常数），可得。•因此，t时，可用Pn代替下式中的,•可得：（2-8）•式（2-8）就是M/M/l模型的平衡方程。,t)(tPn0)(dttdPn)(tPn11()nnnPPP)()()()()(11tPtPtPdttd

Pnnnn2）M/M/l模型平衡方程的物理解释（2-8）（2-8）式左边是由于发送（速率）和到达（速率）而使排队系统离开状态n的速率；（2-8）右边是由于发送和到达而使排队系统从状态n

+1和n-1进入状态n的速率。稳态下，Pn是常数（与t无关，即系统处于n状态的概率是一个常数），所以，上述两个速率必然相等（（2-8）等号两边表达式的值相等）。（2-8）式称为M/M/l模型的平衡方程。M/M/l又称为生（到达）死（离开）过程（服务员数可大

于1）。11)(nnnPPP•以上推导的基础是，到达和发送都是Poisson过程，当时，事件（生或死）要么发生1次（概率为或），要么发生0次（概率为或）。0tttt1t1可以用下面的状态转移图表示M/M/l模型。在n状态周围作一个闭合曲面S，则（2-8

）式左边=离开曲面S的速率；右边=进入曲面S的速率。今后，我们可以画出状态转移图，直接写出（2-8）式。像（2-8）式这样的平衡方程在排队系统研究中起着关键作用。11)(nnnPPP（2-8）•3)解M/M/l模型的平衡方程解（2-8）式，求平衡状态（稳定状态

）下的各个概率（系统处于各种状态的概率均为常数）。为此，在图2-11中作一系列闭合曲面11)(nnnPPP•第1次作的曲面，包围0，…，n共n+1个状态，离开与进入的速率相等：•第2次作的曲面，包围0，…，n-1共

n个状态，进入与离开的速率相等：•……第n次作的曲面，包围0，1共2个状态，进入与离开的速率相等：•第n+1次作的曲面，包围0这1个状态，进入与离开的速率相等：1nnPP1nnPP21PP10PP得生死过程平稳解的求解公式：1n

nPP1nnPP12PP01PP求解各概率只需这n个方程第一、二式两边相加得（2-8）式，所以，此求解公式是满足（2-8）式的11)(nnnPPP（2-8）•解（从1到n）：从可得

从可得从可得，将上述结果依次代入，可得：注意：μ隐含c。01PP01PP12PP020212PPPPPP1nnPPppnn1nnpp0所以0PPnn20001(1)1nnnbuffer

PPP容量无限10PnnP)1(nnpp0因为平均队长为：1)1(3322)

1(3)1(2)1(10)(23243322320nnnPnE平均时延为：()()()ETEwEts111111)11(11)(nE)()(TEnE平均等待时间为：)(111)()(

nEwE2.2.3利特尔定律•2.2.3.1利特尔定律的表述•2.2.3.2利特尔定律的普遍适用性•2.2.3.3有用的关系2.2.3.1利特尔定律的表述有如下图所示的边界为封闭曲面的网络，报文流（报文长度分布无限制）随机地进入网络并

在接受服务以后离开网络。利特尔（little）定律给出了在稳定状态下，网络中暂时存储的报文数目N和报文的平均到达率λ以及这些报文在网络中经历的平均时间T之间的关系：N＝λT（2-9）更一般化，可以把报文看成顾客，把报文数

目N看成顾客平均排队长度，把网络看成排队服务系统。首先可以直观地论证利特尔定律。若系统中平均有N个顾客，则在长L个单位的时间段内，所有N个顾客在系统中停留的总时间为LN个单位时间。再假定每单位时间平均有λ个顾客进入，且平均在系统中停留T个单位时间。则L单位时间进入的全部顾客在系统中停留的总时间，

就等于LλT个单位时间。注意到，该L单位时间进入的顾客不一定都能在同一时间段内全部离开，即有些顾客在系统中的时间尚未计完。但肯定也有在此L个单位时间前面进入的顾客，会因在本L个单位时间段内停留期满而离开。因为利特

尔定律考虑的是系统处于稳定状态，所以上述跨时间段（长L）顾客的影响可互相抵消平衡。于是LN=LλT，故得关系式N=λT。顾客进入和离开排队服务系统的模型以下，对利特尔定律给予简要的推导。设在时刻t＝0时，系统处于初始状态，存在于系统中

的顾客数目为0。又设在时间间隔（0，t）内进入系统的顾客数目为I(t)，离开系统的顾客数目为O(t)。则在时刻t时，系统中的排队长度为：N(t)＝I(t)一O(t)（2-10）在时间间隔（0，t）内，顾客的平均到达率记为λt：

λt＝I(t)/t（2-11）•在时间间隔（0，t）内，所有的顾客在系统中已经经历的时间为Ta（t），它等于曲线I(t)和O(t)之间的面积：Ta（t）＝N（x）dx（2-12）0t在时间间隔（0，t

）内，系统中的平均顾客数目Nt为：Nt＝Ta（t）／t＝{N（x）dx}／t（2-13）0t•在时间间隔（0，t）内，每个顾客在系统中已经经历的平均时间为：Tt＝Ta（t）／I(t)（2-14）•由式（2-11），（2-13）和（2-14）λt＝I(t)/t

（2-11）Nt＝Ta（t）／t＝{N（x）dx}／t（2-13）Tt＝Ta（t）／I(t)（2-14）可得：Nt＝Ta（t）／t＝{Ta（t）／I(t)}{I(t)/t}＝Tt·λt（2-15）0t因为系统是稳定的

，当t→∞时，系统将进入稳定状态，则（0，t）间诸平均值Nt、Tt和λt都有极限。设：λ＝λt，T＝Tt，N＝Nt由（2-15）Nt＝Tt·λtN＝Nt＝Tt·λt＝λt·Tt＝λT•即：N＝λT（2-9）tlimtlimtlimtlimtlimtlimtl

im这就是著名的利特尔定律：N＝λT利特尔定律指出，在稳定状态（也称为在统计平衡条件）下，系统中的平均顾客数目等于顾客的平均到达率乘以这些顾客在系统中经历的平均时间。2.2.3.2利特尔定律的普遍适用性•适用于所有类型的排队系统，也适用于排队系统的一部分。•排队系

统的边界是可以任意设定的，只要N、λ、T属于同一个排队系统即可。•顾客的到达和服务时间的分布规律都没有限制。•排队系统内部结构也没有限制。•注意：进入系统的顾客最终都要被服务，不溢出，即缓冲区(buffer)的容量要足够大。将利特尔定律应用于M/M/l排队模型：整个M/M/l排队：平均时

延等待部分：平等待均时延平均等待队长Ｅ(q)=E(n)－其中，E(q)：等待队长，E(n)：总队长，：正在接受服务的顾客平均数。1)()(nETE1)()()()(wEtsEwETE)(111)()(T

EwE22()()()()111EqEwETEn•服务机构（注意，没有M/M/l限制）因为要么有一个报文正在发送（顾客正在接受服务），要么没有顾客正在接受服务（服务机构空闲）。所以平均正在接受服务的顾客数（即服务

机构中的平均队长）小于１。t时，系统进入稳定状态。因为进入buffer的报文都要被服务，所以最终进入服务机构的报文流，其平均到达率也是。可以直接引用利特尔定律：服务机构中的平均队长＝λ（1/μ）＝ρ。•再从前

面M/M/l的分析结果看服务机构：•Ｐ｛服务机构中队长＝０｝＝Ｐ｛整个排队系统队长＝０｝（buffer中无报文等待，服务机构不工作）＝＝１－•Ｐ｛有顾客正在接受服务｝＝Ｐ｛服务机构中有一个顾客｝＝Ｐ｛整个排队系统队长>0｝（1，

2，3，…，∞都属于此情况）＝１－Ｐ｛整个排队系统队长＝０｝＝１－0P0P•服务机构中的平均队长＝０·Ｐ｛服务机构中队长＝０｝＋１·Ｐ｛服务机构中有一个顾客｝＝•上述M/M/l排队的结果：，可以一般化到任何单服务员的排队（beworkconserving(恒定工作的队)：

只要有需要服务的顾客，这个顾客就将被服务，并且顾客一旦进入系统，不会被拒绝)。•从Ｅ(q)=E(n)－，可见，总是正在被服务的平均数，总是对的。110P10P•[例2-1]某校有1万名学生，每个学生平

均在校学习4年，即N＝10000，T＝4。则λ＝N/T＝2500，即平均每年2500新生入校、2500学生毕业离校（每个学生都要被服务，即得到所有教学环节的训练，不会溢出）。•[例2-2]．平均有10个工件在某流水线上，每小时有4个工件进入该流水线。则N＝10、λ＝4，T＝1

0/4＝2.5，即每个工件平均2.5小时才能加工完成。[例2-3]．图书馆平均每天借出5000册书，每册书的平均借期为60天。图书馆原有藏书100万册。则λ＝5000册/日，T＝60天，N＝Tλ＝30万册（所有读者构成一个排队系

统），即平均有70万册留在书库中。•“规模经济性”（economyofscale）原理：当资源与用户数目同时按比例增长时，在一定范围内（资源与用户数目趋于无穷大的情况不在讨论之列），规模越大越经济。•例2-4]．分组交换网中所有信道（链路、线路）容量加倍，每个用户的数据量也加

倍。采用固定路径，从任何结点进入的报文流均为泊松流，具有相同的负指数长度分布，平均长1/μ。这是M/M/1模型，计算结果如下表。•即全网平均时延减半。[例2-5]．设公用电话通话的持续时间平均为3分钟，一个人等待打电话的平均忍耐时间也是3分钟。求一个公用电话可以支持的最大呼叫量。•[例

2-6]分别用①、②、③、④、⑤标记的5条单向传输数据的链路A→B、B→C、C→D、D→A、A→C（“→”方向即为该链路的数据传输方向），构成一分布式网络。各结点的输入报文流均相等，γA=γB=γC=γD=3/秒，都平均发往另外3个结点，γA、γB、γC

和γD均为泊松流；报文长均为负指数分布，其平均报文长均相等，1/μA=1/μB=1/μC=1/μD=1000bit；规定报文流均沿最短路径传送；各链路容量均相等，C1=C2=C3=C4=C5=7000bps(bit/s)。•1)求各链路报文到达

率：λ1、λ2、λ3、λ4和λ5；•2)求各链路报文流的平均时延：E(T1)、E(T2)、E(T3)、E(T4)、E(T5)（忽略信号在介质上的传播时间）；•3)求全网平均时延E(T)（忽略信号在介质上的传播时间）；解：本题的网络模型如下图所示：ABCDAB

CD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流1)各链路报文到达率：λ1=λ2=λ5=3/秒，λ3=λ4=6/秒；ABCDABCD①②③④⑤

γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流2)由题目条件知，各链路排队系统均为M/M/1模型，故各链路平均排队时延为：E(Ti)=1/(μi

Ci-λi)因为：C1=C2=C3=C4=C5=7000bps；1/μA=1/μB=1/μC=1/μD=1000bit；且λ1=λ2=λ5=3/秒，故：E(T1)=E(T2)=E(T5)=1/[（7000/1000）—3]=0.25秒

而λ3=λ4=6/秒；故：E(T3)=E(T4)=1/[（7000/1000）—6]=1秒3)由利特尔定律求各链队长:E(Ni)=λiE(Ti)E(N1)=E(N2)=E(N5)=3/秒×0.25秒=0.75E(N3)=E(N4)=6/秒×1秒=6全网队长（忽略信号在介质上的传播时

间）:E(N)=E(Ni)=0.75×3＋6×2=14.25全网报文到达率:γ=γA＋γB＋γC＋γD=12/秒由利特尔定律得全网平均时延:E(T)=E(N)/γ=14.25/12秒=1.1875秒ABCDABCD①②③④⑤γAγCγBγDACDABC

DγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流i2.2.3.3在M/M/1排队模型中若干有用的关系2.3M/D/1排队模型•本节直接引用M/G/1排队模型的结论，下标e表示M/M/1排

队模型（指数分布服务时间）：•平均队长（2-20）•平均等待队长（2-21）•平均时延（2-22）•平均等待时间2().()1eEnAEqAAqEqEe)()(AwEtETEes)()()(A

wEwEe)()(（2-23）•A是表示一般服务时间（G）与指数分布服务时间相差程度的一个系数，称为修正系数。（2-24）•M/D/1是M/G/1的特例，服务时间是常数，。因为服务时间是常数，所以也是常数，,。∴•修正系数A为：}1])({[

212ststEActs12st22()ssEttssttE)(22222()[()]0tsssssEtEttt21}1])({[212ststEA将A代入Ｍ/G/1表达式求Ｍ/D/1的各个参数：•平均队长（2-25）•平均等

待队长（2-26）•平均时延（2-27）•平均等待时间（2-28）)1(2)2()1(222111)(222AnE)1(2211)()(22

AqEqEe)1(22)1(22221)1(1)()()(AwEtETEes)1(221)1()()(AwEwEe2.4计算机网络优化设计研究2.4.1计算机网络设计问题2.4.2计算机网络链

路容量优化计2.4.3设计举例2.4.1计算机网络设计问题•计算机网络由六元组(D,L,C,λ,γ,T)确定•其中D是构造这个网络的总费用(代价)，主要是结点和链路的费用。–结点处设置的通信处理机购置费用一次性投入，费用下降快；–结点间的链路(即信道)的建设和维护运行费用则相对较大，且在网络运

行过程中持续投入。•因此，在网络设计中，一般把链路的总费用就看成网络的总费用。•L代表网络的拓扑结构,即结点和链路的构形，应该在哪些位置配置结点设备，各结点间应该有哪些链路。为了保证达到一定的可靠性，还需要考虑整个拓朴图的连通

性，考虑结点缓冲区大小的选定。–由于大大小小的中心城市在人类的社会、政治、经济活动中自然地形成了信息集中和分配的枢纽，这些城市也自然地成为了通信处理机所在结点的位置。剩下的问题就是哪些结点间应该有链路相连。•因此,我们考

虑网络拓扑结构时，不再着重考虑结点位置的确定，而是假定结点位置已经确定的情况下，哪些结点间应该用链路连接起来。•C代表网络各条链路的容量Ci，（i=1，2，…，N。N为全网链路数）。•λ代表分配到网络中各条链路上的报文流量λi(i的含义同前)，涉及到网络中的路由选择、流

量分配以及拥塞控制和避免死锁的措施等。•γ代表全网络的吞吐率,即单位时间通过网络的报文流量，涉及各报文流进入及离开网络的位置以及每个报文流的大小。•T代表网络的平均时延，一般表示端到端的传输时间，为简

化计，经常表示的是端到端的链路排队时延。•设计计算机网络，就是要确定这个六元组。由于六元组中的很多元素都是由多个分量构成。因此确定这个六元组是一个极为复杂的问题。•为了简化计算机网络的设计问题，采用突出主要因素、忽略次要因素的方法，可将计算机网络的设计问

题简化成为几个规划问题。•那么，我们现在主要应该关心什么问题呢？我们希望通过对当前实际情况的分析来回答这个问题。•在当前社会急剧信息化的过程中，大大小小的中心城市形成了信息集中和分配的枢纽，成为数据网结点所在地，结点间以数据信道互连构成了数据网。•由于光纤的广

泛铺设，光通信技术的迅速发展和实用化，信道容量越来越大，任何需互连的结点对间要分配直通信道已不再困难。•因此，当前的数据网在拓扑（结点链路的构形）上大体是稳定的，信息传输的路径大体上是稳定的，可经由直达的或最近的路径，网络结点的位置也是大体固定的。•只要社会的人口、资源、产业布局大

体稳定，公用数据网络的拓扑结构相对而言就是稳定的，而需要解决的主要问题是在满足一定的约束（例如时延）条件下，网络的能力配置需求。•对于公用数据网的建设经营者，要解决连接各结点的链路容量以及结点机的处理能力（单位时

间处理分组的个数、数据端口数、缓冲区大小等），以满足社会需求；•对于基于公用数据网的信息系统的建设、管理及使用者，要解决的则是本信息系统所需使用的信道容量。•两者都有一个共同的目的，那就是既能提供满意的服务，又不浪费资源。•因为通信信道的建设和维护是更耗费资源的，理应充分利用信道能力，不使其虚耗，

因而计算机网络链路容量需求的优化设计就应该是我们主要关心的问题。2.4.2计算机网络链路容量优化设计•给定一个计算机网络，可以是为社会提供公共承载服务的公用数据网，也可以是一个企业或政府机构基于公用数据网上的一个信息系统。•前者的吞吐率

γ是使用这个公用数据网的所有用户总的报文流量，•后者的γ则是该企业或该政府机构内使用这个信息系统的全体用户的总的报文流量。•设所有报文源产生的报文流都是Poison流，由Poison流的性质知全网各链路上到达的报文流也都是Poison流。•设各报文源产生的报文流都

是负指数长度分布，其平均长度为１/μ。显然，各链路服务时间的分布也都是负指数分布。•由此可知，全网所有链路的排队系统都是M/M/１模型。•采用某种确定的路由算法，则各链的报文流量（即报文到达率）λi(i=1，2，…，N)是确定的。•网络拓扑是确定

的。要求全网的平均时延不超过T。•Ci为i链的容量，Ki为i链的费率，则全网的链路总费用为：（2-29）•问题是，在全网平均时延不超过T的约束下，求使全网链路总费用D最小的链路容量Ci,i=1，2，…，N。这是一个非线性规划问题：•目标函数：（2-30）•约束条件

：（2-31）（2-32）NiiiCKD1NiiiCKcMinD1)(0)]/([)/1()(11TCcgiiiNi0iiC•因为第二个约束条件在第一个约束条件中自动满足，所以上

述非线性规划可写成：•目标函数：（2-33）•约束条件：（2-34）NiiiCKcMinD1)(0)]/([)/1()(11TCcgiiiNi•可以证明D(C)是凸函数、g1(c)也是凸函数，则库恩―图克（Kuhn-Tucker）条件为D(C)取极

值的必要及充分条件[13]。设满足库恩――图克条件的点为C*，C*是本问题的K—T点，则C*是极值点。•因为D(C)和g1(c)在其定义域内是连续可微的，C*在D(C)和g1(c)的定义域内，故D(C)和g1(c)在C*处是连续可微的，已知D(C)是凸函数，g1(c)

也是凸函数，本非线性规划问题的可行点C*满足K－T条件，因此C*是上述非线性规划的整体最优解[14]。•所以，只要求出(2-33)、(2-34)式确定的非线性规划的K－T点C*，C*就是这个非线性规划的整体最优解。•求K－T点C*如下：•因为C*是非线性规划(

2-33)、(2-34)的极值点，则存在实数θ*使下述条件成立：(2-35)(2-36)(2-37)•将(2-33)、(2-34)代入上面三式并改写为：i=1，2，…，N(2-38)(2-39)(2-37)0)(1)(***

CgCD0)(1**Cg0*iiiKiC2)*(*0***1NiiiiCT0*•从(2-38)可得i=1，2，...，N(2-40)•将(2-40)代入(2-39)(2-41)•从（2-41）解出：(2-42)•于是得(2-33)、(

2-34)确定的非线性规划的整体最优解由(2-40)、(2-42)两式确定。iiKiCi**0***1NiiiiiiKT211)(*2NiiiTK2.4.3设计举例以一个基于公用数据网的信息系统为例，该

信息系统租用公用数据网的信道作为自己的链路以构成该计算机网。如图所示，A是中心结点，B、C、D分别是一、二、三级结点，将B、C、D连接到上一级结点的链路分别是一、二、三级链路。A连接10个一级结点，一级结点连接５个二级结点，二级结点连接30个三级结点。三级结点是信息源点

，来自各个源点的数据均需送到中心结点A。为简化计算，设进入各个三级结点的报文流都相等，为１报文／秒，则全网的吞吐率γ=1×30×5×10=1500报文／秒。一级、二级、三级链路上的报文流量分别是λ１＝150报文／秒，λ２＝30报文／秒，λ

３＝１报文／秒。T=0.1秒／报文。设所有报文等长，１／μ＝1000比特／报文。一、二、三级链路的费率分别是K1＝0.8，K2=1.0，K3=3.0，单位均为：货币单位／（比特／秒）×月。考虑到此例的中心对称性，只要计算从

中心结点A连接某一个一级结点（例如B）的一个树枝即可反映全网的情况。[例2-8]链路级iCi*(kbps)ΣDi*(货币单位／月)Ti*（秒／报文）１422.170，83，377，366.40.003，674２138.8686，943，400

0.009，185，4３12.47556，137，5000.087，145，9表2-2优化结果全网链路总费用D*=66,458,266.4(货币单位／月)全网平均时延T*=0.100,005,3（秒／报文）从表2-2可见，全网链路费用主要集中在三级链路上，而三级链

路的时延则对全网平均时延起决定作用。计算精度在容许范围内。ABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流[例2-9]•分别用①、②、③、④、⑤标记的5条单向传

输数据的链路A→B、B→C、C→D、D→A、A→C（“→”方向即为该链路的数据传输方向），构成一分布式网络。ABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流•各结点的输入

报文流均相等，γA=γB=γC=γD=3/秒，都平均发往另外3个结点，γA、γB、γC和γD均为泊松流；ABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上

的报文流•报文长均为负指数分布，其平均报文长均相等，1/μA=1/μB=1/μC=1/μD=1000bit；规定报文流均沿最短路径传送；设K1＝K2＝K3＝K4＝K5＝1；•T＝10ms。ABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络

拓扑图(b)网络中的两个环(c)各链路上的报文流•在全网平均时延不超过T的约束下，求使全网链路总费用D最小的链路容量Ci(即优化的链路容量，i=1、2、3、4、5)。ABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网

络中的两个环(c)各链路上的报文流•解：各链路报文到达率：λ1=λ2=λ5=3/秒，λ3=λ4=6/秒；γ=γA＋γB＋γC＋γD=12/秒=（1/（12×（10×10-3）2））×（3×（3×1,000）1/2＋2×（6×

1,000）1/2）2=8,493×104（bit/秒2）ABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流2211*()NiiTiKABCDABCD①②③④⑤γAγCγ

BγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流•则在全网平均时延不超过T=10ms的约束下，使全网链路总费用D最小的链路容量Ci为：**iiiCiKABCDABCD①②③④⑤γAγCγBγDACDABCDγAγ

CγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流•C1=C2=C5=3×1，000+（8,493×104×3×1,000/12）1/2=3，000+（2，123.16×107）1/2=3，000+145.71×103=148,

710bit/秒**iiiCiKABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流•C3=C4=6×1，000+（8,493×104×6×1,000/12）1/2=6，000+（2×2，123.16×1

07）1/2=6，000+206.066×103=212,066bit/秒**iiiCiKABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的

报文流•验算:•E(T1)=E(T2)=E(T5)=1/[（148,710/1000）—3]=0.006,86秒•E(T3)=E(T4)=1/[（212,066/1000）—6]=0.004,85秒E(Ti)=1/(μiCi—λi)ABCDABCD①②③④⑤γAγCγ

BγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流•E(Ni)=λiE(Ti)•E(N1)=E(N2)=E(N5)=3/秒×0.006，86秒=0.020，58•E(N3)=E(N4)=6/秒×0.004，85秒=0.029，1•E(N)=E(Ni)=0

.020，58×3+0.029，1×2=0.061，74+0.058，2=0.119，94iABCDABCD①②③④⑤γAγCγBγDACDABCDγAγCγBγD(a)网络拓扑图(b)网络中的两个环(c)各链路上的报文流•E(T)=E(N)/γ=0.119，94/（12/秒

）=0.009，995秒=9.995ms﹤T=10ms。•验算结果表明，所求得的链路容量Ci满足全网平均时延不超过T=10ms的约束。本节提出的计算机网络链路容量优化设计方法可解决对全网平均时延限定一个界限值的情况下，求解使全网链路总费用D最小的链路容量Ci,(i=

1,2,…,N)。算法简单，计算复杂性低，可方便地用于计算机网络的设计，能求得最优解。本算法既可用于集中式网的优化设计，也可用于分布式网的优化设计。•以下问题还需进一步研究：•对链路费用不与容量成正比情况的处理，

•对链路容量只取离散值情况的处理；•对网中报文流各种统计特征和排队模型以及网络时延的深入研究，例如同时考虑结点机的处理时间、考虑C/S模式下事务处理的响应时间等。