Chapter 3-3：流水线、滑动窗口、GBN 与 SR 学习指南

本节是可靠数据传输 rdt 的继续部分。上一节 rdt3.0 已经解决了“可靠性”问题：比特错误、丢包、ACK 丢失、重复分组都能处理。但 rdt3.0 仍然有一个严重缺陷：

它可靠，但太慢。

Chapter 3-3 的核心任务，就是从 rdt3.0 的性能瓶颈出发，引出 pipelining 流水线协议，再进一步讲 sliding window 滑动窗口，最后比较两种典型流水线协议：GBN 和 SR。

0. 本节核心主线

rdt3.0 的 stop-and-wait 模式是：

1
2
3
4
5

发送一个分组
↓
等待 ACK
↓
收到 ACK 后再发下一个分组

这种方式逻辑简单、可靠性强，但链路利用率很低。尤其在高带宽、长 RTT 的链路上，发送方大部分时间都在等 ACK，而不是在真正发送数据。

所以本节主线可以概括为：

  flowchart TD
    A[rdt3.0 可靠但低效] --> B[stop-and-wait 一次只发一个分组]
    B --> C[链路大部分时间空闲]
    C --> D[引入 pipelining 流水线]
    D --> E[允许多个未确认分组同时在路上]
    E --> F[需要滑动窗口控制发送/接收范围]
    F --> G[形成 GBN 和 SR 两类协议]
  

❗ 本节核心结论：
rdt3.0 解决了可靠性，但没有解决效率；流水线协议通过允许多个未确认分组同时在网络中传输，提高链路利用率。

1. rdt3.0 的性能问题

rdt3.0 是 stop-and-wait 协议。它的发送节奏是：

发一个，等一个 ACK，再发下一个。

这个机制的问题在于，发送方真正把分组推上链路的时间很短，而等待 ACK 往返的时间可能很长。

发送方利用率可以粗略理解为：

1

发送方真正发送数据的时间 / 一个发送周期总时间

在 stop-and-wait 中，一个周期大致是：

1

L/R + RTT

其中：

所以发送方利用率大致是：

1

U_sender = (L/R) / (RTT + L/R)

当链路带宽 R 很大时，L/R 会非常小；但 RTT 不会因为带宽变大而自动变小。于是发送方发完一个分组后，长时间都在等 ACK。

❗ 本节核心结论：
stop-and-wait 的瓶颈不是链路本身太慢，而是协议规定发送方必须等 ACK，导致链路长期空闲。

2. RTT 是什么？

RTT 全称是 Round-Trip Time，即往返时间。

它表示：

1
2
3

一个分组从发送方到接收方
+
ACK 从接收方返回发送方

这一整个来回所花的时间。

注意，RTT 不是单程传播时间，而是往返时间。

如果单向传播延迟是 15 ms，那么忽略处理时间和排队时间时：

1

RTT ≈ 15 ms × 2 = 30 ms

rdt3.0 性能差，就是因为发送方每发完一个分组后，要等待大约一个 RTT 才能继续发送。

3. 流水线 pipelining

3.1 流水线是什么？

流水线协议允许发送方：

在没有收到前面分组 ACK 的情况下，连续发送多个分组。

也就是说，不再是：

1

发 pkt0 → 等 ACK0 → 发 pkt1 → 等 ACK1

而是：

1
2

连续发送 pkt0, pkt1, pkt2, pkt3 ...
之后再陆续收到 ACK

这样可以让链路持续有数据在传输，减少空等时间。

3.2 为什么流水线需要更大的序号空间？

在 stop-and-wait 中，一次只有一个未确认分组，所以 0 和 1 两个序号就够了。

但在流水线中，多个分组可能同时在网络中：

1

pkt0, pkt1, pkt2, pkt3, pkt4

如果仍然只用 0/1 两个序号，就会出现多个不同分组使用相同序号的情况。接收方可能分不清：

• 这是旧的重复 pkt0？
• 还是新一轮的 pkt0？

所以流水线必须扩大序号范围，用更多 bit 表示分组序号。

3.3 为什么流水线需要缓冲区？

因为发送方连续发送多个分组后，这些分组不一定都已经被确认。只要没有被确认，它们就可能需要重传。

