CS 168 · PROJECT 1A · ENGINEERING WORKBOOK
从零实现基础 Traceroute
在不依赖系统 traceroute 的前提下，发送 UDP probe、解析 IPv4/ICMP/UDP 首部，并把每个 TTL 观察到的路由器整理成 list[list[str]]。
工程合同
- What you build
- 在不依赖系统 traceroute 的前提下，发送 UDP probe、解析 IPv4/ICMP/UDP 首部，并把每个 TTL 观察到的路由器整理成 list[list[str]]。
- 核心不变量
- 任何返回结果都必须能由“某个本次发出的 probe → 合法 ICMP 响应 → 外层 source IP”这条证据链解释。
- Definition of Done
- Correct：当前适用测试通过；Understand：能从事件解释状态变化；Evidence：保留最小 trace、失败注入和边界测试。
- 禁止捷径
- 不读取模拟器隐藏全局状态，不修改框架绕过协议，不把本教材伪装成提交实现。
依赖优先的实现路径
0 · 建立包的证据链
- Build
- 手工发送 TTL=1、2、30 的 probe，保存原始 hex；对照 IPv4→ICMP→原始 IPv4→UDP 的嵌套结构，确认 router identity 来自外层 source IP，probe identity 来自 ICMP payload。
- Evidence
- 一张字段/offset 表；三个 probe 的预测与实测差异。
1 · 写三个纯解析器
- Build
- IPv4、ICMP、UDP 构造器只把 bytes 转成字段，不做网络 I/O。先检查最短长度，再按 network byte order 读取；IPv4 用 IHL×4 推导首部长度。
- Evidence
- 正常首部、随机字段、IP options、截断 buffer 的独立测试。
2 · 实现 TTL 外层循环
- Build
- 对 TTL=1..MAX_TTL 设置 socket，每个 TTL 发规定数量 probe；每次接收前调用 recv_select，合法响应加入本 TTL 去重集合，随后 print_result。
- Evidence
- 空 hop 保留空列表；发现目的 IP 后返回，未发现则到最大 TTL。
3 · 识别“到中间 / 到终点”
- Build
- ICMP Time Exceeded/TTL expired 代表中间 hop；目的主机对未监听 UDP port 返回 Destination Unreachable/Port Unreachable。其他 type/code 不能当作成功。
- Evidence
- 用最小合成包证明两类终止条件，不依赖真实互联网的偶然行为。
最小 sanity check
先构造只含两个端点和一个可控故障的最小场景。预测每条消息、字段和状态变化，再运行一次；任何额外消息、无法解释的表项或越界状态都视为失败，即使最终输出碰巧正确。
event | pre-state | input fields | expected mutation | emitted output | observed
失败签名
- 固定假设 IPv4 首部 20 B
- recvfrom 前未用 recv_select
- 把 ICMP payload 中的原始 source 当成路由器地址
- 真实网络异常与 autograder 合同混为一谈
Hint 1 · Concept
先指出哪个协议不变量被破坏，不要直接添加特判。
Hint 2 · Structure
让每个输入事件只经过一次“验证 → 状态转移 → 输出”流水线；把可纯计算的部分提取成无副作用函数。
Hint 3 · Debug strategy
对边界前后各造一个输入，用 spy 记录所有发送动作，并在每次 mutation 后断言控制块/表项关系。
完成后的复盘
- 哪个状态是真正的 single source of truth？
- 哪些测试只证明输出，哪些测试能证明没有额外副作用？
- 如果消息延迟、重复、乱序或刚好落在边界，会破坏哪条假设？
- 今天重写时，你会先设计哪三个 helper / invariant？
能力门：不用翻代码，向未来的自己讲清一个正常轨迹、一个失败轨迹和一个恢复轨迹，并能从日志重建状态。
Prediction → Experiment → Evidence
- Predict：先写出一个 response 的 header chain、终止分支与是否记录 hop。
- Experiment：用最小 mock packet，只改变 TTL、type 或 quoted destination。
- Evidence：记录 send/recv 次数、解析结果与退出原因；不能只写 tests pass。
Closed-book reconstruction
写出一次 TTL round 的 send → bounded receive → validate → classify → record → stop/continue 决策树，并指出每个 break/continue 保护什么。