Mar 16, 2026

miniyuan

数据链路层

---

数据链路层概述

网络体系结构中的位置

数据链路层的核心地位：

• 实现相邻结点之间的通信
• 网络中的主机、路由器、交换机等都必须实现数据链路层
• 不同链路可采用不同的数据链路层协议

基本术语

术语	定义
结点(node)	主机、路由器等网络设备
链路(link)	连接相邻结点之间的信道（有线/无线）
帧(frame)	数据链路层传输的基本单位

信道类型

类型	特点	协议要求
点对点信道	一对一通信	简单，无需协调
广播信道	一对多通信	需要专用共享信道协议协调发送

链路层功能

• 链路管理：建立、拆除连接（面向连接服务时必须）
• 成帧/解帧：将数据封装为帧
• 流量控制：控制发送数据量
• 差错控制：实现无差错传送
• 透明传输：希望所有数据都能原样传输，故需要区分数据信息和控制信息
• 寻址：标识收发双方

链路层子层

• 逻辑链路控制 LLC （Logical Link Control）子层；
• 介质访问控制 MAC （Medium Access Control）子层。 其中与接入到传输媒体有关的内容都放在 MAC子层，而 LLC 子层则与传输媒体无关。故 MAC 子层的协议对 LLC 来说是透明的，但是 LLC 需要识别网络层协议。

由于 TCP/IP 的统治地位，旨在为多种网络层协议提供统一接口的 LLC 子层在实际应用中变得冗余。

实现位置：网络适配器（网卡）

┌─────────────────────────────────────┐
│  application                        │
│  transport                          │
│  network                            │
│  link ←─────────────────────────┐   │
│  physical                       │   │
│      │                          │   │
│  host bus (e.g., PCI)           │   │
│      │                          │   │
│  ┌─────────────────┐            │   │
│  │  network        │←───────────┘   │
│  │  adapter card   │ controller     │
│  │  (NIC)          │ physical       │
│  └─────────────────┘ transmission   │
│      ↑                              │
│  串/并变换、数据缓存、链路层功能实现   │
└─────────────────────────────────────┘

网卡功能：

• 发送端：封装成帧、添加校验位和地址、流量控制
• 接收端：检错、地址检查、流量控制、提取数据交高层

IP 与 MAC 的关系：IP 地址由网络层使用，MAC 地址由链路层使用。ARP 协议负责 IP 到 MAC 的地址解析。但是两者不是一一对应的。

---

成帧与透明传输

封装成帧就是给数据添加首部和尾部，进行帧定界

字节计数法

直接使用头部字段标识帧字节数。但是一旦头部出错则失步。

固定帧长度

固定字符长度，如 RS232。实现非常简单，但是效率低下。

控制字符法

使用规定的字符进行帧定界，如 HDLC、PPP。但是需要处理透明传输，因为数据中可能包含规定的字符。

ASCII 码

ASCII 码分为控制字符和显示字符。若数据是 ASCII 码的，则可以直接利用特殊控制字符 SOH/EOT 进行帧定界。

解决透明传输：

• 发送端：
  • 数据中出现 SOH 或 EOT，则需在前面插入转义字符 ESC（0x1B）
  • 数据中出现 ESC，则需在前面再插入一个 ESC
• 接收端：向上层传输前删除插入的转义字符，连续的两个只删除一个

原始数据: [SOH][A][EOT][B][SOH]
发送数据: [SOH][A][ESC][EOT][B][ESC][SOH][EOT]

二进制

若数据是二进制的，则可以直接利用特殊标志 01111110 进行帧定界。

解决透明传输：

• 发送端：数据中出现5个连续1，立即填入一个0
• 接收端：数据中出现5个连续1，删除后面的0

原始数据: 01111110 (恰好为标志位)
发送数据: 011111010 (5个1后填0)

---

差错控制

基本概念

误码率 $P_b$ = 误码位数 / 发送总位数

无差错帧概率 $P_1 = (1-P_b)^L$ （$L$ 为帧长）

差错控制本质上是利用关系和数据位产生校验位，并将数据位和校验位一起编码为码字发送。接收方检查数据位和校验位的关系即可。

分类：

• 检错码：不能判断错误位的位置
• 纠错码：能够判断错误位的位置

汉明码距

定义：两个等长码字 $\mathbf{x}, \mathbf{y}$ 之间的码距 $d_H(\mathbf{x}, \mathbf{y})$ 为对应位置上不同符号的个数：

