接收方确认 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 -