数据链路层

3.1 数据链路层的功能

数据链路层在物理层之上，负责在相邻节点之间以帧为单位传输数据。

三大基本功能

  1. 帧定界：从物理层的比特流中识别出帧的开始和结束
  2. 透明传输：不管数据是什么样的比特组合，都能正确传输
  3. 差错控制：检测（和纠正）传输过程中出现的差错

为什么需要数据链路层？ 物理层只管传输原始比特流，但比特在传输过程中可能出错（0变1、1变0），而且接收方需要知道从哪里开始解析数据——这些都由数据链路层解决。

3.2 组帧方法

组帧的目的：让接收方能够从连续到达的比特流中准确找出每个帧的边界。

方法 原理 优点 缺点
字符计数法 帧首部用字段标明帧长度 简单 计数字段一旦出错，后续全乱
字符填充法 用特殊字符（DLE STX/ETX）定界，转义填充 易理解 依赖ASCII字符，不适合二进制
零比特填充法 用01111110定界，连续5个1后面加0 透明传输好 只适合二进制
违规编码法 用违反编码规则的信号定界 不需填充 编码需要冗余

重点：零比特填充法（HDLC使用）

  • 帧定界符：01111110（6个连续的1）
  • 发送方：每发现5个连续的1，就在后面插入一个0
  • 接收方：每发现5个连续的1，就删除后面的0
  • 确保数据中不会出现6个连续的1

💡 记忆技巧："看到五个一，就插一个零"——像交通规则一样简单。

3.3 差错控制——CRC循环冗余检验（重中之重！）

基本原理

  • 发送方：数据 + 冗余码（FCS，帧检验序列）一起发送
  • 接收方：用同样的除数做除法，余数为0则无差错

CRC计算步骤

  1. 确定生成多项式G(x)，得到除数（二进制）
  2. 在原始数据后面补k个0（k = 生成多项式的最高次幂）
  3. 用补0后的数据除以除数（模2除法，即异或运算，不借位）
  4. 余数就是FCS（如果位数不足k位，前面补0）
  5. 将FCS替换补的k个0得到最终发送帧

模2除法规则：按位异或——相同为0，不同为1。每次除的时候看被除数最高位，如果是1就除（异或），如果是0就跳过。

典型例题

例1：数据为101001，生成多项式为G(x) = x³ + x² + 1（即除数1101），求发送的码字。

解：

  • G(x)最高次幂为3，补3个0：101001000
  • 执行模2除法：
       110101
1101 | 101001000
       1101
       ----
        1110
        1101
        ----
         0110
         0000
         ----
          1100
          1101
          ----
           010
          换成三位：010
  • 余数 = 010
  • 发送码字 = 101001010

接收方用1101除101001010，余数为0则正确。

例2：如果一个CRC生成多项式为G(x) = x⁴ + x + 1，要发送的数据为1101011011，求发送的比特序列。

解：

  • G(x) = 10011（x⁴ + x + 1中，x⁴系数为1，x³系数为0，x²系数为0，x¹系数为1，x⁰系数为1）
  • 补4个0：11010110110000

执行模2除法：

       1100001010
10011 | 11010110110000
        10011
        -----
         10011
         10011
         -----
          00001  → 前5位是00001，最高位为0，直接下一位
          00011 → 最高位0
          00110
          01100 → 最高位0
          11000
          10011
          -----
          10110
          10011
          -----
           01010
           00000
           -----
            10100
            10011
            -----
              0111
  • 余数 = 0111（补足4位）
  • 发送码字 = 11010110110111

📌 408考点提示：CRC计算几乎每年都考！练习时要做到：

  1. 能根据生成多项式写出除数
  2. 熟练进行模2除法
  3. 知道FCS的位数 = 生成多项式的最高次幂

3.4 海明码（纠错编码——重点！）

海明码可以检测并纠正一位错误，也可以检测多位错误（需要更多冗余位）。

