跳转至

3 The Data Link Layer

说明

本文档正在更新中……

说明

本文档仅涉及部分内容，仅可用于复习重点知识

核心目标：在直接相连的两个网络节点（即"相邻机器"）之间，提供可靠、高效的数据传输服务。其关键在于维持一个"类导线"的信道，保证数据接收顺序与发送顺序完全一致

数据链路层建立在物理层（第一层）之上，物理层负责实际的比特流传输

实际通信信道的三个固有特性：

  1. errors
  2. finite data rate
  3. propagation delay

而数据链路层的三大功能是：

  1. framing：将物理层传来的原始比特流划分成具有明确边界、可管理的逻辑单元，称为 帧
  2. dealing with errors：error detection（差错检测）and error correction（差错纠正）

  3. flow control（流量控制）：防止发送方的发送速率超过接收方的处理能力，避免接收方缓冲区溢出导致数据包丢失

    1. feedback-based（数据链路层）：接收方向发送方主动发送"反馈"信息，动态地控制发送方的发送行为。发送方必须等待接收方的"许可"才能继续发送
    2. rate-based（传输层）：协议本身为发送方设定一个明确的数据传输速率上限。发送方会按照这个预设的、固定的速率进行发送

数据链路层的实现位置：

  1. 在路由器中：在 line card 上实现

  2. 在主机中：通过软硬件结合的方式实现

    1. 硬件部分（主要部分）：在 NIC（network adapter / network interface card，网卡）中，网络适配器的核心是 link-layer controller（链路层控制器），通常是一个单一的专用芯片，它实现了许多链路层服务
    2. 软件部分（辅助部分）：在主机 CPU 和内存中运行的程序。负责处理那些需要更高层逻辑或与操作系统交互的任务

数据链路层提供的三种主要服务类型：

  1. Unacknowledged connectionless service：发送方直接发送数据帧，不等待接收方的确认。适用于网络质量高、错误率低且需要快速传输的场景，如局域网中的以太网
  2. Acknowledged connectionless service：每发送一帧都要求接收方返回确认，但没有预先建立的连接。适用于无线网络等不可靠环境，如 WiFi
  3. Acknowledged connection-oriented service：在数据传输前需先建立连接，传输结束后释放连接。提供了最可靠的数据传输保障，适用于高错误率、长距离的通信链路，如卫星通信

2 Framing

数据链路层接收来自网络层的 packets，并将其封装成 frames 进行传输

通用帧格式：

  1. header：包含控制信息
  2. payload field：实际传输的数据
  3. trailer：通常包含差错检测信息
Img 2

物理层负责接收原始比特流并尝试将其传送到目的地。但由于信道存在噪声，物理层会向其信号添加一些 redundancy，以将误码率降低到可容忍的水平。数据链路层的通常做法是将比特流分割成离散的帧，为每个帧计算一个称为 checksum（校验和）的短令牌，并在传输时将其包含在帧中。当帧到达目的地时，会重新计算校验和。如果新计算的校验和与帧中包含的校验和不同，数据链路层就知道发生了错误，并采取措施处理（丢弃或返回错误报告）

将比特流分割成帧是很困难的，一个优秀的设计必须让接收方能够轻松找到新帧的 起始位置，同时只占用很少的信道带宽

方法：

  1. Byte Count
  2. Flag Byte with Byte Stuffing
  3. Flag Bits with Bit Stuffing
  4. Physical Layer Coding Violations

2.1 Byte Count

在每个帧的头部添加一个字段，明确指出该帧有多少个字节。接收端根据这个数值来正确地解析数据帧

Img 1

2.2 Flag Byte with Byte Stuffing

使用特殊字节作为帧的起始和结束标记。即使发生传输错误，接收端也能通过搜索这些特殊字节来恢复同步

flag byte 是一个约定好的特殊值，在协议中被定义为帧的边界，所有帧都以这个标志字节开头和结尾。那么两个连续的标志字节表示一个帧的结束和下一个帧的开始

但如果某个数据字段中恰好出现了 FLAG 字节，为了避免被误认为是帧边界，需要进行“字节填充”处理。当发送方检测到数据中出现 FLAG 字节时，会在其前面插入一个转义字节（如 ESC），这样接收方就知道这不是真正的帧边界