$$d_H(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{n} \mathbf{1}_{\{x_i \neq y_i\}}$$

最小码距：编码 $\mathcal{C}$ 中所有不同码字间的最小距离

$$d_{\min} = \min_{\mathbf{x} \neq \mathbf{y} \in \mathcal{C}} d_H(\mathbf{x}, \mathbf{y})$$

与检错/纠错码的关系：

如图，对于二进制数而言，码空间就是黑色的等边三角形格点，一个格点对应了一个二进制数。 而我们采用的编码 $\mathcal{C}$ 是码空间的子集，也即图中的红色格点（不一定是等距的），最小码距 $d_{\min}$ 就是红色点间的最小距离。 我们发送的码字一定是一个红色点，记为 $p$。 但是由于误码，接收方收到的码字会偏离到码空间的任一格点，误码 $n$ 位就会偏移码距 $n$，也即在圆周 $\set{\mathbf{x} | d_H(\mathbf{x}, \mathbf{p}) = n}$ 上。

故对于 编码 $\mathcal{C}$：

• 检 $e$ 个错 $\iff$ $d_{\min} \ge e+1$。 此时圆周 $\set{\mathbf{x} | d_H(\mathbf{x}, \mathbf{p}) = e}$ （图中黄色圈）不包含除 $p$ 外的红色点。
• 纠 $t$ 个错 $\iff$ $d_{\min} \ge 2t+1$。 此时圆周 $\set{\mathbf{x} | d_H(\mathbf{x}, \mathbf{p}) = e}$ （图中橙色圈）离编码 $\mathcal{C}$ 中的 $p$ 点最近。

分组码

定义：$(n,k)$ 分组码将信息序列分为 $k$ 个数据位一组，并添加校验码编码为 $n$ 位码字（$n>k$），码率 $R = k/n$。

线性分组码：码字集合构成 $\mathbb{F}_q^n$ 的 $k$ 维子空间。编码可用生成矩阵 $\mathbf{G}_{k \times n}$：

$$\mathbf{c} = \mathbf{u} \cdot \mathbf{G}$$

校验矩阵 $\mathbf{H}_{(n-k) \times n}$ 满足 $\mathbf{c} \cdot \mathbf{H}^T = \mathbf{0}$，用于译码校验。

方法汇总

方法	类型	最小码距 $d_{\min}$	能力
奇偶校验	检错码	2	检测单比特错
二维奇偶校验	纠错码	4	纠正单比特错
汉明码	纠错码	3	纠正单比特错，检测双比特错
CRC	检错码	$\ge 2$	检测 $\le r$ 位的错
校验和	检错码	—	IP/TCP/UDP使用
交织码	—	—	将突发错转为随机错

一维奇偶校验

可检错单比特。设数据位为 $d_1, d_2, \dots, d_k$（$k$ 位）。增加一个校验位 $p$。

校验位计算：

偶校验

$$p = d_1 \oplus d_2 \oplus \cdots \oplus d_k$$

其中 $\oplus$ 表示异或（模 2 加法）。

码字：

$$c_1, c_2, \dots, c_k, c_{k+1} = d_1, d_2, \dots, d_k, p$$

接收端校验：

• 若结果为 $0$：无奇数个错误（可能无错或有偶数个错误）
• 若结果为 $1$：有奇数个错误（可检错，但无法定位）

---

二维奇偶校验

可纠错单比特。设数据为 $m$ 行 $\times$ $n$ 列矩阵

数据位：

$$\begin{matrix} d_{1,1} & d_{1,2} & \cdots & d_{1,n} \\ d_{2,1} & d_{2,2} & \cdots & d_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ d_{m,1} & d_{m,2} & \cdots & d_{m,n} \end{matrix}$$

校验位计算：

行校验位计算：

$$r_i = d_{i,1} \oplus d_{i,2} \oplus \cdots \oplus d_{i,n}, \quad i = 1, 2, \dots, m$$

列校验位计算：

$$c_j = d_{1,j} \oplus d_{2,j} \oplus \cdots \oplus d_{m,j}, \quad j = 1, 2, \dots, n$$

整体校验位计算（可选）：

$$p_{\text{total}} = r_1 \oplus r_2 \oplus \cdots \oplus r_m \oplus c_1 \oplus c_2 \oplus \cdots \oplus c_n$$

也即所有数据位的异或（若行列校验均采用偶校验）。

码字：

发送时码字为 $(m+1) \times (n+1)$ 矩阵：

$$\begin{matrix} d_{1,1} & d_{1,2} & \cdots & d_{1,n} & r_1 \\ d_{2,1} & d_{2,2} & \cdots & d_{2,n} & r_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ d_{m,1} & d_{m,2} & \cdots & d_{m,n} & r_m \\ c_1 & c_2 & \cdots & c_n & p_{\text{total}} \end{matrix}$$

接收端校验：

校验结果	含义
行错、列对	行校验位本身错误
列错、行对	列校验位本身错误
行错、列错	数据位 $d_{i,j}$ 错误（可定位并纠错）
行错、列错、整体错	多处错误，无法纠正（只能检错）

---

汉明码

纠错单比特。

定义数 $r$ 在二进制下 1 的个数为 $\text{popcount}(r)$. 设码字总长度为 $n$，位置编号从 1 开始：

$$\text{Code} = \{c_1, c_2, c_3, \dots, c_n\}$$

校验位位置：

$$R = \{ r \mid \text{popcount}(r) = 1 \} = \{1, 2, 4, 8, 16, \dots, 2^{k-1}\}$$

其中 $2^{k-1} \leq n$。

数据位位置：

$$D = \{ r \mid \text{popcount}(r) \geq 2 \}$$

校验位计算：

对于校验位 $r = 2^m$（$m = 0, 1, 2, \dots$），码字在该位的值：

$$c_r = \bigoplus_{\substack{d \in D \\ (d \ \&\ 2^m) \neq 0}} c_d$$

也即所有二进制展开中包含 $2^m$ 的数据位的异或（模 2 加法）。

接收端校验：

利用收到的数据位，同理计算校验位 $r = 2^m$（$m = 0, 1, 2, \dots$）处的理论值：

$$c_r^{exp} = \bigoplus_{\substack{d \in D \\ (d \ \&\ 2^m) \neq 0}} c_d$$

然后计算：

$$e = \sum_{m=0}^{k-1} (c_r \oplus c_r^{exp}) \cdot 2^m$$

若 $e = 0$，无错误；否则第 $e$ 位出错（显然其应该在码字范围内）。

---

CRC 循环冗余校验

CRC 主要用于检错，在特定配置下可检测单比特错误、双比特错误、奇数个错误、突发错误等。其在硬件方面实现轻松（移位寄存器）。

设：

• 信息位长度：$k$ 位
• 校验位长度：$r$ 位，对应 $r$ 次生成多项式
• 码字长度：$n = k + r$

定义模 2 域上多项式与二进制数之间的双射 $\varphi$：

$$\varphi: \text{GF}(2)[x] \to \mathbb{Z}_2^\infty$$ $$\varphi\left( \sum_{i=0}^{n-1} a_i x^i \right) = (a_{n-1} a_{n-2} \cdots a_1 a_0)_2$$

记 $\varphi^{-1}$ 为其逆映射，将二进制数转换为多项式。

生成多项式：

$G(x)$ 为 $r$ 次模 2 域上的多项式（要求常数项为 1），这是收发双方提前协商好的。

$$G(x) = x^r + g_{r-1}x^{r-1} + \cdots + g_1x + 1$$

可以映射为 $r+1$ 位二进制数 $\varphi(G) = (1\ g_{r-1}\ \cdots\ g_1\ 1)_2$。

生成多项式还应当具有一定的性质，以帮助我们进行检错（见后）。

校验位计算：

$$R(x) = x^r M(x) \bmod G(x)$$

其中 $\deg{R(x)} \leq r-1$，对应 $r$ 位校验码 $\varphi(R)$¹。

码字：

$$T(x) = x^r M(x) + R(x)$$

其中 $\deg{T(x)} \leq n = k + r$，对应 $n$ 位码字 $\varphi(T)$。显然 $T(x)$ 能被 $G(x)$ 模 2 整除，即 $T(x) \equiv 0 \pmod{G(x)}$。

接收端校验：

直接计算余数。

$$S(x) = T(x) \bmod G(x)$$

• 若 $S(x) = 0$，认为无错误（可能是错误未被检测到）。
• 若 $S(x) \neq 0$，检测到错误。

检错能力：

• 当 $G(x)$ 最高项为 $x^r$ 时，能检测所有长度 $\leq r$ 的突发错误。

  证明： 设突发错误长度为 $L \leq r$，对应的错误多项式为：

  $$E(x) = x^i \cdot B(x)$$

  其中 $\deg{B(x)} \leq L-1$，且常数项为 1（表示突发错误的起始位）。

  反设错误漏检，则 $G(x)$ 能整除 $E(x)$，即：

  $$G(x) \mid x^i \cdot B(x)$$

  由于 $G(x)$ 的常数项为 1，$G(x)$ 与 $x^i$ 互素，所以：

  $$G(x) \mid B(x)$$

  矛盾！

• 当 $G(x)$ 含有因子 $x+1$ 时，能检测所有奇数个比特错误。

  证明： 设 $G(x) = (x+1) \cdot H(x)$。

  错误多项式 $E(x)$ 有奇数个 1，则 $E(1) = 1$（模 2 下）。

  反设错误漏检，则 $G(x) \mid E(x)$，代入 $x=1$ 即知矛盾！

• 长度 $> r$ 的突发错误，漏检概率为 $2^{-r}$

  证明： 模 $G(x)$ 的剩余类有 $2^r$ 种，选中整除类的概率为 $1/2^r$。

常用生成多项式：

名称	多项式 $G(x)$	二进制 $\varphi(G)$
CRC-8	$x^8 + x^2 + x + 1$	$100000111_2$
CRC-16-IBM	$x^{16} + x^{15} + x^2 + 1$	$11000000000000101_2$
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$	$100000100110000010001110110110111_2$

其中 CRC-32 用于以太网。

交织

由于检错位数有限，我们希望码字中错误的位数尽量少。但是突发错一般都是连续位数的错误，为了将连续错误分离，我们可以使用交织。

设原码 $\mathcal{C}$ 为 $(n,k)$ 分组码，能纠任意 $t$ 个随机错误。

取 $m$ 个码字（行）排列为 $m\times n$ 矩阵：

$$\mathbf{M} = \begin{bmatrix} c_{1,1} & c_{1,2} & \cdots & c_{1,n} \\ c_{2,1} & c_{2,2} & \cdots & c_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m,1} & c_{m,2} & \cdots & c_{m,n} \end{bmatrix}$$

按列发送：$(c_{1,1},c_{2,1},\ldots,c_{m,1}),\;(c_{1,2},\ldots,c_{m,n}) \cdots$

信道产生长度为 $b$ 的突发错误，在交织后，每个新码字（每列）中错误位数 $\le \left\lceil \dfrac{b}{m} \right\rceil$。

为使每个新码字错误可纠正，只需满足：

$$\left\lceil \frac{b}{m} \right\rceil \le t \quad\Longrightarrow\quad b \le m \cdot t$$

即交织深度 $m$ 可以获得 $m$ 倍的随机纠错能力。

校验和

校验和就是将数据按一定长度分组后求和，将和作为校验位附加发送。实现起来非常容易，故 IP/TCP/UDP 都使用了校验和的方法。

---

可靠传输与流量控制

差错控制负责丢帧，链路层协议负责处理丢帧以及流量控制。

帧可能遇到的异常：

1. 帧丢失
2. 帧迟到
3. 帧损坏
4. 帧重复
5. 帧失序

ARQ 协议族

