postgraduate-prep/subjects/cn/03_数据链路层.md

数据链路层

1. 数据链路层功能

功能	说明
组帧	将网络层数据包封装成帧，添加首部和尾部
差错控制	检测或纠正传输中的比特错误
流量控制	协调收发双方速率，防止接收方溢出
介质访问控制	控制多个节点共享信道时的有序访问（MAC 子层）
链路管理	建立、维护、释放数据链路连接

服务访问点（SAP）：网络层与数据链路层的接口，帧中通过类型字段（EtherType）标识上层协议。

2. 组帧（Framing）

2.1 字符计数法

• 帧首部用计数字段标识帧长
• 计数字段出错则无法同步，现已很少使用

2.2 字符填充法

• 用特殊标志字符界定帧的起止（如 DLE STX / DLE ETX）
• 数据中出现标志字符时在其前插入转义字符 DLE

2.3 零比特填充法（HDLC）

• 以 01111110 作为帧边界
• 数据中每出现连续的 5 个 1 后自动插入一个 0（透明传输）
• 接收端检测到 01111110 即帧边界，自动删除数据中的填充 0

2.4 物理层编码违例法

• 利用物理层编码的冗余信号表示帧边界（如曼彻斯特编码的高-高/低-低）

3. 差错控制

3.1 检错编码

编码	原理	特点
奇偶校验	添加一位使 1 个数为奇/偶	只能检出奇数位错误，检错率低
循环冗余校验（CRC）	数据多项式除以生成多项式，余数作为 FCS	检错能力强，硬件实现简单

CRC 步骤：

1. 选定生成多项式 $G(x)$，阶数为 r
2. 数据后补 r 个 0，模 2 除以 $G(x)$（异或运算）
3. 余数（r 位）即为帧检验序列（FCS），替换补的 0
4. 接收端用同一 G(x) 除整个帧，余数为 0 则无错

CRC 是检错码，不是纠错码，发现错误后要求重传。

3.2 纠错编码（海明码）

海明不等式：$2^k \ge n + k + 1$，其中 n 为有效数据的位数，k 为校验位的位数。

校验位位置：放在 2^{i} 位置（$i = 0,1,2,\dots$），即第 1,2,4,8,\dots 位。

检错与纠错：每个校验位负责一组数据位，出错时多个校验位联合定位错误位，可纠正 1 位错误。

能力	说明
检 2 位错 + 纠 1 位错	增加一位全局奇偶校验位实现
仅纠 1 位错	标准海明码

4. 流量控制与可靠传输机制

4.1 停止-等待协议（Stop-and-Wait）

• 发送方每发一帧，等待 ACK 后再发下一帧
• 超时未收到 ACK 则重传（需编号区分重复帧）
• 信道利用率很低：U = \dfrac{T_D}{T_D + RTT + T_A}

在卫星链路等高延迟信道中效率极低，仅适用于低带宽或简单场景。

4.2 后退 N 帧协议（GBN）

• 发送窗口 $W_T > 1$，接收窗口 W_R = 1
• 发送方可连续发多帧，接收方只按序接收
• 某帧出错 → 丢弃该帧及之后所有帧，发送方超时后从出错帧开始全部重发
• 信道利用率高于停等，但大量重传浪费带宽

4.3 选择重传协议（SR）

• 发送窗口 $W_T > 1$，接收窗口 W_R > 1
• 接收方缓存乱序到达的正确帧，仅要求重传出错帧
• 窗口大小限制：$W_{\max} = 2^{n-1}$（n 为帧序号位数）
• 信道利用率最高，但实现复杂

三个协议对比：

协议	发送窗口	接收窗口	重传策略	利用率
停等	1	1	出错帧超时重发	最低
GBN	>1	1	从出错帧起全部重传	中等
SR	>1	>1	仅重传出错帧	最高

滑动窗口机制：帧序号位数 n 决定可用序号空间 $[0, 2^n-1]$，窗口大小不得超过序号空间的一半或总数（SR 要求 $W_T + W_R \le 2^n$）。

5. 介质访问控制（MAC）

5.1 信道划分介质访问控制

基于复用技术，各节点共享信道而互不干扰：

方式	原理	典型应用
频分多路复用（FDMA）	各节点占用不同频率	广播电视、ADSL
时分多路复用（TDMA）	各节点占用不同时隙	2G GSM
码分多路复用（CDMA）	各节点使用正交码序列	3G 移动通信
波分多路复用（WDMA）	各节点使用不同波长	光纤通信

5.2 随机访问介质访问控制

