数据链路层基础概念

数据链路层概述

数据链路层是 OSI 参考模型中的第二层，位于物理层之上、网络层之下。它的核心任务是在相邻节点之间（即通过物理链路直接连接的两个节点之间）实现可靠、高效的数据传输。

物理层只负责传输原始的比特流，不关心比特的含义和结构。数据链路层则将比特流组织成帧（Frame），并通过差错控制、流量控制等机制，将一条可能出错的物理链路，改造为对网络层看起来无差错的数据链路。

数据链路（Data Link）

当一条物理链路加上实现数据传输协议的硬件和软件后，就构成了一条数据链路。数据链路是逻辑概念，而物理链路是物理概念。

数据链路层的主要功能

1. 组帧（Framing）

将网络层交下来的 IP 数据报（分组），按照一定的格式封装成帧，在帧的首部和尾部添加控制信息，使接收方能从收到的比特流中准确地识别出帧的开始和结束。

组帧需要解决的核心问题是：如何让接收方从连续的比特流中正确区分出一帧的边界？

2. 差错控制（Error Control）

由于物理链路存在噪声和干扰，比特在传输过程中可能发生错误（0 变 1 或 1 变 0）。差错控制包括：

检错（Error Detection）：发现传输中是否出现了错误
纠错（Error Correction）：不仅发现错误，还能自动纠正错误

常见的检错编码有奇偶校验码和循环冗余校验（CRC），常见的纠错编码有海明码。

3. 流量控制（Flow Control）

控制发送方的发送速率，使之不超过接收方的接收和处理能力，防止接收方缓冲区溢出导致数据丢失。常用的机制是滑动窗口协议。

4. 可靠传输（Reliable Transmission）

通过确认（ACK）和重传（Retransmission）机制，确保数据正确、有序地到达接收方。当帧出错或丢失时，发送方会重新发送。

注意：并非所有数据链路层协议都提供可靠传输。例如以太网就不提供可靠传输服务，它将可靠传输的责任交给了上层（TCP）。而 PPP、HDLC 等协议则提供可靠传输。

5. 介质访问控制（Medium Access Control, MAC）

当多个节点共享同一条广播信道时（如以太网），需要规定节点如何访问信道，避免冲突。这就是介质访问控制子层（MAC 子层）的职责。

组帧方法

组帧的关键是在帧的开始和结束处添加特殊的标记，使接收方能识别帧边界。常用的组帧方法有四种。

1. 字节计数法（Character Count）

在帧的首部使用一个字段来标明帧内的字节数。接收方通过读取这个计数字段，就能知道帧有多长，从而确定帧的结束位置。

优点：简单，不需要填充缺点：如果计数字段本身在传输中出错，接收方将无法正确识别帧边界，导致后续所有帧都错位（帧同步丢失）

这种方法曾用于 DECNET 的 DDCMP 协议。

2. 字符填充法（Character Stuffing）

使用特殊的控制字符作为帧的开始和结束标记。例如：

FLAG（标志字节，如 0x7E）作为帧的定界符
当数据中出现与 FLAG 相同的字节时，在其前面插入一个转义字符 ESC（如 0x7D）
如果数据中出现 ESC，则在其前面再插入一个 ESC

接收方收到 ESC 后，就知道下一个字节是数据而非控制字符，然后删除 ESC。

优点：能从错误中恢复（重新找到 FLAG 即可重新同步）缺点：依赖特定的字符集，与字符编码耦合；填充和去填充增加了处理开销

这种方法用于早期的 BISYNC 协议和 PPP 协议（异步模式）。

3. 比特填充法（Bit Stuffing）

使用特殊的比特模式（如 01111110，即 6 个连续的 1）作为帧的定界标志。

发送方：在数据中，每当出现 5 个连续的 1 时，就在其后插入一个 0。这样数据中永远不会出现 6 个连续的 1。

接收方：每当收到 5 个连续的 1 时，检查下一个比特：

如果是 0，删除这个 0（还原数据）
如果是 1，说明这是帧定界标志（01111110）

比特填充法是目前应用最广泛的组帧方法，HDLC 和以太网都采用这种方法。它不依赖字符集，能从错误中快速恢复同步。

4. 违例编码法（Physical Layer Violations）

