Lecture 9：思维导图 - 数据链路层

描述：数据链路层在相邻节点间传输帧。主线是：把网络层分组封装成帧并透明传输；检出比特差错；在需要时以 ARQ 提供可靠传输。局域网侧再延伸到 MAC、以太网、交换机、VLAN 和 802.11 无线 LAN。

NOTE · 原始知识网（点击展开）

本篇按“链路层基本问题 → PPP 点到点链路 → 共享介质访问 → 以太网与交换 → VLAN → 802.11 WLAN”整理。公式中的传播时延、发送时延和窗口均先统一单位；涉及 ACK 编号时以题目给出的语义为准。

3.1 数据链路层的三大功能

NOTE · 教材补充：链路、数据链路与服务边界 链路是相邻节点之间的物理通道；数据链路是在物理链路上加入实现帧同步、介质访问、差错处理等所需的硬件和协议后形成的逻辑传输通道。数据链路层主要解决同一段链路上相邻节点间的帧传送，不负责跨越多台路由器的端到端选路。

不同链路协议可向网络层提供不同强度的服务：

这些是服务模型，不等于所有数据链路协议都必须实现三种。链路层是否重传、是否流量控制，必须看具体协议；以太网能用 FCS 检错并丢弃坏帧，但通常不在 MAC 层为普通数据帧确认和重传。

网络层分组
   -> 封装成帧与透明传输
   -> 差错检测
   -> 发生差错后按需可靠传输
   -> 相邻节点的网络层

3.1.1 封装成帧与透明传输

• 封装成帧：在网络层分组前后加入首部、尾部，形成帧；首部/尾部包含地址、控制、帧界定、检错等信息。
• 透明传输：无论帧的数据部分出现何种比特组合，接收端均能正确还原原始数据，不把数据误认为帧定界符。
• 若数据中恰出现帧首/尾界定符，就会破坏边界，需字节填充或比特填充。
• MTU（最大传送单元）限制一帧数据部分可封装的最大网络层分组；超过 MTU 时需由上层或网络层按协议规则处理。

PPP 是点到点链路常见协议：异步链路采用字节填充，同步链路采用零比特填充；HDLC 等比特面向协议也常结合比特填充。

3.1.2 差错检测

若生成多项式 $G(x)$ 的最高次数为 $r$，发送端把数据 $M$ 左移 $r$ 位，再做模 2 除法：

$$R=(M\cdot 2^r)\bmod G$$

发送序列为 $M\cdot2^r+R$。模 2 加减均为异或，不产生进位或借位。接收端用同一 $G$ 相除；余数非 0 可判错，余数为 0 只表示“未检出错误”，并非数学上绝对无错。

CRC 是检错机制，不自动纠错；FCS 是帧中实际携带的检错序列。校验失败后是否重传由可靠传输协议决定。

3.1.3 可靠传输

无线链路误码率较高，常要求链路层向网络层提供可靠传输。核心机制是确认、序号、超时和重传。

其中 $m$ 为帧序号位数，序号空间为 $2^m$。一般约束为：

$$GBN:\quad W_S\le2^m-1$$

$$SR:\quad W_S+W_R\le2^m$$

若 SR 收发窗口相等，则 $W_S=W_R\le2^{m-1}$。ACK i 可能表示“已经确认到帧 $i$”，也可能表示“下一期待帧为 $i$”；必须先读题目定义。

设 $T_D$、$T_A$ 分别为数据帧和确认帧的发送时延，$T_p$ 为单向传播时延。忽略处理与排队时延时，停止等待利用率为：

$$U=\frac{T_D}{T_D+2T_p+T_A}$$

若发送窗口为 $W$，忽略处理时间，流水线发送时间利用率为：

$$U=\min\left(1,\frac{WT_D}{T_D+2T_p+T_A}\right)$$

满流水至少需要：

$$W_{min}=\left\lceil\frac{T_D+2T_p+T_A}{T_D}\right\rceil$$

若题目给的是“往返传播时延”，可直接用它替换 $2T_p$；若给的是从开始发送数据帧到完整收到 ACK 的实测确认周期，则该数值通常已含 $T_D$、$T_A$，不能再重复相加。这里不把含处理、排队和发送时延的广义网络 RTT 与 $2T_p$ 混为一谈。

流水线协议可同时发送多帧，提升链路利用率；窗口大小受序号位数、带宽时延积和接收缓冲限制。若题目问有效载荷 goodput，还需在 $U\times R$ 基础上乘 $L_{payload}/L_{frame}$，不能把首部、尾部和填充当作有效载荷。

3.2 点对点协议 PPP