因此发送方必须保存：

已发送但尚未确认的分组。

这就是发送缓冲区的作用。

接收方也可能需要缓冲区，尤其是在 SR 中，接收方可能先收到高序号分组，但低序号分组还没到，这时就需要先缓存乱序分组。

❗ 本节核心结论：
流水线提高效率，但也带来新问题：需要更大的序号空间、发送缓冲区、接收缓冲区，以及窗口机制。

4. 滑动窗口 sliding window

滑动窗口是一种控制机制，用来规定：

哪些分组现在允许发送，哪些分组现在允许接收。

可以把它理解为在序号空间上画出一个范围：

• 落在窗口内：可以发送或接收；
• 落在窗口外：不能发送或不能接收。

5. 发送缓冲区 vs 发送窗口

这两个概念很容易混。

简单说：

1
2

发送缓冲区：存东西
发送窗口：管范围

发送缓冲区保存已经发送但还没确认的分组。发送窗口则规定当前哪些序号的分组可以处于“已发送但未确认”的状态。

发送窗口通常有两个边界：

可以理解为：

1
2
3

base                         nextSeqNum
 ↓                               ↓
[ 已发送但尚未确认的分组范围 ]

6. 接收窗口

接收窗口规定：

接收方当前愿意接收哪些序号的分组。

窗口外的分组通常会被丢弃，因为它可能是：

• 旧的重复分组；
• 太早到来的分组；
• 当前接收方不准备处理的分组；
• 序号回绕后造成歧义的分组。

GBN 和 SR 的一个核心区别就在接收窗口大小：

❗ 本节核心结论：
GBN 的接收窗口为 1，所以乱序分组会被丢弃；SR 的接收窗口大于 1，所以可以缓存乱序分组。

7. GBN：Go-Back-N

GBN 全称是 Go-Back-N。

它是一种流水线可靠传输协议，特点是：

• 发送方最多允许 N 个未确认分组在路上；
• 接收方只接受当前期待的分组；
• 接收窗口大小为 1；
• 使用累计确认 cumulative ACK；
• 超时后从最老未确认分组开始重传一批分组。

7.1 GBN 如何处理乱序分组？

假设发送方发送：

1

pkt0, pkt1, pkt2, pkt3, pkt4, pkt5

如果 pkt2 丢失，但 pkt3、pkt4、pkt5 正确到达接收方。

GBN 接收方此时期待的是 pkt2。由于 pkt3、pkt4、pkt5 都不是当前期待的分组，所以会被丢弃。

接收方会反复发送对 pkt1 的 ACK，表示：

1
2

我已经按序收到 pkt1 及之前的分组；
我还在等待 pkt2。

发送方最终超时后，会从 pkt2 开始重传：

1

pkt2, pkt3, pkt4, pkt5

这就是 Go-Back-N 的含义：

一旦中间某个分组丢失，就回退到那个分组，重传它及之后尚未确认的一批分组。

7.2 GBN 的 ACK 是累计确认

GBN 的 ACK 是 cumulative ACK，累计确认。

在 GBN 中：

1

ACKn

通常表示：

1

n 及其之前的所有分组都已经按序收到

例如：

1

ACK3

表示：

1

pkt0, pkt1, pkt2, pkt3 都已经按序收到

如果 pkt2 丢了，即使 pkt3 到了，接收方也不会 ACK3，而是继续发送 ACK1。

❗ 本节核心结论：
GBN 简单，但代价是：一个分组丢失，后面即使正确到达的分组也会被丢弃并重传。

8. SR：Selective Repeat

SR 全称是 Selective Repeat，选择重传。

它也是流水线协议，但比 GBN 更精细。

SR 的特点是：

• 发送窗口大于 1；
• 接收窗口大于 1；
• 接收方可以缓存乱序分组；
• 收到哪个分组，就单独确认哪个分组；
• 发送方只重传没有被确认的分组；
• 逻辑上每个未确认分组都需要独立定时器。

8.1 SR 如何处理丢包？

假设发送方发送：

1

pkt0, pkt1, pkt2, pkt3, pkt4, pkt5

