数据链路层

• 1: 组帧
• 2: 差错控制
• 3: 流量控制
• 4: 介质访问控制
• 5: 局域网和广域网
• 6: 数据链路层设备

# 数据链路层

## 数据链路层的功能

## 组帧

## 差错控制

- 检错编码
- 纠错编码

## 流量控制和可靠传输机制

- 流量控制、可靠传输和滑动窗口
- 停等协议
- 回退N帧
- 选择性重传协议

## 介质访问控制

- 信道划分
- 随机访问：ALOHA, CSMA, CSMA/CD, CSMA/CA
- 轮询访问

## 局域网

- 基本概念和体系结构
- 以太网和IEEE 802.3
- 无限局域网和IEEE 802.11
- VLAN

## 广域网

- 基本概念
- PPP协议

## 数据链路层设备

- 以太网交换机和工作原理

1 - 组帧

数据链路层的主要功能就是组帧。

帧（frame）代表数据链路层的数据发送单位，在接收到来自于网络层的报文（packet）时如何为其添加帧头和帧尾，并且以何种方式进行帧定界（接收方区别连续不同的帧）。

组帧的关键就在于帧定界，也就是对于接收方来说，它能够以某种方式区分连续收到的不同帧。 从这个角度出发，组帧方式可以被分为以下几种：

字符计数法

字符计数法在帧首部使用计数字段来表明帧内字符数量。

当接收方读取帧时，根据读取帧开头的一部分内容，即可得知当前帧的长度是多少，这样就

首位定界字符法

首位定界字符法即 使用特殊控制字符标志帧的开始和结束。

但是使用这种方式可能出现如下问题：就是 首位定界字符 可能会在帧内部出现，这个时候就会造成歧义。

所以当特殊字符出现在帧的数据部分时，需要用转义字符ESC来对特殊字符进行转义，同样，ESC出现在数据部分同样需要转义。

以上图为例，假设我们使用 FLAG 作为首位定界字符的话（注意这里 FLAG 只是字符名称，不是表示字符是 FLAG），那么当 FLAG 出现在数据部分时，我们需要对 FLAG 进行转义，需要注意的是，因为我们使用 ESC 作为转义字符，所以当数据中出现 ESC 时，我们也需要对转义字符自己进行转义。

零比特填充法

零比特填充法（Bit Stuffing）与首位定界字符法思路类似。

用 01111110 作为一个新的数据帧的开头，这里的关键在于要对数据帧内容中与 01111110 相同的部分进行转义，转义的方式如下：

• 在 发送方：
  • 每当数据中出现 连续 5 个 ‘1’ 时，
  • 就自动插入一个 ‘0’，避免形成 6 个连续的 ‘1’（即避免形成 01111110）。
• 在 接收方：
  • 每当检测到 连续 5 个 ‘1’ 后跟着一个 ‘0’，就去掉这个 ‘0’，还原原始数据。
  • 在传送的比特流中可以传送任意比特组合，而不会引起对帧边界的判断错误。零比特填充法很容易由硬件来实现，性能优于字符填充法。

对于零比特填充法，需要记住 01111110 这种开头的比特填充方式 以及 具体如何进行转义。

违规编码法

违规编码法（Physcial Layer Coding Violations）使用特殊电平进行定界。比如，曼彻斯特编码将数据比特“1”编码为“高 - 低”电平，将比特“0”编码为“低 - 高”电平对，而“高 - 高”电平对和“低 - 低”电平对是没有被使用的，所以可以用这两个电平进行帧定界。

编码方式详见 编码和调制。

2 - 差错控制

分类

• 检错编码：奇偶校验码、循环冗余码
• 纠错编码：海明码

奇偶校验码

奇偶校验码（Parity Check Code）是一种简单高效的错误检测机制，广泛应用于数据传输和存储系统中，用于发现单比特错误。其核心思想是通过添加一个校验比特（parity bit），确保数据中“1”的总数符合特定的奇偶规则。

奇偶校验码有两种常见的类型：奇校验和偶校验。

1. 奇校验（Odd Parity）：
   • 校验比特的值使数据（包括校验比特）中“1”的总数为奇数。
   • 例如，若原始数据“1”的个数为偶数，校验比特设为 1；若为奇数，设为 0。
   • 若接收端检测到“1”的总数为偶数，则说明传输中存在错误。
2. 偶校验（Even Parity）：
   • 校验比特确保数据中“1”的总数为偶数。
   • 例如，若原始数据“1”的个数为奇数，校验比特设为 1；若为偶数，设为 0。
   • 若接收端检测到“1”的总数为奇数，则表明数据出错。

奇偶校验码的 工作原理 如下：

• 发送端：根据奇校验或偶校验规则，计算原始数据中“1”的个数，设置校验比特，并将数据连同校验比特一起发送。
• 接收端：检查接收到的数据（包括校验比特）中“1”的总数是否符合预设的奇偶规则。若不符合，说明传输过程中可能发生了单比特错误。

奇偶校验的工作原理是发送端计算数据中所有比特的总数，并根据所选的奇偶性规则设置校验比特的值。接收端在接收数据后再次计算所有比特的总数，包括校验比特，然后检查总数是否满足所选的奇偶性规则。如果总数不符合规则，接收端将检测到错误。

循环冗余码

循环冗余校验（CRC）是一种常用的数据完整性校验方法，主要用于数据传输的错误检测。CRC 的核心思想是将数据看作多项式的系数，并用特定的生成多项式进行除法操作，得到的余数即为 CRC 值。

校验流程

CRC 校验大致流程如下：