利用物理层编码中不使用的编码模式作为帧的定界符。例如在曼彻斯特编码中，每个比特中间都有跳变（高→低表示 1，低→高表示 0），而”无跳变”是违例的，可以用作帧的开始和结束标记。

优点：不需要填充，不影响数据缺点：依赖特定的物理层编码，通用性差

这种方法用于局域网（如 802.5 令牌环）。

差错控制

奇偶校验码（Parity Check）

奇偶校验是最简单的检错编码。在数据位后面附加一个校验位，使得整个码字（数据位+校验位）中 1 的个数为奇数（奇校验）或偶数（偶校验）。

奇校验：校验位使 1 的总数为奇数 偶校验：校验位使 1 的总数为偶数

例如，数据 1011001 中有 4 个 1：

奇校验：校验位为 1（4+1=5，奇数），码字为 10110011
偶校验：校验位为 0（4+0=4，偶数），码字为 10110010

接收方统计收到的码字中 1 的个数，如果不符合约定的奇偶性，就说明传输出错了。

检错能力：只能检测出奇数个比特错误，无法检测出偶数个比特错误。因此检错能力较弱，一般用于要求不高的场合（如 ASCII 码传输）。

循环冗余校验（Cyclic Redundancy Check, CRC）

CRC 是目前应用最广泛的检错编码，检错能力强，计算效率高，几乎所有现代网络协议（以太网、PPP、USB 等）都使用 CRC。

CRC 的基本思想

将待发送的数据看作一个多项式 $M(x)$ 的系数。选择一个生成多项式 $G(x)$ （收发双方事先约定），用 $G(x)$ 对 $M(x)$ 做模 2 除法，得到的余数 $R(x)$ 就是 CRC 校验码。将 $R(x)$ 附加在数据后面发送。

接收方用相同的 $G(x)$ 对收到的数据（含校验码）做模 2 除法，如果余数为 0，说明无差错；否则说明有差错。

CRC 的计算步骤

设数据为 $k$ 位，生成多项式 $G(x)$ 的阶为 $r$ （即 $G(x)$ 有 $r+1$ 位）：

左移：将数据 $M$ 左移 $r$ 位（即在数据末尾添加 $r$ 个 0），得到 $M \cdot 2^r$
模 2 除法：用 $G$ 对 $M \cdot 2^r$ 做模 2 除法（异或运算），得到 $r$ 位余数 $R$
附加：将余数 $R$ 附加在数据 $M$ 后面，得到发送的码字 $T = M \cdot 2^r + R$

模 2 除法的关键：减法就是异或（XOR），不借位。例如 $1011 \oplus 1101 = 0110$ 。

CRC 计算示例

题目：设数据 $M = 101001$ （6 位），生成多项式 $G(x) = x^3 + x^2 + 1$ ，即 $G = 1101$ （4 位， $r=3$ ），求 CRC 校验码。

解答：

数据左移 3 位： $M \cdot 2^3 = 101001000$
用 $G = 1101$ 做模 2 除法：

        110101      （商，不关心）
    ___________
1101|101001000
     1101
     ----
      1110
      1101
      ----
       0111
       0000
       ----
        1110
        1101
        ----
         0110
         0000
         ----
          1100
          1101
          ----
           001    （余数 R = 001）

余数 $R = 001$ ，即 CRC 校验码为 001
发送的码字： $T = 101001001$

接收方收到 101001001 后，用 1101 做模 2 除法，余数为 0，说明无差错。

常用的生成多项式

名称	生成多项式	应用
CRC-8	$x^8+x^2+x+1$	ATM
CRC-16	$x^{16}+x^{15}+x^2+1$	IBM SDLC
CRC-CCITT	$x^{16}+x^{12}+x^5+1$	X.25, V.41
CRC-32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$	以太网, ZIP

CRC 的检错能力：能检测出所有单比特错误、所有双比特错误、所有奇数个比特错误，以及所有长度不超过 $r$ 的突发错误。对于长度大于 $r$ 的突发错误，漏检率为 $2^{-r}$ 。CRC-32 的漏检率极低（约 $2^{-32}$ ），因此被广泛用于以太网等协议。

海明码（Hamming Code）

