计算机网络第1章习题参考解答.doc

ME2012高级计算机网络 第1章习题部分解答 2012-4-22起
要求掌握蓝色的各题
路由器或结点的拓扑连接
1.1，下图中每一个圆圈代表一个网络中的结点，带有星号X用方框标出的是你的端系统主机。
D B F

A E H

G C *X

请回答如下问题：（1）你的本地接入结点是哪一结点？（2）哪些结点是你的本地接入结点的相邻结点？（3）哪些结点是你的本地接入结点的远程结点？（4）哪些结点是END端结点？（5）哪些结点是路由结点？（6）从结点G到H的最短通路有多少个跳段（HOPS）？（7）从结点F到G的最短通路有多少个跳段HOPS？
[解答] （1）你的本地接入结点是结点C；（2）你的本地接入结点的相邻结点是：A和G；（3）你的本地接入结点的远程结点是：B、D、E、F、H；（4）END端结点是：D、F、G、H；（5）路由结点是：A、E、C、B；（6）从结点G到H的最短通路有4个跳段（HOPS）；（7）从结点F到G的最短通路有5个跳段HOPS。

1.2， 考虑由5台路由器所组成的一个点到点结构的简单通信子网，假定在每一台路由器之间允许可以设置一条高速链路，或者是一条中速链路，或者是一条低速链路，也可以不设链路。如果产生并考察每一种拓扑需要花费100ms的计算时间。针对这个很简单的子网而言，请你估算一下假如希望考察所有可能的拓扑（比如用来匹配某个有着预期负载的拓扑），一共需要多少个小时的时间？
[解答] 5个路由器之间两两相联最多有C25=（5×4）/ (1×2)= 10条可能的线路。
每条线路有4种连接的可能性：高速、中速、低速或无连接。
因此，所有可能的拓扑种数是： 410 = 1048576种拓扑，
花费的总时间= 0.1秒×1048576= 104857.6/3600小时= 29.127小时。

1.3，请你分析以下的三个有着不同几何拓扑构型的分组交换网，每一个网络都有N个结点。第一个是星形的网络，其中有一个中央的结点（中央分组交换机），其他[N－1]个结点都只连到中央结点；第二个是环形的网络，N个结点依次相连，组成双向的一个环；第三个则是完全互连网，每一结点有着连到其他[N－1]个结点的直接连线。假定以跳段数HOPS为好坏衡量的标准，列出每一种网的最好的、最坏的和平均的情形下的传输通路中的跳段数。
[解答] 星形网络：最好2，最坏2，平均2；
环形网络：最好1；最坏N/2，平均N/4；[近似]
完全互连网络：最好1，最坏1，平均1。

网络带宽和性能基础
1.4, [《带宽延迟积》和《比特宽度》的概念] 物理信号通过各类媒体传播需要花费时间，假定信号跨越某链路传播时的速率是s= 2.5×10 8 米/秒。此链路L直接连接了相隔距离m为10000千米的两台主机A和B。
（1）现在假定此链路L的带宽为R=1 M bps；请先估算出从主机A到主机B的物理信号传播时间 t prop；再估算出《带宽延迟积》R×t prop；链路的《带宽延迟积》指的是在该链路中允许可有的最大两进位比特位数。
（2）考虑要从主机A到B发送一个 400Kb大小的文件F，采用的方式是把该文件做为一个大报文连续发送，请问：在任何给定的时刻，在该链路L上具有的比特数量的最大值是多少？
（3）假定采用连续发送方式来发送文件F，发送该文件要多长时间？
（4）考虑把该文件F划分成10个分组，每个分组长度是 40 kb。假定每个分组需要被接收方所确认（长度很小的确认分组的传输时间可忽略不计），在前一分组被接收方确认之后，发送方才能发送下一分组，这时，发送该文件F要多长时间？
（5）在链路上传播一个比特信号所占用的链路物理长度被称之为《比特宽度》（以米为单位）；说明在该链路L上的一个比特的宽度是多少？它比一个足球场的长度更长吗？请你根据传播速率s、带宽R和链路长度m，推导出《比特宽度》的一般表达式。
（6）如果我们能调整改变链路L的带宽R，采用哪个R值，能使得一个比特的宽度能与链路的总长度一样长？
[解答]（1）t prop = m/s = 1×10 7 米/ (2.5×10 8 米/秒)=4×10 -2 秒；
带宽延迟积 R×t prop = 1 M bps×4×10 -2 秒= 4×10 4 位。
（2）受限制于带宽R和信号物理传播时间t prop，链路L上的最大比特数为4×10 4 位。（即带宽延迟积）。
（3）文件F的连续发送时间由带宽限定的传输时间和物理信号传播时间两部分所组成：
t trans + t prop= 400Kb/ R + m/s =4×10 8 毫秒/[1×10 6 ]+ 4×10毫秒= 440毫秒。
（4）每一分组都有一个分组的带宽传输时间和往返两个信号传播时间（其中一个是接收方确认信号），因此有 10×（分组t trans + 2× t prop ）= 10×（40毫秒+ 80毫秒）
= 1200毫秒。
（5）链路L的比特宽度即是 m/[ R×t prop] = 1×10 7 米/[4×10 4 位]= 250米。
《比特宽度》的一般公式是：m/[ R×t prop] = m/ [R×m/s]= s/R。
（6）要求比特宽度相等于链路总长度时，即有 s/R = m。
要求R = s/m =(2.5×10 8 米/秒)/（1×10 7 米）= 25 bps。