ARQ (Automatic Repeat reQuest) 自动重传请求 是一种差错控制机制，而滑动窗口协议是一种流量控制与传输策略。我们此处讨论的是两者结合形成的 ARQ 协议族。

分类：

协议	$W_T$	$W_R$	实现方式
停等 ARQ	1	1	停等协议
连续 ARQ	$>1$	1	Go-Back-N
选择重传 ARQ	$>1$	$>1$	Selective Repeat

其中 $W_T$ 为发送窗口，$W_R$ 为接收窗口。

ARQ 协议族需要为数据帧编号以区分新旧帧、处理重传。序号比特数为 $n$，则序号空间为 $0, 1, \dots, 2^n - 1$.

停等 ARQ

工作原理：

• 发送方每次发送一帧 $i$
• 接收方每次接收一帧 $i$，并发送确认帧
• 发送方收到确认帧后再发送下一帧 $i+1$

关键机制：

• 超时重传： 发送方发送后启动定时器，超时未收到确认则重传。主要解决发送帧丢失、确认帧丢失、帧损坏等异常。
• 序号机制： 数据帧和确认帧都带 1 比特序号（0/1 交替），从而可以分辨新旧帧（因为最多只会涉及 2 帧故只需 1 位）。主要解决发送帧迟到、确认帧迟到、帧重复等异常。
• 重复帧处理：接收方丢弃重复帧，并重传确认。主要解决发送帧迟到、帧重复等异常。

信道利用率：

无差错：

$$U_{ideal} = \frac{t_{send \_ data}}{RTT} = \frac{1}{1 + 2 \alpha}$$

其中 $\alpha = \frac{t_{trans}}{t_{send}}$（后一个等式假设 $t_{send \_ ack}$ 可忽略且对称链路），$1 + 2 \alpha$ 实际上表示往返时延对应的发送帧数。²

有差错（确认帧无差错）： 假设成功传输一帧平均需要 $N$ 次传输尝试，帧差错率为 $p$，各帧相互独立。则：

$$N = 1 \cdot (1-p) + (1 + N) \cdot p$$

解得 $N = \frac{1}{1-p}$

$$U_{error} = \frac{U_{ideal}}{N} = \frac{1 - p}{1 + 2 \alpha}$$

性能问题：长时延，信道利用率低（如卫星通信）

连续 ARQ

工作原理：

• 发送方连续发送 $w$ 个未确认帧 $[i, i + w - 1]$，并为窗口下沿 $i$ 设置一个超时计时器
• 接收方按序接收帧，每收到一个按序帧 $j$，发送累积确认 $j$，表示 $j$ 及之前所有帧已正确接收
• 发送方接收到确认 $j$（$i \le j \le i + w - 1$）时
  • 将发送窗口调整为 $[j + 1, j + w]$
  • 取消对 $i$ 的计时器，并对新下沿 $j + 1$ 启动新计时器
  • 发送窗口内的新帧 $[i + w, j + w]$
• 若发送方帧 $i$ 的计时器超时（一定是第一帧超时），则重传 $[i, i + w - 1]$ 中的所有帧

关键机制：

• 单一计时器： 只为窗口下沿的帧设置计时器。事实上，为每一帧都设置是没必要的，因为越先发送的帧越先超时。
• 累积确认： 确认号 $j$ 表示序号 $j$ 及之前所有帧均已正确接收，允许发送方一次性滑动窗口多个位置，减少确认帧数量。
• 回退 N 步重传： 超时发生时，发送方重传从 $i$ 开始的整个窗口内的所有帧，即使其中部分帧可能已被接收方正确接收（但确认丢失），这简化了接收方设计（无需缓存失序帧）。

信道利用率：

无差错：

$$U_{ideal} = \begin{cases} \frac{w}{1 + 2 \alpha}, \qquad w \lt 1 + 2 \alpha \\ 1, \qquad w \ge 1 + 2 \alpha \end{cases}$$

假设 $t_{send \_ ack}$ 可忽略，对称链路，并且不考虑发送窗口的大小限制。

有差错（确认帧无差错）：

• $w \ge 1 + 2 \alpha$ 也即窗口比往返时延对应的帧数大，发送方可以持续发送。此时我们可以用传输次数计算时间。假设成功传输一帧平均需要 $N$ 次传输尝试，帧差错率为 $p$，各帧相互独立。则（每次失败后立即重传）： $$N = 1 \cdot (1-p) + (w + N) \cdot p$$ 解得 $N = 1 + \frac{p w}{1-p}$ 从而 $$U_{error} = \frac{U_{ideal}}{N} = \frac{1-p}{1 + p(w-1)}$$
• $w \lt 1 + 2 \alpha$ 发送方发送完 $w$ 个帧后，必须等待窗口下沿（第 $i$ 帧）的确认返回才能继续滑动窗口。 从而 $$U_{error} = \frac{w (1-p)}{1 + 2 \alpha}$$

选择重传 ARQ

工作原理：

• 发送方连续发送 $w$ 个未确认帧 $[i, i + w - 1]$，并为每个已发送但未确认的帧分别设置一个超时计时器
• 接收方按序或失序均可接收帧，每收到一个帧，均发送选择性确认（独立确认）
• 发送方接收到确认 $j$（$i \le j \le i + w - 1$）时：
  • 取消对帧 $j$ 的计时器
  • 标记帧 $j$ 为已确认
  • 若 $j = i$（即窗口下沿被确认），则滑动窗口至新的下沿 $k$，其中 $k$ 是第一个未确认的帧序号，发送窗口调整为 $[k, k + w - 1]$，并发送新进入窗口的帧 $[i + w - 1, k + w - 1]$
• 若发送方帧 $j$ 的计时器超时，则仅重传帧 $j$

关键机制：

• 多计时器： 为每个已发送但未确认的帧分别维护计时器，允许独立检测每个帧的丢失
• 选择性确认： 接收方对每个正确接收的帧单独发送确认，不要求按序确认，允许发送方精确知道哪些帧已到达
• 仅重传丢失帧： 超时发生时，只重传超时的单个帧，而非整个窗口，提高信道利用率
• 接收方缓存： 接收方需要维护一个接收窗口，缓存所有失序到达但正确的帧，等待缺失的帧补齐后按序交付上层

信道利用率：

在无差错时。但是当出现差错时，连续 ARQ 重传整个窗口（$w$ 帧），而选择重传 ARQ 只重传出错的那一帧，故此时后者利用率更高。

无差错： 与连续 ARQ 相同。

有差错（确认帧无差错）：

$$U_{error} = \begin{cases} \frac{w}{1 + 2 \alpha} (1 - p), \qquad w \lt 1 + 2 \alpha \\ 1 - p, \qquad w \ge 1 + 2 \alpha \end{cases}$$

滑动窗口协议的窗口限制

$$W_T + W_R \le 2^n$$

其中 $n$ 为协议序号比特数。

证明：

正确运行的滑动窗口协议要求：任一时刻，发送窗口与接收窗口中不能包含模 $2^n$ 同余的序号，否则接收端无法区分新旧报文，导致错误。

一方面，发送窗口和接收窗口在整个序号空间内覆盖的长度至多为 $W_T + W_R$，由于 $W_T + W_R \le 2^n$ 故不会出现报文是模 $2^n$ 同余的。

另一方面，当 $W_T + W_R \ge 2^n + 1$ 时，存在反例：

1. 发送方发送 $[0, W_T - 1]$
2. 接收方全部接收并回复 ACK，然后滑动接收窗口至 $[W_T, W_T + W_R - 1]$，其中 $W_T + W_R - 1 \ge 2^n$ 故窗口中包含 $2^n$
3. 发送方没收到 ACK，超时重传 $[0, W_T - 1]$
4. 出现报文 $0$ 和报文 $2^n$ 的混淆错误

确认机制

• 累计确认：一个 ACK 确认多个帧，可以加快发送方窗口的移动。
• 捎带确认：将确认信息附在数据帧中发送，尤其适合在双向数据传输中使用。

---

点对点信道

PPP 协议

PPP (Point-to-Point Protocal) 协议，也即点对点协议。我们需要设计协议建立、封装和配置链路。

PPP 特点

设计目标：简单、灵活、支持多种网络层协议

