QEQuantumEinsteinSearchCtrl/⌘K
Notes/📖 计算机网络（Computer Networking）—— 408考研完全笔记/第三章 数据链路层（⭐⭐⭐⭐）

第三章 数据链路层（⭐⭐⭐⭐）

5 分钟阅读2,151 字18 个小节
返回目录

第三章 数据链路层（⭐⭐⭐⭐）

3.1 数据链路层功能与组帧

  • 成帧、透明传输、差错控制、流量控制、介质访问控制
  • 典型帧界定：字符计数、字符填充、零比特填充、违规编码

3.2 差错控制

一、检错编码

  • 奇偶校验：简单，能力弱
  • CRC：工程主流

CRC核心思路：把数据看作多项式，发送端附加余数，接收端整除校验。

CRC 模2除法计算示例（⭐ 高频）

例：数据 D=101001D = 101001，生成多项式 G(x)=x3+x+1G(x) = x^3+x+1（即 10111011，r=3r=3 位）。

步骤：

  1. 数据后补 r=3r=3 个 0 → 101001000‾101001\underline{000}
  2. 用 10111011 对 101001000101001000 做模2除法（XOR代替减法）：
101001000 ÷ 1011 1011 ──── 0011 0000 ──── 0110 0000 ──── 1101 1011 ──── 1100 1011 ──── 1110 1011 ──── 101 ← 余数 R
  1. 发送帧 = 数据 + 余数 = 101001101‾101001\underline{101}
  2. 接收端：用收到的帧除以 10111011，余数为 0 → 无差错；余数非 0 → 有差错

⚠️ 模2运算：加法和减法都是XOR，不进位不借位！

二、纠错编码

  • 海明码：可实现1位纠错、2位检错（需额外增加1位全校验位）
  • 监督位数满足： 2r≥m+r+12^r \ge m+r+1

海明码编码示例（⭐ 高频选择/填空）

例：对数据 D=1011D = 1011 进行海明编码。

步骤：

  1. 确定校验位数 rr：m=4m=4，需 2r≥4+r+12^r \ge 4+r+1，r=3r=3（23=8≥82^3=8\ge8 ✓）
  2. 编码字总位数：n=m+r=7n = m + r = 7（H7H6H5H4H3H2H1H_7H_6H_5H_4H_3H_2H_1）
  3. 校验位占据 2i2^i 号位：P1P_1=H1H_1，P2P_2=H2H_2，P3P_3=H4H_4
  4. 数据位填入剩余位：H3=D1=1H_3=D_1=1，H5=D2=0H_5=D_2=0，H6=D3=1H_6=D_3=1，H7=D4=1H_7=D_4=1
  5. 求各校验位（偶校验）：
    • P1P_1（校验所有编号含 20=12^0=1 的位）：H1,H3,H5,H7H_1, H_3, H_5, H_7 → P1⊕1⊕0⊕1=0P_1 \oplus 1 \oplus 0 \oplus 1 = 0 → P1=0P_1 = 0
    • P2P_2（校验所有编号含 21=22^1=2 的位）：H2,H3,H6,H7H_2, H_3, H_6, H_7 → P2⊕1⊕1⊕1=0P_2 \oplus 1 \oplus 1 \oplus 1 = 0 → P2=1P_2 = 1
    • P3P_3（校验所有编号含 22=42^2=4 的位）：H4,H5,H6,H7H_4, H_5, H_6, H_7 → P3⊕0⊕1⊕1=0P_3 \oplus 0 \oplus 1 \oplus 1 = 0 → P3=0P_3 = 0
  6. 海明码：H7H6H5H4H3H2H1=1010110H_7H_6H_5H_4H_3H_2H_1 = \mathbf{1010110}

检错纠错：接收方对各组做偶校验，得到 S3S2S1S_3S_2S_1，若 =000= 000 则无错；否则 S3S2S1S_3S_2S_1 的十进制值指示出错位号，取反即可纠正。

