第 12 讲：流水线协议——GBN 与 Selective Repeat

一、流水线：不等 ACK 就继续发

第 11 讲的结论：停等协议在高 BDP 链路上利用率极低。

解决办法：允许发送方在收到确认之前发送多个分组。

停等：
发送方 ┃█┃                    ┃█┃                    ┃█┃
        └─── RTT 全在等待 ───▶

流水线（N=3）：
发送方 ┃█┃█┃█┃              ┃█┃█┃█┃
       三个分组连续发出       第一个 ACK 回来后继续

利用率提升 N 倍：

U = N × (L/R) / (RTT + L/R)     （当 N·(L/R) < RTT + L/R 时）

当 N 大到 N × (L/R) ≥ RTT + L/R 时，发送方永不停歇，利用率 = 100%。此时窗口已经填满了整个管道。

三个必须解决的新问题：

序号范围要扩大
发送方要缓存未确认的分组
⭐ 丢包时怎么恢复——这一条分出了两个流派

二、滑动窗口

两个协议共用的框架：

发送方视角：

  已确认      已发送未确认      可发送     不可发送
┌─────────┬───────────────┬──────────┬─────────┐
│ ....... │ ▓▓▓▓▓▓▓▓▓▓▓▓ │ ░░░░░░░░ │        │
└─────────┴───────────────┴──────────┴─────────┘
          ▲               ▲          ▲
       send_base      nextseqnum   send_base+N

          ◀────── 窗口大小 N ──────▶

send_base：最早的未确认分组序号
nextseqnum：下一个要发的序号
窗口：[send_base, send_base + N − 1]

窗口「滑动」：当 send_base 前面的分组被确认，窗口整体右移，从而允许发送新的分组。

⭐ **窗口大小 N 限制了在途未确认数据量。**它是流量控制（第 14 讲）和拥塞控制（第 16 讲）的着力点——TCP 就是通过操纵这个 N 来控制发送速率的。

三、回退 N 步（Go-Back-N, GBN）

3.1 三条规则

1️⃣ 累积确认（Cumulative ACK）

ACK(n) 的含义 = 「序号 n 及其之前的所有分组，我都正确收到了」

📌 这个语义非常重要：丢失一个 ACK 不要紧，后面任何一个更大的 ACK 都能替它完成确认。

2️⃣ 只用一个定时器

定时器针对最早的未确认分组（send_base）。

3️⃣ 超时 → 重传窗口内所有已发送未确认的分组

这就是「回退 N 步」这个名字的来源。

3.2 接收方：极度简单

接收方只维护一个变量：expectedseqnum

收到分组 n：
   若 n == expectedseqnum:  交付数据，expectedseqnum++，发 ACK(n)
   否则（乱序）:            ⭐ 丢弃，重发 ACK(expectedseqnum − 1)

⭐ GBN 接收方不缓存任何乱序分组。

**为什么？**因为它必须按序交付给应用，而缓存乱序分组会带来复杂度。它选择了「反正发送方会重传，我直接扔掉」。

代价：一个分组丢失，导致后面所有已经成功到达的分组被白白丢弃并重传。

3.3 GBN 时序图

发送方 (N=4)                          接收方  expected=0
  │                                       │
  ├─ pkt0 ────────────────────────────────▶  ✓ 交付, ACK0, exp=1
  ├─ pkt1 ─────────╳                          （丢失）
  ├─ pkt2 ────────────────────────────────▶  ✗ 乱序！丢弃, 重发 ACK0
  ├─ pkt3 ────────────────────────────────▶  ✗ 乱序！丢弃, 重发 ACK0
  │◀── ACK0 ───────────────────────────────┤
  │◀── ACK0 ───────────────────────────────┤
  │◀── ACK0 ───────────────────────────────┤
  │  [pkt1 超时]
  ├─ pkt1 ────────────────────────────────▶  ✓ 交付, ACK1, exp=2
  ├─ pkt2 ────────────────────────────────▶  ✓ 交付, ACK2   ⭐ 重传
  ├─ pkt3 ────────────────────────────────▶  ✓ 交付, ACK3   ⭐ 重传

⚠️ 注意 pkt2 和 pkt3 被传了两次——第一次到达时被丢弃了。这就是 GBN 的浪费。

3.4 GBN 的取舍