但如果转义字节本身也出现在原始数据中，同样需要使用转义字节进行转义

PPP 协议（Point-to-Point Protocol）广泛使用这种字节填充机制

Img 3

2.3 Flag Bits with Bit Stuffing

HDLC（high-level data link control）protocol：使用固定的比特序列 01111110（十六进制 0x7E）作为帧的起始和结束定界符

当数据部分连续出现五个"1"时，发送方自动插入一个"0"；接收方检测到连续五个"1"后的"0"时，会将其删除，恢复原始数据

这种填充方式的作用：

  1. 同步维护：通过强制插入比特，确保传输信号有足够的电平变化，帮助接收方时钟保持同步
  2. 透明度：允许数据字段包含任意比特模式，不会与标志位混淆
  3. 可靠性：有效区分帧边界和数据内容

USB 使用比特填充

Img 4

2.4 Physical Layer Coding Violations

许多物理层编码方案（如 4B/5B、8B/10B）包含未使用的编码组合，将这些编码组合用作帧边界标记，不需要像比特/字节填充那样改变实际数据，避免了填充开销

许多数据链路协议结合使用上述的方法：

以太网和 802.11 让帧以一个明确定义的称为 preamble（前导码）的模式开始。该模式可能相当长（802.11 通常为 72 比特），以便接收方为传入的数据包做好准备。前导码之后是头部中的一个 长度（即计数）字段，用于定位帧的结束

前导码提供充分的同步时间，长度字段确保帧边界准确识别

3 Error Control

两种处理错误的基本策略，这两种策略都向发送的数据添加冗余信息：

  1. error-correcting codes（纠错码）：在数据中添加大量冗余信息，使接收方不仅能发现错误，还能自动纠正错误。适用于不可靠信道（如无线链路、卫星通信）
  2. error-detecting codes（检错码）：添加适量冗余信息，只能检测错误发生，无法自动纠正。检测到错误会请求 retransmission（重传）适用于高可靠性信道（如光纤）

无论是纠错码还是检错码，都无法处理所有可能的错误，因为提供保护的冗余比特与数据比特一样可能在接收时出错

error models

错误产生机制：

  1. 随机错误：由热噪声的极端值引起的，这些极端值会短暂且偶尔地淹没信号，导致孤立的单比特错误，错误之间相互独立
  2. 突发错误：由信号深度衰落、瞬时电磁干扰、设备故障等引起，错误集中出现，连续多个比特受影响

无论是纠错码还是检错码，都不仅用于数据链路层，还广泛应用于其他层，因为 reliability 是一个整体性的关注点

  1. 纠错码：物理层、应用层
  2. 检错码：数据链路层、网络层、传输层

3.1 Error Correcting

Block code（块码）：每个块包含 m 个数据位（原始信息）和 r 个校验位（根据数据位通过某种算法生成，用于检错和纠错）。总长度 n = m + r

  • Codeword（码字）：就是这个长度为 n 比特的序列

  • Code rate（码率）：m / n，表示有效信息所占比例

    • 越高的码率 → 更少的冗余 → 更高效率（但纠错能力弱）
    • 越低的码率 → 更多冗余 → 更强纠错能力（但传输效率低）

因此在噪声较大的信道中，使用低码率，增强抗干扰能力；在高质量信道中，使用高码率，提高吞吐量

两种编码方式：

  1. Systematic Code（系统码）：原始数据位在编码后仍然保留原样，直接出现在码字中，后面附加校验位（信息明文传输）
  2. Linear Code（线性码）：校验位是数据位的线性组合。线性码可以是系统码，也可以不是，即数据位也被变换

3.1.1 Hamming Codes

Hamming distance：两个等长码字在不同比特位置的数量

意义：如果两个合法码字之间的汉明距离为 d，则要将其中一个误变为另一个，至少需要发生 d 个比特错误。因此，汉明距离越大，纠错能力越强

错的越多，越容易发现

minimum hamming distance：根据编码规则，生成所有合法的码字，计算任意两个合法码字之间的汉明距离，找出其中最小的距离，这就是该编码方案的最小汉明距离。这个值决定了编码的检错和纠错能力

  1. 要检测 d 个错误，最小汉明距离至少为 d + 1
  2. 要纠正 d 个错误，最小汉明距离至少为 2d + 1

