CS168 作业总教程与踩坑指南

Note

为什么没有给完整的 proj ?
因为我在WSL里好像网络是有问题，而且我不知道怎么配置。所以我就是额外在本地复制了WSL里写好的代码，然后创建文件的。

参考课程网站：

• Project 1: https://sp25.cs168.io/proj1/
• Project 2: https://sp25.cs168.io/proj2/
• Project 3: https://sp25.cs168.io/proj3/

这份文档按我自己的实际学习经验来写的。

先说总原则

这三次作业虽然内容不一样，但做法其实很统一。

共同建议(其实应该是必须这么做)：

1. 如果是 Windows，在 WSL 里做。
2. 优先用 python3，不要默认写 python
3. 严格在官网指定目录下运行命令
4. 只改官方要求你改的那个文件
5. 每做完一个阶段就测，不要一次写完再找 bug

为什么统一用 python3：

因为我用python会报错，但是python3不会。

目录和提交文件总览

官方要求改动的核心文件分别是：

• proj1: traceroute.py
• proj2: dv_router.py
• proj3: student_socket.py

关于测试方式

因为我不知道Gradescope的邀请码或者是否开放，我就是在本地测试的。 特别的：

• proj2 和 proj3 主要依靠本地单元测试、模拟器和命令行调试
• proj1 因为官方本地测试支持弱一些，所以主要依靠手动验证 traceroute 行为

Project 1: Traceroute

1. 这个项目要做什么

proj1 的目标是实现一个 traceroute。

你要做的事情本质上是：

1. 发 UDP probe
2. 收 ICMP reply
3. 解析 IPv4 / ICMP / UDP 头
4. 根据 TTL 一跳一跳地恢复路径
5. 在 1A 里先做基本版
6. 在 1B 里处理各种异常情况

2. 官方运行环境

官网对 proj1 的运行环境要求可以直接整理成下面这些点：

• 操作系统：项目测试环境是 Linux 和 Mac
• Python 版本：官方测试版本是 Python 3.11
• 工作目录：所有命令都应该在 cs168-sp25-proj1-traceroute 目录下运行
• 可修改文件：只改 traceroute.py
• 运行方式：需要直接在本机网络环境里发探测包、收 ICMP 响应

这部分一定要先确认清楚，因为 proj1 和后两个项目不太一样，它不是纯脚本模拟，而是真的要和本机网络栈打交道。

检查环境的命令是：

python3 --version
sudo python3 traceroute.py cmu.edu

这里的 sudo 很重要，因为 traceroute 通常要用原始套接字，普通权限可能不够。

如果这里都跑不通，就先不要急着写逻辑，先把运行环境修好。

3. 推荐完成顺序

Project 1 最好按这个顺序推进：

1. 先看 Traceroute Guide
2. 先手动跑一次 traceroute，理解返回包长什么样
3. 实现 IPv4、ICMP、UDP 三个 header parser
4. 完成 1A 的基本 traceroute
5. 确认能在简单场景下输出正确路径
6. 再进入 1B 的异常处理

4. 你写代码时真正要抓住的核心

Project 1 的难点不是代码量，而是「你是否真的理解收到的 ICMP 包在说什么」。

你必须搞清楚：

• 当前收到的是 ICMP Time Exceeded 还是 Destination Unreachable
• 这个 ICMP 包是不是你的 probe 引起的
• 里面嵌套的原始 IP/UDP 头是不是和你这次 traceroute 对得上
• 这个 response 属于当前 TTL，还是上一次 probe 的延迟包

5. Project 1A 怎么做

1A 核心是三件事：

1. 正确解析包头
2. 每个 TTL 发 PROBE_ATTEMPT_COUNT 个 probe
3. 收到目标主机响应后结束 traceroute

你要特别注意返回值格式：

• 返回的是 list[list[str]]
• 第 i 个子列表表示 TTL 为 i+1 时发现的路由器
• 同一个 TTL 下不要重复记录相同 IP
• 如果这个 TTL 没探测到任何路由器，就放空列表
• 一旦探测到目标 IP，最后一个列表应该是 [ip]

6. Project 1B 怎么做

1B 不是让你重写 traceroute，而是在已有代码上补「抗脏数据能力」。

你要重点处理：

• 无效 ICMP type
• 无效 ICMP code
• 目的主机不存在
• 某些路由器完全不回包
• packet drop
• duplicate response
• duplicate probe
• delayed duplicate
• 来自别的 traceroute 的旧 response

7. Project 1 最容易踩的坑

坑 1：只要收到 ICMP 就直接认

这是最容易挂 1B 的原因。

不是所有 ICMP 都是你这次 traceroute 的合法响应。你必须检查：

• type / code 对不对
• 内层原始包是不是你发的
• 目标 IP 和端口是不是匹配

