路由
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| routing table/ˈraʊtɪŋ ˈteɪbl/ | 路由表 | lù yóu biǎo |
| longest prefix match | 最长前缀匹配 | zuì zhǎng qián zhuì pǐ pèi |
表与前缀
- 路由器的路由表 routing table 把目的前缀映射到下一跳；最长前缀匹配 longest prefix match 选最具体的路由，默认路由兜底。
- 表
10.0.0.0/8 → X、10.1.0.0/16 → Y、10.1.2.0/24 → Z、默认 → W：10.1.2.200走 Z，10.9.9.9走 X，192.168.1.1走 W。
{exercise:uni-cs0903-table}
练习
目的 10.1.2.200，表中有 /8、/16、/24 条目，走——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
最长前缀匹配：三者皆中，/24 最具体。
Dijkstra 数字版
- 课程权重：A–B 4、A–C 2、B–C 1、B–D 5、C–D 8、C–E 10、D–E 2、E–F 3、D–F 6。从 A 出发安定序 C、B、D、E、F，距离 2、3、8、10、13。
- F 的最优路径 A C B D E F 共 $2+1+5+2+3 = 13$——经 E（$10 + 3$）胜过 D 直连（$8 + 6 = 14$）。安定节点即最终：不再经它松弛。
{exercise:uni-cs0903-dijkstra}
练习
课程图上 F 的最短距离为——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
A C B D E F：2+1+5+2+3 = 13——经 E 胜 D 直连 14。
为何分层聚合
- 平铺表每主机一行：IPv4 要 $4 \times 10^9$ 行。前缀聚合一个 /12 覆盖 $2^{20}$ 地址，表保持在 $10^5$ 量级。
- 聚合故意丢弃主机位——没人需要知道主机，表才留得住人类尺度。
{exercise:uni-cs0903-aggregate}
练习
一个 /12 公告覆盖——个地址。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
32 − 12 = 20 主机位：聚合掉 2^20 个地址。