我们要设计一种编码方式，使得当传输中发生任意一个比特翻转（单比特错误）时，接收端仍能准确恢复原始信息（即能够纠正所有单比特错误）

总共有 \(2^m\) 个可能的信息组合，每个合法消息对应一个唯一的合法码字，对于每一个合法码字，存在 n 个与其汉明距离为 1 的非法码字。所以，每个合法码字需要“负责”自己本身以及所有可能的单比特错误版本，即每个合法码字总共需要占用 n + 1 个不同的比特模式

所有可能的 n 比特二进制序列总数为 \(2^n\)，所有合法码字及其对应的单比特错误版本总共需要的空间是：\((n+1) \times 2^m\)。为了不超过总空间，必须满足 \((n+1)2^m \leqslant 2^n\)，代入 \(n = m + r\)，可得

\(m+r+1 \leqslant 2^r\)

这就是 hamming bound 的简化形式

结论：根据这个公式，我们能够得知纠正单比特错误所需校验位数的理论下限

r 需要足够大，才能提供足够的冗余来区分所有可能的单比特错误情况

m = 4

我们想用 m = 4 个信息位，设计一个能纠正单比特错误的码。根据公式可得，至少需要 r = 3 个校验位，总长度为 n = 7

这就是经典的 (7, 4) 汉明码，可以纠正任意一个比特错误

汉明码的编码过程：

  1. 校验位放置：放置在 2 的幂次方的位置，数据位填充剩余位置
  2. 校验位计算：遍历所有数据位，记录值为 1 的比特位置，将这些位置编号用二进制表示并进行异或运算，异或结果就是校验位的值

汉明码的解码过程：

  1. 伴随式（syndrome word）计算：接收方用同样方法重新计算校验位，与接收到的校验位进行异或比较，得到伴随式
  2. 错误定位：伴随式为 0 则无错误；伴随式非 0，其数值直接指示错误位置（如果是检验位发生了错误，则无需进行纠正；如果是数据位发生了错误，则通过反转该数据位进行纠正）
Img 5
Img 6

3.1.2 Convolutional Code

卷积码与分组码不同。卷积码将 m 比特的输入映射为一个 n 比特的码字，因此原始信息比特不会原封不动地出现在输出码字中

记忆性：卷积码编码器的输出不仅由当前输入的 m 个比特决定，还受到在此之前输入的若干比特的影响

而影响当前输出的过去输入比特的数量（通常包括当前比特）称为 constraint length（约束长度）\(K\)。\(K\) 值越大，编码器的记忆越长，通常编码性能越好，但编 / 解码复杂度也越高

表示方法：\((n,m,K)\)

  • \(n\)：输出的码字长度
  • \(m\)：每次输入的原始数据比特数
  • \(K\)：约束长度
Img 7

卷积码解码器的任务是从接收到的（可能含有错误的）输出码字序列中，反推出最有可能被发送的原始输入数据序列

The Viterbi algorithm：

  1. 构造一个 trellis diagram（网格图）：将时间展开成多个时刻，每个时刻对应一个输入比特。每个节点表示一个编码器状态。从每个状态出发，有两个分支，一个输入比特为 1，一个输入比特为 0。每条边上的数字是对应的输出比特
  2. 在接收端，我们观察到一串输出比特。维特比算法通过遍历这个网格图，寻找一条最可能的路径（即与接收到的序列汉明距离最小的路径）。它维护每一步每个状态下的“最可能路径”，并逐步淘汰不可能路径。最终选择终点处累积错误最少的路径作为原始输入比特序列
Img 8
Img 9

3.2 Error Detecting

由于无线链路不稳定的传播环境，噪声干扰大，误码率高。因此，通常采用前向纠错码，在接收端直接纠正错误，以避免频繁重传带来的巨大开销和延迟

而在有线链路如光纤或高质量铜缆中，信道质量高，误码率极低。在这种情况下，为偶尔出现的错误而持续使用复杂的纠错码不划算。更高效的策略是使用简单的差错检测码，一旦发现错误，就通过 retransmission 机制来纠正。这种方式在可靠信道上整体开销更小

3.2.1 Parity

奇偶校验