PPP 面向点到点全双工链路，可承载多种网络层协议。它结构简单、支持链路参数协商和身份鉴别，但不提供序号、确认、重传与流量控制；FCS 出错的帧直接丢弃，因此 PPP 本身提供无连接、不可靠的数据报服务。

3.2.1 PPP 的组成与帧格式

PPP 由三部分组成：

1. 封装方法：把 IP 等网络层分组封装为 PPP 帧，并用 FCS 检错。
2. LCP（链路控制协议）：建立、配置、测试和终止数据链路，可协商 MRU、鉴别协议等参数。
3. NCP（网络控制协议）：为不同网络层协议配置参数；承载 IPv4 时常用 IPCP。

| Flag | Address | Control | Protocol | Information | FCS | Flag |
|  1B  |   1B    |   1B    |  1/2B    | 0~1500B*   |2/4B |  1B  |
   7E       FF        03

* 信息字段默认最大长度为 1500 B，可经 LCP 协商。Protocol 指明信息字段承载 IP、LCP、NCP 等哪类分组。首尾 Flag=0x7E 可共用；Address=0xFF、Control=0x03 在常规 PPP 中固定，不承担多站寻址或可靠传输序号功能。

3.2.2 透明传输

WARNING · 易错 “加 0x20”不是通用反转义规则。PPP 异步字节转义的统一表达是与 0x20 异或；例如 0x5E XOR 0x20 = 0x7E。

3.2.3 链路工作阶段

flowchart LR
    A[静止] -->|检测到载波| B[建立]
    B -->|LCP 协商成功| C{需要鉴别?}
    C -->|是| D[鉴别]
    C -->|否| E[网络]
    D -->|鉴别成功| E
    E -->|NCP 配置完成| F[打开]
    F -->|传送网络层分组| F
    F -->|链路关闭/故障| G[终止]
    G --> A

链路主线是“静止 → 建立 → 可选鉴别 → 网络 → 打开 → 终止”。LCP 管链路本身，NCP 配置对应网络层协议；二者不能混淆。

3.3 MAC 与局域网

IEEE 802 把局域网数据链路层划分为 LLC（逻辑链路控制）与 MAC（介质访问控制）两个子层。LLC 向网络层提供统一接口；MAC 负责成帧、MAC 寻址以及共享介质访问。现代以太网考题主要集中在 MAC 帧、交换与 VLAN。

3.3.1 介质访问控制方法

广播信道上多个站共享介质，必须决定“谁在何时发送”。常见方法可分为：

• 纯 ALOHA：随时发送，碰撞后随机重传；易受干扰时间为两倍帧时，最大吞吐量 $1/(2e)\approx18.4%$。
• 时隙 ALOHA：只能在时隙边界发送，最大吞吐量 $1/e\approx36.8%$。
• 1-坚持 CSMA：信道空闲立即发送，忙则持续监听；容易在刚转为空闲时集中碰撞。
• 非坚持 CSMA：忙时随机等待后再监听，碰撞较少但时延和空闲浪费可能增大。
• $p$-坚持 CSMA：时隙信道空闲时以概率 $p$ 发送，以 $1-p$ 推迟到下一时隙。

纯 ALOHA 与时隙 ALOHA 的上述最大吞吐量来自固定帧长、独立随机发送/重传且总到达近似泊松过程的经典模型；它们用于比较协议机制，不应脱离这些假设当作任意实际网络的固定上限。

轮询访问

NOTE · 教材补充 轮询由一个主控站按顺序询问各从站是否需要发送。只有获得许可的站才能占用信道，因此正常工作时不会因争用而碰撞。

sequenceDiagram
    participant C as 主控站
    participant A as 站 A
    participant B as 站 B
    C->>A: POLL：是否发送
    A-->>C: 数据或“无数据”
    C->>B: POLL：是否发送
    B-->>C: 数据或“无数据”

• 优点：访问次序确定，可给出等待时间上界；负载高时不会把大量带宽浪费在碰撞和随机退避上，也便于按优先级或配额调度。
• 开销：每次询问、应答和主控站切换都占用时间；大量空闲站仍会产生轮询开销，低负载下往往不如随机访问灵活。
• 故障边界：主控站是单点故障；某从站无响应时，主控站必须依靠超时跳过，否则整个轮询可能停滞。
• 等待上界：正常、有限站点且每站占用时间受限时，一个站最多等待一轮轮询；若允许某站无限期占用，便不能据此声称有界等待。

令牌传递

NOTE · 教材补充 令牌是一个表示“发送许可”的特殊控制帧。站点按规定的逻辑顺序传递令牌，只有持有令牌的站可发送；发送完毕或达到持有时间上限后，再把令牌交给下一站。

