2022年2022年计算机网络习题答案 5.pdf

《2022年2022年计算机网络习题答案 5.pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机网络习题答案 5.pdf（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、ANDREW S. TANENBAUM COMPUTER NETWORKS FOURTH EDITION PROBLEM SOLUTIONS 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 32 页 - - - - - - - - - 第 1 章 概述1. 答：狗能携带 21 千兆字节或者 168千兆位的数据。 18 公里/小时的速度等于 0.005 公里/秒，走过 x 公里的时间为 x / 0.005 = 200 x秒， 产生的数据传输速度为168/200 x Gbps

2、或者840 /x Mbps。因此，与通信线路相比较，若x 32/x，或 f max =x/32。36. 答： 10-9的漂移意味着 109 秒中的 1 秒，或 1 秒中的 10-9秒。对于 OC-1 速率，即51.840Mbps，取近似值 50Mbps，大约一位持续 20ns。这就说明每隔 20 秒，时钟就要偏离 1位。这就说明，时钟必须每隔10 秒或更频繁地进行同步，才能保持不会偏离太大。37. 答： 基本的 SONET 帧是美 125 产生 810 字节。由于 SONET 是同步的，因此不论是否有数据，帧都被发送出去。每秒8000 帧与数字电话系统中使用的PCM 信道的采样频率完全一样。8

3、10字节的 SONET 帧通常用 90列乘以 9 行的矩形来描述，每秒传送51.84Mbps，即8 810 800051840000bps 。这就是基本的 SONET 信道，它被称作同步传输信号STS-1，所有的 SONET 干线都是由多条 STS-1构成。每一帧的前 3 列被留作系统管理信息使用， 前 3 行包含段开销， 后 6 行包含线路开销。剩下的 87 列包含 87 9 8 800050112000bps 。被称作同步载荷信封的数据可以在任何位置开始。线路开销的第一行包含指向第一字节的指针。同步载荷信封（SPE ）的第一列是名师资料总结 - - -精品资料欢迎下载 - - - - -

4、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 32 页 - - - - - - - - - 通路开销。通路开销不是严格的SONET 结构，它在嵌入在载荷信封中。通路开销端到端的流过网络，因此把它与端到端的运载用户信息的SPE 相关联是有意义的。 然而，它确实从可提供给端点用户的 50.112Mbps 中又减去 1 9 8 8000576000bps ，即 0.576Mbps，使之变成49.536Mbps 。OC-3 相当于 3个 OC-1复用在一起，因此其用户数据传输速率是3148.608 Mbps。38. VT1.5 can

5、accommodate 8000 frames/sec 3 columns9 rows8 bits =1.728 Mbps. It can be used to accommodate DS-1. VT2 can accommodate 8000 frames/sec 4 columns 9 rows 8 bits = 2.304 Mbps. It can be used to accommodate European CEPT-1 service. VT6 can accommodate 8000 frames/sec12 columns9 rows8 bits = 6.912 Mbps.

6、It can be used toaccommodate DS-2 service. 39. Message switching sends data units that can be arbitrarily long. Packet switching has a maximum packet size. Any message longer than that is split up into multiple packets. 40. 答： 当一条线路（例如 OC-3）没有被多路复用，而仅从一个源输入数据时，字母c（表示 conactenation ， 即串联）被加到名字标识的后面，

7、因此，OC-3 表示由 3 条单独的 OC-1 线路复用成 155.52Mbps，而 OC-3c 表示来自单个源的155.52Mbps 的数据流。 OC-3c 流中所包含的 3 个 OC-1 流按列交织编排， 首先是流 1 的第 1 列，流 2 的第 1 列，流 3 的第 1 列，随后是流 1 的第 2 列，流 2 的第 2 列，?以此类推，最后形成270 列宽 9 行高的帧。OC-3c 流中的用户实际数据传输速率比OC-3 流的速率略高（ 149.760Mbps 和148.608Mbps），因为通路开销仅在SPE 中出现一次， 而不是当使用 3 条单独 OC-1 流时出现的 3 次。换句话说

