CS 168 · PROJECT 2 · HISTORICAL IMPLEMENTATION RECAP

距离向量路由器：当前 spec × 历史实现复盘

从你在 2023 年真实修改的 branch、table 与 per-neighbor history 出发，重新理解一个距离向量路由器为何必须接受坏消息、传播失效状态，并守住转发不变量。

Implementation Recap Contract

版本边界：Fall 2026 official spec ≠ historical PointBreaker implementation。官方 Project 2 是当前权威要求；这里的 2023 代码只用来反推 state、invariant 与 failure，不是可提交答案。

中心问题：一个只看邻居消息的 router，怎样保持 forwarding choice 新鲜，并只在必要时向每个邻居发送正确 advertisement？

Repository Audit：哪些真是你的代码？

证据	归属	结论
root commit `b24f303` 的 starter skeleton	Framework Context	`DVRouterBase`、Ports、Table、callback 签名和 send APIs 已提供
`b24f303..15ff0ea` diff	YOUR CODE · Historical Implementation	填入七个 stage-marked implementation regions，并新增 history 与 flags
`aeb91c4→46e7c30→15ff0ea`	YOUR CODE · Historical Modification	Stage 10 history 从一维语义修成 per-neighbor state
unit tests / topology fixtures	Framework Context	定义可观察 contract，不归因成个人设计

Part 1 · Router 到底记住什么？

ports[port] → link latency：本地链路成本。
table[destination] → next-hop, metric, expire_time：当前 forwarding belief。
history[(destination,outgoing_port)] → advertised metric：对每个邻居说过什么。

history 不能只是 history[dst]：同一目的 D，对 route 来源 A 要 poison 为 ∞，对 B 却通告 5。

Part 2 · 收到 Route Advertisement：坏消息也要接受

YOUR CODE · Historical Implementation · PointBreaker/routing

new_latency = route_latency + self.ports.get_latency(port)
if (route_dst not in self.table
    or self.table[route_dst].port == port
    or new_latency < self.table[route_dst].latency):
    self.table[route_dst] = TableEntry(dst=route_dst, port=port, latency=new_latency)

What does it do?: 无 route 时安装；现用 next hop 更新时无论变好变坏都接受；其他邻居仅更优时替换。
Why must it?: metric 是当前 next hop 最新宣告的函数，不是历史最小值。
What breaks?: 删 same-next-hop 后，上升 metric 被忽略，stale route 留存。

Execution Trace：3 变 6，为何不能忽略

时刻	table[D]	事件	after/output
t0	via B, 3	—	packet 发 B
t1	via B, 3	B says 5；X→B=1；candidate=6	same next hop 成立，更新为 6
t2	via B, 6	比较每个 (D,neighbor) history	向受影响邻居发新 metric/poison

Counterfactual：删除 same-next-hop 条件

旧 metric=3；B 的 metric 上升后 candidate=6；因为“不更优”被忽略；table 仍称 D=3；packet 继续跟随已改变的 B。被破坏的不变量：当前 route 依赖 B 时，本地 state 必须反映 B 最新的可接受宣告。

Parts 3–5 · send_routes 是二维 policy

输出依赖 destination × outgoing neighbor × route next hop × last advertised value。Normal DV 报 metric；Split Horizon 对 next hop 不发；Poison Reverse 对 next hop 发 ∞。force 绕过增量抑制，single_port 只服务新邻居。

B 经 C 到目的	B→C	B→A
metric 1	Normal:1；Split:不发；Poison:∞	三种均可发 1

Parts 6–8 · Lifecycle / invariant

事件	state change	output	区别
route expiry	删除，或 metric=∞ + 新 expiry	triggered update	expiration ≠ poison reverse
link down	依赖该 port 的 routes 失效	传播坏消息	event poisoning
link up	ports 新增 latency	向新 port 发当前视图	single_port ≠ force all
data packet	不改 control state	finite route 才转发	forwarding ≠ routing

Bug Reconstruction：一维 history 为何过不了 Stage 10

aeb91c4 留下 “q10 still has some bug”，当时按 destination 保存一个值；46e7c30 改 tuple key，但写入 route next-hop；最终 15ff0ea 改为实际 outgoing port。

Wrong assumption：一个 destination 只有一个已通告值。
Root cause：poison reverse 使不同邻居看到不同 metric。
Fixed invariant：history 必须回答“我上次对这个特定邻居说了什么”。

Historical Implementation Review：最终 single_port 分支后仍进入后续逻辑。提交只证明当时 tests 通过；应补计数测试，验证 link-up 时旧端口零额外通告，新端口每目的恰好一次。

Code Prediction

删 same-next-hop：写 metric 变坏后的 stale-route timeline。
history 改成一维：预测 poison reverse 下的漏发/重复发。
link-down 只删 ports：下一枚 data packet 会读到什么无效 state？
single_port 后不 return：设计 send_route 调用次数测试。

Then / Now

Then：让 Stage 10 tests 通过。 Now：per-neighbor history 是输出缓存；same-next-hop 维护 freshness；poison 把失效 state 变成可传播 event。

从代码回到 Lesson

L5 Principles 建模目标；L6 DV trace 手推收敛；L7 Link State 对照全局拓扑；L8 Forwarding 解释 data path；L9 BGP 比较 policy。

Closed-book reconstruction

写 DVRouter 的三类 state、route advertisement 的三个接受条件、每个条件保护的 invariant，以及 update 后向哪个 neighbor 发什么 metric。