flowchart LR
    A[站 A] -->|令牌| B[站 B]
    B -->|令牌| C[站 C]
    C -->|令牌| D[站 D]
    D -->|令牌| A

• 优点：正常情况下无碰撞；每站最长持有时间受限时可形成有界等待，重负载下吞吐量和时延比随机争用更可预测。
• 开销：即使没有数据，也要传递令牌；站点少、负载低或环很长时，等待令牌本身可能比直接争用更慢。
• 管理问题：令牌丢失需要监测并重新生成；重复令牌必须删除；站点或链路故障时还要重构逻辑环。系统必须保证“恢复令牌”不会长期产生多个有效令牌。
• 逻辑环不等于物理环：令牌传递描述的是发送权的逻辑顺序，具体物理拓扑与实现可以不同，不能仅凭“有令牌”断定所有链路一定是物理环形。

三类方法的负载边界

以上只是一般取舍，不是绝对结论；传播时延、站点数量、帧长分布、优先级和实现协议都会改变实际性能。

3.3.2 MAC 地址与以太网帧

MAC 地址是网络接口的链路层标识，IEEE 802 MAC 通常为 48 bit：前 24 bit 通常含 OUI 厂商标识，后 24 bit 由厂商分配。一个 48 bit 地址常写作 6 个十六进制字节，如 02-11-22-33-44-55。

• 单播目的地址只交付给一个接口；广播 MAC 为 FF-FF-FF-FF-FF-FF；多播有特定地址范围。
• MAC 只用于同一链路/局域网内交付；跨网通信仍靠 IP 与路由。
• 首字节最低有效位是 I/G 位：0 表示单个地址，1 表示组地址（多播/广播）。次低位是 U/L 位：0 表示全局管理，1 表示本地管理。
• 判断 I/G、U/L 位时看首字节的低位，不要误看整串地址最右端。

Ethernet II 与 IEEE 802.3

前导码 7B | SFD 1B | 目的 6B | 源 6B | 类型/长度 2B | 数据+填充 46~1500B | FCS 4B
                       <------------ MAC 帧：64~1518B ------------>

• MAC 帧最小 64 B、最大 1518 B，均从目的 MAC 算到 FCS；不包含 7 B 前导码与 1 B 帧开始定界符 SFD。
• 最小数据字段为 46 B，不足时补填充；接收端如何区分有效数据与填充依赖上层长度信息。
• 相邻以太网帧之间至少保留 96 bit time 的帧间间隔。
• IEEE 802.1Q 在源 MAC 后插入 4 B VLAN 标签（常见 TPID 为 0x8100），普通最大标记帧由 1518 B 增至 1522 B。

3.3.3 共享式以太网：CSMA/CD

共享总线/集线器以太网使用 CSMA/CD：先载波监听，空闲再发送；边发边检测冲突，冲突后立即停止、发送强化干扰信号，按截断二进制指数退避等待后重发。

• 只有共享、半双工以太网需要 CSMA/CD；交换式全双工以太网无冲突，不使用它。
• 最小帧长保证发送端在发送结束前能检测最远端冲突；最远端往返传播时间决定槽时间。

设最远两站单向传播时延为 $\tau$、链路速率为 $R$：

$$T_{frame}\ge2\tau,\qquad L_{min}\ge2\tau R$$

争用期（槽时间）为 $2\tau$。传统以太网将其取为 512 bit time；10 Mb/s 下为 $51.2,\mu s$。发生第 $i$ 次碰撞后：

$$k=\min(i,10),\qquad r\in{0,1,\ldots,2^k-1}$$

$$T_{backoff}=r\times512\text{ bit time}$$

发送站检测到碰撞后立即停止当前帧、发送强化干扰信号，再退避重传；连续碰撞 16 次仍失败则放弃并向上层报告。常用近似效率公式为：

$$\eta\approx\frac{1}{1+5a},\qquad a=\frac{\tau}{T_{frame}}$$

它用于估算传播时延相对帧发送时间对效率的影响；若题目给出另一模型或精确参数，以题设为准。

3.3.4 集线器、网桥与交换机

交换机是多端口二层设备，维护 MAC 地址表。对每个到达帧，先按源 MAC + 入端口学习或刷新表项，再处理目的 MAC：

flowchart TD
    A[帧从端口 P 到达] --> B[学习/刷新 源MAC -> P]
    B --> C{目的MAC是否已知?}
    C -->|否/广播/需泛洪的多播| D[向除 P 外的本 VLAN 端口泛洪]
    C -->|是| E{目的端口是否等于 P?}
    E -->|是| F[过滤/丢弃 不再转发]
    E -->|否| G[只向表中目的端口转发]