如果 pkt2 丢失，但 pkt3、pkt4、pkt5 到达接收方。

SR 接收方会：

1
2
3
4

缓存 pkt3
缓存 pkt4
缓存 pkt5
分别发送 ACK3, ACK4, ACK5

发送方收到 ACK3、ACK4、ACK5 后知道：

1
2

pkt3、pkt4、pkt5 已经成功
pkt2 还没有成功

所以发送方只需要重传 pkt2。

当 pkt2 到达接收方后，接收方可以按序交付：

1

pkt2, pkt3, pkt4, pkt5

8.2 SR 可以乱序接收，但不能乱序交付

SR 的接收方可以先缓存高序号分组，但交给上层时仍然必须按序。

例如：

1
2
3
4

pkt3 到了，缓存
pkt4 到了，缓存
pkt5 到了，缓存
pkt2 还没到，不能交付 3/4/5

等 pkt2 到达后，才能一起交付：

1

pkt2, pkt3, pkt4, pkt5

所以：

1

乱序接收 ≠ 乱序交付

SR 的乱序接收是为了减少不必要重传；按序交付是为了保证上层看到的数据顺序正确。

❗ 本节核心结论：
SR 通过乱序缓存和选择性重传减少浪费，但实现复杂度明显高于 GBN。

9. 为什么 SR 要给每个未确认分组维护定时器？

GBN 和 SR 的重传逻辑不同。

SR 的目标是：

哪个分组丢了，就只重传哪个分组。

例如：

1
2
3

发送方发送 pkt0, pkt1, pkt2, pkt3, pkt4
pkt2 丢失
pkt3, pkt4 都被确认

这时发送方不应该重传 pkt3、pkt4，只应该重传 pkt2。

因此，发送方必须知道每个未确认分组各自是否超时。

实际工程实现中，可以用一个全局定时器队列来模拟多个定时器，但在协议逻辑上，SR 等价于“每个未确认分组都有自己的超时状态”。

10. SR 的 ACK 不是累计确认

SR 的 ACK 是单独确认。

在 SR 中：

1

ACK4

只表示：

1

pkt4 收到了

它不表示：

1

pkt0, pkt1, pkt2, pkt3, pkt4 全部收到了

可能出现这种情况：

1
2
3
4
5

pkt0 收到
pkt1 收到
pkt2 丢了
pkt3 收到
pkt4 收到

此时 SR 可以发送 ACK3、ACK4，但这不代表 pkt2 已经收到。

所以：

❗ 本节核心结论：
GBN 的 ACK 是累计确认；SR 的 ACK 是单独确认，ACKn 只说明 n 号分组已收到。

11. GBN vs SR 总对比

可以一句话概括：

GBN 用简单换取低开销，但出错时浪费大；SR 用复杂换取精确重传，出错时代价小。

12. SR 的窗口为什么不能太大？

这是本节最容易难的点。

SR 的窗口不能超过序号空间的一半，否则接收方可能分不清：

1
2

这是旧分组的重传？
还是新一轮的新分组？

12.1 例子：2 bit 序号，窗口大小为 3

假设序号只有 2 bit：

1
2

序号空间 = 0, 1, 2, 3
总大小 S = 4

如果 SR 窗口大小设为 3：

1

N = 3

初始接收窗口是：

1

[0, 1, 2]

发送方发送：

1

pkt0, pkt1, pkt2

接收方收到 pkt0、pkt1、pkt2 后，把它们交付给上层，接收窗口向前滑动。

由于序号会循环使用，新的接收窗口变成：

1

[3, 0, 1]

注意，这时 0 和 1 又重新进入接收窗口了。

12.2 问题：ACK 丢失导致旧分组重传

假设接收方发出的 ACK0、ACK1、ACK2 全部丢失。

发送方不知道接收方已经成功收到这些分组，于是超时后重传旧的：

1

pkt0, pkt1, pkt2

此时接收方当前窗口是：

1

[3, 0, 1]

旧的 pkt0 和 pkt1 正好落在当前接收窗口中。

接收方看到 pkt0 时无法判断：

• 这是上一轮旧 pkt0 的重传；
• 还是新一轮数据里的新 pkt0。