只提供成帧和检错，不提供纠错、流量控制、序号、多点线路、半双工/单工。故没有确认、没有重传、没有序号、没有窗口。

三个组成部分：

1. 封装方法：帧格式定义、透明传输等
2. LCP（链路控制协议）：建立、配置、测试链路，协商链路参数
3. NCP（网络控制协议）：协商网络层参数（IP 地址、DNS 等）

不提供序号和可靠传输：

1. 数据链路层出差错概率不大
2. 在因特网环境下，PPP 封装的数据是 IP 数据报。数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。

PPP 帧格式

┌─────┬─────┬─────┬────────┬──────────┬─────┬─────┐
│  F  │  A  │  C  │protocal│   data   │ FCS │  F  │
│0x7E │0xFF │0x03 │   2B   │  ≤1500B  │ 2B  │0x7E │
└─────┴─────┴─────┴────────┴──────────┴─────┴─────┘

标志字段 F： 始终为 0x7E

地址字段 A： 始终为 0xFF，为形式统一保留的占位符，实际上不起作用

控制字段 C： 一般是 0x03

协议字段 protocal：

• 0x0021：IP 数据报
• 0xC021：LCP 数据
• 0x8021：NCP 数据
• 0xC023：鉴别数据

透明传输

为实现透明传输，需对 data 字段进行填充以避免歧义。

异步传输： 采用字符填充（因为异步传输面向字节）。规则如下：

• 发送端：

  $$\text{Code}_{\text{sned}} = \begin{cases} \text{0x7D, } \text{Code}_{\text{pre}} \oplus \text{0x20} & \text{If} \; \text{Code}_{\text{pre}} \in \text{Escape Set} \\ \text{Code}_{\text{pre}} & \text{Otherwise} \end{cases}$$

  其中 Escape Set = {0x7E, 0x7D} ∪ {0x00 ~ 0x1F}. 0x7E 为帧标志，0x7D 为转义字符，0x00 ~ 0x1F 为控制字符。

  原字符	异或 0x20	转义后
  0x7E	0x5E	0x7D, 0x5E
  0x7D	0x5D	0x7D, 0x5D
  0x00~0x1F	0x20~0x3F	0x7D, 0x20~0x3F

• 接收端：

  $$\text{Code}_{\text{receive}} = \begin{cases} \text{Code}_{\text{next}} \oplus \text{0x20} & \text{If } \text{Code}_{\text{current}} = \text{0x7D} \\ \text{Code}_{\text{current}} & \text{Otherwise} \end{cases}$$

同步传输： 采用零比特填充（因为异步传输面向比特）。规则即为：

• 发送端：连续 5 个 1 后填入一个 0
• 接收端：连续 5 个 1 后去掉一个 0

工作步骤

1. 建立：物理连接建立（如 ISP 拨号上网）后，双方通过 LCP 协商链路参数（如最大接收单元、认证协议等）。
2. 鉴权：若 LCP 协商了认证，则采用规定的协议进行双方身份的认证。
3. 网络：通过 NCP 协商网络层参数，包括分配 IP 地址、DNS 服务器等。
4. 终止：通信完毕时 NCP 释放网络连接，收回 IP 地址。在由 LCP 释放数据链路连接，最后释放物理连接。

注：PPP 协议已不是单纯的数据链路层协议，还涉及物理层和网络层。

---

HDLC 协议

HDLC (High-level Data Link Control) 协议，也即高级数据链路控制。

HDLC 特点

• 面向比特的同步通信协议
• 支持全双工通信，可靠性高
• 滑动窗口协议，发送窗口为 7，接收窗口为 1 或 7

HDLC 帧格式

┌─────┬─────┬─────┬────────┬────────┬─────┐
│  F  │  A  │  C  │  Info  │   FCS  │  F  │
│0x7E │ 1B  │ 1B  │  ≤MTU  │   2B   │0x7E │
└─────┴─────┴─────┴────────┴────────┴─────┘

• 标志字段 F：始终为 0x7E。
• 地址字段 A：占 1 字节。广播信道时是终端的站号；点对点时用于标志命令和响应。
• 控制字段 C：占 1 字节，根据其判断帧的类型。
• 帧检验序列 FCS：占 2 字节。使用 CRC 校验，生成多项式为 $G(x) = x^{16} + x^{12} + x^5 + 1$。

HDLC 帧类型

由上述控制字段 C 标识。

• I 帧（信息帧）： 用于传输数据、捎带确认。

┌───┬────────┬─────┬────────┐
│ 0 │  N(S)  │ P/F │  N(R)  │
├───┼────────┼─────┼────────┤
│ 0 │  3bit  │1bit │  3bit  │
└───┴────────┴─────┴────────┘

字段	长度	含义
N(S)	3 bit	发送序号。发送方标识本帧的序号。
P/F	1 bit	查询/终止位。主站发送时置 P(Poll)=1 表示请求从站响应，从站响应时置 F(Final)=1 表示响应结束。该位为 0 无特殊含义。
N(R)	3 bit	接收序号。表示期望收到的下一帧序号，捎带确认了所有小于该序号的帧

• S 帧（监控帧）： 用于流量控制、差错控制。

┌───┬───┬──────┬─────┬────────┐
│ 1 │ 0 | type │ P/F │  N(R)  │
├───┼───┼──────┼─────┼────────┤
│ 1 │ 0 | 2bit │1bit │  3bit  │
└───┴───┴──────┴─────┴────────┘

S帧类型：

type	类型	缩写	含义
00	接收准备好	RR	确认 N(R) 之前所有帧，准备接收 N(R) 帧
01	接收未准备好	RNR	确认 N(R) 之前所有帧，但暂停接收（流量控制）
10	拒绝	REJ	Go-Back-N，确认 N(R) 之前所有帧，但是要求立即重传 N(R) 及之后所有帧
11	选择性拒绝	SREJ	Selective-Repeat，确认 N(R) 之前所有帧，要求立即重传 N(R) 这一帧

协议	发送窗口 $W_T$	接收窗口 $W_R$	使用的 S 帧
停等 ARQ	1	1	RR（但通常用 ACK 替代）
连续 ARQ	>1	1	RR、REJ
选择重传 ARQ	>1	>1	RR、RNR、REJ、SREJ

• U 帧（无编号帧）: 链路控制，包括确认和断开连接、协商链路参数等。

┌───┬───┬───────────┬───────┐
│ 1 │ 1 |     M     │  P/F  │
├───┼───┼───────────┼───────┤
│ 1 │ 1 |    5bit   │  1bit │
└───┴───┴───────────┴───────┘

常见的有： SABM 设置 ABM 模式；DM 断开模式；DISC 终止链路连接；UA 确认 U 帧

配置方式

• 非平衡配置：分为点对点和点对多点两种。由一个主站及一个或多个从站组成，主站发出帧叫命令，从站发出帧叫响应。
• 平衡配置：两个站都是复合站，同时具有主站和从站的功能。

---

介质访问控制

MAC (Medium Access Control) 子层负责解决共享传输介质中的信道资源分配问题。

希望的性质：

记广播信道速率为 $R$

• 饱和：单结点发送速率为 $R$
• 公平：多结点时，各结点发送速率相同
• 分布式：没有特殊的结点用于协同传输，也没有同步的时钟、时隙
• 简单

信道分配策略

策略	代表技术	适用场景	类比
静态划分	FDMA、TDMA、CDMA	用户少且稳定	给马路划分车道（FDMA），分时使用（TDMA），车牌区分（CDMA）
动态分配	ALOHA、CSMA、预约协议	用户多且突发	制定交通规则

注： 区别信道复用和 MAC

• 信道复用：是物理层/链路层技术手段，考虑将单个物理信道划分成多个逻辑子信道供用户独立使用。
• MAC：是链路层功能策略，关注的是多个用户如何竞争或协调使用同一物理信道（共享信道），其可以借助信道复用实现静态划分，也可以采用其他方式实现动态划分。

静态划分

