计算机网络2章习题及参考答案(20080719)

第2章 网络排队模型和自相似通信量1泊松过程的报文到达间隔是连续随机变量，它的概率分布为： F（t）1一e一t 则到达时间间隔的概率密度函数为： （t） d F（t）/ dt e一t 这是负指数的概率密度函数。到达间隔是负指数分布的连续随机变量。证明，平均到达时间间隔: a1t （t）dt 1/ 答案：用分部积分证明a1E ( t ) t （t）dt te一t dt t d e一t t e一t e一t dt 0 + e一t dt 1/ e一t d（t） 1/ d e一t 1/ e一t 1/（ 0 1 ） 1/2条件同1题，证明，到达时间间隔的方差为：a2 t 2 （t）dt a12 1/2 答案：证明a2 E( t 2 ) E 2 ( t ) t 2 （t）dt 1/2 上式第一项（采用分部积分） t 2 （t）dt t 2 e一tdt t 2 de一t t 2 e一t e一t d t 2 0 +e一t d t 2 2 t e一t d t 2/ t d e一t 2/t e一t e一t d t 2/（ 0 e一t d t ） 2/e一t d t 2/（1/）2/2所以a2 E( t 2 ) E 2 ( t ) t 2 （t）dt 1/2 2/21/2 1/23分组交换网中所有信道（链路、线路）容量加倍，也使用户数加倍（假定每个用户所在位置添一个用户，从同一个结点入网，其数据的目的地也与该位置原来那个用户的目的地相同），每个用户的数据量不变。采用固定路径（新添用户的报文路径与该位置原来那个用户的报文路径相同），从任何结点进入的报文流均为泊松流，具有相同的负指数长度分布，平均长1/。计算前后两种情况下全网平均时延间的关系。答案：这是一个M/M/1模型。计算结果如表2-1：表2-1：先前当前i链服务率C i /(1/)= C i2C i /(1/)= 2C ii链报文到达率i2i全网报文到达率2全网平均时延E(T)=E(N) / i链平均时延E(T i )=1/(C i -i)i链队长E(N i ) =i E(T i )=i /(C i -i)E(N) = E(N i )E(T)=E(N) / i链平均时延E(T i ) =1/(2C i -2i)=0.5 E(T i )i链队长E(N i ) =2i(0.5)E(T i )= E(N i )E(N) = E(N i )= E(N i ) = E(N)E(T)=E(N) / 2= 0.5E(T)即全网平均时延减半。4分组交换网中所有信道（链路、线路）容量增加到原来的N倍，用户数也增加到原来的N倍（假定每个用户所在位置添N一1个用户，从同一个结点入网，其数据的目的地也与该位置原来那个用户的目的地相同），每个用户的数据量不变。采用固定路径（新添用户的报文路径与该位置原来那个用户的报文路径相同），从任何结点进入的报文流均为泊松流，具有相同的负指数长度分布，平均长1/。计算前后两种情况下全网平均时延间的关系。答案：这是一个M/M/1模型。计算结果如表2-2：表2-2：先前当前i链服务率C i /(1/)= C iNC i /(1/)= NC ii链报文到达率iNi全网报文到达率N全网平均时延E(T)=E(N) / i链平均时延E(T i )=1/(C i -i)i链队长E(N i ) =i E(T i )=i /(C i -i)E(N) = E(N i )E(T)=E(N) / i链平均时延E(T i ) =1/(NC i - Ni)= E(T i ) /Ni链队长E(N i ) = Ni E(T i ) /N= E(N i )E(N) = E(N i )= E(N i ) = E(N)E(T)=E(N) / N= E(N) / N= E(T) /N即全网平均时延减小到原来的1/N。5假定报文输入是泊松过程，报文的平均到达率为，平均长度为1，但报文长度分布规律则是任意的（服务机构的能力是稳定的，因此，服务时间的分布与报文长度分布特性相同）。输出信道只有一个（一个服务机构），其容量为C。A是在一个报文的发送 ( 服务 ) 时间Y内，报文的到达数目。A是一个随机变量，A2是随机变量A的函数。 证明：m E A2 / Y Y 2 Y 2 答案：证明如下m E A2 / Y Y eY 其中Y eY又其中Y Y eYeY1 注：e x 1+x+x2/2!+x3/3!+xn/n!+ ( x 49小时。9一个M/M/1排队系统，把服务台本身和等候使用服务台的队列当作两个单独的服务系统。用利特尔公式说明=/和等待队长，其中隐含C。答案：设M/M/1排队系统参数为，（隐含C），如图2-2所示| | |E(T) | 图2-2 M/M/1排队系统对服务台，其模型如图2-3所示：| E(ns) |E(Ts) |图2-3 服务台模型：平均到达率仍为（所有报文都要服务），平均队长E(ns)，平均排队时延为E(Ts),服务机构内无存储器，故，排队时延 = 服务时间 = 1/,考虑利特尔定律的普适性：E(ns) =E(Ts) = /,：以I(t)=1表示服务台忙，即服务台有一个报文；以I(t)=0表示服务台闲，即服务台无报文，如图2-4所示： 图2-4 服务台的忙期和闲期于是：表示(0t，服务台的有效工作时间) =(0t，服务台有一个报文存在的时间)而则表示（0t，服务台的利用率） =（0t，服务台中的平均队长）最后 则表示（服务台平均利用率）=（服务台平均队长E(ns)，其值已在求到，为/）即=/考虑等待使用服务台的队列，如图2-5所示： Q E（w）图2-5 等待使用服务台的队列平均队长Q = E(n) - = E(T) = 其中E(n) 为M/M/1平均队长， E(T)为M/M/1平均排队时延。10一个港口，船的装卸时间为指数分布，平均h，船的到达率为0.25/h，到达为泊松过程，M/M/1。装卸(服务)时间概率密度为：.一支船到达时，要求小时以上服务时间的概率是多少？.在港口中等待装卸的队长是多少？答案：依题意可得： h，0.25 /h 服务时间分布平均排队时延（从到港至装卸完）h于是，一只船到达时，要求小时以上服务时间的概率是：在港口中等待装卸的队长是：11设船到码头，在港停留一小时损失C1 元，服务费用正比于服务（装卸船）率，每小时C2 元，进港船只是泊松流，参数为，装卸时间服从参数为的负指数分布。求使整个系统总费用最小的服务率。答案：系统模型如图2-6所示： 港 口 入 图2-6 系统模型顾客（船东）这是考虑整个排队系统服务机构（港口）求使双方总费用最小的最优策略（服务率）。单位服务率是一小时C2元，即若港口每小时可装卸完一条船，此种服务能力，一小时价值C2元。参考计算机网络中的参数含义，1/（比特/报文），1/(c)=(比特/报文)(秒/比)=秒/报文，若隐含服务能力C，则1/(c)就可表示为1/；类似的，港口参数含义如下：1/(小时/船)（隐含港口服务能力C）， 则(船/小时)即为港口每小时可装卸船数。平均队长E(n)=/(1-)=/(-) 每小时船方损失费用 c1/(-)元每小时服务机构(港口)费用c2 ， 每小时总费用 F=c1 /(-) +c2. 令dF/d= -c1/(-)2 + c2 = 0可求出极值点 *=+ 因为d2F/d2=2C1/(-) 3 0 () 即*是使整个系统总费用最小的服务率(因为二阶导数0，故一阶导数是增函数,则函数是凸的，故极值点*处函数取极小值) 。12试用类似对N=T作直观论证的方法，论证E(q) = E(w)。答案：提示，把等待部分看成一个网络，顾客流随机地进入（等待接受服务）和离开（即将被服务）网络。13某火车站每小时平均有3000旅客进入，而站内通常平均有1000个旅客，每个旅客在火车站平均停留时间是多少？答案：=3000人/hN=1000人按利特尔定律每个旅客在火车站平均停留时间是： 14进入一个M/M/1排队系统的顾客到达率是每小时20个，服务速率是每小时40个，求排队系统中平均顾客数和正在接受服务的顾客平均数。答案：M/M/1 排队， =20人/h， =40人/h。 = /=0.5 平均顾客数（平均队长） ，平均等待队长 正在接受服务的顾客数： E(n) E(q) = 10.5 = 0.515在一个M/M/1排队系统中平均有10个顾客正在等待，求此排队系统服务机构的利用率。答案：M/M/1排队 服务机构利用率： 取有意义的根： 16一个泊松报文流以每秒1000个的平均速率到达路由器的某输出链路的排队系统，报文长度为指数分布，平均长度为1000字符，链路容量为20Mbps。求每个报文的平均等待时间和平均等待队长。答案：这是一个M/M/1模型 = 1000/s， 1/= 1000字符， C = 20Mb/s，C =/s 平均等待时间： = 4/15( ms ) 0.267(ms) （注：公式中，隐含C） 平均等待队长：17多链路协议MLP是X.25的一部分，DTE与DCE之间无论哪个VC都有多条数据链路可以被用作发送分组的资源池，当分组递交给MLP传输时，可选任一可用链路。若DTE与DCE间有5条19.6kbps链路，分组平均长100字节，分组到达率为每秒96个。（1）.对M/M/1模型，计算和E(T) 将5条链路看成一个整体 。（2）.对M/M/5模型，计算E(T)。（3）.对5个M/M/1的模型，计算和E(T) 假定能预先将各VC按其数据量均分给5条19.6kbps链路，因此，DTE与DCE之间特定的VC，将固定在确定的某一条链路上传输其分组 。 （4）.仅就E(T)比较其优劣。答案：对M/M/1模型 ， ， =96/s。1/=800b 平均时延： = 37.7ms（注：公式中，隐含C）对M/M/5模型，m=5个服务员，每个服务员参数为（隐含C），同前。 = 96/s， 其中， 0.78367 （注：公式中，隐含C） 1+50.78367 +0.5(50.78367)2+(1/6)(50.78367)3+(1/24)(50.78367)4+(50.78367)5/(0.21633120)-11+3.91835 +0.515.35347+(1/6)60.16+(1/24)235.73+923.67/(0.21633120) 11+3.91835 +7.677+10.027+9.82+35.58 1 68.017-1 0.0147 (50.78367)5/(0.21633120) 0.0147 35.580.0147 0.523 0.523(0.8/19.6) /50.21633 +(0.8/19.6) 0.5230.0408 /1.08165+0.0408 0.0197+0.0408 0.0605s = 60.5ms（3）. 对5个M/M/1模型 ， ， =（96/5）/s。1/=800b 平均时延： = 188.7ms（注：公式中，隐含C）（4）.仅就E(T)比较其优劣。对5个M/M/1模型：E(T)=188.7ms；对M/M/5模型：E(T)= 60.5ms；对M/M/1模型：E(T)= 37.7ms。所以，仅就E(T)来说，M/M/1最优，5个M/M/1模型最差，M/M/5模型居中。18Cantor集从0,1区间开始，第N次递归后的Cantor集的长度是多少？答案：cantor集从0,1区间开始：（N=0），长度为1 =1；N=1，长度为；N=2，长度为，第N次递归后的cantor集长度为。19CCITT制定的关于分组装拆器PAD（Packet AssemblerDisassembler）的三个建议书（X.3、X.28和X.29）定义了字符方式终端访问X.25网的方法，如图2-6所示。PAD可以适应以下两种情况： （1）对不能像主机那样实现X.25协议的字符方式终端，PAD提供了使它们能够用X.25协议同网上的其它主机通信的能力。 （2）PAD提供了许多参数供各种不同的字符方式终端选择，使它们都可以很方便地接入到X.25网。定义PAD设施的标准共三个： X.3 描述PAD的功能以及控制它工作的一些参数（现共有22个）。 X.28 描述PAD到字符方式终端的协议。 X.29 描述PAD到主机（同步终端）的协议。PAD先将字符方式终端发来的字符存储在缓冲区中，再装配成X.25分组，最后送入X.25网络。当X.25网络向字符方式终端递交分组时，该分组先被PAD缓存，随后PAD将分组中的数据按字符方式逐个发往终端。每个PAD都保存有相连的字符方式终端的参数表，X.28就规定怎样选择这些参数，并详细规定终端与PAD的电气接口以及传送字符的方法。X.29规定的是，主机怎样为每个不同的终端选择合适的参数以及规定主机到PAD的端到端通信过程。 图2-6 PAD和X.3、X.28及X.29的关系考虑各终端通过PAD向外发送字符的简单模型，如图2-7所示：每个字符方式终端的输入字符首先进入PAD中的第一级排队，排队缓冲区刚好容纳一个X.25分组的字符数。一旦缓冲区满，立即组成一个分组送入第二级排队（第一级到第二级传输时间忽略不计）。设为终端产生字符的泊松输入速率，C为输出信道的传输速率，C、均以每秒字符计。I为一个分组包含的用户数据字符数，H为分组头包含的字符数，n为终端数目。求：（1）字符在第一级排队中的平均等待时间； （2）分组在第二级排队中的平均等待时间； （3）一个字符从离开终端到离开PAD的平均时间。 图2-7 PAD中的排队模型答案：对第一级排队模型：依题意，字符按Poisson速率进入buffer，在buffer中字符不到I个之前，这些字符必须等待，不能被服务；等待凑满I个字符，作为一个整体，立即被服务（进入第二级排队，且两级间传输时间忽略不计），因而其平均输出速率应为（/I）分组/s，且根据Poisson过程的性质，输出流（即第二级排队模型的输入流）仍为Poisson流。对第一级排队模型只需考虑其输入过程。因为字符到达率为，故字符平均到达间隔为s。buffer中积满了I个字符的平均时间为。其中，第一个字符平均等待时间为 第一个字符进入后，只需再等待后面的个字符到达。第I个字符等待时间为0s，第j个字符平均等待时间为 。于是，字符在第一级排队中的平均等待时间为： 第二级排队模型为 M/D/1（输出定长分组）平均到达率：分组在第二级排队中的平均等待时间为：20由A，B和C三结点构成一顺时针传输数据的环形网，如图2-8所示。其中，各结点的输入报文流均相等，A =B =C = 2 /秒，A，B和C均为泊松流；报文长均为负指数分布，其平均报文长均相等，1/A=1/B=1/C=1000bit；各链路容量均相等，C1=C2=C3=4000bps(bit/s)。若各结点的输入报文流的一半均发往顺时针环形网上该结点的下一邻结点，而另一半则发往顺时针环形网上该结点的再下一个邻结点。1) 求各链路报文到达率：1，2和3；2) 求全网平均时延E(T) （忽略信号在介质上的传播时间）；3) 求相邻结点间各报文流的平均时延：E(T) A-B， E(T) B-C，E(T) C-A（忽略信号在介质上的传播时间）；4) 求经相邻结点转发到顺时针环形网上再下一个结点的各报文流的平均时延：E(T) A-B-C，E(T) B-C-A，E(T) C-A-B。图2-8 三结点构成的顺时针传输数据的环形网解：1)各链路报文到达率：1=2=3 = 3 /秒2)由题目条件知，各链路排队系统均为M/M/1模型，故各链路平均排队时延为：E(T i )=1/(i C i -i)因为：1=2=3 = 3 /秒；C1=C2=C3=4000bps；1/A=1/B=1/C=1000bit故：E(T 1 )= E(T2 )= E(T 3 )=1/（4000/1000）3 =1秒由利特尔定律求各链队长:E(N i ) =i E(T i ) = 3全网队长（忽略信号在介质上的传播时间）:E(N) =E(N i ) = 9全网报文到达率:=A+B+C = 6 /秒由利特尔定律得全网平均时延:E(T)=E(N) / =9/6=1.5秒3) 因为E(T 1 )= E(T2 )= E(T 3 )=1秒且忽略信号在介质上的传播时间，故相邻结点间各报文流的平均时延分别为:E(T) A-B =E(T 1 )=E(T) B-C= E(T2 )=E(T) C-A= E(T 3 ) =1秒4) 经相邻结点转发到顺时针环形网上再下一个结点的各报文流的平均时延分别为：E(T) A-B-C= E(T) A-B +E(T) B-C = 2秒E(T) B-C-A= E(T) B-C +