海明码计算步骤

  1. 确定校验位个数r：2ʳ ≥ n + r + 1（n为数据位数，r为校验位数）
  2. 将校验位放在2ⁱ的位置（i=0,1,2,...，即第1,2,4,8,...位）
  3. 每个数据位被多个校验位校验，校验位负责所有使其下标二进制对应位为1的数据位
  4. 校验位的值 = 它所负责的所有数据位的异或（偶校验）或同或（奇校验）

典型例题

例3：数据1011，求海明码。

解：

  • n=4，找r：2³=8 ≥ 4+3+1=8 ✓，所以r=3
  • 编码后7位：位置1,2,3,4,5,6,7
  • 校验位位置：1,2,4（2⁰, 2¹, 2²）
  • 数据位位置：3,5,6,7（其他位置）
  • 设数据：D1=1在位置3，D2=0在位置5，D3=1在位置6，D4=1在位置7

求校验位：

  • P1（位置1）：校验所有位置二进制第0位为1的位（位置1,3,5,7）
    • P1 ⊕ D1 ⊕ D2 ⊕ D4 = P1 ⊕ 1 ⊕ 0 ⊕ 1 = 0 → P1 = 0
  • P2（位置2）：校验位置二进制第1位为1的位（位置2,3,6,7）
    • P2 ⊕ D1 ⊕ D3 ⊕ D4 = P2 ⊕ 1 ⊕ 1 ⊕ 1 = 0 → P2 = 1
  • P3（位置4）：校验位置二进制第2位为1的位（位置4,5,6,7）
    • P3 ⊕ D2 ⊕ D3 ⊕ D4 = P3 ⊕ 0 ⊕ 1 ⊕ 1 = 0 → P3 = 0

海明码序列：位置1-7 = 0(P1) 1(P2) 1(D1) 0(P3) 0(D2) 1(D3) 1(D4) = 0110011

纠错：如果有错误，重新计算校验位的值，组成二进制数指出错误位置。

  • 例如：收到0110111（位置6从1变0），重新计算：
    • P1' = 0⊕1⊕0⊕1 = 0
    • P2' = 1⊕1⊕0⊕1 = 1
    • P3' = 0⊕0⊕0⊕1 = 1
  • 二进制110 = 6 → 第6位出错！

📌 408考点提示：海明码通常考选择题（给定数据求海明码或定位错误位），务必熟练计算流程。

3.5 流量控制与可靠传输机制

为什么需要流量控制？ 发送方发送速度可能超过接收方的处理能力，导致数据丢失。流量控制限制发送速率，防止"快发慢收"。

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

  • 发送方发一帧，等待确认（ACK），收到确认再发下一帧
  • 如果超时没收到ACK，就重传
  • 信道利用率 = Td / (Td + Ta + 2Tp) ≈ Td / (Td + 2Tp)
    • 其中Td为发送时延，Ta为确认帧发送时延，Tp为传播时延
  • 效率很低，不适合高速链路

后退N帧协议（GBN——Go-Back-N）

  • 发送方可以连续发送多个帧（窗口大小 > 1）
  • 如果某帧出错或丢失，发送方后退到该帧，重传该帧及其之后所有帧
  • 接收方只按顺序接收，乱序帧丢弃
  • 窗口大小 ≤ 2ⁿ - 1（n为序号位数）

选择重传协议（SR——Selective Repeat）

  • 发送方连续发送多帧
  • 接收方缓存乱序帧，只重传出错/丢失的帧
  • 窗口大小要求：发送窗口 + 接收窗口 ≤ 2ⁿ，且发送窗口 = 接收窗口（通常）
  • 窗口大小 ≤ 2ⁿ⁻¹

GBN和SR对比

特性 GBN SR
接收方缓存 不需要 需要
重传方式 重传从出错帧开始的所有帧 只重传出错的帧
效率 低（连续重传浪费带宽） 高（只重传必要帧）
窗口大小 ≤ 2ⁿ - 1 ≤ 2ⁿ⁻¹
实现复杂度 简单 较复杂

信道利用率与滑动窗口

信道利用率 = 发送方在一个周期内实际发送数据的时间 / 总时间

  • 对于停止-等待：U = Td / (Td + 2Tp)
  • 对于滑动窗口：U = W × Td / (Td + 2Tp)，其中W为窗口大小