海明码是一种纠错编码，由 Richard Hamming 于 1950 年提出。它不仅能检测错误，还能纠正单比特错误。

基本原理

在数据位中插入若干校验位，每个校验位负责对某些位进行奇偶校验。当发生单比特错误时，多个校验组的校验结果会指向出错的位置，从而可以定位并纠正错误。

海明码的编码规则

设数据位为 $m$ 位，校验位为 $k$ 位，则需要满足：

$2^k \geq m + k + 1$

校验位放在位置为 2 的幂次方的位置（即第 1、2、4、8、… 位），数据位放在其余位置。

每个校验位 $P_i$ （位于位置 $2^{i-1}$ ）负责校验所有位置编号的二进制表示中第 $i$ 位为 1 的位。

海明码计算示例

题目：数据为 1011（4 位），求海明码。

解答：

确定校验位数： $m=4$ ，需要 $2^k \geq 4+k+1$ 。 $k=3$ 时 $2^3=8 \geq 8$ ，满足。故校验位 $k=3$ ，总位数 $n=4+3=7$ 。
位置安排（校验位在 1、2、4 位）：

位置	1	2	3	4	5	6	7
内容	P1	P2	D1	P3	D2	D3	D4
数据	?	?	1	?	0	1	1

计算校验位（偶校验）：
- $P_1$ （位置1）负责位置 1,3,5,7： $P_1 \oplus D_1 \oplus D_2 \oplus D_4 = 0$ ，即 $P_1 \oplus 1 \oplus 0 \oplus 1 = 0$ ， $P_1 = 0$
- $P_2$ （位置2）负责位置 2,3,6,7： $P_2 \oplus D_1 \oplus D_3 \oplus D_4 = 0$ ，即 $P_2 \oplus 1 \oplus 1 \oplus 1 = 0$ ， $P_2 = 1$
- $P_3$ （位置4）负责位置 4,5,6,7： $P_3 \oplus D_2 \oplus D_3 \oplus D_4 = 0$ ，即 $P_3 \oplus 0 \oplus 1 \oplus 1 = 0$ ， $P_3 = 0$
海明码为：0 1 1 0 0 1 1（位置1到7）

海明码的纠错

接收方收到码字后，对每个校验组进行校验，得到一个二进制数（称为校正因子）。如果校正因子为 0，说明无错；如果校正因子非 0，其值就是出错位的位置编号，将该位取反即可纠正错误。

例如，收到 0110011，若第 5 位出错变成 0110111：

校验组1（位置1,3,5,7）： $0 \oplus 1 \oplus 1 \oplus 1 = 1$ （出错）
校验组2（位置2,3,6,7）： $1 \oplus 1 \oplus 1 \oplus 1 = 0$ （正确）
校验组3（位置4,5,6,7）： $0 \oplus 1 \oplus 1 \oplus 1 = 1$ （出错）
校正因子 = $P_3 P_2 P_1 = 101_2 = 5$ ，即第 5 位出错，取反纠正。

典型例题

例题1：CRC 计算

设要发送的数据为 1101011011，生成多项式为 $G(x) = x^4 + x + 1$ （即 $G = 10011$ ），求 CRC 校验码和发送的码字。

参考答案(4 个标签)

CRC循环冗余校验模2除法检错编码

数据 $M = 1101011011$ （10位）， $G = 10011$ （5位， $r=4$ ）
数据左移4位： $M \cdot 2^4 = 11010110110000$
用 $G = 10011$ 做模2除法：

11010110110000 ÷ 10011
10011
-----
 10011
 10011
 -----
  00001
  00000
  -----
   00011
   00000
   -----
    00110
    00000
    -----
     01100
     00000
     -----
      11000
      10011
      -----
       10110
       10011
       -----
        01010
        00000
        -----
         1010    （余数 R = 1010，4位）

CRC 校验码为 1010
发送的码字为 11010110111010

答案：CRC 校验码为 1010，发送码字为 11010110111010。

例题2：海明码编码

数据为 1001（4位），采用偶校验，求海明码。

参考答案(4 个标签)

海明码纠错编码偶校验校验位计算

$m=4$ ， $k=3$ （ $2^3=8 \geq 4+3+1=8$ ），总位数 $n=7$
位置安排：

