链路层基本技术 • Roxy's Library

本文内容基于 2025 秋季《计算机网络》课程讲述，如有差错，欢迎指正

链路层概述#

定位与功能#

数据链路层的作用是在物理相连的两个结点间，基于物理层提供的比特流服务，进行数据传输，并向网络层提供接口

传输单元：帧 (Frame)
通信模型：
- 主机和路由器统称为节点 (Node)
- 节点之间通过链路或信道 (Link/Channel) 连接
- 不同链路上可能会使用不同协议，提供不同服务（可靠/不可靠、有连接/无连接等）

早期链路层被进一步划分为两个子层：

逻辑链路控制 (LLC, Logical Link Control)：
- 上层，处理与介质无关的逻辑，如流控、差错控制
- 向网络层提供统一接口
介质访问控制 (MAC, Medium Access Control)：
- 下层，直接与物理介质打交道
- 解决“谁可以使用信道”的问题（即多路访问控制）

链路层位置示意图

链路层功能实现在网络适配器（网卡）上

提供的服务类型#

无确认无连接服务：
- 发送前不建连接，收到后不发确认
- 适用：误码率极低的链路（如光纤、以太网）或实时性要求高允许丢包的场景
- 差错处理：通常直接丢弃，由上层（如TCP）负责重传
有确认无连接服务：
- 不建连接，但每发一帧需确认（ACK）。若超时未收确认则重传
- 适用：不可靠链路（如无线 WiFi）
有确认面向连接服务：
- 建立连接 -> 传输 -> 释放连接
- 提供最可靠的服务（如早期的长途电话链路）

成帧#

物理层传输的是比特流，链路层需要将比特流切分成离散的“帧”，以实现数据传输和差错控制等功能

关键问题在于：如何确定帧的边界？下面介绍几种常见的成帧方法：

字符计数法#

在每个帧的头部加上一个字段记录帧的长度（字符数）

字符计数法示意图

致命缺点：一旦计数字段出错，接收方会失去帧边界同步，导致后续所有帧都无法解析。（已淘汰）

字节填充的定界符#

定义一个特殊的定界符字节 (FLAG)，标记帧的开始和结束

问题：如果有效载荷中恰好出现了 FLAG 字节怎么办？
解决：转义
- 在有效载荷中的 FLAG 前插入一个转义字节 (ESC)
- 如果有效载荷中本身有 ESC，则在 ESC 前再插一个 ESC

字节填充法示意图

对于接收方来说，如果遇到 FLAG，则表示帧边界；如果遇到 ESC，则丢弃它，其下一个字节一定是有效载荷

比特填充的定界符#

既然可以用字节作为帧的边界，那么也可以用一个比特串作为边界，比如使用特殊的比特模式 01111110 (0x7E，两个0之间6个1) 作为帧的定界符

同样的，我们也需要解决有效载荷中出现该比特串的问题

规则：发送方在有效载荷中只要发现连续 5个 1，就强制插入 1个 0
- 原始数据：01111110
- 发送数据：011111010
接收方：发现连续 5个 1 后，检查下一位：
- 是 0 $\to$ 为有效载荷，删除该 0
- 是 1 $\to$ 也就是 0111111，这6个1和前后的各一个0构成定界符

比特填充法示意图

优点：可以传输任意比特长度的数据，不再受限于字节整数倍。

物理编码违例#

上述方法中，我们为了区别有效载荷和定界符，在有效载荷中插入额外的比特或字节，那为什么我们可不可以直接不让有效载荷内出现定界符呢？

核心思想：选择的定界符不会在数据部分出现

一些实例：

4B/5B编码方案
- 4比特数据映射成5比特编码，剩余的一半码字（16个码字）未使用，可以用做帧定界符
- 例如： 00110组合不包含在4B/5B编码中，可做帧定界符
前导码
- 存在很长的前导码（preamble），可以用作定界符
- 例如：传统以太网、802.11
曼切斯特编码 / 差分曼切斯特编码
- 正常的信号在周期中间有跳变，持续的高电平（或低电平）为违例码，可以用作定界符
- 例如：802.5令牌环网

差错检测与修复#

在数据传输的过程中，很有可能会产生各种各样的错误，比如说电磁信号的干扰使得某些比特翻转，从而导致接收方收到错误的数据。对于遇到的错误，链路层可以选择把错误的数据丢弃，让发送方重传；又或者是通过一些高级的编码方式，检测并纠正错误。不论是检错还是纠错，核心思想都是在数据中加入一些冗余信息，这样接收方才可以通过这些信息完成错误检测或纠正

比如蓝牙1/3 FEC 编码，采用的是每个比特重复发送3次的方式

