---

前言

本文的主要内容是计算机网络中数据链路层的一些基础知识，包括数据链路层功能概述、封装成帧中组帧的四种方法、差错控制中的检错编码和纠错编码、流量控制与可靠传输机制中的停止等待协议、后退 N 帧协议以及选择重传协议。

---

一、数据链路层功能概述

结点：主机、路由器。
链路：网络中两个结点之间的物理通道，链路的传输介质主要有双绞线、光纤和微波。链路分为有线链路和无线链路。
数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路。
帧：链路层的协议数据单元，封装网络层数据报。
数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。
数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层的数据可靠地传输到相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
数据链路层的功能主要有：①为网络层提供服务。无确认无连接服务(通常用在实时通信、误码率比较低的通信信道中)，有确认无连接服务(通常用在无线通信、误码率比较高的通信信道中)，有确认面向连接服务(有连接的一定是有确认的)；②链路管理，即连接的建立、维持、释放(用于面向连接的服务)；③组帧；④流量控制；⑤差错控制(帧错/位错)。

---

二、封装成帧

1、透明传输

***透明传输***指的是不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。
当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息，这样才能保证数据链路层的传输是透明的。

2、封装成帧

封装成帧***就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。首部和尾部包含许多的控制信息，它们的一个重要作用就是***帧定界，即确定帧的界限。
封装成帧的示意图如下图所示，需要注意的是，帧的数据部分有一个最大传送单元的限制。

帧同步指的是接收方能从接收到的二进制比特流中区分出帧的起始和终止。

3、组帧的方法

组帧的方法有：字符计数法、字符/节填充法、零比特填充法以及违规编码法。

⑴字符计数法

字符计数法的帧首部使用一个计数字段来标明该帧内的字符数，其示意图如下图所示。

这种方法的缺点是：如果某一帧内的计数字段出现错误，比如错将 5 记成其他数字，那么后面的每一帧内容都会出现差错，即一错百错。

⑵字符/节填充法

当传送的帧是由文本文件(文本文件的字符都是从键盘上输入的，都是ASCII码)组成时， 不管从键盘上输入什么字符都可以放在帧里传过去，即实现透明传输，接收端会根据帧的开头字段和结束字段收到发送端的原本数据而不发生差错，如下图所示。

当传送的帧是由非ASCII码的文本文件组成时，比如是二进制代码的程序或图像等，这个时候帧中的数据可能会有和传输结束标志位(图中的 00000100)一样的段，从而导致帧提前结束，传输发生错误，这种情况如下图所示。

如果是上面的这种情况就要采用字符填充的方法来实现透明传输，字符填充法的具体过程如下图所示。

字符填充法就是在所传输的帧数据中找到与开始段、结束段以及转义字段相同的字段，并在其前加转义字段(上图中的 00011011)，这样在传输的过程中就不会发生错误，而接收端收到帧数据后会剔除掉多余的转义字段，得到与开始帧数据相同的内容。

⑶零比特填充法

零比特填充法中的开始标志位和结束标志位一致，这样仍然有可能在帧数据中出现与其相同的字段，如下图所示。

零比特填充法是这样实现的：在发送端，扫描整个信息字段，只要有连续5个1，就立即填入1个0；在接收端收到一个帧时，先找到标志字段确定边界，再用硬件对比特流进行扫描，发现连续5个1时，就把后面的0删除。
一个零比特填充法的例子如下图所示。

零比特填充法保证了透明传输，在传送的比特流中可以传送任意比特组合，而不会引起对帧边界的判断错误。

⑷违规编码法

前面已经提到过曼彻斯特编码方式，假如用前高后低表示1，前低后高表示0，如下图所示。

由于“高高”和“低低”的在该序列中不会出现，因此可以用“高高”、“低低”来定界帧的起始和终止。
以上提到的四种方法中，字节计数法的计数字段比较脆弱，字符填充法实现比较复杂以及其不兼容性，目前较普遍使用的帧同步法是零比特填充法和违规编码法。

---

三、差错控制

1、差错由来