• 生成多项式：CRC 的核心是一个生成多项式，通常用二进制表示。这个多项式是事先定义好的，并且在发送端和接收端都必须知道。
• 帧校验码计算：为了计算 CRC 校验码，发送端将数据帧和生成多项式进行除法运算，得到余数，然后将余数附加到数据帧的末尾。如果生成多项式是 n 位长，那么 CRC 校验码将是 n-1 位长。
• 传输：将 CRC 校验码附加到数据帧的尾部，发送至接收端。
• 接收端校验：接收端接收到数据帧后，也执行相同的 CRC 校验操作。它将接收到的数据帧与生成多项式进行除法运算，得到一个余数。如果余数为零，表示数据帧没有错误。如果余数不为零，表示数据帧存在错误。

实例

假设我们要发送的数据是：1010001101

我们选择的生成多项式是：110101，对应的是 $x^5 + x^4 + x^2 + 1$

发送方操作：

1. 为了进行校验码计算，首先在原始数据的尾部添加 k−1 个零（其中 k 是生成多项式的位数，这里是 4），所以数据变成了：1010001101 00000
2. 使用生成多项式除以这个新的数据。实际上，我们使用二进制的异或操作来进行模 2 除法。
3. 计算得到的余数就是 CRC。

              110101011
       ------------------
110101 | 101000110100000
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101100
                110101
                ------
                 110010
                 110101
                 ------
                   01110

将计算得到 CRC 01110 添加到数据后面一起发送，接收方接收到的数据为 101000110101110

接收方接收到数据后进行校验，计算过程如下：

              110101011
       --------------------------------------
110101 | 101000110101110
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101111
                110101
                ------
                 110101
                 110101
                 ------
                      0

计算得到余数为零，表示数据帧没有错误。

海明码

海明码（Hamming Code）是一种用于错误检测和纠正的编码方案，通常用于数据传输和存储系统中。它的主要目标是检测和纠正数据中的单比特错误。

海明码的核心思想是在数据位之间插入一定数量的校验位（也称为奇偶校验位），使得每个校验位都负责检查一组特定的位。校验位的数量取决于数据位的数量，并且它们的位置通常是 2 的幂次（即第 1 位、第 2 位、第 4 位……）。

生成过程

以一个 实例 说明海明码的 生成和纠正 过程：

• 步骤 1：确定校验位数量

假如我们的数据是 $1011$ ，也就是 $4$ 位。根据海明码的原则，我们需要确定足够的校验位 $r$ 来满足以下条件：

$2^r \ge k + r + 1$

对于 $k = 4$ （数据位），我们找到最小的 $r$ 为 $3$

• 步骤 2：放置校验位和数据位

首先将校验位（ $p$ ）插入到数据位中的适当位置。校验位下标是 $2$ 的幂（ $1, 2, 4, 8, …$ ）。

• 第 $1 (2^0)$ 位：校验位 $p_1$
• 第 $2 (2^1)$ 位：校验位 $p_2$
• 第 $4 (2^2)$ 位：校验位 $p_3$

然后再放置剩余的数据位 $d$ ：

• 第 $3$ 位：数据位 $d_1$
• 第 $5$ 位：数据位 $d_2$
• 第 $6$ 位：数据位 $d_3$
• 第 $7$ 位：数据位 $d_4$

• 步骤 3：计算校验位

首先给出位置下标的二进制表示：

• $p_1 $ 检查位置 $1$ 、 $3$ 、 $5$ 、 $7$ 的位（最低位为 1） 。所以 $p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0$ ，所以 $p_1 = 0$ 。
• $p_2 $ 检查位置 $2$ 、 $3$ 、 $6$ 、 $7$ 的位（次低位为 1）。这些位的异或值为 $p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1$，所以 $p_2 = 1$ 。
• $p_3 $ 检查位置 $4$ 、 $5$ 、 $6$ 、 $7$ 的位（最高位为 1） 。这些位的异或值为 $p_3 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0$，所以 $p_3 = 0$ 。

• 步骤 4：生成海明码

所以， $1011$ 的 $(7,4)$ 海明码是 $0110011$ 。任何一位的单一错误都可以通过分析校验位来检测并纠正。

检测和纠错

还是以 上文的例子 来说明海明码检测和纠错的过程。

假设在传输过程中第二位出现了错误，接收的码变为 $0010011$ 。

首先，接收者现在要 重新计算校验位：

• $p_1$（位置 1）：检查二进制最低位为 1 的位置（1, 3, 5, 7），即 $p_1, d_1, d_2, d_4$
  • $p_1’ = 0 \oplus 1 \oplus 0 \oplus 1 = 0$
  • 接收到的 $p_1 = 0$，所以 $p_1’ = p_1$，无错误
• $p_2$（位置 2）：检查二进制第二位为 1 的位置（2, 3, 6, 7），即 $p_2, d_1, d_3, d_4$
  • $p_2’ = 0 \oplus 1 \oplus 1 \oplus 1 = 1$
  • 接收到的 $p_2 = 0$，所以 $p_2’ \ne p_2$，有错误
• $p_3$（位置 4）：检查二进制第三位为 1 的位置（4, 5, 6, 7），即 $p_3, d_2, d_3, d_4$
  • $p_3’ = 0 \oplus 0 \oplus 1 \oplus 1 = 0$
  • 接收到的 $p_3 = 0$，所以 $p_3’ = p_3$，无错误

可以看到有错误发生，接下来需要 生成错误模式：

$$(p_1’ \oplus p_1, p_2’ \oplus p_2, p_3’ \oplus p_3) = (0 \oplus 0, 1 \oplus 0, 0 \oplus 0) = (0, 1, 0)$$

错误模式为二进制 010，十进制值为 2，表示错误在位置 2（即 $p_2$）。

最后一步是 纠正错误：位置 2 的值 $p_2$ 从 0 翻转为 1，得到纠正后的码字：

现在，海明码回到了正确的 $0110011$ 状态。

海明距离