• MAC 表是动态软状态；超时未刷新会老化删除，主机移动后也可通过新源帧更新端口。
• 未知单播泛洪不等于广播：目的 MAC 仍是单播，只是交换机暂时不知道出口。
• 透明网桥/交换网络若存在二层环路，泛洪帧可能无限循环并造成广播风暴；STP 通过逻辑阻塞冗余路径形成无环生成树，链路故障时可重新收敛。

生成树协议 STP

NOTE · 教材补充 以太网帧没有类似 IP TTL 的逐跳寿命字段。二层出现环路时，广播、未知单播或某些多播帧可能不断复制循环，同时导致 MAC 表在不同端口间反复抖动。STP 保留物理冗余链路，但把部分端口置为不转发状态，使当前的逻辑转发拓扑成为一棵无环树。

经典 STP 的选举主线是：

1. 选根桥：桥 ID 最小的交换机成为根桥；桥 ID 由优先级和地址等字段共同决定，不能只比较 MAC 地址而忽略优先级。
2. 选根端口：每台非根交换机选择一条到根桥累计路径开销最小的端口作为根端口；并列时再按上游桥 ID、端口 ID 等规则打破平局。
3. 选指定端口：每个网段选择到根桥路径最优的桥所连接端口作为该段指定端口，负责向该网段转发。
4. 阻塞剩余冗余端口：根端口和指定端口参与正常转发，其他端口不转发普通数据帧，从而切断环路。

交换机用 BPDU 交换根桥、路径开销和拓扑信息。链路或设备故障后会重新计算并启用备用路径，因此 STP 的目的不是删除冗余，而是在某一时刻只让无环子集转发。重新收敛期间可能短时中断；RSTP 等改进协议用于加快状态迁移。

flowchart TD
    R[根桥] -->|转发| A[交换机 A]
    R -->|转发| B[交换机 B]
    A -.冗余链路：一端阻塞.- B

交换方式

• 每端口形成独立冲突域；全双工下不发生冲突。
• 交换机的学习、转发、泛洪、老化是高频考点，不能把它写成路由器的 IP 路由表。

冲突域与广播域示意

主机 -- Hub -- 主机       整个 Hub：1 个冲突域、1 个广播域
          |
        Switch            每个交换机端口：独立冲突域
       /      \
   VLAN 10   VLAN 20      每个 VLAN：独立广播域
       \      /
       三层转发            跨 VLAN 必须经过路由/三层交换

3.3.5 VLAN

VLAN 在交换网络中把一个物理 LAN 划分为多个逻辑广播域，隔离广播流量、改善安全与管理。

跨 VLAN 的三层通信必须经过路由/三层交换，二层交换机本身不会跨 VLAN 转发广播域流量。

3.3.6 以太网速率演进

速率提升没有改变 48 bit MAC 地址与常见以太网 MAC 帧主体。判断是否使用 CSMA/CD 的关键不是“是否叫以太网”，而是链路是否处于共享、半双工冲突域。

3.4 无线局域网 IEEE 802.11

无线介质不能可靠边发边听，存在隐藏站等问题，故 802.11 使用 CSMA/CA（载波侦听多路访问/冲突避免），而不是 CSMA/CD。

3.4.1 体系结构

• 基础设施网络：STA 先与 AP 关联，通常通过 AP 转发，即使通信双方处于同一 BSS。
• Ad hoc/IBSS：没有 AP，站点临时组成独立基本服务集并直接通信。
• SSID 是网络名，BSSID 标识具体 BSS，BSA 是覆盖区域；三者不要混淆。

3.4.2 CSMA/CA 与帧间间隔

• 发送前进行物理/虚拟载波监听；新到达的帧若发现信道已持续空闲 DIFS，可按规则直接发送。若信道忙、需要重传或处于发送后退避，则在信道重新空闲 DIFS 后执行随机退避。
• 对典型普通单播数据帧，计数到 0 后发送 DATA；接收方经 SIFS 回 ACK。未收到预期 ACK 时按规则扩大竞争窗口并重试，直到成功或达到重试上限；组播/广播通常不逐帧 ACK，块确认等模式另有确认方式。
• RTS/CTS 可缓解隐藏站：RTS、CTS 中携带持续时间，旁听站设置 NAV 虚拟载波监听。
• SIFS 小于 DIFS，使 ACK、CTS 等即时控制帧优先于普通竞争发送。

帧间间隔优先级为：

$$SIFS<PIFS<DIFS$$