1.5假定信号跨越某链路传播时的速率是s= 2.5×10 8 米/秒。此链路L1直接连接了相隔距离m为10000千米的两台主机A和B。
（1）现在假定此链路L1的带宽为R=1 G bps；请估算出《带宽延迟积》R×t prop；
（2）要从主机A到B发送一个 400Kb大小的文件F，采用的方式是把该文件做为一个大报文连续发送，请问：在任何给定的时刻，在该链路L1上具有的比特数量的最大值是多少？
（3）估算出该链路L1上的一个比特的宽度是多少？
[解答]（1）带宽延迟积 R×t prop = 1 G bps×4×10 -2 秒= 4×10 7 位。
（2）尽管链路L1的《带宽延迟积》允许链路可有的最大比特位数较大，但现在的文件小，在该链路L1上具有的比特数量的最大值是文件F的大小400K。
（3）链路L1的比特宽度即是 m/[ R×t prop] = 1×10 7 米/[4×10 7 位]= 0.25米。

1.6，假定在电缆中电信号的传播速率是光速的2/3（即电信号传播速率是200KM/毫秒），一条100公里长的电缆正在以T1数据速率运行着，请你估算出在该条电缆中充填着多少个二进位？[T1以125μS传送一个幀（一帧即8×24+1位）]
[解答] 电信号传播速率是200KM/毫秒；即100KM电缆会在0.5毫秒填满。
T1以125μS传送193位的一幀（即8×24+1位），0.5毫秒= 500μS，
传播的是[500μs/（125μs）]×193bits= 772bits。
本题也可用《带宽延迟积》 R×t prop = 1.544M bps×5×10 -4 秒= 772 位。

线路交换和分组交换概念
1.7，[比较线路交换和分组交换的用户接纳能力] 假定由多个用户共享一条1Mbps的链路，每个用户传输时要求速率为100Kbps，但每个用户仅有10%的时间需求传输。请作以下的估算：（1）当采用线路交换工作方式时，能够支持多少个用户？（2）当采用分组交换工作方式时，一个给定用户传输的概率是多少？假定有40个用户，在给定时刻，实际有n个用户在同时传输的概率是多少？（3）再请给出有11个或更多个用户同时传输的概率。
[解答] 多用户共享1Mbps链路，每一用户需要100Kbps带宽（发送数据期间），用户发送概率（可能性）=0.1。
（1）在线路交换方式时，支持 1M/ 100K= 10个用户[预留资源]；
（2）分组交换场合下，一个给定用户正在发送数据的概率是：p-= 0.1;
总共有40个用户时, 任一时刻有n个用户在同时发送数据的概率是：
C40 n ×pn×(1－p)40－n ；(其中p = 0.1)。
（3）有11个用户或11个以上用户在同时发送数据的概率是：
1－[（1－p）40＋C140p（1－p）39＋C240p2 （1－p）38＋C340p3（1－p）37＋C440p4 （1－p）36
＋C540p5 （1－p）35 ＋C640p6 （1－p）34＋C740p7 （1－p）33＋C840p8 （1－p）32＋ C940p9 （1－p）31＋C1040p10 （1－p）30]。(其中p = 0.1)。

