从一张拓扑图变成一棵最短路径树再到路由表的实际生成IS-IS 的 SPF 计算过程就是一套非常经典的 Dijkstra 算法。很多朋友学路由协议时都卡在这里LSP 洪泛看懂了、LSDB 也同步了一到 SPF 计算阶段就被一堆术语绕晕。这篇文章我直接把整个计算过程掰开揉碎从数据结构到一次完整迭代再到常见的排障思路一次性讲清楚。1. 从一个“选路问题”说起IS-IS 为什么要用 SPF1.1 链路状态协议和距离矢量协议的差别先想一个生活场景你要开车从北京到上海导航软件不是靠“听邻居说哪条路近”来给你指路的而是掌握了一张全国高速地图然后基于这张地图算出最短路线。IS-IS 就是路由协议里的“导航软件”它不像 RIP 那样只把路由表转发给邻居这种就是距离矢量“我听说去某地经过你那儿比较近”而是让区域内所有路由器都拿到一张完整的网络拓扑图LSDB链路状态数据库再基于这张图各自独立计算最短路径。SPF 算法Shortest Path First最短路径优先就是这张拓扑图的“路径规划引擎”。它解决的核心问题是给定一台路由器知道的全网节点和链路如何快速、无环地算出自己到达每个目的地的最优路径。这也是链路状态协议和距离矢量协议最本质的分水岭一个靠全局视野一个靠邻接互传二者在计算模型、收敛速度、扩展性上都有巨大差异。1.2 IS-IS 眼中的“图”LSP、LSDB 和全网拓扑IS-IS 路由器之间通过交换 LSPLink State PDU链路状态数据单元来互相通告自己的接口状态、邻居关系和链路开销。每台路由器把这些收到的 LSP 存进自己的 LSDB这才有了所谓“全网同步的拓扑图”。需要注意IS-IS 和 OSPF 虽然都是链路状态协议但它俩的报文封装方式不同LSP 的组织形式也不同IS-IS 直接封装在二层不适合在思科、华为等厂商中简单一概而论。但从 SPF 计算的角度你只需要知道LSDB 里有一堆描述链路和节点的记录SPF 算法就是从这个数据库里把图结构提取出来再做路径计算。顺着这个思路继续走为什么 IS-IS 能保证“所有路由器看到同一张图”这就得益于 LSP 的泛洪机制和每条 LSP 上都带有的序号、老化时间、校验和。路由器只有在 LSDB 同步完成后才开始 SPF 计算。如果某个 LSP 还没泛洪完成数据是残缺不全的算出来的最短路径树也必然是残缺甚至错误的。实际排障中“LSDB 不同步导致路由黑洞”是非常常见的现场问题后面我在第 5 章展开聊。1.3 SPF 算法要解决的三个问题SPF 算法看似只是“求最短路径”但落到 IS-IS 这个具体场景它实际上要回答三个递进的问题第一从当前路由器出发到每个网段/节点的最短路径是哪一条这是最基本的目标Dijkstra 算法通过逐步松弛来做到。第二如果有多条路径开销完全相同怎么办这就引出了 ECMP等价多路径IS-IS 在生成最短路径树时允许保留多个父节点然后把这多条下一跳同时放进路由表。第三拓扑发生变化时如何快速收敛只重算受影响的部分而不是动不动全量跑一遍 SPF于是才有了 I-SPF增量 SPF和 PRC部分路由计算这些优化手段。把这三个问题理清楚了你对 IS-IS SPF 的理解就不会飘在算法表面而是能落到真实网络的工程需求上。2. SPF 算法核心拆解Dijkstra 在 IS-IS 中的落地2.1 三个关键数据结构Path、Tent、LSDBSPF 计算不是空谈理论它在代码层面的核心是维护两个集合、依赖一张数据库Path 集合已经计算出最短路径的节点集合算法开始时只有本路由器自己根节点随着迭代不断扩充直到覆盖全网可达节点。Tent 集合候选节点集合那些已经通过某个 Path 集合中的节点发现、但尚未确认“这就最短”的节点先放进 Tent 里候着。LSDB提供边信息。LSP 里写明的邻居关系和开销值就是 SPF 需要处理的边。我常用一句话帮助朋友理解“Path 是定居名单Tent 是候补名单”。每次迭代从候补名单里挑一个最近的迁入定居名单然后检查新居民的邻居看有没有能更新入候选人名单的。整个过程很像一场“最邻近扩展”的选举谁离根节点近谁先上岸。这里要特别注意LSDB 里存储的拓扑信息不一定是完全连接的。非广播多路访问网络NBMA下可能出现部分连通广播网里又引入了伪节点。SPF 算法在迭代前通常会先把图结构建好凡是邻居状态不是 Up 的、接口被动关闭的、或者开销值为无穷大的都会在建图时直接过滤掉不参与计算。2.2 计算步骤与松弛操作把 SPF 的迭代过程写成伪代码大概是这样的初始化 Path { self, cost0 } Tent 所有可达邻居 { neighbor, cost接口开销, parentself } 循环 if Tent 为空: 结束计算 从 Tent 中选出 cost 最小的节点 X移入 Path 遍历 X 的所有邻居 Y 新开销 X.cost cost(X,Y) if Y 不在 Path 且 新开销 Y 在 Tent 中的记录: 更新 Y 的记录parent X, cost 新开销 else if 新开销 Y 在 Tent 中的记录: 为 Y 增加一个父节点 X支持 ECMP 时的处理这个“新开销小于原记录就把父指针更新掉”的操作在算法上叫“松弛”。松弛操作保证每个节点在进入 Path 集合的那一刻其记录的 cost 就是从根节点到它的全局最小值。这里蕴含了一个数学前提边开销非负。IS-IS 的默认开销是正整数所以 Dijkstra 算法成立。如果谁配了负开销SPF 可能算出“越走越近”的诡异环路所以在实际网络中负开销是严格禁止的。另外提醒一个容易被忽视的小细节从 Tent 中选“最小 cost 节点”时如果有多个节点 cost 相同算法选中哪一个都是正确的因为最后生成的最短路径树在这几个节点上的开销相同。但对 ECMP 的处理IS-IS 的做法是记录多个父节点而不是只选其中一个否则等价路径就被丢弃了。这个细节我在第 3.4 节再细说。2.3 度量值为什么这么重要SPF 计算中“cost”的值直接决定了生成树长什么样所以度量值设计是 IS-IS 部署里的关键决策点。老式 IS-IS 默认接口开销是 10所有接口不分带宽一律 10这在早期链路带宽差距不大的年代够用但后来千兆、万兆接口出现全默认 10 的话SPF 算出来的路径很可能不是真正的高带宽路径。现在主流做法是启用 wide metric宽度量支持 24 位开销值可以做到接口级精细化调优。你可以在接口下手动设置开销也可以用自动带宽参考值。比如参考值设为 1000Mbps那么千兆接口开销是 1百兆接口开销是 10SPF 匹配出的最优路径就自然选择了高带宽链路。这就和 Dijkstra 算法里的“权重”概念完全对应了权重定得合理算法才算出合理结果。还需注意 LSP 中通告的开销是单向的A 到 B 的开销可以不同于 B 到 A 的开销。如果配置时不注意链路两端度量值对称SPF 就会算出不对称的往返路径这在某些回程路径敏感的组网里会引发问题。常规做法是保持全网络开销策略一致自动模式选定后不要局部乱改。2.4 伪节点是什么广播网络里的特殊节点在广播多路访问网络比如以太网里所有路由器两两之间都能互通如果每台路由器都在 LSP 里描述“我和其余每一台相邻”那 LSDB 里边的数量就是 N*(N-1)/2N 大了以后数据量和 SPF 计算量都会爆炸。IS-IS 的解决办法是在广播网里选举一个 DISDesignated Intermediate System指定中间系统由它生成一个“伪节点”并通告一条伪节点 LSP描述这个广播网里连接了哪些路由器。伪节点在 SPF 里被当作一个普通节点来参与计算所有真实路由器都只连接到伪节点开销为 0 或配置的接口开销。这样一来原本的全网状连接被折叠成了一个星型结构边的数量从 O(N^2) 降到 O(N)。我打一个比方这就好比小区里每家每户的快递不是每户之间都单独互相送而是统一送到小区快递柜伪节点再由柜子分发给各家。这样 SPF 的迭代次数大幅减少收敛速度自然就快。这里有一个调试时的关键认知伪节点 LSP 的生成者是 DIS而且 DIS 是可以抢占的。一旦 DIS 发生故障或重新选举伪节点标识就变了原来基于该伪节点的 SPF 树全部失效会触发一次全量重算。所以如果广播网内 DIS 频繁震荡SPF 计算次数会明显上升全网路由器的 CPU 都会受影响。3. 一个 SPF 计算实例从 R1 出发算到全网3.1 示例拓扑与初始数据理论讲再多不如手推一遍。我设计了一个最简单的 4 台路由器拓扑链路开销标在边上注意 IS-IS 开销是接口级的每台路由器对自己接口的开销负责节点邻居开销R1R210R1R320R2R35R2R410R3R410假设 LSDB 已经完成同步每台路由器都清楚全网拓扑。现在以 R1 为根执行 SPF。初始阶段Path 集合只有 {R1(0)}Tent 集合里有 R1 直接相连的两个邻居R2(10父 R1) 和 R3(20父 R1)。变量记录如下节点当前最优开销父指针所在集合R10无PathR210R1TentR320R1Tent3.2 一步步推演 SPF 迭代过程第一轮迭代从 Tent 中选出开销最小的节点。R2 开销是 10R3 是 20所以选 R2 进入 Path。把 R2 移入 Path 后遍历 R2 的所有邻居R1、R3、R4。R1 已经在 Path 里直接跳过不需要处理。R3 当前在 Tent 中开销记录是 20父指针是 R1。但通过 R2 到 R3 的新开销是 10R2 自身成本加 5R2-R3 链路开销等于 15小于原来记录的 20。于是松弛发生R3 在 Tent 里的记录被更新为开销 15、父指针改为 R2。R4 是新发现的节点之前不在 Tent 里现在通过 R2 发现开销为 10R210R2-R420父指针为 R2加入 Tent。本轮结束后的状态节点当前最优开销父指针所在集合R10无PathR210R1PathR315R2TentR420R2Tent第二轮迭代Tent 中有 R3(15) 和 R4(20)最小的是 R3把 R3 移入 Path。遍历 R3 的邻居R1、R2、R4。R1、R2 已在 Path 中跳过。R4 在 Tent 中当前记录是开销 20、父指针 R2。通过 R3 到 R4 的新开销为 15R3 自身成本加 10R3-R4 链路开销等于 25大于原有的 20。松弛操作的前提是“新开销更小”这里不满足所以 R4 的记录保持不变仍维持父指针 R2、开销 20。第三轮迭代Tent 里只剩 R4开销 20移入 Path。遍历 R4 邻居R2、R3都已在 Path 中全部跳过。Tent 变空SPF 计算结束。最终结果节点最终最短开销父指针R10无R210R1R315R2R420R2最短路径树为 R1→R2→R3以及 R1→R2→R4。这里特别值得注意R1 和 R3 之间看起来有一条直连链路开销 20但 SPF 依然选择了绕行 R2 的路径总开销 15因为它更短。这就是最短路径树和物理拓扑不一致的典型例子很多刚学 SPF 的人会被“明明有直连为什么要绕路”这个问题卡住答案是算法只认总开销不认跳数或“直观路线”。3.3 从最短路径树到路由表SPF 算出的最短路径树并不是直接写入路由表的它还要经过一次“信息提取”的过程。树上的每个节点对应一台路由器或伪节点但真实目标是网段。IS-IS 路由信息其实是 LSP 里附带的每台路由器在自己的 LSP 中通告它直连的网段和开销。SPF 计算出的是“去往某台路由器的最优路径”然后结合那台路由器 LSP 里通告的网段开销得出“去往某个网段的总开销”最后把这部分信息投递到路由表管理模块。继续用上面的例子。假设 R3 在它的 LSP 里通告了一个直连网段 10.1.3.0/24开销为 0指本机直连网段那么 R1 到达该网段的总开销就是R1 到 R3 的最短开销 15加上 R3 通告的网段开销 0最终路由就是 10.1.3.0/24下一跳 R2开销 15。如果 R4 也通告了 10.1.4.0/24那么 R1 去 10.1.4.0/24 的开销就是 20下一跳同样是 R2。这就是为什么说 SPF 计算结果要先形成一棵“以本机为根的最短路径树”再根据树上的各节点地址和通告前缀生成路由表。只有链路状态变化了才重新算树前缀变化时则可以通过 PRC 做局部刷新不需要重跑整棵树。3.4 等价路径与 ECMP 怎么处理如果我把拓扑稍微改一下把 R1-R3 之间的开销从 20 改成 10情况就完全不同了。R1 到 R3 的路径有两条直连开销 10绕行 R2 的路径开销 15直连更优所以树会变成 R1 直连 R3。如果再把 R2-R3 的开销改成 5同时 R1-R3 也保持 10那 R1 到 R3 就有两条开销相同的路径了直连 R3 开销 10经过 R2 开销也是 10。这时候 Dijkstra 算法在“从 Tent 中选最小节点”这一步可能先选 R3 或 R2但最终的结果必须是两条路径都被记录。在实际实现中IS-IS 会对一个目的地保留多个父指针并在生成路由时产生多个下一跳这就是 ECMP。路由表里会出现同一前缀带两个下一跳、开销相同的条目流量被哈希分摊到两条链路上。ECMP 是 SPF 一个非常实用的自然延伸算最短路径树的时候不死板地“只保留一个父节点”而是对开销相同的候选全部保留。这样做不仅提高了链路利用率还在单条链路故障时实现了快速切换因为另一条等价路径还在树上。调试时注意ECMP 的数量不是无限的常见实现支持 4 条或 8 条等价路径超出后会按一定规则挑选。4. L1/L2 分层与 SPF 的边界问题4.1 Level 分级带来的 SPF 区域化IS-IS 和 OSPF 一样有分层的概念但叫法不同Level-1 相当于 OSPF 的非骨干区域Level-2 相当于骨干区域。一台路由器可以只跑 Level-1、只跑 Level-2或者同时跑 Level-1/2这是最普遍的骨干路由器模式。分层对 SPF 最大的影响是路由器不需要为全网计算一棵完整的树。Level-1 路由器只维护本区域内的 LSDB只计算本区域内的 SPF 树Level-2 路由器维护整个 Level-2 域以及通过路由泄露获取的区域信息。这种设计大幅缩小了单台路由器的计算规模。对于 Level-1 路由器会发现一个有趣的机制它往区域外发流量时不是去算一条到外部目标的最短路径而是通过区域内最近的 Level-1/2 路由器转发并默认把该路由器通告的一条默认路由缺省路由作为出口。换句话说Level-1 的 SPF 树是“区域内精确计算区域外走默认”这大大简化了叶节点路由器的存储和计算压力。4.2 默认路由和路由泄露上面提到的 Level-1 默认路由Level-1/2 路由器会通过特定 LSP 通告给 Level-1 区域告诉区域内部“去外部网络从我这走”。如果一台 Level-1 路由器连接的 Level-1/2 路由器有多台它就会在 SPF 树里发现多个默认路由的等价出口然后在路由表里生成多条默认路由流量可以在这几台 Level-1/2 之间负载均衡。这里又引入一个精细话题Level-1/2 路由器把自己学到的 Level-2 路由以“路由泄露”方式注入到 Level-1 区域。如果泄露了明细路由区域内的 Level-1 路由器就能算出更精确的出口选择而不是一刀切全走默认路由。但注意泄露会增加区域内 LSDB 的规模加大 SPF 计算负担不泄露虽然简单但可能造成次优路径所有外部流量都挤在同一个出口。在实际网络中是否开启路由泄露需要在“计算规模”和“路径最优性”间权衡。我见过不少项目一上来就全量泄露导致区域内 SPF 树变得非常庞大收敛变慢后来又收回去只泄露部分汇聚路由。SPF 的计算成本不是一个理论参数它在真实组网里直接影响故障切换速度。4.3 SPF 触发的真实场景链路抖动时的防抖机制SPF 不是任何时刻都在跑它是由事件触发的。IS-IS 收到新的 LSP或者本地接口状态变化、邻居断开、开销变更这些都会触发 SPF 调度。如果网络不稳定LSP 不断刷新SPF 也不断重算那路由器 CPU 就危险了。所以 SPF 计算前面有一道“防抖”闸门第一次收到触发事件后会等待一个很短的时间间隔比如 50ms看看还有没有后续事件。如果陆续有新的 LSP 到达就继续等待并进入指数退避把间隔逐步拉长到几百毫秒甚至几秒。等到网络安静了才真正执行 SPF 计算。这有点像是给算法加了一个“聚拢窗口”把一阵风暴内的事件合并成一次计算。调试中判断网络是否稳定一个经典指标就是看 SPF 运行次数。如果一段时间内 SPF 运行次数异常多、且每次运行的间隔都很短说明网络里有路由震荡源。常见诱因包括互联接口频繁 up/down、LSP 生成计时器参数不一致导致泛洪循环、等价路径反复切换等。要治本不是去调大防抖参数把问题掩盖而应定位到具体链路或邻居先把物理层和链路层搞定。5. 实战排障SPF 异常的典型症状5.1 路由震荡反复重算现场最头疼的问题就是“全网路由表在抖”。你登录设备看 SPF 日志发现同一棵最短路径树在几十秒内被反复重算每一轮重算后的下一跳都在变化。这时候第一步不是分析算法而是确认到底哪个 LSP 在频繁刷新。排查思路是把最近收到的 LSP 按“源系统 ID”分组统计刷新次数最多的那一个。找到源头路由器后去那台设备上检查它产生的 LSP 为什么每隔几秒就更新。常见原因包括某接口物理层不稳定反复 up/down、等价链路的一端配置了接口开销自动调整而另一端没有、或者该路由器 CPU 过高导致 LSP 重生成超时。把源头搞定全网 SPF 次数自然就回到正常水平。另外一个被忽视的原因时钟不同步。IS-IS 的 LSP 老化时间基于相对时间如果两台设备的时钟偏斜大LSP 剩余寿命的判断就会异常导致未到期就重发新 LSP。所以部署 IS-IS 的网络建议把所有设备纳入统一的时钟同步这不是可选项而是稳定性的刚需。5.2 LSP 不新导致树陈旧和“频繁重算”反着来的一种症状网络明明已经发生变化但路由表迟迟不更新。问题多半出在 LSP 的接收和处理链路而不是 SPF 本身。登录设备检查 LSDB 中对应路由器的 LSP如果发现序列号不是最新或者剩余寿命已经很低却没有被刷新那就是泛洪环节出了故障。泛洪问题的常见诱因包括两台设备之间的 Level-1/Level-2 邻接没有正确建立两边 Level 配置不一致、MTU 问题导致大的 LSP 被静默丢弃、以及某台设备的接口下配置了泛洪过滤策略导致特定 LSP 被拦截。SPF 本身算法没错但它吃的是 LSDB 的“料”料不新鲜炖出来的树就一定是过期的。所以排查 SPF 问题时永远先查 LSDB再查树上。5.3 次优路径问题还有一种情况路由表里明明有路径但不是最佳路径。这往往是 SPF 输入数据的问题而不是算法的问题。最典型的例子就是伪节点参与方式异常。如果广播网中 DIS 发生变化但老伪节点的 LSP 迟迟没有从 LSDB 中清除SPF 就会基于一张同时包含新旧伪节点的“残留图”计算结果生成的路由可能绕路。另一个次优路径原因是度量值不一致。比如一条链路两端接口的 wide metric 配置不同A 到 B 的开销是 10B 到 A 的开销是 100那么从 A 算 SPF 时到 B 的路径开销是 10但从 B 算 SPF 时到 A 的路径开销是 100。路由表里同一个目的地的开销取决于计算方向这就会造成严重的路径不对称。解决方法是统一两端接口开销配置并且通过拓扑检查工具验证双向开销数据。5.4 常见问题速查表症状可能原因排查方向SPF 重算次数过高接口震荡、LSP 反复刷新、等价路径切换查看 SPF 日志定位高频 LSP 源路由更新延迟LSP 泛洪不及时、邻接异常、MTU 问题检查 LSDB 中 LSP 序号与剩余寿命次优路径双向度量不对称、残留伪节点、路由泄露缺失逐段核对接口开销检查 DIS 稳定性部分路由缺失LSP 被过滤、区域边界路由策略错误检查 LSP 过滤策略与 Level 边界配置环路负开销配置或路由策略异常检查是否有非法开销值核验路由策略这张表是我在实际项目中反复验证过的排障路径基本覆盖了 SPF 阶段 90% 以上的异常场景。记住一句话SPF 算法本身很成熟真正出问题的几乎总是它的输入数据——LSDB 的内容和开销信息。结尾一点个人体会SPF 算法看起来只是一段 Dijkstra 的实现但在 IS-IS 里它被赋予了太多工程细节伪节点、Level 分层、防抖调度、增量计算、等价路径处理每一层都让这个经典算法更适应真实网络的复杂性。我每次在只剩三层结构的跨地区项目里都会先把网络设计和 SPF 计算规模算一遍账因为链路状态协议最大的敌人不是算法正确性而是拓扑规模失控导致的收敛缓慢。如果各位能看懂这篇文章里手动推演的那个 4 节点例子再回头看生产环境里任何一张复杂的 SPF 树思路都会清晰得多——不过是从一个根节点出发不断选择最近的邻居扩展直到覆盖整张图而已。