位置	1	2	3	4	5	6	7
内容	P1	P2	D1	P3	D2	D3	D4
数据	?	?	1	?	0	0	1

计算校验位（偶校验）：
- $P_1$ （位置1,3,5,7）： $P_1 \oplus 1 \oplus 0 \oplus 1 = 0 \Rightarrow P_1 = 0$
- $P_2$ （位置2,3,6,7）： $P_2 \oplus 1 \oplus 0 \oplus 1 = 0 \Rightarrow P_2 = 0$
- $P_3$ （位置4,5,6,7）： $P_3 \oplus 0 \oplus 0 \oplus 1 = 0 \Rightarrow P_3 = 1$
海明码为：0 0 1 1 0 0 1

答案：海明码为 0011001。

例题3：组帧方法分析

一个数据链路层协议使用比特填充法，标志字段为 01111110。如果发送方的数据为 011111101111101111110，请写出发送方经过比特填充后实际发送的比特序列。

参考答案(4 个标签)

比特填充组帧帧定界HDLC

原始数据：011111101111101111110
比特填充规则：每当数据中出现 5 个连续的 1，就在其后插入一个 0
逐段处理：
- 01111 → 正常
- 接下来 110：前面已有 01111（4个1），加上这个 1 变成5个连续的1 → 在第5个1后插入0 → 0111110
- 继续：1011111 → 这里又出现5个连续的1 → 插入0 → 10111110
- 继续：01111110 → 5个连续的1 → 插入0 → 011111010
填充后的数据：011111010111110011111010
加上首尾标志字段 01111110：实际发送：01111110 011111010111110011111010 01111110

答案：实际发送的比特序列为 0111111001111101011111001111101001111110（首尾为标志字段，中间为填充后的数据）。

练习题

练习1

简述数据链路层的主要功能，并说明为什么需要组帧。

参考答案(4 个标签)

数据链路层功能组帧差错控制流量控制

数据链路层的主要功能：

组帧：将网络层交来的分组封装成帧，添加首部和尾部，使接收方能从比特流中识别帧边界。
差错控制：通过检错编码（奇偶校验、CRC）和纠错编码（海明码）检测和纠正传输错误。
流量控制：控制发送速率，防止接收方缓冲区溢出。
可靠传输：通过确认和重传机制确保数据可靠到达。
介质访问控制：解决共享信道的访问冲突问题。

为什么需要组帧：物理层只传输原始比特流，没有结构和边界。如果不组帧，接收方无法知道一段数据从哪里开始、到哪里结束，也无法对一段数据进行差错检测。组帧将比特流组织成独立的数据单元（帧），是实现差错控制和可靠传输的基础。

练习2

设数据为 1101，生成多项式 $G(x) = x^3 + x + 1$ （即 $G=1011$ ），求 CRC 校验码。

参考答案(3 个标签)

CRC循环冗余校验模2除法

数据 $M = 1101$ （4位）， $G = 1011$ （4位， $r=3$ ）
左移3位： $1101000$
模2除法：

1101000 ÷ 1011
1011
----
 1100
 1011
 ----
  1110
  1011
  ----
   101    （余数）

余数 $R = 101$

答案：CRC 校验码为 101。

术语对照表

中文术语	英文术语	缩写	说明
数据链路层	Data Link Layer	DLL	OSI第二层
帧	Frame	-	数据链路层的协议数据单元
组帧	Framing	-	将比特流组织成帧
差错控制	Error Control	-	检测和纠正传输错误
流量控制	Flow Control	-	控制发送速率
循环冗余校验	Cyclic Redundancy Check	CRC	广泛使用的检错编码
海明码	Hamming Code	-	可纠正单比特错误的纠错编码
奇偶校验	Parity Check	-	最简单的检错编码
比特填充	Bit Stuffing	-	HDLC等协议使用的组帧方法
介质访问控制	Medium Access Control	MAC	共享信道的访问控制
生成多项式	Generator Polynomial	-	CRC计算中使用的多项式

上一章节数据链路层掌握数据链路层的功能、组帧、差错控制、流量控制、介质访问控制及典型局域网协议。

下一章节流量控制与可靠传输学习停止-等待协议、滑动窗口协议、GBN和SR协议的工作原理与性能分析