路由算法（距离向量、链路状态）

路由器——互联网的”指路人”

你的电脑想把数据发给 Google 的服务器，中间要经过十几台路由器。每台路由器必须做出一个关键决定：下一步往哪走？

你的电脑 → 宿舍路由器 → 校园网路由器 → 电信骨干 → ... → Google

🏫 类比：高速公路导航 你开车从广州去北京（你的电脑→Google 服务器）：

• 到了广州收费站（路由器 A），你不可能知道全程路线
• 但你知道”上京港澳高速”（路由表告诉你：去北京往北走）
• 到了长沙收费站（路由器 B），你也只需要知道”继续往北”
• 每个收费站只知道下一段路怎么走——不需要知道全程

关键思想：每台路由器不需要知道去全世界所有网络的完整路径——只需要知道”下一跳”往哪个方向。

距离向量算法（Distance Vector）——“邻居之间互相传话”

基本原则： 每个路由器定期把自己的路由表复制一份发给邻居。邻居收到后，检查”经过你能不能到某些网络”——如果能，且距离更短，就更新路由表。

路由器 A 的路由表         路由器 B 的路由表        路由器 C 的路由表
┌────────┬────┬────┐    ┌────────┬────┬────┐    ┌────────┬────┬────┐
│ 目标   │距离│下一跳│    │ 目标   │距离│下一跳│    │ 目标   │距离│下一跳│
├────────┼────┼────┤    ├────────┼────┼────┤    ├────────┼────┼────┤
│ Net-1  │ 0  │ 直接│    │ Net-1  │ 1  │ A  │    │ Net-1  │ 2  │ B  │
│ Net-2  │ 1  │ B  │    │ Net-2  │ 0  │ 直接│    │ Net-2  │ 1  │ B  │
│        │    │    │    │ Net-3  │ 1  │ C  │    │ Net-3  │ 0  │ 直接│
└────────┴────┴────┘    └────────┴────┴────┘    └────────┴────┴────┘

优点： 实现简单，每台路由器只需要和邻居通信

缺点——致命的收敛慢： 当网络拓扑变化时（比如一条链路断了），错误信息会在路由器之间”传染”——距离值慢慢增大到无穷大，这个过程需要很多轮。

⚠️ 计数到无穷（Count-to-Infinity）问题 A 和 B 之间的链路断了。A 把这条路由的距离改成无穷大（通常 16 跳=RIP 认为不可达）。但 B 还没来得及更新，它告诉 A：“我能到那个网络，距离 2”。A 就以为经过 B 可以去那个网络，更新距离为 3……B 又从 A 学到距离 3，更新为 4……两个路由器互相骗，距离数一直涨到 16 才停下。

🏫 类比：两个路痴互相指路 我：“去北京怎么走？” 你：“我不知道”（断开） 我：“他可能知道” → 继续问 你：“走我这边！（其实我也不知道）” → 错误信息传播

代表协议：RIP（Routing Information Protocol）

• 跳数限制 15 跳（超过 15 认为不可达）
• 每 30 秒广播一次完整路由表
• 适用于小型网络

链路状态算法（Link State）——每个人手里都有一张地图

链路状态的思路完全不同：每台路由器把自己和谁连着的”地图”广播给所有路由器——最后每台路由器都有全网的完整拓扑图，自己用 Dijkstra 算法算最短路径。

链路状态算法的五个步骤：
① 发现邻居——每台路由器找到直连的邻居
② 测量代价——到每个邻居的"距离"（通常是带宽/延迟）
③ 构建 LSP（Link State Packet）——描述自己连了哪些邻居
④ 泛洪 LSP——把自己的 LSP 发给网络中的所有路由器
⑤ 每台路由器现在都有全网拓扑图 → 用 Dijkstra 算出最短路径树

🏫 类比：全班画地图

• 距离向量：A 告诉 B”我知道怎么去食堂”，B 告诉 C……传话可能有误
• 链路状态：每个人自己画一张学校地图（A 画自己周围，B 画自己周围……拼起来），然后自己算最短路径——信息准确、计算独立

代表协议：OSPF（Open Shortest Path First）

• 基于 Dijkstra 算法
• 收敛快（秒级）
• 支持分层——大网络分成多个区域减少计算量

三大路由协议对比

协议	算法	度量	收敛	规模	一句话
RIP	距离向量	跳数	慢（分钟级）	小（15跳）	“邻居告诉我怎么走”
OSPF	链路状态	带宽	快（秒级）	大（企业骨干）	“我有全图，自己算”
BGP	路径向量	多种策略	较慢	全球互联网	”我不仅要快，还要看政策”

BGP——互联网的”外交官”

BGP（Border Gateway Protocol） 是互联网不同运营商之间的路由协议。它不像 OSPF 那样找”最短路径”——而是根据商业策略选择路径。

AS 100（中国电信）─── AS 200（中国联通）   ←  AS = 自治系统
         │                  │               （一个运营商）
         └── AS 300（腾讯）──┘

BGP 的策略选择通常考虑：

• 商业关系： 客户付了钱，可以走提供商的链路；对等互联不花钱，只交换自己客户的路由
• 政策： 某些国家的流量不能经过某些国家的网络
• 路径长度： AS PATH 越短越好

# 查看 BGP 路由表
$ bgproute 8.8.8.0/24
BGP routing table entry for 8.8.8.0/24
Paths: (4 available, best #2)
  Not advertised to any peer
  Refresh Epoch 1
  15169 15169 15169         ← AS PATH
    192.168.1.1 from 0.0.0.0 (192.168.1.1)
      Origin IGP, metric 0, localpref 100, valid, internal, best

💡 BGP 为什么叫”路径向量”？ 它和距离向量一样从邻居学路由，但不只是”距离”——它把经过的 AS 列表（AS PATH）也传给你，防止环路。就像快递单上盖的章：北京→上海→广州，每个中转站盖一个章，如果又回到北京——说明出环了。

小结

概念	要点	一句话
路由	数据包经过哪些路由器到达目标	”下一跳往哪走”
距离向量（RIP）	交换路由表，邻居传话	”我邻居告诉我的”
链路状态（OSPF）	广播拓扑图，各自计算	”我有全图，自己算”
BGP	按策略选路，连接不同运营商	”客户的路优先走”
收敛	网络变化后所有路由器达成一致	网络”冷静下来”的时间

为什么先学这个？ 路由协议让数据包能跨越互联网到达目标。下一节看看IPv6 与 ICMP——IPv4 地址不够用怎么办。