ANDREW S. TANENBAUM 秒，约 533 msec。 ------COMPUTER NETWORKS FOURTH EDITION PROBLEM SOLUTIONS 8. A collection of five routers is to be connected in a point-to-point subnet. Collected and Modified By YanZhenXing, Mail To:zxyan@ecnu.cn Between each pair of routers, the designers may put a high-speed line, a Classify: EàEasy, MàMiddle, HàHard，DàDelete Green: Important Red: Master Blue: VI Others:Know Grey: Unnecessary Chapter 1 IntroductionProblems 2. An alternative to a LAN is simply a big timesharing system with terminals for all users. Give two advantages of a client-server system using a LAN.(M) 使用局域网模型可以容易地增加节点。 如果局域网只是一条长的电缆，且不会因个别的失效而崩溃( 服务 器)的情况下，使用局域网模型会更便宜。 使用局域网可提供更多的计算能力和更好交互式接口。 3. The performance of a client-server system is influenced by two network factors: the bandwidth of the network (how many bits/sec it can transport) and the latency (how many seconds it takes for the first bit to get from the client to the server). Give an example of a network that exhibits high bandwidth and high latency. Then give an example of one with low bandwidth and low latency.(E) 横贯大陆的光纤连接可以有很多千兆位/秒带宽， 但是由于光速度传送要越过数 千公里，时延将也高。 相反，使用 56 kbps 调制解调器呼叫在同一大楼内的计算机则有低带宽和较低的 时延。 4. Besides bandwidth and latency, what other parameter is needed to give a good characterization of the quality of service offered by a network used for digitized voice traffic?(M) 声音的传输需要相应的固定时间，因此网络时隙数量是很重要的。传输时间可以 用标准偏差方式表示。实际上，短延迟但是大变化性比更长的延迟和低变化性更糟。 6. A client-server system uses a satellite network, with the satellite at a height of 40,000 km. What is the best-case delay in response to a request?(E) 由于请求和应答都必须通过卫星，因此传输总路径长度为 160,000 千米。在空气 和真空中的光速为 300，000 公里/秒， 因此最佳的传播延迟为 160,000/300，000
例如采用镜像medium-speed line, a low-speed line, or no line. If it takes 100 ms of computer time 13. What is the principal difference between connectionless communication and to generate and inspect each topology, how long will it take to inspect all of
connection-oriented communication?(E)
them?(E)
将路由器称为 A，B，C，D 和 E. 则有 10 条可能的线路；AB, AC, AD, AE, BC, BD, BE, CD, CE,和 DE 每条线路有 4 410 = 1,048,576。
检查每个拓扑需要 100 ms，全部检查总共需要 104,857. 6 秒，或者稍微超过 29 个小时。
9. A group of 2n - 1 routers are interconnected in a centralized binary tree, with a router at each tree node. Router i communicates with router j by sending a message to the root of the tree. The root then sends the message back down to j. Derive an approximate expression for the mean number of hops per message for large n, assuming that all router pairs are equally likely.(H)
这意味着，从路由器到路由器的路径长度相当于路由器到根的两倍。 若在树中，
根深度为 1，深度为 n，从根到第 n 层需要 n-1 跳，在该层的路由器为 0.50。 从根到 n-1 层的路径有 router 的 0.25 和 n--2 跳步。 为：
l = 0.5*(n-1)+0.25*(n-2)+0.125*(n-3)…… 结果化简为 l＝n－2，平均路由路径为 2n-4。
10. A disadvantage of a broadcast subnet is the capacity wasted when multiple hosts attempt to access the channel at the same time. As a simplistic example,
suppose that time is divided into discrete slots, with each of the n hosts attempting to use the channel with probability p during each slot. What fraction of the slots are wasted due to collisions?(H) 区分 n-2 事件。 事件 1 到 n 由主机成功地、没有冲突地使用这条信道的事件组 成。 这些可能性的事件的概率为 p(1－p)n-1。事件 n+1 是一个空闲的信道，其概率 为(1- p)n。事件 n+2 是一个冲突。由于事件 n+2 互斥，它们可能发生的事件必须统
一合计。 冲突的可能性等于那些小部分的槽的浪费，只是 1－ np(1－p)n-1－ (1－p)n
11. What are two reasons for using layered protocols?(M) 通过协议分层可以把设计问题划分成较小的易于处理的片段 分层意味着某一层的协议的改变不会影响高层或低层的协议
因此，路径长度 l
种可能性(3
速度或者不是线路)，拓扑的总数为
连接的请求。第二阶段，只有在连接成功建立之后，保持连接状态，才能开始数据
主要的区别有两条。 17. In some networks, the data link layer handles transmission errors by
其一：面向连接通信分为三个阶段，第一是建立连接，在此阶段，发出一个建立 requesting damaged frames to be retransmitted. If the probability of a frame's being
传输。第三阶段，当数据传输完毕，必须释放连接。而无连接通信没有这么多阶段，
它直接进行数据传输。 其二：面向连接的通信具有数据的保序性， 而无连接的通信不能保证接收数据的
顺序与发送数据的顺序一致。 14. Two networks each provide reliable connection-oriented service. One of them offers a reliable byte stream and the other offers a reliable message stream. Are these identical? If so, why is the distinction made? If not, give an example of how they differ.(E)
不相同。在报文流中，网络保持对报文边界的跟踪；而在字节流中，网络不做这 样的跟踪。例如，一个进程向一条连接写了 1024 字节，稍后又写了另外 1024 字节。 那么接收方共读了 2048 字节。对于报文流，接受方将得到两个报文。每个报文 1024
字节。 而对于字节流，报文边界不被识别。接收方把全部的 2048 个字节当作一个
整体，在此已经体现不出原先有两个报文的事实。 15. What does ''negotiation'' mean when discussing network protocols? Give an example.(E)
协商就是要让双方就在通信期间将使用的某些参数或数值达成一致。最大分组长 度就是一个例子。
16. In Fig. 1-19, a service is shown. Are any other services implicit in this figure? If so, where? If not, why not?(E)
服务是由 k 层向 k＋1 层提供的。
服务必须由下层 k 提供，即，对层 k 的服务是由 k- 1 层提供的。
damaged is p, what is the mean number of transmissions required to send a frame? 21. List two ways in which the OSI reference model and the TCP/IP reference Assume that acknowledgements are never lost.(M) model are the same. Now list two ways in which they differ.（M）
k-1
假设某帧传到第 k 次才传输成功，起初 k-1 次传输皆尝试失败，概率为 p ,相似点：都是独立的协议栈的概念；层的功能也大体相似。 第 k
不同点：OSI 更好的区分了服务、接口和协议的概念，因此比 TCP/IP 具有更好
次传输成功，概率为(1-p) ，则发送一帧成功的平均传输次数为：
的
隐藏性，能够比较容易的进行替换；OSI 是先有的模型的概念，然后再进行协议的
实现，而 TCP/IP 是先有协议，然后建立描述该协议的模型；层次数量有差别；
1. Which of the OSI layers handles each of the following: TCP/IP a. (a) Dividing the transmitted bit stream into frames. 没有会话层和表示层，OSI 不支持网络互连。OSI 在网络层支持无连接和面向连接
的通信，而在传输层仅有面向连接的通信，而 TCP/IP 在网络层仅有一种通信模式b. (b) Determining which route through the subnet to use.（E）
（无 把传输的比特流划分为帧——数据链路层
连接），但在传输层支持两种模式。
决定使用哪条路径通过子网——网络层.
22. What is the main difference between TCP and UDP?（E）
19. If the unit exchanged at the data link level is called a frame and the unit
TCP 是面向连接的，而 UDP 是一种数据报服务。 exchanged at the network level is called a packet, do frames encapsulate packets or
25. When a file is transferred between two computers, two acknowledgement do packets encapsulate frames? Explain your answer.（E）
帧封装包。 当一个包到达数据链路层时，整个数据包，包括包头、数据及全部strategies are possible. In the first one, the file is chopped up into packets, which are
individually acknowledged by the receiver, but the file transfer as a whole is not 内
acknowledged. In the second one, the packets are not acknowledged individually,
容，都用作帧的数据区。或者说，将整个包放进一个信封(帧)里面，( 如果能
but the entire file is acknowledged when it arrives. Discuss these two approaches.
装入的
（E）
话)。
- 2 -
如果网络容易丢失分组，那么对每一个分组逐一进行确认较好，此时仅重传因为 丢失 许多无线设备需要移动，电池使用寿命不长也是其缺点之一。
的分组。
Chapter 2 The Physical Problems 如果网络高度可靠，那么在不发差错的情况下，仅在整个文件传送的结尾发送一
次确认，从而减少了确认的次数，节省了带宽；不过，即使有单个分组丢失，也需 要重传整个文件。 26. Why does ATM use small, fixed-length cells?（E） 因为这样可以迅速地经由交换机转发，并且这是在硬件上完成的。这样的设计使 2. A noiseless 4-kHz channel is sampled every 1 msec. What is the maximum data rate?（E） 得制造可以同时并行处理多个 CELLS 的硬件设备更加容易。另外，它们不会阻碍 传输线路很久，更加容易保证提供出高质量的服务。 28. An image is 1024 x 768 pixels with 3 bytes/pixel. Assume the image is uncompressed. How long does it take to transmit it over a 56-kbps modem channel? Over a 1-Mbps cable modem? Over a 10-Mbps Ethernet? Over 100-Mbps Ethernet?(E) 该图像大小为 1024 * 768 * 3 * 8 = 18,874,368 bits. 传输速率为 56Kbits/sec，需要 18,874,368 / 56,000 = 337.042 sec. 传输速率为 1Mbits/sec， 需要 18,874,368 / 106 = 18.874 sec. 传输速率为 10Mbits/sec，需要 18,874,368 / 107 = 1.887 sec. 传输速率为 100Mbits/sec，需要 18,874,368 / 108 = 0.189 sec. 29. Ethernet and wireless networks have some similarities and some differences. One property of Ethernet is that only one frame at a time can be transmitted on an Ethernet. Does 802.11 share this property with Ethernet? Discuss your answer.(E) 想象一下隐藏终端的问题。假设一个无线网络里有五台终端，从 A 至 E，使它们 每一台都只可以联系到与其相邻的两个邻居之一，那么 A 在与 B 通讯的同时 D 可 以与 E 进行通讯。因此无线网络有潜在的并行性，这与以太网上不同的。 30. Wireless networks are easy to install, which makes them inexpensive since installation costs usually far overshadow equipment costs. Nevertheless, they also have some disadvantages. Name two of them.（E）
无线网络的缺点：一是安全性，偶然出现在无线网络内的人都能监听到网络上传
递的消息；再有就是可靠性，无线网络在传输过程中会出现很多错误；另外，
由尼奎斯特定理，无噪声信道最大数据传输率=2Hlog2V b/s。依题有带宽 H =
4kHz，因此最大数据传输率决定于每次采样所产生的比特数（log2V）。 如果每次采样产生 16bits，那么数据传输率可达 128kbps； 如果每次采样产生 1024bits，那么可达 8.2Mbps。
3. Television channels are 6 MHz wide. How many bits/sec can be sent if four-level digital signals are used? Assume a noiseless channel.（E） 依题有带宽 H = 6MHz，每次采样 log2V = 2bit
由尼奎斯特定理，可发送的最大数据传输率为 2Hlog2V = 24Mbps。 4. If a binary signal is sent over a 3-kHz channel whose signal-to-noise ratio
- 3 - is 20
dB, what is the maximum achievable data rate?（M）
由香农定理信道比为 S/N 的有噪声信道的最大数据传输率 = Hlog2(1+S/N)。
依题知带宽 H = 3kHz，信噪比为 10lgS/N = 20 dB，知 S/N =100 由于 log2101≈6.658，该信道的信道容量为 3log2(1+100)=19.98kbps 再根据尼奎斯特定理，发送二进制信号的 3kHz 信道的最大数据传
输速率为
2Hlog2V = 2*3 log22 = 6kbps 综上，可以取得的最大数据传输速率为 6kbps。
5. What signal-to-noise ratio is needed to put a T1 carrier on a 50-kHz line?（M）
T1 信号的带宽 = 1.544 * 106Hz，为发送 T1 信号，由香农定理，最大数据传输率
= Hlog62(1+S/N) = 1.544 * 10Hz ，依题知带宽 H = 50 kHz，解得 S/N = 231–1 再由尼奎斯特定理 2Hlog2V = 2Hlog2S/N = 93 dB 所以，在 50kHz 线路上使用 T1 载波需要 93dB 的信
噪比。
7. How much bandwidth is there in 0.1 micron of spectrum at a wavelength of 1
micron?(M)
依题知频段为 0.1 ，波长为 1
因此，在 0.1 的频段中可以有 30THz。
12. Multipath fading is maximized when the two beams arrive 180 degrees out of
The screen is 480 x 640 pixels, each pixel being 24 bits. There are 60 screen images phase. How much of a path difference is required to maximize the fading for a per second. How much bandwidth is needed, and how many microns of wavelength 50-km-long 1-GHz microwave link?（E） are needed for this band at 1.30 microns?（M） 由公式 ，这里光速 c =300000km/s，依题 f=1GHz，所以微波的波长是 传输数据的速率为 480×\慇2X640×24×\慇2X60bps，即 442Mbps。
8. It is desired to send a sequence of computer screen images over an optical fiber.
30cm。 如果一个波比另一个波多行进 15cm，那么它们到达时将 180 异相。显然，答案与链 路长度是 50km 的事实无关。 18. A simple telephone system consists of two end offices and a single toll office to which each end office is connected by a 1-MHz full-duplex trunk. The average telephone is used to make four calls per 8-hour workday. The mean call duration is 6 min. Ten percent of the calls are long-distance (i.e., pass through the toll office). What is the maximum number of telephones an end office can support? (Assume 4 kHz per circuit.)（E） 需要 442Mbps 的带宽，对应的波长范围是 。 9. Is the Nyquist theorem true for optical fiber or only for copper wire?（D） 尼奎斯特定理是一个数学性质，不涉及技术处理。该定理说，如果你有一个函每部电话每小时做 0.5 次通话，每次通话 6 分钟。因此一部数，
电话每小时占用一条 它的傅立叶频谱不包含高于 f 的正弦和余弦，那么以 2 f电路 3 分钟，60/3=20，即 20 部电话可共享一条线路。由于只有 10%的呼叫是长 的频率采样该函数，那么 途， 你就可以获取该函数所包含的全部信息。因此尼奎斯特定理适用于所有介质。 所以 200 部电话占用一条完全时间的长途线路。局间干线复用了 1000000/4000=250 10. In Fig. 2-6 the lefthand band is narrower than the others. Why?（E） 条线路，每条线路支持 200 部电话，因此，一个端局可以支持的电话部数为 200*250=50000。. 21. The cost of a fast microprocessor has dropped to the point where it is now possible to put one in each modem. How does that affect the handling of telephone line errors?（E） 通常在物理层对于在线路上发送的比特不采取任何差错纠正措施。在每个调制解 调器中都包括一个 CPU 使得有可能在第一层中包含错误纠正码，从而大大减少第 二层所看到的错误率。由调制解调器做的错误处理可以对第二层完全透明。现在许 多调制解调器都有内建的错误处理功能。 22. A modem constellation diagram similar to Fig. 2-25 has data points at the following coordinates: (1, 1), (1, -1), (-1, 1), and (-1, -1). How many bps can a modem 得小，才能保持⊿f 大约相等。
with these parameters achieve at 1200 baud?（E）
顺便指出，3 个带宽大致相同的事实是所使用的硅的种类的一个碰巧的特性反映。
11. Radio antennas often work best when the diameter of the antenna is equal to
the wavelength of the radio wave. Reasonable antennas range from 1 cm to 5 meters
in diameter. What frequency range does this cover?（E） 由于这 3 个波段的频率范围大体上相等，根据公式 ， 小的波段⊿ 也
- 4 -
每个波特有 4 个合法值，因此比特率是波特率的两倍。
对应于 1200 波特，数据速率是 2400bps。 Mbps
23. A modem constellation diagram similar to Fig. 2-25 has data points at (0, 1) 的信道而言下载时间是 1.1msec，依题平均排队延迟时间也是 1.1msec，则总下载时 and (0, 2). Does the modem use phase modulation or amplitude modulation?（E） 间是 2.2msec，对 ADSL 而言并没有排队延迟时间，所以 1 Mbps 的下载时间是
40 相位总是 0，但使用两个振幅，因此这是直接的幅度调制。 24. In a constellation diagram, all the points lie on a circle centered on the origin. What kind of modulation is being used?（E） 如果所有的点都在同一圆周上，那么它们有着同样的幅度，所以没有使用幅度调 制。在星座图中从来就不使用频率调制，所以，这里所采用的编码是纯相位调制。 25. How many frequencies does a full-duplex QAM-64 modem use?（E） 全双工的 QAM-64 使用了两个频率。一个给上行流，一个给下行流。调制机制本 身只使用了相位和幅度调制，这里对频率不做调制。 26. An ADSL system using DMT allocates 3/4 of the available data channels to the downstream link. It uses QAM-64 modulation on each channel. What is the capacity of the downstream link?（M） DMT 指离散的多信道调制。这里总共有 256 条信道，减去 6 条给 POTS 以及再减 少 2 条用于控制，余下的 248 条留给数据。依题其中的 3/4 即 186 条信道给下行流。 ADSL 是以 4000 baud/s 进行调置。所以对 QAM-64（6 bits/baud）可得每条信道 的带宽为 24,000 bps 所以下行流总的带宽为 24,000 bps*186=4.464 Mbps 27. In the four-sector LMDS example of Fig. 2-30, each sector has its own 36-Mbps channel. According to queueing theory, if the channel is 50% loaded, the queueing time will be equal to the download time. Under these conditions, how long does it take to download a 5-KB Web page? How long does it take to download the page over a 1-Mbps ADSL line? Over a 56-kbps modem?（E）
LMDS 指本地多点分发服务。一个 5-KB 的网页数据量为 40,000 bits，对于 36
msec，在 56 kbps 的条件下下载时间是 714 msec.
28. Ten signals, each requiring 4000 Hz, are multiplexed on to a single channel using FDM. How much minimum bandwidth is required for the multiplexed channel? Assume that the guard bands are 400 Hz wide.（E） 对于 10 个 4000 Hz 干扰。
所需要的最小带宽为 4000 * 10 + 400 * 9 = 43,600 Hz
的信号，我们需要使用 9 个防护频段来避免可能的
b. (b) The T1 PCM system.（E）
两种情况下均为 8000 次采样/秒。使用 2 进制编码，则对 a 每次采样中发送 2 位
数据，对 T1 线路，每次采样发送 7 位数据。所以相对的最大数据传输率为： (a) 每次采样 2 比特的模拟编码 2Hlog2V = 16 kbps (b) T1 PCM 系统 2Hlog2V = 56 kbps
32. If a T1 carrier system slips and loses track of where it is, it tries to
29. Why has the PCM sampling time been set at 125 μsec?（E）
resynchronize using the 1st bit in each frame. How many frames will have to be
125 的采样时间对应于每秒 8000 次采样。一个典型的电话通道为 4kHz。根据inspected on average to resynchronize with a probability of 0.001 of being wrong? 尼 （M） 奎斯特定理，为获取一个 4kHz 的通道中的全部信10 个帧。 在数字通道上某些随机比特是 0101010101 模式的概率是 1/1024。息需要每秒 8000 次的采样频率。 察 30. What is the percent overhead on a T1 carrier; that is, what percent of the 1.544 Mbps are not delivered to the end user?（M）
T1 线路的每一帧中，端点用户使用 193 位中的 168（7*24）位，开销占 25（=193-168）
看 10 个帧，若每一帧中的第一位形成比特串 0101010101，则判断同步成功，而误 判的概率为 1/1024，小于 0.001。
33. What is the difference, if any, between the demodulator part of a modem and the coder part of a codec? (After all, both convert analog signals to digital ones.) (M) 有区别。编码器接受任意的模拟信号，并从它产生数字信号。而解调器仅仅接受 调制了的正弦（或余弦）波，产生数字信号。
位，因此开销比例等于 25/193=13%。
31. Compare the maximum data rate of a noiseless 4-kHz channel using a. (a) Analog encoding (e.g., QPSK) with 2 bits per sample.
- 5 -
34. A signal is transmitted digitally over a 4-kHz noiseless channel with one sample every 125 μsec. How many bits per second are actually sent for each of these
encoding methods?(M)
c. (a) CCITT 2.048 Mbps standard. d. (b) DPCM with a 4-bit relative signal value. e. (c) Delta modulation. a．CCITT 2.048Mbps 标准用 32 个 8 位数据样本组成一个 125 的基本帧，30 个 信道用于传信息，2 个信道用于传控制信号。在每一个 4kHz 信道上发送的数据率
就是 8*8000=64kbps。
b．差分脉码调制（DPCM）是一种压缩传输信息量的方法，它发送的不是每一次 =x/32。
37. In Fig. 2-37, the user data rate for OC-3 is stated to be 148.608 Mbps. Show how this number can be derived from the SONET OC-3 parameters.(H)
抽样的二进制编码值，而是两次抽样的差值的二进制编码。现在相对差值是 4 位， 所以对应每个 4kHz 信道实际发送的比特速率为 4*8000=32kbps。 c．增量调制的基本思想是：当抽样时间间隔 s t 很短时，模拟数据在两次抽样之
间的变化很小，可以选择一个合适的量化值 v 作为阶距。把两次抽样的差别近似为
不是增加一个 v 就是减少一个 v。这样只需用 1bit 二进制信息就可以表示一次抽样
结果，而不会引入很大误差。因此，此时对应每个 4kHz 信道实际发送的数据速率
为 1*8000=8kHz。
35. A pure sine wave of amplitude A is encoded using delta modulation, with x samples/sec. An output of +1 corresponds to a signal change of +A/8, and an output
signal of -1 corresponds to a signal change of -A/8. What is the highest frequency that can be tracked without cumulative error?(E) 在波的 1/4 周期内信号必须从 0 A。为了能够跟踪信号，在 T/4 的时间内 （假定波的周期是 T）必须采样 8 样 32 次，采样的时间间隔 是 1/x，因此波的全周期必须足够的长，使得能包含 32 32/x，或 f max
上升到 次，即每一个全波采次采样，即 T >
用户数据传输
速率是 49.546×\慇2X3＝148.608 Mbps。
39. What is the essential difference between message switching and packet switching?（E）
报文交换中，对于数据块的大小没有任何限制。
分组交换则对于数据块的大小有最大分组长度的限制，任何报文超出了这一限制 都会被分割成小块的多个分组。
40. What is the available user bandwidth in an OC-12c connection?（H）
产生 810 字节。由于
[[当一条线路（例如 OC-3）没有被复用，而是仅传输来自一个源的数据，则在线 路名称后面加一个字母 c（表示 conactenation，即串联）。因此，OC-3 表示了由 3 条独立的 OC-1 线路构成的一条 155.52Mbps 线路，而 OC-3c 表示来自于单个源的
155.52Mbps 的数据流。OC-3c 流内的 3 个 OC-1 流被按列交替插入，首先是流 1 的
基本的 SONET（同步光网络）帧是每 125
SONET 是同步
的，因此不论是否有实际要发送的数据，帧都存在。每秒 8000 帧的速率正好符合
所有数字电话系统中使用的 PCM 信道的采样率。对于 810 字节的 SONET 帧，通 - 6 - 常用 90 列乘以 9 行的矩形来描述，每个单元对应一个字节。每秒传送 8000 次，每
次 8*810=6480 位，总数据传输率为 51.84Mbps。这就是基本的 SONET 信道，它被
称作同步传输信号 STS-1，所有的 SONET 干线都是 STS-1 的倍数。每一帧的前 3 列 被保留，用于管理信息系统，前 3 行包含段开销，后 6 行包含线路开销。剩下的 87 列包含 87×9×8×8000＝50.112Mbps 的用户数据。用户数据（称为同步载荷信封，
即 SPE）可以从帧内的任一位置开始，并不限于第 1 行，第 4 列。线路开销的第一
行包含指向 SPE 的第一字节的指针，SPE 的第一列是路径开销。 路径开销不是严格的 SONET 结构，它在嵌入在载荷信封中。路径开销端到端的
流过网络，因此把它与端到端的运载用户信息的 SPE 相关联是有意义的。然而，它
从可提供给终端的用户数据中的 50.112Mbps 中又减去 1×9×8×8000＝0.576Mbps，
使之变成 49.536Mbps 。OC-3 相当于 3 个 OC-1 复用在一起，因此其
第 1 列，流 2 的第 1 列，流 3 的第 2 列，流 2 的第 2 列， 以此类推，最后形成 270 列宽 9
的第 1 列，随后是流 1
行高的帧。
为了使分组交换比电路交换快，必须：
OC-3c 流中的用户实际数据传输速率比 OC-3 流的速率略高（149.760Mbps所以：
和 43. Suppose that x bits of user data are to be transmitted over a k-hop path in a 148.608Mbps），因为路径开销仅在 SPE 中出现一次，而不是当使用 3 条单独 packet-switched network as a series of packets, each containing p data bits and h OC-1 header bits, with x >>p + h. The bit rate of the lines is b bps and the propagation 流时出现的 3 次。换句话说，OC-3c 中 270 列中的 delay is negligible. What value of p minimizes the total delay?（M） 260 列可用于用户数据，而在 所需要的分组总数是 x/p，因此加上头信息的总数据量为(p+h)x/p 位。 OC-3 中仅能使用 258 列。更高层次的串联帧（如 OC-12c）也存在这样的情况。]] 源端发送这些位需要时间为(p+h)x/pb， OC-12c 帧有 12*90=1080 列和 9 行。其中段开销和线路开销占 12*3=36中间的路由器重传最后一个分组所花的总时间为(k-1)(p+h)/b，
列，这
样同步载荷信封就有 1080-36=1044 列。SPE 中仅 1 列用于路径开销，结果就是 1043 列用于用户数据。
由于每列 9 个字节，因此一个 OC-12c 帧中用户数据比特数是 8 ×\慇2X9×1043＝75096。 每秒 8000 帧，得到用户数据速率 75096×8000 =600768000bps，即 600.768Mbps。 所以，在一条 OC-12c
连接中可提供的用户带宽是 600.768Mbps。 因此我们得到的总的延迟为 41. Three packet-switching networks each contain n nodes. The first network has a star topology with a central switch, the second is a (bidirectional) ring, and the third is fully interconnected, with a wire from every node to every other node. What are the best-, average-, and-worst case transmission paths in hops?（E） 三种网络的特性如下：
星型：最好为 2，最差为 2，平均为 2； 环型：最好为 1，最差为 n/2，平均为 n/4 如果考虑 n 为奇偶数，
则 n 为奇数时，最坏为（n-1）/2，平均为（n+1）/4 n 为偶数时，最坏为 n/2，平均为 n2/4(n1) 全连接：最好为 1，最差为 1，平均为 1。 ，
对该函数求 p 的导数，得到 ，令 得到
因为p＞0，所以 故 时能使总的延迟最小。 对于电路交换， t= s 时电路建立起来；t＝s+x/d 时报文的最后一位发送完毕；t= s+x/d+kb 时报文到达目的地。而对于分组交换，最后一位在 t=x/b时发送完毕。
为到达最终目的地，最后一个分组必须被中间的路由器重发 k-1 次，每次重发花
42. Compare the delay in sending an x-bit message over a k-hop path in a 时间 p/b，所以总的延迟为 circuit-switched network and in a (lightly loaded) packet-switched network. The circuit setup time is s sec, the propagation delay is d sec per hop, the packet size is p
bits, and the data rate is b bps. Under what conditions does the packet network have
a lower delay?(M)
44. In a typical mobile phone system with hexagonal cells, it is forbidden to reuse
a frequency band in an adjacent cell. If 840 frequencies are available, how many can
be used in a given cell?（B）
每个蜂窝单元都有 6 个邻居。假定中间的单元使用频率 A，它的邻居则可以依次
使用 B，C，B，C，B，C，也就是说，只需用三个相互独立的单元就足够 another,
the current call is abruptly terminated, even though all transmitters and receivers are functioning perfectly. Why?（E）
在邻近的蜂窝单元中频率不能复用。所以当一名用户从一个单元移动到另一个单 元时，必须给他分配一个新的频率。如果当用户移到一个新的单元，但是当前的新 单元中的所有频率都在使用中，则用户的呼叫必须被终止。
了。所以，
每个单元可以使用 280 种频率。
47. Sometimes when a mobile user crosses the boundary from one cell to
- 7 -
48. D-AMPS has appreciably worse speech quality than GSM. Is this due to the requirement that D-AMPS be backward compatible with AMPS, whereas GSM had
no such constraint? If not, what is the cause?（M） It is not caused directly by the need for backward compatibility. The 30 kHz channel
was indeed a requirement, but the designers of D-AMPS did not have to stuff three users
into it. They could have put two users in each channel, increasing the payload before error correction from 260 ×50=13 kbps to 260×\慇2X75 =19.5 kbps. Thus, the quality loss was
an intentional trade-off to put more users per cell and thus get away with bigger cells. 49. Calculate the maximum number of users that D-AMPS can support simultaneously within a single cell. Do the same calculation for GSM. Explain the difference.（M）
D-AMPS uses 832 channels (in each direction) with three users sharing a single channel. This allows D-AMPS to support up to 2496 users simultaneously per cell. GSM
uses 124 channels with eight users sharing a single channel. This allows GSM to support
up to 992 users simultaneously. Both systems use about the same amount of spectrum (25
MHz in each direction).
D-AMPS uses 30 KHz×\慇2X832 = 24.96 MHz. GSM uses 200 KHz ×\慇2X124 =24.80 MHz.
The difference can be mainly attributed to the better speech quality provided by GSM (13
Kbps per user) over D-AMPS (8 Kbps per user). 50. Suppose that A, B, and C are simultaneously transmitting 0 bits, using a CDMA system with the chip sequences of Fig. 2-45(b). What is the resulting chip sequence?（E）
传输 0，则时间片序列取其补码，传输 1，则时间序列取其本身。 将 A，B，C 相加后，取补码得结果为：(+3 +1 +1 -1 -3 -1 -1 +1).
51. In the discussion about orthogonality of CDMA chip sequences, it was stated
that if S?T = 0 then S??T is also 0. Prove this.(E)
percent
chance of arriving undamaged. If no error control is done by the data link protocol, how many times must the message be sent on average to get the entire thing through? （E）
由于每一帧有 0.8 p=0.810=0.107。
为使信息完整的到达接收方，发送一次成功的概率是 p 的概率正确到达，整个信息正确到达的概率为
，二次成功的概率
By definition
If T sends a 0 bit instead of 1 bit, its chip sequence is negated, with the i-th element
是
becoming Ti . Thus,
(1-p)p，三次成功的概率为(1-p)2 p，i 次
52. Consider a different way of looking at the orthogonality property of - 8 -
CDMA
chip sequences. Each bit in a pair of sequences can match or not match. Express the
orthogonality property in terms of matches and mismatches.
When two elements match, their product is +1. When they do not match, their product
is -1. To make the sum 0, there must be as many matches as mismatches. Thus, two chip
sequences are orthogonal if exactly half of the corresponding elements match and exactly
half do not match.
53. A CDMA receiver gets the following chips: (-1 +1 -3 +1 -1 -3 +1 +1). Assuming
the chip sequences defined in Fig. 2-45(b), which stations transmitted, and which
bits did each one send?（E）
分别与（-1 +1 -3 +1 -1 -3 +1 +1）做内积：
A：（-1 +1 -3 +1 -1 -3 +1 +1）d (-1 -1 -1 +1 +1 -1 +1 +1) /8 = 1 B：（-1 +1 -3 +1 -1 -3 +1 +1）d (-1 -1 +1 -1 +1 +1 +1 -1) /8 = -1 C：（-1 +1 -3 +1 -1 -3 +1 +1）d (-1 +1 -1 +1 +1 +1 -1 -1) /8 = 0 D：（-1 +1 -3 +1 -1 -3 +1 +1）d (-1 +1 -1 -1 -1 -1 +1 -1) /8 = 1
所以 A，D 发送的都是 1 bits，B 发送的是 0 bit,，C 没有发送 Chapter 3 The Data Link Layer Problems
1. An upper-layer packet is split into 10 frames, each of which has an 80
次成功的概率为(1-p)i-1p，因此平均的发送
数等于：
2. The following character encoding is used in a data link protocol: A: 01000111;
B: 11100011; FLAG: 01111110; ESC: 11100000 Show the bit sequence of
a single bit to cause an error not detected by the checksum? If not, why not? If so, how? Does the checksum length play a role here?（M） 可能。假定原来的正文包含位序列 01111110 将变成 011111010。如果由于传输错误第二个 0
作为数据。位填充之后，这个序列 丢失了，收到的位串又变成
transmitted
(in binary) for the four-character frame: A B ESC FLAG when each of the following framing methods are used: a. (a) Character count.
b. (b) Flag bytes with byte stuffing.
c. (c) Starting and ending flag bytes, with bit stuffing.（E） 结果为
(a)字符计数 00000101 01000111 11100011 11100000 01111110
(b)字节填充 01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110
(c)位填充 01111110 01000111 110100011 111000000 011111010 01111110
3. The following data fragment occurs in the middle of a data stream for which the byte-stuffing algorithm described in the text is used: A B ESC C ESC FLAG FLAG D. What is the output after stuffing?（E）
填充后结果为：A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D. 4. One of your classmates, Scrooge, has pointed out that it is wasteful to end each
frame with a flag byte and then begin the next one with a second flag byte. One flag
byte could do the job as well, and a byte saved is a byte earned. Do you agree?（E）
只用一个标记位无法知道一帧何时结束。如果帧流是无限量的，一个标记位或许
是可以的。但是当一帧以标记位结束了之后，在一段时间内（比如 15 分钟）没有新
的帧到达时，接收者如何来分辨出下一字节是真正的新帧的开始还是碰巧是线路上
的噪声呢？这样的协议设计的过于简单了。
5. A bit string, 0111101111101111110, needs to be transmitted at the data link layer. What is the string actually transmitted after bit stuffing?（E） 输出：011110111110011111010.
6. When bit stuffing is used, is it possible for the loss, insertion, or modification
01111110，被接收方看成是帧尾。然后接收方在该串的前面寻找检验和，并对它进
行验证。如果检验和是 16 位，那么被错误的看成是检验和的 16 位的内容碰巧经验
证后仍然正确的概率是 1/216。如果这种概率的条件成立了，就会导致不正确的帧被
接收。显然，检验和段越长，传输错误不被发现的概率会越低，但该概率永远不等 于零。
16. Data link protocols almost always put the CRC in a trailer rather than in a
header. Why?（E）
CRC 是在发送期间进行计算的。一旦把最后一位数据送上外出线路，就
numbers be?（M）
为了有效运行，序列空间（实际上就是发送窗口大小）必须足够的大，以允许发 送方在收到第一个确认应答之前可以不断发送。信号在线路上的传播时间为 6×3000=18000 在 T1 速率，发送 64
帧需花的时间：64×8÷(1.536×106)= 0.33
，即 18ms。
字节的数据。
所以，发送的第一帧从开始发送起，18.33ms 后完全到达接收方。确认应答又花 了很少的发送时间（忽略不计）和回程的 18ms。这样，加在一起的时间是 36.33ms。
发送方应该有足够大的窗口，从而能够连续发送 36.33ms。 36. 33/0.33=110
也就是说，为充满线路管道，需要至少 110 帧，因此序列号为 立即把
CRC 编码附加在输出流的后面发出。如果把 CRC 放在帧的头部，那7 位。 么就要在发送 这一题有争议的地方是 T1 的速度，T1 的数据速率根据它的结构应该是（193-1-24） 之前把整个帧先检查一遍来计算 CRC。这样每个字节都要处理两遍，第一/193*1.544=1.344mbps,但是答案中是（193-1）/193*1.544=1.536mbps。 遍是为了
- 9 -
计算检验码，第二遍是为了发送。把 CRC 放在尾部就可以把处理时间减半。
17. A channel has a bit rate of 4 kbps and a propagation delay of 20 msec. For
what range of frame sizes does stop-and-wait give an efficiency of at least 50 percent? （E）
当发送一帧的时间等于信道的传播延迟的 2
倍时，信道的利用率为
50%。或者说，
当发送一帧的时间等于来回路程的传播延迟时，效率将是 50%。而在帧长满足发送
时间大于延迟的两倍时，效率将会高于 50%。 现在发送速率为 4Mb/s，发送一位需要 0.25 。
只有在帧长不小于 160kb 时，停等协议的效率才会至少达到 50%。
18. A 3000-km-long T1 trunk is used to transmit 64-byte frames using protocol 5.
If the propagation speed is 6 μsec/km, how many bits should the sequence
19. In protocol 3, is it possible that the sender starts the timer when it is already running? If so, how might this occur? If not, why is it impossible?(M)
协议 3 中，发送者有可能启动一个已经运行着的计时器。假设发送者传输一帧并 且迅速返回一个错误的确认。主循环将会执行一段时间并且将会发送一帧，然而这 可能导致死锁。
假定有一组帧正确到达，并被接收。然后，接收方会向前移动窗口。现在假定所
时计时器仍然是运行着的。 20. Imagine a sliding window protocol using so many bits for sequence numbers that wraparound never occurs. What relations must hold among the four window edges and the window size, which is constant and the same for both the sender and the receiver.(M) 使发送者的窗口为 (Sl , Su) 之间的关系应满足： 0 <= Su- Sl +1 <= W1 Ru - Rl + 1 = W Sl <= Rl <=Su + 1 21. If the procedure between in protocol 5 checked for the condition a <= b <=c instead of the condition a <= b < c, would that have any effect on the protocol's correctness or efficiency? Explain your answer.（H） 改变检查条件后，协议将变得不正确。 假定使用 3 位序列号，考虑下列协议运行过程：A 站刚发出 7 号帧；B 站接收到 这个帧，并发出捎带应答 ack；A 站收到 ack，并发送 0~6 号帧。假定所有这些帧都 ，接收者的窗口为 (Rl , Ru)，窗口大小为 W，则它们 在传输过程中丢失了；B 站超时，重发它的当前帧，此时捎带的确认号是 7；考察 A 站在 r.rack = 7 到达时的情况，关键变量是 ack_expected = 0，r.rack = 7， next_frame_to_send_= 7。 修改后的检查条件将被置成―真‖，不会报告已发现的丢失帧错误，而误认为丢失 了的帧已被确认。另一方面，如果采用原先的检查条件，就能够报告丢失帧的错误。 所以结论是：为保证协议的正确性，已接收的确认应答号应该小于下一个要发送的 序列号。 22. In protocol 6, when a data frame arrives, a check is made to see if the sequence number differs from the one expected and no_nak is true. If both
conditions hold, a NAK is sent. Otherwise, the auxiliary timer is started. Suppose that the else clause were omitted. Would this change affect the protocol's correctness?(M)
有的确认帧都丢失了，发送方最终会产生超时事件，并且再次发送第一帧，接收方
A 站发送 0 号帧给 B 站。B 站收到此帧，并发送 ACK 帧，但 ACK 丢失了。A 站
将发送一个 NAK。然后 NONAK 被置成伪。假定 NAK
发生超时，重发 0 号帧。但 B 站现在期待接收 1 号帧，因此发送 NAK，否
也丢失了。那么从这个时 定收到
候开始，发送方会不断发送已经被接收方接受了的帧。接收方只是忽略这些帧，但 的 0 号帧。显然，现在 A 站最好不重发 0 号帧。由于条件 由于 NONAK 为伪，所以不会再发送 NAK，从而产生死锁。如果设置辅助计数器 r.rack+1 removed from the code. Would this affect the correctness of the protocol or just the 就说明了这段程序中的另一个条件，即 r.rack+1 删除这一段程序会影响协议的正确性，导致死锁。因为这一段程序负责处理接收 26. Imagine that you are writing the data link layer software for a line used to 到的确认帧，没有这一段程序，发送方会一直保持超时条件，从而使得协议的运行 send data to you, but not from you. The other end uses HDLC, with a 3-bit sequence 不能向前进展。 number and a window size of seven frames. You would like to buffer as many out-of-sequence frames as possible to enhance efficiency, but you are not allowed to 24. Suppose that the case for checksum errors were removed from the switch statement of protocol 6. How would this change affect the operation of the protocol? modify the software on the sending side. Is it possible to have a receiver window greater than 1, and still guarantee that the protocol will never fail? If so, what is the （M） largest window that can be safely used?（E） 这将会失去使用 NAKs 的目的，因此我们不得不回退到超时。尽管性能上有所下 降，但是不影响协议的正确性。NAKs 并不是关键的。 25. In protocol 6 the code for frame_arrival has a section used for NAKs. This section is invoked if the incoming frame is a NAK and another condition is met. Give a scenario where the presence of this other condition is essential.（M） 这里要求 r.rack+1 不可以。最大接收窗口的大小就是 1。现在假定该接收窗口值变为 2。开始时发送 方发送 0 至 6 号帧，所有 7 个帧都被收到，并作了确认，但确认被丢失。现在接 收方准备接收 7 号和 0 号帧，当重发的 0 号帧到达接收方时，它将会被缓存保留， - 10 - 接收方确认 6 号帧。当 7 号帧到来的时候，接收方for 将把 7 号帧和缓存的 0 号帧传 d. (a) Stop-and-wait. 递给主机，导致协议错误。因此，能够安全使用的最大窗口值为 1。 e. (b) Protocol 5. 27. Consider the operation of protocol 6 over a 1-Mbps error-free line. The f. (c) Protocol 6.（E） maximum frame size is 1000 bits. New packets are generated 1 second apart. The 对应三种协议的窗口大小值分别是 1、7 和 4。 timeout interval is 10 msec. If the special acknowledgement timer were eliminated, unnecessary timeouts would occur. How many times would the average message be 使用卫星信道端到端的典型传输延迟是 270ms，以 1Mb/s transmitted?（E） 1000bit 长的帧 发送 1 位用时间 1 ，发送 1000bit 的最长帧花时间 1ms。由于超时间隔是 10ms， 而 1s 才能产生一个新的数据帧，所以超时是不可避免的。假定 A 站向 B 站发送 一个帧，正确到达接收方，但较长时间无反向交通。不久，A 站发生超时事件，导 致重发已发过的一帧。 B 站发现收到的帧的序列号错误，因为该序列号小于所期待接收的序列号。因此 B 站将发送一个 NAK，该 NAK 会携带一个确认号，导致不再重发该帧。结果每个 帧都被发送两次。 28. In protocol 6, MAX_SEQ = 2n - 1. While this condition is obviously desirable to make efficient use of header bits, we have not demonstrated that it is essential. Does the protocol work correctly for MAX_SEQ = 4, for example?（M） 不能，协议的运行将会失败。当 MaxSeq=4，序列号的模数=4+1=5，窗口大小将 等于：NrBufs<=5/2=2.5，即得到，NrBufs=2。因此在该协议中，偶数序号使用缓冲 区 1。这种映射意味着帧 4 和 0 将使用同一缓冲区。假定 0 至 3 号帧都正确收到了， 并且都确认应答了，并且都确认应答了。如果随后的 4 号帧丢失，且下一个 0 号帧 收到了，新的 0 号帧将被放到缓冲区 0 中，变量 arrived[0]被置成―真‖。这样，一个 失序帧将被投递给主机。事实上，采用选择性重传的滑动窗口协议需要 MaxSeq 是 奇数才能正确的工作。然而其他的滑动窗口协议的实现并不具有这一性质。 29. Frames of 1000 bits are sent over a 1-Mbps channel using a geostationary satellite whose propagation time from the earth is 270 msec. Acknowledgements are always piggybacked onto data frames. The headers are very short. Three-bit sequence numbers are used. What is the maximum achievable channel utilization 发送， 的发送时间为 1ms。我们用 t=0 表示传输开始的时间，那么在 t=1ms 时，第一帧发 送完毕；t=271ms 时，第一帧完全到达接收方；t=272ms，对第一帧的确认帧发送完 毕；t=542ms，带有确认的帧完全到达发送方。因此一个发送周期为 542ms。如果在 542ms 内可以发送 k 个帧，由于每一个帧的发送时间为 1ms，则信道利用率为 k/542， 因此： （a） k=1，最大信道利用率=1/542=0.18% （b） k=7，最大信道利用率=7/542=1.29% （c） k=4，最大信道利用率=4/542=0.74% 第一帧 发送完毕； t=270+80=350ms，第一帧完全到达接收方；t=350+80=430ms，对第一帧作捎带确 认的反向数据帧可能发送完毕；t=430+270=700ms，带有确认的反向数据帧完全到 达发送方。因此，周期为 700ms，发送 128 帧时间 80*128=10240ms，这意味着传 输管道总是充满的。每个帧重传的概率为 0.01，对于 3960 个数据位，头开销为 40 位，平均重传的位数为 4000*0.01=40 位，传送 NAK 的平均位数为 40*1/100=0.40 位，所以每 3960 个数据位的总开销为 80.4 位。 因此，开销所占的带宽比例等于 80.4/(3960+80.4)=1.99%。 31. Consider an error-free 64-kbps satellite channel used to send 512-byte data frames in one direction, with very short acknowledgements coming back the other way. What is the maximum throughput for window sizes of 1, 7, 15, and 127? The earth-satellite propagation time is 270 msec.（M） 30. Compute the fraction of the bandwidth that is wasted on overhead (headers and retransmissions) for protocol 6 on a heavily-loaded 50-kbps satellite channel with data frames consisting of 40 header and 3960 data bits. Assume that the signal 使用卫星信道端到端的传输延迟为 270ms，以 64kb/s 发送，周期等于 propagation time from the earth to the satellite is 270 msec. ACK frames never 604ms。发 occur. NAK frames are 40 bits. The error rate for data frames is 1 percent, and the 送一帧的时间为 64ms，我们需要 604/64=9 个帧才能保持通道不空。 error rate for NAK frames is negligible. The sequence numbers are 8 bits.（M） 发送 4096 位，吞吐率为 使用选择性重传滑动窗口协议，序列号长度是 8 位。窗口大小为 128。卫星信对于窗口值 1，每 604ms 道 端到端的传输延迟是 270ms。以 50kb/s 的发 送时间是 0.02*4000=80ms。我们用 t=0 4096/0.604=6.8kb/s。 发送 4096*7 位，吞吐率为 发送，4000bit（3960+40）长的数据帧对于窗口值 7，每 604ms 4096*7/0.604=47.5kb/s。 表示传输开始时间，那么，t=80ms，对于窗口值超过 9（包括 15、127），吞吐率达到最大值，即 64kb/s。 - 11 - 32. A 100-km-long cable runs at the T1 data rate. The propagation speed in the cable is 2/3 the speed of light in vacuum. How many bits fit in the cable?（E） 在该电缆中的传播速度是每秒钟 200 000km，即每毫秒 200km，因此 100km T1 帧，即 193*4=772bit。 33. Suppose that we model protocol 4 using the finite state machine model. How many states exist for each machine? How many states exist for the communication channel? How many states exist for the complete system (two machines and the channel)? Ignore the checksum errors.（M） 每台机器都有两个关键的变量 next3frame3to3send and frame3expected，每个都可 以取值 0 或 1。因此，每台机器都有四种可能的状态。在信道上的一个消息包含了 要被发送的帧的序列号和被确认的帧的序列号。因此，存在四种类型的消息。信道 的电 缆将会在 0.5ms 内填满。T1 速率 125 传送一个 193 位的帧，0.5ms 可以传送 4 个 激发序列是 10，6，2，8。它通信去接收一个偶数，确认丢失，发送者超时，并 且重新由接收者生成确认。 35. Given the transition rules ACàB, BàAC, CDàE, and EàCD, draw the Petri net described. From the Petri net, draw the finite state graph reachable from the initial state ACD. What well-known concept do these transition rules model?(E) 可能在每个方向上有 0 或 1 条消息。所以，信道上状态的数量是带着 0 条消息的 1 个，带着 1 条消息的 8 个，带着 2 条消息的 16 个 (每个方向上只有一条消息)。 总共有 1 + 8 + 16 = 25 种可能的信道状态。对完整的系统这隐含了 4*4*25 =400 种可能的状态。 34. Give the firing sequence for the Petri net of Fig. 3-23 corresponding to the state sequence (000), (01A), (01—), (010), (01A) in Fig. 3-21. Explain in words what the sequence represents.（M） Petri 网和状态图如下 系统模型是互斥的。 B 和 E 是关键段它们不能同时被激活，例如不允许状态 BE， 位置 C 代表一个符号它可以被 A 或 D 推出，但是不能同时被 AD 推出。 本题是关于 Petri 网的，根据题目的描述，应该是 B 推出 C，E 推出 C，所以答案 的图箭头应该由 B、E 指向 C。 - 12 - Chapter 4 The Medium Access Control Sublayer Problems e. (b) What is the probability of exactly k collisions and then a success? f. (c) What is the expected number of transmission attempts needed?（M） 1. For this problem, use a formula from this chapter, but first state the formula. Frames arrive randomly at a 100-Mbps channel for transmission. If the channel is （a）在任一帧时间内生成 k 帧的概率服从泊松分布 busy when a frame arrives, it waits its turn in a queue. Frame length is exponentially distributed with a mean of 10,000 bits/frame. For each of the following 生成 0 帧的概率为 e-G；对于纯的 ALOHA，发送一帧的冲突危险区为两个帧时， frame arrival rates, give the delay experienced by the average frame, including both 在两帧内无其他帧发送的概率是 e-G×e –G=e-2G；对于分隙的 ALOHA，由于冲突危险 queueing time and transmission time.（E） 区减少为原来的一半，任一帧时内无其他帧发送的概率是 e-G。 a. (a) 90 frames/sec. b. (b) 900 frames/sec. c. (c) 9000 frames/sec. 排队理论延迟时间公式： ，这里信道容量 C=108 and ，所以 现在时隙长度为 40ms，即每秒 25 个时隙，产生 50 次请求， 所以每个时隙产生 两个请求，G=2。因此，首次尝试的成功率是：e-2= 1/ e2 （b） （c）尝试 k 次冲突，第 k 次才能发送成功的概率（即前 k-1次才成功）为： sec，对上面的三种帧到达率?，有 (a) 0.1 msec,(b) 0.11 msec, (c) 1 msec. 对于 (c)， 10 倍延迟。 由 sec. What is the approximate total channel load?（E） 2. A group of N stations share a 56-kbps pure ALOHA channel. Each station μoutputs a 1000-bit frame on an average of once every 100 sec, even if the previous 每个终端每 200（=3600/18）秒做一次请求，总共有 10 000 个终端，因此，总的 秒做 10000 次请求。平均每秒钟 50 次请求。每one has not yet been sent (e.g., the stations can buffer outgoing frames). What is 负载是 200 秒钟 8000 个时隙，所 the 以平均每个时隙的发送次数为 50/8000=1/160。 maximum value of N?（E） 5. A large population of ALOHA users manages to generate 50 requests/sec, 对于纯的 ALOHA，信道利用率为 1/e2= 0.184，可用的带宽是 0.184×56 Kb/s=10.304Kb/ s。每个站需要的带宽为 1000/100=10b/s。而N=10304/10≈1030 including both originals and retransmissions. Time is slotted in units of 40 msec. d. (a) What is the chance of success on the first attempt? 所以，最多可以有 1030 个站，即 N 的最大值为 1030。 3. Consider the delay of pure ALOHA versus slotted ALOHA at low load. Which one is less? Explain your answer.（E） 对于纯的 ALOHA，发送可以立即开始。对于分隙的 ALOHA，它必须等待下一个 时隙。这样，平均会引入半个时隙的延迟。因此，纯 ALOHA 小。 的延迟比较4. Ten thousand airline reservation stations are competing for the use of a single slotted ALOHA channel. The average station makes 18 requests/hour. A slot is 125 7. In an infinite-population slotted ALOHA system, the mean number of slots a 那么每帧传送次数的数学期望为 6. Measurements of a slotted ALOHA channel with an infinite number of station waits between a collision and its retransmission is 4. Plot the delay versus throughput curve for this system.（M） users show that 10 percent of the slots are idle. g. (a) What is the channel load, G? h. (b) What is the throughput? i. (c) Is the channel underloaded or overloaded?(E) （a）从泊松定律得到 p0= e –G ，因此 G = - lnp0 = - ln0.1 = 2.3 （b） S = G e-G， G = 2.3，e –G=0.1 ，S = 2.3*0.1 = 0.23 （c）因为每当 G>1 时，信道总是过载的，因此在这里信道是过载 的。 每帧传送次数的数学期望为： E 个事件为 E-1 个长度等于 4 个时隙的间隔时间所分隔。因此一 个帧从第一次 发送开始时间到最后一次尝试成功的发送开始时间之间的长度即延迟是 4(eG1)，吞 吐率 S= Ge-G。 对于每一个 G 值，都可以计算出对应的延迟值 D=4(eG-1)，以及吞吐率值 S=Ge-G 。 - 13 - are needed to resolve the contention?（E） 8. How long does a station, s, have to wait in the worst case before it can start 在自适应树遍历协议中，可以把站点组织成二叉树（见图）的形式。在一次成功 transmitting its frame over a LAN that uses 的传输之后，在第一个竞争时隙中，全部站都可以试图获得信道，如果仅其中之一 需用信道，则发送冲突，则第二时隙内只有那些位于节点 B 以下的站（0j. (a) the basic bit-map protocol? 到 7）可 k. (b) Mok and Ward's protocol with permuting virtual station numbers? 以参加竞争。如其中之一获得信道，本帧后的时隙留给站点 C 以下的（M） 站；如果 B 点 (a) The worst case is: all stations want to send and s is the lowest numbered station. Wait time N bit contention period + (N-1)d bit for transmission of frames. The total is N+(N-1)dbit times. (b) The worst case is: all stations have frames to transmit and s has the lowest virtual station number. Consequently, s will get its turn to transmit after the other N-1 stations have transmitted one frame each, and N contention periods of size log2 N each. Wait time is thus(N+1)×\慇2Xd+N×log2 bits. 当竞争周期刚刚扫瞄过的时候，N 号站点正好由数据发送，所以他要等到数据 1 发送完（最差时前面 N-1 个站点都有数据要发，即（N-1）*d）,然后下一个扫描周 期（N 位），再等前面所有站点发送完数据；所以总的延迟为： （N-1）*d+N+(N-1)*d=2（N-1）*d+N ; 9. A LAN uses Mok and Ward's version of binary countdown. At a certain instant, the ten stations have the virtual station numbers 8, 2, 4, 5, 1, 7, 3, 6, 9, and 0. The next three stations to send are 4, 3, and 9, in that order. What are the new virtual station numbers after all three have finished their transmissions?（E） 当 4 站发送时，它的号码变为 0，而 0、1、2 和 3 号站 的号码都增 1，10 个站 点的虚站号变为 8，3，0，5，2，7，4，6，9，1 当 3 站发送时，它的号码变为 0，而 0、1 和 2 站的号码都 增 1，10 个站点的虚 站号变为：8，0，1，5，3，7，4，6，9，2 最后，当 9 站发送时，它变成 0，所有其他站都增 1，结果是：9，1，2，6，4， 按此方法即可画出时延对吞吐率的曲线。 8，5，7，0，3。 10. Sixteen stations, numbered 1 through 16, are contending for the use of a shared channel by using the adaptive tree walk protocol. If all the stations whose addresses are prime numbers suddenly become ready at once, how many bit slots 下面有两个或更多的站希望发送，在第二时隙内会发生冲突，于是第三时隙内由 D 节点以下各站来竞争信道。 的时隙数取决于为了到达准备好发送的两个站的共同先辈点必须往回走多少级。先 计算这两个站具有共同的父节点的概率 p1。在 2n个站中，要发送的两个站共享一个 指定的父节点的概率是 - 14 - 本题中，站 2、3、5、7、11 隙，每个时隙内参加竞 争的站的列表如下： 第一时隙：2、3、5、7、11、13 第二时隙：2、3、5、7 第三时隙：2、3 第四时隙：2 第五时隙：3 第六时隙：5、7 第七时隙：5 第八时隙：7 第九时隙：11、13 第十时隙：11 第十一时隙：13 和 13 要发送，需要 11 个时 11. A collection of 2n stations uses the adaptive tree walk protocol to arbitrate access to a shared cable. At a certain instant, two of them become ready. What are the minimum, maximum, and mean number of slots to walk the tree if 2n >>1?（H） 2 n个站点对应 n+1 级，其中 0 级有 1 个节点，1 级有 2 个节点， n 级有 2 n个 节点。在 i 级的每个节点下面所包括的站的个数等于总站数的 1/2i。本题中所需要 12. The wireless LANs that we studied used protocols such as MACA instead of 总共 2 n-1 个父节点，所以， using CSMA/CD. Under what conditions, if any, would it be possible to use CSMA/CD instead?(E) 因为 2n >>1，所以 p≈2- n 在共享父节点的条件下遍历树，从第二级开始每一级访问两个节点，这样遍历树 如果所有站的发射有效范围都很大，以至于任一站都可以收到所有其他站发送的 所走过的节点总数 n1= 1+2+…+2+2=1=2n，接下来，我们考察两个发送站共享祖父 信号，那么任一站都可以与其他站以广播方式通信。在这样的条件下，CSMA/CD 可 节点的概率 p2和遍历树所走过的节点总数 n2。此时在每个父节点下面仅可能有一 以工作的很好。 个 站发送。两个发送站共享一个指定的祖父节点的概率是 1/ C22n-1。 共有 2n-2 个祖父节点 遍历树比 1 n 减少两个节点，即 级祖先 13. What properties do the WDMA and GSM channel access protocols have in common? See Chap. 2 for GSM. (E) 两种协议都使用 FDM 和 TDM 结合的方法，它们都可以提供专用的频道（波长）， 并且都划分时隙，实现 TDM。 14. Six stations, A through F, communicate using the MACA protocol. Is it possible that two transmissions take place simultaneously? Explain your answer.(E) 是的。想像一下它们都在一条直线上并且每个站都只能连到它最近的邻居，那么 A 可以发送给 B 同时 E 正发送给 F 通过类似的分析和计算，可以得到，两个发送站共享曾祖父节点（属 n-3 节点）的概率是 p3= 2-n+2 遍历树所经过的节点总数比 n2又少两个节点， 15. A seven-story office building has 15 adjacent offices per floor. Each office contains a wall socket for a terminal in the front wall, so the sockets form a rectangular grid in the vertical plane, with a separation of 4 m between sockets, both horizontally and vertically. Assuming that it is feasible to run a straight cable between any pair of sockets, horizontally, vertically, or diagonally, how many 因此，最坏的情形是 2n+1 个时隙（共享父节点），对应于 i=0； 最好的情形是 3 个时隙，对应于 i=n-1 （两个发送站分别位于左半树和右半meters of cable are needed to connect all sockets using 树）， l. (a) a star configuration with a single router in the middle? m. (b) an 802.3 LAN? (E) (a) 从一到七层记数。在星形配置中，路由器在第四层中央。需要铜线的站个数 7 所以平均时隙数等于 *15 – 1=104 sites. 这些铜线的总长度 =1832 meters. ，总共 该表达式可以简化为 (b) 对 802.3, 7 水平铜线每层需要 56 m 长，加上竖直方向的共 24 m 416 m. 16. What is the baud rate of the standard 10-Mbps Ethernet?（E） 最小为 3 个，最大为 n+2 个，给出的答案最大不对。 最大的情况为两个站点兄弟，共父母。 两个黄色的园代表要发数据的站点 所以在这种情况下的时槽为：数的路径长度加 2 即： n+2 以太网使用曼彻斯特编码，这就意味着发送的每一位都有两个信号周期。标准以 太网的数据率为 10Mb/s，因此波特率是数据率的两倍，即 20MBaud。 17. Sketch the Manchester encoding for the bit stream: 0001110101.(E) 信号是一个二植方波高 (H) 和 低(L)，形式为 LHLHLHHLHLHLLHHLLHHL. 18. Sketch the differential Manchester encoding for the bit stream of the previous problem. Assume the line is initially in the low state.(E) - 15 - 对于 1km 电缆，单程传播时间为 1/200000=5×10-6 s=5 ，往返传播时间为 2t 工作，最小帧19. A 1-km-long, 10-Mbps CSMA/CD LAN (not 802.3) has a propagation speed of =10 。为了能够按照 CSMA/CD 。以 1Gb/s 200 m/μsec. Repeaters are not allowed in this system. Data frames are 256 bits long, 的发射时间不能小于 10 -6-9 including 32 bits of header, checksum, and other overhead. The first bit slot after a 速率工作，10 可以发送的比特数等于：（10*10）/（1*10）=10000 因此，最小帧是 10000 bit = 1250 字节长。 successful transmission is reserved for the receiver to capture the channel in order to send a 32-bit acknowledgement frame. What is the effective data rate, excluding 22. An IP packet to be transmitted by Ethernet is 60 bytes long, including all its overhead, assuming that there are no collisions?(M) headers. If LLC is not in use, is padding needed in the Ethernet frame, and if so, -6依题知一公里的在铜缆中单程传播时间为 1/200000=5×10 s=5 usec，往返传播时 how many bytes?(E) 间为 2t =10 usec，一次完整的传输分为 6 步： 最小的以太网帧是 64 bytes，包含了以太网地址帧头，类型/长度域，以及校验发送者侦听铜缆时间为 10usec，若线路可用 发送数据帧传输时间为 256 bits / 10Mbps = 25.6 usec 数据帧最后一位到达时的传播延迟时间为 5.0usec 接收者侦听铜缆时间为 10 usec，若线路可用 和。 由于帧头域占用 18 bytes，并且分组是 60 bytes，总帧长是 78 bytes，这已经超过了 64-byte 的最小限制。 因此，不必再填充 z 了。 形式为 HLHLHLLHHLLHLHHLHLLH. 23. Ethernet frames must be at least 64 bytes long to ensure that the transmitter is still going in the event of a collision at the far end of the cable. Fast Ethernet has the 接收者发送确认帧用时 3.2 usec same 64-byte minimum frame size but can get the bits out ten times faster. How is it 确认帧最后一位到达时的传播延迟时间为 5.0 usec possible to maintain the same minimum frame size?(E) 总共 58.8sec，在这期间发送了 224 bits 的数据，所以数据传输率为 3.8 Mbps. 将快速以太网的电缆长度至为以太网的 1/10 即可。 20. Two CSMA/CD stations are each trying to transmit long (multiframe) files. 24. Some books quote the maximum size of an Ethernet frame as 1518 bytes After each frame is sent, they contend for the channel, using the binary exponential instead of 1500 bytes. Are they wrong? Explain your answer.（E） backoff algorithm. What is the probability that the contention ends on round k, and 以太网一帧中数据占用是 1500 bytes，但是把目的地地址，源地址，类型/长度域 what is the mean number of rounds per contention period?(M) 以及校验和域也算上，帧总长就为 1518 bytes 把获得通道的尝试从 1 开始编号。第 i 次尝25. The 1000Base-SX specification states that the clock shall run at 1250 MHz, 试分布在 2i-1个时隙中。因此，i 次 even though gigabit Ethernet is only supposed to deliver 1 Gbps. Is this higher speed 尝试碰撞的概率是 2-(i-1)，开头 k-1 次尝试失败，紧接着第 kto provide for an extra margin of safety? If not, what is going on here?(E) 次尝试成功的概率是： 传输数据用 10 位来表示 8 位的真实数据，编码的利用率是 80%，一秒钟可以 即： 传 送 1250 mb 的数据，相当于 125*106码字。 位有效数据，所 以实际的数据传输率是 1000 mb/sec. 每个码字代表的是 8上式可简化为： 所以每个竞争周期的平均竞争次数是∑?kpk 26. How many frames per second can gigabit Ethernet handle? Think carefully and take into account all the relevant cases. Hint: the fact that it is gigabit Ethernet matters.(E) 最小的以太网帧是 64bytes = 512 bits，所以依题 1 Gbps 的带宽可得 1,953,125 21. Consider building a CSMA/CD network running at 1 Gbps over a 1-km cable =2 with no repeaters. The signal speed in the cable is 200,000 km/sec. What is the *106 frames/sec，然而，这只是在充满最小的帧时是这样，如果没有充满帧，填充短 minimum frame size?(E) 帧至 4096 bits，这时每秒处理的帧的最大数量为 244,140 bytes，对于最大的帧长 12,144 bits，每秒处理的帧的最大数量为 82,345 frames/sec. 27. Name two networks that allow frames to be packed back-to-back. Why is this feature worth having?(E) - 16 - 千兆以太网和 802.16 都有这个特性。这不仅对于提高带宽的使用效率很有用，同 时对于帧长的要求限制不多。 能要准确计算需要的带宽。最后，最好选用固定位速率服务。 32. Give two reasons why networks might use an error-correcting code instead of error detection and retransmission.（M） 28. In Fig. 4-27, four stations, A, B, C, and D, are shown. Which of the last two 一个原因是实时服务质量的需要，如果发现了一个错误，并没有时间去做重传， stations do you think is closest to A and why?(E) 必须继续传下去，这里可以使用转发时纠正错误。另一个原因在低质量的线路上（利 用无线带宽），错误率相当高最后所有的帧都必须重传，并且重传时可能也会被破 站 C 最接近 A。因为 C 最先听到 A 发出的 RTS 并且通过插入一个 NAV 信号作 为回应。D 对其没有回应，说明它不在 A 的频率范围内。 29. Suppose that an 11-Mbps 802.11b LAN is transmitting 64-byte frames back-to-back over a radio channel with a bit error rate of 10-7. How many frames per second will be damaged on average?（E） 一帧是 64bytes=512 bits，位出错率为 p=10-7，所有 512 位正确到达的概率为 (1- p)512= 0.9999488，所以帧被破坏的概率约为 5*10-5，每秒钟发送的帧数为 11*106 /512 = 21,484frames/sec，将上两个数乘一下，大约每秒钟有一帧被破坏。 30. An 802.16 network has a channel width of 20 MHz. How many bits/sec can be sent to a subscriber station?（E） 这取决于离子站有多远。如果子站就在附近，那么使用 QAM-64 可得带宽 120 Mbps；中等距离时，使用 QAM-16 可得带宽 80 Mbps；远程距离，QPSK 可得带宽 40 Mbps. （原题给出的是 20mhz 的带宽，要求的是数据率，按照前面的 Nyquist 定理，最 大数据率应该是：2HlogN,但是答案没有乘以 2。） 31. IEEE 802.16 supports four service classes. Which service class is the best choice for sending uncompressed video?（E） 未压缩的视频有一个固定的位速率。每帧都有与前一帧相同的点数量，因此，可 坏。为了避免这些，转发时纠正错误码用于提高到达的帧的正确率的比例。 33. From Fig. 4-35, we see that a Bluetooth device can be in two piconets at the same time. Is there any reason why one device cannot be the master in both of them at the same time?（M） 蓝牙同 802.11 一样使用的是 FHSS。最大的不同在于蓝牙每秒的跳数是 1600 hops， 远快于 802.11 - 17 - 一个设备不可能同时是两个微微网中的主节点。这样会引起两个问题：首先，头 部只有三位地址可用，每个微微网有 7 个从结点，因此，每个从结节没有独立的地 址。其次，起始帧的访问码源于主节点的标记符，这是子节点区分消息来自于哪个 微微网。如果两个重叠的微微网使用相同的访问码，就会区分不出帧是属于哪个微 微网的。实际上，两个微微网会合并到一个大的微微网而不是相互独立的两个。 34. Figure 4-25 shows several physical layer protocols. Which of these is closest to the Bluetooth physical layer protocol? What is the biggest difference between the two?（E） 35. Bluetooth supports two types of links between a master and a slave. What are 表 they and what is each one used for?（E） ACL 频道是异步的，随着不规则到达的帧产生数据。 SCO 频道是同步的，随着周期性到达的帧运行在一个稳定的速率下。 36. Beacon frames in the frequency hopping spread spectrum variant of 802.11 contain the dwell time. Do you think the analogous beacon frames in Bluetooth also contain the dwell time? Discuss your answer.（M） 不是的。在 802.11 中停延时间不是标准化的，所以它必须对到达的新站声明，在 蓝牙里这需要 625usec. 没有必要对这去声明，所有的蓝牙设备中都有这样的硬件芯片，蓝牙被设计得便 宜，并且固定跳率和停延时间的话处理芯片会更便宜。 37. Consider the interconnected LANs showns in Fig. 4-44. Assume that hosts a and b are on LAN 1, c is on LAN 2, and d is on LAN 8. Initially, hash tables in all bridges are empty and the spanning tree shown in Fig 4-44(b) is used. Show how the hash tables of different bridges change after each of the following events happen in sequence, first (a) then (b) and so on.（M） n. (a) a sends to d. o. (b) c sends to a. p. (c) d sends to c. q. (d) d moves to LAN 6. r. (e) d sends to a. 第一帧会被所有的网桥转发。这传完后，每个网桥都会通过它的散列表中的合适 端口建一个到目的地 a 的表项。例如，D 当前的散列表为从 LAN 2 转发到目的地 a； 第二帧将会被网桥 B, D, and A 收到。这些网桥会在它们的散列表中增加一个新的 项，帧的目的地到 c；例如网桥 D 的散列表会又有一个从 LAN 2 转发到目的地 网桥 G, I and J 不用于转发任何帧。主要原因在于有循环可以为一个扩展的 LAN c 的 提高可靠性。如果当前生成树中的网桥有坏的，则动态生成树算法会重新配置一棵 表项；第三帧将会被网桥 H，D，A，以及 B 收到，这些网桥将会在它们的散列表 新的生成树，它可能会包含一个或多个不在原先的生成树中的网桥。 中 39. Imagine that a switch has line cards for four input lines. It frequently happens 增加一个表项，帧的目的地到 d；第四帧将会被网桥 E，C，B，D，以及 A that a frame arriving on one of the lines has to exit on another line on the same card. 收到， 网桥 E 和 C 会在它们的散列表中增加一个表项，帧的目的地到 d，当网桥 D，What choices is the switch designer faced with as a result of this situation?（E） 最简单做选择就是不做特殊处理。每一个到来的帧被输出到底板并被发送到目标 B， 卡上。这时，卡内流量通过底板；另一种选择就是识别出这种情况并且对其专门处 以及 A 更新它们的散列表项时，到达目的地 d 当 d 移到 LAN6 上去后，如果他发数据给 a 的话，路由 j，一定可以知道 d 理，直接发送帧并且不通过底板。 在 LAN6 上的，答案中没有给出 j 的这一表项。 40. A switch designed for use with fast Ethernet has a backplane that can move 10 Gbps. How many frames/sec can it handle in the worst case?（E） 最坏的情况就是无穷的 64-byte (512-bit)帧流。如果底板能处理 10bps，可处理的 9 38. One consequence of using a spanning tree to forward frames in an extended 9 LAN is that some bridges may not participate at all in forwarding frames. Identify 帧的数量为 10/512 = 1,953,125 frames/sec. 41. Consider the network of Fig. 4-49(a). If machine J were to suddenly become three such bridges in Fig. 4-44. Is there any reason for keeping these bridges, even white, would any changes be needed to the labeling? If so, what?（E） though they are not used for forwarding?（E） - 18 - 端口 B1 到 LAN 3 需要被重新标记为 GW. 可以工作。进入核心域的帧都会是合法帧，因此帧会在第一个核心交换机里被加 上标记，可以用 MAC 或 IP 地址。 类似的，在出口处，交换机去掉这些标记后再 输出帧。 42. Briefly describe the difference between store-and-forward and cut-through Chapter 5 The Network Layer Problems switches.（E） 1. Give two example computer applications for which connection-oriented service 一个存储转发交换机在它的表项里存储进来的每一帧，然后检查并且转发它；直 is appropriate. Now give two examples for which connectionless service is best.(E) 通型交换机帧一进来就完全转发掉。只要目的地地址是可用的，转发就可以开始。 43. Store-and-forward switches have an advantage over cut-through switches with 文件传送、远程登录和视频点播需要面向连接的服务。另一方面，信用卡验证和 respect to damaged frames. Explain what it is.（E） 存储转发型交换机存储整个帧然后转发它们。一个帧到来后，可以验证校验和， 如果帧被破坏了，马上丢掉坏帧。用直通型交换机，坏帧不能被交换机丢掉，因为 其他的销售点终端、电子资金转移，以及许多形式的远程数据库访问生来具有无连 接的性质，在一个方向上传送查询，在另一个方向上返回应答。 2. Are there any circumstances when connection-oriented service will (or at least should) deliver packets out of order? Explain.(M) 那时检测错误的同时帧就已经转掉了。 有。中断信号不遵从顺序的投递，它会跳过在它前面的数据。例如是当一个终端 44. To make VLANs work, configuration tables are needed in the switches and 用户键入退出（或 kill）健时，由退出信号产生的分组被立即发送，并且跳过了当 bridges. What if the VLANs of Fig. 4-49(a) use hubs rather than multidrop cables? 前队列中等待程序处理的排在前面任何数据（即已经键入但没被程序读取的数据）。 Do the hubs need configuration tables, too? Why or why not?（E） 3. Datagram subnets route each packet as a separate unit, independent of all 不做路由，进入到集线器的每一帧分发到所有其它的线路上。 others. Virtual-circuit subnets do not have to do this, since each data packet follows 45. In Fig. 4-50 the switch in the legacy end domain on the right is a VLAN-aware a predetermined route. Does this observation mean that virtual-circuit subnets do not need the capability to route isolated packets from an arbitrary source to an switch. Would it be possible to use a legacy switch there? If so, how would that work? arbitrary destination? Explain your answer.（E） If not, why not?（E） 不对。为了使分组能从任意源到达任意目的地，连接建立时要选择路由，虚电路 网络也需要这一能力。 不需要，集线器只是将所有的输入线收集在一起，并没有进行配置。在集线器中 4. Give three examples of protocol parameters that might be negotiated when a connection is set up.（E） 在连接建立的时候可能要协商窗口的大小、最大分组尺寸和超时值。 - 19 - 5. Consider the following design problem concerning implementation of virtual-circuit service. If virtual circuits are used internal to the subnet, each data packet must have a 3-byte header and each router must tie up 8 bytes of storage for circuit identification. If datagrams are used internally, 15-byte headers are needed but no router table space is required. Transmission capacity costs 1 cent per 106 bytes, per hop. Very fast router memory can be purchased for 1 cent per byte and is depreciated over two years, assuming a 40-hour business week. The statistically average session runs for 1000 sec, in which time 200 packets are transmitted. The mean packet requires four hops. Which implementation is cheaper, and by how much?（H） 4 跳意味着引入了 5 个路由器。实现虚电路需要在 1000 秒内固定分配 5*8=40 字 节的存储器。实现数据报需要比实现虚电路多传送的头信息的容量等于(15-3 ) ×4×200＝9600 字节-跳段。 现在的问题就变成了 40000 字节-跳段的电路容量的 7 所有的路由选择如下： ABCD, ABCF, ABEF, ABEG, AGHD, AGHF, AGEB, and AGEF，所以总跳数为 24 8. Give a simple heuristic for finding two paths through a network from a given source to a given destination that can survive the loss of any communication line (assuming two such paths exist). The routers are considered reliable enough, so it is not necessary to worry about the possibility of router crashes.（E） 使用最短通路搜索算法选择一条路径，然后，删除刚找到的路径中的使用的所有 的弧（对应各条链路）。接着，再运行一次最短通路搜索算法。这个第 2 条路径在 第 1 条路径中有线路失效的情况下，可以作为替代路径启用；反之亦然。 字节-秒的存储器对比 9600开销。如果存储器的使用期为两年，即 3600×8×5×52×2=1.5×10秒，一个字节-秒的 代价为 1/( 1.5×107)= 6.7×10-8分，那么 40000 字节-秒的代价为 2.7 毫分。另一方面， -61 个字节-跳段代价是 10分，9600 个字节-跳段的代价为 10-6×\慇2X9600=9.6×10-3分，即 9.6 毫分，即在这 1000 秒内的时间内便宜大约 6.9 毫分。 9. Consider the subnet of Fig. 5-13(a). Distance vector routing is used, and the following vectors have just come in to router C: from B: (5, 0, 8, 12, 6, 2); from D: 6. Assuming that all routers and hosts are working properly and that all software (16, 12, 6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The measured delays to B, D, and E, in both is free of all errors, is there any chance, however small, that a packet will be are 6, 3, and 5, respectively. What is C's new routing table? Give both the outgoing line to use and the expected delay.（M） delivered to the wrong destination?（E） 有可能。大的突发噪声可能破坏分组。使用 k 位的检验和，差错仍然有 2-k 的概 率被漏检。如果分组的目的地段或虚电路号码被改变，分组将会被投递到错误的目 的地，并可能被接收为正确的分组。换句话说，偶然的突发噪声可能把送往一个目 的地的完全合法的分组改变成送往另一个目的地的也是完全合法的分组。 7. Consider the network of Fig. 5-7, but ignore the weights on the lines. Suppose that it uses flooding as the routing algorithm. If a packet sent by A to D has a maximum hop count of 3, list all the routes it will take. Also tell how many hops worth of bandwidth it consumes.（E） A， B，C，D， E，F 通过 B 给出（11，6，14，18，12，8） - 20 - 通过 D 给出（19，15，9，3，12，13） 通过 E 给出（12，11，8，14，5，9） 取到达每一目的地的最小值（C 除外）得到：（11，6，0，3，5，8） 输出线路是：（B，B，-，D，E，B） 10. If delays are recorded as 8-bit numbers in a 50-router network, and delay vectors are exchanged twice a second, how much bandwidth per (full-duplex) line is chewed up by the distributed routing algorithm? Assume that each router has three lines to other routers.（E） 路由表的长度等于 8*50=400bit。该表每秒钟在每条线路上发送 2 此 400*2=800b/s，即在每条线路的每个方向上消耗的带宽都是 800 bps。 11. In Fig. 5-14 the Boolean OR of the two sets of ACF bits are 111 in every row. Is this just an accident here, or does it hold for all subnets under all circumstances? （M） 它区的路由，14 个表项用于远程的群，这时路由表尺寸最小为 20+15+14。 次，因这个结论总是成立的。如果一个分组从某条线路上到达，必须确认包的到达。 如 果线路上没有分组到达，它就是在发送确认。情况 00 ( 没有分组到达并且不发送确 认)和 11 (到达和返回)逻辑上错误，因此不存在。 12. For hierarchical routing with 4800 routers, what region and cluster sizes should be chosen to minimize the size of the routing table for a three-layer hierarchy? A good starting place is the hypothesis that a solution with k clusters of k regions of k routers is close to optimal, which means that k is about the cube root of 4800 (around 16). Use trial and error to check out combinations where all three parameters are in the general vicinity of 16. 依题可选择 15 个群、16 个区，每个区 20 个路由器时，即使得 4800=15*16*20， 这时每个路由器需要 20 个表项记录本地路由器，15 个表项记录用于到同一群内其 13. In the text it was stated that when a mobile host is not at home, packets sent to its home LAN are intercepted by its home agent on that LAN. For an IP network on an 802.3 LAN, how does the home agent accomplish this interception?（E） Conceivably it might go into promiscuous mode, reading all frames dropped onto the LAN, but this is very inefficient. Instead, what is normally done is that the home agent tricks the router into thinking it is the mobile host by responding to ARP requests. When the router gets an IP packet destined for the mobile host, it broadcasts an ARP query （1）反向通路转发算法，算法进行到5个跳段后结束，AC，FDIJ，asking for the 802.3 MAC-level address of the machine with that IP address. When the KHG(D)(J)E(I)N， mobile host is not around, the home agent responds to the ARP, so the router associates L(F)(E)(D)O(H)(J)M，(K)(G)(M)(H)(N)(L)，总共产生28个分组 the mobile user’s IP address with the home agent’s 802.3 MAC-level address. （2）使用汇集树算法，需要 4 个跳段，AC，FDIJ，KGHEN，LMO，总共产生 14. Looking at the subnet of Fig. 5-6, how many packets are generated by a 14 个分组。 broadcast from B, using a. (a) reverse path forwarding? b. (b) the sink tree?（M） 15. Consider the network of Fig. 5-16(a). Imagine that one new line is added, between F and G, but the sink tree of Fig. 5-16(b) remains unchanged. What changes occur to Fig. 5-16(c)?（M） - 21 - 在 d 中，E，H，I 接收到了广播信息之后阴影节点是新的接收节点；箭头显示了 可能的逆向路由路径。H 收到分组 A 后，它广播 A；然而，I 知道了如何到达 I，所 以 I 不广播收到的分组。 18. Suppose that node B in Fig. 5-20 has just rebooted and has no routing information in its tables. It suddenly needs a route to H. It sends out broadcasts with TTL set to 1, 2, 3, and so on. How many rounds does it take to find a route?（E） 从结点 B 到 H 需要 3 跳，因此要花 3 圈来找到路由线路。 19. In the simplest version of the Chord algorithm for peer-to-peer lookup, searches do not use the finger table. Instead, they are linear around the circle, in either direction. Can a node accurately predict which direction it should search? Discuss your answer.（E） 可以大致估计，但不是很精确。假设有 1024 个结点标记，如果结点 300 Node F currently has two descendants, A and D. It now acquires a third one, G, not circled because the packet that follows IFG is not on the sink tree. Node G acquires a second descendant, in addition to D, labeled F. This, too, is not circled as it does not come in on the sink tree. 当前的 c 中的结点 F 有两个孩子 A 和 D，依题意不改变汇集树 b 的话，再 正在查 为 F 加 一个孩子 G，不会有环是因为 IFG 之后的分组不在汇集树 b 中。结点 G 下再加找结点 800，可能最好去顺时针方向查找，但是也许可能顺时针方向有 20 个真实 的 一个 孩子 D，标记 F。同样，不会有环是因为在汇集树 b 中之后再没有分组进来。 结点在结点 300 和结点 800 之间，而逆时针方向只有 16 个真实结点在它们之16. Compute a multicast spanning tree for router C in the following subnet for a 间。 group with members at routers A, B, C, D, E, F, I, and K.（E） 多种生成树是可能的，例如其中一颗为： 散列函数 SHA-1 的目的在于生成一个非常流畅的分布使得结点密度在环上基本 上是一样的。但是会总有统计学上的波动，因此直接向前的选择可能是错误的。 20. Consider the Chord circle of Fig. 5-24. Suppose that node 10 suddenly goes on line. Does this affect node 1's finger table, and if so, how?（E） 17. In Fig. 5-20, do nodes H or I ever broadcast on the lookup shown starting at A? （E） 在表项 3 中的结点从 12 变 10。 21. As a possible congestion control mechanism in a subnet using virtual circuits internally, a router could refrain from acknowledging a received packet until (1) it knows its last transmission along the virtual circuit was received successfully and (2) it has a free buffer. For simplicity, assume that the routers use a stop-and-wait protocol and that each virtual circuit has one buffer dedicated to it for each direction of traffic. If it takes T sec to transmit a packet (data or acknowledgement) - 22 - and there are n routers on the path, what is the rate at which packets are delivered 24. Give an argument why the leaky bucket algorithm should allow just one to the destination host? Assume that transmission errors are rare and that the packet per tick, independent of how large the packet is.（M） host-router connection is infinitely fast.（M） 通常计算机能够以很高的速率产生数据，网络也可以用同样的速率运行。然而， 协议很不好。对时间以 T 秒为单位分时隙。在时隙 1 中，源路由器发送第一路由器却只能在短时间内以同样高的速率处理数据。对于排在队列中的一个分组， 不管它有多大，路由器必须做大约相同分量的工作。显然，处理 10 个 100个分 字节长 组。在时隙 2 的开始时第 2 个路由器收到了分组，但是还没发送确认。在时隙 3 的分组所作的工作比处理 1 个 1000 字节长的分组要做的工作多得多。 的 开始时第 3 个路由器收到了分组，但也不发送确认。这样，此后所有的路由器都不 25. The byte-counting variant of the leaky bucket algorithm is used in a particular 发送确认。仅当目的地主机从目的地路由器取得分组时才会发送第 1 个确认。现system. The rule is that one 1024-byte packet, or two 512-byte packets, etc., may be 在 sent on each tick. Give a serious restriction of this system that was not mentioned in 确认开始往回传播。在源路由器可以发送第 2 个分组之前，需要两次通过该the text.（E） 子网， 不可以发送任何大于 1024 字节的分组。 所费时间为 2(n-1)T 秒/分组，很显然，这种协议的效率是很低的。 26. An ATM network uses a token bucket scheme for traffic shaping. A new token 22. A datagram subnet allows routers to drop packets whenever they need to. The is put into the bucket every 5 μsec. Each token is good for one cell, which contains probability of a router discarding a packet is p. Consider the case of a source host 48 bytes of data. What is the maximum sustainable data rate?(E) connected to the source router, which is connected to the destination router, and 每 5 产生一个令牌，1 秒中可以发送 200,000 个信元。每个信元含有 48then to the destination host. If either of the routers discards a packet, the source 个数据 host eventually times out and tries again. If both host-router and router-router lines 5字节，即 8×48=384bit。最大的可持续的净数据速率为 384×2×10=76.8Mb/s are counted as hops, what is the mean number of 27. A computer on a 6-Mbps network is regulated by a token bucket. The token c. (a) hops a packet makes per transmission? bucket is filled at a rate of 1 Mbps. It is initially filled to capacity with 8 megabits. d. (b) transmissions a packet makes? How long can the computer transmit at the full 6 Mbps?(E) e. (c) hops required per received packet?(M) 由公式 S＝C /(M-P )，这里的 S 表示以秒计量的突发时间长度，M 表示以每秒字 （1）由源主机发送的每个分组可能行走 1 段。走 1 个 跳段的概率为 p ，走 2 个跳段的概率为(1- p)2。那 么，一个分组平均通路长度的期望值为：L=1*p+2*(1- p)p +3*(1- p)2 = p2-3 p+3 2个跳段、2 个跳段或 3 个跳节计量的最大输出速率，C 表示以字节计的桶的容量，P 表示以每秒字节计量的令 个跳段的概率为(1- p)p，走 3牌到达速率。则：S=((8*106)/8) / ((6*106)/8 - (1*106)/8) = 1.6 s 因此，计算机可以用完全速率 6Mb/s 发送 1.6 s 的时间。 28. Imagine a flow specification that has a maximum packet size of 1000 bytes, a 即每次发送一个分组的平均跳段数是 p-3 p+3。 token bucket rate of 10 million bytes/sec, a token bucket size of 1 million bytes, and （2）一次发送成功（走完整个通路）的概率为(1- p)2，令 a =(1- p)2，两次发射成 功的概率等于(1- a) a，三次发射成功的概率等于(1- a)2 a ，…，因此一个分组平均 发送次数为： ，即一个分组平均要发送 1/(1- p )2次。 a maximum transmission rate of 50 million bytes/sec. How long can a burst at 22 （3）每一个接收到的分组行走的平均跳段数等于：H=L*T=( p-3 p+3)/ (1- p) 首先，警告位方法通过设置一个特殊的位来显示地发送一个拥塞标记给源。而 23. Describe two major differences between the warning bit method and the RED 方法是通过简单地丢掉源分组中的一个来隐式标记。 RED method.（E） 其次，警告位方法只有在没有缓冲区空间时才丢掉一个分组，而 RED 方法是在所 有的缓冲区空间被消耗完才丢弃分组。 maximum speed last?（E） 令最大突发时间长度为 Δ t 秒。在极端情况下，漏桶在突发期间的开 始是充满的 （1MB），这期间数据流入桶内 10Δ t MB，流出包含 50Δ t MB，由等式 1+10Δ t=50Δ t，得到 Δ t=1/40s，即 25ms。因此，以最大速率突发传送可维持 25ms 的时- 23 - 间。 29. The network of Fig. 5-37 uses RSVP with multicast trees for hosts 1 and 2 as shown. Suppose that host 3 requests a channel of bandwidth 2 MB/sec for a flow from host 1 and another channel of bandwidth 1 MB/sec for a flow from host 2. At the same time, host 4 requests a channel of bandwidth 2 MB/sec for a flow from host 1 and host 5 requests a channel of bandwidth 1 MB/sec for a flow from host 2. How 34. Suppose that host A is connected to a router R 1, R 1 is connected to another much total bandwidth will be reserved for these requests at routers A, B, C, E, H, J, router, R 2, and R 2 is connected to host B. Suppose that a TCP message that K, and L?(E) contains 900 bytes of data and 20 bytes of TCP header is passed to the IP code at host A for delivery to B. Show the Total length, Identification, DF, MF, and Fragment offset fields of the IP header in each packet transmitted over the three links. Assume that link A-R1 can support a maximum frame size of 1024 bytes including a 14-byte frame header, link R1-R2 can support a maximum frame size of 512 bytes, including an 8-byte frame header, and link R2-B can support a maximum frame size of 512 bytes including a 12-byte frame header.（M） 在 I1 最初的 IP 数据报会被分割成两个 IP 数据报，以后不会再分割了。 链路 A-R1：Length = 940; ID = x; DF = 0; MF = 0; Offset = 0 链路 R1-R2： (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60 链路 R2-B: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60 35. A router is blasting out IP packets whose total length (data plus header) is 可以。只需把分组封装在属于所经过的子网的数据报的载荷段中，并进行发送。 带宽流量如下：A?2，B?0，C?1，E?3，H?3，J?3，K?2 和 L?1 30. The CPU in a router can process 2 million packets/sec. The load offered to it is 1.5 million packets/sec. If a route from source to destination contains 10 routers, how much time is spent being queued and serviced by the CPUs?(E) 依题知 =2 million， =1.5 million，可知 =0.75，从排队理论可知，每个分 组经历的延迟是空系统中的四倍。空系统中的时延是 500 nsec，这里为 2 sec. 经过 10 个路由器，排队总时间为 20 sec. 31. Consider the user of differentiated services with expedited forwarding. Is there a guarantee that expedited packets experience a shorter delay than regular packets? Why or why not?（E） 无法保证，如果快速的分组太多，它们分配的带宽可能会比常规的分组的性能更 差。 32. Is fragmentation needed in concatenated virtual-circuit internets or only in datagram systems?（E） 都需要分割功能。即使是在一个串接的虚电路网络中，沿通路的某些网络可能接 受 1024 字节分组，而另一些网络可能仅接受 48 字节分组，分割功能仍然是需要的。 33. Tunneling through a concatenated virtual-circuit subnet is straightforward: the multiprotocol router at one end just sets up a virtual circuit to the other end and passes packets through it. Can tunneling also be used in datagram subnets? If so, how?（E） 1024 bytes. Assuming that packets live for 10 sec, what is the maximum line speed the router can operate at without danger of cycling through the IP datagram ID number space?（E） addresses, respectively, and in that order. For each of these, give the first IP address assigned, the last IP address assigned, and the mask in the w.x.y.z/s notation.（M） A：4000?212；B：2000?211；C：4000?212；D：8000?213； 如果线路的比特率为 b，则每秒钟分组的数量为 b/8192，那么发送一个分组所需 始地址，尾地址，和子网掩码如下： 的时间为 8192/b；输出 65,536 个分组要花费 229 /b sec，依题分组的生存期为 A：198.16.0.0 –198.16.15.255 子网写作 198.16.0.0/20 10s， B：198.16.16.0 – 198.16.23.255 子网写作 198.16.16.0/21 将 229 /b=10，可得 b 为 53,687,091 bps C：198.16.32.0 – 198.16.47.255 子网写作 198.16.32.0/20 40. A large number of consecutive IP address are available starting at 198.16.0.0. Suppose that four organizations, A, B, C, and D, request 4000, 2000, 4000, and 8000 - 24 - D：198.16.64.0 – 198..16.95.255 子网写作 198.16.64.0/19 46. ARP and RARP both map addresses from one space to another. In this respect, they are similar. However, their implementations are fundamentally different. In what major way do they differ?（E） 在 RARP 的实现中有一个 RARP 服务器负责回答查询请求。 在 ARP 的实现中没有这样的服务器，主机自己回答 ARP 查询。 52. The Protocol field used in the IPv4 header is not present in the fixed IPv6 header. Why not?（E） 设置协议段的目的是要告诉目的地主机把 IP 分组交给那一个协议处理程序。中 途的路由器并不需要这一信息，因此不必把它放在主头中。实际上，这个信息存在 于头中，但被伪装了。最后一个（扩展）头的下一个字段就用于这一目的。 Chapter 6 The Transport Layer Problems 1. In our example transport primitives of Fig. 6-2, LISTEN is a blocking call. Is this strictly necessary? If not, explain how a nonblocking primitive could be used. What advantage would this have over the scheme described in the text?(E) 从―被动连接建立在进行中‖到―已建立‖的虚线不再依确认的传输情况而定。该变 迁可立即发生。实质上，―被动连接建立在进行中‖状态已经消失，因为它们什么时 候都不可见。 3. In both parts of Fig. 6-6, there is a comment that the value of SERVER_PORT must be the same in both client and server. Why is this so important?（E） 如果客户机发送一个分组给 SERVER_PORT 并且服务器当时并没有侦听这一端 口，那么这个分组将不会被投递给服务器。 4. Suppose that the clock-driven scheme for generating initial sequence numbers is used with a 15-bit wide clock counter. The clock ticks once every 100 msec, and the maximum packet lifetime is 60 sec. How often need resynchronization take place a. (a) in the worst case? b. (b) when the data consumes 240 sequence numbers/min?（M） 时钟驱动方案的基本思想是同一时间不会有两个活动的 TPDUs 使用相同的序列 号。序列号空间应该足够大，使得当编号循环一周时，具有相同号码的旧的 TPDU 已 经不复存在。 （a） 时钟大循环周期是 215，即 32768 100ms，即 0.1 秒，所以 滴答，每滴答 不是。事实上，LISTEN 调用可以表明建立新连接的意愿，但不封锁。当有了建 立连接的尝试时，调用程序可以被提供一个信号。然后，它执行，比如说，OK 或 REJECT 来接受或拒绝连接。然而，在原先的封锁性方案中，就缺乏这种灵活性。 2. In the model underlying Fig. 6-4, it is assumed that packets may be lost by the network layer and thus must be individually acknowledged. Suppose that the network layer is 100 percent reliable and never loses packets. What changes, if any, are needed to Fig. 6-4?(E) 大循环周期是 3276.8s 送方在 。假定数据产生速率非常低（接近零），那么发 - 25 - 3276.8-60=3271.8 秒时进入禁止区，需要进行一次重新同步。 最坏的情况是延迟的―连接请求‖和对―连接被接收‖的确认应答都在网络上存活。 （b） 每分钟使用 240 个序列号，即每秒使用 4 个号可以设想，当第 2 个重复分组到达时，如果在网上还存在一个老的对序列号为 y 的 秒为单位），那么实际使用中的序列号是 4t 个。当接近大循环的末尾时以及在下一 分组的确认应答，显然会破坏三次握手协议的正常工作，故障性的产生一条没有人 大循环的开始阶段，4t 有一定的大小，位于禁止区的上方，现在由于每秒钟 10 真正需要的连接，从而导致灾难性的后果。 个 6. Imagine that a two-way handshake rather than a three-way handshake were 滴答，禁止区的左边是 10(t-3216.8)。令4t =10(t-3216.8)，得t=5316.3 秒。即当 t=5316.3 码，如果时间以 t 表示（以 时，开始进入禁止区，需要进行一次重新同步。 5. Why does the maximum packet lifetime, T, have to be large enough to ensure that not only the packet but also its acknowledgements have vanished?（M） 首先看三次握手过程是如何解决延迟的重复到达的分组所引起的问题的。 used to set up connections. In other words, the third message was not required. Are deadlocks now possible? Give an example or show that none exist.（M） 我们知道，3 次握手完成两个重要功能，既要双方做好发送数据的准备工作（双 方都知道彼此已准备好），也要允许双方就初始序列号进行协商，这个序列号在握 手过程中被发送与确认。 现在把三次握手改成仅需要两次握手，死锁是可能发生的。例如，考虑计算机 A 和 B 之间的通信。假定 B 给 A 发送一个连接请求分组，A 收到了这个分组，并 正常情况下，当主机 1 发出连接请求时，主机 1 选择一个序号 x，并向主机 2 发 送一个包含该序号的请求 TPDU；接着，主机 2 回应一个接受连接的 TPDU，确认 x，并声明自己所选用的初始序列号 y；最后，主机 1 在其发送的第一个数据 TPDU 中确认主机 2 所选择的初始序列号。 当出现延迟的重复的控制 TPDU 个已经释放的连接 的延迟重复的连接请求（ CONNECTION REQUEST），该 TPDU 在主机 1 毫不知 时，一个 TPDU 是来自于一情的情况下到达主机 2。 主机 2 通过向主机 1 发送一个接受连接的 TPDU（CONNECTION ACCEPTED） 来响应该 TPDU，而该接受连接的 TPDU 的真正目的是证实主机 1 确实试图建立一 个新的连接。在这一点上，关键在于主机 2 建议使用 y 作为从主机 2 到主机 1 交 通的初始序列号，从而说明已经不存在包含序列号为 y 的 TPDU，也不存在对 y 的 应答分组。当第二个延迟的 TPDU 到达主机 2 时，z 被确认而不是 y 被确认的事 实告诉主机 2 这是一个旧的重复的 TPDU，因此废止该连接过程。在这里。三次握 手协议是成功的。