方法	全称	划分维度	资源分配	适用场景
FDMA	频分多址	频率	为每个用户分配固定频段	模拟通信、广播、蜂窝系统
TDMA	时分多址	时间	为每个用户分配固定时隙	数字通信、GSM、卫星通信
CDMA	码分多址	码字	为每个用户分配正交码序列	3G移动通信、军用通信
WDMA	波分多址	波长	为每个用户分配不同波长	光纤通信

问题： 考虑 M/M/1 排队系统：

• 帧平均长度：$1/\mu$ bit
• 信道容量：$C$ bps，也即服务率 $\mu C$ 帧/s
• 帧到达率：$\lambda$ 帧/s

则平均延迟：

$$T_{pre} = \frac{1}{\mu C - \lambda}$$

当信道划分为 $N$ 个独立子信道时：

• 每个子信道容量降为 $C/N$
• 平均到达率降为 $\lambda/N$（假设均匀分布）

则每个子信道延迟：

$$T_{after} = \frac{1}{\mu (C/N) - (\lambda/N)} = \frac{N}{\mu C - \lambda}$$

故总延迟增大 $N$ 倍，并且信道利用率还会降低。

动态划分：总结对比表

协议类型	低负载延迟	高负载吞吐量	典型最大吞吐量
纯 ALOHA	低	极低	$1/2e \approx 0.184$
时隙 ALOHA	低	低	$1/e \approx 0.368$
CSMA/CD	很低	中等	取决于传播时延
位图协议	高	高	接近 1
轮询/令牌	高	高	接近 1
有限竞争协议	低	高	接近 1（自适应时）

动态划分：随机访问协议

纯 ALOHA

想发就发，冲突后随机重发。

效率：

假设所有帧长度均为 $L$ bit，信道速率 $R$ bps，发送时间均为 $T = L/R$ s，各结点发送相互独立，新帧和重传帧的总到达率服从泊松分布，平均到达率为 $G$ frame/s。

某一帧在 $t = t_0$ 时刻开始发送，若要发送成功，要求在 $(t_0 - T, t_0 + T)$ 内没有其他帧到达。故成功概率：

$$P_{success} = e^{-2 T G}$$

吞吐量：

$$S = G \cdot e^{-2 T G} \; [frame/s]$$

为使吞吐量最大化，求导得极大值点 $G = 1/2T = L/2R$，带入即得：

$$S_{\max} = \frac{1}{2eT} \; [frame/s] = \frac{R}{2e} \; [bps]$$

时隙 ALOHA

将连续时间划分为离散的时隙，时隙长度恰好等于一帧的发送时间。规定帧到达后，只能在下一时隙开始时发送。注意要求结点间的同步。

效率：

假设所有帧长度均为 $L$ bit，信道速率 $R$ bps，发送时间均为 $T = L/R$ s，各结点发送相互独立，新帧和重传帧的总到达率服从泊松分布，平均到达率为 $G$ frame/s。

某一帧在 $t = t_0$ 时刻开始发送，若要发送成功，要求在 $(t_0 - T, t_0]$ 内没有其他帧到达。故成功概率：

$$P_{success} = e^{-T G}$$

吞吐量：

$$S = G \cdot e^{-T G} \; [frame/s]$$

为使吞吐量最大化，求导得极大值点 $G = 1/T = L/R$，带入即得：

$$S_{\max} = \frac{1}{eT} \; [frame/s] = \frac{R}{e} \; [bps]$$

CSMA

载波侦听多路访问（Carrier Sense Multiple Access），发送前先侦听信道：

协议	信道空闲时的行为	信道繁忙时的行为
非坚持 CSMA	立即以概率 1 发送	随机等待一段时间后再侦听
1-坚持 CSMA	立即以概率 1 发送	持续侦听，一旦空闲立即发送
p-坚持 CSMA	以概率 $p$ 立即发送，以概率 $1-p$ 延迟一个时间单元后再次侦听	持续侦听直至空闲，然后以概率 $p$ 发送，以概率 $1-p$ 延迟一个时间单元后再次侦听

注：

• 侦听的是端结点收到的信号，对于一个信号帧，侦听端从第一个比特到达，到最后一个比特离开，侦听总时长为该帧的发送时长。
• p-坚持 CSMA 的时间单元是信道的最大传播时延 $\tau$。

CSMA/CD

在一般的 CSMA 中，会出现碰撞，也即两个信号都在传输但是首比特都还未抵达目标结点时。故可以附加碰撞检测（Collision Detection），一旦检测到碰撞就停止发送并等待（还可能发送干扰信号通知所有站点）。

• 碰撞检测时长： 碰撞检测时长应为 $2 RTT_{\max}$，其中 $RTT_{\max}$ 为网络中任意两个结点之间传播时延的最大值。碰撞检测时长也称为争用期/碰撞窗口/槽时间

  证明： 如图，$t_0$ 时刻 B 点发送信号，$t_1$ 时刻 D 点发送信号。 则 $t_0 - RTT \lt t_1 \lt t_0 + RTT$ 时才会发生碰撞（注意实际发送时间是离散的时隙，此处当作连续处理）。 此时 D 点碰撞检测时长不小于 $t_0 - t_1 + RTT$，B 点碰撞检测时长不小于 $t_1 - t_0 + RTT$，最大值 $2RTT$ 在边界取到。

• 二进制指数类型退避算法

  遇到碰撞时使用二进制指数类型退避算法确定重传时间。 具体来说，设本次发送已发生 $n$ 次碰撞。 则第 $n+1$ 次发送（即第 $n$ 次重传）需等待 $x$ 个争用期 $2 RTT_{\max}$，其中 $x$ 是从集合 $\set{0, 1, \cdots, 2^{\min(n, 10)} - 1}$ 中均匀选取的随机整数。 若重传 16 次仍失败则丢弃。

CSMA/CA

在无线局域网中，难以实现边发边听的碰撞检测，因此采用碰撞避免（Collision Avoidance）机制来减少碰撞发生。

注：可以侦听信道是否空闲，但是不能进行碰撞检测，因为不能边发边听，但是可以只听。

工作流程：

1. 节点有帧要发送时，先侦听信道
   • 检查物理载波侦听（检测信道信号能量）
   • 检查虚拟载波侦听（NAV 是否 > 0）
   • 只有当两者都指示信道空闲时，才认为信道空闲（理论上只需 NAV）
2. 判断需要等待的帧间间隔
   • 若节点最近收到错误帧（CRC 校验失败）且该帧不是发给自己的，则需等待 EIFS 时间
   • 否则，等待 DIFS 时间
3. 若信道持续空闲相应帧间间隔时间，则进入随机退避阶段
   • 随机退避计数器从竞争窗口 CW 中均匀选取初始值，范围 $[0, CW - 1]$
   • CW 初始值为 $CW_{\min}$，成功发送后恢复为 $CW_{\min}$
4. 退避计数器递减
   • 信道空闲时，每经过一个时隙，计数器减 1
   • 信道繁忙时，计数器冻结
   • 若信道繁忙期间收到有效帧，根据帧中的 Duration 字段更新 NAV
5. 计数器减至 0 时立即发送数据帧，数据帧头中设置 Duration 字段（包含 SIFS + ACK 的时间）
6. 接收端正确收到帧后，等待 SIFS 时间后回复 ACK
7. 若发送端未收到 ACK，则认为发生碰撞
   • 将竞争窗口加倍，$CW = \min(2 CW, CW_{\max})$
   • 重新进入退避阶段（步骤 2）
   • 若重传 16 次仍失败，则丢弃该帧，CW 重置为 $CW_{\min}$

RTS/CTS 机制：

为解决隐蔽节点问题，可选用 RTS/CTS 握手协议：

• 发送端发送 RTS（请求发送）帧
• 接收端回复 CTS（允许发送）帧，通知周围节点预约信道
• 发送端收到 CTS 后才发送数据帧
• 周围节点根据 RTS/CTS 中的时长信息更新 NAV，在此期间不发送

注：实际上，RTS 也会发生碰撞，如图 6 中，若 STA 1 的初始退避为 7 则会产生碰撞。但是由于 RTS 比较短，故概率更小、损失更轻。

时间间隔类型：