但是，冗余信息越多，开销越大，传输效率越低，因此我们需要考虑的是在保证一定差错检测和纠错能力的前提下，如何减少冗余信息量？

检错码#

检错码只能使接收方推断数据是否发生错误，但不能推断哪位发生错误，接收方可以请求发送方重传数据。主要用在高可靠、误码率较低的信道上，例如光纤链路

奇偶校验

1位奇偶校验：增加1位校验位，可以检查奇数位错误

偶校验：保证1的个数为偶数个
奇校验：保证1的个数为奇数个

奇偶校验示意图

单纯的使用1位奇偶校验只能检测单比特错误，且不能知道错误位置。但如果对数据进行合适的排布，可以提供一定能力的纠错功能

二维奇偶校验：把数据排成矩阵形式，每行每列都校验。能检测并纠正单比特错误

二维奇偶校验示意图

校验和 CheckSum

TCP/IP体系中主要采用的错误检测方法（细节见UDP checksum ↗）

发送方进行 16 位二进制求和运算，将计算结果取反，随数据一同发送
接收方对收到的数据和校验和进行同样的 16 位二进制求和运算，结果应为全 1，否则表示出错

循环冗余校验 CRC

一种基于二进制多项式运算的检验方法

计算方法：

设原始数据 $D$ 为m位二进制串
如果要产生 $r$ 位CRC校验码，事先选定一个 $r+1$ 位二进制串 $G$ (称为生成多项式，收发双方提前商定)， $G$ 的最高位为1
将原始数据 $D$ 乘以 $2^r$ （相当于在D后面添加 $r$ 个 0），产生 $m+r$ 位二进制串
用 $G$ 对 $D\times 2^r$ 做模2除，得到余数 $R$ （ $r$ 位，不足 $r$ 位前面用0补齐）即为CRC校验码

接收端校验方法：

接收到的数据除以 $G$ ，余数为 0 则无错
能检测出少于 $r+1$ 位的错误

CRC示意图

理论分析#

一些定义：

码字 (code word)：一个包含 $m$ 个数据位（信息位）和 $r$ 个校验位的 $n$ 位单元，描述为 $(n, m)$ 码， $n=m+r$
码率 (code rate)：码字中不含冗余部分所占的比例，可以用 $m/n$ 表示
海明距离 (Hamming distance)：两个码字之间不同对应比特的数目
- 例：0000000000 与0000011111的海明距离为 $5$
- 如果两个码字的海明距离为 $d$ ，则需要 $d$ 个单比特错就可以把一个码字转换成另一个码字
- 为了检查出 $d$ 个错（比特错），可以使用海明距离为 $d+1$ 的编码。
- 为了纠正 $d$ 个错，可以使用海明距离为 $2d+1$ 的编码。

在现实中，我们很多时候考虑的更多的是单个比特位发生的错误。下面我们分析一下要去纠正单个比特位发生的错误，我们至少需要多少校验位

假设有 $m$ 个信息位， $r$ 个校验位，共 $n$ 个比特，要纠正单比特错

$n$ 个比特一共可以有 $2^n$ 个码字，包含有效码字与无效码字
每个 $m$ $m$ 位有效信息，除了本身的 $n$ $n$ 位有效码字，与该有效码字距离为1的 $n$ $n$ 个码字必须无效
- 否则，当单比特错误发生时，无法判断是否出错
同时，任何两个有效码字，它们距离为1的无效码字没有重叠
- 否则，无法判断错误的码字离哪个有效码字更近
因此，每个 $m$ 位有效信息，实际上消耗至少 $n+1$ 个码字，即： $(n + 1) 2^m \le 2^n$
利用 $n = m + r$ ，得到 $(m + r + 1) \le 2^r$
在给定 $m$ 的情况下，利用该式可以得出 $r$ 的下界

这个下界可以达到，如海明码

纠错码#

接收方能够通过纠错码判断接收到的数据是否有错，并能纠正错误（定位出错的位置）。主要用于错误发生比较频繁的信道上，如无线链路；也经常用于物理层，以及更高层（例如，实时流媒体应用和内容分发）

使用纠错码的技术通常称为前向纠错(FEC，Forward Error Correction)

海明码

利用奇偶校验位的特定位置组合，定位出错的比特位

我们以 $(15,11)$ 海明码为例：

11位数据位，4位校验位，共15位码字
校验位位置：放置在 $2^k$ 位置上 (第 1, 2, 4, 8位)，记为 $P_1, P_2, P_4, P_8$
默认使用偶校验
所有码字以下图方式排列，图中右下角数字为码字中位序号

