数等于：
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 -