# 数据链路层习题 ## 数据链路层功能 **例题** 数据链路层协议的功能不包括()。 $A.$定义数据格式 $B.$提供结点之间的可靠传输 $C.$控制对物理传输介质的访问 $D.$为终端结点隐蔽物理传输的细节 解：$D$。数据链路层的主要功能包括组帧，组帧即定义数据格式，$A$正确。数据链路层在物理层提供的不可靠的物理连接上实现结点到结点的可靠性传输，$B$正确。控制对物理传输介质的访问由数据链路层的介质访问控制（$MAC$）子层完成，$C$正确。数据链路层不必考虑物理层如何实现比特传输的细节，因此$D$错误。 **例题** 为了避免传输过程中帧的丢失，数据链路层采用的方法是()。 $A.$帧编号机制 $B.$循环冗余校验码 $C.$汉明码 $D.$计时器超时重发 解：$D$。为防止在传输过程中帧丢失，在可靠的数据链路层协议中，发送方对发送的每个数据帧设计一个定时器，当计时器到期而该帧的确认帧仍未到达时，发送方重发该帧。为保证接收方不会接收到重复帧，需要对每个发送的帧进行编号。汉明码和循环冗余校验码都用于差错控制。 ## 组帧 **例题** 在一个数据链路协议中使用下列字符编码： $A\,0100\,0111$；$B\,1110\,0011$；$ESC\,1110\,0000$；$FLAG\,0111\,1110$ 在使用下列成帧方法的情况下，说明为传送$4$个字符$A$、$B$、$ESC$、$FLAG$所组织的帧而实际发送的二进制位序列（使用$FLAG$作为首尾标志，$ESC$作为转义字符）。 1）字符计数法。 2）使用字符填充的首尾定界法。 3）使用比特填充的首尾标志法。 1）解：第一字节为所传输的字符计数$5$，转换为二进制为$0000\,0101$，后面依次为$A$、$B$、$ESC$、$FLAG$的二进制编码：$0000\,0101\quad0100\,0111\quad1110\,0011\quad1110\,0000\quad0111\,1110$。 2）解：首尾标志位$FLAG$（$0111\,1110$）在首部和尾部都需要加上，在所传输的数据中，若出现控制字符，则在该字符前插入转义字符$ESC$（$1110\,0000$）：$0111\,1110\quad0100\,0111\quad1110\,0011\quad1110\,0000\quad1110\,0000\quad1110\,0000\quad0111\,1110\quad0111\,1110$。 3）解：首尾标志位$FLAG$（$0111\,1110$）在首部和尾部都需要加上，在所传输的数据中，若连续出现$5$个“$1$”，则在其后插入“$0$”：$0111\,1110\quad0100\,0111\quad1101\,0011\quad1110\,0000\quad0111\,11010\quad0111\,1110$。 ## 差错控制 ### 噪声 **例题** 通过提高信噪比可以减弱其影响的差错是())。 $A.$随机差错 $B.$突发差错 $C.$数据丢失差错 $D.$干扰差错 解：$A$。一般来说，数据的传输差错是由噪声引起的。通信信道的噪声可以分为两类：热噪声和冲击噪声。热噪声一般是信道固有的，引起的差错是随机差错，可以通过提高信噪比来降低它对数据传输的影响。冲击噪声一般是由外界电磁干扰引起的，引起的差错是突发差错，它是引起传输差错的主要原因，无法通过提高信噪比来避免。 ### CRC循环冗余码 **例题** 在数据传输过程中，若接收方收到的二进制比特序列为$1011\,0011\,010$，接收双方采用的生成多项式为$G(x)=x^4+x^3+1$，则该二进制比特序列在传输中是否出错?如果未出现差错，那么发送数据的比特序列和$CRC$检验码的比特序列分别是什么？ 解：根据题意，生成多项式$G(x)$对应的二进制比特序列为$11001$。进行如下的二进制模二除法，被除数为$1011\,0011\,010$，除数为$11001$所得余数为0,因此该二进制比特序列在传输过程中未出现差错。发送数据的比特序列是$1011\,001$，$CRC$检验码的比特序列是$1010$。 ## 流量控制 ### 停止等待协议 **例题** 如一个信道的数据传输速率为$4kb/s$，单向传播时延为$30ms$，若使用停止等待协议的信道最大利用率为$80\%$，则数据帧长度至少为多少？ 解：令数据帧长度为$L$（$kb$），利用公式：信道利用率=(单位时间内发送数据的比特数÷发送方发送数据传输率)÷发送周期。 得到：$0.8=\dfrac{L}{4}\div\left(\dfrac{L}{4}+2\times0.03\right)$ 最后得到$L=960b$。 **例题** 对于下列给定的值，不考虑差错重传，非受限协议（无须等待应答）和停止-等待协议的有效数据率是多少？（即每秒传输了多少真正的数据，单位为$b/s$。） $R$=传输速率（$16Mb/s$） $S$=信号传播速率（$200m/\mu s$） $D$=接收主机和发送主机之间传播距离（$200m$） $T$=创建帧的时间（$2\mu s$） $F$=每帧的长度（$500bit$） $N$=每帧中的数据长度（$450bit$） $A$=确认帧$ACK$的帧长（$80bit$） 解： 信道利用率公式都是实际传输的有用数据$N$除以传输这些数据所需要的时间。所以分子都是$N$。 1）非受限协议 传输周期包括创建帧的时间，以及发送整个帧的时间，不考虑传播时间，因为传播时间对于非受限协议不影响，会不停地发送，所以传播时间多长无关。 有效数据率：$=\dfrac{N}{T+\dfrac{F}{R}}=\dfrac{450bit}{2\mu s+\dfrac{500bit}{16bit/\mu s}}\approx13.53bit/\mu s=13.53Mb/s$。 2）停止等待协议 停止等待协议需要发送一次数据帧，还需要接收一次确认帧，所以需要两次建立帧的时延和传播时延。发送的数据包括数据本身以及一个$ACK$。 有效数据率：$=\dfrac{N}{2\times(T+D/S)+(F+A)/R}=\dfrac{450bit}{2\times\left(2\mu s+\dfrac{200m}{200m/\mu s}\right)+\dfrac{500bit+80bit}{16bit/\mu s}}\approx10.65bit/\mu s=10.65Mb/s$。 ### 后退N帧协议 $k$位比特编号最大接受窗口为$2^k-1$。 **例题** 数据链路层采用了$GBN$协议，发送方已经发送了编号为$0$到$7$的帧，当计时器超时时，若发送方只收到了$0$、$2$、$3$号帧的确认，则发送方需要重新发送的帧数为（）。 $A.1$    $B.2$    $C.3$    $D.4$ 解：$D$。请注意的是$GBN$是累计确认的，所以最后收到了$3$号帧的确认代表$0$、$1$、$2$、$3$号帧都确认收到了，没有收到$1$号的确认也无所谓，所以这时候就应该从$4$号帧开始重发，所以是$D$。 **例题** 两台主机之间的数据链路层采用后退$N$帧协议（$GBN$）传输数据，数据传输速率为$16kb/s$，单向传播时延为$270ms$，数据帧长度范围是$128\sim512$字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序列的比特数至少为()。 $A.2$    $B.3$    $C.4$    $D.5$ 解：$C$。已知数据帧长度范围是$128\sim512$字节，所以数据帧长度是不确定的，而要保证信道使用率最高，所以按最小数据帧长度计算（因为单向传播时延固定下，越大的数据帧信道利用率越高）。 一帧发送所需要的时间为$128\times8/(16\times10^3)=64ms$，而发送一帧到确认该帧一共需要$64+270\times2+64=668ms$，这个时间段内可以传输$668/64=10.4$帧，所以至少需要$4$为比特进行编号（$2^4=16>10.4$）。 **例题** 主机甲与主机乙之间使用后退$N$帧协议传输数据，甲的发送窗口尺寸为$1000$，数据帧长为$1000$字节，信道带宽为$100Mb/s$，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲、乙之间的单向传播时延是$50ms$，则甲可以达到的最大平均数据传输速率约为()。 $A.10Mb/s$ $B.20Mb/s$ $C.80Mb/s$ $D.100Mb/s$ 解：首先是求最大的平均数据传输速率。已知题目中已经给出了一个速度$100Mb/s$，这是带宽即最大传输速度。实际的最大传输速率不会超过这个速度。 首先要计算出一个帧在收到确认帧的整个发送周期。首先$1000$字节，信道带宽为$100Mb/s$，即发送时延为$1000\times8=8000bit\div100Mb/s=0.00008s$，所以一共需要$50ms\times2+0.00008s=0.10008s$，即一个帧完成传输需要$0.10008s$$。 此时这个周期内由于使用后退$N$帧协议，所以可以传输$0.10008s\times100Mb/s=10008000b$个数据，即$10008000\div8000=1251$组，即这个时间段能发送$1251$个帧，但是实际上发送窗口为$1000$即最多只能发送$1000$个帧，达不到$100Mb/s$的带宽满值。 实际能达到的速率为$1000\times1000\times8\div0.10008s\approx80MB/s$。 **例题** 假定卫星信道的数据率为$100kb/s$，卫星信道的单程传播时延为$250ms$，每个数据帧的长度均为$2000$位，并且不考虑误码、确认帧长、头部和处理时间等开销，为达到传输的最大效率，试问帧的顺序号应为多少位，此时信道利用率是多少。 解：首先卫星信道的单程传播时延为$250ms$，所以$RTT=250\times2=500ms=0.5s$。 而一个帧的发送时间等于$2000bit/(100kb/s)= 20\times10^{-3}s$。 一个帧发送完后经过一个单程时延到达接收方，再经过一个单程时延发送方收到应答，从而可以继续发送，因此要达到传输效率最大，就是不用等确认也可继续发送帧，这就要求一个单程上不断发送帧。 设窗口值等于$x$，令$2000bit\times x/(100kb/s)= 20×10^{-3}s+RTT=20×10^{-3}s+0.5s=0.52s$。 得$x=26$。要取得最大信道利用率，窗口值是$26$即可，因为在此条件下，可以不间断地发送帧，所以发送速率保持在$100kb/s$。 由于$16<26<32$，帧的顺序号应为$5$位。在使用后退N帧$ARQ$的情况下（选择重传协议信道利用率只用后退$N$帧协议的差不多一半），最大窗口值是$31$，大于$26$，可以不间断地发送帧，此时信道利用率是$100\%$。 **例题** 甲乙双方均采用后退$N$帧协议（$GBN$）进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为$1000B$。$S_{x,y}$和$R_{x,y}$分别表示甲方和乙方发送的数据帧，其中$x$是发送序号，$y$是确认序号（表示希望接收对方的下一帧序号），数据帧的发送序号和确认序号字段均为$3$比特。信道传输速率为$100Mb/s$，$RTT=0.96ms$。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中$t$为初始时刻，此时甲方的发送和确认序号均为$0$，$t_1$时刻甲方有足够多的数据待发送。请回答下列问题。 1）对于图($a$)，$t_0$时刻到$t_1$时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少？正确接收的是哪几个帧（请用$S_{x,y}$形式给出）？ 2）对于图($a$)，从$t_1$时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个（请用$S_{x,y}$形式给出）？ 3）对于图($b$)，从$t_1$时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧？重发的第一个帧是哪个帧（请用$S_{x,y}$形式给出）？ 4）甲方可以达到的最大信道利用率是多少? ![ab图][ab] 解：双方始终采用捎带确认，表示上一帧的确认帧在本次的数据帧上。数据帧的发送序号和确认序号字段均为$3$比特，在后退$N$帧协中，发送窗口最大为$2^3-1=7$。 1）由于使用累计确认，所以最开始的$R_{0,1}$就表示第一个确认帧（序号为$0$，确认了$0$，期待$1$），在最后发送的$R_{3,3}$表示希望确认$3$号，所以前面的$S_{0,0}$、$S_{1,0}$、$S_{2,0}$一共$3$个帧全部接收确认了。（$R_{2,3}$丢失了） 2）已知一共可以发送$0\sim7$号帧。由于$t_1$此时已经根据$R_{3,3}$确认了$2$号帧成功接收，还可以发$8-3=5$个，已经发送了$S_{4,1}$，所以第一个发送的是$S_{5,2}$。然后依次发送$S_{6,2}$，$S_{7,2}$，然后开始新的序号$S_{0,2}$，$S_{1,2}$，一共$5$个。 3）由于$t_1$时$S_{2,0}$超时，由于收到乙$R_2$帧，所以重发的的确认号为$3$，所以甲方开始重传$2$号帧以及之后的帧，即$S_{2,3}$后面的三个帧。 4）基本公式还是周期数据量除以周期时长。发送窗口为$2^3-1=7$，即同一趟内最多可以同时发送$7$个数据，所以每趟内用于传输数据的时间为$7\times\dfrac{8\times1000}{100\times10^6}$。 由于使用捎带确认，所以发送确认帧的时间就等于发送数据帧的时间，即$2\times\dfrac{8\times1000}{100\times10^6}$，因为计算是一趟，而不是一个周期，还要加上一个$RTT$。 所以总共$\dfrac{7\times\dfrac{8\times1000}{100\times10^6}}{0.96\times10^{-3}+2\times\dfrac{8\times1000}{100\times10^6}}=50\%$。 ### 选择重传协议 $k$位比特编号最大接受窗口为$2^{k-1}$，即一半。 **例题** 数据链路层采用了$SR$协议，发送方已经发送了编号为$0$到$3$的帧，若发送方只收到了$1$号帧的确认，$0$、$2$号帧依次超时，则发送方需要重新发送的帧数为（）。 $A.0$    $B.1$    $C.2$    $D.3$ 解：$C$。请注意的是$SR$是单独确认的，所以收到了$1$号帧的确认，而$0$，$2$号超时，代表这两个需要重传，所以是$C$。 **例题** 对于滑动窗口协议，若分组序号采用$3$比特编号，发送窗口大小为$5$，则接收窗口最大是()。 $A.2$ $B.3$ $C.4$ $D.5$ 解：$B$。滑动窗口协议又分为两种后退$N$帧协议与选择重传协议，其中后退$N$帧协议接收窗口为$1$，而选择重传协议中滑动窗口数量为$2^3=8$，所以接收窗口最大为$8-5=3$。 **例题** 对无序接收的滑动窗口协议，若序号位数为$n$，则发送窗口最大尺寸为()。 $A.2^n-1$ $B.2n$ $C.2n-1$ $D.2^{n-1}$ 解：$D$。虽然没有明确给出哪个协议，但是可以根据无序接收知道这个指选择重传协议。所以选$D$。 **例题** 在选择$ARQ$协议中，设编号用$3bit$，发送窗口$W_T=6$，接收窗口$W_R=3$。试找出一种情况，使得在此情况下协议不能正确工作。 解：对于选择重传协议，接收窗口和发送窗口的尺寸需满足：接收窗口尺寸$W_R$＋发送窗口尺寸$W_T\leqslant2^n$，而题目中给出的数据是$W_R+W_T=9\leqslant2^3$，所以是无法正常工作的。 举例如下： 发送方：$01234567012345670$。 接收方：$01234567012345670$。 发送方发送$0\sim5$号共$6$个数据帧时，因发送窗口已满，发送暂停。接收方收到所有数据帧，对每个帧都发送确认帧，并期待后面的$6$、$7$、$0$号帧。若所有的确认帧都未到达发送方，经过发送方计时器控制的超时时间后，发送方再次发送之前的$6$个数据帧，而接收方收到$0$号帧后，无法判断是新的数据帧还是旧的重传的数据帧。 **例题** 在数据传输速率为$50kb/s$的卫星信道上传送长度为$1kbit$的帧，假设确认帧总由数据帧捎带，帧头的序号长度为$3bit$，卫星信道端到端的单向传播延迟为$270ms$。对于下面三种协议，信道的最大利用率是多少。 1）停止-等待协议。 2）后退$N$帧协议。 3）选择重传协议（假设发送窗口和接收窗口相等）。 解：最大信道利用率即每个传输周期内每个协议可发送的最大帧数。由题意，数据帧的长度为$1kbit$，信道的数据传输速率为$50kb/s$，因此信道的发送时延为$1/50s =0.02s$，另外信道端到端的传播时延$0.27s$。本题中的确认帧是捎带的（通过下一个数据帧来传送），因此每个数据帧的传输周期为$(0.02+0.27+0.02+0.27)s=0.58s$, 1）在停止-等待协议中，发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧.接收方每接收一帧，都要反馈一个应答信号，表示可接收下一帧。其中用于发送数据帧的时间为$0.02s$。因此，信道的最大利用率为$0.02/0.58= 3.4\%$。 2）在后退$N$帧协议中，接收窗口尺寸为$1$，若采用$n$比特对帧编号，则其发送窗口的尺寸$W$满足$1