对于第 k 个数据位，将 k 分解为2的次幂之和，得到的每个2的次幂，都参与对第 k 位的校验

例如，第 11 位数据位，11 = 8 + 2 + 1，因此由 $P_1, P_2, P_8$ 校验

每个校验位负责校验的数据位如下：海明码校验位示意图

假设第 7 位出错，接收方计算各个校验位：

$P_1,P_2$ 出错，确定在最后一列
$P_4$ 出错， $P_8$ 正确，确定在第二行
结合可知，第 7 位出错

RS 码 (Reed-Solomon Code)

以有限域运算为基础，提供多位纠错能力

RS码会将需要编码的01流数据重新划分为以符号(Symbol)为单位的数据块
$m$ 表示符号的大小，如 $m=4$ 表示每个符号由4位二进制数组成
对于一个 $(n, k)$ RS编码， $k$ 为原始数据符号数， $n-k$ 为校验符号数
$n-k=2t$ ， $t$ 表示能够纠正的错误数
校验符号里的内容，通过对数据进行线性组合得到

RS码示意图图中任意两个symbol损坏都可以进行修复，不论是否属于同一帧

对于RS编码来说，关键是如何去设计这些线性组合，使得符号在损坏时可以恢复

设计线性组合也就是设计一个矩阵，使其和数据向量相乘得到编码后的向量。具体方法有很多，比如基于生成多项式的方法，基于范德蒙德矩阵，基于柯西矩阵的方法等。这里就不在讲述，因为笔者也没搞懂（

介质访问控制#

多个用户共享同一条信道时（比如WiFi），可能多个用户同时发送数据，导致信道冲突，引发数据损坏或丢失。我们希望使用某一种多路访问控制技术来决定这个信道下一个时刻是由谁去进行访问，或者说在发生冲突时怎么去解决。而不是在数据校验之后再去重传数据，这样会大大降低信道的利用率

静态信道划分#

通过某些物理上的手段，把这些信道划分成多个子信道，然后把这些子信道分配给每个站点。在物理上保证每个站点使用子信道时是没有任何的冲突的

TDMA(time division multiple access)

把整个信道划分成多个时间片，每个站点在自己的时间片内发送数据，未使用的时间片闲置

FDMA(frequency division multiple access)

把整个信道划分成不同的频段。每个站点得到一个固定的频段，每个频段带宽相同

划分的频段越多，每个频段的带宽也就越小

CDMA(code division multiple access)

为每个站点去分配一套独特的编码方案，发送方使用该编码对数据进行编码，即使冲突发生，接收方也能进行解码

主要用于无线通信
虽然它的效率和之前我们所讲的两种方法一样，都是 $1/N$ ，但是好处是编码与活跃的用户数相关，不活跃的站点不会占用资源

随机访问#

不再对信道进行划分，而是允许多个站点去同时传输，并且允许冲突的发生。关键在于，冲突检测和发生冲突之后进行恢复

ALOHA 类协议#

纯ALOHA

想发就发。每个站点收到上层数据包，立即向信道发送；没有任何同步或信道检测
随时可能冲突，冲突的帧被完全破坏，破坏了的帧要重传

纯ALOHA的信道利用率计算：

定义

帧时T：发送一个标准长的帧所需的时间
- 一个帧时内用户产生的新帧：均值N个，服从泊松分布
- 一个帧时内信道中产生的帧（包括重传）：均值G个，服从泊松分布，物理意义是网络负载；当重负载( $G>>1$ ) 时，冲突频繁
吞吐量S：在帧时T内发送成功的平均帧数，显然 $S \le 1$
$P_0$ ：一帧发送成功(即未发生冲突)的概率，就是发送成功的分组在已发送分组的总数中所占的比例

由定义可知： $S = G \times P_0$

如何计算 $P_0$ 呢？

一个帧要成功传输，必须在它传输的时间，没有跟别的帧发生碰撞
$P_0$ 的含义是在连续两个T的时间内都没有其它帧生成的概率，即连续两个T的时间内都生成0帧的概率之乘积
由于帧的生成服从泊松分布，因此在相邻 $2T$ 内生成0帧的概率为 $P_0= Pr(k=0)\times Pr(k=0) = e^{-2G}$

所以 $S=G \times e^{-2G}$ ，当 $G=0.5$ 时， $S$ 达到最大值 $1/(2e) \approx 18.4\%$

即纯ALOHA信道的利用率最高为 $18.4\%$

分隙ALOHA