协议	核心思想	特点
ALOHA	有数据直接发，冲突后随机等待重发	纯 ALOHA 利用率 $1/2e$，时隙 ALOHA 1/e
CSMA	发前先听信道，忙则等待	非坚持/1-坚持/p-坚持三种策略
CSMA/CD	边发边听，检测到冲突立即停止（有线）	用于以太网，最小帧长确保冲突检测
CSMA/CA	发前先预约信道（无线）	用于 802.11 WLAN，避免隐蔽站问题

CSMA/CD 要点：

• 争用期（碰撞窗口）= $2\tau$（\tau 为单程传播时延）
• 最小帧长 = 争用期 × 数据传输速率
• 二进制指数退避算法：第 i 次冲突后从 [0, 2^i-1] 随机选退避时间

5.3 轮询访问介质访问控制

方式	原理	特点
轮询（Polling）	主节点依次询问从节点	无冲突，但有轮询开销和等待延迟
令牌传递（Token Passing）	持有令牌的节点才能发送	用于令牌环网和令牌总线

6. 局域网

6.1 以太网（Ethernet，IEEE 802.3）

MAC 地址：48 位全球唯一地址，前 24 位为 OUI（厂商代码），后 24 位为序列号。

以太网帧格式：

字段	前导码	定界符	MAC 目的地址	MAC 源地址	长度/类型	数据	填充	FCS（CRC）
长度（B）	7	1	6	6	2	46-1500	可变	4

最小帧长 64B：保证在检测到冲突前帧尚未发送完毕（CSMA/CD 要求）。数据不足 46B 时需填充。

以太网速率演进：

标准	速率	介质
10BASE-T	10 Mbps	双绞线
100BASE-T（快速以太网）	100 Mbps	双绞线
1000BASE-T（千兆以太网）	1 Gbps	双绞线/光纤
10GBASE-T（万兆以太网）	10 Gbps	光纤/双绞线

6.2 虚拟局域网（VLAN）

• 基于交换机端口/MAC 地址/协议/IP 子网等划分逻辑工作组
• IEEE 802.1Q 帧标记：在标准以太网帧中插入 4B VLAN 标记（VID 12 位），最大 4096 个 VLAN
• 隔离广播域，提高安全性和灵活性

6.3 无线局域网（WLAN，IEEE 802.11）

CSMA/CA：发送前先等待 DIFS，然后退避随机时间；接收方回复 ACK 前等待 SIFS。

帧类型：

类型	用途
管理帧	关联、认证、信标（Beacon）
控制帧	RTS/CTS、ACK
数据帧	传输上层数据

隐蔽站问题：站 A 和 C 分别位于 AP 两侧，彼此无法感知对方发送，使用 RTS/CTS（请求发送/允许发送）解决。

7. 广域网

7.1 PPP 协议（点对点协议）

• 提供点对点链路上的数据封装
• 三个组件：HDLC 封装、LCP（链路控制协议）、NCP（网络控制协议）
• 透明传输：异步链路用字符填充法，同步链路用零比特填充法
• 无需流量控制和纠错（只做检错）

PPP 常用于拨号上网、PPPoE（以太网上的 PPP，宽带接入）。

7.2 HDLC 协议（高级数据链路控制）

• 面向比特的同步链路控制协议
• 三种站：主站（命令）、从站（响应）、复合站
• 三种帧：信息帧（I）、监控帧（S）、无编号帧（U）
• 使用零比特填充法透明传输

PPP vs HDLC：

特性	PPP	HDLC
面向方式	字节	比特
透明传输	字符填充/零比特填充	零比特填充
ACK	不需要	需要
差错控制	只检错	检错 + 重传
流量控制	不支持	滑动窗口

8. 数据链路层设备

设备	层级	转发依据	功能
网桥	2	MAC 地址	隔离冲突域（不隔离广播域），连接两个网段
交换机	2	MAC 地址	多端口的网桥，全双工，每个端口独立带宽

冲突域：同一时刻只能有一台设备发送数据的区域（交换机每个端口独立冲突域）。 广播域：广播帧能到达的范围（交换机不隔离广播域，VLAN 可隔离）。

自学习算法（交换机/网桥地址表建立）：

1. 收到帧时记录源 MAC 地址及入端口
2. 目的 MAC 在表中 → 只转发到对应端口
3. 目的 MAC 不在表中 → 从所有端口广播（洪泛）
4. 地址表条目有老化时间

交换机三种交换方式：

方式	转发时机	延迟	错误检测
直通交换	只查目的 MAC 地址即转发	低	无
存储转发	完整接收一帧，查 FCS 无误后转发	高	完整检测
无碎片交换	接收前 64B（最小帧长）后转发	中	可滤除冲突碎片