8、， OC-3c 中 270 列中的 260 列可用于用户数据，而在OC-3 中仅能使用 258列。更高层次的串联帧（如OC-12c）也存在。OC-12c 帧有 12*90=1080 列和 9 行。其中段开销和线路开销占12*3=36 列，这样同步载荷信封就有 1080-36=1044 列。SPE 中仅 1 列用于通路开销，结果就是1043 列用于用户数据。由于每列 9 个字节，因此一个 OC-12c 帧中用户数据比特数是8 91043 75096。每秒8000 帧，得到用户数据速率75096 8000 =600768000bps ，即 600.768Mbps。所以，在一条 OC-12c 连接中

9、可提供的用户带宽是600.768Mbps。41. 答： The three networks have the following properties: 星型：最好为 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。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11

10、 页，共 32 页 - - - - - - - - - 42. 对于电路交换，t= s时电路建立起来； ts+ x /d 时报文的最后一位发送完毕；t=s+x/b+kd 时报文到达目的地。而对于分组交换，最后一位在t=x/b时发送完毕。为到达最终目的地， 最后一个分组必须被中间的路由器重发k1 次，每次重发花时间 p/ b，所以总的延迟为为了使分组交换比电路交换快，必须：所以：43. 答： 所需要的分组总数是x /p ，因此总的数据加上头信息交通量为(p+h)x/p 位。源端发送这些位需要时间为(p+h)x/pb 中间的路由器重传最后一个分组所花的总时间为(k-1)(p+h)/ b 因此我们得

11、到的总的延迟为对该函数求 p 的导数，得到令得到因为 p0，所以故时能使总的延迟最小。44. Each cell has six neighbors. If the central cell uses frequency group A, its six neighbors can use B, C, B, C, B, and C respectively. In other words, only 3 unique cells are needed. Consequently, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

12、名师精心整理 - - - - - - - 第 12 页，共 32 页 - - - - - - - - - each cell can have 280 frequencies. 45. First, initial deployment simply placed cells in regions where there was high density of human or vehicle population. Once they were there, the operator often did not want to go to the trouble of moving them

13、. Second, antennas are typically placed on tall buildings or mountains. Depending on the exact location of such structures, the area covered by a cell may be irregular due to obstacles near the transmitter. Third, some communities or property owners do not allow building a tower at a location where

14、the center of a cell falls. In such cases, directional antennas are placed at a location not at the cell center. 46. If we assume that each microcell is a circle 100 m in diameter, then each cell has an area of 2500108m2 and divide it by the area of 1 microcell, we get 15,279 microcells. Of course,

15、it is impossible to tile the plane with circles (and San Francisco is decidedly three-dimensional), but with 20,000 microcells we could probably do the job. 47. Frequencies cannot be reused in adjacent cells, so when a user moves from one cell to another, a new frequency must be allocated for the ca

16、ll. If a user moves into a cell, all of whose frequencies are currently in use, the user s call must be terminated. 48. 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

17、. They could have put two users in each channel, increasing the payload before error correction from 260 50=13 kbps to 26075 =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. D-AMPS uses 832 channels (in each direction

18、) 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

19、in each direction). D-AMPS uses 30 KHz892 = 26.76 MHz. GSM uses 200 KHz 124 =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. The result is obtained by negating each of A, B, and C and then adding th

20、e three chip sequences. Alternatively the three can be added and then negated. 13 11 +1).51. By definition名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 32 页 - - - - - - - - - If T sends a 0 bit instead of 1 bit, its chip sequence is negated, with the i-th ele

21、ment becoming Ti . Thus, 52. 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 m

22、atch. 53. Just compute the four normalized inner products: (1 +1 3 +1 1 3 +1 +1) d (11 1 +1 +1 1 +1 +1)/8 = 1(1 +1 3 +1 1 3 +1 +1) d (11 +1 1 +1 +1 +1 1)/8 = 1(1 +1 3 +1 1 3 +1 +1) d (1 +1 1 +1 +1 +1 11)/8 = 0(1 +1 3 +1 1 3 +1 +1) d (1 +1 1 1 1 1 +1 1)/8 = 1The result is that A and D sent 1 bits, B

