路由选择 — 分组怎么选路Copy Anchor Link

这一章讲一件事: 每台路由器里那张「到哪个网络、下一跳交给谁」的表, 是怎么算出来、怎么随网络变化自动修正的。 先讲算法(最短路径、距离向量、链路状态),再讲协议(RIP、OSPF、BGP)—— 算法是数学,协议是把数学装进路由器并让它在真实网络里收敛的工程。 最后你会明白 Internet 为什么被切成一个个「自治系统」,以及为什么域间路由讲的是 与域内完全不同的语言。

1. 从查表到算表Copy Anchor Link

第 06 章的路由器转发时只干一件事:查转发表。表从哪来?两种来源:

• 静态路由:管理员手工配置,网络变了手工改。简单、可预测,适合小而稳定的网;
• 动态路由:路由器之间周期性交换信息、各自运行路由算法算出最优表项, 链路断了、拥塞了,表自己更新¹。

动态路由算法的好坏有六条验收标准:正确、简单、健壮(拓扑变了能重新算)、 稳定(收敛,不来回振荡)、公平、最优²。注意「最优」排最后——工程上, 简单和健壮往往比理论最优更要紧,这是贯穿全章的口味。

设计路由算法时还有几个前置选择题³:选最短还是选「最佳」(按延迟、带宽、费用的加权)? 按数据报还是虚电路方式工作?集中式算还是分布式算?用静态还是动态策略? ——不同答案组合出完全不同的网络,本章后面每一节都是一种答案的具体化。

2. 顶层全景:算法与协议的对号入座Copy Anchor Link

  6.5 路由选择算法(数学)
    ├─ 静态:洪泛、固定路由、随机路由
    ├─ 动态:孤立式(热土豆)、集中式、分布式
    │         └─ 分布式两大流派:
    │             距离向量(Bellman-Ford)── RIP
    │             链路状态(Dijkstra/SPF)── OSPF
    └─ 分层路由:网络太大就分区
  6.6 Internet 路由协议(工程)
    ├─ 自治系统(AS)切分世界
    ├─ IGP(域内):RIP、OSPF
    └─ EGP(域间):EGP(历史)、BGP(现役)

主线例子(贯穿本章): 六个路由器 A、B、C、D、E、F 组成的网络(书里的图 6-20), 各链路的「费用」标在边上(A–B=3,A–C=7,A–D=1,B–F=3,D–E=2,E–F=1……)。 我们要算出 A 到每个结点的最优路径,再让这套计算在 RIP 和 OSPF 两种协议里各跑一遍, 看同样的目标怎么生出两种性格的路由器。

3. 核心原理Copy Anchor Link

3.1 静态策略:三种笨办法,各有各的场景Copy Anchor Link

洪泛(flooding):收到分组的结点,向除进来那条线外的所有出口复制转发。 最笨也最可靠:只要源和目的之间有一条通路在,分组必到,而且第一个到的必走最短路径 (各路径并行扩散,短的总先到)⁴。代价是分组数量爆炸,要加措施(跳数计数、序号去重)。 场景:军事网(结点随时会被炸)、网络诊断与测试。

固定路由选择:每对源目的之间预先算好一条最优路径,每个结点存一张 「目的 → 下一跳」表,分组来了查表即走。全网由一个网络控制中心统一算好、统一下发⁵。 优点:转发极快;缺点:不抗变化——链路断了或拥塞了,表不会自己改。 负载稳定、拓扑不变的网里依然好用。

随机路由选择:收到分组,随机挑一个邻居发出去。简单到没有路由表,代价是路径不可预测、 可能绕圈。只在极特殊场合用(如匿名路由的思想实验)。

3.2 动态策略的三种体位Copy Anchor Link

孤立式:结点只看自己眼前的信息,不听别人报。代表作是 1964 年的热土豆算法: 收到分组,把它扔给输出队列最短的那条链路——像烫手山芋,先扔出去再说⁶。 改良版:队列长度加链路权值取最小。缺点:完全不知道远方情况,容易把分组往死胡同送; 优点:对本地拥塞反应极快。今天数据中心里的某些负载均衡仍看得到它的影子。