假设:
- 所有帧大小一样
- 时间划分为等长的时间槽，每个时间槽刚好可以传输1个帧
- 站点只能在时间槽开始时发起传输
- 冲突只在时间槽起点发生
- 所有站点的时钟是同步的（这个假设很难实现，需要定期同步）
当站点有帧需要发送时，在下一个时间槽开始时进行传输
- 如果直到传输完毕都没有冲突，则完成
- 如果发生冲突，以概率 $p$ 在下一时间槽重传

分隙ALOHA的信道利用率计算：

和纯ALOHA类似，不同的是 $P_0$ 只需要在一个时间槽内没有其它帧生成

$P_0 = Pr(k=0) = e^{-G}$

所以 $S=G \times e^{-G}$ ，当 $G=1$ 时， $S$ 达到最大值 $1/e \approx 36.8\%$ ，是纯ALOHA的两倍

两种ALOHA的比较

ALOHA比较图

CSMA 类协议#

CSMA (Carrier Sense Multiple Access) 即载波监听多路访问协议，其特点是：在发送数据前，先监听信道状态，只有在信道空闲时才发送数据

根据监听后发送的策略，可以分为三种类型：

非持续式CSMA

特点：

经侦听，如果介质空闲，开始发送
如果介质忙，则等待一个随机分布的时间，然后重复步骤1

等待一个随机时间可以减少再次碰撞冲突的可能性，但是等待时间内介质上如果没有数据传送，那么这段时间是浪费的

1-持续式CSMA

特点：

经侦听，如果介质空闲，开始发送
如果介质忙，则持续监听，一旦空闲重复步骤1

1-持续式的延迟时间要少于非持续式，但如果此时有多个站点等待发送，那么一旦介质空闲，所有站点都会立即发送，会发生冲突

p-持续式CSMA

特点：

经侦听，如介质空闲，那么以 $p$ 的概率立刻发送，以 $(1–p)$ 的概率推迟一个时间单元再进行处理
如介质忙，持续侦听，一旦空闲重复步骤1
如果发送已推迟一个时间单元，再重复步骤1

这是对上面两种协议的一种折中

CSMA/CD（1-持续式+冲突检测）

原则：“边听边说” (Listen while talking)

先听：空闲则发送
边发边听：发送过程中进行冲突检测
冲突停止：一旦检测到冲突，立即停止发送，并发送Jam信号 (Jamming Signal) 通知全网
随机重传：等待随机时间后重复步骤1

关于侦听时间的选择:

冲突的位置决定了侦听时间的长短
最极端情况：信号刚好到达另一端时发生冲突，此时，对方的冲突信号回到源端时才能检测到冲突。这段时间刚好是一个RTT

csma_cd_timing

以太网中的CSMA/CD实现细节

完全使用CSMA/CD
- 发送前：1-持续式
- 发送时：检测冲突
冲突解决方法：二进制指数后退
- 第 $i$ 次冲突后，从 $[0, 1, ..., 2^i - 1]$ 中随机选一个数 $k$ ，等待 $512k$ 个比特数据所需的发送时间

轮流协议#

使用信道划分的方法，在高负载时，信道利用率高且保证公平；但是在低负载时，信道利用率低，即使只有1个站点需要发数据，也只能用1/N带宽。使用随机访问的方法，在低负载时，信道利用率高；但在高负载时，冲突严重

轮流协议希望将这两者的优势结合。

轮询协议

在站点间选择一个主节点，由主节点给其他站点分配信道使用权

通常轮流通知每个站点，可以传输多少帧
传输完成后，通知下一个站点

问题：

轮询通知本身也带来了延迟和带宽占用
主节点单点故障会导致整个网络瘫痪

令牌传递

将所有站点组织成某种结构，使得可以安排顺序
令牌（Token）在网络中传递，只有持有令牌的站点才能发送帧，然后将令牌传递给下一个站点；如果没有数据发送，则直接将令牌传递给下一个站点
问题是令牌的可靠性与维护代价需要保障

位图协议

把整个传输过程划分成了两个时期

竞争期
- 每个站点在自己的时隙里发送竞争比特
- 所有站点收集这些信号，形成一个位图，表示哪些站点有数据要发送
传输期
- 按照位图的顺序，允许有数据的站点依次发送数据
- 传输完成后，进入下一个竞争期

当负载大时（要发送数据的站点多），信道利用率很高（竞争期开销相对较小）；当负载小时，竞争期开销相对较大，信道利用率下降

但是没有考虑到站点优先级的问题

二进制倒计数

给站点分配一个长度相同的序号 ID
所有站点同步广播 ID，若发送 0 的站点听到 1，则退出竞争
- 结果：高序号（优先级高）的站点胜出。信道利用率几乎 100%

有限竞争协议

在低负荷时：使用竞争法，以减少延迟时间
在高负荷时：使用无冲突法，以获得高的信道效率