23、sent a 0 bit, and C was silent. 54. 答： 可以，每部电话都能够有自己到达端局的线路，但每路光纤都可以连接许多部电话。忽略语音压缩，一部数字PCM 电话需要 64kbps 的带宽。如果以 64kbps 为单元来分割 10Gbps ，我们得到每路光缆串行156250 家。现今的有线电视系统每根电缆串行数百家。55. 答：它既像 TDM ， 也像 FDM 。 100 个频道中的每一个都分配有自己的频带（FDM） ，在每个频道上又都有两个逻辑流通过TDM 交织播放（节目和广告交替使用频道）。This example is the same as the AM rad

24、io example given in the text, but neither is a fantastic example of TDM because the alternation is irregular. 56. A 2-Mbps downstream bandwidth guarantee to each house implies at most 50 houses per coaxial cable. Thus, the cable company will need to split up the existing cable into 100 coaxial cable

25、s and connect each of them directly to a fiber node. 57. The upstream bandwidth is 37 MHz. Using QPSK with 2 bits/Hz, we get 74 Mbps upstream. Downstream we have 200 MHz. Using QAM-64, this is 1200 Mbps. Using QAM-256, this is 1600 Mbps. 58. Even if the downstream channel works at 27 Mbps, the user

26、interface is nearly always 10-Mbps Ethernet. There is no way to get bits to the computer any faster than 10-Mbps under these circumstances. If the connection between the PC and cable modem is fast Ethernet, then the full 27 Mbps may be available. Usually, cable operators specify 10 Mbps Ethernet bec

27、ause they do not want one user sucking up the entire bandwidth. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 32 页 - - - - - - - - - 第 3 章 数据链路层1. 答：由于每一帧有 0.8 的概率正确到达，整个信息正确到达的概率为p=0.810=0.107。为使信息完整的到达接收方，发送一次成功的概率是p ，二次成功的概率是 (1-p)p，三次成功的概率为 (1-p)2 p，i 次成功

28、的概率为 (1-p)i-1 p，因此平均的发送次数等于：2. The solution is (a) 00000100 01000111 11100011 11100000 01111110 (b) 01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110 (c) 01111110 01000111 110100011 111000000 011111010 01111110 3. After stuffing, we get A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D

29、. 4. If you could always count on an endless stream of frames, one flag byte might be enough. But what if a frame ends (with a flag byte) and there are no new frames for 15 minutes. How will the receiver know that the next byte is actually the start of a new frame and not just noise on the line? The

30、 protocol is much simpler with starting and ending flag bytes. 5. The output is 011110111110011111010. 6. 答：可能。假定原来的正文包含位序列01111110 作为数据。位填充之后，这个序列将变成 01111010 。如果由于传输错误第二个0 丢失了，收到的位串又变成01111110 ，被接收方看成是帧尾。 然后接收方在该串的前面寻找检验和，并对它进行验证。 如果检验和是 16 位，那么被错误的看成是检验和的16 位的内容碰巧经验证后仍然正确的概率是1/216。如果这种概率的条件成立了，就会

31、导致不正确的帧被接收。显然，检验和段越长，传输错误不被发现的概率会越低，但该概率永远不等于零。7. 答：如果传播延迟很长， 例如在探测火星或金星的情况下， 需要采用前向纠错的方法。还有在某些军事环境中，接收方不想暴露自己的地理位置，所以不宜发送反馈信号。如果错误率足够的低，纠错码的冗余位串不是很长，又能够纠正所有的错误，前向纠错协议也可能是比较合理和简单的。8. Making one change to any valid character cannot generate another valid character due to the nature of parity bits. Ma

32、king two changes to even bits or two changes to odd bits will give another 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 32 页 - - - - - - - - - valid character, 所以 Hamming 距离为 2 9. Parity bits are needed at positions 1, 2, 4, 8, and 16, so messages that do no

33、t extend beyond bit 31 (including the parity bits) fit. Thus, five parity bits are sufficient. The bit pattern transmitted is 011010110011001110101 10. The encoded value is 101001001111. 11. If we number the bits from left to right starting at bit 1, in this example, bit 2 (a parity bit) is incorrec

34、t. The 12-bit value transmitted (after Hamming encoding) was 0 xA4F. The original 8-bit data value was 0 xAF. 12. 答： 单个错误将引起水平和垂直奇偶检查都出错。两个错误，无论是否同行或者同列，也容易被检测到。 对于有三位错误的情况， 就有可能无法检测了。 for example, if some bit is inverted along with its row and column parity bits. Even the corner bit will not catch

