# 附录 F 习题 带 ✪ 的习题，其解答向在 textbooks.elsevier.com 注册的教师提供。 ### 习题 F.1 {#exercise-f-1} ✪ [15]〈F.2，F.3〉对于较远距离，电子通信是否总比非电子方式快？比较两种发送 1000 GB 数据的方式所需的时间：使用 25 盘 8 mm 磁带并交给隔夜快递；通过 Internet 使用 FTP。作如下四项假设： - 磁带在太平洋时间下午 4 点取走，次日东部时间上午 10 点（太平洋时间上午 7 点）送达 4200 km 外。 - 第一条网络路径中，最慢链路是传输速率为 45 Mbit/s 的 T3 线路。 - 第二条路径中，最慢链路是 100 Mbit/s 以太网。 - 你能使用两地之间最慢链路带宽的 50%。 这两条 Internet 路径上的全部字节，是否都能在隔夜快递员到达之前送达？ ### 习题 F.2 {#exercise-f-2} ✪ [10]〈F.2，F.3〉沿用习题 F.1 的假设，运送一个 1000 GB 包裹的隔夜快递，其带宽是多少？ ### 习题 F.3 {#exercise-f-3} ✪ [10]〈F.2，F.3〉沿用习题 F.1 的假设，要比隔夜快递更快，最慢链路至少需要多大带宽？哪些标准网络选项能达到这一速率？ ### 习题 F.4 {#exercise-f-4} ✪ [15]〈F.2，F.3〉最初的以太网标准规定速率为 10 Mbit/s，最大距离为 2.5 km。在这种以太网上，处于飞行途中的字节最多有多少？假设能够使用峰值带宽的 90%。 ### 习题 F.5 {#exercise-f-5} ✪ [15]〈F.2，F.3〉正如 F.2 节的延迟例题所示，WAN 的飞行时间很长，因此流控成为一个问题。以太网最初在 10 Mbit/s 速率下标准化时，没有包含流控。对于链路长 100 m 的 10 Gbit/s 以太网，假设能够使用峰值带宽的 90%，计算飞行中的字节数。这个答案对网络设计者意味着什么？ ### 习题 F.6 {#exercise-f-6} ✪ [15]〈F.2，F.3〉假设以太网上发送零长度数据分组的总开销为 100 μs，空载网络能够以标称峰值 1000 Mbit/s 的 90% 传输。本题假设以太网分组头和分组尾合计为 56 字节，并连续发送大小相同的分组。令有效载荷从 32 字节起，以 32 字节为增量变化，直到最大值 1500 字节；画出实际提供的用户数据带宽（Mbit/s）随有效载荷大小变化的曲线。 ### 习题 F.7 {#exercise-f-7} ✪ [10]〈F.2，F.3〉习题 F.6 表明，单个用户实际得到的带宽可能令人失望。沿用其假设，要达到峰值带宽的一半，最大有效载荷大小需要增加多少？ ### 习题 F.8 {#exercise-f-8} ✪ [10]〈F.2，F.3〉ATM 采用固定传输大小的原因之一是：短消息排在长消息后面时，节点可能必须等整次传输结束。对于时间敏感的应用，例如语音和视频，大传输单元造成的延迟可能超出应用容许范围。在空载互连中，若一个节点必须等待一个最大长度的以太网分组，最坏延迟是多少微秒？等待一次 ATM 传输又是多少？分组大小见图 F.30。本题假设能使用 622 Mbit/s ATM 网络和 1000 Mbit/s 以太网各自带宽的 100%。 ### 习题 F.9 {#exercise-f-9} ✪ [10]〈F.2，F.3〉习题 F.7 提示，为增加实际带宽，需要扩大最大有效载荷；习题 F.8 则提示，这会影响最坏延迟。如果按照习题 F.7 的答案增加最大有效载荷，对延迟会有什么影响？ ### 习题 F.10 {#exercise-f-10} ✪ [12/12/20]〈F.4〉图 F.11（原书标注第 F-31 页）中的 Omega 网络由三列交换机组成，每列四个，每个交换机有两个输入和两个输出。交换机可以设为**直通**（straight）：上输入接上输出、下输入接下输出；也可以设为**交换**（exchange）：上输入接下输出、下输入接上输出。对于每一列交换机，都把输入和输出从上到下编号为 0、1、…、7，与处理器编号对应。 a. [12]〈F.4〉当交换机设为交换状态且有一条消息通过时，该消息所用输入和输出的编号有什么关系？（提示：考虑对编号二进制表示中的位进行操作。） b. [12]〈F.4〉对于相邻列中由链路连接的两个交换机，前一交换机的输出编号与所接后一交换机的输入编号是什么关系？ c. [20]〈F.4〉根据 a、b 两问的结果，设计并描述一种简单的 Omega 网络分布式控制路由方案。消息携带由发送处理器计算的**路由标记**（routing tag）。说明处理器如何计算标记，以及每个交换机如何检查标记中的一个位来决定自身状态。 ### 习题 F.11 {#exercise-f-11} ✪ [12/12/12/12/12/12]〈F.4〉证明，图 F.11（原书标注第 F-31 页）的八节点 Omega 网络能否实现以下置换，即通信模式： a. [12]〈F.4〉**位反转置换**：二进制坐标为 \(a_{n-1},a_{n-2},\ldots,a_1,a_0\) 的节点，与节点 \(a_0,a_1,\ldots,a_{n-2},a_{n-1}\) 通信。 b. [12]〈F.4〉**完美洗牌置换**（perfect shuffle）：节点 \(a_{n-1},a_{n-2},\ldots,a_1,a_0\) 与节点 \(a_{n-2},a_{n-3},\ldots,a_0,a_{n-1}\) 通信，即循环左移一位。 c. [12]〈F.4〉**位取反置换**：节点 \(a_{n-1},a_{n-2},\ldots,a_1,a_0\) 与节点 \(\bar a_{n-1},\bar a_{n-2},\ldots,\bar a_1,\bar a_0\) 通信，即每一位都取反。 d. [12]〈F.4〉**蝶形置换**：节点 \(a_{n-1},a_{n-2},\ldots,a_1,a_0\) 与节点 \(a_0,a_{n-2},\ldots,a_1,a_{n-1}\) 通信，即交换最高位和最低位。 e. [12]〈F.4〉**矩阵转置置换**：节点 \(a_{n-1},a_{n-2},\ldots,a_1,a_0\) 与节点 \(a_{n/2-1},\ldots,a_0,a_{n-1},\ldots,a_{n/2}\) 通信，即把位置大致相隔半圈的位互换。 f. [12]〈F.4〉**桶形移位置换**（barrel-shift）：节点 \(i\) 与节点 \((i+1)\bmod(N-1)\) 通信，其中 \(N\) 是节点总数，\(0\leq i\)。 > **译注：**e 问的下标含有 \(n/2\)；但本题指定八节点，地址长度为三位，原文没有说明奇数位长时如何划分两组位。原页 f 问确实写作“modulo \(N-1\)”，也只给出 \(0\leq i\)。若意在表达全部 \(N\) 个节点上的循环移位置换，通常应模 \(N\)，且 \(0\leq i ### 习题 F.14 {#exercise-f-14} ✪ [15]〈F.4〉使用 18 端口交叉开关，为 64 个节点设计使各条链路所需带宽均衡的交换拓扑。假设通信流量均匀分布。 ### 习题 F.15 {#exercise-f-15} ✪ [15]〈F.4〉比较交叉开关、Omega 网络和胖树连接八个节点时的互连延迟。使用图 F.11（原书标注第 F-31 页）、F.12（第 F-33 页）和 F.14（第 F-37 页）。假设胖树全部由双输入、双输出交换机构成，使其硬件资源更便于与 Omega 网络比较。每个交换机带来一个单位的时间延迟。胖树随机选择路径，因此各例均须给出最好和最坏情况。从节点 0 向节点 6 发送消息需要多长时间？节点 1 与节点 7 通信需要多长时间？ ### 习题 F.16 {#exercise-f-16} ✪ [15]〈F.4〉仿照图 F.14（原书标注第 F-37 页）中的 4-cube，画出 6-cube 拓扑。若分组目的地均匀分布，分组所需的最大跳数和平均跳数分别是多少？ ### 习题 F.17 {#exercise-f-17} ✪ [15]〈F.4〉完成一张类似图 F.15（原书标注第 F-40 页）的表，列出各类网络拓扑的性能和成本；但不局限于 64 节点，而是考虑用 \(k\times k\) 交换机连接 \(N\) 个节点的一般情形。 ### 习题 F.18 {#exercise-f-18} ✪ [20]〈F.4〉重做 F.4 节的“NEWS 最近邻通信”例题，但把 NEWS 通信换成习题 F.11 中的位取反通信模式。 ### 习题 F.19 {#exercise-f-19} ✪ [15]〈F.5〉给出互连网络发生死锁必须具备的四个具体条件。维序路由消除了哪些条件？采用“逃逸”路径的自适应路由消除了哪些？采用回退式或前进式死锁恢复的自适应路由又消除了哪些？解释答案。 ### 习题 F.20 {#exercise-f-20} ✪ [12/12/12/12]〈F.5〉下列路由算法通过禁止某些维度转弯来约束路由。分析它们是否同时满足连通性和无死锁性，从而证明能否用作二维 mesh 的逃逸路径，并解释答案。（提示：可以参考 Turn Model 算法；也可以画出一个 \(4\times4\) mesh 的有向通道依赖图，检查是否不存在环，以证明结论。）以下用 W、E、N、S 分别表示西、东、北、南。 a. [12]〈F.5〉允许的转弯为 W→N、E→N、S→W、S→E。 b. [12]〈F.5〉允许的转弯为 W→S、E→S、N→E、S→E。 c. [12]〈F.5〉允许的转弯为 W→S、E→S、N→W、S→E、W→N、S→W。 d. [12]〈F.5〉允许的转弯为 S→E、E→S、S→W、N→W、N→E、E→N。 ### 习题 F.21 {#exercise-f-21} ✪ [15]〈F.5〉假设一个 64 节点二维 mesh 的通信流量均匀分布，计算并比较维序路由与 up*/down* 路由的效率因子 \(\rho\) 的上界。对于 up*/down*，假设根节点位于最优位置，即靠近 mesh 中心的节点。（提示：需要根据路由算法，求出承担全局负载的网络二等分链路上的负载。） ### 习题 F.22 {#exercise-f-22} ✪ [15]〈F.5〉沿用习题 F.21 的假设，求用 \(4\times4\) 交换机构成的 64 节点胖树上，up*/down* 路由的效率因子。将结果与二维 mesh 上的 up*/down* 路由比较并解释。 ### 习题 F.23 {#exercise-f-23} ✪ [15]〈F.5〉假设向输出端口发出的请求、输出端口返回的许可都均匀分布，计算两阶段仲裁把交换机全部 \(k\) 个输入端口同时匹配到 \(k\) 个输出端口的概率。将它与三阶段仲裁的匹配概率比较：后者允许每个输入端口同时提出两个请求，同样假设请求与许可均匀随机分布。 ### 习题 F.24 {#exercise-f-24} ✪ [15]〈F.5〉F.5 节的公式展示了 cut-through 交换的价值。用于构建集群的以太网交换机往往不支持 cut-through。对于 64 节点集群，比较在 1000 Mbit/s 以太网上传送 1500 字节时，使用和不使用 cut-through 所需的时间。假设每个以太网交换机耗时 1.0 μs，消息经过七个中间交换机。 ### 习题 F.25 {#exercise-f-25} ✪ [15]〈F.5〉沿用习题 F.24 的假设，对于 32 字节，cut-through 与存储转发的差别是什么？ ### 习题 F.26 {#exercise-f-26} ✪ [15]〈F.5〉降低延迟的一种方法是使用更大的交换机。与习题 F.24 不同，假设连接集群中任意两个节点只需三个中间交换机，其余参数与 F.24 相同。对于 1500 字节，cut-through 与存储转发的差别是什么？对于 32 字节呢？ ### 习题 F.27 {#exercise-f-27} ✪ [20]〈F.5〉使用 FlexSim 1.2（http://ceng.usc.edu/smart/FlexSim/flexsim.html）或其他周期精确的网络模拟器，模拟 256 节点二维 torus。采用虫孔路由、32 flit 分组、均匀随机通信模式，以及四个虚拟通道。比较三种方案的性能：采用 DOR 的确定性路由；使用逃逸路径的自适应路由，即 Duato 协议；以及使用前进式死锁恢复的真正完全自适应路由，即 Disha。仿照图 F.19的例题，分别画出延迟随施加负载变化和吞吐量随施加负载变化的曲线。对每种算法再分别用两个、八个虚拟通道运行模拟并绘图。比较并解释结果，说明虚拟通道的数量以及各算法使用通道的方式，如何影响网络性能、为什么会有这种影响。（提示：采集结果之前，应先预热数千个网络周期，确保模拟达到稳态。） ### 习题 F.28 {#exercise-f-28} ✪ [20]〈F.5〉重做习题 F.27，以位反转通信替代均匀随机通信。比较并解释结果，说明通信模式如何影响网络性能及其原因。 ### 习题 F.29 {#exercise-f-29} ✪ [40]〈F.5〉分别采用 16 flit 和 128 flit 分组，重做习题 F.27、F.28。比较并解释结果，说明分组大小与其他设计参数如何影响网络性能及其原因。 ### 习题 F.30 {#exercise-f-30} [20]〈F.2，F.4，F.5，F.8〉图 F.7、F.16 和 F.20 按机型列出了本书第四版出版时，TOP500 中若干超级计算机的互连网络特性。用最新 TOP500 更新这些表格。与原图数据相比，系统及其网络发生了怎样的变化？再利用图 F.29、F.31，对微处理器中的 OCN 以及面向集群的 SAN 作类似比较。 ### 习题 F.31 {#exercise-f-31} ✪ [12/12/12/15/15/18]〈F.8〉使用 M/M/1 排队模型作答。某网桥的测量结果显示，分组以每秒 200 个的速率到达，网关转发每个分组约需 2 ms。 a. [12]〈F.8〉网关利用率是多少？ b. [12]〈F.8〉网关中的平均分组数是多少？ c. [12]〈F.8〉分组在网关中停留的平均时间是多少？ d. [15]〈F.8〉改变到达率，画出响应时间随利用率变化的曲线。 e. [15]〈F.8〉对于 M/M/1 队列，系统中至少有 \(n\) 个任务的概率为 \(\mathrm{Utilization}^{n}\)。若 FIFO 能容纳 10 条消息，溢出概率是多少？ f. [18]〈F.8〉要使因 FIFO 溢出造成的丢包率低于百万分之一，网关的缓冲容量至少应为多大？ ### 习题 F.32 {#exercise-f-32} ✪ [20]〈F.8〉发送与接收时间不均衡，会导致网络性能问题。发送过快时，接收方来不及取出消息，网络发生积压，消息延迟上升。**带宽匹配**（bandwidth matching）提供了一种简单办法：降低发送方速率，使之与接收方性能匹配［Brewer 和 Kuszmaul 1994］。若两台机器通过 UDP 一类协议交换相同数量的消息，其中一台会领先，先发完自己的所有消息。接收方把这些消息全部存放好后，才发送自己的消息。估算这种情况与带宽匹配情况的性能。假设发送开销 200 μs，接收开销 300 μs，飞行时间 5 μs，延迟 10 μs，两台机器希望交换 100 条消息。 ### 习题 F.33 {#exercise-f-33} [40]〈F.8〉按照带宽匹配的建议，放慢 UDP 发送代码，使之与接收代码匹配，比较采用与不采用带宽匹配时的 UDP 性能［Brewer 和 Kuszmaul 1994］。设计实验，测定性能变化幅度。当两个节点发送到同一目的地时，应该怎样改变发送速率？当一个发送方向两个目的地发送时呢？ ### 习题 F.34 {#exercise-f-34} ✪ [40]〈F.6，F.8〉如果能使用 SMP 和集群，编写程序，测量处理器之间的通信延迟与通信带宽，如图 F.32（原书标注第 F-80 页）所示。 ### 习题 F.35 {#exercise-f-35} [20/20/20]〈F.9〉如果能使用 UNIX 系统，用 `ping` 探索 Internet。先阅读手册页，再不带选项标志运行 `ping`，确保能到达以下站点；它应报告 `X is alive`。根据所用系统，可能可以设置详细模式 `-v` 和路由追踪模式 `-R`，查看本机与目标机器之间的路径；也可能必须使用原书所称的 `trace route` 程序，此时请查阅其手册页。可以使用 UNIX 的 `script` 命令记录整个会话。 a. [20]〈F.9〉追踪到同一 LAN 中另一台机器的路由。延迟是多少？ b. [20]〈F.9〉追踪到校园内另一台不在同一 LAN 的机器的路由。延迟是多少？ c. [20]〈F.9〉追踪到校外另一台机器的路由。例如，如果你给朋友发电子邮件，可以试着追踪这条路由。看看能否查明沿途使用了哪些网络。延迟是多少？ ### 习题 F.36 {#exercise-f-36} [15]〈F.9〉使用 FTP 从远程站点传输文件，再在同一 LAN 的本地站点间传输。两次传输的带宽有什么差异？在一天中的不同时刻或一周中的不同日期再试。瓶颈在 WAN 还是 LAN？ ### 习题 F.37 {#exercise-f-37} ✪ [10/10]〈F.9，F.11〉图 F.41（原书标注第 F-93 页）对不同 TCP/IP 消息大小，比较了高带宽、高开销网络与低带宽、低开销网络的延迟。 a. [10]〈F.9，F.11〉对于哪些消息大小，高带宽网络提供的实际带宽更高？ b. [10]〈F.9，F.11〉对于 a 问中的消息大小，每种网络的实际带宽分别是多少？ ### 习题 F.38 {#exercise-f-38} ✪ [15]〈F.9，F.11〉利用图 F.41（原书标注第 F-93 页）的统计数据，估算每种网络的每条消息开销。 ### 习题 F.39 {#exercise-f-39} ✪ [15]〈F.9，F.11〉习题 F.37 计算了开销和峰值带宽不同的两个网络，在不同消息大小下哪个更快。利用图 F.41（原书标注第 F-93 页）的统计数据，低开销、低带宽网络能够更快传输的消息占百分之多少？高开销、高带宽网络能够更快传输的数据占百分之多少？ ### 习题 F.40 {#exercise-f-40} ✪ [15]〈F.9，F.11〉衡量互连延迟与带宽的一项有趣指标，是达到峰值带宽一半所需的消息大小。这个半峰值点借用向量处理术语，有时称为 \(n_{1/2}\)。利用图 F.41（原书标注第 F-93 页），估算使用 155 Mbit/s ATM 和 10 Mbit/s 以太网发送 TCP/IP 消息时的 \(n_{1/2}\)。 ### 习题 F.41 {#exercise-f-41} [讨论]〈F.10〉Google 集群曾由 1 机架单元（RU）的 PC 构成，每台有一个处理器、两个磁盘。如今有密度高得多的选择。若用现代方案替换这些 1 RU PC，能减少多少机房面积？访问 Compaq 或 Dell 网站，寻找密度最高的替代方案。估算这对设备成本、场地租金分别有什么影响？为达到良好的功耗／性能效率，互连网络设计会受到怎样的影响？ ### 习题 F.42 {#exercise-f-42} [讨论]〈F.13〉编写本书第四版时，Ethernet、InfiniBand、Advanced Switching 在机房中的竞争会如何发展，还不清楚。各自有什么技术优势和经济优势？系统维护人员为什么会偏好其中某一种？如今每种网络的流行程度如何？与 Myrinet、Quadrics 等专有商用网络相比如何？