1、- 1 - 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？ 解答 （
2、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 的计算时间。针对这个很
3、简单的子网 而言，请你估算一下假如希望考察所有可能的拓扑（比如用来匹配某个有着预期负载的拓 扑） ，一共需要多少个小时的时间？ 解答 5 个路由器之间两两相联最多有 C25=（54）/ (12)= 10 条可能的线路。 每条线路有 4 种连接的可能性：高速、中速、低速或无连接。 因此，所有可能的拓扑种数是： 410 = 1048576 种拓扑， 花费的总时间= 0.1 秒1048576= 104857.6/3600 小时= 29.127 小时。 1.3，请你分析以下的三个有着不同几何拓扑构型的分组交换网，每一个网络都有 N 个结点。 第一个是星形的网络，其中有一个中央的结点（中央分组交换机）
4、，其他N1 个结点都只 连到中央结点；第二个是环形的网络，N 个结点依次相连，组成双向的一个环；第三个则 是完全互连网，每一结点有着连到其他N1 个结点的直接连线。假定以跳段数 HOPS 为 好坏衡量的标准，列出每一种网的最好的、最坏的和平均的情形下的传输通路中的跳段数。 解答 星形网络：最好 2，最坏 2，平均 2； 环形网络：最好 1；最坏 N/2，平均 N/4；近似 完全互连网络：最好 1，最坏 1，平均 1。 网络带宽和性能基础 1.4, 带宽延迟积 和比特宽度的概念 物理信号通过各类媒体传播需要花费时间， 假定信号跨越某链路传播时的速率是 s= 2.510 8 米/秒。此链路 L 直
5、接连接了相隔距离 m 为 10000 千米的两台主机 A 和 B。 - 2 - （1）现在假定此链路 L 的带宽为 R=1 M bps；请先估算出从主机 A 到主机 B 的物理信号 传播时间 t prop；再估算出带宽延迟积Rt prop；链路的带宽延迟积指的是在 该链路中允许可有的最大两进位比特位数。 （2）考虑要从主机 A 到 B 发送一个 400Kb 大小的文件 F，采用的方式是把该文件做为一个 大报文连续发送，请问：在任何给定的时刻，在该链路 L 上具有的比特数量的最大值是多 少？ （3）假定采用连续发送方式来发送文件 F，发送该文件要多长时间？ （4）考虑把该文件 F 划分成 10
6、个分组，每个分组长度是 40 kb。假定每个分组需要被接 收方所确认（长度很小的确认分组的传输时间可忽略不计） ，在前一分组被接收方确认之后， 发送方才能发送下一分组，这时，发送该文件 F 要多长时间？ （5）在链路上传播一个比特信号所占用的链路物理长度被称之为比特宽度 （以米为单 位） ；说明在该链路 L 上的一个比特的宽度是多少？它比一个足球场的长度更长吗？请你根 据传播速率 s、带宽 R 和链路长度 m，推导出比特宽度的一般表达式。 （6）如果我们能调整改变链路 L 的带宽 R，采用哪个 R 值，能使得一个比特的宽度能与 链路的总长度一样长？ 解答（1）t prop = m/s = 11
7、0 7 米/ (2.510 8 米/秒)=410 -2 秒； 带宽延迟积 Rt prop = 1 M bps410 -2 秒= 410 4 位。 （2）受限制于带宽 R 和信号物理传播时间 t prop，链路 L 上的最大比特数为 410 4 位。 （即带宽延迟积） 。 （3）文件 F 的连续发送时间由带宽限定的传输时间和物理信号传播时间两部分所组成： t trans + t prop= 400Kb/ R + m/s =410 8 毫秒/110 6 + 410 毫秒= 440 毫秒。 （4）每一分组都有一个分组的带宽传输时间和往返两个信号传播时间（其中一个是接收方 确认信号） ，因此有 10（
8、分组 t trans + 2 t prop ）= 10（40 毫秒+ 80 毫秒） = 1200 毫秒。 （5）链路 L 的比特宽度即是 m/ Rt prop = 110 7 米/410 4 位= 250 米。 比特宽度的一般公式是：m/ Rt prop = m/ Rm/s= s/R。 （6）要求比特宽度相等于链路总长度时，即有 s/R = m。 要求 R = s/m =(2.510 8 米/秒)/（110 7 米）= 25 bps。 1.5 假定信号跨越某链路传播时的速率是 s= 2.510 8 米/秒。此链路 L1 直接连接了相隔距 离 m 为 10000 千米的两台主机 A 和 B。 （
9、1）现在假定此链路 L1 的带宽为 R=1 G bps；请估算出带宽延迟积Rt prop； （2）要从主机 A 到 B 发送一个 400Kb 大小的文件 F，采用的方式是把该文件做为一个大报 文连续发送，请问：在任何给定的时刻，在该链路 L1 上具有的比特数量的最大值是多少？ （3）估算出该链路 L1 上的一个比特的宽度是多少？ 解答（1）带宽延迟积 Rt prop = 1 G bps410 -2 秒= 410 7 位。 （2）尽管链路 L1 的带宽延迟积允许链路可有的最大比特位数较大，但现在的文件小， 在该链路 L1 上具有的比特数量的最大值是文件 F 的大小 400K。 （3）链路 L1
10、的比特宽度即是 m/ Rt prop = 110 7 米/410 7 位= 0.25 米。 1.6，假定在电缆中电信号的传播速率是光速的 2/3（即电信号传播速率是 200KM/毫秒） ， 一条 100 公里长的电缆正在以 T1 数据速率运行着，请你估算出在该条电缆中充填着多少 个二进位？T1 以 125S 传送一个幀（一帧即 824+1 位） 解答 电信号传播速率是 200KM/毫秒；即 100KM 电缆会在 0.5 毫秒填满。 - 3 - T1 以 125S 传送 193 位的一幀（即 824+1 位） ，0.5 毫秒= 500S， 传播的是500s/（125s）193bits= 772b
11、its。 本题也可用带宽延迟积 Rt prop = 1.544M bps510 -4 秒= 772 位。 线路交换和分组交换概念 1.7，比较线路交换和分组交换的用户接纳能力 假定由多个用户共享一条 1Mbps 的链路， 每个用户传输时要求速率为 100Kbps，但每个用户仅有 10%的时间需求传输。请作以下的 估算：（1）当采用线路交换工作方式时，能够支持多少个用户？（2）当采用分组交换工 作方式时，一个给定用户传输的概率是多少？假定有 40 个用户，在给定时刻，实际有 n 个用户在同时传输的概率是多少？（3）再请给出有 11 个或更多个用户同时传输的概率。 解答 多用户共享 1Mbps 链
12、路，每一用户需要 100Kbps 带宽（发送数据期间） ，用户发送 概率（可能性）=0.1。 （1）在线路交换方式时，支持 1M/ 100K= 10 个用户预留资源； （2）分组交换场合下，一个给定用户正在发送数据的概率是：p-= 0.1; 总共有 40 个用户时, 任一时刻有 n 个用户在同时发送数据的概率是： C40 n pn(1p) 40n ；(其中 p = 0.1)。 （3）有 11 个用户或 11 个以上用户在同时发送数据的概率是： 1（1p） 40C 140p（1p） 39C 240p2 （1p） 38C 340p3（1p） 37C 440p4 （1p） 36 C 540p5 （1
13、 p） 35 C 640p6 （1p） 34C 740p7 （1p） 33C 840p8 （1p） 32 C940p9 （1p） 31C 1040p10 （1p） 30。(其中 p = 0.1)。 1.8 假定由多个用户共享一条 1Gbps 的链路，每个用户忙时要求以 100Kbps 速率产生数据， 但每个用户忙于产生数据的概率仅有 p=0.1。 （1）当采用线路交换工作方式时，能够支持 多少个用户？（2）当采用分组交换工作方式和 M 个用户时，请列出公式表示：有多于 N 个用户发送数据的概率。 （以 M、N 和 p 来表示） 。 解答 （1）1G=10 9， 线路交换要预留好每用户带宽资源
14、10 9 /100K= 104 =10000 个用户。 （2）分组交换有多于 N 个用户发送数据的概率 M C M 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）
15、+H D 时，到达目的地。 （2）分组交换 T= （M/R ） +（H 1）（P/R）+ HD 到达目的地。 分组交换网的延迟时间更短些要求： （M/R ）+ （H1）（P/R）+ H D (H1)P/R。 1.10，请分析在分组交换网中分组的大小与传输延迟的关系：假定需要把 M 位二进位的一 个用户报文以一列分组的形式沿着一条有 H 个跳段的通路上传输，链路的数据速率都是 R bps，传播延迟忽略不计。如果每个分组有 P 位数据位和 hd 位头部信息位。试推导出采用 - 4 - 多少大的分组数据位 P 值，能使总的传输延迟达到最小？假定不考虑排队延迟 解答区分 H（跳段数）和头部长度 hd；
16、需发送的总位数是：（M/P ）（P+hd）位； 简化后的总延迟时间 T= 发送时间转发时间=（ M/P）（P+hd）/R +（H 1） （P+hd ）/R。 使 T 最小化，dT /dP = 0； dT /dP = （M hd）/ （RP 2） + （H 1）/R = 0。 P= M hd /（H-1） 。 1.11，分段长度的讨论 从主机 A 到主机 B 发送一个 F 位的大文件，在 A 与 B 之间有两 段链路，并且链路不阻塞（即没有排队时延） 。主机 A 将该文件分成为长度是 S 位的报文 段，并为每个报文段增加一个 40 位的首部，使每个报文段形成为 L=40+S 位的一个分组。 假定
17、每条链路的传输速率是 R bps，请你估算出能使从 A 到 B 发送该文件的时延值 T 达到 最小时的 S 值（忽略传播时延） 。 解答本题完全类似于 1.16，需发送的总位数是：（F/S）（S+40 ）位； 简化总延迟时间 T= 发送时间转发时间 =（F/S）（S+40）/R +（21） （S+40）/R 。 使 T 最小化，dT /dS = 0； dT /dS = （40F）/ （RS 2）+ （21）/R = 0。 S= 40F 。相当于在 1.16 公式中代入, hd=40; M=F; H=2。 性能延迟与吞吐能力 1.12，路由器缓存排队延迟本题简要分析路由器的输出链路前端的缓存 的
18、排队延迟， 假定所有的分组长度是 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/N0+ L/R +2L/R+ 3L/R+
19、 .+(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/R1/（
20、1-I）。 （2）L/R=x， 总时延 = x / （ 1ax） 。 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 pr
21、op 大于 d trans，在 t=d trans 时，该分组的第一个比特位于何 处？（6）假定 d prop 小于 d trans，在 t=d trans 时，该分组的第一个比特位于何处？ （7）假定 - 5 - S=2.5108，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
22、 +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.510 8, L=100, R=28 Kbps, 要求 d prop= d trans, 即是 M/S= L/R 因此， M= LS/R= 1002.5108 / (28103)= 892857 米。 1.
23、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 。