典型例题

例4：在一个50kb/s的卫星信道上，传播时延为270ms，帧长为1500bit，确认帧长度忽略。求停止-等待协议的信道利用率，以及要达到80%利用率需要的窗口大小。

解：

  • Td = 1500 / (50 × 1000) = 1500/50000 = 0.03s = 30ms
  • 2Tp = 2 × 270 = 540ms
  • 停止-等待利用率 = 30 / (30 + 540) = 30/570 ≈ 5.3%
  • 设窗口大小为W，W × 30 / (30 + 540) ≥ 80%
  • W × 30 ≥ 0.8 × 570 = 456
  • W ≥ 15.2，所以窗口至少为16

💡 记忆技巧：停止-等待=发1等1；GBN=出错后退，后面的全重发；SR=谁错就重发谁。

3.6 介质访问控制

信道划分介质访问控制

方式 原理 特点
FDMA（频分多路复用） 不同用户使用不同频率 同时使用，互不干扰
TDMA（时分多路复用） 不同用户使用不同时隙 共享频率，分时使用
CDMA（码分多路复用） 不同用户使用不同码片序列 同时同频，码分隔离

CDMA原理：每个用户分配一个唯一的码片序列，要发1就发送码片序列本身，发0就发送码片序列的反码。接收方用码片序列与接收信号做内积，结果为1→发送1，结果为-1→发送0，结果为0→其他用户信号。

随机访问介质访问控制

ALOHA协议

  • 纯ALOHA：想发就发，冲突后随机等待再发。吞吐率约18.4%
  • 时隙ALOHA：只能在时隙开始时发送，吞吐率约36.8%

CSMA（载波监听多路访问）

协议 监听方式 冲突处理
1-坚持CSMA 信道忙就持续监听 空闲立即发送
非坚持CSMA 信道忙就等待随机时间 空闲立即发送
p-坚持CSMA 信道空闲以概率p发送 用于时隙

CSMA/CD（载波监听多点接入/碰撞检测）——重点！ 以太网使用的协议。核心思想：先听后说，边听边说。

  • 载波监听：发送前先监听信道是否空闲
  • 碰撞检测：发送过程中持续监听，一旦检测到碰撞就停止发送
  • 碰撞后的处理：发送阻塞信号→退避（截断二进制指数退避算法）→重新发送

最短帧长计算——必考！

检测到碰撞的最短时间：2τ（τ为单程传播时延） 在2τ时间内必须持续发送，否则无法检测到碰撞。

最短帧长 = 2τ × 数据传输速率

典型例题

例5：一个CSMA/CD网络，最远两个站点之间的距离为2km，信号传播速度为2×10⁸ m/s，网络速率为10Mb/s，求最短帧长。

解：

  • τ = 2000 / (2 × 10⁸) = 10⁻⁵s = 10μs
  • 2τ = 20μs
  • 最短帧长 = 10 × 10⁶ × 20 × 10⁻⁶ = 200 bit

这就是为什么以太网最小帧长为64B（512bit）——对应2τ ≈ 51.2μs，速度为10Mb/s时的最短帧长。

截断二进制指数退避算法

  • 基本退避时间 = 2τ
  • k = min(重传次数, 10)
  • 重传时间 = r × 2τ，其中r在[0, 2ᵏ-1]中随机取整
  • 重传16次仍不成功则放弃

CSMA/CA（避免碰撞）——无线局域网使用

  • 不能检测碰撞（无线信号强弱差异大）
  • 使用RTS/CTS握手机制避免碰撞
  • 使用确认帧ACK

CSMA/CD 与 CSMA/CA 对比

CSMA/CD CSMA/CA
适用 有线以太网 无线局域网
检测 可以检测碰撞 无法检测碰撞
策略 检测到碰撞就停止 尽量避免碰撞
确认 不需要ACK 需要ACK
握手 无 RTS/CTS

3.7 局域网与以太网

IEEE 802标准系列

  • 802.3：以太网（CSMA/CD）
  • 802.11：无线局域网（WiFi）
  • 802.1Q：VLAN标签