传输中的差错都是由于噪声引起的。
从全局性来说，由于线路本身电气特性所产生的随机噪声(热噪声)是信道固有的，它是随机存在的，其解决办法就是通过提高信噪比来减少或避免干扰，而提高信噪比就需要对传感器的一些硬件设置或参数做改动。
从局部性来说，外界特定原因所造成的短暂冲击噪声是产生差错的主要原因，其通常是利用编码技术来解决的。
差错分为位错和帧错两种。位错就是比特位出错，也就是在传输过程中1变成0或者0变成1的错误。帧错又包括帧丢失、帧重复和帧失序。
差错控制在数据链路层实现的原因是：早发现，早丢弃，避免将差错的数据传送到接收方再丢弃，这样会耗费资源。

2、检错编码

数据链路层的编码和物理层的数据编码与调制不同。物理层编码针对的是单个比特，解决传输过程中比特的同步等问题，如曼彻斯特编码；数据链路层的编码针对的是一组比特，它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。
检错编码包括奇偶校验码和循环冗余码。

⑴奇偶校验码

奇偶校验码分为奇校验码和偶校验码，一个 n 位的奇/偶校验码由 n-1 位信息元和一位校验元组成，如下图所示。

上图中的校验元 x 可以为 0，也可以为 1，x 是 1 还是 0 取决于 n-1 位信息元中 1 的个数以及所采用的的方式是奇校验码和偶校验码。
举例：如果一个字符 S 的 ASCII 编码从低到高依次为 1100101，采用奇校验，在下述收到的传输后字符中，哪种错误不能检测？
A. 11000011 B. 11001010 C. 11001100 D. 11010011
分析：字符 S 的 ASCII 编码为 1100101，其中 1 的个数为 4，但题目说采用奇校验，因此校验元应该设为 1，所以奇校验码为 11100101，上面选项中只有 D 选项中有 5 个1，因此，这种错误无法检测，故选 D。
奇偶校验码的特点是只能检查出奇数个比特错误，其检错能力为50%。
如果只有1个或奇数个比特位发生错误，那是可以通过奇偶校验码检测出来的，但若是有偶数个比特位发生错误，通过奇偶校验码是检测不出来的，因为偶数个位发生错误后，1 的个数相较于原序列没有变化。

⑵循环冗余码

冗余编码指的是在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某种规则的码字后再发送，当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则，接收端根据收到码字是否仍符合原规则，从而判断是否出错。
循环冗余码的思想如下图所示。

发送端发送的数据就是要传的数据加上冗余码(FCS检验序列)。
接收端检错的过程：把收到的每一个帧都除以同样的除数，然后检查得到的余数R。若余数为0，判定这个帧没有差错，接受；若余数为不为0，判定这个帧有差错，但无法确定到位，丢弃该帧。
FCS 的生成以及接收端循环冗余码检验都是由硬件实现，处理很迅速，因此不会延误数据的传输。
在数据链路层仅仅使用循环冗余检验差错只能做到对帧的无差错接收，也就是说，凡是接收端数据链路层接收的帧，我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错。接收端丢弃的帧虽然曾收到了，但是最终还是因为有差错被丢弃，所以凡是接收端数据链路层接收的帧均无差错。
计算冗余码的步骤：①加0，假设生成多项式G(x)的阶为 r(多项式为 N 位，则阶数为 N-1)，则加 r 个 0；②模2除法数据加0后除以生成多项式，余数为冗余码(FCS检验序列)。
举例：要发送的数据是 1101011011，采用CRC校验，生成多项式是10011，那么最终发送的数据应该是？
解答：10011 表示成多项式为：$x^4+x^1+x^0$ = $x^4+x+1$ 因此阶数为4，原序列补 4 个 0，即 11010110110000，然后用 11010110110000 和生成多项式 10011相除，每次除完后做异或运算，如下图所示。

得到的最终发送数据为 11010110111110。
注意：在模2除法中，即使划定的几位比被除数小，只要首位是1，任然商1。比如上例中的10011÷11010时也要商1，然后做异或运算。
然后在接收端进行检错，如下图所示。