集中式:全网的拓扑与流量报给一个路由控制中心(RCC),它算好所有表项再下发。 RCC 有全局视野,结果「完美」,但计算量大、中心与全网的信息交换本身就是流量负担, 中心一挂全网瞎⁷。适合拓扑变化不大的场合。

分布式:每个结点只跟邻居交换信息,各自迭代计算,直到全网收敛。 这是今天的绝对主流,两个流派:距离向量与链路状态——本章剩余部分都是它们的展开。

3.3 最短路径算法:DijkstraCopy Anchor Link

一切路由算法的地基:把网络抽象成一张加权图(结点是路由器,边是链路,权是费用—— 可以是距离、延迟、费用的任意度量),求源点到所有结点的最短路径树⁸。

Dijkstra(1959)的思路是贪心扩张:维护一个已确定最短路径的结点集合 N, 每轮从 N 外找出「离源最近」的结点 w 加入 N,然后用 w 去松弛它的邻居: 若「源到 w 的最短路 + w 到 v 的边」比当前记录的源到 v 更短,就更新⁹。

主线例子跑表(书里的表 6-7 同款,初始 N={A}):

  步骤  入N     B(经)      C(经)      D(经)      E(经)      F(经)
   0    A      3(A)       7(A)       1(A)       ∞          ∞
   1    D      3(A)       6(D)       —          3(D)       6(D)
   2    B      —          6(D)       —          3(D)       5(B)
   3    E      —          6(D)       —          —          4(E)
   4    F      —          6(D)       —          —          —
   5    C      —          —          —          —          —

结果:A→D(1),A→B(3),A→D→E(3),A→D→E→F(4),A→D→C(6)。 注意第 2 步的 F:5(B) 被第 3 步的 4(E) 改写——每一轮新入 N 的结点都可能刷新 全表的最优估计,这就是「松弛」在表格上的样子¹⁰。 A 的路由表由此直接生成:到 F 下一跳 D,到 E 下一跳 D,到 B 下一跳 B…… 「最短路径树」一转手就是路由表,这是理解后面所有协议的钥匙: 协议之间交换的从来不是「完整地图」就是「距离摘要」,目的都是让每台路由器凑齐 自己跑 Dijkstra(或 Bellman-Ford)所需的原料。

3.4 距离向量:只告诉邻居「我到哪有多远」Copy Anchor Link

Bellman-Ford 的本地视角:结点 X 到 Y 的距离,等于「X 到各邻居的距离 + 邻居到 Y 的距离」里的最小值:

  DX(Y) = min over v: c(X,v) + Dv(Y)

每个路由器只需知道:自己和邻居的链路费用(c)以及邻居们声称的到各目的的距离(Dv)。 于是协议形态自然成形:每台路由器定期把整张表(目的,距离)发给所有邻居; 收到邻居的表,按上式重算自己的;算出的表变了就再发出去,如此往复直到稳定¹¹。

主线例子在距离向量下的样子:E 只需知道「到 A 直连 1、到 D 直连 2」,加上 B 报来的 「我到 A 是 7」、D 报来的「我到 A 是 3」,算出自己经 D 到 A 只要 2+3=5,路由表项 「到 A,下一跳 D,距离 5」——没有全局地图,只信邻居的二手消息,这就是「距离向量」 名字的由来:更新消息 = (目的向量 V,距离 D)¹²。