1.8假定由多个用户共享一条1Gbps的链路，每个用户忙时要求以100Kbps速率产生数据，但每个用户忙于产生数据的概率仅有p=0.1。（1）当采用线路交换工作方式时，能够支持多少个用户？（2）当采用分组交换工作方式和M个用户时，请列出公式表示：有多于N个用户发送数据的概率。（以M、N和p来表示）。
[解答] （1）1G=10 9， 线路交换要预留好每用户带宽资源10 9 /100K= 104 =10000个用户。
（2）分组交换有多于N个用户发送数据的概率
M
∑ CM n p n （1-p） M-n
n=N+1

1.9，请你比较在特定的经过简化的线路交换网与分组交换网上沿着有H个跳段的一个通路传输一个M位二进位的报文的延迟时间。假定线路的建立时间是S秒，每个跨段链路上的传输延迟为D，分组的大小是P位二进位，数据的传输速率是R bps。在估算时忽略掉分组头部的开销。试问在什么情况下，分组交换网的延迟时间会更短些？
[解答]（1）线路交换 T=S时建立线路；T=S+（M/R）时报文的最后一位发送完毕；
T= S+（M/R）+H×D时，到达目的地。
（2）分组交换 T= （M/R）+（H－1）×（P/R）+ H×D 到达目的地。
分组交换网的延迟时间更短些要求：
[（M/R）+（H－1）×（P/R）+ H×D ]< [ S+（M/R）+H×D]; 即S>(H－1)×P/R。

1.10，请分析在分组交换网中分组的大小与传输延迟的关系：假定需要把M位二进位的一个用户报文以一列分组的形式沿着一条有H个跳段的通路上传输，链路的数据速率都是R bps，传播延迟忽略不计。如果每个分组有P位数据位和hd位头部信息位。试推导出采用多少大的分组数据位P值，能使总的传输延迟达到最小？[假定不考虑排队延迟]
[解答]区分H（跳段数）和头部长度hd；需发送的总位数是：（M/P）×（P+hd）位；
简化后的总延迟时间
T= 发送时间＋转发时间=[（M/P）×（P+hd）]/R +（H－1）（P+hd）/R。
使T最小化，dT /dP = 0； dT /dP = －（M hd）/（RP2）+ （H－1）/R = 0。
P= √M hd /（H-1）。

1.11，[分段长度的讨论] 从主机A到主机B发送一个F位的大文件，在A与B之间有两段链路，并且链路不阻塞（即没有排队时延）。主机A将该文件分成为长度是S位的报文段，并为每个报文段增加一个40位的首部，使每个报文段形成为L=40+S位的一个分组。假定每条链路的传输速率是R bps，请你估算出能使从A到B发送该文件的时延值T达到最小时的S值（忽略传播时延）。
[解答]本题完全类似于1.16，需发送的总位数是：（F/S）×（S+40）位；
简化总延迟时间T= 发送时间＋转发时间=[（F/S）×（S+40）]/R +（2－1）（S+40）/R。
使T最小化，dT /dS = 0； dT /dS = －（40F）/（RS2）+ （2－1）/R = 0。
S= √40F。相当于在1.16公式中代入, hd=40; M=F; H=2。

