本节书摘来自异步社区《IS-IS网络设计解决方案》一书中的第6章，第6.2节，作者【美】Abe Martey，更多章节内容可以访问云栖社区“异步社区”公众号查看

6.2　使用SPF算法计算IS-IS路由

IS-IS网络设计解决方案
ISO 10589附录C2定义了使用SPF算法进行IS-IS协议的路由计算。RFC 1195附录C定义了SPF算法的修改版本从而使IS-IS协议支持IP路由选择。Dijkstra算法产生网络拓扑的最短路径树，从而确定去往不同目标的最短（最优）路径并放入IP路由表。为了获得IP路由的最佳路径，IP子网会被看作是最短路径树的树叶。网络事件只会导致链路状态数据包中IP可达性条目的改变，而不要求重新计算整个最短路径树。在这种状况下，IS-IS协议只需进行部分路由计算（Partial Route Calculation，PRC）而不是完整地运行SPF算法。在大多数情况下，IS-IS路由计算中无处不在的PRC优化了IP路由选择收敛的执行效率。

前文曾提到SPF算法的计算时间的阶数O(LlogN)，其中L为链路数量，N为节点数量。LogN因子是由Dijkstra算法操作的步骤2（见图6-2）产生的。T集合中的元素会预先按照开销进行排序从而避免在选择最低开销元素时进行线性搜索。在排序的T集合中使用二进制搜索机制并插入新条目所需的处理时间引入了logN因子。通过使用一个基于6位字段的有限路径开销（ISO 10589中定义），可以将复杂性阶数优化并降低为O(N)，从而消除了logN。这是通过使用快速的阵列排序数据结构，将节点按照路径开销而不是逻辑距离进行散列排序实现的。不幸的是，随着时间推移，在IS-IS网络设计及其他IS-IS路由选择应用（例如MPLS流量工程）中，6位的度量字段已经不足以提供足够的灵活性。在IS-IS中采用更大路径开销（宽度量）很明显地要比小而有限的路径开销（窄度量）具有网路优化方面的优势（见第5章）。

RFC 1195对IS-IS路由选择的SPF算法进行了修改，允许在多条等价路径上实现负载均衡。但在通常情况下，Dijkstra算法仍按照前文所述的过程工作。在RFC 1195附录C中对SPF算法的操作进行了很好的描述。在构建最短路径树时会使用以下三种列表：未知或候选列表（Unknown or candidate list，UNK）、实验列表（Tentative，TENT）和已知路径列表（known Paths，PATHS）。当SPF开始运行时，所有的节点放入UNK中。随后在初始化时将源节点移入PATHS。节点会根据其下一跳及度量信息放入TENT，从而进一步检查其是否可以放入PATHS。IS-IS为所有邻居维护一个邻接数据库，为SPF的运行提供TENT中直连邻居的下一跳信息。对于非直连的主机，从PATHS中经过其父节点获得第一跳信息。存放在TENT和PATHS中的条目是由三元组组成的：{n, d(n), Adj(n)}，其中：

• n=系统ID；
• d(n)=从源s到n的距离；
• Adj(n)=源s已知的n有效邻接的集合。

在算法的每一步都需要检查TENT列表，具有到源的最小开销的节点将被移入PATHS。当节点被放入PATHS后，该节点所通告的IP前缀及相应的度量和下一跳信息将放入IS-IS路由选择信息库（IS-IS Routing Information Base，RIB）。如果放入PATHS中的节点的直连邻居不在TENT中，则将其移入TENT并对其开销进行相应的调整，以进行下一次选择。

请注意IP内部及外部前缀包括地址和掩码在内共占8字节，这些前缀永远都是叶子。