它有一个著名的病:无穷计数(count-to-infinity)。 书里的例子¹³: A、B 都连着网络 X(平时:A 到 X 距离 1 直接连,B 到 X 经 A 距离 2)。 A 与 X 之间的链路断了,A 宣布「到 X 距离 = ∞」。但就在这条坏消息还在路上时, B 的旧表「到 X = 2 经 A」先到了 A 的耳朵里——A 一算:经 B 到 X 只要 2+1=3! 于是 A 改报「到 X = 3 经 B」;B 收到后更新为「4 经 A」;A 再更新成「5 经 B」…… 坏消息以每轮加 1 的速度绕圈传播,直到距离顶到协议允许的无穷大(如 RIP 的 16), 两人才同时承认 X 不可达。在此期间,若有目的为 X 的分组,就在 A、B 之间来回打转。

四味药,每味治一部分¹⁴:

RIP 实际用了水平分割 + 抑制规则 + 16 跳上限(16 即无穷大,顺便限制了网络直径)¹⁵。

3.5 链路状态:每人一张地图,各算各的最短路Copy Anchor Link

距离向量是「道听途说」,链路状态是「发给大家我自己量到的」:

每个路由器五步¹⁶:

1. 发现邻居:发 Hello 包,知道直接相邻的都有谁;
2. 量链路费用:测到每个邻居的延迟或开销(如 echo 往返测延迟);
3. 组装 LSP(链路状态分组):「我是谁、我连着谁、每条链路的费用」;
4. 泛洪 LSP:用带确认与序号的可靠洪泛,把 LSP 扩散到全网每一路由器 (不同于距离向量的只发邻居);
5. 各算各的:每人都攒齐了全网的 LSP,本地跑一遍 Dijkstra,算出以自己为根的 最短路径树 → 生成路由表。

对比两张表(书里的表 6-9)¹⁷:

链路状态为什么能避开无穷计数?因为坏消息(某链路断了)作为一条 LSP 一次性泛洪全网, 所有人同时删掉这条边、同时重算——不存在「你信我的旧消息」的窗口期, 谣言没有绕圈的土壤。代价:初始洪泛需要高带宽,每个结点要存全网的拓扑数据库。

3.6 分层路由:地图太大就分区Copy Anchor Link

Internet 规模的网络,让每台路由器都存全网拓扑不现实。分层路由的折衷: 把网络分成若干区域,区域内用任何前述算法算细路;跨区域时, 由边界上的路由器负责「到别的区域往哪走」,区域内部的细节对外隐藏¹⁸。

主线例子的收尾:A.a 要发给 C.b——先在本区域内路由到边界路由器 A.b, A.b 负责找「到区域 C 的最佳路径」,交给 C.a,C.a 再在区域 C 内投递¹⁹。 这是后面 OSPF 区域与自治系统概念的预演:分层的第一收益是路由表和路由流量都按 区域缩小,第二收益是管理权可以按区域切分——后者直接催生下一节的自治系统。

3.7 自治系统:Internet 的政治地图Copy Anchor Link

Internet 不属于任何单一管理机构,它由成千上万个**自治系统(AS)**组成—— 一个独立管理实体控制的一组网络和路由器²⁰。每个 AS:

• 内部路由自己说了算,想跑 RIP、OSPF 或谁都不通告的私有协议都行;
• 但必须挑一个或多个「发言人」路由器,用与邻居 AS 相同的协议对外宣告可达性。

由此分出协议的两层:

• IGP(内部网关协议):AS 内部用,讲究性能——RIP、OSPF、IGRP/EIGRP;
• EGP(外部网关协议):AS 之间用,讲究政策——「哪些流量允许穿过我」比 「哪条路最短」重要²¹。这是两套设计语言的根本差异: IGP 优化性能,EGP 表达立场。

3.8 RIP:距离向量的正装版Copy Anchor Link

RIP(RFC 1058,更新版 RIPv2 是 RFC 1723)把距离向量装进 Internet:

• 度量 = 跳数:直连网络距离 1,每过一个路由器加 1;16 跳即不可达—— 这个上限既是无穷计数的安全绳,也把 RIP 的网络直径限制在 15 跳内²²;
• 载体是 UDP 520 端口(协议实现位于应用层,但服务的是网络层转发)²³;
• 三张计时器:更新计时器 30s(周期广播整张路由表)、超时计时器 180s (路由 180s 没被刷新就置为无效,距离改 16)、清除计时器 270s(无效路由再保留一段时间 后彻底删除,给「它可能复活」留窗口)²⁴;
• 被动与主动:主机可以跑被动 RIP(只听不播),路由器跑主动 RIP(又听又播);
• RIPv1 vs RIPv2:v1 是分类时代的协议,路由项不带掩码、不支持 CIDR 与认证; v2 补上掩码字段、支持变长掩码和简单认证²⁵。

RIP 的更新规则(合并主线例子):R3 直连网络 X、Y(距离 1),从 R1 收到 「X 距离 1、W 距离 1」——X 已直连且更近,忽略;W 是新的,加表「经 R1,距离 2」。 只有「我没有的」或「比你当前更短(且下一跳不是来源本身)」才更新²⁶。 坏消息(链路断)靠超时把距离慢慢抬到 16——无穷计数在 30s×(16−当前) 的时间内自愈, 小网没问题,大网就是灾难。

3.9 OSPF:链路状态的正装版Copy Anchor Link

OSPF(1990 年成为标准,Internet 的主力 IGP)把链路状态装进 Internet,并加了 大型网络必需的几件工程装备²⁷:

拓扑数据库即权力:每台路由器泛洪自己的 LSA(链路状态通告),攒出全网(本区域内) 的一致拓扑数据库,各自跑 Dijkstra 算出以自己为根的最短路径树²⁸。 OSPF 把网络抽象成有向图:路由器是结点,每条弧标两个参数——传输费用(从路由器出发 的弧非零,从网络出发的弧为 0)和 ToS(可以按低延迟/高带宽分别算路)²⁹。

区域(AREA):AS 再切成若干区域;区域内泛洪全部细节,区域之间只传摘要路由, 由一个特殊的**主干区域(area 0)**统一中转——所有跨区域通信必须经过主干, 整个 AS 形成以主干为中心的星形逻辑结构³⁰。路由器由此分四类: 内部路由器、区域边界路由器(ABR,把本区域摘要上报主干)、主干路由器、 自治系统边界路由器(ASBR,对外的发言人)³¹。

指定路由器(DR)与备份(BDR):多访问网络(以太网)上若有 n 台路由器两两交换 LSA, 需要 O(n²) 条邻接关系;OSPF 选出 DR 作为「课代表」,大家只和 DR/BDR 同步, DR 代表本网段发 LSA——邻居关系降到 O(n),带宽大省³²。 Hello 报文发现邻居并选举 DR(优先级高者当选,同优先级比路由器 ID)。

五种报文:Hello(发现邻居、保活)、Database Description(同步拓扑摘要)、 Link State Request(请求详情)、Link State Update(泛洪 LSA)、Link State Ack(确认)³³。 对比 RIP 的「整张表周期广播」,OSPF 平时只发 Hello,变了才泛洪增量—— 路由流量与稳定性都赢了 RIP,代价是复杂度和资源消耗。

3.10 BGP:域间的语言是政策Copy Anchor Link

AS 之间用 BGP;现役标准是 BGP-4。与所有 IGP 都不同,BGP 是路径向量协议: 通告的不是「距离 N」,而是「到前缀 P 的路径,途经 AS1→AS3→AS7」³⁴。

路径向量的妙处:每条路由自带完整 AS 序列,环路一眼可见 (看到自己的 AS 号就拒收)——BGP 从根上没有无穷计数。

三个过程³⁵:

1. 邻居获取:两台 BGP 路由器先建立 TCP 连接(端口 179),发 Open 报文建邻, Keep Alive 维持——用可靠传输驮路由信息,重传确认全免;
2. 邻居可达性:周期 Keep Alive(或按协商);
3. 网络可达性:维护可达子网数据库和最佳路由;路由一变才发 Update(增量更新), 不是周期全量——和 OSPF 一样,只发变化。

