计算机网络 第三章 课后题答案

英文版教材第三章 1、2、3、4、6、7、9、11、14、15、16, 补充题1

1. An upper-layer packet is split into 10 frames, each of which has an 80% 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?
   考点：概率中的乘法和加法原理
   答：整个报文无差错的到达接受端的概率$=0.8^{10}=0.107$=0.810=0.107，因此成功发送1个报文平均需要传输的概率$=\frac{1}{0.107}=9.3$=0.1071​=9.3

2. The following character encoding is used in a data link protocol:
   A: 01000111 B: 11100011 FLAG: 01111110 ESC: 11100000
   Show the bit sequence transmitted (in binary) for the four-character frame A B ESC FLAG when each of the following framing methods is used:
   (a) Byte count.
   (b) Flag bytes with byte stuffing.
   (c ) Starting and ending flag bytes with bit stuffing.
   考点：3种成帧方式
   答：（a）00000100 01000111 11100011 11100000 01111110(4 A B ESC FLAG)
   （b）01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110(FLAG A B ESC ESC ESC FLAG FLAG)
   （c）01111110 01000111 110100011 111000000 011111010 (A B ESC FLAG)
   注意：考试经常反向考（给HDLC帧，还原数据）

3. 假定利用海明码传送 16bit 报文，则需要添加多少 bit 的检查位才能确保接受方能够检测并纠正单个 bit 错误？
   如果传送 1101001100110101 的报文，在使用偶数校验方式，请给出传送的位模式。
   考点：纠错码（海明码）
   答：根据公式 $m+r+1≤2^r$m+r+1≤2r，当 $m=16$m=16 时，r最小为5。因此需要添加 5bit 的检查位。
   
   利用编码简便法有：码字中为1的位号为 b3, b5, b7, b11, b12, b15, b17, b19, b21，表示为二进制码并按模2求和，得到校验码 P5P4P3P2P1=01011，因此发送的位模式为 111010110011001010101

4. What is the remainder obtained by dividing $x^7 + x^5 + 1$x7+x5+1 by the generator polynomial $x^3 + 1$x3+1?
   考点：检错码(CRC)
   答：将 $M(x)=x^7 + x^5 + 1$M(x)=x7+x5+1 表示为2进制为 10100001，由题意知 $r=3$r=3，将 $M(x)$M(x) 左移 3 位得到：10100001000，$R(x)=10100001000\%G(x)=111$R(x)=10100001000%G(x)=111

5. Data link protocols almost always put the CRC in a trailer rather than in a header. Why?
   考点：计算机网络的串行通信
   答：串行通信，接受完帧后可直接看校验位，节省存储，加速；否则要额外存储CRC且效率降低

6. 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%?
   考点：停等协议的信道利用率
   
   答：由题意知：$T_f=\frac{L}{4kbps},T_d=20ms$Tf​=4kbpsL​,Td​=20ms，信道利用率 $Cr=\frac{T_f}{T_f+2T_d}≥50\%$Cr=Tf​+2Td​Tf​​≥50%，代入得 $L≥160bit$L≥160bit

7. 如果Go back N 中的between函数检查的条件是 $a≤b≤c$a≤b≤c 而不是 $a≤b<c$a≤b<c，则对于协议的正确性和效率有影响吗？
   考点：理解Go back N的流程和原理；学会假设发送应答场景，利用错误样例来推翻题目中的假设
   答：有影响。 考虑以下情况（3bit举例）：先发送7号帧，成功接收并返回ACK；接着连发0-6号帧，但发生丢失。接收端等不到ACK，触发timeout事件，重新发送刚才的帧，此时携带的ACK=7。发送端检测到7满足a≤b≤c，误认为0-6号帧成功发送。在未收到0-6号帧时，发送端未进行回退，导致帧顺序出错。

8. Consider the operation of protocol 6 over a 1-Mbps perfect (i.e., error-free) line. The maximum frame size is 1000 bits. New packets are generated 1 second apart. The timeout interval is 10 msec. If the special acknowledgement timer were eliminated, unnecessary timeouts would occur. How many times would the average message be transmitted?
   考点：理解选择重传协议的工作原理和流程
   确定是否会发生超时：传输时间$=1000 bit/1Mb=1ms$=1000bit/1Mb=1ms，而 $10ms≪1s$10ms≪1s，所以超时不可避免；
   确定是否会产生NAK帧：超时后发送端会重发帧，接收端发现重复，回NAK，然后发送端可发新帧（序号滚动）。
   因此，平均每帧传送2次

9. In protocol 6, $MAX\_SEQ = 2^n − 1$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$MAX_SEQ=4, for example?
   考点：$MAX\_SEQ$MAX_SEQ和arrived[]在协议6中的作用，与模运算的关系；情景假设
   答：若$MAX\_SEQ=4$MAX_SEQ=4，则模$=5, Ws=Wr=5/2=2$=5,Ws=Wr=5/2=2，则只有两个缓冲区in_buf[0]和in_buf[1]，序号从0-4开始轮回，0,2,4使用in_buf[0]，1,3使用in_buf[1]。假设0,1,2,3都正确收到并已回复ACK，则下一步发送4,0。若4丢失但0成功接收时，0号帧会占用in_buf[0]，此时arrive[0]=true，则while中的数据发生错序上交。