📝 加一位全校验位可实现"SEC-DED"（单纠双检）。

3.3 流量控制与可靠传输（滑动窗口）

信道利用率近似： U≈W⋅tfRTT+tf+tackU\approx\frac{W\cdot t_f}{RTT+t_f+t_{ack}}

协议发送窗口接收窗口ACK语义
停止等待11逐帧确认
GBN≤2n−1\le 2^n-11累积确认
SR≤2n−1\le 2^{n-1}≤2n−1\le 2^{n-1}逐帧确认

⚠️ 陷阱1：GBN 的 ACK 具有累积性，SR 不具有。

⚠️ 陷阱2：SR 不是“全重传”，只重传丢失或出错帧。> ⚠️ 陷阱3（SR联合约束）：SR 要求 Ws+Wr≤2nW_s + W_r \le 2^n，否则接收方无法区分新旧帧。当 Ws=WrW_s = W_r 时，各 ≤2n−1\le 2^{n-1}。

3.4 介质访问控制

一、信道划分

  • FDM / TDM / WDM / CDM

CDMA（码分多址）内积计算

每个站分配唯一码片序列（长度为 mm 的向量），各码片序列两两正交：

Si⃗⋅Sj⃗={mi=j0i≠j\vec{S_i}\cdot\vec{S_j}=\begin{cases} m & i=j \\ 0 & i\ne j \end{cases}

接收端用某站码片与叠加信号做规格化内积： di=1mSi⃗⋅D⃗d_i = \frac{1}{m}\vec{S_i}\cdot\vec{D}

  • di=+1d_i=+1：该站发送了比特 1
  • di=−1d_i=-1：该站发送了比特 0
  • di=0d_i=0：该站未发送

📝 计算要点：发送 1 用原码片，发送 0 用码片取反（−S⃗-\vec{S}），叠加后逐位相加。

二、随机访问

ALOHA 协议（考纲要求）

维度纯 ALOHA时隙 ALOHA
发送时机任意时刻只能在时隙开始时
冲突窗口2T02T_0（T₀为帧传输时间）T0T_0
最大吞吐率Smax=12e≈18.4%S_{max}=\frac{1}{2e}\approx 18.4\%Smax=1e≈36.8%S_{max}=\frac{1}{e}\approx 36.8\%
吞吐率公式S=Ge−2GS=Ge^{-2G}S=Ge−GS=Ge^{-G}

⚠️ 时隙 ALOHA 吞吐率是纯 ALOHA 的 2倍。

CSMA 三类协议对比（考纲要求）

类型信道忙时信道空闲时特点
1-坚持持续监听，一空就发立即发送冲突概率高，延迟低
非坚持放弃监听，随机等待后重试立即发送冲突少，但延迟大
p-坚持持续监听以概率 pp 发送，1−p1-p 等下一个时隙折中方案

CSMA/CD（以太网）

  • 口诀：先听后发，边听边发，冲突停发，随机重发
  • 争用期（冲突窗口）：2τ2\tau
  • 最短帧长： Lmin=2τ⋅RL_{min}=2\tau\cdot R
  • 10Mbps经典最短帧长：64B
  • 截断二进制指数退避：
    • 第 kk 次重传，从 {0,1,...,2k′−1}\{0,1,...,2^{k'}-1\} 中随机选一个等待时间（k′=min⁡(k,10)k'=\min(k,10)）
    • 等待时间单位 = 2τ2\tau（争用期）
    • 最多重传16次，超过则丢弃帧

CSMA/CA（802.11）

  • 无线环境难以冲突检测，故采用冲突避免
  • 帧间间隔优先级：SIFS < PIFS < DIFS
  • RTS/CTS + NAV 用于缓解隐藏站问题

CSMA/CA 工作流程：

  1. 发送方等待 DIFS 时间
  2. 信道空闲则进入退避倒计时（随机退避时隙）
  3. 倒计时归零后发送数据帧
  4. 接收方等待 SIFS 后回复 ACK

NAV（网络分配向量）计算：

NAV=SIFS+ACK传输时间+数据帧传输时间NAV = SIFS + ACK传输时间 + 数据帧传输时间

使用 RTS/CTS 时，其他站通过 CTS 帧中的 Duration 字段设置 NAV 计时器，在 NAV 期间不发送。

对比CSMA/CDCSMA/CA
冲突处理检测到冲突后停发尽量避免冲突
确认机制无ACK（半双工）有ACK
信道检测物理+电缆信号物理+虚拟载波监听(NAV)
帧间间隔最小帧间隔SIFS/DIFS/PIFS
应用场景有线以太网802.11无线局域网

📝 2024真题：CSMA/CA 中 NAV 的计算与 RTS/CTS 时序分析。

三、轮询访问

  • 令牌传递：有序、公平、冲突小，适合重负载
  • 令牌环网工作流程：空闲令牌在环中循环→站点捕获令牌→发送数据帧→目的站复制数据→帧回到发送站后释放令牌
  • 适用场景：负载重时效率高，轻载时令牌循环浪费带宽

3.5 局域网、广域网与设备

一、以太网帧（V2）

  • 目的MAC(6B) + 源MAC(6B) + 类型(2B) + 数据(46-1500B) + FCS(4B)
  • 最短帧64B，最大帧1518B
  • FCS基于CRC，仅校验从目的地址到数据字段

二、VLAN（802.1Q）

  • 标签4B，VID 12位
  • 802.1Q帧最大 1522B

三、PPP 协议

  • 点到点链路主流协议，面向字节
  • 帧格式：7E FF 03 协议(2B) 数据 FCS(2B) 7E
  • 组件：LCP（建立/配置/测试数据链路）、NCP（配置网络层协议，如IPCP）
  • 特点：无纠错、无序号、无流量控制，仅检错

四、HDLC 协议（考纲要求）

  • 面向比特的数据链路层协议
  • 帧格式：标志 01111110 + 地址(8b) + 控制(8/16b) + 数据 + FCS(16b) + 标志
  • 三种帧：信息帧(I帧)、监督帧(S帧)、无编号帧(U帧)
  • 支持全双工，有序号和流量控制
对比PPPHDLC
面向字节比特
序号/流控无有
透明传输字节填充/零比特填充零比特填充
差错控制仅检错可纠错
应用拨号上网/PPPoE同步传输链路

五、网络设备与隔离域

设备冲突域广播域
集线器不隔离不隔离
交换机/网桥隔离冲突域不隔离广播域
路由器隔离冲突域隔离广播域

网桥/交换机自学习算法

  1. 收到帧后，记录源MAC→端口号的映射到转发表
  2. 查转发表：
    • 找到目的MAC → 从对应端口转发（若目的端口=源端口则丢弃）
    • 找不到 → 向所有端口泛洪（除来源端口）
  3. 转发表条目有老化时间，到期自动删除

⚠️ 交换机是即插即用设备，无需手动配置。

📌 第三章总结

  • 三大计算核心：CRC、滑动窗口（含SR联合约束）、退避时间
  • 三大机制核心：CSMA/CD、CSMA/CA（NAV计算）、VLAN
  • 三大设备辨析：Hub vs Switch vs Router
  • ALOHA两种 + CSMA三类 + CD/CA 对比必须熟记
  • HDLC vs PPP 对比是高频选择题点
  • 关联陷阱编号：#2 #12 #13

🎯 第三章 Top-Down 案例模板（一跳内如何可靠发送）

步骤提问模板本章落点
场景点到点还是共享信道？PPP/HDLC vs MAC协议
可靠性需检错还是重传？CRC + 滑动窗口
竞争有无冲突检测能力？CSMA/CD 与 CSMA/CA 区分
计算题目问效率还是窗口约束？吞吐公式、窗口边界