✅ 优点	❌ 缺点
接收方极简，只需 1 个变量，无缓冲区	一个丢包引发大量重传
只需 1 个定时器	高丢包率 + 大窗口时效率灾难性下降
累积 ACK 对 ACK 丢失有鲁棒性	浪费的重传本身加剧拥塞

四、选择重传（Selective Repeat, SR）

核心思想：只重传真正丢失的那一个。

4.1 三条规则

1️⃣ 逐分组确认（Individual ACK）

ACK(n) 的含义 = 「我收到了分组 n」（仅此一个，不含之前的）

2️⃣ 每个未确认分组各有一个定时器

3️⃣ 超时 → 只重传那一个分组

4.2 接收方：需要缓冲区

接收方维护一个接收窗口 [rcv_base, rcv_base + N − 1]

收到分组 n：
   若 n 在接收窗口内:
        缓存它，发 ACK(n)
        若 n == rcv_base: ⭐ 把从 rcv_base 开始所有连续的已缓存分组
                            一次性交付给应用，窗口右移
   若 n 在 [rcv_base − N, rcv_base − 1]（窗口左侧）:
        ⭐ 仍然发 ACK(n)！  ← 关键，见下文
   否则: 忽略

⚠️ 窗口左侧的分组也要 ACK——这是学生最容易漏掉的一条。原因：如果之前的 ACK 丢了，发送方会重传，此时必须再回一次 ACK，否则发送方永远无法推进窗口。

4.3 SR 时序图（同一场景）

发送方 (N=4)                          接收方  rcv_base=0
  │                                       │
  ├─ pkt0 ────────────────────────────────▶  ✓ 交付, ACK0, base=1
  ├─ pkt1 ─────────╳                          （丢失）
  ├─ pkt2 ────────────────────────────────▶  ⭐ 缓存!  ACK2
  ├─ pkt3 ────────────────────────────────▶  ⭐ 缓存!  ACK3
  │◀── ACK0 ───────────────────────────────┤
  │◀── ACK2 ───────────────────────────────┤
  │◀── ACK3 ───────────────────────────────┤
  │  [仅 pkt1 超时]
  ├─ pkt1 ────────────────────────────────▶  ✓ 一次性交付 1,2,3 ⭐
  │◀── ACK1 ───────────────────────────────┤     base=4

只重传了 1 个分组，对比 GBN 的 3 个。

4.4 SR 的取舍

✅ 优点	❌ 缺点
重传最少，带宽效率最高	接收方要缓冲区（内存开销）
高丢包率下性能远好于 GBN	要维护 N 个定时器（实现复杂）
	序号空间要求更严格（见第五节）

五、序号空间：一个必考的证明

⚠️ 序号是有限的（k 位序号 → 序号空间 2ᵏ，会循环使用）。窗口大小 N 必须受序号空间约束，否则协议会出错。

5.1 GBN：序号空间 ≥ N + 1

为什么 N 不行？

设序号空间为 4（序号 0,1,2,3），窗口 N = 4。

发送方发出 pkt0, pkt1, pkt2, pkt3
接收方全部收到并交付，发出 ACK0..ACK3
⭐ 所有 ACK 全部丢失

发送方超时，重传 pkt0
接收方此时 expectedseqnum = 0（因为序号回绕了）
   → 它会把这个重传的 pkt0 当成新的 pkt0 接受 ❌ 数据重复交付

结论：序号空间必须至少 N + 1，让接收方能区分「新一轮的 0」和「上一轮的 0」。

5.2 SR：序号空间 ≥ 2N ⭐

SR 的要求更严格，这是本讲最经典的考题。

反例：序号空间 4（0,1,2,3），窗口 N = 3。

情形 A：
  发送方发 pkt0,1,2
  接收方全收到，交付，发 ACK0,1,2，接收窗口滑到 [3,0,1]
  ⭐ 三个 ACK 全部丢失
  发送方超时，重传 pkt0
  接收方看到序号 0 —— 它在当前接收窗口 [3,0,1] 内！
  → ❌ 当作新分组接受，数据重复

情形 B：
  发送方发 pkt0,1,2
  ACK0 到达，pkt1、pkt2 丢失
  发送方窗口滑到 [1,2,3]，发送 pkt3
  接收方接收窗口是 [1,2,3]，收到 pkt3 —— 缓存
  ...

⭐ 问题在于：从接收方的角度看，情形 A 中重传的 pkt0
   和情形 B 中一个全新的 pkt0（下一轮的），报文完全一样，无法区分。

