Lab 3：在 UDP 之上实现可靠传输协议

💻 语言：Python 3.9+ 或 C++17（只能用 UDP socket）

为什么这个作业最重要

⭐ 理解 TCP 和实现 TCP 是两回事。 你可以完美复述滑动窗口、快速重传、AIMD——直到你自己写一个，才会发现那些教材上一笔带过的地方藏着多少真正的困难。

提供的框架

课程提供以下文件（不可修改）：

lab3/
├── channel.py          # ⭐ 可配置的不可靠信道模拟器
├── test_harness.py     # 自动测试与评分脚本
├── reference_traces/   # 参考的正确行为轨迹
└── YOUR_CODE/
    ├── sender.py       # ⭐ 你要实现
    └── receiver.py     # ⭐ 你要实现

信道模拟器

python3 channel.py --loss 0.05 --reorder 0.02 --corrupt 0.01 \
                   --delay-mean 50 --delay-jitter 20 --bandwidth 10

⚠️ 信道对上下行独立生效——你的 ACK 也会丢、也会乱序。

报文格式（必须严格遵守）

 0        8       16       24       32
┌────────┬────────┬────────┬────────┐
│              Seq (32)              │  ⭐ 字节序号（不是分组序号）
├────────────────────────────────────┤
│              Ack (32)              │
├────────┬────────┬─────────────────┤
│ Flags  │ 保留    │   Window (16)   │  Flags: SYN=1 ACK=2 FIN=4 SACK=8
├────────┴────────┼─────────────────┤
│  Checksum (16)  │  Length (16)     │  ⭐ 16 位反码校验和（第 10 讲）
├─────────────────┴─────────────────┤
│           Payload (0–1024)         │
└────────────────────────────────────┘

⚠️ 所有多字节字段使用网络字节序（大端）（第 9 讲的坑 3）。

import struct
HEADER_FMT = '>IIBBHHH'      # ⭐ '>' 表示大端
HEADER_LEN = struct.calcsize(HEADER_FMT)

Part 1：停等协议 rdt3.0（20 分）

实现第 11 讲的 rdt3.0：

✅ 16 位反码校验和（检测 --corrupt）
✅ 1 位交替序号
✅ 固定超时（先用 500 ms）
✅ 超时重传
✅ 对重复分组回 ACK 但不重复交付

通过标准：

python3 test_harness.py --part 1 --loss 0.2 --corrupt 0.05
# ⭐ 接收到的文件必须与发送的文件【逐字节相同】（用 sha256 校验）

📌 **这一步只考正确性，不考性能。**在 20% 丢包下它会慢得令人发指——这正是你要亲身体会的（第 11 讲的利用率公式）。

必须记录的数据：在 --loss 0、RTT=100ms、文件 1 MB 时的传输时间与吞吐量。与第 11 讲的公式 U = (L/R)/(RTT+L/R) 对比。

Part 2：Go-Back-N（25 分）

✅ 发送窗口 N（命令行可配，默认 16）
✅ ⭐ 累积确认
✅ ⭐ 单个定时器（针对最老的未确认分组）
✅ ⭐ 超时重传窗口内全部已发送未确认分组
✅ 接收方【丢弃】乱序分组，重发上一个 ACK
✅ 序号空间 ≥ N+1（第 12 讲）

必须记录：在丢包率 0%、1%、5%、10% 下的吞吐量与总发送分组数。

⭐ 总发送分组数是关键指标——它直接体现 GBN 的重传浪费。

Part 3：选择重传（25 分）⭐

✅ ⭐ 逐分组确认
✅ ⭐ 每个未确认分组一个定时器（可用一个定时器堆实现）
✅ ⭐ 超时只重传那一个
✅ ⭐ 接收方【缓存】乱序分组，补齐后批量交付
✅ ⭐ 接收窗口左侧的分组仍要回 ACK（第 12 讲的易错点）
✅ 序号空间 ≥ 2N

⚠️ 本 Part 最容易出错的三处：

① 忘记对【窗口左侧】的重复分组回 ACK
   → 发送方永远等不到 ACK → 死锁

② 接收窗口滑动时没有把【所有连续已缓存】的分组一次交付
   → 数据顺序错乱

③ 定时器管理：用 N 个 threading.Timer 会在窗口大时开销爆炸
   ⭐ 正确做法：用一个 heapq 维护 (超时时刻, seq)，主循环里检查堆顶

必须记录：与 Part 2 在相同参数下的对比表。

⭐ 报告中必须解释这张表符合还是不符合第 12 讲的理论预测。

Part 4：自适应超时（15 分）

实现第 13 讲的 RTT 估计：

EstimatedRTT = 0.875 × EstimatedRTT + 0.125 × SampleRTT
DevRTT       = 0.75 × DevRTT + 0.25 × |SampleRTT − EstimatedRTT|
Timeout      = EstimatedRTT + 4 × DevRTT

