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

第2章网络排队模型和自相似通信量1．泊松过程的报文到达间隔是连续随机变量，它的概率分布为：F（t）＝1一e一λt则到达时间间隔的概率密度函数为：α（t）＝dF（t）/dt＝λe一λt这是负指数的概率密度函数。到达间隔是负指数分布的连续随机变量。证明，平均到达时间间隔:a1＝0tα（t）dt＝1/λ答案：用分部积分证明a1＝E(t)＝0tα（t）dt＝0tλe一λtdt＝—0tde一λt＝—[te一λt0—0e一λtdt]＝0+0e一λtdt＝—1/λ0e一λtd（—λt）＝—1/λ0de一λt＝—1/λe一λt0＝—1/λ（0—1）＝1/λ2．条件同1题，证明，到达时间间隔的方差为：σa2＝0t2α（t）dt－a12＝1/λ2答案：证明σa2＝E(t2)—E2(t)＝0t2α（t）dt－1/λ2上式第一项（采用分部积分）＝0t2α（t）dt＝0t2λe一λtdt＝－0t2de一λt＝—[t2e一λt0—0e一λtdt2]＝0+0e一λtdt2＝20te一λtdt＝—2/λ0tde一λt＝—2/λ[te一λt0—0e一λtdt]＝—2/λ（0—0e一λtdt）＝2/λ0e一λtdt＝2/λ（1/λ）＝2/λ2所以σa2＝E(t2)—E2(t)＝0t2α（t）dt－1/λ2＝2/λ2－1/λ2＝1/λ23．分组交换网中所有信道（链路、线路）容量加倍，也使用户数加倍（假定每个用户所在位置添一个用户，从同一个结点入网，其数据的目的地也与该位置原来那个用户的目的地相同），每个用户的数据量不变。采用固定路径（新添用户的报文路径与该位置原来那个用户的报文路径相同），从任何结点进入的报文流均为泊松流，具有相同的负指数长度分布，平均长1/μ。计算前后两种情况下全网平均时延间的关系。答案：这是一个M/M/1模型。计算结果如表2-1：表2-1：先前当前i链服务率Ci/(1/μ)=μCi2Ci/(1/μ)=2μCii链报文到达率λi2λi全网报文到达率γ2γ全网平均时延E(T)=E(N)/γi链平均时延E(Ti)=1/(μCi-λi)i链队长E(Ni)=λiE(Ti)=λi/(μCi-λi)E(N)=iE(Ni)E(T)=E(N)/γi链平均时延E(Ti)’=1/(2μCi-2λi)=0.5E(Ti)i链队长E(Ni)’=2λi(0.5)E(Ti)=E(Ni)E(N)’=iE(Ni)’=iE(Ni)=E(N)E(T)’=E(N)‘/2γ=0.5E(T)即全网平均时延减半。4．分组交换网中所有信道（链路、线路）容量增加到原来的N倍，用户数也增加到原来的N倍（假定每个用户所在位置添N一1个用户，从同一个结点入网，其数据的目的地也与该位置原来那个用户的目的地相同），每个用户的数据量不变。采用固定路径（新添用户的报文路径与该位置原来那个用户的报文路径相同），从任何结点进入的报文流均为泊松流，具有相同的负指数长度分布，平均长1/μ。计算前后两种情况下全网平均时延间的关系。答案：这是一个M/M/1模型。计算结果如表2-2：表2-2：先前当前i链服务率Ci/(1/μ)=μCiNCi/(1/μ)=NμCii链报文到达率λiNλi全网报文到达率γNγ全网平均时延E(T)=E(N)/γi链平均时延E(Ti)=1/(μCi-λi)i链队长E(Ni)=λiE(Ti)=λi/(μCi-λi)E(N)=iE(Ni)E(T)=E(N)/γi链平均时延E(Ti)’=1/(NμCi-Nλi)=E(Ti)/Ni链队长E(Ni)’=NλiE(Ti)/N=E(Ni)E(N)’=iE(Ni)’=iE(Ni)=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]＝!)(12AeYAYAA＝λY＋λ2Y2答案：证明如下m＝E[A2/Y]＝!)(12AeYAYAA＝λYe―λY＋!)(22AeYAYAA其中!)(22AeYAYAA＝λYe―λY!)(122AYAAA又其中!)(122AYAAA＝]1)1[()!1()(12AAYAA＝λY)!2()(22AYAA＋[11])!1()(12AYAA＝λYeλY＋eλY―1[注：ex＝1+x+x2/2!+x3/3!+……+xn/n!+……(―∞x+∞)]所以m＝E[A2/Y]＝λYe―λY＋λYe―λY[λYeλY＋eλY―1]＝λYe―λY＋（λY）2＋λY―λYe―λY＝λY＋λ2Y26．输入是泊松过程，报文的平均到达率为λ，平均长度为1／µ，但报文长度的分布规律则是任意的（服务机构的能力是稳定的，因此，服务时间的分布与报文长度分布特性相同）。输出信道只有一个（一个服务机构），其容量为C。A是在一个报文的发送(服务)时间Y内，报文的到达数目。A是一个随机变量，A2是随机变量A的函数。Y是一个随机变量，Y的概率密度是b（Y）,Y分布范围：0―∞，按全概率公式：A2＝E[A2]＝0mb（Y）dY其中，m＝E[A2/Y]＝!)(12AeYAYAA＝λY＋λ2Y2证明：A2＝E[A2]＝0mb（Y）dY＝0(λY＋λ2Y2)b（Y）dY＝λ0Yb（Y）dY＋λ20Y2b（Y）dY＝λ/μC＋λ2(σY2＋1/μ2C2)答案：证明如下，一个报文的发送(服务)时间Y的平均值为：1/μC＝E[Y]＝0Yb（Y）dYσY2＝E[Y2]―E2[Y]＝0Y2b（Y）dY―1/μ2C2则0Y2b（Y）dY＝σY2＋1/μ2C2所以A2＝λ0Yb（Y）dY＋λ20Y2b（Y）dY＝λ/μC＋λ2(σY2＋1/μ2C2)7．经一条通信线路到交换中心的报文流的到达过程是泊松过程，平均每分钟240个报文。线路传送速率800字符/s。报文长的分布（包括控制字符）近似为指数型，其平均长为176字符，计算系统性能的主要参数。假定缓冲器的容量足够多。答案：平均服务时间为（1/μ）/C=176字符/（800字符/s）=0．22sλ＝240个报文/60s＝4报文/sρ＝λ/μC=0．88利用M／M／1公式，计算队长N＝ρ/（1一ρ）＝7．33报文;等待队长NW＝ρ2/（1一ρ）＝6．45报文；报文排队时延T＝1/（μC一λ）＝1．83s;等待时间TW＝ρ/μC（1一ρ）＝1．61s8．一个车间有5台机器，机器故障间隔为指数分布，平均间隔长为50h，一个工人平均在0.5h内修好机器，假定修理时间也是指数分布。在开工期间，若希望98%的时间机器可以使用，问需几个维修工人？答案：这是一个M/M/m问题，求其最优m值，其排队模型如图2-1所示：图2-1一个M/M/m排队模型解本M/M/m问题，可不用边际算法求最优m，可直接从平均等待时间E(w)≤1/2h求m，采用试探算法即可求出其最优m值；入1=入2=5=501(1/h)入=5*501=0.1(1/h)μ=μ1=μ2=…=μm=1/0.5=2(1/h)对一台机器，平均50h一次故障，只要修理时间0.5h加上平均等待时间E(w)小于1h，则可用时间为49h，若希望98%的时间机器可以使用，则只要平均等待时间E(w)≤0.5h即可。本题中，平均服务时间（修理时间）E(ts)=(1/μ)h对M/M/m,要求等待时间E(w)=5.0)1()(mtsBEh整理得：10!)(!)1)(1()]1(1[)(mnnmnmmmmm试探：m=1ρ[1-1+ρ]≤(1-ρ)(1-ρ)ρ=20121.022221)1(0≤1-2ρ=1-0.1=0.9成立m=1即可。核对：m=1，问题简化为M/M/1模型。其平均排队时延E（T）＝1/（μ一λ）＝1/（2一0.1）＝20/38＝E(ts)+E(w)＝0.5+E(w)(其中μ隐含C)显然满足E(w)≤0.5h的要求，已保证可用时间49小时。9．一个M/M/1排队系统，把服务台本身和等候使用服务台的队列当作两个单独的服务系统。用利特尔公式说明ρ=λ/μ和等待队长12Q，其中μ隐含C。答案：设M/M/1排队系统参数为λ，μ（隐含C），如图2-2所示201121.01mmm|)(nE|μλ|E(T)|图2-2M/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服务台的忙期和闲期于是：'0)(tdttI表示(0——t’，服务台的有效工作时间)=(0——t’，服务台有一个报文存在的时间)而')('0tdttIt则表示（0——t’，服务台的利用率）=（0——t’，服务台中的平均队长）μ最后')('0'limtdttItt则表示（服务台平均利用率ρ）=（服务台平均队长E(ns)，其值已在①求到，为λ/μ）即ρ=λ/μ⑵考虑等待使用服务台的队列，如图2-5所示：QE（w）图2-5等待使用服务台的队列平均队长Q=E(n)-ρ=λE(T)–ρ=1)(22其中E(n)为M/M/1平均队长，E(T)为M/M/1平均排队时延。10．一个港口，船的装卸时间为指数分布，平均３h，船的到达率为λ＝0.25/h，到达为泊松过程，M/M/1。装卸(服务)时间概率密度为：ctcetb)(⑴.一支船到达时，要求２０小时以上服务时间的概率是多少？⑵.在港口中等待装卸的队长是多少？答案：⑴依题意可得：31ch，λ＝0.25/h75.0c服务时间分布tctdtcetTPtF0][)(ttctctdectde00)(ctctcteete1]1[0平均排队时延（从到港至装卸完）μ12413111cTh32011]20[][eeTPtTPct于是，一只船到达时，要求２０小时以上服务时间的概率是：3203201]20[1]20[eeTPTP⑵在港口中等待装卸的队长是：25.241169431)43(122wN11．设船到码头，在港停留一小时损失C1元，服务费用正比于服务（装卸船）率，每小时C2元，进港船只是泊松流，参数为λ，装卸时间服从参数为μ的负指数分布。求使整个系统总费用最小的服务率μ。答案：系统模型如图2-6所示：港口入μ图2-6系统模型顾客（船东）这是考虑整个排队系统服务机构（港口）求使双方总费用最小的最优策略（服务率μ）。单位服务率是一小时C2元，即若港口每小时可装卸完一条船，此种服务能力，一小时价值C2元。参考计算机网络中的参数含义，1/μ（比特/报文），1/(μc)=(比特/报文)×(秒/比)=秒/报文，若隐含服务能力C，则1/(μc)就可表示为1/μ；类似的，港口参数含义如下：1/μ(小时/船)（隐含港口服务能力C），则μ(船/小时)即为港口每小时可装卸船数。平均队长E(n)=ρ/(1-ρ)=λ/(μ-λ)∴每小时船方损失费用λc1/(μ-λ)元每小时服务机构