这就产生了歧义。

12.3 正确限制

为了避免旧窗口和新窗口重叠，SR 通常要求：

1

窗口大小 N ≤ 序号空间大小 S / 2

如果序号使用 n bit，那么序号空间大小为：

1

S = 2^n

所以 SR 窗口大小应满足：

1

N ≤ 2^(n-1)

例如 2 bit 序号：

1
2

S = 4
N ≤ 2

如果窗口大小为 2：

1
2

初始窗口：[0, 1]
滑动后：[2, 3]

旧的 pkt0、pkt1 即使重传回来，也不在当前窗口 [2,3] 中，因此不会被误认为新分组。

❗ 本节核心结论：
SR 允许乱序接收，因此必须限制窗口大小；否则序号回绕后，旧分组可能落入新窗口，被误认为新数据。

13. Stop-and-wait、GBN、SR 总体比较

14. 易混点整理

14.1 rdt3.0 慢，不是因为它不可靠

rdt3.0 的正确性没有问题。
它的问题是 stop-and-wait 导致链路利用率低。

14.2 流水线不是无限制发送

流水线必须配合窗口机制。
否则发送方无限制发送，会造成缓存压力、序号歧义和拥塞风险。

14.3 发送缓冲区不是发送窗口

• 发送缓冲区：存储数据；
• 发送窗口：控制序号范围。

14.4 GBN 丢弃乱序分组，不代表分组损坏

pkt3 可能完好无损，但如果接收方还在等 pkt2，GBN 就会丢弃 pkt3。

原因不是 pkt3 错了，而是它来早了。

14.5 SR 可以乱序接收，但必须按序交付

SR 缓存乱序分组，是为了减少重传。
但上层应用看到的数据仍然必须按序。

14.6 GBN 的 ACKn 和 SR 的 ACKn 含义不同

这个区别非常重要。

15. 自测题：暂不附答案

1. rdt3.0 已经能实现可靠传输，为什么还需要引入流水线协议？

2. 在 stop-and-wait 中，为什么链路带宽很大时，利用率反而可能非常低？

3. 发送方利用率 U_sender 中，L/R 和 RTT 分别代表什么？

4. 为什么 RTT 大会拖低 stop-and-wait 的利用率？

5. 流水线协议为什么必须扩大序号范围？

6. 如果流水线协议仍然只用 0/1 两个序号，会发生什么问题？

7. 为什么流水线协议需要发送缓冲区？

8. 请区分“发送缓冲区”和“发送窗口”。

9. 发送窗口的前沿和后沿分别在什么事件发生时移动？

10. 接收窗口的作用是什么？为什么窗口外分组通常要丢弃？

11. GBN 的接收窗口为什么等于 1？这会导致它如何处理乱序分组？

12. GBN 中，如果 pkt2 丢失，但 pkt3、pkt4、pkt5 都正确到达接收方，接收方会怎么处理它们？为什么？

13. SR 为什么可以减少不必要的重传？它为此付出了哪些复杂性代价？

14. 为什么 SR 中 ACK 不是累计确认？这和 GBN 有什么区别？

15. 为什么 SR 的窗口大小不能超过序号空间的一半？请用“旧分组被误认为新分组”的角度解释。

最终总结

Chapter 3-3 的核心不是重新讨论可靠性，而是讨论如何让可靠传输变得高效。

rdt3.0 已经能可靠传输，但 stop-and-wait 让发送方大部分时间都在等 ACK。流水线协议通过允许多个未确认分组同时在网络中传输，提高链路利用率。滑动窗口负责管理这些分组的发送范围和接收范围。

在此基础上，GBN 和 SR 代表两种不同取舍：

• GBN：简单，接收窗口为 1，累计确认，乱序分组直接丢弃，出错时回退重传一批；
• SR：复杂，接收窗口大于 1，单独确认，乱序分组可以缓存，出错时只选择性重传需要的分组。

❗ 最终核心结论：
GBN 是“简单但浪费”的流水线可靠传输；SR 是“复杂但精确”的流水线可靠传输。GBN 适合低出错、低复杂度场景；SR 适合高带宽、长 RTT、重传代价高的场景。