3-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?
这样将使得NAK的作用失效，于是我们将退回到超时。尽管效率会降低，正确性却不会受到影响。NAK不是必不可少的。
3-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. 在协议6中，针对frame_arrival的代码中有一部分被用于NAK。如果收到的帧是一个NAK，并且另一个条件也满足的话，则这部分代码会被调用到。请给出一个场景，在此场景下这另一个条件是非常关键的。 答：这里要求r.rack+1 A 站发送0 号帧给B 站。B 站收到此帧，并发送ACK帧，但ACK丢失了。A 站发生超时，重发0 号帧。但B 站现在期待接收1 号帧，应此发送NAK，否定收到的0 号帧。显然，现在A 站最好不重发0 号帧。由于条件r.rack+1 3-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 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 largest window that can be safely used? 想象你正在编写一个数据链路层软件，它被用在一条专门给你发送数据的线路上，而不是让你往外发送数据。另一端使用了HDLC，3位序列号和一个可容纳7帧的窗口。你希望将乱序的帧尽可能多地缓存起来，以提高效率，但是你又不允许修改发送方的软件。是否有可能让接收方的窗口大于1，并且仍然保证该协议不会失败呢？如果可能的话，能够安全使用的最大窗口是多少？ 答：不可以。最大接收窗口的大小就是1。现在假定该接收窗口值变为2。开始时发送方发送0 至6 号帧，所有7 个帧都被收到，并作了确认，但确认被丢失。现在接收方准备接收7 号和0 号帧，当重发的0 号帧到达接收方时，它将会被缓存保留，接收方确认6 号帧。当7 号帧到来的时候，接收方将把7 号帧和缓存的0 号帧传递给主机，导致协议错误。因此，能够安全使用的最大窗口值为1。 3-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? 在协议6中，MAX_SEQ＝2n－1.这个条件显然是希望尽可能地利用头部的位，但是我们无法证明这个条件确实很关键。例如，协议在MAX_SEQ＝4的时候也能够正确地工作吗？ 答：不能，协议的运行将会失败。当MaxSeq=4，序列号的模数=4+1=5，窗口大小将等于：NrBufs<=5/2=2.5，即得到，NrBufs=2。因此在该协议中，偶数序号使用缓冲区1。这种映射意味着帧4 和0 将使用同一缓冲区。假定0 至3 号帧都正确收到了，并且都确认应答了，并且都确认应答了。如果随后的4 号帧丢失，且下一个0 号帧收到了，新的0 号帧将被放到缓冲区0 中，变量arrived[0]被置成“真”。这样，一个失序帧将被投递给主机。事实上，采用选择性重传的滑动窗口协议需要MaxSeq 是奇数才能正确的工作。然而其他的滑动窗口协议的实现并不具有这一性质。 第 13 页 共 40 页 3-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 for (a) Stop-and-wait. (b) Protocol 5. (c) Protocol 6. 利用地球同步卫星在一个1Mbps的信道上发送1000位的帧，该信道离开地球的传输延迟为270ms。确认信息总是被捎带在数据帧傻姑娘。头部非常短，并且使用3位序列号。在下面的协议中，最大可获得的信道利用率是多少？(a)停-等协议(b)协议5（c)协议6 答：对应三种协议的窗口大小值分别是1、7 和4。 使用卫星信道端到端的典型传输延迟是270ms，以1Mb/s 发送，1000bit 长的帧的发送时间为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% 3-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 propagation time from the earth to the satellite is 270 msec. ACK frames never occur. NAK frames are 40 bits. The error rate for data frames is 1 percent, and the error rate for NAK frames is negligible. The sequence numbers are 8 bits. 答：使用选择性重传滑动窗口协议，序列号长度是8 位。窗口大小为128。卫星信道端到端的传输延迟是270ms。以50kb/s 发送，4000bit（3960+40）长的数据帧的发送时间是0.02*4000=80ms。我们用t=0 表示传输开始时间，那么，t=80ms，第一帧发送完毕； 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%。 3-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? 答：在该电缆中的传播速度是每秒钟200 000km，即每毫秒200km，因此100km 的电缆将会在0.5ms 内填满。T1 速率125传送一个193 位的帧，0.5ms 可以传送4 个T1 帧，即193*4=772bit。 第 14 页 共 40 页 第 4 章 介质访问子层 4-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 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 frame arrival rates, give the delay experienced by the average frame, including both queueing time and transmission time. (a) 90 frames/sec. (b) 900 frames/sec. (c) 9000 frames/sec. (time delay, T // a channel of capacity C bps // with an arrival rate of ? frames/sec) 这个公式是4.1.1段落给出的Markov排队问题的标准公式。也就是，。这里C =108 、， sec。对于这三种到达速率，我们得出的是(a) 0.1 msec,(b) 0.11 msec, (c) 1 msec. 对于c 的情况，我们操作一个带来10倍延迟的排队系统 4-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 one has not yet been sent (e.g., the stations can buffer outgoing frames). What is the maximum value of N? N个站共享一个56kbps的纯ALOHA信道。每个站平均每100秒输出一个1000位的帧，及时前面的帧还没有被送出，它也这样进行（比如这些站可以将送出的帧缓存起来）。请问N的最大值是多少？ 答：对于纯的ALOHA，可用的带宽是0.184×56 Kb/s?=10.304?Kb/ s。每个站需要的带宽为1000/100=10b/s。而N=10304/10≈1030 所以，最多可以有1030 个站，即N 的最大值为1030。 4-3 Consider the delay of pure ALOHA versus slotted ALOHA at low load. Which one is less? Explain your answer. 答：对于纯的ALOHA，发送可以立即开始。对于分隙的ALOHA，它必须等待下一个时隙。这样，平均会引入半个时隙的延迟。因此，纯ALOHA 的延迟比较小。 4-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 μsec. What is the approximate total channel load? 每个终端每200（=3600/18）秒做一次请求，总共有10 000 个终端，因此，总的负载是200 秒做10000 次请求。平均每秒钟50 次请求。每秒钟8000 个时隙，所以平均每个时隙的发送次数为50/8000=1/160。 第 15 页 共 40 页 4-5 A large population of ALOHA users manages to generate 50 requests/sec, including both originals and retransmissions. Time is slotted in units of 40 msec. (a) What is the chance of success on the first attempt? (b) What is the probability of exactly k collisions and then a success? (c) What is the expected number of transmission attempts needed? 一大群ALOHA用户每秒钟产生50个请求，包括原始的请求和重传的请求。时槽单位为40ms。(a)首次发送成功的几率是多少？(b)恰好k次冲突之后成功的概率是多少? (c)所需传送次数的期望值是多少？ 答：（a）在任一帧时间内生成k 帧的概率服从泊松分布 生成0 帧的概率为e-G 对于纯的ALOHA，发送一帧的冲突危险区为两个帧时，在两帧内无其他帧发送的概率是e-G×e –G=e-2G 对于分隙的ALOHA，由于冲突危险区减少为原来的一半，任一帧时内无其他帧发送的概率是e-G 。 现在时隙长度为40ms，即每秒25 个时隙，产生50 次请求，所以每个时隙产生两个请求，G=2。因此，首次尝试的成功率是：e-2 = 1/ e2 （b） （c）尝试k 次才能发送成功的概率（即前k-1 次冲突，第k 次才成功）为： 那么每帧传送次数的数学期望为 4-6 Measurements of a slotted ALOHA channel with an infinite number of users show that 10 percent of the slots are idle. (a) What is the channel load, G? (b) What is the throughput? (c) Is the channel underloaded or overloaded? 对一个无限用户的分槽ALOHA信道的测试表明，10%的时槽是空闲的。(a)信道载荷G是多少?(b)吞吐量是多少?（c)该信道是载荷不足，还是过载了? 答：（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 时，信道总是过载的，因此在这里信道是过载的。 4-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 (a) the basic bit-map protocol? (b) Mok and Ward's protocol with permuting virtual station numbers? 如果一个LAN使用了下列协议，请问在最差情况下，一个站s在开始传送帧之前必须要等到多长时间？（a）基本的位图协议（b）改变虚拟站序列号的Mok-Ward协议 (a) 最坏的情况是：所有站都想发送，其中s是编号最小的站点。等待时间是N位争用周期+(N-1) ×d 位帧传输，一共是N+(N-1) d位时间； (b) (b) 最坏的情况是：所有站都有帧要传输，s具有其中最小的虚拟站编号。因此，s在其它N-1个站各发送了一个帧之后将获得传输机会，以及每个大小为log2 N 的N个争用周期。 等待时间是(N+1)×d+N×log2 Nbits.？？？ 第 16 页 共 40 页