四类报文:Open(建邻)、Update(宣告新路由/撤销旧路由)、Keep Alive(保活)、 Notification(出错拆邻)³⁶。Update 一次可宣布多条可撤路由 + 一条新路径的属性 (含 AS-PATH、NEXT-HOP 等)——属性机制是 BGP 表达政策的载体: 「优先走这个 AS」「这个前缀的流量别从我这穿」都写在属性里。

IBGP 与 EBGP:同一 AS 内的 BGP 会话叫内部连接,跨 AS 的叫外部连接—— IBGP 存在的理由:AS 的发言人 ASBR 可能不止一台,AS 内部得先把对外路由一致化³⁷。

4. 作者的判断与证据Copy Anchor Link

• 「没有银弹」:六种理想特性把「最优」排在最后、复杂度和开销贯穿各节对比表, 这是教材少有的克制——路由选择是权衡的教科书案例³⁸。
• 「BGP 是政策路由」:「IGP 更多地考虑性能,EGP 则是策略路由」一句, 是全章含金量最高的判断:它解释了为什么学了 RIP/OSPF 还是看不懂运营商的行为³⁹。
• 分层路由的论证链(表太大→分区→边界汇总)先给工程收益,到 AS 再补上管理收益, 从 3.6 到 3.7 的过渡是全书结构设计得最自然的一段⁴⁰。

5. 边界与局限Copy Anchor Link

• RIP 的实际部署已退居小型网络/教学,但「跳数、30s、16=∞」仍是面试与故障排查的 通用语言;书中 RIPv1 篇幅按 2025 年看偏多。
• OSPF 的区域设计、DR 选举细节按教材口径简化:真实网络还有虚链路、NSSA 等 区域变体,书里没展开。
• BGP 的属性与政策一章只点到(AS-PATH、增量更新),MED、Local-Pref、 路由反射这些工程核心未涉及——想读懂运营商公告还得看专门的 BGP 资料。
• 拥塞相关路由(按负载调权)未讲:链路状态的费用是静态配置的, 「动态 metric」只在孤立式路由里以热土豆的形式露了一面。

判断(我们的,不是书里的): 本章最该带走的是那张「距离向量 vs 链路状态」的 对照表——它不只在路由里成立:任何需要「分布式系统各自形成一致视图」的场景 (数据库复制、Gossip 协议、区块链共识)都是这两条路线的某种重演: 「传状态摘要、各算各的」收敛快但占资源,「传增量、互相背书」省资源但怕谣言。 BGP 的存在则提醒:规模到了一定程度,路由问题就从数学问题变成了政治经济问题。 如果错,会错在: 数据中心内部的新兴路由(Fabric、RDMA 网络)又开始挑战 「分布式 SPF」的统治,而 SDN 的控制集中化像是「集中式路由」借尸还魂—— 历史路线没有优劣,只有场景。

6. 可带走的Copy Anchor Link

1. 路由六性:正确、简单、健壮、稳定、公平、最优——最优排最后;
2. 洪泛必达且先到者最短,代价是流量爆炸——可靠性最强的笨办法;
3. Dijkstra = 集合扩张 + 松弛;「最短路径树一转手就是路由表」;
4. 距离向量:只发邻居、二手消息、收敛慢、无穷计数;
5. 无穷计数的四味药:水平分割、毒性反转、抑制、触发更新;
6. 链路状态:LSP 泛洪全网、人人有地图、各跑各的 Dijkstra、收敛快、吃资源;
7. 分层路由:区域内细、区域间粗;AS = 管理自治 + 发言人对外;
8. RIP:跳数度量、30s 更新、180s 超时、16=∞、UDP 520、v2 才支持 CIDR;
9. OSPF:LSA 泛洪、拓扑数据库、Dijkstra;区域 + 主干;DR/BDR 省邻接;Hello/DBD/LSR/LSU/LSAck;
10. BGP:路径向量(TCP 179、增量更新),AS-PATH 防环;域内讲性能,域间讲政策。

7. 原文地图Copy Anchor Link