得到的最终余数为 0，因此没有差错，接收。

3、纠错编码——海明码

纠错编码使用的是海明码，海明码可以发现双比特错，但是只能纠正单比特错。
海明码的工作流程：确定校验码的位数 r—>确定校验码和数据的位置—>求校验码的值—>检错并纠错。
①确定校验码的位数 r
海明不等式：$2^r$-1 ≥ k + r ，其中 k 为信息位，r 为冗余信息位。
比如要发送的数据是 D=101101，则 k = 6，满足不等式的最小的 r 的值为4，即校验码的位数为 4。
②确定校验码和数据的位置
总的数据位数 = 校验码的位数 + 原数据的位数
校验码的位置只能在第 $2^n$ (n=0,1… 但 $2^n$ ≤ 总的数据位数)位上，数据按照顺序插空就行。
还是用上面的例子，已经求得校验码的位数为 4，原数据位数为 6，合在一块就是10位，其摆放的位置如下图所示。

③求校验码的值
校验码值的求法：我们已经知道校验码的位置只能在第 $2^n$ (n=0,1… 但 $2^n$ ≤ 总的数据位数)位上，因此校验码位置所对应的二进制不管是由几位构成，其中只有 1 位是 1(如：0001、0010、0100、1000等)，假设某校验码位置对应的二进制中 1 的位置是第 2 位，那么在所有数据中找到第 2 位为 1 的这些数据，和该校验位异或，并令其值为 0，然后就能求出该校验位的值。具体的求解过程如下图所示。

最终数据 101101 所对应的海明码为 0010011101。
④检错并纠错
检错和求校验码值左边的式子相同，而等式右边不再是 0，而是根据现有序列求得的值，依次求出所有值后，按照逆序写出各等式右边的值，将其转化为十进制就是对应出错的位置，如果没有出错，那么等式右边的值都是 0，对应的十进制也是 0。
纠错很简单，如果检错后发现没错，自然不必纠错，若有错，根据检错结果也知道出错的位置，将该位置的二进制取反即可(1变0或者0变1)。
具体的检错过程如下图所示。

---

四、流量控制与可靠传输机制

较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制是数据链路层的一项重要工作。
数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。
数据链路层流量控制手段：接收方收不下就不回复确认。
传输层流量控制手段：接收端给发送端一个窗口公告。
流量控制的方法有：停止等待协议、后退 N 帧协议(GBN)和选择重传协议(SR)，其中后退 N 帧协议和选择重传协议属于滑动窗口协议。
停止等待协议的发送窗口大小为 1，接收窗口大小也为 1；后退 N 帧协议的发送窗口大小大于 1，接收窗口大小为 1；选择重传协议的发送窗口大小大于 1，接收窗口大小也大于 1。
滑动窗口解决的就是流量控制和可靠传输(发送方自动重传)的问题。

1、停止等待协议

除了比特出差错，底层信道还会出现丢包问题。
丢包就是指由于物理线路故障、设备故障、病毒攻击、路由信息错误等原因导致数据包的丢失。数据包就是一段数据，它在不同层有不同的名字，在链路层叫做帧，在网络层叫做 IP 数据报或者分组，在传输层叫做报文段。
停止等待协议的出现就是为了解决丢包问题和实现流量控制。
研究停止等待协议的前提：虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据，一方接收数据；因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的；停止等待就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。
停等协议的应用情况分为无差错情况和有差错情况。
无差错情况如下图所示。

由于这种情况下每发送一个数据帧就停止并等待，因此用 1 bit 编号就够了。
有差错情况的情况分为数据帧丢失、确认帧丢失以及确认帧迟到。
①数据帧丢失
数据帧丢失的情况如下图所示。

在传送帧的过程中会设置超时计时器，每次发送一个帧就启动一个计时器，而且超时计时器设置的重传时间应当比帧传输的平均 RTT (帧传输的往返时间)更长一些。超时计时器到时后仍然没能收到确认帧的信号，则会重传刚才传过的帧。
需要注意的是：每发完一个帧后，必须保留它的副本(如果重传的话就会用到)；数据帧和确认帧必须编号(避免发送出错和接收出错)。
②确认帧丢失
确认帧丢失指的是接收方收到了帧数据但确认帧在回传的时候丢失了，这样在超时计时器到时后不会收到确认帧的信号，因此会重传该帧，如下图所示。