35、this. 13. 答： 用 n 行 k 列的矩阵来描述错误图案，在该矩阵中，正确的位用0 表示，不正确的位用 1 表示。由于总共有 4 位传输错误， 每个可能的错误矩阵中都恰有4 个 1。则错误矩阵的个数总共有C nk4个。而在错误矩阵中，当4 个 1 正好构成一个矩形的4 个顶点的时候，这样的错误是检测不出来的。则检测不出来的错误矩阵的个数为C2n C2k所以，错误不能检测的概率是：即；14. 答： 如所列的除式，所得的余数为x2+x+1。. 15. The frame is 10011101. The generator is 1001. The message after append

36、ing three zeros is 10011101000. The remainder on dividing 10011101000 by 1001 is 100. So, the actual bit string 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 32 页 - - - - - - - - - transmitted is 10011101100. The received bit stream with an error in the third

37、 bit from the left is 10111101100. Dividing this by 1001 produces a remainder 100, which is different from zero. Thus, the receiver detects the error and can ask for a retransmission. 16. 答：CRC 是在发送期间进行计算的。 一旦把最后一位数据送上外出线路，就立即把CRC 编码附加在输出流的后面发出。如果把CRC 放在帧的头部，那么就要在发送之前把整个帧先检查一遍来计算CRC。这样每个字节都要处理两遍， 第一

38、遍是为了计算检验码， 第二遍是为了发送。把CRC 放在尾部就可以把处理时间减半。17. 答：当发送一帧的时间等于信道的传播延迟的2 倍时，信道的利用率为50%。或者说，当发送一帧的时间等于来回路程的传播延迟时，效率将是50%。而在帧长满足发送时间大于延迟的两倍时，效率将会高于50%。现在发送速率为 4Mb/s，发送一位需要 0.25。只有在帧长不小于160kb 时，停等协议的效率才会至少达到50%。18. 答； 为了有效运行，序列空间（实际上就是发送窗口大小）必须足够的大，以允许发送方在收到第一个确认应答之前可以不断发送。信号在线路上的传播时间为6 3000=18000，即 18ms。在 T1

39、 速率，发送 64 字节的数据帧需花的时间：64 8 (1.536 106)= 0.33 。所以，发送的第一帧从开始发送起，18.33ms 后完全到达接收方。确认应答又花了很少的发送时间（忽略不计）和回程的18ms。这样，加在一起的时间是36.33ms。发送方应该有足够大的窗口，从而能够连续发送36.33ms 。36. 33/0.33=110 也就是说，为充满线路管道，需要至少110 帧，因此序列号为7 位。19. It can happen. Suppose that the sender transmits a frame and a garbled acknowledgement com

40、es back quickly. The main loop will be executed a second time and a frame will be sent while the timer is still running. 20. Let the sender s window be (Sl , Su) and the receivers be (Rl , Ru). Let the window size be W. The relations that must hold are: 0 Su- Si+1 W1RuRl1WSlRlSu121. 答： 改变检查条件后，协议将变得

41、不正确。假定使用3 位序列号，考虑下列协议运行过程：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 32 页 - - - - - - - - - A 站刚发出 7 号帧； B 站接收到这个帧，并发出捎带应答ack。A 站收到 ack，并发送06 号帧。假定所有这些帧都在传输过程中丢失了。B 站超时，重发它的当前帧， 此时捎带的确认号是 7。考察 A 站在 r.rack=7 到达时的情况，关键变量是ack_expected=0 ，r.rack=7，next_frame_t

42、o_send_=7 。修改后的检查条件将被置成“真”，不会报告已发现的丢失帧错误，而误认为丢失了的帧已被确认。另一方面，如果采用原先的检查条件，就能够报告丢失帧的错误。所以结论是：为保证协议的正确性，已接收的确认应答号应该小于下一个要发送的序列号。22. 答： 可能导致死锁。假定有一组帧正确到达，并被接收。然后，接收方会向前移动窗口。现在假定所有的确认帧都丢失了，发送方最终会产生超时事件，并且再次发送第一帧，接收方将发送一个NAK 。然后 NONAK 被置成伪。假定 NAK 也丢失了。那么从这个时候开始，发送方会不断发送已经被接收方接受了的帧。接收方只是忽略这些帧， 但由于 NONAK 为伪，