帧间隔	全称	长度	用途
SIFS	Short Inter-Frame Space	最短	ACK、CTS、数据分片等最高优先级响应
PIFS	PCF Inter-Frame Space	次短（SIFS + 1 时隙）	PCF 模式下 AP 获取信道控制权
DIFS	DCF Inter-Frame Space	较长（SIFS + 2 时隙）	DCF 模式下普通站点竞争信道
EIFS	Extended Inter-Frame Space	最长（SIFS + DIFS + ACK_Time）	帧接收错误后的错误恢复等待

网络分配向量（NAV）：

NAV 本质上是冻结时间计时器，利用接收到的帧中的 Duration 字段进行设置。利用 NAV 可以实现虚拟载波侦听。

动态划分：无冲突协议

位图协议

位图协议（Bitmap Protocal）是预约协议的一种实现方式，本质上也是统计时分复用（STDM）的一种具体实现方式。

位图协议将时间划分为若干个周期，每个周期包含两个阶段：

1. 预约阶段： 信道被划分为 $N$ 个微时隙，与网络中的 $N$ 个站点一一对应。若某站点有数据要发送，就在属于自己的微时隙中发送一个 1 比特的预约信号。所有站点都监听整个预约阶段，从而获知自己是第几个发送（如果需要）。
2. 数据传输阶段： 站点按照顺序依次发送数据帧，不会碰撞。

效率：

假设站点总数为 $N$，信道速率为 $R$ bps，数据帧长度为 $L$ bit，每个微时隙的时长为 $d$ s

则预约阶段开销：$N \cdot d$ s

设 $k$ 个站点在数据传输阶段有数据发送，总传输时间为 $k \cdot \frac{L}{R}$ s

信道利用率：

$$\eta = \frac{k \cdot \frac{L}{R}}{N \cdot d + k \cdot \frac{L}{R}} = \frac{L}{N R d/k + L}$$

显然 $k$ 越大（负载越高）利用率越高。

轮询协议

轮询协议（Polling Protocol）是一种集中式的介质访问控制协议，通过一个主节点依次询问各从节点是否有数据发送，从而避免碰撞。常用于无线局域网、蓝牙。

流程：

1. 轮询阶段：主节点向某个从节点发送一个简短的轮询帧（Poll Frame）
2. 数据传输阶段：被轮询的从节点若有数据，则发送一个数据帧；若有多个数据帧，可一次发完或等待下次轮询
3. 确认/应答：从节点发送完毕后，主节点继续轮询下一个从节点

效率： 假设有 $N$ 个从节点，信道速率为 $R$ bps，数据帧长度为 $L$ bit，轮询帧的传输时间为 $t_{poll}$ s，应答帧的传输时间为 $t_{ack}$ s，当前轮询周期中有数据发送的从节点数为 $k$。

则总周期时间：

$$T_{cycle} = N \cdot t_{poll} + k \cdot \frac{L}{R} + (N-k) \cdot t_{ack} [s]$$

有效数据传输时间为 $k \cdot \frac{L}{R} [s]$，因此：

$$\eta = \frac{k \cdot \frac{L}{R}}{N \cdot t_{poll} + k \cdot \frac{L}{R} + (N-k) \cdot t_{ack}}$$

$k$ 越大（负载越高）利用率越高，且当满载时利用率接近 100%

令牌传递协议

令牌传递协议（Token Passing Protocol）是一种分布式的无冲突介质访问控制协议，让所有节点构成一个逻辑环，控制帧（Token）在环依次循环传递，只有持有令牌的节点才能发送数据，从而避免碰撞。

流程：

1. 令牌传递阶段：令牌在逻辑环内按顺序传递。每个节点持续监听信道，等待令牌到达。
2. 数据传输阶段：
   • 节点收到令牌后，若有数据要发送，则持有令牌并发送一个或多个数据帧。发送完毕后，节点传递令牌给逻辑环中的下一个节点。
   • 若无数据要发送，节点立即传递令牌给下一个节点。
3. 令牌监控：由于令牌是分布式传递的，需要机制检测令牌丢失（如超时后由指定节点生成新令牌）或令牌重复。

效率：

假设节点总数为 $N$，信道速率为 $R$ bps，数据帧长度为 $L$ bit，令牌帧的传输时间为 $t_{token}$ s， 节点间传递令牌的平均传播时延（含处理时间）为 $t_{prop}$ s，当前令牌循环周期中有数据发送的节点数为 $k$。

则总周期时间：

$$T_{cycle} = N \cdot (t_{token} + t_{prop}) + k \cdot \frac{L}{R} \quad [\text{s}]$$

有效数据传输时间为 $k \cdot \frac{L}{R}$ s，因此：

$$\eta = \frac{k \cdot \frac{L}{R}}{N \cdot (t_{token} + t_{prop}) + k \cdot \frac{L}{R}}$$

$k$ 越大（负载越高）利用率越高，且当满载时利用率接近 100%。

动态划分：有限竞争协议

有限竞争协议是介于随机访问协议和无冲突协议之间的一类介质访问控制协议。

随机访问协议在低负载时延迟小，但在高负载时碰撞频繁、效率低。无冲突协议在高负载时效率高，但在低负载时固定开销大、延迟高。而有限竞争协议在低负载时，让所有站点一起竞争，延迟小；高负载时，将站点分组，限制每组的竞争站点数，降低碰撞概率。

分组方式可以是静态的（固定分组），也可以是动态的（根据负载自适应调整组大小）。

有限竞争协议

静态的分组。

机制： 将 $N$ 个站点划分为若干组，每组内的站点数适中。当站点有数据要发送时：

1. 先在所属组的竞争时隙内以随机访问协议（时隙 ALOHA）发送
2. 若成功，则发送数据
3. 若碰撞，则在本组内重试，或采用某种退避策略

效率：

假设站点总数为 $N$，信道速率为 $R$ bps，数据帧长度为 $L$ bit，发送时间均为 $T = L/R$ s。将 $N$ 个站点划分为 $n$ 组，每组大小相等，即每组有 $M = N/n$ 个站点。 每个时隙只允许某一组内的站点参与竞争，组内站点使用时隙 ALOHA 方式发送。

设组内每个站点以 $\lambda$ 帧/时隙的概率发送（包括新帧和重传帧），则组内总到达率为 $G = M \cdot \lambda$ 帧/时隙。

在时隙 ALOHA 中，组内成功发送的概率为 $P_{success} = e^{-G}$，该组的吞吐量为：

$$S_{group} = G \cdot e^{-G} \quad [\text{帧/时隙}]$$

信道总吞吐量（以帧/时隙计）为：

$$S = \frac{1}{n} \cdot n \cdot S_{group} = G e^{-G}$$

将 $G = M\lambda$ 代入，得：

$$S = M \lambda \cdot e^{-M \lambda}$$

故 $S$ 在 $M = \frac{1}{\lambda}$ 时取最大值：

$$S_{\max} = \frac{1}{e} \quad [\text{帧/时隙}]$$

自适应有限竞争协议

根据当前负载动态调整分组大小，本质上是根据最优分组 $M = \frac{1}{\lambda}$：

• 低负载：$\lambda$ 小，则 $M$ 大。此时让所有站点在同一组竞争，延迟小。
• 高负载：$\lambda$ 大，则 $M$ 小。此时将站点分成多个小组，碰撞少。

可以使用树形分裂算法或二叉树竞争实现。

---

广播信道

以太网

以太网（Ethernet）是一种广泛使用的局域网技术。以太网的标准有 DIX Ethernet V2 以及 IEEE 802.3，两者差别很小。一般都采用 DIX Ethernet V2.

服务特点

1. 无连接的工作方式：一方面事先不建立逻辑连接，另一方面通信双方不维护状态信息（数据帧不编号、不发 ACK）。
2. 不可靠交付：遇到差错只需丢弃帧，遇到重传只需发送帧。
3. 半双工通信：使用 CSMA/CD 协议，故只能进行双向交替通信。
4. 使用曼彻斯特编码，更高速的以太网使用其他编码。

IEEE 802.2 标准定义的三种 LLC 服务类型：

