首页/计算机网络/第 3 章 数据链路层
408 计算机学科专业基础 计算机网络 第 3 章

数据链路层
组帧、可靠传输与以太网

选择题 3–4 道,常出综合题。必会计算:CRC、滑动窗口的信道利用率与序号位数、CSMA/CD 最短帧长;必会概念:GBN 与 SR 的区别、以太网帧格式、交换机自学习、冲突域与广播域。

网络层把分组交下来,数据链路层负责把它可靠地从一个结点送到相邻结点:怎么标出一帧的开头结尾(组帧)、怎么发现错误(差错检测)、发太快怎么办(流量控制)、大家共用一根线怎么不撞车(介质访问控制)。

6 个考点模块 4 类计算 2 个交互模拟器 8 张图
0 1 2 3 4 5 6 7 发送窗口 W = 4 已确认已发未确认可以发不能发
00
复习策略

考频地图

★★★★★ 高频 选择 + 计算 + 综合
考点考频常见问法必须会的动作
组帧(比特/字节填充)★★★☆☆“填充后的比特串是”5 个 1 后插 0
CRC★★★★☆“FCS 是多少”补 r 个 0,模 2 除
停等 / GBN / SR★★★★★“信道利用率”“至少需要几位序号”“重传几帧”周期 = Td + RTT
CSMA/CD★★★★★“最短帧长”“争用期”“退避时间”最短帧 = 2τ × R
CSMA/CA、802.11 地址★★★☆☆“地址 1/2/3 分别是什么”看 To DS / From DS
交换机、冲突域、广播域★★★★☆“图中有几个冲突域”交换机每口一个冲突域,路由器每口一个广播域
一句话:帧 = 首部 + 数据 + 尾部(含 FCS)。CRC 只检错不纠错;滑动窗口的本质是“在等确认的时间里多发几帧”;CSMA/CD 要求帧足够长,长到发送方能在发完之前听到冲突。
01
3.1 · 打基础

组帧

★★★☆☆ 中频 选择题

物理层送上来的是一串连续的比特,数据链路层要在里面找到“一帧从哪开始、到哪结束”。难点是透明传输:如果数据里恰好出现了和帧定界符一样的比特组合,不能误判成帧结束。

方法做法问题 / 使用者
字符计数法帧首部用一个字段说明本帧有多少字节计数字段一出错,后面所有帧都乱套
字节填充(字符填充)用特殊字节(如 0x7E)定界;数据中出现定界符或转义符时,前面插入转义字符PPP(异步传输)
零比特填充帧定界符 01111110;发送方在数据中每遇到连续 5 个 1 就插入一个 0,接收方删掉HDLC、PPP(同步传输)
违规编码用物理层不会出现的码元(如曼彻斯特中“高-高”)表示帧边界802 局域网
#
零比特填充例:帧界 01111110
比特串
1
原始数据
011011111111110010(中间有 10 个连续的 1)
2
从左往右数,连续 5 个 1 后插 0(插入后重新计数)
0110 1111101111100010 = 01101111101111100010
3
接收方:连续 5 个 1 后面的那个 0 删掉
还原为 011011111111110010

填充后,数据中最多只会出现连续 5 个 1,绝不会出现 6 个 1,因此不会被误认为帧界 01111110。PPP 字节填充规则:数据中的 0x7E → 0x7D 0x5E,0x7D → 0x7D 0x5D,小于 0x20 的控制字符前加 0x7D 并把它加 0x20。

02
3.2 · 计算

差错控制:CRC 与海明码

★★★★☆ 高频 计算

一、检错编码

  • 奇偶校验:加 1 位使 1 的个数为奇(偶)数。只能检测奇数个比特错,偶数个错检测不出来。
  • 循环冗余校验 CRC:发送方和接收方约定一个 r 阶生成多项式 G(r + 1 位)。发送方在数据 M 后补 r 个 0,用模 2 除法除以 G,余数(r 位)就是帧检验序列 FCS,附在 M 后面发出。接收方把整个帧除以 G,余数为 0 就认为没错。