在要发送的原始数据块末尾添加一个额外的比特，即奇偶校验位。这个校验位的值不是随意的，而是根据数据块中"1"的个数和所选的校验规则（偶校验或奇校验）来决定的

  • even parity：确保整个码字（数据位 + 校验位）中"1"的总数为偶数
  • odd parity：确保整个码字中"1"的总数为奇数

示例

数据：1011010

  • 采用偶校验：校验位添加 0，码字变为 10110100
  • 采用奇校验：检验位添加 1，码字变为 10110101

使用单个奇偶校验位的码其码距为 2，因为任何单比特错误都会产生一个具有错误奇偶性的码字。因此，它可以检测出所有的单比特错误

码距为 2 意味着任何有效的码字之间至少有两个比特不同

如果发生偶数个比特错误，"1"的总数的奇偶性可能保持不变，错误就无法被检测出来

分析 parity 的优势

假设一个信道的误码率为 \(10^{-10}\)，每个数据块包含 1000 比特的数据

  1. 纠错码（汉明码）：根据 hamming bound 的公式，可得每个数据块需要 10 个校验位。那么传输 1 兆比特数据，就需要总共 10000 比特的校验位
  2. 检错码（奇偶检验）+ 重传：每个数据块仅需 1 个校验位。传输 1 兆比特数据，所需的奇偶校验位总数为 1000 比特。而根据信道的误码率，大约每 1000 个数据块中会有 1 个块出错需要重传。因此，总开销为 1000（校验位） + 1001（重传块的 1000 数据位和 1 校验位） = 2001 比特

所以，在误码率很低的可靠信道上，采用简单的差错检测配合重传机制，其效率远高于使用复杂的前向纠错机制

奇偶校验的局限性：简单奇偶校验能有效检测单比特错误，但对于突发错误，即连续多个比特发生错误，其检测能力会急剧下降。在随机噪声导致的长突发错误场景下，发生"未被检测出的错误"的概率大约是 50%。这个漏检率对于绝大多数需要可靠通信的系统来说是不可接受的

解决方案有：

  1. Interleaving：在发送端，数据比特被按照某种规则重新排列（例如，按矩阵的列写入），然后再计算和传输。在接收端，进行相反的解交错操作，恢复原始顺序。一个长的突发错误在传输过程中会破坏连续比特，但经过解交错后，这些错误比特在数据流中就被分散开了，变成了单个或短小的错误，从而使得简单的奇偶校验也能有效地检测到它们
  2. Two-dimensional parity：将数据比特排列成一个矩阵（二维阵列）。不仅为每一行计算一个行奇偶校验位，也为每一列计算一个列奇偶校验位。一个突发错误可能会破坏矩阵中的连续几行，但它在每一行中可能只造成一两个错误。这样，行校验有可能检测到部分行的错误，而列校验则几乎肯定能检测到这些错误，因为错误比特分布在不同列中。这大大提高了检测突发错误（乃至多种错误模式）的能力
Img 10
Img 11

3.2.2 Checksum

校验和

广泛应用于 TCP / IP / UDP

16-bit Internet checksum：采用 one's complement 加法

而现在计算机一般都是用 tow's complement，反码求和等价于将所有 16 位数据相加后取模 \(2^{16}\)，并将高位溢出的部分加回到低位上

发送端计算校验和：

  1. 将待发送的数据（不包括校验和字段本身）划分为连续的 16 位字。如果数据长度不是 16 位的整数倍，需要进行填充
  2. 将校验和字段本身视为 0000，然后与所有其他的 16 位数据字进行求和
  3. 将上一步求和产生的任何高位进位加回到结果的低位，从而得到所有数据字的反码和
  4. 对上一步得到的 16 位反码和执行按位取反操作，取反后的值就是最终计算出的校验和

示例

  1. 0001 + f203 + f4f5 + f6f7 = 2ddf0
  2. 2 是高位溢出的，加回到低位，ddf2
  3. 取反后得到校验和 220d

接收端计算校验和：

  1. 将待发送的数据（不包括校验和字段本身）划分为连续的 16 位字。如果数据长度不是 16 位的整数倍，需要进行填充
  2. 接收端的校验和字段非零，与所有其他的 16 位数据字进行求和
  3. 将上一步求和产生的任何高位进位加回到结果的低位，从而得到所有数据字的反码和
  4. 对上一步得到的 16 位反码和执行按位取反操作，如果结果为 0，则说明接受到的数据无误

