CS 168 · PROJECT 3 · HISTORICAL IMPLEMENTATION RECAP

TCP 传输栈：历史实现深度复盘

用 Fall 2022 Transport spec 与 PointBreaker/transport 的 2024 提交轨迹复建一个用户态 TCP socket 的心智模型，找出已闭合的不变量与尚未闭合的边界。

Implementation Recap Contract

来源状态：Fall 2026 Project 3 尚未发布，因此 current official spec ≠ historical PointBreaker implementation。这里只复盘 2024 repository 与其 Fall 2022 handout，不推断未来接口。当前兼容性：BLOCKED_BY_SOURCE；历史 Recap 深度：GOLD。

中心问题：两个端点如何用各自局部 state，共同维持“可靠、有序字节流”的幻觉？

Repository Audit：starter 与你的修改

证据	归属	结论
root commit `b0dbaf1`	Framework Context	control blocks、FinControl、RetxQueue、socket shell、acceptable_seg 大部已存在
Stage markers + root-to-head diff	YOUR CODE · Historical Implementation	握手、收发、ACK、窗口、关闭、重传、RTO 的 stage-marked implementation regions 有 117 行新增、40 行修改
`eb226bc…34af76a`	YOUR CODE · Historical Modification	逐 Stage 实现；末次提交明确修复 bytes-in-flight bug
tests 与 `tcp_sockets.py`	Framework Context	行为证据与参考环境，不归为个人答案

Part 1 · Socket 保存两个 sequence spaces

TX	含义	RX	含义
SND.UNA	最旧未累计确认字节	RCV.NXT	下一连续期待字节
SND.NXT	下一个可发送序号	RCV.WND	当前可接收空间
SND.WND	peer 通告的发送上限	RecvQueue	到达但尚不能连续交付的片段
ISS/WL1/WL2	初始序号与窗口更新证据	—	—

Part 2 · Sequence Space 贯穿全篇

ISS=100。SYN 占一个序号，所以握手后 SND.UNA=100、SND.NXT=101；发送 [101,201) 后 NXT=201。序号在模 2³² 的环上，因此 framework 提供 |PLUS| |MINUS| |LT| |LE|。

YOUR CODE · Historical Implementation · PointBreaker/transport

self.snd.nxt = self.snd.nxt |PLUS| len(p.tcp.payload)

What：推进发送右边界。
Why：ACK 才能定义已证明安全的前缀。
Break：重叠序号使 ACK 与 retransmission state 失去唯一含义。

Parts 3–9 · Code → Concept

对象/路径	机制	Invariant
`connect / handle_synsent`	Handshake	双方建立初始 sequence space；SYN 消耗 1
`RetxQueue.pop_upto`	累计 ACK	只保存尚未被 ACK boundary 证明安全的数据
`RecvQueue`	乱序 buffering	仅从 RCV.NXT 连续交付
`acceptable_seg`	receive window	只有与当前窗口相交的序列区间可影响 state
`update_rto`	RTT estimator	timeout 适应路径延迟与波动
`FinControl.pending`	延迟关闭	FIN 排在待发送 application bytes 之后

Full Failure Trace：loss + out-of-order + cumulative ACK

步	事件	UNA/NXT/retx	RCV.NXT/recv/ACK
0	初始	100/100/[]	100/[]/—
1	send [100,200)，lost	100/200/[[100,200)]	100/[]/—
2	[200,300) 到达	100/300/两项	100/[[200,300)]/ACK100
3	timeout earliest	100/300/重传第一项	100/队列不变/—
4	缺口补齐	100/300/两项待 ACK	依次消费两段→300/[]/ACK300
5	ACK300 到达	300/300/pop_upto→[]	300/[]/—

RetxQueue 不是 packet history，而是未被累计 ACK 证明安全的数据；RecvQueue 保存等待 RCV.NXT 缺口闭合的证据。

Counterfactual：pop_upto 多删一个

ACK200 时若连起点为 200 的 segment 也删除，而该段随后丢失，timer 已无对象可重传。被破坏的不变量：queue 必须覆盖全部已发送、但未被累计 ACK 覆盖的 sequence space。

acceptable_seg：为什么不能接受所有网卡送来的 segment

old duplicate 不应重复交付，过远 future segment 不应占满有限 buffer，zero window 又有专门边界行为。判断的是 segment interval 与 [RCV.NXT, RCV.NXT+RCV.WND) 是否相交；普通整数比较在 wraparound 附近会颠倒时间顺序。

FIN：close intent ≠ FIN transmitted

Framework Context · historical starter

if not self.pending or self.sent or self.socket.tx_data:
    return

pending 是延迟执行状态。tx_data 非空时 FIN 不能抢到数据前面，否则 peer 会先观察到字节流结束。

RTO：估计与 Karn ambiguity

固定 timeout 在高 RTT 上伪重传，在低 RTT 上恢复慢。首次 sample R=100ms 时 SRTT=100ms、RTTVAR=50ms；K=4 且 G 较小时 RTO=300ms。历史 ACK 路径只为 not p.retxed 的 packet 采样，因为重传后无法知道 ACK 对应原发送还是重传。

Bug Reconstruction：Stage 9 漏掉 backoff

handout 要求每次重传将 RTO 加倍并 cap；commit 29fb2ce 却写 self.rto = min(self.rto, self.MAX_RTO)，只 clamp、没有改变值，提交信息也仅称 “passed 1 2 of stage 9”。

Failure：持续 loss 时仍同频重传。
Fixed invariant：连续 timeout 必须降低探测频率；补 test 验证 1→2→4 秒并在 MAX_RTO 截止。

Bug Reconstruction：bytes in flight 是总预算

commit 34af76a 明确为 “fixed bytes in fly bug in stage 4”，发送循环开始计算 snd.nxt-snd.una。window 不是“单个 packet 大小”，而是所有未确认 bytes 的总预算；部分 ACK 只能释放相同大小额度。

Code Prediction

pop_upto 多删一项，在哪次 loss 后无法恢复？
普通整数比较 wraparound seq，哪个旧 segment 会被误判为未来？
重传也取 RTT sample，为何不能判定 sample 对应哪次发送？
close() 不等 tx_data 就发 FIN，peer 看到什么顺序？

Then / Now

Then：逐 Stage 通过 handshake、send、receive、close 与 timer tests。 Now：UNA/NXT 是证明边界；两个 queue 保存未闭合义务；FinControl 把用户意图排进 sequence order。

从代码回到 Lesson

L11 Reliability 对齐 sequence/ACK；L12 Design 对齐 control block；L13 Congestion 解释 timer 为何不能替代 cwnd。

Closed-book reconstruction

重画 loss trace 的每一步：SND.UNA、SND.NXT、SND.WND、retx queue、RCV.NXT、RCV.WND、recv queue 与 ACK；指出每步依赖的机制。