海明距离（Hamming Distance，也译作汉明距离）是指两个等长编码（码字）之间对应位置上不同比特的个数。它是衡量编码差异的指标，用于分析编码集的错误检测和纠正能力。

编码集

编码集 是指在数据通信或存储系统中用于表示信息的一组码字（codewords）。每个码字是一个固定长度的比特序列，设计目的是通过添加冗余比特来检测或纠正传输过程中的错误。编码集的检测和纠错能力主要由其 最小海明距离 决定：

最小海明距离是编码集中任意两个不同码字之间海明距离的最小值，记为 $d$。它反映了编码集的“分散性”：$d$ 越大，码字之间的差异越大，编码集的错误检测和纠正能力越强。

最小海明距离为 $d$ 的编码集具备如下能力：

• 检错能力：最多可以检测 $d-1$ 位错误。
• 纠错能力：最多可以纠错 $\lfloor (d - 1) / 2 \rfloor$。

3 - 流量控制

停等协议

停等 (Stop-and-Wait) 是一种基础的自动重传请求 (ARQ) 协议。其基本思想是在发送每个数据帧后都停下来，等待接收方的确认。只有在收到确认后，发送方才会继续发送下一个帧。由于这种方法在任何时刻只允许一个帧在传输中，因此它被称为“停等”。

过程关键：

1. 发送数据：发送方发送一个数据帧到接收方，并启动一个计时器等待确认。
2. 等待确认：发送方在发送数据帧后处于等待状态，直到接收到确认或计时器到期。
3. 确认的接收：接收方在收到数据帧后，检查其完整性（例如通过校验和）。如果数据帧正确，接收方会发送一个确认帧回到发送方。
4. 计时器到期：如果发送方的计时器在收到确认之前到期，发送方会假设数据帧丢失或确认丢失，并重新发送数据帧。然后再次启动计时器。

回退 N 帧

在 回退 N 帧（GBN, Go Back N）协议中，发送方可以连续发送多个帧，而不需要等待每个帧的确认。但是，发送方需要为每个帧维护一个计时器。如果一个帧的计时器到期而没有收到确认，发送方会重新发送该帧及其之后发送的所有帧。

过程关键：

1. 窗口大小：在 GBN 中，若帧序号的比特数为 $n$，则发送窗口的最大值为 $2^n - 1$，接受窗口的大小为 $1$。
2. 发送过程：发送方连续发送窗口内的帧，每发送一个帧，都会为其启动一个计时器。
3. 接收过程：接收方只接收期望的帧序号。如果接收到的帧是期望的，它会发送一个确认。如果接收到的帧不是期望的（可能是由于前面的帧丢失），它会丢弃该帧并重新发送对上一个正确接收的帧的确认。
4. 超时和重传： 发送方通常只为 最早发送但未确认的帧（窗口内的第一个未确认帧）设置一个单一的超时定时器。 如果计时器到期，该帧及其之后发送的所有帧都会被重传。重传的原因是，如果一个帧丢失，后续的帧虽然可能已经到达接收方，但由于接收方的窗口大小为 1，它们会被丢弃。
5. 滑动窗口：当发送方收到一个帧的确认，它知道该帧及其之前的所有帧都已正确接收。于是，它会将窗口向前滑动，从而可以发送新的帧。

通过 GBN, SR 交互演示 你可以更好理解 GBN、SR 的过程。

选择性重传