类型	名称	连接	编号/确认	适用场景
Type 1	无连接	无	不编号、不发 ACK	以太网（绝大部分）、Wi-Fi（数据帧）
Type 2	面向连接	有	编号、发 ACK、窗口流控	令牌环、某些工业网络
Type 3	无连接带确认	无	不发 ACK（但可发带确认的帧）	极少使用，介于两者之间

以太网中的 CSMA/CD

使用 1-坚持 CSMA，二进制指数退避类型算法。

关键参数：

• 争用期：对 10 Mbps 的 Ethernet 而言，争用期 $2\tau = 51.2 \mu s$，相当于传输 $64$ 字节
• 最短帧长：为确保碰撞时仍在发送，最短帧长为 $64$ 字节
• 帧间间隔：$9.6 \mu s$，相当于传输 $96$ bit

注：

• 争用期决定了以太网最大端到端长度，当然实际上争用期还考虑了各种不利因素。
• 实际传输中小于最短帧长的帧就代表发生碰撞了。
• 帧间间隔是同一个站点连续发送两帧之间的最小间隔，为了保持公平性，防止单结点持续占据信道。实际上 CSMA 中并不要求使用帧间间隔。

信道利用率：

假设帧长为 $L$ bit，数据率为 $C$ bps，则帧发送时延为 $T_0 = L/C$ s，结点间单向传播时延均为 $\tau$，令 $a = \tau / T_0$。系统采用 1-坚持 CSMA/CD 和二进制指数退避。

则在单结点无竞争连续发送时，最大信道利用率为：

$$S_{single} = \frac{T_0}{\tau + T_0} = \frac{1}{1 + a}$$

在多结点饱和竞争时，为便于分析，将时间划分为长度为 $2\tau$ 的离散争用时隙，并假设所有站点只在时隙边界开始发送。

在饱和状态下，每个时隙内的发送抵达次数服从泊松分布，平均抵达次数 $G$ 在吞吐量最大时取 $G=1$，此时冲突概率 $p = 1 - 1/e$，平均冲突次数 $\overline{k} = e-1$。故最大信道利用率为：

$$S_{multiple} = \frac{T_0}{\tau + T_0 + 2 \tau \overline{k}} = \frac{1}{1 + a(2e-1)}$$

从而

• $a$ 越小，表示碰撞一发生就检测出来并停止发送，信道利用率更高。
• $a$ 越大，表示碰撞检测出来时浪费的信道资源越多，信道利用率更低。
• 我们可以通过增加帧长、提高速率以减小 $a$。

MAC 地址

MAC 地址长度为 48 位（6 字节），通常采用十六进制表示，例如 00:1A:2B:3C:4D:5E。
它固化在网卡的 ROM 中，因此也被称为物理地址或硬件地址，属于 EUI-48（扩展唯一标识符-48） 格式。

一般一张网卡有一个 MAC 地址，相当于网络接口的标识符。

注：除了 EUI-48，也存在 EUI-64 格式（64 位），主要用于 IPv6 地址生成及某些无线技术中。

地址格式： 一般为48位。

• 前 24 位：OUI（Organiztionally Unique Identifier），组织唯一标识符，由 IEEE 分配给设备制造商，用于标识厂商。
• 后 24 位：扩展标识符，由厂商自主分配，确保在同一 OUI 下每个网卡的地址唯一。

地址类型：

第一字节的最低位为 I/G 位（Individual / Group）。

• I/G = 0**：单播地址**，表示该地址唯一标识一个网络接口。
• I/G = 1**：多播地址**，表示该地址标识一组网络接口。

第一字节的次低位为 U/L 位（Universal / Local）

• U/L = 0**：全局唯一地址**，通常由 IEEE 分配的 OUI 保证，即全球唯一 MAC 地址。
• U/L = 1**：本地管理地址**，由网络管理员或软件覆盖指定，用于覆盖硬件自带的全局地址。

注：广播地址是多播地址的一种特例，即 FF-FF-FF-FF-FF-FF，表示发送给同一广播域内的所有设备。

识别：

• 单播地址
• 广播地址
• 多播地址 混杂方式 （promiscuous mode） 工作的以太网适配器会接收所有帧。

Ethernet 帧格式

┌───────────────┬───────────────┬───────────────┬───────────────────┬──────────────┐
│ Dest MAC (6B) │ Src MAC (6B)  │ EtherType(2B) │ payload(46-1500B) │   FCS (4B)   │
└───────────────┴───────────────┴───────────────┴───────────────────┴──────────────┘

其中：

• MAC 地址：48位（6字节），每个网卡拥有全球唯一的MAC地址。
• EtherType 类型字段：指示上层协议，常见值：
  • 0x0800：IPv4
  • 0x0806：ARP
  • 0x86DD：IPv6
• payload：由于帧最少 64B，故 payload 最少 46B，不足的会添加 padding。其中开头的 7B 为前同步码，紧跟 1B 为帧定界符，均由硬件生成。
• FCS 帧校验序列：用于检测传输错误。
• MTU（Maximum Transmission Unit）：最大传输单元，此处是 1500B

以太网演进

以太网按拓扑结构可以分为：星形网、总线网和环形网。

• 传统以太网： 总线型结构，所有设备共享信道，通过 CSMA/CD 解决冲突。槽时间 $51.2 \mu s$ 决定最小帧长 64 字节。
• 10BASE-T： 物理拓扑改为星型，使用集线器连接双绞线，但逻辑上仍是共享总线，CSMA/CD 照常工作。
• 100BASE-T： 速率提升至 100 Mbps，保持帧格式不变，槽时间等比例缩短至 $5.12 \mu s$，参数 a 不变，保证兼容性。
• 1000BASE-T： 速率 1000 Mbps，槽时间设为 $4.096 \mu s$（对应 512 字节）。因最小帧长仍为 64 字节，引入载波延伸填充短帧；引入帧突发一次发送多帧提升效率。同时支持全双工模式，无需 CSMA/CD。

标准	速率	拓扑结构	传输介质	槽时间	关键技术特点
传统以太网	10 Mbps	总线型	同轴电缆	$51.2 \mu s$	CSMA/CD，共享介质
10BASE-T	10 Mbps	星型	双绞线	$51.2 \mu s$	集线器，逻辑仍为总线
100BASE-T	100 Mbps	星型	双绞线/光纤	$5.12 \mu s$	保持帧格式，参数 a 不变
1000BASE-T	1000 Mbps	星型	双绞线/光纤	$4.096 \mu s$	载波延伸、帧突发、全双工支持

---

无线局域网

无线局域网（WLAN），遵循 IEEE 802.11 系列协议。

特性

与有线链路的区别：

• 信号强度衰减（路径损耗）
• 干扰（频段共享）
• 多径传播
• 隐蔽节点问题、暴露节点问题

网络设备与结构

接入点（AP）： AP 用于实现以下功能。

• 帧转换：实现 802.11 无线帧与 802.3 以太网帧的相互转换
• 广播 BSSID：周期性发送信标帧（Beacon Frame）宣告自身存在
• 关联管理：处理站点的关联与认证请求
• 桥接功能：连接无线网络与有线网络

网络模式：

模式	特点
BSS（基本业务集）	有 AP（接入点），连接有线网络
Ad hoc	无 AP，节点自组织网络

一个 BSS 由一个接入点（AP），多个无线站点（STA）和一个 BSSID 组成。

关联机制

扫描方式	过程
被动扫描	AP 周期性发送信标帧 → STA 选择 AP → STA 发送关联请求帧 → AP 返回关联响应帧
主动扫描	STA 广播探测帧 → AP 回复探测响应帧 → STA 选择 AP → STA 发送关联请求帧 → AP 返回关联响应帧

WLAN 通用帧结构

也即 PSDU（PLCP Service Data Unit）

┌─────────┬──────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────┐
│  Frame  │ Duration │Address 1│Address 2│Address 3│   Seq   │Address 4│ Payload │ CRC │
│ Control │          │  (RA)   │  (TA)   │ (BSSID) │ Control │         │         │     │
│   2B    │    2B    │   6B    │   6B    │   6B    │   2B    │   6B    │ 0-2312B │ 4B  │
└─────────┴──────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────┘

地址字段说明：

