Appearance
路由协议：RIP、OSPF、BGP
概念
路由协议（routing protocol）是路由器之间"交换路由信息、共同算出转发表"的一套约定——它决定了每个路由器怎么知道"去某个网络该走哪个口"。
★ 按作用范围分成两类，这是本章的第一道分界线：
| 类别 | 全称 | 作用范围 | 代表协议 |
|---|---|---|---|
| IGP | 内部网关协议（Interior Gateway Protocol） | 同一个自治系统 AS 内部 | RIP、OSPF |
| EGP | 外部网关协议（Exterior Gateway Protocol） | 不同 AS 之间 | BGP |
★ 自治系统（Autonomous System，AS）是"处在同一个管理机构下、使用统一路由策略的一组网络"——AS 内部各路由器目标一致（把包尽快送到对端），AS 之间则各有各的政治与经济算盘。 这个区别直接决定了：IGP 优化的是"最短"，BGP 优化的是"最符合策略"。
与上一章的衔接：上一章（net/32-nat.md）讲了"ICMP 类型 5 是路由器纠正主机选路"；本章讲的是"路由器之间怎么互相告知路径"——前者是"路由器 → 主机"的纠正，后者是"路由器 ↔ 路由器"的协商。 而上一章的"最长前缀匹配"是本章算出来的路由表被查询时的判定规则。
原理
一、路由的三种来源与"路由表里有什么"
| 来源 | 怎么来 | 特点 |
|---|---|---|
| 直连路由 | 接口配置了 IP 且接口 up，自动产生 | 距离最小、优先级最高 |
| 静态路由 | 管理员手工写 | 不占带宽、不自适应；适合小网络与默认路由 |
| 动态路由 | 路由协议算出来的 | 能自适应拓扑变化，但占用带宽与 CPU |
★ 一条动态路由表项至少包含四个字段：
text
目的网络 / 前缀长度 | 下一跳 | 出接口 | 度量值 (metric)
------------------------------------------------------------------
200.10.1.0/24 | 10.0.0.2 | eth0 | 3
★ 度量值 = 该协议的"距离单位": RIP 用跳数, OSPF 用带宽代价, BGP 用 AS 路径长度
★ 不同协议的度量值不可直接比较 -> 靠"管理距离/优先级"先在协议间排序⚠️ "度量值不可比"是本章最容易忽略的一句：RIP 说的"距离 3"与 OSPF 说的"代价 3"完全是两种单位——所以一个路由器同时跑多个协议时，先比"管理距离"（Cisco 口径：直连 0、静态 1、OSPF 110、RIP 120），同协议内部才比度量值。 408 一般不深考管理距离，但要知道"跨协议不能直接比 metric"。
二、RIP：距离向量算法
RIP（Routing Information Protocol，路由信息协议）是最早的内部网关协议——它的思想极简：每个路由器只跟"相邻"的路由器说话，说自己"到各个网络有多远"，剩下的靠大家互相传。
★ RIP 的四个硬参数（必背）：
| 参数 | 值 | 含义 |
|---|---|---|
| 度量 | 跳数（hop count） | 直连网络距离为 1，每经过一个路由器加 1 |
| 最大距离 | 15 | 距离 16 表示"不可达"——这就是"RIP 只能用于小网络"的原因 |
| 通告周期 | 30 秒 | 每 30 s 把整张路由表发给所有邻居 |
| 承载 | UDP，端口 520 | RIP 是应用层进程，靠 UDP 承载 |
| 失效率 | 180 秒未收到 → 标为距离 16 | 再过 60 秒（共 240 s）从表中删除 |
⚠️ "RIP 用 UDP"这一点常考：RIP 报文本身是应用层报文——它跑在 UDP 520 上。 对比：OSPF 直接封装在 IP 数据报里（协议号 89），BGP 跑在 TCP 179 上。 三个协议的承载方式各不相同，这是最爱考的对照点。
★ 距离向量算法的三条更新规则（本章核心，必背）：
设路由器收到邻居 X 发来的通告，其中说"我到网络 N 的距离是 d"。对本表的每一条：
| 情形 | 动作 |
|---|---|
| 规则① 本表没有到 N 的表项 | 新增：到 N 的距离 = |
| 规则② 本表有 N，且下一跳正是 X | 无条件替换：距离改为 |
| 规则③ 本表有 N，下一跳不是 X | 只有 |
⚠️ 规则②为什么"无条件替换"：因为 X 是"通往 N 的必经下一跳"——既然路径必须经过 X，那么"X 说到 N 的距离变了"，本机到 N 的距离必然跟着变。 哪怕 X 报的距离变大了（说明网络变差了），也要照改。 这一条是"坏消息传得慢"的根源（见本节第四部分）。
⚠️ 规则③为什么"必须更优才替换"：这是防止"路径自环"的最后一道闸——若不加这个条件，A 就会把"从 B 学到的东西再学一遍"，形成"A 经 B 去 B 刚才说的地方"这种绕圈路径。
★ 锚点（本章定死）：B 收到邻居 C 发来的距离向量，按三条规则更新自己的表
text
B 的原表 (更新前):
┌──────────┬──────────┬──────────┐ C 发来的报文:
│ 目的网络 │ 距离 │ 下一跳 │ ┌──────────┬──────────┐
├──────────┼──────────┼──────────┤ │ 目的网络 │ 距离 │
│ N1 │ 7 │ A │ ├──────────┼──────────┤
│ N2 │ 2 │ C │ │ N2 │ 4 │
│ N6 │ 8 │ F │ │ N3 │ 8 │
│ N8 │ 4 │ E │ │ N6 │ 4 │
│ N9 │ 4 │ F │ │ N8 │ 3 │
└──────────┴──────────┴──────────┘ │ N9 │ 5 │
└──────────┴──────────┘
★ 通告里的距离要 "+1" 之后才参与比较
逐条判定:
┌──────┬──────────────┬──────────────────────────────┬───────────────┐
│ 网络 │ 使用哪条规则 │ 理由 │ 更新后 │
├──────┼──────────────┼──────────────────────────────┼───────────────┤
│ N2 │ 规则② │ 下一跳就是 C -> 无条件替换 │ 4+1 = 5, 下一跳 C │
│ N3 │ 规则① │ 本表没有 N3 -> 新增 │ 8+1 = 9, 下一跳 C │
│ N6 │ 规则③ │ 下一跳 F != C, 4+1=5 < 8 -> 换 │ 5, 下一跳 C │
│ N8 │ 规则③ │ 下一跳 E != C, 3+1=4 = 4 -> 不动│ 4, 下一跳 E │
│ N9 │ 规则③ │ 下一跳 F != C, 5+1=6 > 4 -> 不动│ 4, 下一跳 F │
└──────┴──────────────┴──────────────────────────────┴───────────────┘
N1 不在 C 的通告里 -> 完全不动 (7, 下一跳 A)★ 由锚点得出的三条经验：
- 下一跳是同一个邻居的条目，一定要改（锚点里 N2 从 2 变成 5，是"变坏"也照改）。
- 新增条目只发生在"本表没这个网络"时（N3 就是这样进来的）。
+1之后再比较——N8 的
三、OSPF：链路状态算法
OSPF（Open Shortest Path First，开放最短路径优先）换了思路：不再"传递别人说的距离"，而是"每个路由器都把自己周围的链路状态告诉全 AS，然后各自算"。
★ OSPF 的三步：
text
第①步 发现邻居: 用 HELLO 分组周期打招呼 (默认 10 s 一次, 40 s 无回应认为邻居死)
第②步 洪泛链路状态: 每个路由器把自己的"链路状态通告"(LSA) 发给全 AS 内所有路由器
★ LSA 内容: 我有哪些邻居 + 到各邻居的代价 (cost)
第③步 各算各的: 每个路由器拿到"全 AS 的完整拓扑图"后, 用 Dijkstra 算最短路径树★ "链路状态"与"距离向量"的根本差别：
| 对比项 | 距离向量（RIP） | 链路状态（OSPF） |
|---|---|---|
| 每个路由器知道什么 | 只知道"邻居说到各网络多远" | 知道"整个 AS 的拓扑" |
| 交换的内容 | 整张路由表 | 只有"我与邻居的链路状态" |
| 交换对象 | 只和相邻路由器 | 洪泛给全 AS |
| 算法 | Bellman-Ford（分布式） | Dijkstra（每个路由器独立算） |
| 收敛速度 | 慢（坏消息传得慢） | 快 |
| 环路风险 | 有（要加水平分割等防护） | 无（每个人拿全图算，不会自欺） |
★ OSPF 的五个分组（必背）：
| 分组 | 作用 |
|---|---|
| HELLO | 发现与维持邻居关系 |
| DD（Database Description） | 描述自己的链路状态数据库摘要 |
| LSR（Link State Request） | 请求对方缺的那部分 LSA |
| LSU（Link State Update） | 真正把 LSA 发出去（洪泛） |
| LSAck | 确认收到 |
★ OSPF 的其他要点：
| 要点 | 内容 |
|---|---|
| 承载 | 直接封装在 IP 数据报里，协议号 89（不经 UDP/TCP） |
| 代价（cost） | 由管理员按带宽设——通常取 |
| 区域（area） | 骨干区域是 area 0；其他区域必须直接连到 area 0（否则要靠虚链路） |
| 支持的地址 | 支持 VLSM 与 CIDR（因为 LSA 里带掩码） |
| 负载均衡 | 到同一目的地的多条等代价路径可以同时用 |
| 认证 | 支持报文认证，防止伪造 LSA |
⚠️ "为什么 OSPF 要划分区域"：洪泛的本质是"每个人都要知道全图"——网络一大，LSA 数量与 Dijkstra 的计算量都爆炸。 划区域后，LSA 只在区域内洪泛，区域间只交换"汇总后的路由"——这就是 OSPF 能撑大网的原因。 （这个思路与
net/31-subnet.md的"聚合"是同一个动机：把细节折叠起来。）
四、坏消息传得慢与两种防护
RIP 最著名的缺陷就是"好消息传得快，坏消息传得慢"（good news travels fast, bad news travels slow）。
★ 场景：网络 N1 原本直连在路由器 A 上，A–B 之间有一条链路，B 的路由表里"N1 距离 2，下一跳 A"。 现在 N1 与 A 的链路断了。
text
断链后:
A 的表: N1 的直连条目消失 -> A 认为 N1 不可达 (距离 16)
B 的表: N1 距离 2, 下一跳 A <- ★ 这个旧值要等 180 s 才超时!
然后 (没有防护的话):
① B 周期通告 "我到 N1 的距离是 2" -> A 收到
A: 本表没有 N1 -> 规则① 新增: A 认为经 B 到 N1 距离 3 <- 假路由诞生!
② A 通告 "我到 N1 的距离是 3" -> B 收到
B: 下一跳正是 A -> 规则② 无条件替换: B 改成 4
③ B 通告 4 -> A 收到 (下一跳是 B, 规则②) -> A 改成 5
④ ... 你来我往, 每次 +2, 一直数到 16 才发现"不可达"
★ 结果: 要经过 15 次交换才收敛, 期间 A 与 B 都拿着"能到 N1"的假路由在转发★ 两种防护（都要会写）：
| 防护 | 做法 | 效果 |
|---|---|---|
| 水平分割（split horizon） | 从某个接口学到的路由，不再从这个接口通告回去 | A 不会再"把从 B 学到的 N1 说给 B"——假路由不再产生；但 B 的错项仍要等超时 |
| 毒性逆转（poisoned reverse） | 从某个邻居学到的网络，向该邻居通告时把距离写成 16（明确说"我这儿到不了"） | 邻居当场就判定不可达，不必等 180 s——收敛快得多 |
| 触发更新（triggered update） | 拓扑一变立刻通告，不等 30 s 周期 | 加快好消息的传播，缩小不一致窗口 |
⚠️ 水平分割不能解决"环路通信"的全部问题：水平分割只在"两方互相学习"的链路上有效；在三个以上路由器组成的环里，A 仍可能从第三个路由器（不是 B）学到一条绕圈的假路由。 所以工程上常用的是"水平分割 + 毒性逆转 + 触发更新"三者组合。 这一点是 RIP 无法根治的问题，也正是 OSPF 用链路状态取代距离向量的直接理由。
五、BGP：路径向量与策略路由
BGP（Border Gateway Protocol，边界网关协议）是 AS 之间的路由协议——它交换的不是"距离"，而是"到达某网络需要经过哪些 AS"，这个序列就叫 AS 路径（AS path）。
★ 为什么 AS 之间不能用"最短距离"：因为 AS 之间是商业与政治关系——同一份流量走哪家运营商，涉及结算、带宽成本、安全审查。 所以 BGP 的选路原则是"先讲策略，再讲路径长短"（这正是 BGP 与 IGP 最本质的差别）。
★ BGP 的四个要点：
| 要点 | 内容 |
|---|---|
| 算法类型 | 路径向量（path vector）——交换"AS 序列"，天然用于检测环路（路径里出现自己的 AS 号就丢弃） |
| 承载 | TCP，端口 179（靠 TCP 保证可靠传输，这是唯一用 TCP 的路由协议） |
| 两种会话 | eBGP（不同 AS 的路由器之间）+ iBGP（同一 AS 内部的路由器之间） |
| 四种报文 | OPEN（建立会话）/ UPDATE（通告路由）/ KEEPALIVE（保活，通常取保持时间的 1/3，如保持 180 s、保活 60 s）/ NOTIFICATION（报错） |
⚠️ "BGP 用 TCP"这一点常考：RIP 用 UDP 520（不可靠，靠周期通告兜底）、OSPF 直接用 IP 协议号 89（自带确认机制）、BGP 用 TCP 179——三者的选择逻辑是"链路可靠程度不同"：BGP 的邻居可能隔着几十跳和好几个 AS，必须靠 TCP 兜住可靠性。
★ 三协议九项对照（本章最该背下来的一张表）：
| 对比项 | RIP | OSPF | BGP |
|---|---|---|---|
| 范围 | IGP（AS 内） | IGP（AS 内） | EGP（AS 间） |
| 算法 | 距离向量 | 链路状态 | 路径向量 |
| 度量 | 跳数（最大 15） | 带宽代价 | AS 路径长度 + 策略 |
| 承载 | UDP 520 | IP，协议号 89 | TCP 179 |
| 交换对象 | 相邻路由器 | 全 AS 洪泛 | AS 边界的 BGP 邻居 |
| 交换内容 | 整张路由表 | 链路状态（LSA） | AS 路径属性 |
| 收敛 | 慢 | 快 | 慢（但稳定） |
| 规模 | 小网络 | 中大型 | 全球互联网 |
| 环路防护 | 水平分割 / 毒性逆转 | 不需要（有全图） | AS 路径自检 |
示例
例 1：C 实现——距离向量表的三规则更新
参数：B 的原表五项；C 通告五项（
N2 4 / N3 8 / N6 4 / N8 3 / N9 5）。
#include <stdio.h>
#include <string.h>
#define CAP 8
typedef struct {
char net[4];
int dist;
char nh; /* 下一跳路由器名, '-' 表示直连 */
int used;
} Route;
void add(Route *rt, const char *net, int d, char nh) {
int i;
for (i = 0; i < CAP; i++)
if (!rt[i].used) {
strcpy(rt[i].net, net);
rt[i].dist = d;
rt[i].nh = nh;
rt[i].used = 1;
return;
}
}
/* 收到邻居 nh 通告的 (net, d), 按 RIP 三条规则更新本表 */
void update(Route *rt, const char *net, int d, char nh) {
int i;
for (i = 0; i < CAP; i++) {
if (rt[i].used && strcmp(rt[i].net, net) == 0) {
printf(" %-3s ", net);
if (rt[i].nh == nh) {
printf("下一跳同为 %c (规则② 无条件替换): %d -> %d\n",
nh, rt[i].dist, d + 1);
rt[i].dist = d + 1;
} else if (d + 1 < rt[i].dist) {
printf("下一跳 %c 改 %c 且 %d < %d (规则③ 更优替换)\n",
rt[i].nh, nh, d + 1, rt[i].dist);
rt[i].dist = d + 1;
rt[i].nh = nh;
} else {
printf("下一跳 %c 改 %c 但 %d >= %d (规则③ 不替换)\n",
rt[i].nh, nh, d + 1, rt[i].dist);
}
return;
}
}
printf(" %-3s 本表没有 (规则① 新增): 距离 %d, 下一跳 %c\n", net, d + 1, nh);
add(rt, net, d + 1, nh);
}
void showtable(const char *tag, Route *rt) {
int i;
printf(" %s\n", tag);
printf(" %-6s %-6s %s\n", "NET", "DIST", "NEXT");
for (i = 0; i < CAP; i++)
if (rt[i].used)
printf(" %-6s %-6d %c\n", rt[i].net, rt[i].dist, rt[i].nh);
}
int main(void) {
Route rt[CAP];
const char *rnet[5] = {"N2", "N3", "N6", "N8", "N9"};
int rdist[5] = {4, 8, 4, 3, 5};
int i;
for (i = 0; i < CAP; i++) rt[i].used = 0;
add(rt, "N1", 7, 'A');
add(rt, "N2", 2, 'C');
add(rt, "N6", 8, 'F');
add(rt, "N8", 4, 'E');
add(rt, "N9", 4, 'F');
printf("① 更新前\n");
showtable("B 的原表:", rt);
printf("\n② B 收到 C 发来的距离向量 (N2 4, N3 8, N6 4, N8 3, N9 5)\n");
for (i = 0; i < 5; i++) update(rt, rnet[i], rdist[i], 'C');
printf("\n③ 更新后\n");
showtable("B 的新表:", rt);
printf("\n④ 三条规则的使用次数\n");
printf(" 规则① (新增) 1 次 —— 只有 N3\n");
printf(" 规则② (无条件替换) 1 次 —— 只有 N2\n");
printf(" 规则③ (更优才换) 3 次 —— N6 换, N8 与 N9 不换\n");
printf(" ★ 通告里的距离要 +1 后才比较: 3 + 1 = 4 与 4 相等 -> 不换\n");
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
text
① 更新前
B 的原表:
NET DIST NEXT
N1 7 A
N2 2 C
N6 8 F
N8 4 E
N9 4 F
② B 收到 C 发来的距离向量 (N2 4, N3 8, N6 4, N8 3, N9 5)
N2 下一跳同为 C (规则② 无条件替换): 2 -> 5
N3 本表没有 (规则① 新增): 距离 9, 下一跳 C
N6 下一跳 F 改 C 且 5 < 8 (规则③ 更优替换)
N8 下一跳 E 改 C 但 4 >= 4 (规则③ 不替换)
N9 下一跳 F 改 C 但 6 >= 4 (规则③ 不替换)
③ 更新后
B 的新表:
NET DIST NEXT
N1 7 A
N2 5 C
N6 5 C
N8 4 E
N9 4 F
N3 9 C
④ 三条规则的使用次数
规则① (新增) 1 次 —— 只有 N3
规则② (无条件替换) 1 次 —— 只有 N2
规则③ (更优才换) 3 次 —— N6 换, N8 与 N9 不换
★ 通告里的距离要 +1 后才比较: 3 + 1 = 4 与 4 相等 -> 不换⚠️ 三点说明：
- 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现实跑核对，输出逐字一致。
%-6s的表格头必须是 ASCII：printf的字段宽度按"字节"补齐，中文一个字占 3 字节、却只显示 2 列宽——用中文表头必然错位。 所以代码里写NET / DIST / NEXT，中文说明放在正文里。- N2 由 2 变成 5（"变差"也照改）是这个例子的灵魂：因为 C 是通往 N2 的下一跳——规则②不比较大小，只认"下一跳是不是它"。 若把这条写成"更优才换"，N2 就会永远停在 2，路由器会一直以为有一条并不存在的快路。
例 2：Python——三协议对照、坏消息传得慢与 Dijkstra
def pad(s, w):
"""按"显示宽度"补空格: 汉字算 2 列, 否则终端里对不齐"""
return s + ' ' * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))
print('=== ① 三协议对照 ===')
rows = [('范围', 'IGP (AS 内)', 'IGP (AS 内)', 'EGP (AS 间)'),
('算法', '距离向量', '链路状态', '路径向量'),
('度量', '跳数 (最大 15)', '带宽代价', 'AS 路径 + 策略'),
('承载', 'UDP 520', 'IP 协议号 89', 'TCP 179'),
('交换对象', '相邻路由器', '全 AS 洪泛', 'AS 边界的邻居'),
('交换内容', '整张路由表', '链路状态 LSA', 'AS 路径属性'),
('收敛速度', '慢', '快', '慢但稳定'),
('适用规模', '小网络', '中大型网络', '全球互联网'),
('环路防护', '水平分割/毒性逆转', '不需要 (有全图)', 'AS 路径自检')]
print(' ' + pad('对比项', 12) + pad('RIP', 20) + pad('OSPF', 20) + 'BGP')
for r in rows:
print(' ' + pad(r[0], 12) + pad(r[1], 20) + pad(r[2], 20) + r[3])
print()
print('=== ② 锚点: B 收到 C 的通告, 三条规则逐条判定 ===')
table = {'N1': (7, 'A'), 'N2': (2, 'C'), 'N6': (8, 'F'), 'N8': (4, 'E'), 'N9': (4, 'F')}
adv = [('N2', 4), ('N3', 8), ('N6', 4), ('N8', 3), ('N9', 5)]
print(' ' + pad('网络', 8) + pad('原值', 10) + pad('通告', 8) + pad('d+1', 8)
+ pad('规则', 10) + '结果')
for net, d in adv:
if net not in table:
rule, res = '规则①', '新增: 距离 %d, 下一跳 C' % (d + 1)
table[net] = (d + 1, 'C')
old = '—'
else:
od, onh = table[net]
old = '%d/%s' % (od, onh)
if onh == 'C':
rule = '规则②'
res = '无条件替换: %d -> %d' % (od, d + 1)
table[net] = (d + 1, 'C')
elif d + 1 < od:
rule = '规则③'
res = '更优替换: %d -> %d' % (od, d + 1)
table[net] = (d + 1, 'C')
else:
rule = '规则③'
res = '不替换 (d+1 = %d >= %d)' % (d + 1, od)
print(' ' + pad(net, 8) + pad(old, 10) + pad(str(d), 8) + pad(str(d + 1), 8)
+ pad(rule, 10) + res)
print(' N1 不在通告里 -> 完全不动 (7, 下一跳 A)')
print(' 最终表: ' + ', '.join('%s=%d/%s' % (k, v[0], v[1]) for k, v in sorted(table.items())))
print()
print('=== ③ 坏消息传得慢: A 与 N1 断链后逐轮交换 ===')
INF = 16
A = {} # A 上 N1 的直连条目消失
B = {'N1': [2, 'A']} # B 的旧值, 要 180 s 才超时
log = []
ex = 0
while ex < 40:
d = B['N1'][0]
ex += 1
if d >= INF:
if A.get('N1', [0, '-'])[1] == 'B':
A['N1'] = [INF, 'B']
elif 'N1' not in A:
A['N1'] = [min(d + 1, INF), 'B']
elif A['N1'][1] == 'B':
A['N1'] = [min(d + 1, INF), 'B']
elif d + 1 < A['N1'][0]:
A['N1'] = [min(d + 1, INF), 'B']
log.append((ex, 'B->A', d, A['N1'][0], B['N1'][0]))
if A['N1'][0] >= INF and B['N1'][0] >= INF:
break
d = A['N1'][0]
ex += 1
if B['N1'][1] == 'A':
B['N1'] = [min(d + 1, INF), 'A']
elif d + 1 < B['N1'][0]:
B['N1'] = [min(d + 1, INF), 'A']
log.append((ex, 'A->B', d, A['N1'][0], B['N1'][0]))
if A['N1'][0] >= INF and B['N1'][0] >= INF:
break
print(' ' + pad('次序', 8) + pad('方向', 10) + pad('通告值', 10) + pad('A 的距离', 12) + 'B 的距离')
for r in log:
print(' ' + pad(str(r[0]), 8) + pad(r[1], 10) + pad(str(r[2]), 10)
+ pad(str(r[3]), 12) + str(r[4]))
print(' 共交换 %d 次才双双归到 16 —— 这就是"坏消息传得慢"' % len(log))
print(' ★ 期间 A 与 B 都拿着"能到 N1"的假路由在转发 (距离 3 ~ 15)')
print()
print('=== ④ 三种防护的对比 ===')
for a, b, c in [('无防护', '照常互相通告', '交换 15 次才归 16, 且产生假路由'),
('水平分割', '从该接口学到的不再发回该接口', 'A 不产生假路由; B 的错项仍等 180 s 超时'),
('毒性逆转', '向学来的邻居通告"距离 = 16"', 'B 当场告诉 A 不可达, 不必等超时'),
('触发更新', '拓扑一变立即通告, 不等 30 s', '缩短不一致窗口, 加快好消息')]:
print(' ' + pad(a, 12) + pad(b, 32) + c)
print(' ★ 三者常组合使用; RIP 无法根治环状网络里的假路由 -> 这是 OSPF 出场的理由')
print()
print('=== ⑤ OSPF: Dijkstra 算最短路径树 (从 R1 出发) ===')
edges = [('R1', 'R2', 2), ('R1', 'R3', 5), ('R2', 'R3', 2), ('R2', 'R4', 4),
('R3', 'R4', 1), ('R4', 'R5', 3), ('R3', 'R5', 6)]
nodes = sorted({n for e in edges for n in e[:2]})
adj = {n: [] for n in nodes}
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
dist = {n: float('inf') for n in nodes}
prev = {n: None for n in nodes}
dist['R1'] = 0
done = []
while len(done) < len(nodes):
cur = min((n for n in nodes if n not in done), key=lambda n: dist[n])
done.append(cur)
for v, w in adj[cur]:
if dist[cur] + w < dist[v]:
dist[v] = dist[cur] + w
prev[v] = cur
print(' ' + pad('目的', 8) + pad('最短代价', 12) + pad('前一跳', 10) + '完整路径')
for n in nodes:
path, cur = [], n
while cur is not None:
path.append(cur)
cur = prev[cur]
path.reverse()
print(' ' + pad(n, 8) + pad(str(dist[n]), 12) + pad(str(prev[n]), 10)
+ ' -> '.join(path))
print(' ★ R5 走的是 R1-R2-R3-R4-R5 = 2+2+1+3 = %d, 而不是 R1-R3-R5 = 5+6 = 11'
% dist['R5'])
print(' ★ 每个路由器拿全图各算一次, 结果必然一致 -> 不会出现自欺的假路由')
print()
print('=== ⑥ 代价是怎么定的 ===')
print(' ' + pad('链路带宽', 14) + pad('代价 10^8 / 带宽', 20) + '说明')
for bw, name in [(10 ** 7, '10 Mbps'), (10 ** 8, '100 Mbps'), (10 ** 9, '1 Gbps'), (10 ** 10, '10 Gbps')]:
print(' ' + pad(name, 14) + pad(str(max(1, 10 ** 8 // bw)), 20) + '取整且不小于 1')
print(' ★ 代价小的链路优先 -> OSPF 会自动绕开慢链路, 而 RIP 只看跳数不看带宽')
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
输出对照（真实运行结果）：
=== ① 三协议对照 ===
对比项 RIP OSPF BGP
范围 IGP (AS 内) IGP (AS 内) EGP (AS 间)
算法 距离向量 链路状态 路径向量
度量 跳数 (最大 15) 带宽代价 AS 路径 + 策略
承载 UDP 520 IP 协议号 89 TCP 179
交换对象 相邻路由器 全 AS 洪泛 AS 边界的邻居
交换内容 整张路由表 链路状态 LSA AS 路径属性
收敛速度 慢 快 慢但稳定
适用规模 小网络 中大型网络 全球互联网
环路防护 水平分割/毒性逆转 不需要 (有全图) AS 路径自检
=== ② 锚点: B 收到 C 的通告, 三条规则逐条判定 ===
网络 原值 通告 d+1 规则 结果
N2 2/C 4 5 规则② 无条件替换: 2 -> 5
N3 — 8 9 规则① 新增: 距离 9, 下一跳 C
N6 8/F 4 5 规则③ 更优替换: 8 -> 5
N8 4/E 3 4 规则③ 不替换 (d+1 = 4 >= 4)
N9 4/F 5 6 规则③ 不替换 (d+1 = 6 >= 4)
N1 不在通告里 -> 完全不动 (7, 下一跳 A)
最终表: N1=7/A, N2=5/C, N3=9/C, N6=5/C, N8=4/E, N9=4/F
=== ③ 坏消息传得慢: A 与 N1 断链后逐轮交换 ===
次序 方向 通告值 A 的距离 B 的距离
1 B->A 2 3 2
2 A->B 3 3 4
3 B->A 4 5 4
4 A->B 5 5 6
5 B->A 6 7 6
6 A->B 7 7 8
7 B->A 8 9 8
8 A->B 9 9 10
9 B->A 10 11 10
10 A->B 11 11 12
11 B->A 12 13 12
12 A->B 13 13 14
13 B->A 14 15 14
14 A->B 15 15 16
15 B->A 16 16 16
共交换 15 次才双双归到 16 —— 这就是"坏消息传得慢"
★ 期间 A 与 B 都拿着"能到 N1"的假路由在转发 (距离 3 ~ 15)
=== ④ 三种防护的对比 ===
无防护 照常互相通告 交换 15 次才归 16, 且产生假路由
水平分割 从该接口学到的不再发回该接口 A 不产生假路由; B 的错项仍等 180 s 超时
毒性逆转 向学来的邻居通告"距离 = 16" B 当场告诉 A 不可达, 不必等超时
触发更新 拓扑一变立即通告, 不等 30 s 缩短不一致窗口, 加快好消息
★ 三者常组合使用; RIP 无法根治环状网络里的假路由 -> 这是 OSPF 出场的理由
=== ⑤ OSPF: Dijkstra 算最短路径树 (从 R1 出发) ===
目的 最短代价 前一跳 完整路径
R1 0 None R1
R2 2 R1 R1 -> R2
R3 4 R2 R1 -> R2 -> R3
R4 5 R3 R1 -> R2 -> R3 -> R4
R5 8 R4 R1 -> R2 -> R3 -> R4 -> R5
★ R5 走的是 R1-R2-R3-R4-R5 = 2+2+1+3 = 8, 而不是 R1-R3-R5 = 5+6 = 11
★ 每个路由器拿全图各算一次, 结果必然一致 -> 不会出现自欺的假路由
=== ⑥ 代价是怎么定的 ===
链路带宽 代价 10^8 / 带宽 说明
10 Mbps 10 取整且不小于 1
100 Mbps 1 取整且不小于 1
1 Gbps 1 取整且不小于 1
10 Gbps 1 取整且不小于 1
★ 代价小的链路优先 -> OSPF 会自动绕开慢链路, 而 RIP 只看跳数不看带宽六条结论：
- ★ 三条更新规则的分工：规则①管新增、规则②管"下一跳就是它"（无条件替换）、规则③管"另有出路"（更优才换）——锚点里 1 次新增、1 次无条件替换、3 次比较（1 换 2 不换）。
- ★ N2 从 2 变成 5 是"变差也照改"：因为 C 正是通往 N2 的下一跳——这条规则不能写成"更优才换"。
- ★
+1之后才比较：N8 的 - ★ 坏消息传得慢的账：要交换 15 次才双双归到 16（每来回一轮涨 2，从 3 涨到 16 正好 15 次）——期间两家都拿着假路由在转发。
- ★ 两种防护的差别：水平分割是"不说"（邻居只能等超时）、毒性逆转是"明确说不可达"（邻居当场修正）。
- ★ OSPF 用 Dijkstra 得到
R1-R2-R3-R4-R5：而"看起来短"的R1-R3-R5是
考点
考点
1. 必背结论
- ★ IGP = AS 内部（RIP / OSPF），EGP = AS 之间（BGP）；AS = 同一管理机构下、统一路由策略的网络集合。
- ★ RIP 四参数：度量 = 跳数（最大 15、16 = 不可达）/ 周期 30 s / 承载 UDP 520 / 180 s 失效、240 s 删除；直连网络距离为 1。
- ★★ 距离向量三条规则：① 本表没有 → 新增
- ★★ 锚点：B 原表
N1 7/A、N2 2/C、N6 8/F、N8 4/E、N9 4/F；C 通告N2 4、N3 8、N6 4、N8 3、N9 5→ 新表N1 7/A、N2 5/C、N3 9/C、N6 5/C、N8 4/E、N9 4/F。 - ★ 坏消息传得慢：断链后两家互相"学习"假路由、每来回涨 2，共 15 次交换才归 16。
- ★ 三种防护：水平分割（从该接口学到的不再发回）/ 毒性逆转（向学来的邻居通告 16）/ 触发更新（不等 30 s）。
- ★ OSPF：链路状态 + Dijkstra；五种分组 HELLO / DD / LSR / LSU / LSAck；直接封装在 IP（协议号 89）；骨干区域 area 0，其他区域必须连到它；支持 VLSM 与 CIDR。
- ★ OSPF 代价：
- ★ BGP：路径向量、TCP 179、eBGP/iBGP、四种报文 OPEN / UPDATE / KEEPALIVE / NOTIFICATION；选路先讲策略。
- ★ 环路防护各不同：RIP 靠水平分割与毒性逆转；OSPF 不需要（人人有全图）；BGP 靠 AS 路径自检（路径里出现自己的 AS 号就丢弃）。
- ★ 承载对照（最爱考）：RIP → UDP 520；OSPF → IP 协议号 89；BGP → TCP 179。
2. 高频陷阱
- 把 RIP 的"最大距离"记成 16：错。最大可用距离是 15，16 表示"不可达"——"能用的最大跳数"与"不可达的标记值"差 1，这是必考的细节。
- 说"RIP 跑在 TCP 上"：错。RIP 用 UDP 520；唯一用 TCP 的是 BGP（179）。
- 把 OSPF 说成"跑在 UDP 上"：错。OSPF 直接封装在 IP 数据报里，协议号 89。
- 更新规则③写成"
- 规则②写成"更优才替换"：错。无条件替换——锚点里 N2 从 2 变成 5 就是这条。
- 忘记"通告距离要 +1"：错。所有比较都用
- 认为"RIP 会较快收敛"：错。好消息快、坏消息慢——断链要 15 次交换才归 16。
- 把"水平分割"与"毒性逆转"混为一谈：错。水平分割是"不说"，毒性逆转是"说不可达（距离 16）"。
- 认为"水平分割能根治假路由"：错。只在两方互相学习的链路上有效；环状拓扑里第三方仍会传出绕圈路径。
- 把 OSPF 的算法说成"距离向量"：错。链路状态 + Dijkstra——它交换的是"链路状态"而不是"距离"。
- 认为"OSPF 的路由器只知道自己邻居的信息"：错。它掌握全 AS 的拓扑（这正是它不会产生环路假路由的原因）。
- 把 OSPF 的洪泛说成"把路由表发给所有路由器"：错。发的是"自己与邻居的链路状态（LSA）"，不是路由表。
- 认为"OSPF 的区域可以随意连"：错。其他区域必须连到骨干区域 area 0（否则要用虚链路）。
- 说 BGP 交换"跳数"：错。交换 AS 路径——AS 数量不是"距离"，还要叠加策略。
- 认为"BGP 一定选 AS 路径最短的"：错。策略优先——可能故意选更长的路径（商业结算、安全考虑）。
- 把"管理距离"与"度量值"混为一谈：要分清。管理距离 = 协议之间的优先级；度量值 = 协议内部的优劣——跨协议先比管理距离。
3. 解题模板（"距离向量表更新题"）
① 拿到"邻居发来的报文"和"本机原表"
② 逐条处理通告里的每个 (N, d):
+1: 先算 d' = d + 1
本表有 N 吗?
没有 -> 规则①: 新增 (N, d', 下一跳 = 该邻居)
有, 下一跳就是该邻居 -> 规则②: 无条件改为 d'
有, 下一跳是别人 -> 规则③: d' < 原值 才改为 d' 且改下一跳
d' >= 原值 保持不动
③ 通告里没有的网络 -> 一律不动 (不要"清零"或"删除")
④ 写出更新后的完整表
★ RIP 计时题:
30 s 周期通告; 180 s 未收到 -> 距离置 16; 240 s 后删除
★ OSPF 最短路题:
把拓扑画成带权图, 以源路由器为根跑 Dijkstra
代价按题目给的值; 默认 10^8 / 带宽
★ 协议归属题:
值域 15 / UDP 520 -> RIP
代价 / 协议号 89 / 五分组 -> OSPF
AS 路径 / TCP 179 / 四报文 -> BGP4. 与相邻章节的接口
net/30-ip.md（IP 数据报）：路由协议通告的"目的网络"就是上一章的 IP 网络地址；RIP 报文被封在 UDP 里、OSPF 报文封在 IP 里（协议号 89），用到的都是上一章的封装与"协议号"字段。net/31-subnet.md（子网划分与 CIDR）：上一章的"最长前缀匹配"是本章路由表被查询时的判定规则；RIPv2 增加了掩码字段才支持 VLSM/CIDR（RIPv1 不支持），OSPF 的 LSA 里也带掩码——"协议能不能带掩码"直接决定了它们能用什么样的地址结构。net/32-nat.md（NAT 与 ICMP）：ICMP 类型 5（改变路由）是"路由器 → 主机"的选路纠正，本章是"路由器 ↔ 路由器"的路由交换——前者靠单方面通知，后者靠协议协商；"ICMP 差错报文不再对 ICMP 差错发差错"与本章的"环路防护"是同一种"防止无限套娃"的思路。net/34-ipv6.md（IPv6）：OSPFv3 与 RIPng 为 IPv6 重写；IPv6 的链路本地地址用于邻居发现，与 OSPF 的 HELLO 邻居发现作用相似。ds/23-shortest.md（最短路算法）：本章 OSPF 用的 Dijkstra 与ds里讲的 Dijkstra 是同一个算法——区别只在"图的规模与实现"：ds讲怎么算，本章讲"每个路由器各自拿着全图算一遍"。os/30-filesystem.md（文件系统）：路由表的"最长前缀匹配 + 多级索引"与文件系统目录的"多级索引 + 路径匹配"是同一种"分层查找"结构——差别只在于路由表要按"1 位/8 位/任意位"跳着走，文件系统按固定层级走。
小结
- IGP（AS 内）：RIP、OSPF；EGP（AS 间）：BGP。
- RIP：跳数、最大 15、16 = 不可达、周期 30 s、UDP 520、180 s 失效。
- ★★ 距离向量三条规则：① 没有就新增
- ★ 锚点结论：
N2从 2 变 5（变差也改）、N3新增 9、N6换 5、N8与N9不动（ - 坏消息传得慢：15 次交换才归 16；防护 = 水平分割 + 毒性逆转 + 触发更新。
- OSPF：链路状态 + Dijkstra、HELLO/DD/LSR/LSU/LSAck、IP 协议号 89、area 0 为骨干、代价
- ★ OSPF 算例：从 R1 到 R5 的最短路是
R1-R2-R3-R4-R5，代价 8——比"跳数更少"的R1-R3-R5（11）更优。 - BGP：路径向量、TCP 179、eBGP / iBGP、OPEN / UPDATE / KEEPALIVE / NOTIFICATION、策略优先。
- ★ 承载速记：RIP-UDP 520、OSPF-IP 89、BGP-TCP 179。
下一篇：IPv6 与组播
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。