示例

  1. 0001 + f203 + f4f5 + f6f7 + 220d = 2fffd
  2. 2 是高位溢出的，加回到低位，ffff
  3. 取反后得到 0000，说明接收到的数据无误

因特网校验和的本质是一个简单的算术和。这种设计使其计算效率高、实现简单，但也导致了其检错能力存在固有的弱点

  1. 无法检测零数据的增删：如果在数据流中增加或删除若干字节的 0，由于 0 加上任何值都不改变总和，所以最终的校验和结果可能保持不变，从而导致这些错误无法被检测出来
  2. 无法检测数据部分的交换：如果消息中的两个或多个 16 位字的位置被交换，校验和的结果同样不会改变

3.2.3 Cyclic Redundancy Check

循环冗余校验（CRC）

CRC 是一种基于二进制多项式除法的、非常强大的差错检测码。它通过在数据块后添加一个冗余的 frame check sequence（FCS，帧校验序列）来实现检错

发送端操作：

  1. 输入：一个长度为 m 比特的原始数据块
  2. 处理：发送端根据一个双方预先约定好的生成多项式，对原始数据进行计算
  3. 输出：计算生成一个长度为 n - m 比特的 FCS。将 FCS 附加到原始数据之后，形成一个总长度为 n 比特的完整帧

这个完整的 n 比特帧，在数学上可以被那个生成多项式整除（模 2 除法），没有余数。生成多项式必须满足其最高次项和常数项（即比特模式的首位和末位）的系数都为 1

接收端操作：

  1. 验证：接收端收到这个 n 比特的帧后，使用相同的生成多项式对它进行模 2 除法运算
  2. 判断：如果余数为零，说明传输过程中极有可能没有发生错误，数据被接受；如果余数不为零，则肯定发生了传输错误，接收端会丢弃该帧或请求重传

参数定义：

  1. \(T\)：最终传输的 n 比特长度的数据
  2. \(D\)：长度为 m 比特的原始数据
  3. \(F\)：由 CRC 算法计算出的校验码，长度为 n - m
  4. \(P\)：双方预先约定的比特模式，也称为生成多项式。长度为 n - m + 1
  5. \(Q\)：商
  6. \(R\)：余数
Img 12

A utopian simplex protocol（乌托邦式单工协议）：理想化通信模型

  1. 单向传输：数据只从一方流向另一方
  2. 始终就绪：假设发送方和接收方的上层（网络层）随时都能立即处理数据
  3. 忽略处理时间：假设数据在发送端和接收端的封装、解封装、计算等处理时间为零
  4. 无限缓冲区：假设发送和接收方有永远用不完的缓存空间来存储数据
  5. 无损信道：这是最不切实际的假设，认为物理信道是完美的，帧永远不会出错或丢失

A simplex stop-and-wait protocol for an error-free channel（用于无差错信道的单工停止-等待协议）

解决流量控制的问题：即使信道是完美的（无差错），如果发送方发送帧的速度快于接收方处理（例如，将数据上传给网络层）的速度，接收方的缓冲区最终会被填满，导致帧被丢弃

解决方案：引入 feedback 机制。接收方通过向发送方发送一个 dummy frame（哑帧，确认帧，ACK）来主动控制发送方的节奏

工作流程：发送方发送一帧数据，然后停止并等待。接收方成功接收该帧并将其上传给网络层后，发回一个 ACK。发送方收到 ACK 后，才被允许发送下一帧

该协议对信道的要求：由于通信是单向的（数据一个方向，ACK 反方向），且同一时间只有一个方向在传输，因此半双工信道（可以双向通信但不能同时）就足够了

A simplex stop-and-wait protocol for a noisy channel（用于噪声信道的单工停止-等待协议）

解决信道噪声的问题：信道不是完美的。数据帧可能在传输过程中发生比特错误（损坏） 或完全丢失

解决方案：超时重传机制。在发送方引入一个 timer（计时器）

工作流程：发送方发送一帧，并同时启动计时器。如果发送方没有在预定的时间内收到 ACK 消息，发送方就认为帧传输失败。发送方于是重新发送原来的那一帧，并重启计时器。这个过程一直重复，直到发送方最终收到对应的 ACK 为止

缺陷：duplicate，重复帧问题。如果接收方发给发送方的 ACK 丢失了，那么发送方会再次发送一个同样的数据包，导致数据重复