这种情况下需要注意的是，在接收端收到了两个重复的帧，因此要丢弃重复的一帧。
③确认帧迟到
确认帧迟到指的是在超时计时器到时后没能接收到该确认帧，但在传其他帧的过程中收到了迟到的该确认帧，如下图所示。

这种情况下就要将迟到的确认帧丢弃，因为该帧的数据帧和确认帧已经传输成功了。
停止等待协议的优点是实现简单，缺点是信道利用率太低，信道利用率的计算示意图如下图所示。

信道利用率就是发送方在一个发送周期内有效地发送数据所需要的时间占整个发送周期的比率。
信道利用率 = $\frac{L/C}{T}$ ，其中 T 表示发送周期，也就是从开始发送数据到收到第一个确认帧为止的这段时间；L 表示时间 T 内发送的比特数据；C 表示发送方数据传输率。
信道吞吐率 = 信道利用率 × 发送方的发送速率
例题：一个信道的数据传输率为4 kb/s，单向传播时延为30ms，如果使停止等待协议的信道最大利用率达到80%，则要求的数据帧长度至少为多少？
解答：在公式 信道利用率 = $\frac{L/C}{T}$ 带入数据
即 80% = $\frac{L/4000}{L/4000+2\times 0.03}$ ，得到 L = 960 bit
因此数据帧长度至少为960 bit。

2、后退 N 帧协议(GBN)

停止等待协议下信道利用率太低，因此就出现了像下图所示的流水线技术。

在上图所示的这种情况下就需要满足：必须增加序号范围；发送方需要缓存多个分组。
滑动窗口中的发送窗口：发送方维持一组连续的允许发送的帧的序号。
滑动窗口中的接收窗口：接收方维持一组连续的允许接收帧的序号。
后退 N 帧协议中发送与接收数据的具体过程如下图所示。

后退 N 帧协议中发送方必须响应的三件事：
①上层的调用。上层(这里一般是网络层)要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送；如果窗口已满，发送方只需将数据返回给上层，暗示上层窗口已满，让上层等一会再发送。但是实际实现中，发送方可以缓存上层要求发送的这些数据，等到窗口不满时再发送帧。
②收到了一个确认帧(ACK)。GBN协议中，对 n 号帧的确认采用累积确认的方式，标明接收方已经收到 n 号帧和它之前的全部帧。
③超时事件。协议的名字为后退 N 帧/回退 N 帧，其来源于出现丢失和时延过长帧时发送方的行为，就像在停止等待协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧。
后退 N 帧协议中接收方做的事： 如果正确收到 n 号帧并且其按序排列，那么接收方为 n 帧发送一个确认帧(ACK)，并将该帧中的数据部分交付给上层。 其余的情况都丢弃帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任何失序帧，只需要维护一个信息：expectedseqnum(接收方期待接收的下一帧，比如0，1帧已经收到，下一个期待的帧就是2，但是迟迟没有接收到2帧，反而接收到了3帧，此时expectedseqnum = 2，然后丢弃3帧让发送方重传2帧及之后的帧)。
后退 N 帧协议发送接收的具体流程如下图所示。