模 2 运算:加减都是异或,没有进位借位 1 ⊕ 1 = 0  1 ⊕ 0 = 1  0 ⊕ 0 = 0 G = x³ + x² + 1 → 1101(最高次 3 → r = 3 → 补 3 个 0,余数 3 位)
  • CRC 在数据链路层只检错不纠错:检测到错误就丢弃,至于重传由上层或可靠传输协议负责。
  • “无比特差错”不等于“可靠传输”:帧丢失、重复、失序靠的是序号、确认、重传机制,不是 CRC。
  • 余数位数 = 生成多项式的阶数 r(= G 的位数 − 1),不足要在前面补 0,例如余数 1 写成 001。

二、纠错编码:海明码

在 k 位数据中插入 r 位校验位,使每一位出错都对应一个唯一的“错误位置”。要能纠正 1 位错,需要满足:

2ʳ ≥ k + r + 1 例:k = 4 位数据 → r = 3(2³ = 8 ≥ 4 + 3 + 1)→ 共 7 位,即 (7, 4) 海明码 校验位放在 2 的整数次幂位置:第 1、2、4、8…位

海明距离 d:两个合法码字之间不同比特数的最小值。检测 d 位错需要海明距离 d + 1;纠正 d 位错需要 2d + 1。海明码在组成原理第 2 章有完整计算,这里知道条件即可。

03
3.3 · 计算重点

流量控制与可靠传输

★★★★★ 必考 选择 + 计算

流量控制:接收方处理不过来时让发送方慢一点。可靠传输:帧出错或丢了要重发。这两件事用同一套机制实现——滑动窗口 + 确认 + 超时重传(ARQ,自动重传请求)。

一、停止-等待:发一帧,等确认

发送窗口 = 接收窗口 = 1。为了区分“新帧”和“重传的帧”,帧要编号,1 位序号(0、1 交替)就够。问题是效率:发完一帧后整整一个 RTT 都在等。

信道利用率 U = Td ÷ (Td + RTT) (忽略确认帧发送时延和处理时延,RTT = 2Tp) 例:卫星信道 Tp = 270 ms,数据率 100 kbit/s,帧长 1000 bit Td = 10 ms,U = 10 ÷ (10 + 540) ≈ 1.8%

二、连续 ARQ:在等确认的时候继续发

后退 N 帧 GBN选择重传 SR 发送方接收方发送方接收方 ✗ 01234234 3 失序,丢弃4 失序,丢弃 收 0收 1 帧 2 超时 → 重传 2、3、4 ✗ 012342 缓存 3缓存 4收到 2接收方补齐 2 后,把 2、3、4 一起交付 只重传帧 2
图 3-1 帧 2 丢失后:GBN 的接收方只按序接收,后面的帧全部丢弃,发送方从 2 开始全部重发;SR 的接收方把 3、4 缓存起来,发送方只补发 2。
协议发送窗口 WT接收窗口 WR确认方式出错时
停止-等待11逐帧确认超时重传该帧
后退 N 帧 GBN1 < WT ≤ 2ⁿ − 11累积确认:ACK n 表示 n 及以前都已正确收到从出错帧开始全部重传
选择重传 SRWT ≤ 2ⁿ⁻¹WR ≤ 2ⁿ⁻¹(满足 WT + WR ≤ 2ⁿ)逐帧确认只重传出错帧

为什么 GBN 发送窗口最多 2ⁿ − 1?以 n = 2(序号 0–3)为例,若 W = 4:发送方发 0、1、2、3,接收方全收到并发出确认,但确认全丢了。发送方超时重发旧的 0;而接收方此时期待的新帧序号也是 0,会把旧帧当新帧收下——出错。W = 3 时就不会混淆。SR 同理要求窗口不超过序号空间的一半。

连续 ARQ 信道利用率 U = min(1, W × Td ÷ (Td + RTT)) 要达到 100% 利用率:W ≥ (Td + RTT) ÷ Td 序号位数 n:GBN 需 2ⁿ − 1 ≥ W;SR 需 2ⁿ⁻¹ ≥ W
  • GBN 的接收窗口是 1,所以它不缓存失序帧;SR 的接收窗口 > 1,可以缓存。
  • GBN 累积确认:收到 ACK 3 意味着 0–3 都到了,即使 ACK 1、ACK 2 丢了也没关系。
  • GBN 重传几帧?从超时的那帧开始,到已发出的最后一帧为止全部重传。
  • 算利用率时,题目若说“确认帧长度忽略不计”,周期就是 Td + 2Tp;若确认帧也有发送时延,还要加上。
