TCP 拥塞控制四算法

慢开始cwnd 从 1 开始，指数增长

初始 cwnd=1 MSS，每收到 1 个 新 ACK → cwnd += 1 MSS。效果：每经过 1 个 RTT，cwnd 翻倍。

轮次	cwnd（发送数）	发送报文段序号	收到 ACK 后 cwnd 变化
1	1	M0	+1 → 2
2	2	M1, M2	+2 → 4
3	4	M3~M6	+4 → 8
4	8	M7~M14	+8 → 16

cwnd=16 = ssthresh。按本例处理：下一轮切换为拥塞避免算法

/* 慢开始算法 */
cwnd = 1;  // 初始 1 MSS
ssthresh = 16;  // 慢开始门限

/* 轮次 1: 发 M0 */
ACK(M0) → cwnd += 1;  // cwnd = 2

/* 轮次 2: 发 M1, M2 */
ACK(M1), ACK(M2) → cwnd += 2;  // cwnd = 4

/* 轮次 3: 发 M3~M6 */
ACK(M3..M6) → cwnd += 4;  // cwnd = 8

/* 轮次 4: 发 M7~M14 */
ACK(M7..M14) → cwnd += 8;  // cwnd = 16

// cwnd == ssthresh：教材例子按“下一轮切换”处理

1

R1

2

R2

4

R3

8

R4

16

R5

cwnd bar 图：指数增长，4 轮从 1 到 16

拥塞避免cwnd 线性增长，每 RTT +1

cwnd > ssthresh 后，改慢为稳：每经过 1 个完整 RTT → cwnd += 1 MSS。若 cwnd = ssthresh，慢开始和拥塞避免都可使用；例题常从下一轮按拥塞避免处理。

轮次	cwnd	发送报文段序号	每轮结束后 cwnd
5	16	M15~M30	17
6	17	M31~M47	18
7	18	M48~M65	19
⋮	⋮	⋮	⋮
13	24	M171~M194	超时！

轮次 13：24 个报文段中部分丢失 → 超时重传 → 判断网络拥塞

/* 拥塞避免算法 */
// cwnd > ssthresh → 每 RTT +1
for (rtt = 5; cwnd < infinity; rtt++) {
    cwnd += 1;  // 线性增长
    send(cwnd segments);
    wait_for_ack();
}

/* 当 cwnd = 24 时发生超时 */
// Tahoe 处理：
ssthresh = cwnd / 2;  // = 12
cwnd = 1;             // 重回起点
// 重新执行慢开始...

16

R5

17

R6

18

R7

19

R8

20

R9

24

R13

线性增长缓慢但稳定，直到超时

超时重传后cwnd→1，ssthresh←cwnd/2

Tahoe 版本的统一处理：不管什么原因丢包，一旦超时：

动作	公式	本例
更新 ssthresh	ssthresh ← max(cwnd/2, 2×MSS)	24/2 = 12
重置 cwnd	cwnd ← 1 MSS	1
重新执行	慢开始算法

第二轮慢开始：1→2→4→8→12（新 ssthresh）→ 13→14→...

关键规律：ssthresh 总是拥塞发生前 cwnd 的一半，作为"安全窗口"的参考线。

/* Tahoe: 超时后的恢复 */
// 阶段 1: 拥塞检测
if (timeout) {
    ssthresh = max(cwnd / 2, 2 * MSS);
    cwnd = 1;           // 回到原点
}
// 阶段 2: 重新慢开始
while (cwnd < ssthresh) {  // 1→2→4→8→12
    per_ack: cwnd += 1;   // 指数级
}
// 阶段 3: 再次拥塞避免
while (no_loss) {           // 12→13→14→...
    per_rtt: cwnd += 1;    // 线性
}
/* 问题: 如果只是个别报文段丢失
   （非拥塞），Tahoe 也会把 cwnd
   砍到 1 —— 效率损失大 */

快重传收到 3 个重复 ACK → 立即重传

接收方收到失序报文段时，立即发送重复 ACK（不延迟）。发送方据此判断：

事件	发送方动作
收到 ACK(M1)	正常确认 M1 ✓
收到 ACK(M2)	正常确认 M2 ✓
收到 ACK(M2) ×1	dup ACK #1 — 可能是乱序
收到 ACK(M2) ×2	dup ACK #2 — 注意
收到 ACK(M2) ×3	dup ACK #3 → 立即重传 M3！不等超时

意义：收到 3 个重复 ACK 意味着"M3 丢了，但 M4/M5/M6 都到了" → 网络并未拥塞，只是个别丢包。

/* 快重传算法 */
int dup_count = 0;
int last_ack = 0;

void on_ack(int ack_num) {
    if (ack_num > last_ack) {
        // 新的累积确认
        last_ack = ack_num;
        dup_count = 0;
    } else if (ack_num == last_ack) {
        // 重复确认
        dup_count++;
        if (dup_count == 3) {
            // 立即重传丢失的报文段
            retransmit(last_ack);
        }
    }
}

/* 快重传避免了等待超时，使
   整个网络吞吐量提高约 20% */

快恢复Reno：跳过慢开始，直接线性增长

快重传后，Reno 不把 cwnd 降到 1，而是执行快恢复：

步骤	Tahoe	Reno（快恢复）
ssthresh	cwnd/2	cwnd/2
cwnd	1	ssthresh + 3
收到 dup ACK	—	cwnd += 1（临时扩大）
收到新 ACK	慢开始 1→2→4→...	cwnd = ssthresh，进入拥塞避免

总结：拥塞控制的四个算法是逐步演进的——慢开始和拥塞避免是基础（Tahoe, 1988），快重传和快恢复是改进（Reno, 1990）。核心思想：试探着增加，丢包了就减，但不该减过头。

/* Reno: 快重传 + 快恢复 */
void on_3_dup_ack() {
    ssthresh = cwnd / 2;
    cwnd = ssthresh + 3;
    // 快恢复阶段
    retransmit_lost_segment();
}
void on_dup_ack_during_recovery() {
    cwnd += 1;  // 每额外 dup ACK +1
}
void on_new_ack() {
    cwnd = ssthresh;  // 结束快恢复
    // 直接进入拥塞避免（线性增长）
}

/* 四种算法总结:
   ① 慢开始: cwnd 指数增长
   ② 拥塞避免: cwnd 线性增长
   ③ 快重传: 3 dup ACK → 立即重传
   ④ 快恢复: 不降到 1，继续线性
*/