Appearance
滑动窗口：停止-等待、GBN、SR
概念
滑动窗口（sliding window）就是给发送方和接收方各划定一个"允许连续处理多少个帧"的范围——发送方不用等到确认回来才发下一帧，接收方也能一次容纳多个帧。
一句话说清它是什么：滑动窗口 = 把"发一帧停一下"改成"连续发一串、按序号对账"；窗口就是那个"允许在途的帧数上限"。
两种窗口（一对概念）：
| 窗口 | 谁维护 | 含义 |
|---|---|---|
| 发送窗口（ | 发送方 | "已发出但还没收到确认"的帧数上限——窗口内是"已发未确认"，窗口外右侧是"还没发" |
| 接收窗口（ | 接收方 | "允许接收的、不在期望范围内的帧数上限"——窗口内是"可以收下（并缓存）的序号" |
三种协议由两个窗口值区分（必背）：
| 协议 | 发送窗口 | 接收窗口 | 序号位数 | 一句话 |
|---|---|---|---|---|
| 停止-等待（Stop-and-Wait） | 1 | 1 | 1 | 发一帧、等一个确认，最慢也最简单 |
| 后退 N 帧（GBN） | 1 | 连续发，丢帧后从丢的那帧起全部重传 | ||
| 选择重传（SR） | 连续发，只重传真正丢了的那几帧，但要缓存失序帧 |
⚠️ "滑动窗口"解决的是两个问题，别只记一个：
- 可靠传输——靠"序号 + 确认 + 超时重传"，丢帧和错帧都能被发现并补上。
- 流量控制——接收方通过"窗口大小"告诉发送方"我还能收多少"，发送方不许超过。 （TCP 里这个窗口值写在首部的"窗口字段"里，见
net/43-flow.md。）两个功能共用同一个机制，这是滑动窗口设计得最漂亮的地方。
与上一章（net/21-error.md）的衔接：上一章的 CRC 只能"发现"错误；本章回答"发现之后怎么办"——ARQ（自动重传请求）就是"检错 + 重传"那条路线的完整实现。
原理
一、停止-等待：最简单的可靠传输，也是最浪费的
停止-等待的流程：
text
发送方 接收方
│ ① 发第 0 帧 ─────────────────────→ │ 收到, 校验通过
│ │ ② 交上层
│ ←───────────── ③ 回 ACK0 │
│ ④ 收到 ACK0, 序号 +1 │
│ ⑤ 发第 1 帧 ─────────────────────→ │
...
帧丢失 -> 发送方超时(计时器到点) -> 重传
确认丢失 -> 发送方超时 -> 重传 -> 接收方靠"序号"认出重复帧, 丢弃并重发确认
确认迟到 -> 发送方已重传, 迟到的确认被忽略(靠序号区分)三条"异常情况"的处理才是考点：
| 异常 | 发送方的动作 | 接收方的动作 |
|---|---|---|
| 数据帧丢失 / 出错 | 超时重传 | —— |
| 确认帧（ACK）丢失 | 超时重传 | 收到重复帧 → 丢弃，但"再发一次 ACK"（否则会死锁） |
| 确认帧迟到 | 已重传，收到迟到确认就丢弃 | 靠序号区分，不重复交付 |
⚠️ "序号只有 1 位（0/1 交替）就够了"是停止-等待最关键的一条：因为发送方"发一帧就等一个确认"，接收方永远不会同时面对两个不同的帧——它只需要区分"这是新帧还是上一帧的重传"，1 位正好。
信道利用率（必背公式）：
其中
锚点（本章定死）：帧长
⚠️ 0.2494% 这个数要记住它的"数量级感"：也就是说，信道 99.75% 的时间在空等。
只有 ，而 有 ——发送方发完一帧之后，剩下的时间全在等确认，链路完全空闲。 这就是"必须做流水线传输"的动力。
二、滑动窗口：把"等确认"的时间填满
核心思路：发送方不必等确认回来才发下一帧——它可以在"发送窗口"范围内连续发送多个帧，让链路上始终有数据在飞。 这段时间里能发多少帧，取决于"一个 RTT 内能塞进多少个
信道利用率（滑动窗口版）：
锚点（沿用上面的参数，
| 发送窗口 | 有效数据率（× 10 Mbps） | |
|---|---|---|
| 1（退化为停止-等待） | 0.2494% | 0.0249 Mbps |
| 2 | 0.4988% | 0.0499 Mbps |
| 10 | 2.4938% | 0.2494 Mbps |
| 100 | 24.9377% | 2.4938 Mbps |
| 200 | 49.8753% | 4.9875 Mbps |
| 400 | 99.7506% | 9.9751 Mbps |
| 401 | 100.0000%（封顶） | 10 Mbps |
| 500 | 100.0000%（封顶） | 10 Mbps |
最小窗口（刚好填满链路所需）：
⚠️ 三条必考结论：
- 利用率与窗口成正比，直到 100% 封顶：
时刚好铺满；再大也不会超过 100%（链路上就那么宽）。 越小（帧越短 / 速率越高），需要的窗口越大："带宽时延积"越大，越需要大窗口——这就是 TCP 在高带宽长时延链路上必须"窗口扩大选项"的原因。 - "窗口大小"决定的是"效率"，"窗口上限"决定的是"正确性"——后者由序号位数卡死（下一节）。
三、窗口上限：由序号位数决定（本节最核心）
序号只有
★ GBN 的上限：
text
假设 n = 2 (序号 0~3), 若允许 W_T = 4 = 2^n:
发送方发出 0,1,2,3 全部丢失确认
超时 -> 重传 0,1,2,3
接收方收到第二个"0"时: 这是"新的一轮第 0 帧"还是"上一轮的重传"?
★ 分不清 —— 因为序号空间刚好用尽, 两个"0"完全重叠
→ 所以 GBN 的窗口最多 2^n - 1 (= 3)★ SR 的上限：
text
假设 n = 2 (序号 0~3), 若允许 W_T = 3 (> 2^(n-1) = 2):
发送方发 0,1,2 (窗口=3)
接收窗口也 = 3 -> 期望收 0,1,2 (但只有 4 个序号, 会与下一轮重叠)
若 0,1,2 的确认全丢 -> 重传 0,1,2
接收方刚刚收下并缓存了 0,1,2 并"滑过窗口"到 3,0,1
★ 收到重传的 0 时: 它落在新窗口内 -> 被当成"新帧"收下 -> 数据重复
→ 所以 SR 的窗口最多 2^(n-1) (= 2), 即接收窗口与发送窗口之和不超过 2^n★ 一句话记住两条上限的推导依据：
| 协议 | 上限 | 推导依据 |
|---|---|---|
| GBN | 接收窗口为 1，只靠"期望序号"区分新旧；只要"发送窗口 + 1 | |
| SR | 发送窗口与接收窗口都要占序号空间，且两者相等： |
序号位数与窗口上限（锚点表）：
| 序号位数 | 序号范围 | GBN 上限 | SR 上限 | GBN 序号利用率 | SR 序号利用率 |
|---|---|---|---|---|---|
| 1 | 0 ~ 1 | 1 | 1 | 50.00% | 50.00% |
| 2 | 0 ~ 3 | 3 | 2 | 75.00% | 50.00% |
| 3 | 0 ~ 7 | 7 | 4 | 87.50% | 50.00% |
| 4 | 0 ~ 15 | 15 | 8 | 93.75% | 50.00% |
| 8 | 0 ~ 255 | 255 | 128 | 99.61% | 50.00% |
⚠️ 这张表顺带回答了一个常被问的问题："GBN 和 SR 谁更省序号？" 答案是 GBN——GBN 能把序号空间用到
（ 时 99.61%），而 SR 只能用一半（恒 50.00%）。 SR 的代价换来的是"重传量小"。
四、确认与重传：累积确认 vs 逐帧确认
| 对比项 | GBN | SR |
|---|---|---|
| 确认方式 | 累积确认（ACK | 逐帧确认（每个帧单独确认） |
| 接收方对失序帧 | 一律丢弃（因为接收窗口 = 1，只有"期望的那个"才收） | 先缓存起来（接收窗口 > 1） |
| 失序时的 ACK | 重复发送"最后一个按序帧"的 ACK | 正常确认已收到的帧 |
| 超时重传范围 | 该帧及其后所有已发未确认的帧 | 只重传超时的那一帧 |
| 发送窗口滑动 | 滑到"最早一个未被确认的帧" | 滑到"连续被确认的最高序号 + 1" |
| 接收方缓冲需求 | 不需要缓存（丢弃失序帧） | 需要缓存整个接收窗口 |
| 实现复杂度 | 简单 | 复杂 |
| 典型协议 | TCP 的"部分 GBN 特性" | TCP 的 SACK 选项 |
★ 锚点：一次丢帧的代价（发送 0 ~ 5 共 6 帧，帧 2 丢失）
GBN 的逐帧过程：
text
收到 0 -> 交上层, 回 ACK0
收到 1 -> 交上层, 回 ACK1
(帧 2 丢失)
收到 3 -> 失序, 丢弃, 重复回 ACK1 <- 注意: 回的是"最后一个按序帧"
收到 4 -> 失序, 丢弃, 重复回 ACK1
收到 5 -> 失序, 丢弃, 重复回 ACK1
发送方帧 2 超时 -> 重传 2, 3, 4, 5 <- 窗口内未确认的全部重传
重传的 2,3,4,5 均按序到达 -> 回 ACK2, ACK3, ACK4, ACK5
数据帧总数 = 6 + 4 = 10 帧; 确认帧 = 4(首轮) + 5(重传) = 9 个SR 的逐帧过程：
text
收到 0 -> 交上层, 回 ACK0
收到 1 -> 交上层, 回 ACK1
(帧 2 丢失)
收到 3 -> 失序但缓存, 回 ACK3 <- 先存着, 等 2 来了一起交付
收到 4 -> 失序但缓存, 回 ACK4
收到 5 -> 失序但缓存, 回 ACK5
发送方帧 2 超时 -> 只重传 2 <- 只重传那一个
收到 2 -> 交付 2,3,4,5 给上层, 回 ACK2
数据帧总数 = 6 + 1 = 7 帧; 确认帧 = 5(首轮) + 1(重传) = 6 个| 协议 | 首轮数据帧 | 重传帧 | 数据帧总数 | 确认帧数 | 缓存需求 |
|---|---|---|---|---|---|
| GBN | 6 | 4（2,3,4,5） | 10 | 9 | 无 |
| SR | 6 | 1（2） | 7 | 6 | 缓存 3 帧 |
⚠️ "GBN 多传了 3 帧"是本节最该记住的量化对比：丢 1 帧就让 GBN 白发了 3 帧（3, 4, 5 白跑一趟）——丢帧率越高、窗口越大，GBN 的浪费越严重。 但当"误码率很低"时，GBN 的简单实现反而更划算——这就是"为什么两者都有人用"。
⚠️ 一个易错细节：GBN 收到失序帧时回的是 ACK1 而不是 ACK3：因为它采用累积确认，"我只按序收到了 1，所以我只能确认到 1"——重复的 ACK1 在发送方看来就是"帧 2 出问题了"的信号（TCP 里的"重复确认"机制正是这么工作的，见
net/41-tcp.md的快重传）。
示例
例 1：C 实现——利用率、最小窗口、窗口上限与丢帧代价
参数：
（1000 bit @ 10 Mbps）、 、序号位数 ；丢帧场景为"发送 0 ~ 5，帧 2 丢失"。
#include <stdio.h>
/* 信道参数(本章锚点) */
#define TD 100.0 /* 数据帧发送时延: 1000 bit / 10 Mbps = 100 us */
#define RTT 40000.0 /* 往返时延: 单程 20 ms, 往返 40 ms = 40000 us */
int main(void) {
int i, n, W;
double u;
printf("① 停止-等待: U = T_D / (T_D + RTT)\n");
printf(" T_D = %.0f us, RTT = %.0f us -> U = %.0f / %.0f = %.4f%%\n",
TD, RTT, TD, TD + RTT, TD * 100.0 / (TD + RTT));
printf("\n② 滑动窗口: U = min(1, W x T_D / (T_D + RTT))\n");
{
int ws[8] = {1, 2, 10, 100, 200, 400, 401, 500};
for (i = 0; i < 8; i++) {
u = ws[i] * TD / (TD + RTT);
if (u > 1.0) u = 1.0; /* 封顶 100% */
printf(" W = %3d -> U = %8.4f%%, 有效数据率 = %6.4f Mbps\n",
ws[i], u * 100.0, u * 10.0);
}
}
printf("\n③ 最小窗口 W_min = ceil((T_D + RTT) / T_D)\n");
W = (int)((TD + RTT) / TD);
if ((TD + RTT) / TD > (double)W) W++; /* 向上取整 */
printf(" ceil(%.0f / %.0f) = ceil(%.0f) = %d\n", TD + RTT, TD, (TD + RTT) / TD, W);
printf("\n④ 序号位数 n 与窗口上限\n");
for (n = 1; n <= 8; n++) {
int seq = 1 << n;
printf(" n = %d 位: 序号 0~%3d; GBN W <= 2^n-1 = %3d (%.2f%%);"
" SR W <= 2^(n-1) = %3d (%.2f%%)\n",
n, seq - 1, seq - 1, (seq - 1) * 100.0 / seq, seq / 2, seq / 2 * 100.0 / seq);
}
printf("\n⑤ 一次丢帧的代价: 发送 0~5, 帧 2 丢失\n");
printf(" GBN: 重传 2,3,4,5 共 4 帧 -> 数据帧总数 = %d\n", 6 + 4);
printf(" SR : 只重传 2 共 1 帧 -> 数据帧总数 = %d\n", 6 + 1);
printf(" GBN 比 SR 多传 %d 帧 (白跑的是 3,4,5)\n", (6 + 4) - (6 + 1));
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
① 停止-等待: U = T_D / (T_D + RTT)
T_D = 100 us, RTT = 40000 us -> U = 100 / 40100 = 0.2494%
② 滑动窗口: U = min(1, W x T_D / (T_D + RTT))
W = 1 -> U = 0.2494%, 有效数据率 = 0.0249 Mbps
W = 2 -> U = 0.4988%, 有效数据率 = 0.0499 Mbps
W = 10 -> U = 2.4938%, 有效数据率 = 0.2494 Mbps
W = 100 -> U = 24.9377%, 有效数据率 = 2.4938 Mbps
W = 200 -> U = 49.8753%, 有效数据率 = 4.9875 Mbps
W = 400 -> U = 99.7506%, 有效数据率 = 9.9751 Mbps
W = 401 -> U = 100.0000%, 有效数据率 = 10.0000 Mbps
W = 500 -> U = 100.0000%, 有效数据率 = 10.0000 Mbps
③ 最小窗口 W_min = ceil((T_D + RTT) / T_D)
ceil(40100 / 100) = ceil(401) = 401
④ 序号位数 n 与窗口上限
n = 1 位: 序号 0~ 1; GBN W <= 2^n-1 = 1 (50.00%); SR W <= 2^(n-1) = 1 (50.00%)
n = 2 位: 序号 0~ 3; GBN W <= 2^n-1 = 3 (75.00%); SR W <= 2^(n-1) = 2 (50.00%)
n = 3 位: 序号 0~ 7; GBN W <= 2^n-1 = 7 (87.50%); SR W <= 2^(n-1) = 4 (50.00%)
n = 4 位: 序号 0~ 15; GBN W <= 2^n-1 = 15 (93.75%); SR W <= 2^(n-1) = 8 (50.00%)
n = 5 位: 序号 0~ 31; GBN W <= 2^n-1 = 31 (96.88%); SR W <= 2^(n-1) = 16 (50.00%)
n = 6 位: 序号 0~ 63; GBN W <= 2^n-1 = 63 (98.44%); SR W <= 2^(n-1) = 32 (50.00%)
n = 7 位: 序号 0~127; GBN W <= 2^n-1 = 127 (99.22%); SR W <= 2^(n-1) = 64 (50.00%)
n = 8 位: 序号 0~255; GBN W <= 2^n-1 = 255 (99.61%); SR W <= 2^(n-1) = 128 (50.00%)
⑤ 一次丢帧的代价: 发送 0~5, 帧 2 丢失
GBN: 重传 2,3,4,5 共 4 帧 -> 数据帧总数 = 10
SR : 只重传 2 共 1 帧 -> 数据帧总数 = 7
GBN 比 SR 多传 3 帧 (白跑的是 3,4,5)⚠️ 三点说明：
- 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现实跑核对，输出 30 行逐字一致。
(int)转换默认"截断"而不是"四舍五入"：所以要做"向上取整"必须补一步"若原值大于截断值就 +1"——(int)(401.0) = 401侥幸正确，但若参数变成40100 / 99 = 405.05，(int)会给出 405 而不是 406，那就错了。1 << n不要写成pow(2, n)：窗口上限是纯整数结论，用移位既准确又不会引入浮点误差（与net/21-error.md里求汉明码校验位数是同一个道理）。
例 2：Python——三种协议全表与逐帧对账
import math
def pad(s, w):
"""按"显示宽度"补空格: 中文算 2 列, 否则终端里对不齐"""
return s + ' ' * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))
TD, RTT = 100.0, 40000.0 # us
print('=== ① 三种协议: 窗口与序号 ===')
print(' ' + pad('协议', 14) + pad('发送窗口 W_T', 16) + pad('接收窗口 W_R', 16) + '序号位数')
for nm, wt, wr, nb in [('停止-等待', '1', '1', '1 位'),
('后退 N 帧 GBN', '2^n - 1', '1', 'n 位'),
('选择重传 SR', '2^(n-1)', '= W_T', 'n 位')]:
print(' ' + pad(nm, 14) + pad(wt, 16) + pad(wr, 16) + nb)
print(' ★ 停止-等待是"两边窗口都为 1"的退化情形')
print()
print('=== ② 停止-等待: U = T_D / (T_D + RTT) ===')
print(' 参数: 帧长 1000 bit, 数据率 10 Mbps -> T_D = %.0f us' % TD)
print(' 单程传播 20 ms -> RTT = %.0f us' % RTT)
u = TD / (TD + RTT)
print(' U = %.0f / (%.0f + %.0f) = %.4f%%' % (TD, TD, RTT, u * 100))
print(' → 信道有 %.4f%% 的时间在空等' % (100 - u * 100))
print()
print('=== ③ 滑动窗口: U = min(1, W x T_D / (T_D + RTT)) ===')
print(' ' + pad('发送窗口 W', 14) + pad('利用率', 14) + pad('有效数据率', 16) + '状态')
for W in [1, 2, 10, 100, 200, 400, 401, 500]:
u = min(1.0, W * TD / (TD + RTT))
tag = '退化 = 停止-等待' if W == 1 else ('刚好铺满' if W == 401 else
('封顶' if W > 401 else '链路有空闲'))
print(' ' + pad(str(W), 14) + pad('%.4f%%' % (u * 100), 14)
+ pad('%.4f Mbps' % (u * 10), 16) + tag)
print(' W_min = ceil((%.0f + %.0f) / %.0f) = ceil(%.0f) = %d'
% (TD, RTT, TD, (TD + RTT) / TD, math.ceil((TD + RTT) / TD)))
print(' ★ W 与利用率成正比, 到 W = 401 封顶; 再大也不涨')
print()
print('=== ④ 序号位数 n 与窗口上限 ===')
print(' ' + pad('n', 6) + pad('序号范围', 14) + pad('GBN 上限', 12) + pad('SR 上限', 12)
+ pad('GBN 序号利用率', 18) + 'SR 序号利用率')
for n in [1, 2, 3, 4, 8]:
seq = 1 << n
print(' ' + pad(str(n), 6) + pad('0 ~ %d' % (seq - 1), 14)
+ pad(str(seq - 1), 12) + pad(str(seq // 2), 12)
+ pad('%.2f%%' % ((seq - 1) * 100.0 / seq), 18)
+ '%.2f%%' % (seq // 2 * 100.0 / seq))
print(' ★ GBN: 发送窗口 + 1 <= 2^n → W <= 2^n - 1')
print(' ★ SR : 发送窗口 + 接收窗口 <= 2^n → W <= 2^(n-1)')
print()
print('=== ⑤ 一次丢帧的逐帧对账: 发送 0~5, 帧 2 丢失 ===')
print(' GBN (累积确认, 失序帧一律丢弃):')
gbn = [(0, 'OK', '交上层', 'ACK0'), (1, 'OK', '交上层', 'ACK1'),
(2, '丢失', '——', '——'), (3, '失序', '丢弃', 'ACK1 重复'),
(4, '失序', '丢弃', 'ACK1 重复'), (5, '失序', '丢弃', 'ACK1 重复')]
for seqn, st, act, ack in gbn:
print(' ' + pad('帧 %d' % seqn, 10) + pad(st, 10) + pad(act, 16) + ack)
print(' ' + pad('超时重传', 10) + pad('2,3,4,5', 10) + pad('窗口内全重传', 16)
+ 'ACK2~ACK5')
print(' 数据帧总数 = 6 + 4 = %d; 确认帧 = 4 + 5 = %d' % (10, 9))
print()
print(' SR (逐帧确认, 失序帧先缓存):')
sr = [(0, 'OK', '交上层', 'ACK0'), (1, 'OK', '交上层', 'ACK1'),
(2, '丢失', '——', '——'), (3, '失序', '缓存', 'ACK3'),
(4, '失序', '缓存', 'ACK4'), (5, '失序', '缓存', 'ACK5')]
for seqn, st, act, ack in sr:
print(' ' + pad('帧 %d' % seqn, 10) + pad(st, 10) + pad(act, 16) + ack)
print(' ' + pad('超时重传', 10) + pad('2', 10) + pad('只重传丢的那帧', 16) + 'ACK2')
print(' 数据帧总数 = 6 + 1 = %d; 确认帧 = 5 + 1 = %d' % (7, 6))
print(' ★ GBN 比 SR 多传 3 帧 —— 白跑的是 3, 4, 5; SR 的代价是要缓存 3 帧')
print()
print('=== ⑥ 窗口越大, 单帧丢失的连带代价越大 (每轮丢 1 帧) ===')
print(' 设丢失帧平均落在窗口中部: GBN 重传帧数 = (W+1)/2, SR 重传帧数 = 1')
print(' ' + pad('发送窗口 W', 14) + pad('GBN 本轮总帧', 16) + pad('SR 本轮总帧', 14) + 'GBN 多传')
for W in [4, 8, 16, 64, 128]:
g = W + (W + 1) / 2.0
s = W + 1
print(' ' + pad(str(W), 14) + pad('%.1f' % g, 16) + pad('%.1f' % s, 14)
+ '%.1f 帧' % (g - s))
print(' ★ 绝对浪费随窗口增大 (1.5 -> 63.5 帧) —— 这是 SR 存在的理由')
print(' ★ 但"浪费率"反而下降 ((W+1)/2 / W): 大窗口把一次浪费摊薄了')
print(' ' + pad('W', 8) + pad('浪费率', 12) + '（对照, 别把两个方向记反）')
for W in [4, 8, 16, 64, 128]:
print(' ' + pad(str(W), 8) + '%.2f%%' % ((W + 1) / 2.0 / W * 100))
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
输出对照（真实运行结果）：
=== ① 三种协议: 窗口与序号 ===
协议 发送窗口 W_T 接收窗口 W_R 序号位数
停止-等待 1 1 1 位
后退 N 帧 GBN 2^n - 1 1 n 位
选择重传 SR 2^(n-1) = W_T n 位
★ 停止-等待是"两边窗口都为 1"的退化情形
=== ② 停止-等待: U = T_D / (T_D + RTT) ===
参数: 帧长 1000 bit, 数据率 10 Mbps -> T_D = 100 us
单程传播 20 ms -> RTT = 40000 us
U = 100 / (100 + 40000) = 0.2494%
→ 信道有 99.7506% 的时间在空等
=== ③ 滑动窗口: U = min(1, W x T_D / (T_D + RTT)) ===
发送窗口 W 利用率 有效数据率 状态
1 0.2494% 0.0249 Mbps 退化 = 停止-等待
2 0.4988% 0.0499 Mbps 链路有空闲
10 2.4938% 0.2494 Mbps 链路有空闲
100 24.9377% 2.4938 Mbps 链路有空闲
200 49.8753% 4.9875 Mbps 链路有空闲
400 99.7506% 9.9751 Mbps 链路有空闲
401 100.0000% 10.0000 Mbps 刚好铺满
500 100.0000% 10.0000 Mbps 封顶
W_min = ceil((100 + 40000) / 100) = ceil(401) = 401
★ W 与利用率成正比, 到 W = 401 封顶; 再大也不涨
=== ④ 序号位数 n 与窗口上限 ===
n 序号范围 GBN 上限 SR 上限 GBN 序号利用率 SR 序号利用率
1 0 ~ 1 1 1 50.00% 50.00%
2 0 ~ 3 3 2 75.00% 50.00%
3 0 ~ 7 7 4 87.50% 50.00%
4 0 ~ 15 15 8 93.75% 50.00%
8 0 ~ 255 255 128 99.61% 50.00%
★ GBN: 发送窗口 + 1 <= 2^n → W <= 2^n - 1
★ SR : 发送窗口 + 接收窗口 <= 2^n → W <= 2^(n-1)
=== ⑤ 一次丢帧的逐帧对账: 发送 0~5, 帧 2 丢失 ===
GBN (累积确认, 失序帧一律丢弃):
帧 0 OK 交上层 ACK0
帧 1 OK 交上层 ACK1
帧 2 丢失 —— ——
帧 3 失序 丢弃 ACK1 重复
帧 4 失序 丢弃 ACK1 重复
帧 5 失序 丢弃 ACK1 重复
超时重传 2,3,4,5 窗口内全重传 ACK2~ACK5
数据帧总数 = 6 + 4 = 10; 确认帧 = 4 + 5 = 9
SR (逐帧确认, 失序帧先缓存):
帧 0 OK 交上层 ACK0
帧 1 OK 交上层 ACK1
帧 2 丢失 —— ——
帧 3 失序 缓存 ACK3
帧 4 失序 缓存 ACK4
帧 5 失序 缓存 ACK5
超时重传 2 只重传丢的那帧 ACK2
数据帧总数 = 6 + 1 = 7; 确认帧 = 5 + 1 = 6
★ GBN 比 SR 多传 3 帧 —— 白跑的是 3, 4, 5; SR 的代价是要缓存 3 帧
=== ⑥ 窗口越大, 单帧丢失的连带代价越大 (每轮丢 1 帧) ===
设丢失帧平均落在窗口中部: GBN 重传帧数 = (W+1)/2, SR 重传帧数 = 1
发送窗口 W GBN 本轮总帧 SR 本轮总帧 GBN 多传
4 6.5 5.0 1.5 帧
8 12.5 9.0 3.5 帧
16 24.5 17.0 7.5 帧
64 96.5 65.0 31.5 帧
128 192.5 129.0 63.5 帧
★ 绝对浪费随窗口增大 (1.5 -> 63.5 帧) —— 这是 SR 存在的理由
★ 但"浪费率"反而下降 ((W+1)/2 / W): 大窗口把一次浪费摊薄了
W 浪费率 （对照, 别把两个方向记反）
4 62.50%
8 56.25%
16 53.12%
64 50.78%
128 50.39%六条结论：
- 停止-等待的利用率只有 0.2494%：
- 利用率与窗口成正比、到 100% 封顶：
- 窗口上限由序号位数卡死：GBN 是
- 序号利用率 GBN 高、SR 恒定 50.00%：
- ★ 丢帧代价锚点：发送 0 ~ 5、帧 2 丢失 → GBN 重传 4 帧（总数 10），SR 只重传 1 帧（总数 7）——GBN 多传 3 帧，且失序帧 3、4、5 全被丢弃白跑一趟。
- 接收方缓存是 SR 的隐藏成本：SR 必须缓存整个接收窗口（本例 3 帧），GBN 一帧都不用存——"重传量"与"缓存量"的权衡，与
os/20-contiguous.md里"最佳适应反而最差"是同一类取舍。
考点
考点
1. 必背结论
- 滑动窗口解决两件事：可靠传输（序号 + 确认 + 超时重传）与流量控制（窗口大小）。
- 三种协议的两个窗口值：停止-等待
- ★ 停止-等待利用率：
- ★ 滑动窗口利用率：
- ★ 锚点（本章定死）：
- 最小窗口：
- ★ GBN 窗口上限
- ★ SR 窗口上限
- 锚点（
- 序号利用率：GBN
- GBN 用累积确认：ACK
- SR 用逐帧确认：失序帧先缓存，等缺口补上再一起交付。
- ★ 丢帧代价锚点：发送 0 ~ 5、帧 2 丢失 → GBN 重传 2,3,4,5（数据帧共 10、确认 9）；SR 只重传 2（数据帧共 7、确认 6）——GBN 多传 3 帧。
- 停止-等待的三种异常：数据帧丢失 → 超时重传；ACK 丢失 → 超时重传 + 接收方对重复帧"丢弃但重发 ACK"；ACK 迟到 → 发送方丢弃，接收方靠序号不重复交付。
- 序号位数：停止-等待只需 1 位（因为永远只有一帧在途）。
2. 高频陷阱
- 利用率公式漏掉
- 把
- 以为"窗口越大利用率越高，没有上限"：错。利用率封顶 100%——超出
- GBN 窗口上限写成
- SR 窗口上限写成
- 认为 GBN 收到失序帧时"回该帧的 ACK"：错。回的是"最后一个按序帧"的 ACK（重复确认）——累积确认的含义就是"我只按序收到了这么多"。
- 认为 GBN 的接收方会缓存失序帧：错。GBN 接收窗口 = 1，失序帧直接丢弃——缓存失序帧是 SR 的特征。
- 认为 SR 重传时会把窗口内所有未确认帧都重传：错。SR 只重传真正超时的那些帧——"全部重传"是 GBN 的行为。
- 把"发送窗口滑动"的时刻搞错：GBN 滑到"最早未被确认的帧"；SR 滑到"连续被确认的最高序号 + 1"——SR 有缺口时窗口不动（否则会与接收窗口错位）。
- 停止-等待的序号位数答成"2 位（0 和 1 两个）"：表述上要写"1 位可表示 0/1 两个序号"——题目问"需要几位序号"时答 1 位。
- 把"重复确认"当成"出错"：错。GBN/TCP 里重复 ACK 是正常信号，表示"某个帧丢了"——TCP 的快重传正是靠"收到 3 个重复 ACK"触发的。
- 混淆"窗口"与"缓存"：错。窗口是"允许在途/可接收的序号范围"，缓存是"实际存下的帧"——SR 缓存失序帧，GBN 不缓存。
3. 解题模板（"滑动窗口计算题"）
① 先辨协议: 两个窗口值是多少?
1 / 1 -> 停止-等待
2^n-1 / 1 -> GBN
2^(n-1) / 同 -> SR
② 利用率: U = W x T_D / (T_D + RTT + T_A), 上限 100%
题目给"帧长 L + 带宽 C" -> T_D = L / C
题目给"传播时延 d" -> RTT = 2d
③ 反求窗口: 要 U = 100% -> W >= (T_D + RTT) / T_D, 向上取整
④ 窗口上限: 题目给序号位数 n -> GBN 2^n-1; SR 2^(n-1)
反过来: 给窗口求 n -> GBN n >= log2(W+1); SR n >= 1+log2(W)
⑤ 丢帧题: 数"重传了哪些帧 + 一共发了多少帧 + 回了几个 ACK"
GBN 重传 = 丢帧及其后所有已发未确认帧; SR 重传 = 只有丢帧本身
⑥ 判断题见"窗口"字眼就先问一句: 这是"窗口大小"(效率) 还是"窗口上限"(正确性)?4. 与相邻章节的接口
net/21-error.md（差错控制）：上一章解决"怎么发现错误"，本章解决"发现之后怎么补"——ARQ = 检错码 + 确认 + 超时重传 + 序号，四件套齐了才叫可靠传输。net/23-csma.md（介质访问控制）：本章假设"帧一旦发出就完整到达或被完整丢弃"；下一章开始处理"多个站抢同一条线"的问题——链路层的两大任务（可靠传输 + 介质访问）在下一章合流。net/41-tcp.md与net/44-congestion.md（传输层）：TCP 的"滑动窗口 + 累积确认 + 超时重传"就是本章的 GBN 思路；TCP 的 SACK 选项则是 SR 思路；"重复 ACK 触发快重传"直接从本章的"GBN 重复确认"长出来。net/43-flow.md（TCP 流量控制）：本章的"窗口大小由接收方决定"在那一章变成"接收窗口 rwnd"——滑动窗口的流量控制功能在那里被量化。os/32-io.md（I/O 缓冲）："SR 必须缓存失序帧"与"双缓冲要把数据先存下"是同一类"用空间换时间"——缓冲量对应"等待填补的缺口"。ds/02-stack-queue.md（队列）："窗口滑动"本质是一个环形队列——序号按
小结
- 滑动窗口 = 给收发双方各划一个"允许连续处理多少帧"的范围；同时解决可靠传输与流量控制。
- 三种协议：停止-等待
- ★ 利用率公式：停止-等待
- ★ 锚点：
- ★ 窗口上限：GBN
- 序号利用率：GBN
- GBN 累积确认、失序丢弃、重复 ACK；SR 逐帧确认、失序缓存、只重传丢帧。
- ★ 丢帧代价：发送 0 ~ 5、帧 2 丢失 → GBN 发 10 帧、SR 发 7 帧——GBN 多传 3 帧，SR 多耗 3 帧缓存。
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。