Img 13

关于 stop-and-wait 协议的两个问题

  1. 超时时间应设置多长？

    1. 必须预留足够的时间，让帧能够到达接收方、让接收方在最坏情况下完成处理、并且让确认帧能够传回发送方
    2. 如果超时间隔设置过短，发送方会传输不必要的帧（即重复帧）
    3. 如果超时间隔设置过长，信道将会处于空闲状态，降低效率

  2. 如何避免将重复帧当作新帧接收？接收方必须能够判断收到的帧是一个新帧还是一个重复帧

关于第 2 个问题的解决方案：为帧分配 sequence number（序列号）

具体实现：每个发出的数据帧都带有一个序列号。接收方返回的确认帧也携带它所确认的那个数据帧的序列号。对于最简单的停止-等待协议（每次只发一帧），由于在任何时刻只有一个未确认的帧，因此只需要两个序列号（0 和 1）循环使用就足够了。这只需要 1 个比特来表示

接收方检查收到的数据帧序列号。如果序列号与期望接收的下一个新帧的序列号相同，则接收并上传给网络层，然后更新期望的序列号。如果序列号是旧的（与期望的不符），则说明是重复帧，直接丢弃，但仍为这个重复帧发送一个 ACK（以防之前的 ACK 丢失）

序列号的位置在每个数据帧的头部。但头部空间非常宝贵，为了减少开销（提高效率），我们希望序列号字段尽可能小

在 stop-and-wait 协议中，序列号所需的最小比特数是多少

只有在收到对当前帧（设为帧 m）的确认后，才会发送下一帧（帧 m+1）。如果发送方在准备发送帧 m+1，那它必定已经收到了帧 m 的确认。而发送方之前能发送帧 m，又意味着它必定已经收到了帧 m-1 的确认。

因此，在正常情况下，帧 m-1、m、m+1 的发送和确认是一个严格顺序、没有重叠的过程

需要区分的对象永远只在两个连续的序列号之间（即当前期望的帧和它的前一个或后一个帧），那么只需要两个不同的序列号标签就足够了

1 个比特恰好可以提供两个序列号：0 和 1。让序列号在这两个值之间交替，就足以让接收方明确判断

Img 14
Img 15
Img 16
Img 17

5 Sliding Window Protocols

滑动窗口协议：适用于全双工通信，即 A 和 B 可以同时互相发送数据。因此，从 A 到 B 的链路上，既会有 A 发给 B 的数据帧，也会有 B 发给 A 的确认帧。这两个方向的流量是混合在一起的

Piggybacking（稍带确认）：当 B 需要向 A 发送数据并且同时需要确认之前从 A 收到的数据时，它不会单独发送一个纯粹的确认帧。相反，它会将确认信息（ACK）放入它要发给 A 的数据帧的头部字段中

B 在准备好要发送给 A 的数据帧后，会稍微等待一个极短的时间（延迟发送）。如果在这段等待时间内，有需要确认的 A 发来的数据帧到达，B 就会将这个确认信息"捎带"在自己即将发出的数据帧里，一起发送给 A

那么这个极短的等待时间具体是多久呢

设置一个固定的等待计时器。如果在计时器超时之前，本机恰好有数据要发送给对端，那么确认信息就可以完美地捎带在这个数据帧上发出。如果在计时器超时之后，仍然没有反向数据，为了不耽误确认，数据链路层会立即发送一个独立的、专门的确认帧，以避免发送方因等待 ACK 而超时

三种主要的滑动窗口协议：

  1. A one-bit sliding window protocol：实质上就是停止-等待协议在全双工场景下的实现。发送窗口大小为 1，效率最低，但实现最简单，缓冲区需求最小
  2. A protocol using go back N：发送窗口大于 1，允许连续发送多个帧。如果某个帧出错，发送方会回退并从出错的帧开始重传所有后续帧。效率高于停止-等待，但重传开销可能较大
  3. A protocol using selective repeat：发送窗口大于 1。它只选择性地重传那些真正出错或丢失的帧。效率最高，但实现最复杂，因为接收方需要更大的缓冲区来缓存乱序到达的帧

评论区

欢迎在评论区指出文档错误，为文档提供宝贵意见，或写下你的疑问