04
3.4 · 计算重点

介质访问控制

★★★★★ 必考 选择 + 计算

点对点链路上只有两个结点,不存在“抢”的问题。但在广播信道(总线、无线)上,多个站共用一个信道,同时发就会冲突。三大类解决办法:

类型做法代表
信道划分(静态)预先分好,各用各的,不会冲突FDM、TDM、WDM、CDM
随机访问(动态)谁有数据谁发,冲突了再想办法ALOHA、CSMA、CSMA/CD、CSMA/CA
轮询访问(动态)轮流获得发送权令牌传递(令牌环)

一、CSMA:先听后说

类型信道空闲时信道忙时特点
1-坚持立即发送一直监听,空闲后立即发多个站同时等待时,空闲一到必冲突
非坚持立即发送放弃监听,随机等一段时间再听冲突少,但信道可能空闲着没人用
p-坚持以概率 p 发送,1 − p 推迟到下个时隙持续监听折中

二、CSMA/CD:边说边听,冲突就停(有线以太网)

“先听后说”仍可能冲突:A 发出的信号要经过传播时延 τ 才能到达 B,在这之前 B 听到的是“空闲”。所以还要边发送边检测,一旦检测到冲突就立即停止,并发送 32 bit 的人为干扰信号。

AB(总线另一端) t = 0t = τ − δt ≈ 2τ A 开始发送 B 刚好在 A 的信号到达前 听到空闲,也开始发送 → 立刻检测到冲突 A 最迟要到 2τ 才知道冲突了
图 3-2 争用期 = 2τ(端到端往返传播时延)。如果 A 的帧在 2τ 之前就发完了,A 就以为发送成功,无法得知冲突。
最短帧长 = 争用期 2τ × 数据率 R 例:总线长 100 m,传播速率 2×10⁸ m/s,带宽 100 Mbit/s τ = 100 ÷ (2×10⁸) = 0.5 μs,最短帧 = 2 × 0.5 μs × 100 Mbit/s = 100 bit 标准以太网(10 Mbit/s):争用期规定为 51.2 μs → 最短帧 512 bit = 64 B

截断二进制指数退避:第 k 次重传前,从 {0, 1, …, 2k′ − 1} 中随机取 r,等待 r × 2τ,其中 k′ = min(k, 10)。重传 16 次仍失败就放弃并报告上层。冲突越多,等待的范围越大,自动适应负载。

CSMA/CD 只能半双工工作(发送时要同时听)。现代交换式以太网是全双工的,根本不会冲突,也就不需要 CSMA/CD。

三、CSMA/CA:尽量避免冲突(无线局域网 802.11)

无线为什么不能用 CD

① 无线信号衰减大,自己发送时信号强,很难检测到别人的弱信号;② 隐蔽站问题:A、C 都能和 AP 通信,但 A、C 互相听不到,都以为信道空闲,于是在 AP 处冲突。

CSMA/CA 做了什么

① 信道空闲后还要等一段帧间间隔(DIFS),再随机退避;② 可选 RTS/CTS:发送前先发短的请求帧 RTS,AP 回 CTS,所有听到 CTS 的站都推迟发送(解决隐蔽站);③ 接收方收到数据帧后等 SIFS 回 ACK,没收到 ACK 就重传(链路层确认)。

帧间间隔:SIFS(最短,用于 ACK、CTS)< PIFS < DIFS(最长,用于普通数据帧开始竞争)。间隔越短优先级越高。

四、令牌传递

一个特殊的令牌帧在环上依次传递,只有拿到令牌的站才能发数据。不会冲突,负载重时效率高;但令牌丢失或站点故障要专门处理。

  • 最短帧长和最大距离是同一个关系:帧长固定时,距离越大越可能检测不到冲突。题目问“最远距离”就用 L ÷ R = 2d ÷ v 反解 d。
  • CSMA/CD 检测到冲突后发的是 32 bit 干扰信号,然后再退避。
  • CSMA/CA 的 RTS/CTS 是可选的,用于数据帧较长时。