根本原因：发送窗口和接收窗口可能在序号空间上错开，两者合起来最多覆盖 2N 个序号。要保证不重叠歧义，序号空间必须 ≥ 2N。

📌 记忆法：

GBN:  序号空间 ≥ N + 1      （接收窗口大小为 1）
SR :  序号空间 ≥ 2N         （接收窗口大小为 N）

通用规则：序号空间 ≥ 发送窗口 + 接收窗口

5.3 更深的原因：分组会在网络中滞留

⚠️ 上面的分析假设分组不会「迟到很久」。现实中，一个分组可能在某个路由器队列里待很久然后突然出现。

这就是为什么 TCP 要有 MSL（最长报文段寿命，通常 30–120 秒）的概念，以及为什么初始序号要随机化——第 14 讲的 TIME_WAIT 状态直接来源于此。

六、GBN vs SR 全面对比

	GBN	SR
ACK 语义	累积（n 及之前全收到）	逐个（仅 n）
定时器数量	1 个（针对最老的未确认）	N 个
接收窗口	1	N
接收方缓存乱序分组	❌ 丢弃	✅ 缓存
超时后重传	窗口内全部	只重传那一个
序号空间要求	≥ N + 1	≥ 2N
实现复杂度	低	高
高丢包率下	差	好
ACK 丢失的影响	小（后续 ACK 覆盖）	大（需要该分组超时）

TCP 是哪一个？

⭐ 都不是，TCP 是二者的混合体：

TCP 特征	更像
累积确认	GBN
只维护一个重传定时器	GBN
接收方缓存乱序报文段	SR
快速重传只重传一个报文段	SR
SACK 选项明确告知哪些块已收到	SR

第 13 讲会详细拆解。TCP 的设计哲学是：默认走 GBN 的简单路径，但用 SR 的机制处理常见情况（单个丢包）。

七、例题（Worked Example）

题目：窗口大小 N = 4，序号空间充足。发送方连续发送 pkt0–pkt5。pkt2 在传输中丢失，其余全部正常到达，所有 ACK 均无丢失。假设超时时间足够长，超时发生在 pkt5 发出之后。

(a) 用 GBN，接收方一共交付了几个分组给应用？发送方一共发送了几个分组（含重传）？ (b) 用 SR，回答同样的问题。 (c) 若链路带宽紧张，哪个协议更好？若接收方是内存极小的物联网设备呢？

解答：

(a) GBN

pkt0 ✓ 交付, ACK0
pkt1 ✓ 交付, ACK1
pkt2 ╳ 丢失
pkt3 → 乱序，丢弃，重发 ACK1
pkt4 → 乱序，丢弃，重发 ACK1
pkt5 → 乱序，丢弃，重发 ACK1
     （注意：窗口 N=4，send_base=2 时窗口是 [2,3,4,5]，恰好发完）
[pkt2 超时] → 重传 pkt2, pkt3, pkt4, pkt5
pkt2 ✓ 交付, pkt3 ✓, pkt4 ✓, pkt5 ✓

接收方交付：6 个（0–5）
发送方发送：6 + 4 = 10 个分组

(b) SR

pkt0 ✓ 交付, ACK0
pkt1 ✓ 交付, ACK1
pkt2 ╳ 丢失
pkt3 → ⭐ 缓存, ACK3
pkt4 → ⭐ 缓存, ACK4
pkt5 → ⭐ 缓存, ACK5
[仅 pkt2 超时] → 只重传 pkt2
pkt2 ✓ → 一次性交付 2,3,4,5

接收方交付：6 个
发送方发送：6 + 1 = 7 个分组

GBN 多发了 3 个分组，浪费 43% 的传输量。

(c)

链路带宽紧张 → 选 SR。重传越少越好，而且 GBN 的多余重传在拥塞时会火上浇油（第 15 讲）。
接收方内存极小 → 选 GBN。SR 需要 N 个分组的接收缓冲区（若 N=1000、分组 1500 字节，就是 1.5 MB）以及 N 个定时器，对一个几十 KB 内存的传感器节点不现实。

📌 这个取舍在真实系统中天天发生：受限设备上的 CoAP、LoRaWAN 等协议大量采用简化的停等或类 GBN 机制，正是出于同样的理由。

八、随堂自测