坑 2：没有去重

官网 1B 明确有 duplicate tests。

如果你不对响应去重，就会出现：

• 某个 TTL 多出重复 IP
• 或者上一层 TTL 的残留包跑到下一层去

坑 3：收包逻辑写成「把队列彻底清空」

官网专门提醒了这一点。

如果你每个 TTL 都强行把接收队列完全 drain 掉，虽然逻辑上可能还能跑，但会特别慢，还容易导致简单测试超时。

正确思路是：

• 当前 TTL 收到足够的有效响应后就可以前进
• 但如果发生重复包，也要考虑适当清理残留，别把脏包留到下一轮

坑 4：没有处理 silent routers / missing host

不是每一跳都会回你。

所以你不能假设：

• 每个 TTL 一定有响应
• 最终一定能到达目标主机

Project 2: Distance-Vector Routing

1. 这个项目要做什么

proj2 的目标是实现一个 distance-vector router。

核心内容包括：

• 静态路由
• 数据转发
• 发送路由通告
• 接收路由通告并更新表项
• 超时删除
• poison / split horizon / poison reverse
• incremental updates
• link up / link down triggered updates

2. 官方环境要求

官方说明里给出的 setup 要点：

• 操作系统：这个项目本质上是本地 Python 模拟，不像 proj1 那样依赖 raw socket
• 测试版本是 Python 3.8
• 命令要在 cs168-sp25-proj2-routing/simulator 目录下运行
• 只改 dv_router.py

这里其实可以把官方运行环境理解成三件事：

1. 进入 simulator 目录
2. 跑 dv_unit_tests.py
3. 跑 simulator.py 看网络可视化和表项变化

如果不在这个目录下运行，测试脚本和拓扑模块的相对路径很容易直接错掉。

常用命令：

python3 --version
python3 dv_unit_tests.py 1
python3 dv_unit_tests.py 5
python3 dv_unit_tests.py 10
python3 simulator.py --start --default-switch-type=dv_router topos.simple

3. 推荐完成顺序

Project 2 很适合严格按 stage 做。

推荐顺序：

1. Stage 1: add_static_route
2. Stage 2: handle_data_packet
3. Stage 3: send_routes
4. Stage 4: handle_route_advertisement
5. Stage 5: expire_routes
6. Stage 6/7/8/9: split horizon、poison reverse、poison expired 等增强逻辑
7. Stage 10A: incremental triggered updates
8. Stage 10B: link up / link down triggered updates

4. 这个项目真正的核心思路

你要始终抓住 Bellman-Ford 更新逻辑：

• 邻居告诉我它到某个目标的代价
• 我把它的代价加上到这个邻居的链路代价
• 如果这条路更好，我就更新自己的 forwarding table
• 如果这个邻居本来就是我当前 next hop，那它的后续更新我也要接受

同时你要记住：

• forwarding table 的 key 是目的 host
• value 里要记录 port、latency、expire_time
• 项目里找的是到 host 的路，不是到 router 的路

5. Project 2 最容易踩的坑

坑 1：转发表里 route 存了，但转发时没用

很多人 Stage 1 能过，Stage 2 直接挂，因为只会建表，不会按表转发。

handle_data_packet 里至少要检查：

• 目的地址是否在表中
• latency 是否小于 INFINITY
• 符合条件才发送

坑 2：更新表项时没处理「当前 next hop」的情况

收到广告时，不是「只有更优路径才更新」这么简单。

如果当前 route 就是从这个邻居学来的，那这个邻居后续发来的更新你通常也要跟着改，不然表会陈旧。

坑 3：route 过期了却没删

这会导致：

• 实际链路已经断了
• 但路由器还在往旧端口发包

官网专门用断链测试来卡这个点。

坑 4：poison 和 delete 混在一起

POISON_EXPIRED、POISON_ON_LINK_DOWN、POISON_REVERSE 这些名字很像，但触发条件完全不一样。

不要混：

• expired route 要不要 poison
• link down 时要不要 poison
• 发给原 next hop 时是否 poison reverse

坑 5：Stage 10 之前没留出干净结构

官网明确提醒 Stage 10 会明显更长。

如果你前面把 send_routes 和 handle_route_advertisement 写得很乱，Stage 10A 的 incremental update 基本会重构一遍。

所以前面就建议你：

• 尽量抽 helper method
• 给每个 port 维护 advertisement history

坑 6：忘记 single_port

Stage 10B 会要求：

• link up 时只给新邻居同步
• send_routes(single_port=...) 只发给一个 port

如果你还按「无脑广播到所有 port」写，就会挂。

6. Project 2 最实用的本地测试方式

这个项目的本地测试条件其实是最完整的。

我比较推荐的做法是：

