CH3 数据链路层习题

CH3 数据链路层习题

CH3 数据链路层习题

3.1 典型习题与分析

【3】 位串0111101111101111110需要在数据链路层上被发送，请问，经过位填充之后实际被发送出去的是什么？

解答：

经过位填充之后的输出为：011110111110011111010。

【4】 假设使用海明码来传输16位的报文。请问，需要多少个检查位才能确保接收方可以检测并纠正单个位错误？对于报文1101001100110101，请给出所传输的位模式。假设在海明码中使用了偶数位。 解答：

对于一个16位的报文只在1，2，4，8和16位需要校验位，所以五个校验位就够了，所要传输的位模式为0110101110011001110101。

【5】 检测错误的一种方法是按n行、每行k位来传输数据，并且在每行和每列加上奇偶位。其中右下角是一个检查它所在行和列的奇偶位。这种方案能够检测出所有的单个错误吗？2位错误呢？3位错误呢？ 解答：

单个错误能够很容易的被行校验和列校验检测出来；两个错误时，如果不在同一行，行校验可以检测出来，如果在同一行，列校验可以检测出来；对于三个错误，如果同一行和同一列的位同时翻转，就无法检测出错误。

【6】 一条3000公里长的T1骨干线路被用来传输64字节的帧，两端使用了回退n帧技术的协议。如果传输速度为6?s/公里，则序列号应该有多少位？

解答：

为了能够正常传输，序列号（也就是窗口大小）必须足够大使得发送器发送数据直到接收到第一个回应为止。线路传输时延为18ms，T1线路的速度为1.536Mbps，64字节的帧需要0.3ms。所以，第一帧完全到达需要18.3ms，同时回应帧需要18ms返回，总共需要的时间为36.3ms。发送器需要能够保持36.3ms的窗口大小，发送一帧需要0.3ms，所以可以发送121个帧，那么7位的序列号就足够了。

【7】 考虑在一条1Mbps的无错误的线路上使用选择性重传协议的操作。最大的帧长度为1000位，每过1秒钟产生新的分组，超时间隔为10ms。如果特殊的确认定时器被去掉的话，则不必要的超时就会发生。平均报文要被传输多少次？ 解答：

假定A给B发送一帧数据正确到达，但是B没有发送相应的回应，过段时间A超时重传，但是当B接收到这帧数据时发现序号不对，低于期待的序号值，因此它发送带确认号的NAK给A。所以每帧将会被重传两次。

【8】 PPP基本上是以HDLC为基础的，HDLC则使用了位填充技术来防止在有效载荷数据中偶尔出现标志字节，以避免引起混淆。请给出至少一个理由说明为什么PPP却使用了字节填充技术？

－ 1 －

CH3 数据链路层习题

解答：

PPP和HDLC相比它是用软件来实现的，而HDLC是硬件实现的，在软件中对字节的操作相对于位操作要简单的多；另外PPP是为MODEM来设计的，而MODEM是对字节操作的而不是对位操作的。

【9】 利用地球同步卫星在一个1Mbps的信道上发送1000位的帧，该信道离开地球的传输延迟为270ms。确认信息总是被捎带在数据帧上。头部非常短，并且使用3位序列号。在下面的协议中，最大可获得的信道利用率是多少？

(a) 停－等协议

(b) 回退n帧协议 (c) 选择性重传协议

解答：

假定t=0时开始传输，t=1ms时第一帧发送完毕，t=271ms时第一帧到达接收点，t=272ms时回应帧发送完毕，t=542ms时回应帧到达接收点。所以传输一帧的周期为542ms。542ms内发送k帧数据，它的效率为k/542。所以，

(a) k = 1，效率为1/542 = 0.18%

(b) k = 7，效率为7/542 = 1.29% (c) k = 4，效率为4/542 = 0.74%