选择性重传 (SR，Selective Repeat）是另一种自动重传请求 (ARQ) 协议，它旨在解决回退 N 帧协议在高误码率环境下的效率问题。与 Go-Back-N 不同，Selective Repeat 只重传那些确实丢失的帧，而不是所有之后的帧。这使得 SR 在高误码率环境下比 GBN 更为高效。

过程关键：

1. 窗口大小：在 SR 中，一般发送窗口和接受窗口大小一致，若帧序号的比特数为 $n$，则窗口大小最大为 $2^{n-1}$。
2. 发送过程：发送方连续发送窗口内的帧，并为每个发送的帧启动一个计时器。
3. 接收过程：接收方接收所有在其窗口范围内的帧，并为正确接收的每个帧发送确认。接收到的帧可能是乱序的，但接收方可以缓存这些乱序的帧，直到可以按正确的顺序将其传递给上层。
4. 超时和重传：如果发送方的某个帧的计时器到期，只有这个特定的帧会被重传，而不是所有的帧。这是 SR 与 GBN 的主要区别。
5. 滑动窗口：发送方和接收方的窗口都是动态移动的。当发送方收到一个帧的确认时，它会尝试滑动其窗口以发送新的帧。同时，接收方在将帧按正确顺序传递给上层后，也会滑动其窗口。
6. 处理冲突的确认：考虑到网络的延迟，发送方可能在超时并重传一个帧后才收到其早期版本的确认。为了处理这种情况，SR 协议需要具有识别和丢弃重复确认的机制。

对比

停等协议（Stop-and-Wait）、GBN（Go-Back-N）、SR（Selective Repeat）是计算机网络中用于可靠数据传输的三种流量控制和错误处理协议。它们的主要目标是确保在不可靠的通信信道上的数据传输的可靠性。

重点注意接收方和发送方的窗口大小范围。

窗口大小限制

$$\text{发送窗口大小} + \text{接受窗口大小} \le 2^n$$

滑动窗口协议是计算机网络中用于控制传输层数据流的一种机制。在这种协议下，发送窗口和接收窗口的大小有一个重要的限制，即它们的和不能超过序列号空间的大小。序列号空间是由能够用于标识帧的序列号的总数确定的，这通常是由序列号的位数决定的。

对于一个使用了 $n$ 位序列号的协议，序列号的范围是从 $0$ 到 $2^n-1$ 。因此，整个序列号空间的大小是 $2^n$ ，这意味着理论上最多可以有 $2^n$ 个不同的帧在传输中被唯一区分。

这个限制的主要原因是防止所谓的“序列号回绕”（Sequence Number Wraparound）。如果发送窗口和接收窗口的大小之和大于序列号空间的大小，那么就可能发生一个新的帧使用了一个老的、已经被使用的序列号，但是该帧可能还在网络中传输或者被延迟。接收方将无法区分这是一个新的帧还是重复的帧。

信道利用率

在 ARQ 协议中，信道利用率（也叫做链路利用率）是指信道用于传输有效数据的效率，通常定义为 成功传输数据的时间占总传输时间的比例。它反映了协议在给定信道条件下的性能，是评估 ARQ 协议效率的重要指标。

信道利用率 $U$ 可以表示为

$$U = \frac{T_{data}}{T_{total}}$$

其中：

• $T_{data}$：成功传输有效数据的时间。
• $T_{total}$：总时间，包含数据传输、确认、重传以及等待。

一般情况

对于 ARQ 协议，假设信号传播时间为 $T_p$，一个数据帧的传输时间为 $T_d$，一个确认帧的传输时间为 $T_a$，发送窗口的最大值为 $N$，信号往返时间 $RTT = 2 \cdot T_p$。

在此情况下，信道利用率 $U$ = 发送数据的时间 / 从发送第一个帧的时间到收到第一个确认帧的时间：

$$U = \frac{N \cdot T_d}{RTT + T_d + T_a}$$

停等协议

对于停等协议，信道利用率为

$$U = \frac{T_d}{RTT + T_d + T_a}$$

连续 ARQ 协议

对于使用了滑动窗口的协议（比如回退 N 帧和选择性重传），一次性可以传输 $N$ 个数据帧，信道利用率为

$$U = \frac{N \cdot T_d}{RTT + T_d + T_a}$$

注意有些时候确认帧比较小，在这种情况下确认帧传输时间 $T_a$ 可以忽略。

此外，$U \le 1$，所以当 $N \cdot T_d > RTT + T_d + T_a$ 时，信道利用率 $U = 1$。

4 - 介质访问控制

共享介质

在介绍 MAC 概念之前，必须要说明一下共享介质的概念。

在一个网络环境中，多个设备可能需要同时访问同一个物理介质来发送数据，这个介质可以是电缆、光纤或者无线信道。

当设备发送数据时，数据包会在整个介质上传播，所有连接到该介质的设备都可以接收到数据包。如果多个设备同时发送数据，介质上的数据信号就会相互冲突进而导致错误。

所以 MAC 协议确保了 共享介质上的 有效、公正且有序的数据传输。

MAC 方式总结

介质访问控制（MAC，Media Access Control）可以分为 信道划分 以及 随机访问 两种大方向。

也叫做多路复用，在一条传输介质上同时传输多个不同种类的信号（种类可以根据不同的参数进行划分），这样不同的设备可以发送特定类型的信号，并且不同信号之间相互不干扰，信道划分 访问控制可以分为以下几种：

• FDM：频分多路复用
• TDM：时分多路复用
• WDM：波分多路复用
• CDM：码分多路复用

指多台设备共享同一个通信介质时，它们可以随机地尝试发送数据，而不需要事先协调，当发生冲突后再做后续的协调，以保证不会接收到错误的数据。

• ALOHA
• CSMA
• CSMA/CD
• CSMA/CA

多路复用

多路复用（Multiplexing）是一种技术，用于在同一传输介质上同时传输多个信号，包含频分多路复用（FDM）、时分多路复用（TDM）、波分多路复用（WDM）和码分多路复用（CDM）四种。

FDM

频分多路复用（FDM）将可用带宽划分为若干个不重叠的频段，每个信号占用一个频段。各个信号可以同时传输，但彼此之间不会干扰，因为它们占用不同的频率。

FDM 在传统的模拟电话系统和广播中广泛使用。

TDM

时分多路复用（TDM）将时间划分成若干个时隙，每个信号在不同的时隙中传输。所有信号在时间上轮流使用同一传输介质。

TDM 常用于数字通信系统，如数字电话网络。

WDM

波分多路复用（WDM）是 FDM 的一种应用，主要用于光纤通信。它将光纤的可用带宽划分为多个波长（颜色），每个信号占用一个波长。

WDM 技术可以大幅增加光纤的通信容量，广泛应用于长距离和高速光纤网络。

CDM

码分多路复用（CDM）使用不同的编码来区分各个信号。所有信号可以在同一频带上同时传输，但通过使用不同的编码序列来避免相互干扰。

虽然 CDM 的概念可以用在许多不同的传输系统中，但在实践中，它主要作为 码分多址（CDMA，Code Division Multiple Access）的基础技术。

在 CDMA 中，每一个比特时间划分为 m 个短的时间槽，称为码片（chip），每个站被指派一个惟一的 m bit 码片序列 (chip sequence) 。

• 如果发送比特 1，则发送自己的 m 位码片序列。
• 如果发送比特 0，则发送该码片序列的二进制反码。

简单理解就是，A 站向 C 站发出的信号用一个向量来表示，B 站向 C 站发出的信号用另一个向量来表示，两个向量要求相互正交。向量中的分量，就是所谓的码片。

当两个或多个站点同时发送时，各路数据在信道中线性相加。为了从信道中分离出各路信号，要求各个站点的码片序列相互正交。

令向量 $S$ 表示站 S 的码片向量，令 $T$ 表示其他任何站的码片向量。两个不同站的码片序列正交，就是向量 $S$ 和 $T$ 的规格化内积（inner product）都是 0：

$$S \cdot T = \frac{1}{m} \sum_{i=1}^{m}{S_i T_i} = 0$$

任何站的码片向量和该码片反码的向量的规格化内积都是 -1：

$$S \cdot \overline{S} = \frac{1}{m} \sum_{i=1}^{m}{S_i \cdot \overline{S_i}} = 0$$

举个实际的例子来说明。令向量 $S$ 表示 A 站的码片向量，$T$ 表示 B 站的码片向量。假设 A 站的码片序列被指派为 00011011，则 A 站发送 00011011 就表示发送比特 1，发送 11100100 就表示发送比特 0。为了方 便计算，将码片中的 0 写为 -1，将 1 写为 +1，因此 A 站的码片序列是 (-1 -1 -1 +1 +1 -1 +1 +1)。

令 $T$ = (-1 -1 +1 -1 +1 +1 +1 -1)，可以观察到，不管是 $T$ 还是 $\overline{T}$，都有四个码片的值与 $S$ 相反，所以 $S \cdot T = 0$。

当 A 站向 C 站发送数据 1 时，就发送了向量 (-1 -1 -1 +1 +1 -1 +1 +1)。

当 B 站向 C 站发送数据 1 时，就发送了向量 (+1 +1 -1 +1 -1 -1 -1 +1)。

两个向量在公共信道上叠加，实际上是线性相加，得到 $S + \overline{T}$ = (0 0 -2 2 0 -2 0 2)。

ALOHA 协议

ALOHA 协议是一种早期开发的随机访问协议，用于在共享信道上传输数据。ALOHA 有两种基本类型：纯 ALOHA 和时隙 ALOHA。

• 纯 ALOHA：用户可以在任何时间发送数据包。由于没有时间同步，数据包之间容易发生冲突。
• 时隙 ALOHA：时间被分成离散的时隙，用户只能在时隙的开始发送数据包。这种方法通过同步发送时间，减少了冲突的概率。

纯 ALOHA

纯 ALOHA（Pure ALOHA）是一种简单的随机接入协议，允许用户在任意时刻发送数据包，而无需对时间进行任何同步或分时。 由于用户可以在任何时间发送数据包，数据包之间可能会发生冲突。

工作原理：

• 用户随时发送数据包。
• 如果数据包成功到达接收端，则传输完成。
• 如果发生冲突（即两个或多个用户同时发送数据包），相关用户需要等待随机的时间后重传。

时隙 ALOHA

时隙 ALOHA（Slotted ALOHA）在纯 ALOHA 的基础上引入了时间同步，将时间划分为一系列等长的时隙。用户只能在时隙的开始发送数据包。

工作原理：

• 时间被划分为等长的时隙。
• 用户在时隙的开始时发送数据包。
• 如果一个时隙内只有一个用户发送数据包，则传输成功。
• 如果多个用户在同一时隙发送数据包，发生冲突，相关用户等待随机时间后重传。

CSMA 协议

CSMA（Carrier Sense Multiple Access）的中文叫做 载波监听多路访问，理解 CSMA 的关键在于理解它的名称中的两个部分：载波监听 以及 多路访问：

• 载波监听（Carrier Sense）：因为 CSMA 是随机访问介质控制的一种方式，所以在发送数据前，必须确定当前通信介质中没有其他设备正在发送数据。所以载波监听可以被理解为以太网口内部芯片自带的一种功能，具体而言就是一种可以监听 信道在当前位置是否有数据传输的 的一种功能。
• 多路访问（Multiple Access）：多个设备可以访问同一个通信介质。这意味着在任何给定时间，任何设备都可以尝试发送数据。

所以 CSMA 可以理解为 通过 载波监听 避免冲突，进而实现共享介质上的 多路访问。

以下图为例，A、B、C、D 分为是连接到同一共享介质上的不同设备，当 A 开始发送数据时，B、C、D 分别会在不同的时刻监测到信号，具体的时刻为 设备与 A 之间的距离 / 信号传播速度。

这里需要深入理解 传播时延和传输时间 这两个概念：

• 传输时延（propogation time） = 距离 / 信号传播速度
• 传输时间（transmission time） = 数据大小 / 数据传输速率

CSMA 的问题在于它无法处理碰撞，当一个设备监听到当前介质中无信号时，它就可以发送数据，但监听得到的结果可能是 “假结果”。因为有可能其他设备已经发送信号了，只是信号由于传播时延还没有到达当前设备。

所以假设当前设备监听得到了“假结果”，那么此时发送数据后介质上就会发生冲突。比如假设 C 在 A 的信号到来之前检测得到假结果，然后发送帧，这个时候信道中就会出现冲突：

CSMA 也 根据其在信道空闲时的行为分为三种类型，如下所示：

CSMA/CD 协议

CSMA/CD（CSMA with Collision Detection，载波监听多路访问/碰撞检测）是 CSMA 的一种拓展，在了解这个知识之前，请确保你已经理解了什么是 CSMA 中的 CS（Carrier Sense 即 载波监听），以及什么是 CSMA 中的 MA（Multiple Access 即 多路访问）。

CSMA/CD 比 CSMA 多出一个 CD（Collision Detection 即 碰撞检测）的功能。 在上文中我们提到，CSMA 中监听到信道空闲可能是“虚假的”，所以在 CSMA 发送数据后介质中也许会发生冲突，但 CSMA 只能依靠非常原始的方案处理冲突。

CSMA/CD 就高级一些，在发送数据期间，我们刚刚提到的 监测器件（Carrier，就是 CSMA 中 C 的简称）会一直监听有没有冲突发生， 如果有冲突的话，就等待一段随机的时间，然后重试以上过程，并且发送一个特殊信号告诉其他设备发生了冲突。

以上图为例，假设 A 向 D 发送一段数据，C 向 A 发送一段数据，我们可以观察到：冲突发生的时间点 和 设备检测到冲突的时间点是不同的。 当 A 和 C 检测到冲突发生时，它们会立即停止发送，并且发送信号通知其他设备该次碰撞：

流程

CSMA/CD 的工作流程如下：

1. 准备发送：适配器从网络层获得一个分组，封装成帧，放入网络适配器缓存准备发送。
2. 检测信道：监听信道是否空闲，若信道空闲，则开始发送该帧；若信道忙，则持续检测直至信道空闲。
3. 在发送过程中，适配器仍然持续检测信道。这里只有如下两种可能。
   • 发送成功：在争用期内一直未检测到冲突，该帧肯定能发送成功。
   • 发送失败：在争用期内检测到冲突，此时立即停止发送，并且广播碰撞通知信号。接着适配器执行指数退避算法， 等待一段随机时间后返回到步骤 2。若重传 16 次仍不能成功，则停止重传并向上报错。

指数退避算法

在随机访问网络中，当冲突发生后，设备需要等待一段时间后重试发送，以避免再次冲突。 指数退避算法（Exponential Backoff Algorithm）通过动态调整等待时间，减少连续冲突的概率，提高网络效率。

其核心思想是当冲突发生时，设备随机选择一个等待时间，并在每次冲突后成倍增加等待时间范围，以降低后续冲突的可能性。

指数增长规则 如下：

• 如果是第 $k$ 次重传尝试（通常从 $k=1$ 开始），则从以下范围随机选择等待时间槽（slot）的个数：

$$[0, 2^k - 1]$$

• 每个时间槽长度为一个基本单位（如 51.2 微秒，以太网中一个“slot time”）。
• 最大的 $k$ 通常是有限制的，例如以太网中最大为 10（即窗口最多增长到 $2^{10} - 1 = 1023$）

如果尝试达到一定次数仍冲突，放弃传输并上报错误。

举个实际例子：

假设某设备在尝试发送时检测到冲突：

• 第 1 次重试：在 [0, 1] 中随机选择一个时间槽（即可能等待 0 或 1 个 slot time）。
• 第 2 次重试：在 [0, 3] 中随机选择（0~3 个 slot）。
• …
• 第 10 次重试：在 [0, 1023] 中随机选择。
• 第 16 次重试后仍失败：报错放弃。

限制条件

CSMA/CD 可以使用的限制条件：帧的传输时延至少要两倍于信号在总线上的传播时延

为了在一个帧的发送过程中检测到冲突，发送站必须在整个帧发送完毕之前收到冲突信号。如果一个站点在发送完整个帧后才能检测到冲突，那么冲突的数据就已经在网络上传输完毕了，这样无法避免数据的损坏。

这种机制是基于这样一个事实：冲突的信号需要在网络上传播并被发送站检测到，发送站才会知道发生了冲突。因此，如果帧的传输时延太短，发送站可能在信号冲突返回之前就已经发送完毕了帧，导致无法检测到冲突。为了确保冲突能够被检测到，必须要求帧的传输时间足够长，以便在帧发送结束前，冲突信号能够返回到发送站。

CSMA/CA 协议

CSMA/CD 适用于以太网（使用有线连接的局域网），但在无线局域网（WLAN，Wireless LAN）中无法直接使用 CSMA/CD，主要有以下原因：

1. 无线设备不能同时“听”和“说”：无线收发器在发送数据时，无法同时监听信道来判断是否发生碰撞。
2. 信道干扰比有线环境严重：无线信号受环境干扰更大，误判空闲或碰撞的概率更高。
3. 隐藏节点问题（隐蔽站）：假设 A 和 C 两台无线设备都想给 B 发送数据，但 A 和 C 彼此“看不到”，只看到 B 是空闲的。结果就是 A 和 C 同时给 B 发送，发生碰撞，但它们却以为没事。

为此，802.11 标准定义了广泛用于无线局域网的 CSMA/CA 协议，它对 CSMA/CD 协议进行修改，将冲突检测改为冲突避免 (Collision Avoidance,.CA)。“冲突避免”并不是指协议可以完全避免冲突，而是指协议的设计要尽量降低冲突发生的概率。

流程

1. 侦听信道（Carrier Sense）
   • 设备在发送数据前通过物理侦听（检查信道电信号）和虚拟侦听（NAV，网络分配向量，记录信道占用时间）判断信道是否空闲。若信道忙碌，设备进入退避机制，等待随机时间后再次侦听，以降低碰撞风险。
2. 发送请求（RTS，Request to Send）
   • 若信道空闲超过特定时间（DIFS，分布式帧间间隔），设备可发送 RTS 帧，通知其他设备其传输意图及所需时间。RTS 帧是可选的，主要用于较大数据包或高干扰环境。
3. 清除发送请求（CTS，Clear to Send）
   • 接收设备在确认信道空闲后（等待 SIFS，短帧间间隔），回复 CTS 帧，确认传输许可并通知附近设备保持沉默。CTS 帧增强了信道保护，减少隐藏节点问题。
4. 数据传输
   • 发送设备收到 CTS 帧后（等待 SIFS），开始传输数据帧。其他设备通过 NAV 设置避免干扰，确保信道专用于当前传输。
5. 确认帧（ACK，Acknowledgment）
   • 接收设备成功接收数据后（等待 SIFS），发送 ACK 帧确认。若发送端未收到 ACK（可能因碰撞或干扰），启动重传机制，重新执行上述步骤。

根据以上过程我们可以观察到 CSMA/CA 的一些关键特点：

• 碰撞避免：CSMA/CA 通过侦听、RTS/CTS、退避机制预测和确认机制并避免碰撞，而非像 CSMA/CD（以太网）那样检测碰撞后处理，适合无线网络因其难以实时检测碰撞。
• 隐藏节点问题：两设备因距离远无法互相侦听，可能同时发送数据导致碰撞。RTS/CTS 机制 通过通知附近设备解决此问题。

IFS

由于无线信道的可靠程度不如有线网络，所以 802.11 标准使用 停等方案，即站点每通过无线局域网发送完一帧，就要在收到对方的确认帧后才能继续发送下一帧。

为了尽量避免冲突，802.11 标准规定，所有站完成发送后，必须等待一段很短的时间（继续监听）才能发送下一帧。这段时间称为帧间间隔（InterFrame Space，IFS）。帧间间隔的长短取决于该站要发送的帧的类型，这些类型用于优先级管理，确保关键帧

802.11 标准使用了下列三种 IFS：

• SIFS（Short IFS）：当设备发送一个数据帧后，它会等待 SIFS 时间，以便快速发送另一个数据帧或发送 ACK（确认）帧作为响应。
• DIFS（Distributed IFS）：当设备想要发送数据时，它首先侦听信道，如果信道被其他设备占用，则等待一个 DIFS 的时间，然后再次侦听信道。
• PIFS（Point Coordination IFS）：中心协调器使用 PIFS 来在其他设备竞争前抢占信道。

NAV

在 CSMA/CA 中，网路分配向量（NAV）是用来告诉其他节点预计要占 用无线媒体多长时间的一种机制。

在发送 RTS（请求发送）和 CTS（清除发送）帧时，发送节点会 在帧头中包含一个持续时间字段，这个字段表示从发送当前帧到接收到最后一个 ACK 帧所需的时 间。

其他节点在收到 RTS 或 CTS 帧时，会根据帧中声明的 预计占用时间，在自己的 NAV 计时器上设定一个倒计时。 在 NAV 倒计时期间，设备会 认为信道被占用，即使它侦听到的无线信号很弱或根本没检测到数据，也不会尝试发送，以避免干扰正在通信的设备。

简单来说，NAV 就像设备内部的一个“占用表”，告诉自己：别人正在用，等一会再发。

5 - 局域网和广域网

局域网

局域网（Local Area Network，LAN）是一种覆盖范围较小、用于连接同一物理地点（如家庭、办公室、学校或企业内）的计算机和其他设备的计算机网络。

特性

局域网的特性主要由三个要素决定：拓扑结构、传输介质 和 介质访问控制方式，其中介质访问控制方式是最关键的因素，它决定了局域网的主要技术特性。

常见的局域网 拓扑结构 主要包括以下四类：

• 星形结构
• 环形结构
• 总线形结构
• 星形与总线形结合的复合型结构

在 传输介质 方面，局域网可以采用铜缆、双绞线和光纤等多种介质，其中双绞线是当前的主流传输介质。

局域网常用的 介质访问控制方法 包括 CSMA/CD 协议、令牌总线协议和令牌环协议。 其中，CSMA/CD 协议和令牌总线协议主要应用于总线形局域网，而令牌环协议则主要用于环形局域网。

实现

局域网主要包含三种实现：

• 以太网（目前使用范围最广）。逻辑拓扑是总线形结构，物理拓扑是星形结构。
• 令牌环（Token Ring，IEEE802.5）。逻辑拓扑是环形结构，物理拓扑是星形结构。
• FDDI（光纤分布数字接口，IEE802.8）。逻辑拓扑是环形结构，物理拓扑是双环结构。

以太网

在实际的局域网应用中，由于以太网占据垄断地位，所以基本上成为了局域网的代名词， 需要对局域网的概念有深入了解。

传输介质

以太网常用的传输介质有 4 种：粗缆、细缆、双绞线和光纤，这里需要熟练掌握它们的英文名， 常在选择题中出现：

注意上述传输介质的英文名称其实是挺有讲究的：

首先是前缀的数字，代表的是传输介质的速率，10 代表 10 Mbps，100 代表 100 Mbps，注意这里是 Mbps 而不是 MB/s。

其次是中间的 base 一次，代表基带传输（Baseband），基带与宽带（broadband）相对应。基带表示直接传输原始数字信号，不调制；宽带代表使用模拟调制技术传输多个频道信号，常见于有线电视等。

最后是后缀的英文字母，代表的传输介质的类型：

• 注意字母 T 是 twisted pair 的首字母，含义是双绞线。
• FL 是 Fiber optic 的缩写，含义是光纤。

帧格式

如上图所示，以太网帧格式从逻辑上可以分为物理层控制字段、帧首部、数据负载、差错校验字段这四个部分，每个字段的具体说明如下所示：

• 物理层控制字段
  • 前导码（Preamble）：7B
    • 由 7 字节的交替的 1 和 0 位组成，用于同步接收方的时钟。
  • 帧开始分隔符（Start of Frame Delimiter, SFD）：1B
    • 通常为 10101011，标志帧的开始。
• 帧首部：固定为 14B
  1. 目的地址（Destination MAC Address）：6B
     • 指定帧的接收者的物理 MAC 地址。
  2. 源地址（Source MAC Address）：6B
     • 指定帧发送者的物理 MAC 地址。
  3. 类型/长度字段（Type/Length）：2B
     • 如果值大于或等于 0x0600（1536），则表示帧携带的数据的类型（例如 IPv4、IPv6、ARP 等）。
     • 如果值小于或等于 0x05DC（1500），则表示数据字段的长度。
• 负载
  • 数据和填充（Data and Padding）：范围为 46-1500B
    • 携带帧的有效载荷，即要传输的数据。
    • 如果数据少于 46 字节，则需要填充，确保数据字段的最小长度为 46 字节。
• 差错校验字段
  • 帧校验序列（Frame Check Sequence, FCS）：4 字节：
    • 一个循环冗余校验（CRC）值，用于错误检测。接收方计算帧的 CRC，并与这个字段进行比较，以确定帧是否在传输过程中被损坏。

无线局域网

帧格式

802.11 帧共有三种类型，即数据帧、控制帧和管理帧。数据帧的格式如图 3.28 所示。

802.11 数据帧由以下三部分组成：

• MAC 首部，共 30 字节。帧的复杂性都在 MAC 首部。
• 帧主体，即帧的数据部分，不超过 2312 字节。
• 帧检验序列 FCS 是 MAC 尾部，共 4 字节。

可以观察到，802.11 帧首部中字段很多，但是其实主要考察的就是个别字段。

其中最重要的是 4 个地址字段（都是 MAC 地址）。这里仅讨论前三个地址（地址 4 用于自组网络）。 这三个地址的内容取决于帧控制字段中的“去往 AP”和“来自 AP”这两个字段的数值，如下表所示：

💡核心记忆点：

• 地址 1：谁接收这帧（无线信号的接收者）
• 地址 2：谁发的这帧（无线信号的发送者）
• 地址 3：通信的最终目标或源（真实的目的地或来源）

VLAN

VLAN（Virtual Local Area Network）虚拟局域网，是通过逻辑划分的方式，把一个物理局域网拆分成多个独立的子网。

打个比方：一家公司只有一个办公室（一个交换机），但希望让财务部、技术部和人事部各自的数据隔离，互不干扰。VLAN 就像是在这一个办公室里，用“看不见的墙”把它们隔开，互相听不到对方说话。

⚙️ 那么 VLAN 是如何实现的呢？

VLAN 是通过 交换机 和 VLAN 标签（Tag）实现的。简单来说：

• 普通交换机：看网线在哪个口（port）来转发数据。
• 支持 VLAN 的交换机：会在数据包中加上 VLAN 标签，按“部门”来转发。

802.3c 标准定义了支持 VLAN 的以太网帧格式的扩展。它在以太网帧中插入一个 4 字节的 标识符（插在源地址字段和类型字段之间），称为 VLAN 标签，用来指明发送该帧的计算机属于 哪个虚拟局域网。插入 VLAN 标签的帧称为 802.1Q 帧，如下图所示。

其中 VID（VLAN ID）为 12 位，一个 VLAN 交换机最多支持 4096 个 VLAN。

📦 VLAN 示例： 假设有三台电脑：

• PC1：财务部，接在 VLAN 10
• PC2：技术部，接在 VLAN 20
• PC3：人事部，接在 VLAN 30

它们都连在一台交换机上，如果没有 VLAN，三者可以互相通信。如果配置了 VLAN：

• PC1 发的广播，只有 VLAN 10 内的设备能收到。
• PC2 和 PC3 不会收到 PC1 的数据，除非通过路由器（或者三层交换机）跨 VLAN 通信。

广域网

HDLC 协议

HDLC（High-Level Data Link Control，高级数据链路控制）是一种 面向比特（bit-oriented） 的 数据链路层协议，用于在点对点或点对多点通信中提供可靠的数据传输。

HDLC 几个特点可以被简单总结为：面向比特、面向连接、提供可靠传输。

需要注意的是 HDLC 使用 零比特填充法 来组帧。

PPP 协议

PPP（Point-to-Point Protocol）是一种数据链路层协议，用于在两个点对点连接的网络之间传输数据。PPP 最初是为拨号连接设计的，但它后来被广泛用于建立各种类型的点对点连接，包括 DSL（数字用户线路）、ISDN（综合业务数字网）和串口连接等。

6 - 数据链路层设备

交换机

交换机（Switch）是网络中用于连接设备并转发数据帧的二层设备。它通过分析数据帧中的 MAC 地址，将数据帧从接收端口精准转发到目标设备所在的端口。相比集线器，交换机只将数据帧发送到必要端口，避免广播到整个网络，显著降低碰撞域，提升带宽利用率和传输速度。

转发表

转发表（也称 MAC 地址表）是交换机内部维护的一张记录表，存储了网络设备 MAC 地址与其连接端口的对应关系。每条记录通常包含以下信息：

• MAC 地址：网络设备的唯一标识。
• 端口号：设备连接的交换机端口。
• 附加信息（可选）：如 VLAN 标识或条目有效时间。

如上图所示，交换机 A 和 B 分别通过转发表记录了通往每个 MAC 地址的端口。

转发流程

交换机收到数据帧后，会根据转发表执行以下步骤：

1. 检查目标 MAC 地址：从数据帧中提取目标 MAC 地址。
2. 查询转发表：
   • 如果转发表中存在目标 MAC 地址的记录，交换机将数据帧直接转发到对应端口。
   • 如果转发表中没有目标 MAC 地址，交换机将数据帧广播到除接收端口外的所有端口（称为广播帧），以寻找目标设备。
3. 转发数据帧：根据查询结果，数据帧被发送到目标端口或广播。

交换方式

交换机的交换方式决定了 交换机在接收到数据帧后，决定如何以及何时将该帧转发到目标端口，交换方式有如下三种：

• 直通交换：交换机在接收到数据帧的前6个字节（即目的MAC地址）后，立即根据MAC地址表查找目标端口并开始转发，无需等待整个数据帧接收完成。
• 存储转发 ：交换机接收完整数据帧后，存储在缓冲区中，进行CRC（循环冗余校验）检查，确认数据帧无误后再根据MAC地址表转发。
• 碎片隔离：介于直通交换和存储转发之间，检查数据帧的前64字节（以太网最小帧长），若帧长不足64字节（碎片），则丢弃；若正常，则转发。

网桥

网桥（Bridge）的功能和交换机基本一致，两者都是二层网络设备，用于转发数据帧。网桥中也有转发表的概念，转发过程和交换机一致，这里不再赘述。

那么 网桥和交换机区别  在哪里呢？

网桥是比较早期计算机网络使用的设备，现在已经渐渐被交换机替代，两者的重要区别如下表：