✅ ⭐ Karn 算法：【不对重传过的分组采样 RTT】
✅ ⭐ 超时后指数退避（Timeout 加倍，上限 60 s）
✅ 初始 Timeout = 1 s

必须提交一张图：横轴时间，纵轴同时画出 SampleRTT、EstimatedRTT、Timeout 三条曲线。

⭐ 在报告中解释：当信道时延突然增大时（用 --delay-mean 中途变化），三条曲线各自如何反应？为什么 Timeout 的反应比 EstimatedRTT 更"迟钝"？

Part 5：拥塞控制（25 分）⭐

实现第 16 讲的 TCP Reno：

✅ ⭐ 慢启动：cwnd 从 1 MSS 开始，每收到一个 ACK 加 1 MSS
✅ ⭐ 达到 ssthresh 后转入拥塞避免：每 RTT 加 1 MSS
✅ ⭐ 超时：ssthresh = cwnd/2, cwnd = 1，回到慢启动
✅ ⭐ 3 个重复 ACK：ssthresh = cwnd/2, cwnd = ssthresh + 3，进入快速恢复
✅ ⭐ 实际发送窗口 = min(cwnd, rwnd, 发送缓冲区)

必须提交一张 cwnd 演化图：横轴时间（或 RTT 轮次），纵轴 cwnd。

⭐ 图上必须标注出：

① 慢启动阶段（指数增长的那一段）
② 转入拥塞避免的转折点
③ 每一次丢包事件
④ ⭐ 区分【超时】（cwnd 掉到 1）和【3 个重复 ACK】（cwnd 掉到约一半）

📌 **这张图是本作业的标志性成果。**它应该长得和第 16 讲那张锯齿图一模一样——如果不像，说明你的实现有问题。

加分项（+10）

任选其一实现并对比：

⭐ SACK 选项：让发送方一次得知所有空洞，与纯 SR 对比恢复速度
⭐ CUBIC：cwnd 是距上次丢包时间的三次函数，与 Reno 在高 BDP 下对比
⭐ 快速恢复的窗口膨胀/收缩细节（RFC 6582 NewReno）

Part 6：性能实验报告（10 分）

必须包含以下实验（不是描述，是数据）：

实验 1：窗口大小 vs 吞吐量

固定 RTT = 100 ms、带宽 10 Mbps、无丢包，测量窗口 = 1, 2, 4, 8, 16, 32, 64 时的吞吐量。

⭐ 在同一张图上画出理论值 U = min(1, W·(L/R)/(RTT+L/R)) 和实测值，解释差异。

实验 2：丢包率 vs 吞吐量

固定窗口，测量丢包率 = 0.1%, 0.5%, 1%, 2%, 5% 时的吞吐量。

⭐ 验证第 16 讲的公式：吞吐量是否近似正比于 1/√L？用对数坐标画图，看斜率是否接近 −0.5。

实验 3：BDP 验证

固定带宽，改变 RTT（20/50/100/200 ms），测量"跑满链路所需的最小窗口"。

⭐ 验证它是否正比于 RTT（即正比于 BDP）。

⚠️ 一票否决项

❌ 传输结果与原文件不一致 → 该 Part 直接 0 分
   （可靠传输协议的第一要务是【正确】，性能是第二位的）
❌ 在无丢包信道上都无法完成传输 → 全作业 0 分
❌ 使用了 TCP socket 而非 UDP → 全作业 0 分

调试建议 ⭐

这是本课程最容易卡住的作业。以下建议来自往届学生的真实困难。

1. 分阶段验证，不要一次写完

① 先在【零丢包、零乱序】的信道上跑通停等 → 验证报文格式正确
② 加 --loss 0.1 → 验证超时重传
③ 加 --corrupt 0.05 → 验证校验和
④ 加 --reorder 0.1 → ⭐ 这一步会暴露大部分序号 bug
⑤ 加 --duplicate 0.05 → 验证重复检测

2. 打日志，但要能关掉

def log(event, **kw):
    if VERBOSE:
        print(f"[{time.time()-T0:8.3f}] {event:12s} " +
              " ".join(f"{k}={v}" for k, v in kw.items()), file=sys.stderr)

log("SEND", seq=seq, len=n, cwnd=round(cwnd,1))
log("RECV_ACK", ack=ack, dup=dup_count)
log("TIMEOUT", seq=send_base, new_rto=round(rto,3))

⚠️ 日志一定要输出到 stderr，否则会污染数据流。

3. 把日志直接变成图

# 边跑边写 CSV，实验结束直接画图
csv_writer.writerow([t, cwnd, ssthresh, rtt_sample, est_rtt, timeout])

📌 **不要等实现完了再想怎么画图。**从第一行代码就开始记录，你会在开发过程中就发现问题。

4. 最常见的五个 bug

5. 用参考轨迹对照

python3 test_harness.py --part 5 --compare reference_traces/part5.trace

它会告诉你你的 cwnd 演化在哪一步开始偏离参考实现。