字段	含义	说明
Address 1	RA（接收地址）	目的 MAC 地址，可以是主机或 AP
Address 2	TA（发送地址）	源 MAC 地址，可以是主机或 AP
Address 3	BSSID	AP 的 MAC 地址或 Ad hoc 网络标识
Address 4	可选地址	仅在 Ad hoc 模式下使用

注：地址的获取需要使用 ARP 请求。

帧控制字段说明：

包含 2 bit 的 Type 字段，用以标注帧类型。

Type	帧类型	说明
0x0	管理帧	节点与 AP 的关联、定时与同步、认证
0x1	控制帧	竞争阶段的握手与确认、结束无竞争期
0x2	数据帧	在 CP 及 CFP 阶段传输上层数据

另含 4 bit 的 Subtype 字段，用以标注更具体的帧类型。

无线局域网的 CSMA/CA

WLAN 的问题：

1. 碰撞检测困难：无线信号衰减大，节点发送时自身信号远强于其他节点信号，无法同时收发以实现可靠的碰撞检测。
2. 隐蔽节点问题：网络拓扑不构成完全图，部分节点无法相互监听，导致在接收端可能发生碰撞而发送端不自知。
3. 暴露节点问题：节点因监听到其他节点的发送而退避，但实际上自己的发送并不会干扰对方正在进行的通信，导致不必要的信道闲置和吞吐量下降。

所以在 WLAN 中，只能采用碰撞避免的 CSMA/CA。

---

局域网扩展与交换

网络互连设备

各层的网络互连设备：

层级	设备
Application layer	Application gateway
Transport layer	Transport gateway
Network layer	Router
Data link layer	Bridge, Switch
Physical layer	Repeater, Hub

常见设备对比：

特性	中继器（Repeater）	集线器（Hub）	网桥（Bridge）	交换机（Switch）	路由器（Router）
工作层次	物理层	物理层	数据链路层	数据链路层	网络层
主要功能	再生放大信号	多端口信号转发	根据MAC地址过滤转发	根据MAC地址选择性转发	路由选择与分组转发
转发方式	原样转发	广播到所有端口（接收口除外）	选择性转发	选择性转发	路由转发
典型端口数	2	4-24	2	8-48	2-16
转发依据	无	无	MAC 地址表	MAC 地址表	IP 路由表
碰撞域隔离	否	否	是	是	是
广播域隔离	否	否	否	否	是
带宽模式	共享	共享	独立	独享（全双工）	独立
MAC 地址学习	无	无	有（自学习）	有（自学习）	不适用
地址表/路由表	无	无	MAC 地址表	MAC 地址表	IP 路由表
工作模式	半双工	半双工	半双工/全双工	全双工	全双工
冲突处理	无，由网卡检测	CSMA/CD	CSMA/CD 或全双工	全双工	不涉及
典型应用	延长传输距离	早期以太网共享连接	连接两个局域网段	局域网内部互连	连接不同网络、互联网接入
当前状态	较少独立使用	基本淘汰	基本被交换机取代	核心设备	核心设备

注：混杂模式下，互连设备为 Hub 则可以捕获设备上所有接口的数据，若为 Switch 则只能捕获自己接口的数据。

自学习转发

交换表结构：（MAC 地址，接口，TTL）

自学习过程：

1. 收到帧后，记录源 MAC 地址和输入接口
2. 查交换表找目的 MAC 地址对应的接口
3. 若找到且接口不同：转发到该接口
4. 若找到但接口相同：丢弃（不能发给自己）
5. 若未找到：flood（泛洪），转发到除输入外的所有接口

生成树协议

为了提高可靠性，通常会在交换机之间部署冗余链路，这会导致网络中存在环路。生成树协议（Spanning Tree Protocol, STP）通过构造网络结构的生成树，将网状拓扑修剪成无环路的树状拓扑。

环路问题：

• 广播风暴：广播帧在环路中无限循环转发
• MAC 地址表震荡：转发表频繁更新
• 帧重复接收

图论建模：

将交换网络抽象为一个无向连通图：

$$G = (V, E)$$

• $V$：交换机集合
• $E$：交换机之间的链路集合
• 每条边 $e \in E$ 有权值 $w(e) > 0$，表示链路开销

注：PC等终端设备不在图中，因为 STP 只考虑交换机之间的互连。

步骤：

1. 选举根网桥

   $$r = \arg\min_{v \in V} \text{BID}(v)$$

   BID 由优先级和 MAC 地址组成。

2. 计算最短距离

   定义 $d(v)$ 为交换机 $v$ 到根网桥 $r$ 的最短路径开销：

   $$d(v) = \min \left\{ \sum_{e \in P} w(e) \;\middle|\; P \text{ 是 } v \text{ 到 } r \text{ 的路径} \right\}$$

   以 $r$ 为源点，运行分布式 Dijkstra 算法，计算所有交换机的最短距离 $d(v)$。

3. 选举根端口

   对于每个非根交换机 $v \in V \setminus \{r\}$，选择一条边连接到距离更小的邻居：

   $$\text{parent}(v) = \arg\min_{(u,v) \in E} \big( d(u) + w(u,v) \big)$$

   被选中的边 $(u, v)$ 中，$v$ 端的端口就是根端口。

4. 选举指定端口

   对于每条边 $(u, v) \in E$：

   • 如果 $d(u) < d(v)$，则 $u$ 端的端口是指定端口
   • 如果 $d(u) > d(v)$，则 $v$ 端的端口是指定端口
   • 如果 $d(u) = d(v)$，则比较 BID，较小者端的端口是指定端口

5. 确定阻塞端口

   既不是根端口也不是指定端口，则作为阻塞端口。

6. 确定最小生成树

   定义转发边集：

   $$T = \{ (u, v) \in E \mid \text{u, v didn't have blocked} \}$$

   则

   • $T$ 是 $G$ 的最小生成树
   • $|T| = |V| - 1$
   • $T$ 以 $r$ 为根，每个非根节点通过 parent(v) 连接到树

虚拟局域网（VLAN）

作用：

• 隔离广播域（减少广播流量）
• 安全隔离（不同 VLAN 不能直接通信）
• 灵活组网（不受物理位置限制）

实现方式：

• 基于端口：按交换机端口分组
• 基于 MAC 地址：按设备 MAC 分组

端口类型：

• Access 端口：连接终端设备，只属于一个 VLAN。发送时剥离标签，接收时打上默认 VLAN 标签。
• Trunk 端口：连接交换机，可承载多个 VLAN。发送时保留 802.1Q 标签，接收时根据标签转发。

IEEE 802.1Q VLAN 帧格式：

IEEE 802.3
┌──────────┬──────────┬───────────┬─────────┬──────┐
│ Dest MAC │ Src MAC  │ EtherType │ payload │ FCS  │
│    6B    │    6B    │    2B     │46-1500B │  4B  │
└──────────┴──────────┴───────────┴─────────┴──────┘

IEEE 802.1Q
┌──────────┬──────────┬────────────┬───────────┬─────────┬──────┐
│ Dest MAC │ Src MAC  │ 802.1Q Tag │ EtherType │ payload │ FCS  │
│    6B    │    6B    │    4B      │    2B     │46-1500B │  4B  │
└──────────┴──────────┴────────────┴───────────┴─────────┴──────┘

802.1Q Tag (4B)
┌─────────────────────────────────────────────────┐
│                  802.1Q Tag                     │
│                     4B                          │
├─────────────────┬───────────────────────────────┤
│      TPID       │              TCI              │
│       2B        │              2B               │
├─────────────────┼───────┬───┬───────────────────┤
│     0x8100      │  Pri  │CFI|       VID         │
│       2B        │  3b   │1b │       12b         |
└─────────────────┴───────┴───┴───────────────────┘

字段	长度	说明
TPID	2B	Tag Protocol Identifier，固定值 0x8100
TCI	2B	Tag Control Information
Pri	3b	优先级，0-7，用于 QoS 优先级划分
CFI	1b	Canonical Format Indicator，以太网为 0
VID	12b	VLAN ID，取值范围 1-4094，0 和 4095 保留

Footnotes

1. 是多项式除法！所以不能借位，并且是环上的加减法 ↩

2. 发送端占用信道传输有效数据的时间比例。 ↩