发送窗口的尺寸限制：若采用 n 个比特对帧编号，那么发送窗口的尺寸$W_T$应满足：1 ≤ $W_T$ ≤ $2^n-1$，因为发送窗口尺寸过大，就会使得接收方无法区别新帧和旧帧，从而产生二义性。
比如采用 2 个比特对帧编号，则发送窗口的尺寸 1 ≤ $W_T$ ≤ 3，如果采用 4 窗口，即用 0，1，2，3 ，0，1，2，3 ……编号，如果从头开始的确认帧全部丢失，等到超时计时器到时后重传数据帧时就无法区分了。
后退 N 帧协议中的重点：累积确认，偶尔捎带确认，捎带确认指的是接收方给发送方发数据的时候捎带上确认帧； 接收方只按顺序接收帧，如果不按序则丢弃；确认序列号最大的、按序到达的帧；发送窗口最大为$2^n-1$，接收窗口大小为1。
后退 N 帧协议的优点：因连续发送数据帧而提高了信道利用率。
后退 N 帧协议的缺点：在重传时必须把原来已经正确传送的数据帧重传，使得传送效率降低。
例题：数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是()。
A. 2 B. 3 C. 4 D. 5
解答：接收方可以隔一段时间发送一个确认帧，没必要每一个都发送确认帧，因为它是累计确认的，该题中发送方接收到的最大确认帧是3号帧，因此只需要重发的帧是3号帧后面的 4、5、6、7号帧，故选 C。

3、选择重传协议(SR)

上面提到的后退 N 帧协议的缺点是它会批量重传，对于有些接收到的帧也要丢弃重传。那么可不可以只重传一些出错的帧呢？对于该问题的解决办法就是设置单个确认，同时加大接收窗口，设置接收缓存，缓存一些乱序到达的帧。
选择重传协议中发送方与接收方的示意图如下图所示。

选择重传协议中发送方必须响应的三件事：
①上层的调用。从上层收到数据后，选择重传协议发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧，否则就像后退 N 帧协议一样，要么将数据缓存，要么返回给上层之后再传输。
②收到了一个确认帧。如果收到确认帧，假如该帧的序号在窗口内，则选择重传协议发送方将那个被确认的帧标记为已接收；如果该帧序号是窗口的下界，也就是最左边的第一个窗口对应的序号，则窗口向前移动到具有最小序号的未确认帧处；如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧。
一个例子如下图所示，其中绿色的块表示已经传输成功且收到确认帧，橙色的块表示已发送还未收到确认帧，白色的块表示还未发送的数据帧。

③超时事件。每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。
选择重传协议中接收方做的事： 选择重传协议中接收方将确认一个正确接收的帧而不管其是否按序，失序的帧将被缓存，并返回给发送方一个该帧的确认帧，直到所有帧(序号更小的帧)皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前移动滑动窗口。
选择重传协议中接收方做的事的示意图如下图所示。

选择重传协议发送接收的具体流程如下图所示。

滑动窗口的尺寸限制：发送窗口最好等于接收窗口，因为发送窗口过大会产生溢出，小了没意义。若采用 n 个比特对帧编号，发送窗口等于接收窗口的大小，即 $W_{Tmax}$ = $W_{Rmax}$ = $2^{n-1}$。
滑动窗口设置过大会导致无法判断要发送的是新的帧还是旧的帧，如下图所示。

如果滑动窗口的大小设置合适就不会发生这种情况，如下图所示。

选择重传协议中的重点：对数据帧逐一确认，并且收到一个确认一个； 只重传出错帧；接收方有缓存(对于已经收到的帧且其前面还有没收到的帧，这些帧就会放进缓存)；发送窗口与接收窗口的大小相等，即 $W_{Tmax}$ = $W_{Rmax}$ = $2^{n-1}$。
例题：数据链路层采用了选择重传协议，发送方已经发送了编号为0~3的帧。现已收到1号帧的确认，而0、2号帧依次超时，则发送方需要重传的帧数是()。
A. 2 B. 3 C. 4 D. 5
解答：由于只收到了1号帧的确认，且3号帧的情况现在为止(可能已经在传输的过程中)，而0、2号帧依次超时，故需要重传的帧数是2，选择 A 。

---

总结

以上就是计算机网络——数据链路层功能概述、封装成帧、差错控制、流量控制与可靠传输机制的所有内容了，本文的重点内容是组帧的四种方法、检错编码和纠错编码、停止等待协议、后退 N 帧协议以及选择重传协议。
参考视频：
数据链路层功能概述
封装成帧和透明传输
差错控制检错编码
差错控制纠错编码
流量控制与可靠传输机制
停止等待协议
后退 N 帧协议
选择重传协议