【计算机网络】3数据链路层①

这篇笔记专门讲数据链路层的功能。

2.功能

数据链路层的主要任务是让帧在一段链路上或一个网络中传输。

2.1.封装成帧（组帧）

解决的问题：①帧定界②帧同步③透明传输

实现组帧的方法通常有以下种。

2.1.1.字符计数法

原理：在每个帧开头，用一个定长计数字段来记录该帧所含的字节数（包含计数字段自身所占用的字节）。

问题：任何一个计数字段出错，都会导致后续所有帧无法定界。

2.1.2.Byte填充法

原理：使用特定字节来定界一帧的开始与结束。控制字符表示帧的开始；控制字符表示帧的结束。

信息位中如果出现特殊字符（控制字符，控制字符，转义字符），则发送方要在转义字符之前填充一个转义字符来加以区分，接收方要做逆处理。

2.1.3.0bit填充法

在数据链路层早期使用的协议中，便是采用这种比特填充的首尾标志法来实现透明传输的。

原理：零比特填充法允许数据帧包含任意个数的比特。它使用一个特定的比特串来标志一帧的开始和结束。

为了不使数据字段中出现的比特流被误判为帧的首尾标志，需要对数据部分做一些处理：发送方需要对帧的数据部分进行处理，每当遇到连续个，就填充个；接受方需要对帧的数据部分进行逆处理，每当遇到连续个，就删掉后面的。

2.1.4.违规编码法

在物理层进行比特编码时，常采用违规编码法。

局域网 标准就采用了这种方法。

原理：使用“违规信号”，表示帧的开头、结尾。

例如，采用曼彻斯特编码时，使用“中间不跳变”作为“违规信号”，标记帧的开头、结尾。

2.2.差错控制

差错控制的目标是发现并解决一个帧内部的“位错”。

这里的“位错”指的是比特差错（传输差错中的一种），即比特在传输过程中可能产生差错，可能变成，也可能变成。

---

常利用编码技术进行差错控制。

差错控制机制	编码技术（实现差错控制机制的具体技术方法）
自动重传请求（Automatic Repeat reQuest,ARQ）：当接收方检测到差错时，就设法通知发送方重发，直到收到正确的数据为止。	检错编码
向前纠错（Forword Error Correction,FEC）：接收方不但能发现差错，而且能确定错误的位置并加以纠正。	纠错编码

2.2.1.检错编码

检错编码都采用冗余编码技术，核心思想是在信息位（帧的“数据部分”）被发送前，按某种关系附加一定的校验位（为了给帧的“数据部分”检错/纠错而附加的一些冗余比特，在信息位的首部或尾部添加），构成一个符合某一规则的码字后发送。

当要发送的有效数据变化时，相应的冗余位也随之变化，使得码字遵从不变的规则。接收方根据收到的码字是否仍符合原规则来判断是否出错。常见的检错编码有奇偶检验码和循环冗余码。

奇偶校验码是奇校验码和偶校验码的统称。

1️⃣组成

奇偶校验码由位信息位和位校验位组成。检验位的取值(或)将使整个检验码中的个数为奇数或偶数。

2️⃣约定

发送方和接收方先共同约定是采用奇校验还是偶校验。

3️⃣发送方求校验位

奇校验码：附加一个检验位后，位的码字中的个数为奇数。

偶校验码：附加一个检验位后，位的码字中的个数为偶数。

4️⃣接收方检错

如果发送方和接收方共同约定采用奇校验的规则，那么接收方的数据链路层收到帧之后会检查这个帧的校验位和信息位里含有的是不是奇数个。如果是奇数个，就认为没有错误；如果不是奇数个，就认为有错误。

如果发送方和接收方共同约定采用偶校验的规则，那么接收方的数据链路层收到帧之后会检查这个帧的校验位和信息位里含有的是不是偶数个。如果是偶数个，就认为没有错误；如果不是偶数个，就认为有错误。

5️⃣硬件实现

在现实应用中，偶校验码要比奇校验码更常用，原因是偶校验很容易用简单的异或门实现。

偶校验的硬件实现：各信息进行异或(模加)运算，得到的结果即为偶校验位。

⊕：异或（模2加）    0 ⊕ 0 = 0       0 ⊕ 1 = 1        1 ⊕ 0 = 1          1 ⊕ 1 = 0

求偶校验位：

1⊕0⊕0⊕1⊕1⊕0⊕1=0  

1⊕0⊕1⊕0⊕1⊕1⊕1=1  

进行偶校验（所有位进行异或，若结果为1说明出错）：  

0⊕1⊕0⊕0⊕1⊕1⊕0⊕1=0

1⊕1⊕0⊕1⊕0⊕1⊕1⊕1=0   

1⊕1⊕0⊕1⊕0⊕1⊕1⊕0=1  （可以检测出奇数位错误）

1⊕1⊕0⊕1⊕0⊕1⊕0⊕0=0  （无法检测出偶数位错误）

6️⃣奇偶校验码仅能检测出奇数位错误，无纠错能力。

数据链路层广泛使用循环冗余码(Cyclic Redundancy Code,CRC)检错技术。

1️⃣循环冗余校验码由位信息位和位校验位组成。

2️⃣发送方和接收方先共同约定一个生成多项式(要求最低位必须为)

生成多项式可用位位串【除数】表示，位位串可视为阶数为的多项式的系数序列。

=信息码的长度

=生成式多项式最高次幂=

3️⃣发送方求校验位：生成

发送方基于待发送的位信息位和，计算出位校验位（帧检验序列）。

---

信息码左移位，低位补。

对移位后的信息码，用生成多项式进行模除法，产生余数。

由于除数有位，所以我们会取被除数的高位与除数先“商”一次。

模除法取商的方式比较特别，我们只看被除数的最高位，如果是，就先商。

之后再对后位进行模减（效果与模加相同）的运算，得到余数。

再将被除数的后面一位补到余数的低位。此时的余数最高位是，商。

以此类推。

最后得到的余数为校验位。

对应的码为

4️⃣接收方检错：检验

接收方收到数据和冗余码后，通过来计算收到的数据和冗余码是否产生差错。

收到位数据，与生成多项式模除，计算位余数。

余数为，说明无错误；余数非，说明出错。

---

发送：        记为

接收：        用进行模除，余数为，代表没有出错。

接收：        用进行模除，余数为，代表可能是出错。

5️⃣检错纠错能力

①可检测出所有奇数个错误；

②可检测出所有双比特的错误；

③可检测出所有小于等于校验位长度的连续错误；

④若选择合适的生成多项式，且，则可纠正单比特错。

对于确定的生成多项式，出错位与余数是相对应的。

---

为什么叫循环冗余码？

因为将模除对应的位串，会发现得到的余数在循环。

---

循环冗余码(CRC)是具有纠错功能的，只是数据链路层仅使用了它的检错功能，检测到帧出错则直接丢弃，是为了方便协议的实现，因此本节不介绍CRC的检错功能。 

2.2.2.纠错编码

海明校验码

奇偶校验码只有个校验位，只能携带种状态信息(对/错)。

海明码有多个校验位，能携带多种状态信息(对/错，错在哪)

海明码的设计思路是将信息位分组进行偶校验→多个校验位→多个校验位标注出错位置

1️⃣确定海明码的位数

设为有效信息的位数，为检验位的位数，则信息位和检验位应满足

海明码位数 成立，则满足条件。

设信息位为，共位；检验位为，共位；

对应的海明码为 。

2️⃣确定检验位的分布

规定检验位在海明位号为的位置上，其余各位为信息位，因此有：

的海明码位号为 ，即为。

的海明码位号为，即为。