05
3.5 · 高频

以太网、无线局域网与 PPP

★★★★☆ 高频 选择 + 综合

一、以太网 MAC 帧(Ethernet V2)

前导码 7 B+ 帧开始定界符 1 B 目的地址6 B 源地址6 B 类型2 B 数据46 ~ 1500 B FCS4 B 物理层加的 MAC 帧:64 ~ 1518 B(6 + 6 + 2 + 46…1500 + 4) 数据不足 46 B 要填充;以太网 MTU = 1500 B;类型 0x0800 = IPv4,0x0806 = ARP
图 3-3 以太网帧。目的地址在前,交换机读到前 6 个字节就能决定往哪转发(直通交换)。
  • MAC 地址:48 位,固化在网卡中,前 24 位是厂商代码。全 1(FF-FF-FF-FF-FF-FF)为广播地址。网卡收到帧后检查目的地址,不是发给自己的就丢弃。
  • 以太网提供无连接、不可靠的服务:不编号、不确认,出错帧直接丢弃,可靠性交给上层(TCP)。
  • 常见标准:10BASE-T(双绞线、星形、集线器)、100BASE-T(快速以太网,可全双工)、吉比特、10 吉比特以太网(只用全双工,不再用 CSMA/CD)。
  • VLAN:在源地址后插入 4 B 的 802.1Q 标记(其中 VID 12 位),帧最大长度变为 1522 B。同一 VLAN 内才能直接通信,VLAN 隔离广播域;不同 VLAN 间通信需要路由器(或三层交换机)。

二、802.11 无线局域网帧的地址

802.11 数据帧有 4 个地址字段(常用前 3 个),含义取决于帧是发往 AP 还是从 AP 发出:

场景To DSFrom DS地址 1(接收者)地址 2(发送者)地址 3
站 A → AP(准备发往有线网的 R)10AP 的 MAC(BSSID)A 的 MAC目的地址 R
AP → 站 B(来自有线网的 R)01B 的 MACAP 的 MAC(BSSID)源地址 R

记法:地址 1 永远是“这一跳无线链路的接收者”,地址 2 永远是“这一跳的发送者”,地址 3 放“另一头真正的通信方”。

三、PPP 协议(点对点链路)

  • 帧格式:标志 0x7E | 地址 0xFF | 控制 0x03 | 协议 2 B | 信息 ≤ 1500 B | FCS 2 B | 标志 0x7E。
  • 组成:封装成帧的方法、链路控制协议 LCP(建立、配置、测试链路)、网络控制协议 NCP(为各种网络层协议配置,如分配 IP)。
  • 不使用序号和确认,只保证无差错接收(CRC),不提供可靠传输;只支持点对点、全双工;面向字节。
06
3.6 · 高频

交换机与冲突域

★★★★☆ 高频 选择 + 综合

一、交换机的自学习

交换机(多端口网桥)工作在数据链路层,靠一张交换表(MAC 地址 → 端口)转发帧。表不是配置出来的,是“看”出来的:

交换机 123 A B C ① A 发给 B:学到“A 在端口 1”;表中没有 B → 泛洪(除端口 1 外全发) ② B 回复 A:学到“B 在端口 2”;A 已知在端口 1 → 只从端口 1 转发 ③ 之后 A↔B:直接转发,C 收不到,不再泛洪 交换表 A → 端口 1(有效期 300 s) B → 端口 2
图 3-4 自学习:用源地址学习,用目的地址转发。目的地址未知或是广播地址时泛洪;目的端口与来源端口相同时直接丢弃。
  • 存储转发:收完整帧、做 CRC 检查后再转发;可靠,可连接不同速率的端口,时延较大。
  • 直通交换:只读完目的地址(前 6 B)就开始转发;时延小,但不检错。
  • 交换机的每个端口独占带宽:10 Mbit/s 交换机接 10 台主机(全双工),每台都能用满 10 Mbit/s。