性能延迟与吞吐能力
1.12，[路由器缓存排队延迟]本题简要分析《路由器的输出链路前端的缓存》的排队延迟，假定所有的分组长度是L比特，传输速率Rbps，每隔LN/R秒有N个分组同时到达缓存，请列出分组的平均排队延迟公式。（提示：对第1个分组的排队延迟是0，对第2个分组的排队延迟是L/R，对第3个分组的排队延迟是2L/R。当第二批分组到达时，第N个分组已经传输）。
[解答]传输N个分组需花LN/R秒；因此，当一批N个分组到达时，缓冲区为空。这N个分组的第1个分组的排队延迟是0，第2个分组的排队延迟是L/R秒，第n个分组的排队延迟是（n-1）L/R秒。平均延迟是： 1/N×[0+ L/R +2L/R+ 3L/R+ …….+(N-1)L/R]
= (L/R)×(1/N)×[0+1+2+….+(N-1)]=L/R×(1/N)×[N(N-1)/2]= L(N-1)/(2R).

1.13 分析路由器缓存内的排队延迟，令I表示流量强度，即I = La/R（其中a是分组到达队列的速率 ，即每秒到达的分组数，R 是链路的传输速率，L比特是分组的长度）；假定排队延迟的公式是 IL/[R（1-I）]。
（1）请写出总时延的公式，这里的总延时指排队延迟加上传输时延。
（2）以L/R作为变量x；列出总时延作为变量x的函数公式。
[解答]（1）传输时延是L/R，因此总时延 = IL/[R（1-I）] + L/R = L/R×[1/（1-I）]。
（2）L/R=x， 总时延 = x / （ 1－ax）。

1.14，[传播延迟与发送延迟] 主机A和B由速率为R bps的一条链路相连，链路传播速率为S 米/秒；假定A与B相距M米，从主机A向主机B发送的分组长度为L位。
（1）请用M和S来表示出传播延迟d prop。（2）请用L和R表示该分组的发送（传输）延迟d trans。（3）忽略排队和处理延迟，请给出 端到端 时延D的公式。
（4）假定主机A在t=0时刻开始发送该分组，在t=d trans时，该分组的最后一个比特在什么地方？（5）假定d prop 大于d trans，在t=d trans时，该分组的第一个比特位于何处？（6）假定d prop 小于d trans，在t=d trans时，该分组的第一个比特位于何处？（7）假定
S=2.5×108，L=100位，R=28Kbps。请你求出d prop 等于d tans时的距离M值。此题即是书本42页的第6道题。
[解答]传输速率Rbps，单个链路，相距M米，链路传播速率S米/秒，分组长度L位。
（1） 传播延迟d prop= M/S秒； （2）发送延迟d trans= L/R 秒；
（3）端到端简化延迟= d prop +d trans = M/S+ L/R； 不考虑结点处理延迟和排队延迟；
（4）当t=0时，开始发送；到 t=d trans时，分组的最后1位正在离开主机A。
（5）d prop> d trans，t= d trans时，分组的第1位在A到B的链路途中。
（6）d prop< d trans，t= d trans时，分组的第1位已在B主机中。
（7）S=2.5×108, L=100, R=28 Kbps, 要求 d prop= d trans, 即是 M/S= L/R
因此， M= LS/R= 100×2.5×108 / (28×103)= 892857米。

1.15, 在一个线路交换网络上，从主机A到主机B发送一个640000个两进位的文件需要花多长的时间？假定（1）所有链路的带宽是1.536Mbps，（2）每一链路采用具有24个时间片划分的TDM时分多路复用工作方式；（3）点到点电路的建立时间是500ms。（忽略传播延迟等）。
[解答]在TDM工作方式下，A到B的传输速率为1.536M bps / 24= 64Kbps.
640K位文件的发送传输时间是: 640K/ 64Kbps = 10秒。再需要加上线路交换工作方式下，在A与B之间点到点电路的建立时间是500ms。
因此，从主机A到主机B发送一个640000个两进位的文件需要花的时间是 10秒+0.5秒= 10.5秒。

1.16 主机A到主机B的通信经历A的输出网到公用网P，再到B的输入网。假定A的输出网的吞吐率是30Mbps; 公用网P的带宽是1Gbps，最多允许接纳50个用户，每个用户最多占用其1/50的带宽；B的输入网链路的吞吐率是25Mbps。请简要说明从A到B通信的平均吞吐率是多大？
[解答]可以认为A到B通信占用P的带宽是1G/50=20Mbps；平均吞吐能力应是
Min（30M，20M，25M）=20Mbps。
- 5 -