1. 先跑当前 stage 对应的 dv_unit_tests.py
2. 当前 stage 过了以后，再开 simulator
3. 一边看可视化，一边在终端打印 routing table

这样你既能看见测试结果，也能看见协议行为。

常见调试手段：

python3 simulator.py --start --default-switch-type=dv_router topos.simple
python3 simulator.py --start --default-switch-type=dv_router topos.candy

然后在终端里直接看：

print(s1.table)
print(s2.table)

这个项目不要只跑单元测试，也要看可视化和路由表变化。

Project 3: Transport

1. 这个项目要做什么

proj3 的目标是补完一个简化版 TCP socket。

你要实现的核心能力包括：

• 三次握手
• 按序接收
• 乱序接收
• 发送数据
• 处理 ACK
• 处理窗口
• 连接关闭
• 超时重传
• RTT / RTO 更新

2. 官方环境要求

官方说明里给出的 setup 要点：

• 操作系统：项目测试环境是 Linux 和 Mac
• 测试版本是 Python 3.7
• 所有 Python 命令建议在 cs168-sp25-proj3-transport/ext/cs168p2 目录下运行
• 只改 student_socket.py

这里需要额外注意两个官方运行环境细节：

• 第一次通常要先给 ../../pox.py 执行权限
• 所有测试命令都应该从 ext/cs168p2 这个目录发起

官方 setup 示例里有：

chmod +x ../../pox.py
python ../../pox.py config=tests/sanity_test.cfg

我自己会统一改成：

chmod +x ../../pox.py
python3 ../../pox.py config=tests/sanity_test.cfg

先把这条 sanity test 跑通，再开始写 stage，效率会高很多。

3. 先把环境跑通再写

这个项目很不适合「代码先写一半，再回头补环境」。

正确顺序应该是：

1. 先进入官方要求的工作目录
2. 先跑 sanity test
3. 确认 pox.py、autograder.py、tests/ 都能正常工作
4. 再开始按 stage 写 student_socket.py

4. 推荐完成顺序

Project 3 最适合严格按 Stage 走。

推荐顺序：

1. Stage 1: 三次握手
2. Stage 2: 按序收包
3. Stage 3: 乱序收包
4. Stage 4: 发包与 ACK
5. Stage 5: advertised window
6. 跑通 all 5 后提交 3A
7. Stage 6: passive close
8. Stage 7: active close
9. Stage 8: retransmission
10. Stage 9: RTT / RTO

5. 常用命令

常用命令可以写成：

python3 autograder.py s1
python3 autograder.py s2
python3 autograder.py s5
python3 autograder.py all 5
python3 autograder.py all

单独调失败测试时，官网推荐的做法也很重要：

• 从失败输出里复制那条 ../../pox.py ... 命令
• 去掉最后的 --filename=...
• 手动运行它看更直观的输出

6. Project 3 最容易踩的坑

坑 1：直接用普通整数比较 TCP 序号

官网专门给了 modular arithmetic 运算符。

涉及这些字段时，不要随手用普通大小比较：

• seq
• ack
• snd.nxt
• snd.una
• rcv.nxt

特别是 wraparound 测试里，普通比较很容易炸。

坑 2：忘了 SYN 和 FIN 都占 1 个序号

payload 长度不是唯一要占 sequence space 的东西。

• SYN 占 1
• FIN 占 1

这个错会连锁影响：

• 下一次发送序号
• ACK 判定
• 状态迁移

坑 3：乱序包直接塞进 rx_data

Stage 3 不是「谁先到就先交付给应用层」。

正确思路是：

1. 乱序包先进 queue
2. 只有等它变成当前 rcv.nxt 时才能真正处理
3. 每处理完一个包，再继续看后面是否已经连续

坑 4：ACK 时机不对

很多测试挂掉不是因为主逻辑完全错，而是 ACK 时机错。

你要特别盯住：

• 收到按序 payload 后有没有 ACK
• 收到乱序包后有没有请求缺失数据
• 收到 FIN 后有没有 ACK

坑 5：窗口没真正生效

不是「有数据就发」，而是「窗口允许多少就发多少」。

maybe_send() 至少要同时考虑：

• 发送窗口剩余空间
• self.tx_data 剩余数据
• 单个 segment 不超过 mss

坑 6：对重传包也更新 RTT / RTO

Stage 9 里这个点特别容易出错。

如果一个包已经重传过，再拿它当正常样本更新 RTT，RTO 就会越来越不靠谱。

7. Project 3 最实用的本地测试方式

这个项目和 proj2 一样，也非常适合本地测试。

我更建议这样调：

1. 先只跑当前 stage 的测试
2. 如果失败，就把失败用例单独拎出来
3. 手动执行那条 pox.py config=... 命令
4. 再回到 student_socket.py 对应函数里查

不要一上来就直接跑 all，因为错误会很多，但不一定容易定位。