以太网帧格式

以太网V2标准帧（最常用）：

前导码(8B) 目的MAC(6B) 源MAC(6B) 类型(2B) 数据(46~1500B) FCS(4B)
  • 前导码：7B前同步码 + 1B帧开始定界符（接收方同步时钟用）
  • 类型：标识上层协议（0x0800→IP, 0x0806→ARP）
  • 数据：最少46B（不足时需要填充Pad），最多1500B（MTU）
  • FCS：CRC校验，生成多项式G(x) = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

MAC地址（物理地址）

  • 长度48位（6字节），全球唯一
  • 前24位为OUI（厂商代码），后24位为厂家分配的序列号
  • 用十六进制表示为：XX-XX-XX-XX-XX-XX
  • 全1的MAC地址是广播地址（FF-FF-FF-FF-FF-FF）

3.8 网桥和交换机

网桥（Bridge）

  • 工作在数据链路层
  • 连接两个或多个局域网段
  • 根据MAC地址转发帧
  • 能隔离冲突域（不同端口在不同冲突域）

透明网桥的自学习算法（重点！）

自学习过程：

  1. 学习：每收到一个帧，将源MAC地址和到达端口记录在转发表中
  2. 转发：查找帧的目的MAC地址
    • 如果找到目的MAC → 从对应端口转发
    • 如果端口就是接收端口 → 丢弃（不需要转发）
    • 如果找不到 → 从所有其他端口泛洪（flooding）
  3. 老化：转发表中的条目有生命周期，旧的条目被删除

交换机（Switch）

  • 本质是多端口的网桥
  • 工作在数据链路层
  • 每个端口是一个独立的冲突域
  • 全双工工作，无冲突
  • 转发方式：
    • 直通交换：只读取目的MAC就转发，延迟小，但不检查错误
    • 存储转发：接收整个帧并检查CRC后再转发，延迟大，但可靠性高
    • 无碎片交换：接收前64B就转发，折中方案

3.9 虚拟局域网（VLAN）

什么是VLAN？ VLAN将一个物理局域网在逻辑上划分为多个相互隔离的广播域。

优点

  1. 隔离广播域，减少广播流量
  2. 提高安全性（不同VLAN之间默认不通）
  3. 管理灵活（不用改物理布线）

VLAN划分方式

  • 基于端口划分（最常见）
  • 基于MAC地址
  • 基于协议
  • 基于IP子网

802.1Q帧格式 在标准以太网帧中插入4字节VLAN标签：

  • TPI（2B，固定0x8100表示带VLAN标签）
  • PCP（3bit，优先级）
  • DEI（1bit）
  • VID（12bit，VLAN标识符，0~4095，0和4095保留）

📌 408考点提示：数据链路层是408考试的重头戏，分值占比最高之一！

  1. CRC计算（大题或选择题）
  2. CSMA/CD最短帧长计算（经典题型）
  3. 滑动窗口协议的信道利用率计算（必考）
  4. 交换机自学习过程（选择题常见）
  5. VLAN基本概念（了解即可）

综合例题

例6：在一个CSMA/CD网络中，网络速率为100Mb/s，信号传播速度为2×10⁸m/s，最短帧长为512bit。求网络的最大跨距。

解：

  • 最短帧长 = 2τ × 速率
  • 512 = 2τ × 100 × 10⁶
  • 2τ = 512 / (100 × 10⁶) = 5.12 × 10⁻⁶s = 5.12μs
  • τ = 2.56μs
  • 最大跨距 = τ × v = 2.56 × 10⁻⁶ × 2 × 10⁸ = 512m

所以当速率提升到100Mb/s时，最大距离缩短到512m（10Mb/s时为2500m左右，通过中继器扩展）。

⚠️ 易错点：

  1. CRC计算中使用的是模2除法，不是普通的除法——不借位！
  2. 停止-等待协议的序号位数只需要1位（这也就够了，因为发送窗口为1）
  3. 交换机隔离冲突域但不隔离广播域；路由器两者都隔离