【10】 在一个负载很重的50kbps卫星信道上使用选择性重传协议，数据帧包含40位的头和3960位的数据，请计算一下浪费在头部和重传的开销占多少比例。假设从地球到卫星的信号传输时间为270ms。ACK帧永远不会发生，NAK帧为40位。数据帧的错误率为1％，NAK帧的错误率忽略不计，序列号为8位。 解答：

对于50kbps的信道和8位的序列号，信道始终是满的。平均每帧重传的次数为0.01。每个正确接收的帧浪费了40位的头，1％×4000位的重传位和每100帧就有一个40位的NAK，所以每3960位的数据对应80.4位的开销，即80.4/(3960+80.4)=1.99%。

【11】一个信道的数据速率为4kbps，其传播时延为20ms，那么对于效率至少为50％的停等协议而言，此协议帧的大小范围为多少？ 解答：

对于停等协议，其协议效率为U?tproptframe20msL/4k11?2a。当U?50%时，可以得到

a??，因此得到L?160，即帧长度应该大于160比特。

【12】对于窗口大小为1000比特，速率为1Mbps，延迟为270ms的卫星信道，下列情况下的最大链路利用率是多少？

a. 采用停等协议的流量控制。 b. 连续流量控制，窗口大小为7。 c. 连续流量控制，窗口大小为127。 d. 连续流量控制，窗口大小为255。

－ 2 －

CH3 数据链路层习题

解答：在此卫星信道下，a?270ms1000/1Mb/s?270

1?0.0018。

（a）采用停等协议，其链路的最大利用率为U?1?2aW7（b）W＝7，连续流量控制下的链路利用率为U???0.0126。

1?2a1?540（c）W＝127，连续流量控制下的链路利用率为U?（d）W＝255，连续流量控制下的链路利用率为U?W1?2aW1?2a??1271?5402551?540?0.2286。 ?0.459。

【13】一个信道的数据速率为R bps，传输时延为t秒/公里，发送端和接收端的距离为L公里，帧的大小固定为B比特，在最大利用率的前提下给出帧的序号域的最小值(忽略回应帧的影响)。 解答：

当窗口大小W?2a?1时，信道得利用率为100％，因此应该取W?2a?1。 而a?tproptframe?L?tB/R?1BL?R?t，因此W?2BL?R?t?1，而帧的序号域的最小值应该是

2??n??log2(L?R?t?1)??1。

B??【14】对于P = 110011，M = 11100011，求其CRC是多少？

解答：由于P的位数是6，因此应该加5为冗余位，计算如下：

111?1101?100011?1011011011010110000011001100111010101101011011010

101?11011?11 因此R＝11010， T＝1110001111010。

【15】两个相邻的节点A、B采用滑动窗口协议，其序号占用3比特，在后退N帧ARQ的方式中，发送方的窗口尺寸为4。假定A给B发送数据，对于下列事件指出窗口的位置： a. 在A发送数据帧之前。

b. 在A发送数据帧0，1，2之后，B应答了0，1帧，并且A收到了这些回应帧。 c. 在A发送数据帧3，4，5之后，B应答了第4帧，并且A收到了这些回应帧。

－ 3 －

CH3 数据链路层习题

解答：根据滑动窗口的原理和后退N帧ARQ的基本思想，结果如图3.18所示。

节点A01234567010123节点B45670（a）节点A0123456701012节点B345670（b）节点A0123456701012节点B345670（c） 图 3.18 滑动窗口的位置

【16】在上题中，如果采用选择重发ARQ方式，且发送方和接收方的窗口尺寸都是4。题中的三个问题的结果又如何？

解答：根据滑动窗口的原理和选择重发ARQ的基本思想，结果如图3.19所示。

节点A01234567010123节点B45670（a）0123456701012345670（b）0123456701012345670（c）01234567010123456701（d） 图 3.19 滑动窗口的位置

【15】两个节点通过一条1Mbps的卫星链路进行通信，传输时延为270ms，卫星在这里的作用只是做一下转发，可以忽略交换时延，对于帧大小为1024，3位顺序号的HDLC协议，那么最大可能的数据吞吐量是多少？ 解答：

－ 4 －