退避计数每经过一个空闲时隙减 1；一旦介质变忙就冻结，待介质再次空闲并持续 DIFS 后从剩余值继续，而不是重新抽取。发送失败时扩大竞争窗口；成功后按规则执行发送后退避，防止单个站持续独占。

3.4.3 隐藏站、RTS/CTS 与 NAV

• 隐藏站：A、C 彼此听不到，却都能到达同一 AP；二者同时发送会在 AP 处碰撞。
• 暴露站：某站听到邻站发送后过度退避，但它向另一接收方发送本可不造成干扰，导致空间复用下降。
• RTS/CTS 主要缓解隐藏站：旁听 RTS 或 CTS 的站按 Duration 设置 NAV，在预约期内保持静默。它不能消除控制帧碰撞、误码或所有无线冲突。

CTS 发出后的 NAV 为：

$$NAV_{CTS}=SIFS+T_{DATA}+SIFS+T_{ACK}$$

sequenceDiagram
    participant S as 发送站
    participant A as AP/接收站
    participant O as 其他站
    Note over S,O: 信道空闲 DIFS，发送站完成随机退避
    S->>A: RTS（预约剩余时间）
    Note over S,A: SIFS
    A->>S: CTS
    A-->>O: 其他站旁听同一 CTS（非 MAC 广播）并设置 NAV
    Note over S,A: SIFS
    S->>A: DATA
    Note over S,A: SIFS
    A->>S: ACK

3.4.4 802.11 地址字段

RA/TA 是当前无线一跳的接收方/发送方，DA/SA 是 MSDU 的最终目的/原始源。普通基础设施 BSS 最常考 To DS=1, From DS=0 与 To DS=0, From DS=1；四地址同时使用主要见无线分配系统桥接。

3.5 高频边界与易错点

• 数据链路层解决相邻节点的帧传输；端到端可靠性属于运输层问题，二者层次不同。
• CRC/FCS 是检错，不等于纠错或自动重传；余数为 0 也只能说“未检出错误”。
• PPP 有 FCS 却仍不可靠，因为它没有序号、ACK、超时重传和流量控制。
• 以太网 64~1518 B 不含前导码与 SFD；802.1Q 普通最大标记帧为 1522 B，帧间间隔为 96 bit time。
• Hub 不隔离冲突域；交换机每端口隔离冲突域，但同一 VLAN 默认仍属于同一广播域。
• 交换机按源 MAC 学习、按目的 MAC 查表；目的端口等于入端口时过滤，未知单播才泛洪。
• 全双工交换式以太网不使用 CSMA/CD；10 Gb/s 以太网只支持全双工。
• VLAN 是二层广播域划分；跨 VLAN 必须三层转发。Access、Trunk、Hybrid 的具体标签行为要结合 PVID/端口配置。
• 802.11 用 CSMA/CA，退避遇忙冻结；RTS/CTS 缓解但不能彻底消除隐藏站和碰撞。

3.6 题型索引

• 1 题型 - 三种可靠传输协议：停止等待、GBN、SR 的窗口、ACK 与重传范围。
• 2 题型 - 信道利用率相关计算：传播/发送时延、流水窗口、序号位数与 goodput。
• 3 题型 - CSMA CD相关信息计算：争用期、最小帧长、Hub 延迟与二进制指数退避。
• 4 题型 - 透明传输与PPP协议：零比特填充、字节反转义、PPP 状态与不可靠性。
• 5 题型 - CSMA CA协议：SIFS/DIFS、退避、RTS/CTS、NAV 与四地址映射。

相关知识

• 科目导航：计算机网络导航
• 阅读顺序：上一篇：检错与纠错机制 · 下一篇：三种可靠传输协议

3.7 本节复盘

• 数据链路层围绕“成帧透明传输、检错、可靠传输”展开；透明传输靠字节/比特填充。
• CRC 用模 2 除法检错；停止等待、GBN、SR 通过确认、序号、超时重传提供不同程度的可靠性与效率。
• MAC 是二层本地标识；共享以太网用 CSMA/CD，交换式全双工不使用 CSMA/CD。
• 交换机按源 MAC 学习、按目的 MAC 转发；VLAN 划分逻辑广播域，跨 VLAN 需三层转发。
• 802.11 用 CSMA/CA、退避及可选 RTS/CTS 缓解无线冲突/隐藏站；典型单播交换另用 ACK/重传提高单跳可靠性，不能概括为所有帧必达或逐帧确认。
• PPP 由封装、LCP 和 NCP 组成；同步链路零比特填充，异步链路按 XOR 0x20 字节转义。
• 以太网帧、VLAN 标签、交换机学习/STP 与 WLAN 四地址必须结合具体字段和转发方向判断，不能只背设备层次。