二、冲突域与广播域

路由器 交换机 集线器 PC1 PC2 PC3 PC4 PC5 PC6 橙色虚线 = 冲突域:5 个 绿色实线 = 广播域:2 个
图 3-5 交换机的每个端口是一个冲突域(3 个接 PC + 1 个连路由器);集线器下面整体是 1 个冲突域;路由器每个接口一个广播域。
设备层次隔离冲突域隔离广播域
中继器、集线器物理层✗✗
网桥、交换机数据链路层✓(每个端口一个)✗(VLAN 可以)
路由器网络层✓✓(每个接口一个)
  • 交换机学习用源 MAC,转发看目的 MAC,不要反过来。
  • 交换机收到广播帧会向所有其他端口转发,所以它不隔离广播域。
  • 交换机对主机是透明的:主机不知道交换机的存在,也不需要配置交换机地址。
07
实战

真题与自测

★★★★★ 收口 选择 + 综合

一、真题问法

问法 1:“数据链路层采用 GBN,发送方已发送 0~7 号帧。计时器超时时只收到 0、2、3 号帧的确认,发送方需要重发几帧?”→ 累积确认:收到 ACK 3 说明 0–3 都到了,从 4 开始重发 4、5、6、7,共 4 帧。

问法 2:“主机甲乙之间信道速率 3 kbit/s,单向传播时延 200 ms,帧长 1000 B(可视为不计确认帧),采用 GBN 要使利用率最大,帧序号至少需要几位?”→ Td = 8000 / 3000 ≈ 2.67 s,周期 = 2.67 + 0.4 = 3.07 s,W ≥ 3.07 / 2.67 → 2 帧,GBN 需 2ⁿ − 1 ≥ 2 → n ≥ 2,至少 2 位。

问法 3:“CSMA/CD 网络,数据率 1 Gbit/s,电缆中信号传播速度 200 000 km/s,最短帧长减少 800 bit 时,最远两站之间的距离至少需要怎样变化?”→ 最短帧 = 2d/v × R,ΔL = 800 bit 对应 Δd = 800 × v / (2R) = 80 m,减少 80 m。

问法 4:“下图网络中有几个冲突域、几个广播域?”→ 交换机每端口一个冲突域,集线器整体一个,路由器每接口一个广播域。

二、折叠自测

1. 数据 1101011011,生成多项式 x⁴ + x + 1,FCS 是多少?

G = 10011,补 4 个 0 后模 2 除,余数为 1110。在 CRC 计算器中输入可验证全过程。

2. 3 位序号,GBN 和 SR 的最大发送窗口各是多少?

GBN:2³ − 1 = 7;SR:2³⁻¹ = 4(接收窗口也是 4)。

3. 停止-等待协议需要几位序号?为什么?

1 位就够。只需区分“这一帧”和“上一帧(重传)”,0、1 交替即可。

4. 10 Mbit/s 以太网争用期是多少?最短帧多长?

争用期 51.2 μs,最短帧 512 bit = 64 B。

5. 为什么无线局域网不用 CSMA/CD?

无线信号衰减大,发送时难以检测到其他站的弱信号;还存在隐蔽站问题,即使检测也检测不到。因此改用 CSMA/CA 尽量避免冲突,并用 ACK 确认。

6. 交换机收到一个目的 MAC 不在交换表中的帧怎么办?

除进入端口外,向所有其他端口泛洪;同时用该帧的源 MAC 更新交换表。

7. PPP 协议提供可靠传输吗?

不提供。PPP 只做 CRC 检错,出错帧丢弃,不编号、不确认、不重传。

三、考前速览

五句话

零比特填充:5 个 1 后插 0。
CRC 补 r 个 0,模 2 除,余数 r 位。
U = W·Td / (Td + RTT)。
GBN ≤ 2ⁿ − 1,SR ≤ 2ⁿ⁻¹。
最短帧 = 2τ × R。

五个易错

① GBN 累积确认,接收窗口为 1。
② CRC 不纠错,也不保证可靠。
③ 交换机用源地址学习。
④ 交换机不隔离广播域。
⑤ 802.11 地址 1 是本跳接收者。