10. 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 for
    (a) Stop-and-wait?
    (b) Protocol 5?
    (c ) Protocol 6?
    考点：信道利用率的计算（单个信道），一定画出时序图：
    
    答：因为总是使用捎带应答技术，因此信道利用率 $Cr=\frac{T_f}{2T_f+2T_d}$Cr=2Tf​+2Td​Tf​​，信道传播时延 $t_传=\frac{1k}{1Mbps}=1ms$t传​=1Mbps1k​=1ms
    （a）$Cr=\frac{1}{2×1+2×270}=0.185\%$Cr=2×1+2×2701​=0.185%。
    （b）$Ws=2^3-1=7$Ws=23−1=7，则 $Cr=\frac{1×7}{2×1+2×270}=1.29\%$Cr=2×1+2×2701×7​=1.29%
    （c）$Ws=2^{3-1}=4$Ws=23−1=4，则 $Cr=\frac{1×4}{2×1+2×270}=0.738\%$Cr=2×1+2×2701×4​=0.738%
    其他考题类型：$Ws$Ws为多少时效率能达到100%？$Ws＞Ws_{max}$Ws＞Wsmax​ 时效率为多少（还是100%）？

11. 在一个负载很重的50Kbps的卫星信道上使用协议6，数据帧包含40bit的头和3960bit的数据，请计算一下浪费在头部和重传的开销占多少比例？
    假设从地球到卫星的信号传输时间为270ms。
    ACK 帧永远不会发生；
    NAK 帧为40bit。
    数据帧的错误率为1％，NAK帧的错误率忽略不计。
    序号位为8位。
    考点：根据已知条件和协议分析，画出时序图
    答：帧长度$=40+3960=4000bit$=40+3960=4000bit，发送时延$=\frac{4000}{50kbps}=80ms$=50kbps4000​=80ms，因为未发送ack，则一定采用了捎带应答技术，由此画出时序图：
    
    成功发送一帧的时间$=2×80+2×270=700ms$=2×80+2×270=700ms.已知序号位为8位，则 $Ws=2^{n-1}=2^7=128$Ws=2n−1=27=128，对应的发送时延$=128×80=10240ms>>700ms$=128×80=10240ms>>700ms，则此时的链路利用率是100%，管道中充满了比特。
    每个帧重传开销$=4000×1\%=40bit$=4000×1%=40bit
    每个帧 nak 开销$=40×1\%=0.4bits$=40×1%=0.4bits
    协议头40bit，因此总的开销$=40+0.4+40=80.4bit$=40+0.4+40=80.4bit，所占比例$=\frac{80.4}{80.4+3960}=1.99\%$=80.4+396080.4​=1.99%

12. 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.
    考点：极限信道利用率与吞吐量的计算
    答：512字节数据帧发送时延$=\frac{512×8bit}{64kbps}=64ms$=64kbps512×8bit​=64ms。接受端回一个很短的ack（不计发送时间），因此时序图如下：
    
    信道利用率达到100%时有 $W_S·T_f≥2T_d+T_f$WS​⋅Tf​≥2Td​+Tf​，所以在 $W_S≥9.4375$WS​≥9.4375，即 $W_S>10$WS​>10 时，吞吐量$=64kbps$=64kbps。当窗口大小 $=n(n≤9)$=n(n≤9) 时，吞吐率$=\frac{64n}{64+2×270}$=64+2×27064n​。当 $n=1,7,15,127$n=1,7,15,127 时代入上式，得到结果为（吞吐量=吞吐率×带宽）：
    

13. 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?
    考点：时延带宽积的计算
    答：电缆的传输速率$=2/3×3×10^8=2×10^8 m/s$=2/3×3×108=2×108m/s，则传播时延$=\frac{100km}{2×10^8 m/s}=5×10^{-4} s$=2×108m/s100km​=5×10−4s，T1的带宽$=1.544Mbps$=1.544Mbps，则电缆中容纳的比特（时延带宽积）$=5×10^{-4}×1.544Mbps=772bit$=5×10−4×1.544Mbps=772bit

14. Give at least one reason why PPP uses byte stuffing instead of bit stuffing to prevent accidental flag bytes within the payload from causing confusion.
    考点：PPP的特点
    答：①PPP是由软件实现的，而位填充在硬件协议中实现，对于软件实现，字节操作比位操作更简单；②PPP是设计用于调制解调器的，调制解调器接收和传送数据的单位是字符而不是位。

15. What is the minimum overhead to send an IP packet using PPP? Count only the overhead introduced by PPP itself, not the IP header overhead. What is the maximum overhead?
    考点：PPP帧的数据结构
    答：最小开销是：每帧有2个标志字节、1个协议字节和2个校验字节，每帧总共5字节开销；
    最大开销是：2个标志字节、1个地址字节、1个控制字节、2个协议字节和4个校验字节，一共10字节开销。

    补充题1：一个PPP帧的数据部分(用十六进制写出)是7D 5E FE 27 7D 5D 7D 5D 65 7D 5E。试问真正的数据是什么（用十六进制写出）？
    考点：字节填充的理解
    答：由于PPP的字节填充法规定：
    0x7E转换为(0x7D, 0x5E)；0x7D转换为(0x7D, 0x5D)
    
    补充题2：在网络中截获了一串数据，用十六进制表示为：06 7E 25 7D 5E 16 7D 5D 7E A8 FF，其中包含一个完整的PPP帧，请以十六进制写出该PPP帧的内容（不包含首尾标志）
    考点：对字节填充首尾标志法的理解
    答：PPP帧的帧头、帧尾都是7E，因此完整的传输帧是7E 25 7D 5E 16 7D 5D 7E，去掉帧头帧尾和填充字节，帧中的内容是：25 7E 16 7D