43、所以不会再发送NAK ，从而产生死锁。如果设置辅助计数器（实现“else ”子句），超时后重发 NAK ，终究会使双方重新获得同步。23. 答： 删除这一段程序会影响协议的正确性，导致死锁。因为这一段程序负责处理接收到的确认帧，没有这一段程序，发送方会一直保持超时条件，从而使得协议的运行不能向前进展。24. It would defeat the purpose of having NAKs, so we would have to fall back to timeouts. Although the performance would degrade, the correctness wo

44、uld not be affected. The NAKs are not essential. 25. 答： 这里要求 r.rack+1next_frame_to_send 。考虑下列操作细节：A 站发送 0 号帧给 B 站。B 站收到此帧，并发送ACK 帧，但 ACK 丢失了。 A 站发生超时，重发 0 号帧。但 B 站现在期待接收 1 号帧，应此发送 NAK ，否定收到的 0 号帧。显然，现在 A 站最好不重发 0 号帧。由于条件 r.rack+1next_frame_to_send 不成立，所以用不着选择性重传 0 号帧，可以继续向前推进传送1 号帧。这个例子就说明了这段程序中的另一个

45、条件，即 r.rack+1next_frame_to_send 也是重要的。26. 答：不可以。最大接收窗口的大小就是1。现在假定该接收窗口值变为2。开始时发送方发送 0 至 6 号帧，所有 7 个帧都被收到，并作了确认，但确认被丢失。现在接收方准备接收 7 号和 0 号帧，当重发的 0 号帧到达接收方时， 它将会被缓存保留， 接收方确认 6 号帧。当 7 号帧到来的时候， 接收方将把 7 号帧和缓存的 0 号帧传递给主机， 导致协议错误。因此，能够安全使用的最大窗口值为1。27. 答： 发送 1 位用时间 1， 发送 1000bit 的最长帧花时间 1ms。 由于超时间隔是 10ms，而 1

46、s 才能产生一个新的数据帧，所以超时是不可避免的。假定A 站向 B 站发送一个帧，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 32 页 - - - - - - - - - 正确到达接收方， 但较长时间无反向交通。不久， A 站发生超时事件，导致重发已发过的一帧。B 站发现收到的帧的序列号错误，因为该序列号小于所期待接收的序列号。因此B 站将发送一个 NAK ，该 NAK 会携带一个确认号， 导致不再重发该帧。 结果每个帧都被发送两次。28. 答： 不能，协议的运行将

47、会失败。当MaxSeq=4，序列号的模数 =4+1=5，窗口大小将等于： NrBufs1 时，信道总是过载的，因此在这里信道是过载的。7. 答：每帧传送次数的数学期望为：E 个事件为 E-1 个长度等于 4 个时隙的间隔时间所分隔。因此一个帧从第一次发送开始时间到最后一次尝试成功的发送开始时间之间的长度即延迟是4(eG1)，吞吐率 S= Ge-G。对于每一个 G 值，都可以计算出对应的延迟值D=4(eG-1)，以及吞吐率值 S=Ge-G。按此方法即可画出时延对吞吐率的曲线。8. (a) The worst case is: all stations want to send and s is

48、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

49、 other N-1 stations have transmitted one frame each, and N contention periods of size log2 N each. Wait time is thus(N+1)d+N log2 bits. 9. 答：在解答这一问题之前， 首先要了解什么是Mok 和 Ward 版本的二进制倒计数法。在二进制倒计数法中，每个想要使用信道的站点首先将其地址以二进制位串的形式按照由高到低的顺序进行广播，并且假定所有地址的长度相同。为了避免冲突，必须进行仲裁：如果某站发现其地址中原本为0 的高位被置换为 1，那么它便放弃发送。对于次高位进

50、行同样的信道竞争操作，直到最后只有一个站赢得信道为止。一个站点在赢得信道竞争后便可发送一帧，然后另一个信道竞争周期又将开始。Mok 和 Ward 提出了二进制倒计数法的一个变种。该方法采用了并行接口而不是串行接口：还使用虚拟站号，在每次传输之后对站重新编号，从 0开始，已成功传送的站被排在最后。如果总共有N 个站，那么最大的虚拟站号是N-1。在本题中， 当 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 个站点的虚站号变为：