一、路由问题：在动态变化的图上寻路
互联网是一张不断变化的图。节点（路由器）会上下线，边（链路）会拥塞、断裂或新增，每条边的权值（带宽、延迟、丢包率）也在持续波动。路由算法要解决的核心问题只有一个：在这张动态图上，为每一对源和目的地找到一条”好”的路径，并且在拓扑发生变化时尽快收敛到新的正确状态。
形式化地说，给定一个加权有向图 G = (V, E)，其中 V 是路由器集合，E 是链路集合，w(u, v) 是链路权值。路由算法需要为每个节点 n 构建一张路由表 T(n)，使得对于任意目的地 d，T(n)[d] 给出下一跳 next_hop(n, d) 和度量值 cost(n, d)。
静态路由（管理员手动配置）在超过 90 万条前缀的互联网中完全不现实。动态路由协议的设计空间可以沿两个维度划分：
域内 (IGP) 域间 (EGP)
距离向量 (DV) RIP, EIGRP --
链路状态 (LS) OSPF, IS-IS --
路径向量 (PV) -- BGP域内协议（IGP）在一个自治系统（AS）内部运行，优化目标是最短路径。域间协议（EGP）在自治系统之间运行，优化目标是策略合规。这种分层设计是互联网可扩展性的关键。
评价路由算法的五个维度：正确性（无环最优路径）、收敛速度、可扩展性、开销（带宽/内存/CPU）、策略支持。没有一种算法在所有维度上都最优，这也是为什么三大类算法各有其生态位。
二、距离向量算法：Bellman-Ford 的分布式演绎
距离向量（Distance Vector, DV）是最古老的动态路由算法。其核心思想来自 Bellman-Ford 松弛：
d(v) = min { w(v, u) + d(u) } 对所有邻居 u每个节点只知道两件事：到邻居的直连开销，以及邻居声称的到各目的地的开销。节点不知道完整的网络拓扑，只维护一张距离向量表。
算法流程
1. 初始化：每个节点 v 设 d(v, v) = 0，d(v, x) = INF (x != v)
2. 周期性地向所有邻居发送自己的完整距离向量
3. 收到邻居 u 的距离向量后，对每个目的地 x：
if w(v, u) + d(u, x) < d(v, x):
d(v, x) = w(v, u) + d(u, x)
next_hop(v, x) = u
4. 若距离向量有变化，触发更新通告
5. 重复直到收敛计数到无穷问题
DV 算法最严重的缺陷是计数到无穷（count-to-infinity）问题。考虑一个简单的三节点链路：
A ---1--- B ---1--- C
初始状态：
A: d(A,C) = 2, via B
B: d(B,C) = 1, via C
当 B-C 链路断开时：
B: d(B,C) = INF
B 收到 A 的更新：d(A,C) = 2
B 计算：d(B,C) = w(B,A) + d(A,C) = 1 + 2 = 3，via A （错误！A 是经过 B 到 C 的）
A 收到 B 的更新：d(B,C) = 3
A 计算：d(A,C) = w(A,B) + d(B,C) = 1 + 3 = 4
... 循环递增直到达到 INF这个过程可能需要很多轮才能收敛，这就是所谓的”好消息传得快，坏消息传得慢”。
缓解方案
为了应对计数到无穷问题，DV 算法引入了多种补丁：
水平分割（Split Horizon）：不把从某邻居学到的路由再通告回该邻居。在上面的例子中，A 不会把经由 B 学到的 C 路由告诉 B。
毒性反转（Poison Reverse）：比水平分割更激进。不仅不告诉邻居从它那里学到的路由，还主动告诉它该路由的度量是无穷大。
水平分割：A 不告诉 B 关于 C 的路由
毒性反转：A 告诉 B "我到 C 的距离是 INF"触发更新（Triggered Update）：路由表变化时立即发送更新，不等待周期性定时器。
保持计时器（Hold-down Timer）：收到某目的地不可达的通告后，在一段时间内拒绝接受对该目的地的新路由，防止残留的旧信息造成环路。
补丁 | 能解决的场景 | 局限性
-------------|--------------------|--------------------------
水平分割 | 两节点环路 | 三节点以上的环路无效
毒性反转 | 两节点环路（更彻底）| 同上
触发更新 | 加速收敛 | 不能消除环路本身
保持计时器 | 减少路由震荡 | 牺牲收敛速度这些补丁都不能彻底解决问题，只是在实践中大幅减少了出现计数到无穷的概率和持续时间。
三、RIP：简单但有限的距离向量协议
路由信息协议（Routing Information Protocol, RIP）是 DV 算法最经典的实现，也是互联网最早的动态路由协议之一。
RIP 的基本特性
版本 | RIPv1 (RFC 1058) | RIPv2 (RFC 2453) | RIPng (RFC 2080)
协议 | UDP 520 | UDP 520 | UDP 521
度量 | 跳数 | 跳数 | 跳数
最大跳数 | 15 | 15 | 15
VLSM | 不支持 | 支持 | 支持（IPv6）
认证 | 无 | 明文/MD5 | IPsec
组播 | 广播 255.255.255.255| 224.0.0.9 | FF02::9
更新间隔 | 30 秒 | 30 秒 | 30 秒15 跳限制
RIP 使用跳数作为唯一的度量标准，并将最大跳数限制为 15。跳数 16 表示”不可达”。这个限制有两个后果：
- 网络直径受限：任意两点之间最多 15 跳，这在大型企业网络中很容易超过。
- 计数到无穷有上界：最多数到 16 就会停止，这实际上是一种简单粗暴但有效的收敛保证。
收敛速度
RIP 的收敛速度非常慢。默认情况下，每 30 秒发送一次完整的路由表更新。即使使用触发更新，完全收敛也可能需要数分钟。
最坏情况收敛时间估算：
15 跳 * 30 秒/轮 = 450 秒 = 7.5 分钟
加上保持计时器 (180 秒) = 更长这在现代网络中完全不可接受。实际生产环境中，RIP 几乎已经被 OSPF 和 IS-IS 完全取代。RIP 的价值主要在于教学：它是理解距离向量算法最直观的实例。
EIGRP
Cisco 的 EIGRP 使用 DUAL 算法，是对经典 DV 的重大改进：使用复合度量、维护拓扑表、保证无环路收敛、支持不等价负载均衡。2013 年发布为 RFC 7868，但实际上仍主要在 Cisco 设备上使用。
四、链路状态算法：Dijkstra 的 SPF 与全局视图
链路状态（Link State, LS）算法采用了完全不同的哲学：让每个节点知道整个网络的拓扑，然后各自独立地用 Dijkstra 算法计算最短路径树。
核心思想
DV: "我不知道全貌，但我的邻居告诉我他们到各处的距离"
LS: "我知道整个地图，我自己算最短路径"LS 算法的三个步骤：
- 邻居发现：通过 Hello 协议发现直连邻居
- 链路状态通告（LSA）洪泛：每个节点将自己的链路状态（邻居列表和链路开销）封装成 LSA，洪泛到整个网络
- SPF 计算：每个节点用收到的所有 LSA 构建完整拓扑数据库（LSDB），然后运行 Dijkstra 算法计算到所有目的地的最短路径
Dijkstra 算法回顾
Dijkstra 的 SPF（Shortest Path First）算法是链路状态路由的计算核心：
SPF(G, src):
dist[src] = 0
dist[v] = INF 对所有 v != src
PQ = 所有节点的优先队列（按 dist 排序）
while PQ 非空:
u = PQ.extract_min()
for each neighbor v of u:
alt = dist[u] + w(u, v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
PQ.decrease_key(v, alt)
return dist[], prev[]使用二叉堆的时间复杂度为 O((V + E) log V)，使用斐波那契堆可以达到 O(E + V log V)。
LSA 洪泛机制
LSA 洪泛是 LS 算法的关键组件。每个 LSA 包含：
- 发起者 ID
- 序列号（用于检测新旧）
- 年龄（防止旧 LSA 永远留在网络中）
- 链路列表和对应开销
洪泛过程采用可靠的泛洪：
收到 LSA 时：
if LSA 的序列号 > 数据库中已有的:
更新 LSDB
向所有接口（除了收到 LSA 的接口）转发该 LSA
发送 LSAck 确认
elif LSA 序列号 == 已有的:
发送 LSAck（去重）
else:
丢弃（旧的）数据库同步
当两台路由器建立邻接关系时，需要同步各自的 LSDB。这通过 Database Description（DD）报文交换实现：
1. 建立邻接：Hello -> 2-Way -> ExStart -> Exchange -> Loading -> Full
2. ExStart: 协商主从关系和初始序列号
3. Exchange: 交换 DD 报文（LSDB 摘要）
4. Loading: 请求缺失的 LSA
5. Full: 数据库同步完成LS 算法的优势
相比 DV，LS 的优势明显：无计数到无穷（独立计算，无信息回环）、收敛快（一次 LSA 洪泛 + 一次 SPF）、路由一致性（基于相同 LSDB）。代价是更高的内存占用和计算开销。
五、OSPF 详解：区域、LSA 类型与路由汇总
开放最短路径优先（OSPF, Open Shortest Path First）是最广泛使用的链路状态 IGP。当前版本是 OSPFv2（RFC 2328，IPv4）和 OSPFv3（RFC 5340，IPv6）。
区域设计
OSPF 引入区域（Area）划分来解决可扩展性。LSA 洪泛被限制在区域内部，大幅减少 LSDB 大小和 SPF 计算开销。所有区域必须直接或通过虚链路连接到 Area 0（骨干区域）。
区域类型
OSPF 定义了多种区域类型来控制 LSA 的传播范围：
区域类型 | 允许的 LSA 类型 | 外部路由处理 | 使用场景
----------------|---------------------|--------------------|-----------------
普通区域 | 1, 2, 3, 4, 5 | 完整接收 | 默认
Stub 区域 | 1, 2, 3 | 默认路由替代 | 末端区域
Totally Stubby | 1, 2 | 默认路由替代 | 更精简的末端区域
NSSA | 1, 2, 3, 7 | Type-7 LSA 转换 | 需要引入外部路由的末端区域
Totally NSSA | 1, 2, 7 | 默认路由 + Type-7 | 最精简但保留外部引入LSA 类型
OSPF 定义了多种 LSA 类型，每种承载不同的路由信息：
Type | 名称 | 发起者 | 洪泛范围 | 内容
-----|----------------------|--------|----------|---------------------------
1 | Router LSA | 所有路由器 | 区域内 | 路由器的直连链路和邻居
2 | Network LSA | DR | 区域内 | 多路访问网络上的路由器列表
3 | Summary LSA (Network)| ABR | 跨区域 | 域间网络路由
4 | Summary LSA (ASBR) | ABR | 跨区域 | ASBR 的位置
5 | AS External LSA | ASBR | 整个 AS | 外部路由（重分发）
7 | NSSA External LSA | ASBR | NSSA 内 | NSSA 区域内的外部路由虚链路（Virtual Link）
当一个区域无法直连 Area 0 时，可通过虚链路穿越中转区域建立逻辑连接。虚链路应视为临时方案，良好的网络设计应避免使用。
路由汇总（Route Summarization）
路由汇总是 OSPF 可扩展性的关键。ABR 可以将多条明细路由聚合为一条汇总路由，同时隐藏区域内部拓扑变化：
Area 1 中有：
10.1.1.0/24
10.1.2.0/24
10.1.3.0/24
10.1.4.0/24
ABR 汇总后向 Area 0 通告：
10.1.0.0/22
效果：Area 0 的 LSDB 中只有 1 条 Type-3 LSA 而非 4 条OSPF 的开销计算
OSPF 的链路开销（Cost）默认基于接口带宽：
Cost = Reference Bandwidth / Interface Bandwidth
默认参考带宽 = 100 Mbps
接口类型 | 带宽 | 默认 Cost
-------------|-----------|----------
FastEthernet | 100 Mbps | 1
GigabitEth | 1 Gbps | 1 (需调参考带宽!)
10 GigabitEth| 10 Gbps | 1 (需调参考带宽!)
Serial | 1.544 Mbps| 64
建议：将参考带宽设为 100 Gbps 以区分高速链路
router ospf 1
auto-cost reference-bandwidth 100000六、路径向量算法：BGP 与策略路由
域内路由追求最短路径，但域间路由面对的是完全不同的问题：自治系统之间的路由选择主要由商业策略驱动，而非最短路径。
为什么需要路径向量？
距离向量和链路状态在域间路由中都不适用：DV 的计数到无穷在 7 万+ AS 的规模下不可接受，LS 要求暴露全局拓扑而 AS 之间不愿意这样做，域间路由更需要基于商业关系的策略控制。路径向量（Path Vector）是 DV 的演进，关键改进是每条路由携带完整的 AS 路径。
BGP 基础
边界网关协议（BGP, Border Gateway Protocol）是唯一的域间路由协议，当前版本 BGP-4（RFC 4271）。BGP 是一种路径向量协议。
BGP 消息类型：
OPEN - 建立对等关系
UPDATE - 通告新路由或撤销旧路由
KEEPALIVE - 维持会话（默认 60 秒）
NOTIFICATION - 错误通知并关闭会话
ROUTE-REFRESH - 请求重新发送路由（RFC 2918）BGP 使用 TCP 端口 179 建立对等连接（OSPF 使用 IP 协议号 89），因此不需要自己处理可靠传输和分片重组。
AS_PATH 与环路防止
AS_PATH 是 BGP 最重要的属性之一。当一条路由从一个 AS 传播到另一个 AS 时，传播者将自己的 AS 号追加到 AS_PATH 中。
AS 65001 发起前缀 10.0.0.0/8：
AS_PATH = [65001]
传播到 AS 65002：
AS_PATH = [65002, 65001]
传播到 AS 65003：
AS_PATH = [65003, 65002, 65001]
当 AS 65001 收到这条路由时：
发现自己的 AS 号在 AS_PATH 中 -> 丢弃（环路检测）这种机制简单而优雅地解决了环路问题，完全不需要 DV 那些复杂的补丁。
iBGP 与 eBGP
BGP 有两种模式：
eBGP (External BGP)：不同 AS 之间的 BGP 对等
- AS_PATH 会追加本地 AS 号
- 默认 TTL = 1（直连邻居）
- 管理距离 = 20
iBGP (Internal BGP)：同一 AS 内部的 BGP 对等
- AS_PATH 不变
- 默认 TTL = 255
- 管理距离 = 200
- 需要全互联（Full Mesh）或路由反射器iBGP 的全互联要求在大型 AS 中不可扩展。解决方案：路由反射器（指定少数路由器作为反射器）或 BGP 联盟（AS 内部划分子 AS）。
七、BGP 决策过程：13 步最佳路径选择
当 BGP 路由器对同一前缀收到多条候选路径时，需要通过一套严格的决策过程选出最佳路径。以下是标准的 BGP 最佳路径选择算法（以 Cisco IOS 为参考）：
步骤 | 属性 | 优先级 | 说明
-----|----------------------|--------|----------------------------------
1 | Weight | 最大 | Cisco 专有，本地有效
2 | LOCAL_PREF | 最大 | 本 AS 内统一的优先级
3 | Locally originated | 优先 | 本地发起的路由优于学到的
4 | AS_PATH length | 最短 | 经过的 AS 数量最少
5 | Origin type | IGP>EGP>? | IGP 优于 EGP 优于 incomplete
6 | MED | 最小 | 影响入站流量的度量
7 | eBGP over iBGP | 优先 | eBGP 学到的优于 iBGP 学到的
8 | IGP metric to next-hop| 最小 | 最近的出口（热土豆路由）
9 | Oldest route | 优先 | 更稳定的路由
10 | Router ID | 最小 | 打破平局
11 | Cluster List length | 最短 | 路由反射器相关
12 | Neighbor IP | 最小 | 最终打破平局
13 | (Multipath) | -- | 等价多路径选择LOCAL_PREF：域内策略的主要工具
LOCAL_PREF 是 iBGP 中传播的属性，默认值 100，值越大越优先。运营商用它实现基本的路由策略：
典型 LOCAL_PREF 策略：
Customer routes: LP = 150 （最优先，客户付费给我们）
Peer routes: LP = 100 （对等交换）
Provider routes: LP = 80 （最不优先，我们付费给提供商）
效果：流量优先走客户路径（我们收费），其次对等（免费），最后才走提供商（我们付费）MED：影响入站流量
MED（Multi-Exit Discriminator）用于向邻居 AS 建议从哪个入口点进入本 AS。MED 值越小越优先。
AS 65001 有两个连接到 AS 65002：
链路 A：MED = 100 （高速链路）
链路 B：MED = 200 （备份链路）
AS 65002 收到相同前缀从两个链路传来，会优先选择 MED = 100 的链路 A但 MED 只是一个”建议”，邻居 AS 可以完全忽略。默认情况下 MED 只在来自同一邻居 AS 的路由之间比较。
BGP Communities：灵活的标签系统
BGP Community 是一个 32 位标签，可以附加在路由上用于策略传递：
标准 Community 格式：AS:Value
知名 Community：
NO_EXPORT (0xFFFFFF01) - 不向 eBGP 邻居通告
NO_ADVERTISE (0xFFFFFF02) - 不向任何邻居通告
NO_EXPORT_SUBCONFED - 不出联盟
自定义 Community 示例：
65001:100 - 标记为客户路由
65001:200 - 标记为对等路由
65001:666 - 黑洞路由（触发 RTBH）
65001:1000 - 请求将 LOCAL_PREF 设为 1000Extended Community 和 Large Community（RFC 8092）进一步扩展了标签空间。 ## 八、数据中心路由：Clos 拓扑与 DC 中的 BGP
现代超大规模数据中心已经形成了独特的路由架构。
Clos 拓扑
数据中心普遍采用 Clos（胖树）拓扑，通常是 3 层或 5 层结构：
3 层 Clos 拓扑：
Spine 1 Spine 2 Spine 3 Spine 4
| \ X / | \ X / |
| \/ / | \/ / |
| /\ / | /\ / |
| / X \ | / X \ |
Leaf 1 Leaf 2 Leaf 3 Leaf 4
| | | |
+---+ +---+ +---+ +---+
|Srv| |Srv| |Srv| |Srv|
+---+ +---+ +---+ +---+
特点：
- 每个 Leaf 连接到所有 Spine
- 任意两个 Leaf 之间恰好 2 跳
- 东西向带宽 = Spine 数量 * 单链路带宽
- 天然支持 ECMP为什么数据中心使用 BGP
RFC 7938（Use of BGP for Routing in Large-Scale Data Centers）描述了在数据中心使用 BGP 的方案。选择 BGP 而非 OSPF 的原因：无需区域规划（每台交换机一个 AS）、策略灵活、BFD + BGP 实现亚秒级故障检测、BGP Multipath + ECMP、域内域间统一协议栈。
ECMP（等价多路径）
Clos 拓扑的核心优势是天然支持 ECMP。从任意 Leaf 到另一个 Leaf，存在与 Spine 数量相同的等价路径，负载均衡通常基于 5-tuple hash。
数据中心 BGP 设计
典型的 DC BGP 设计采用 eBGP，每台 Spine 和 Leaf 分配独立的私有 ASN。关键配置要点：BFD 实现 <50ms 故障检测、maximum-paths 设为 Spine 数量、peer-group 简化配置、route-map 过滤不期望的路由。
与传统 DC 的对比
特性 | 传统 DC (STP+OSPF) | 现代 DC (Clos+BGP)
------------|---------------------|---------------------
冗余利用 | STP 阻塞 50% | ECMP 利用所有路径
东西向带宽 | 受限于汇聚层 | 线性扩展
收敛时间 | STP: 30-50s | BFD+BGP: <1s
可扩展性 | 数百台 | 数万台九、完整 C 实现：Dijkstra SPF 与距离向量模拟器
Dijkstra SPF 实现
以下是完整的 Dijkstra 最短路径算法 C 实现，使用邻接表和最小堆：
/*
* dijkstra_spf.c - Dijkstra Shortest Path First implementation
* 使用二叉最小堆优先队列
* 编译：gcc -O2 -o dijkstra dijkstra_spf.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_NODES 256
#define MAX_EDGES 2048
#define INF INT_MAX
/* ---- 图结构 ---- */
typedef struct edge {
int to;
int cost;
struct edge *next;
} Edge;
typedef struct {
Edge *head[MAX_NODES];
int n; /* 节点数 */
} Graph;
void graph_init(Graph *g, int n)
{
g->n = n;
memset(g->head, 0, sizeof(g->head));
}
void graph_add_edge(Graph *g, int from, int to, int cost)
{
Edge *e = (Edge *)malloc(sizeof(Edge));
e->to = to;
e->cost = cost;
e->next = g->head[from];
g->head[from] = e;
}
void graph_add_bidi(Graph *g, int u, int v, int cost)
{
graph_add_edge(g, u, v, cost);
graph_add_edge(g, v, u, cost);
}
/* ---- 最小堆优先队列 ---- */
typedef struct {
int node;
int dist;
} HeapItem;
typedef struct {
HeapItem items[MAX_NODES];
int pos[MAX_NODES]; /* node -> heap position */
int size;
} MinHeap;
void heap_init(MinHeap *h)
{
h->size = 0;
memset(h->pos, -1, sizeof(h->pos));
}
static void heap_swap(MinHeap *h, int i, int j)
{
HeapItem tmp = h->items[i];
h->items[i] = h->items[j];
h->items[j] = tmp;
h->pos[h->items[i].node] = i;
h->pos[h->items[j].node] = j;
}
static void heap_sift_up(MinHeap *h, int i)
{
while (i > 0) {
int parent = (i - 1) / 2;
if (h->items[i].dist < h->items[parent].dist) {
heap_swap(h, i, parent);
i = parent;
} else {
break;
}
}
}
static void heap_sift_down(MinHeap *h, int i)
{
while (1) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < h->size && h->items[left].dist < h->items[smallest].dist)
smallest = left;
if (right < h->size && h->items[right].dist < h->items[smallest].dist)
smallest = right;
if (smallest != i) {
heap_swap(h, i, smallest);
i = smallest;
} else {
break;
}
}
}
void heap_push(MinHeap *h, int node, int dist)
{
int i = h->size++;
h->items[i].node = node;
h->items[i].dist = dist;
h->pos[node] = i;
heap_sift_up(h, i);
}
HeapItem heap_pop(MinHeap *h)
{
HeapItem top = h->items[0];
h->pos[top.node] = -1;
h->size--;
if (h->size > 0) {
h->items[0] = h->items[h->size];
h->pos[h->items[0].node] = 0;
heap_sift_down(h, 0);
}
return top;
}
void heap_decrease_key(MinHeap *h, int node, int new_dist)
{
int i = h->pos[node];
if (i < 0 || i >= h->size) return;
if (new_dist < h->items[i].dist) {
h->items[i].dist = new_dist;
heap_sift_up(h, i);
}
}
/* ---- Dijkstra SPF ---- */
typedef struct {
int dist[MAX_NODES];
int prev[MAX_NODES];
int visited[MAX_NODES];
} SPFResult;
void dijkstra(Graph *g, int src, SPFResult *r)
{
MinHeap heap;
heap_init(&heap);
for (int i = 0; i < g->n; i++) {
r->dist[i] = INF;
r->prev[i] = -1;
r->visited[i] = 0;
}
r->dist[src] = 0;
for (int i = 0; i < g->n; i++)
heap_push(&heap, i, r->dist[i]);
while (heap.size > 0) {
HeapItem u = heap_pop(&heap);
if (u.dist == INF) break;
r->visited[u.node] = 1;
for (Edge *e = g->head[u.node]; e; e = e->next) {
if (r->visited[e->to]) continue;
int alt = u.dist + e->cost;
if (alt < r->dist[e->to]) {
r->dist[e->to] = alt;
r->prev[e->to] = u.node;
heap_decrease_key(&heap, e->to, alt);
}
}
}
}
/* ---- 路径回溯打印 ---- */
void print_path(SPFResult *r, int src, int dst)
{
if (dst == src) {
printf("%d", src);
return;
}
if (r->prev[dst] == -1) {
printf("(unreachable)");
return;
}
print_path(r, src, r->prev[dst]);
printf(" -> %d", dst);
}
/* ---- 路由表打印 ---- */
void print_routing_table(Graph *g, int src, SPFResult *r)
{
printf("\n=== SPF Routing Table (source = %d) ===\n", src);
printf("%-8s %-8s %-10s %s\n", "Dest", "Cost", "NextHop", "Path");
printf("----------------------------------------------\n");
for (int d = 0; d < g->n; d++) {
if (d == src) continue;
printf("%-8d ", d);
if (r->dist[d] == INF) {
printf("INF -- (unreachable)\n");
continue;
}
/* 找第一跳 */
int next = d;
while (r->prev[next] != src && r->prev[next] != -1)
next = r->prev[next];
printf("%-8d %-10d ", r->dist[d], next);
print_path(r, src, d);
printf("\n");
}
}
/* ---- 释放图内存 ---- */
void graph_free(Graph *g)
{
for (int i = 0; i < g->n; i++) {
Edge *e = g->head[i];
while (e) {
Edge *tmp = e;
e = e->next;
free(tmp);
}
}
}
/* ---- 测试：模拟小型 OSPF 网络 ---- */
int main(void)
{
/* 0 ---10--- 1 ---5--- 2
* | | |
* 3 20 8
* | | |
* 3 ---15--- 4 ---2--- 5 */
Graph g;
graph_init(&g, 6);
graph_add_bidi(&g, 0, 1, 10); graph_add_bidi(&g, 1, 2, 5);
graph_add_bidi(&g, 0, 3, 3); graph_add_bidi(&g, 1, 4, 20);
graph_add_bidi(&g, 2, 5, 8); graph_add_bidi(&g, 3, 4, 15);
graph_add_bidi(&g, 4, 5, 2);
SPFResult result;
printf("Dijkstra SPF - OSPF Shortest Path Simulation\n");
dijkstra(&g, 0, &result);
print_routing_table(&g, 0, &result);
/* 模拟链路故障：断开 0-1 链路 */
printf("\n*** Link 0-1 failed! Recalculating... ***\n");
for (Edge *e = g.head[0]; e; e = e->next)
if (e->to == 1) e->cost = INF;
for (Edge *e = g.head[1]; e; e = e->next)
if (e->to == 0) e->cost = INF;
dijkstra(&g, 0, &result);
print_routing_table(&g, 0, &result);
graph_free(&g);
return 0;
}距离向量模拟器
以下是完整的距离向量路由模拟器，实现 Bellman-Ford 迭代、水平分割和毒性反转：
/*
* dv_simulator.c - Distance Vector routing simulator
* 实现 Bellman-Ford 迭代，支持水平分割和毒性反转
* 编译：gcc -O2 -o dvsim dv_simulator.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_NODES 16
#define MAX_NEIGHBORS 8
#define INF 9999
/* 距离向量条目 */
typedef struct {
int cost;
int next_hop;
} DVEntry;
/* 邻居信息 */
typedef struct {
int id;
int link_cost;
} Neighbor;
/* 路由器 */
typedef struct {
int id;
DVEntry table[MAX_NODES]; /* 距离向量表 */
DVEntry new_table[MAX_NODES]; /* 计算中的新表 */
Neighbor neighbors[MAX_NEIGHBORS];
int num_neighbors;
int changed; /* 本轮是否有变化 */
} Router;
typedef struct {
Router routers[MAX_NODES];
int num_nodes;
int split_horizon;
int poison_reverse;
} Network;
/* 初始化网络 */
void net_init(Network *net, int n, int sh, int pr)
{
net->num_nodes = n;
net->split_horizon = sh;
net->poison_reverse = pr;
for (int i = 0; i < n; i++) {
Router *r = &net->routers[i];
r->id = i;
r->num_neighbors = 0;
r->changed = 0;
for (int j = 0; j < n; j++) {
r->table[j].cost = (i == j) ? 0 : INF;
r->table[j].next_hop = (i == j) ? i : -1;
}
}
}
/* 添加双向链路 */
void net_add_link(Network *net, int u, int v, int cost)
{
Router *ru = &net->routers[u];
Router *rv = &net->routers[v];
ru->neighbors[ru->num_neighbors].id = v;
ru->neighbors[ru->num_neighbors].link_cost = cost;
ru->num_neighbors++;
ru->table[v].cost = cost;
ru->table[v].next_hop = v;
rv->neighbors[rv->num_neighbors].id = u;
rv->neighbors[rv->num_neighbors].link_cost = cost;
rv->num_neighbors++;
rv->table[u].cost = cost;
rv->table[u].next_hop = u;
}
/* 获取节点 src 向邻居 nbr 通告的到 dest 的距离 */
int get_advertised_cost(Network *net, int src, int nbr, int dest)
{
Router *r = &net->routers[src];
int actual_cost = r->table[dest].cost;
int via = r->table[dest].next_hop;
if (net->poison_reverse && via == nbr && dest != src) {
return INF; /* 毒性反转：从 nbr 学到的路由，告诉 nbr 是 INF */
}
if (net->split_horizon && via == nbr && dest != src) {
return INF; /* 水平分割：不通告从 nbr 学到的路由 */
}
return actual_cost;
}
/* 执行一轮 Bellman-Ford 迭代 */
int dv_iterate(Network *net)
{
int global_changed = 0;
for (int i = 0; i < net->num_nodes; i++) {
Router *r = &net->routers[i];
r->changed = 0;
memcpy(r->new_table, r->table, sizeof(r->table));
for (int dest = 0; dest < net->num_nodes; dest++) {
if (dest == i) continue;
int best_cost = INF;
int best_hop = -1;
/* 检查所有邻居 */
for (int n = 0; n < r->num_neighbors; n++) {
int nbr_id = r->neighbors[n].id;
int link_cost = r->neighbors[n].link_cost;
/* 邻居声称的到 dest 的距离 */
int nbr_cost = get_advertised_cost(net, nbr_id, i, dest);
if (nbr_cost == INF || link_cost == INF) continue;
int total = link_cost + nbr_cost;
if (total < best_cost) {
best_cost = total;
best_hop = nbr_id;
}
}
if (best_cost != r->new_table[dest].cost ||
best_hop != r->new_table[dest].next_hop) {
r->new_table[dest].cost = best_cost;
r->new_table[dest].next_hop = best_hop;
r->changed = 1;
}
}
}
/* 提交新表 */
for (int i = 0; i < net->num_nodes; i++) {
Router *r = &net->routers[i];
if (r->changed) {
memcpy(r->table, r->new_table, sizeof(r->table));
global_changed = 1;
}
}
return global_changed;
}
/* 打印所有路由表 */
void net_print_tables(Network *net)
{
for (int i = 0; i < net->num_nodes; i++) {
Router *r = &net->routers[i];
printf(" Router %d: ", i);
for (int d = 0; d < net->num_nodes; d++) {
if (d == i) continue;
if (r->table[d].cost >= INF) printf("[%d:INF] ", d);
else printf("[%d:%d via %d] ", d, r->table[d].cost, r->table[d].next_hop);
}
printf("\n");
}
}
/* 模拟链路故障 */
void net_fail_link(Network *net, int u, int v)
{
for (int i = 0; i < net->routers[u].num_neighbors; i++)
if (net->routers[u].neighbors[i].id == v)
{ net->routers[u].neighbors[i].link_cost = INF; break; }
for (int i = 0; i < net->routers[v].num_neighbors; i++)
if (net->routers[v].neighbors[i].id == u)
{ net->routers[v].neighbors[i].link_cost = INF; break; }
net->routers[u].table[v].cost = INF;
net->routers[u].table[v].next_hop = -1;
net->routers[v].table[u].cost = INF;
net->routers[v].table[u].next_hop = -1;
}
void run_simulation(const char *label, int sh, int pr)
{
printf("\n=== %s (SH:%s PR:%s) ===\n", label, sh?"ON":"OFF", pr?"ON":"OFF");
Network net;
net_init(&net, 3, sh, pr); /* A(0) --1-- B(1) --1-- C(2) */
net_add_link(&net, 0, 1, 1);
net_add_link(&net, 1, 2, 1);
printf("--- Initial convergence ---\n");
int round = 0;
while (dv_iterate(&net)) { printf("Round %d:\n", ++round); net_print_tables(&net); }
printf("Converged in %d rounds.\n", round);
printf("--- Link B(1)-C(2) failed ---\n");
net_fail_link(&net, 1, 2);
round = 0;
int max_rounds = 25;
while (dv_iterate(&net) && round < max_rounds) { printf("Round %d:\n", ++round); net_print_tables(&net); }
if (round >= max_rounds) printf("*** Count-to-infinity: no convergence in %d rounds ***\n", max_rounds);
else printf("Converged in %d rounds after failure.\n", round);
}
int main(void)
{
run_simulation("Plain Bellman-Ford", 0, 0);
run_simulation("Split Horizon", 1, 0);
run_simulation("Poison Reverse", 0, 1);
return 0;
}编译和运行
# 编译
gcc -O2 -Wall -o dijkstra dijkstra_spf.c
gcc -O2 -Wall -o dvsim dv_simulator.c
# 运行
./dijkstra
./dvsim十、Segment Routing：从 MPLS 到 SRv6
传统路由协议确定了转发路径后，报文只能沿着最短路径走。流量工程（Traffic Engineering, TE）需要让流量走非最短路径，这就需要额外的机制。
MPLS 时代
多协议标签交换（MPLS）通过在 IP 报文前插入标签来实现快速转发和流量工程。但 MPLS TE 的问题在于状态爆炸：每条 LSP 都是软状态，中间节点需要维护所有穿越的 LSP。
Segment Routing（SR）
Segment Routing 的核心思想是：将路径编码在报文头中，中间节点不需要维护任何逐流状态。
SR 中的 Segment 类型：
Prefix SID：目标是一个前缀（全局唯一）
Adjacency SID：目标是一条特定链路（本地有效）
Service SID：目标是一个服务功能
示例：从 A 到 D，强制经过 B-C 链路
普通最短路径：A -> E -> D
SR 路径：A 在报文中编码 [Adj(B-C), Prefix(D)]
转发过程：
A: 查看 segment list，推送到 B
B: 弹出 Adj(B-C)，转发到 C
C: 查看 Prefix(D)，按最短路径转发到 DSR-MPLS vs SRv6
Segment Routing 有两种数据平面实现：
特性 | SR-MPLS | SRv6
----------------|------------------------|---------------------------
封装 | MPLS 标签栈 | IPv6 扩展头（SRH）
Segment 标识 | 20-bit MPLS 标签 | 128-bit IPv6 地址
需要 MPLS 基础设施| 是 | 否（原生 IPv6）
网络编程 | 有限 | 丰富（SRv6 Network Programming）
MTU 影响 | 每个 segment 4 字节 | 每个 segment 16 字节
运营商采用 | 广泛 | 快速增长SRv6 Network Programming
SRv6 的一个独特优势是网络编程能力。通过定义不同的 Endpoint Behavior（RFC 8986），可以实现丰富的功能：
SRv6 Behavior | 功能
--------------------|------------------------------------------
End | 普通 SRv6 endpoint
End.X | 指定出接口（类似 Adjacency SID）
End.DT4 / End.DT6 | 解封装并查 IPv4/IPv6 路由表（VPN）
End.DX4 | 解封装并转发到指定 IPv4 邻居
End.B6.Encaps | 插入 SRv6 封装（流量工程）
SRv6 SID 结构：|<-- Locator(/48) -->|<-- Function(16b) -->|<-- Args -->|流量工程应用
SR 使得流量工程从逐跳信令变为头端编码：控制器计算路径，头端编码 segment list，中间节点零状态，故障时头端直接更新 segment list。
十一、真实世界：路由表增长、BGP 劫持与 RPKI
互联网路由表增长
全球 BGP 路由表的增长是互联网面临的长期挑战之一。
年份 | IPv4 前缀数 | IPv6 前缀数 | 主要驱动因素
---------|---------------|--------------|--------------------
2000 | ~80,000 | ~100 | 互联网商业化
2005 | ~170,000 | ~1,000 | 地址碎片化
2010 | ~340,000 | ~5,000 | 多宿主增长
2015 | ~580,000 | ~25,000 | 移动互联网
2020 | ~850,000 | ~100,000 | 云计算/CDN
2025 | ~1,000,000 | ~220,000 | IPv6 部署加速
路由表增长的影响：
- TCAM（三态内容寻址存储器）容量压力
- FIB 更新速率增加
- BGP 收敛时间延长
- 设备成本上升BGP 劫持
BGP 的设计基于信任：路由器默认相信邻居通告的路由。这导致了 BGP 劫持成为互联网安全的重大威胁。常见的劫持方式包括：前缀劫持（通告不属于自己的前缀）、子前缀劫持（通告更具体的子前缀以获得优先选择）、AS_PATH 操纵（伪造更短路径）。
著名事件： - 2008 年：巴基斯坦电信劫持 YouTube 前缀（国内封锁泄露到全球） - 2018 年：Rostelecom 劫持多家金融机构流量 - 2019 年：多次大规模路由泄露事件
### RPKI：资源公钥基础设施
RPKI（Resource Public Key Infrastructure）是目前最有前途的 BGP 安全解决方案。
```text
RPKI 组件：
1. ROA（Route Origin Authorization）：
- 由前缀持有者签发
- 声明哪个 AS 被授权发起哪个前缀
- 格式：(前缀, 最大前缀长度, 授权 AS)
2. 验证结果：
Valid - ROA 存在且匹配
Invalid - ROA 存在但不匹配（可能是劫持）
NotFound - 没有 ROA（无法判断）
3. 路由过滤策略：
Valid -> Accept
Invalid -> Drop (ROV - Route Origin Validation)
NotFound -> Accept (目前大多数运营商的做法)
RPKI 部署现状（2025 年）：
- 全球约 50% 的前缀有 ROA 签名
- 主要运营商和 IXP 已部署 ROV
- NIST RPKI Monitor 提供实时监控
- 仍在快速推进中BGPsec
RPKI 只能验证路由起源，不能防止 AS_PATH 操纵。BGPsec（RFC 8205）旨在验证整条 AS_PATH 的真实性，但由于每次通告都需加密签名、需要全路径 AS 都支持、破坏增量部署模型等原因，实际部署几乎为零。
十二、工程陷阱表与个人观点
常见工程陷阱
陷阱 | 后果 | 建议
---------------------------|------------------------|-----------------------------
OSPF 参考带宽未调整 | 1G 和 10G 链路同 cost | 设为 100G 或更高
OSPF Area 0 不连通 | 域间路由黑洞 | 检查骨干连通性，慎用虚链路
iBGP 未全互联且无 RR | 路由黑洞 | 部署路由反射器或联盟
BGP next-hop-self 遗漏 | iBGP 学到的路由不可达 | eBGP 邻居设 next-hop-self
MED 跨 AS 比较 | 次优路径选择 | 明确 bgp always-compare-med
BGP 最大前缀数未设 | 邻居泄露全表撑爆内存 | 设置 maximum-prefix
BFD 未部署 | 故障检测依赖 Hold Timer | 生产环境必开 BFD
ECMP 哈希极化 | 流量不均衡 | 检查哈希算法和种子
OSPF MTU 不匹配 | 邻接卡在 ExStart | 统一 MTU 或 ip ospf mtu-ignore
路由汇总遗漏 null route | 次优路由或环路 | 汇总时始终配黑洞路由
eBGP 未设 TTL security | TTL 欺骗攻击 | 配置 ttl-security hops 1
RPKI invalid 路由未过滤 | 接受被劫持的路由 | 部署 ROV，drop invalid协议选型决策树
你的场景是？
|
+-- 单个数据中心内部
| +-- 规模 < 50 台 -> OSPF 单区域
| +-- 规模 50-500 台 -> OSPF 多区域 或 IS-IS
| +-- 规模 > 500 台 -> eBGP (RFC 7938 风格)
|
+-- 企业多站点
| +-- WAN 互联 -> OSPF + BGP（OSPF 做 IGP，BGP 做 VPN overlay）
| +-- SD-WAN -> 可能不需要传统路由协议
|
+-- 运营商骨干
| +-- IGP: IS-IS（大多数 Tier-1 的选择）
| +-- iBGP: 路由反射器 + 全互联 RR 层
| +-- TE: SR-MPLS 或 SRv6
|
+-- 云/CDN
+-- 自有骨干: 类似运营商
+-- DC 内部: eBGP Clos
+-- 对外: BGP 多宿主个人观点
关于 OSPF vs IS-IS：企业环境选 OSPF（工程师熟悉、调试工具丰富）。运营商和超大规模选 IS-IS：运行在二层之上不依赖 IP，TLV 结构天然可扩展，在 Segment Routing 生态中支持更好。
关于 BGP 在数据中心：RFC 7938 方案优雅，但每台交换机一个 AS 号意味着成百上千个 BGP 会话。没有强大的自动化平台（Ansible、Nornir 或自研系统），这个方案很难运维。
关于 SRv6：网络编程理念很有吸引力，但 128-bit SID 的 MTU 开销是实际工程问题。uSID 方案通过将多个 micro-SID 编码进一个 128-bit container 来缓解，但增加了复杂度。
关于路由安全：RPKI ROV 是当前互联网安全最重要的进展之一。但”NotFound = Accept”意味着只要足够多前缀没有 ROA，攻击者就有操作空间。如果你管理的前缀还没有 ROA，现在就去签发。
关于未来：长期趋势是 SDN 控制器计算路径、SR 数据平面执行。但”纯集中式”永远不会完全取代”分布式”——控制器本身也需要分区容错。最终形态更可能是”集中计算 + 分布式兜底”的混合架构。
推荐阅读
书籍：
- "Internet Routing Architectures" - Sam Halabi
- "OSPF: Anatomy of an Internet Routing Protocol" - John T. Moy
- "Segment Routing Part I/II" - Clarence Filsfils et al.
RFC：
RFC 2328 (OSPFv2), RFC 4271 (BGP-4), RFC 7938 (DC BGP),
RFC 8402 (SR Architecture), RFC 8986 (SRv6), RFC 6480 (RPKI)