窗口从 1 增大到 N，利用率如何变化？什么时候达到 100%？
GBN 接收方为什么不缓存乱序分组？这个决定的代价是什么？
累积确认对 ACK 丢失有什么好处？
SR 接收方收到一个接收窗口左侧的分组，应该怎么办？为什么？
证明：SR 中若序号空间为 2N−1，可以构造出协议出错的场景。
TCP 在哪些方面像 GBN，哪些方面像 SR？
窗口 N=5，序号用 3 位（空间 8）。GBN 可以吗？SR 可以吗？

九、本讲要点回顾

流水线把利用率提升 N 倍：U = N(L/R)/(RTT + L/R)，N 足够大时达到 100%。
滑动窗口限制在途未确认数据量——这是 TCP 控制发送速率的着力点。
GBN：累积确认、1 个定时器、接收窗口为 1、超时重传窗口内全部。接收方简单，代价是重传浪费。
SR：逐个确认、N 个定时器、接收窗口为 N、只重传丢失的那个。效率高，代价是复杂度与内存。
序号空间 ≥ 发送窗口 + 接收窗口：GBN 要 N+1，SR 要 2N。
TCP 是混合体：累积确认与单定时器（GBN 侧），接收方缓存与选择性重传（SR 侧）。

十、自测答案

1. 利用率变为停等的 N 倍：U = N(L/R)/(RTT + L/R)。当 N·(L/R) ≥ RTT + L/R 时，发送方在收到第一个 ACK 时窗口仍未发完，因而永不空闲，利用率达到 100%。此时的 N 恰好对应把管道填满，即 N ≈ BDP/L。

2. 因为接收方必须按序把数据交付给应用，缓存乱序分组意味着要维护缓冲区、跟踪哪些序号已到、以及在补齐后做批量交付——这些都是复杂度和内存。GBN 选择了「反正发送方会重传全部，我直接扔掉」的极简方案。代价是：一个分组丢失会导致后面所有已成功到达的分组被白白丢弃并重传，在大窗口、高丢包率下浪费极其严重。

3. 累积确认意味着 ACK(n) 隐含确认了 n 之前的所有分组。因此中间的 ACK 丢失是无害的——只要后面有任何一个更大的 ACK 到达，发送方就能一次性推进窗口。这使 GBN 对反向路径的丢包具有天然鲁棒性。（对比 SR：每个 ACK 都是独立信息，丢一个就必须等对应分组超时重传。）

4. 必须发送 ACK(n)。该分组落在窗口左侧，说明接收方之前已经收过并确认过它，发送方之所以重传，是因为那次的 ACK 丢失了。如果接收方保持沉默，发送方的 send_base 将永远无法推进，连接死锁。（数据本身则丢弃，不重复交付。）

5. 取 N=3、序号空间 5（0–4）。发送方发 pkt0,1,2；接收方全收到、交付、发 ACK0,1,2，接收窗口滑到 [3,4,0]。三个 ACK 全部丢失。发送方超时重传 pkt0。接收方看到序号 0，而 0 在当前接收窗口 [3,4,0] 内 → 误当作新分组接受，造成重复交付。因此 2N−1 = 5 不够，必须 ≥ 2N = 6。

6. 像 GBN：使用累积确认；只维护一个重传定时器（针对最老的未确认字节）。像 SR：接收方缓存乱序到达的报文段（不丢弃）；快速重传只重传缺失的那一个报文段；SACK 选项让接收方明确告知哪些不连续的块已收到，使发送方能做真正的选择性重传。

7. 序号空间 = 8。

GBN：要求空间 ≥ N+1 = 6。8 ≥ 6 ✅ 可以。
SR：要求空间 ≥ 2N = 10。8 < 10 ❌ 不可以，会出现窗口重叠歧义。SR 在 3 位序号下窗口最大只能是 4。

一、流水线：不等 ACK 就继续发#

二、滑动窗口#

三、回退 N 步（Go-Back-N, GBN）#

3.1 三条规则#

3.2 接收方：极度简单#

3.3 GBN 时序图#

3.4 GBN 的取舍#

四、选择重传（Selective Repeat, SR）#

4.1 三条规则#

4.2 接收方：需要缓冲区#

4.3 SR 时序图（同一场景）#

4.4 SR 的取舍#

五、序号空间：一个必考的证明#

5.1 GBN：序号空间 ≥ N + 1#

5.2 SR：序号空间 ≥ 2N ⭐#

5.3 更深的原因：分组会在网络中滞留#

六、GBN vs SR 全面对比#

TCP 是哪一个？#

七、例题（Worked Example）#

八、随堂自测#

九、本讲要点回顾#

十、自测答案#