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

6.3　Cisco路由器上实现IS-IS SPF

IS-IS网络设计解决方案
在特定的路由器平台上对某种协议的实现对网络操作者来说几乎是透明的，不同厂商的产品之间遵循标准以实现互操作性。特定厂商的协议实施细节及软件代码通常具有厂商的专利。但无论如何，一名网络工程师如果想要更好地了解特定平台上的IS-IS原理和操作方法，都要学习各种参数，如默认计时器、标志位、默认参数以及如何配置方面。此外，如ISO 10589和RFC 1195这类标准也提供了非常有用的指导。本节对Cisco路由器上IS-IS协议的操作，特别是关于SPF算法的实现进行了讨论。

Cisco路由器上SPF进程的工作机制如前文所述。算法中使用3个相互独立的列表（UNK、TENT和PATH）以计算区域内的最短路径树。计算过程是基于链路状态数据库中的内容和路由器的配置实现的。SPF算法由SPF进程在路由器的处理器上执行，SPF进程由IS-IS体系中的IS-IS决策进程控制。决策进程同时与负责管理链路状态数据库的更新进程关联。链路状态数据库的任何变化将触发SPF进程并可能导致SPF算法的一次整体执行或者PRC。如ISO 10589中定义的，默认情况下SPF进程的执行间隔不能低于10秒钟。使用命令show isis spf-log可以查看触发SPF进程的事件（见例6-1）。在一个动态的环境中，10秒的SPF进程运行间隔之间可能会发生多个连续的事件。对于当前版本的IOS只有第一个触发SPF的事件会被记录在SPF事件日志中。一些老版本的IOS则记录最后一个事件。

在使用RSP4处理器的Cisco 7500系列路由器上，对于少于1000个节点的网络，SPF进程的持续运行时间一般不超过1秒。一个200 MHz的处理器，在每个周期执行一条指令，每秒钟可以执行2亿条指令。考虑到每个节点平均需要执行大约10万个指令以计算SPF树，也就是说1秒钟可以计算出2000个节点的最短生成树。因此，对于一个Level 1的IS-IS网络来说，如果其规模大约为500个节点，则计算最短生成树的时间大约需要250毫秒。请注意这并不是一个绝对的数值，以下的这些因素也会对结果产生影响：

• 网络的实际拓扑结构（全互连或部分互连）；
• 操作系统的类型（允许进程抢占或非抢占）；
• 每个周期实际的指令执行数（某些处理器可以每个周期执行两个指令）；
• 代码的内在优化方法。

如前文所述，SPF算法需要的处理时间与阶数O(LlogN)相关，其中L为链路数量，N为节点数量。logN因子的存在是由于SPF算法每次迭代时均需要对TENT列表进行分类。此外，排序过程的复杂性依赖于节点之间的互连程度。需要注意的是，当一个节点从TENT列表移入PATHS列表时，其所有仍在UNK列表中的直连邻居将移入TENT列表，在此期间执行分类操作。

在每次SPF进程运行将要结束时，只有PATHS列表中的条目能够被选择放入路由器的路由选择表。路由处理器会花费一些周期将IS-IS路由与其他源，例如BGP、静态路由和OSPF等产生的相似路由（相同前缀）进行比较，并将具有最低管理距离的源产生的前缀放入路由选择表。通过Dijkstra算法计算的SPF树将路由器看作是顶点并将路由器通告的IP网段看作是叶子。因此，只与IP前缀相关的网络改变不会导致生成树的整体计算。取而代之的是，路由器会执行部分计算以查找是否存在可替代的IP前缀。当最优路径被选择出来时，路由器同时还会将两个或更多的相似但度量较大的路由保存为备用路由。当最优路径消失时，备用路由将作为可选替代。这就允许Cisco IOS在任何路由变化发生时快速地找到替代路径。由于网络拓扑是通过LSP中通告的邻接关系确定的，邻接关系的丢失意味着拓扑的变化，也就会触发一次SPF算法的整体执行。例如，当一条点到点链路失效时，路由器丢失了与另一端邻居的邻接关系，这是一个拓扑变化的信号，因此，将计划一次SPF的整体执行。但是对于一个例如以太网的广播接口，其可能只有一个IP子网与IP工作站相连，对于此类接口，由于不通过链路与其他IS-IS路由器相连，因此链路的失效仅仅意味着IP子网的丢失而不是邻接关系的丢失。因为IP子网只是SPF树的一片叶子，子网丢失不是网络拓扑变化的标志，因此，仅会运行PRC以寻找替代路径。

对于一台IS-IS路由器的路由处理器来说，三个高开销活动分别是SPF、PRC和LSP生成。在连续发生的事件之间使用延迟可以有效地控制处理器的利用率。表6-2显示了在连续执行的SPF和PRC进程以及相同链路上连续的LSP传递之间的初始等待时间和最小间隔时间。

当一个LSP生成时会被尽可能快地泛洪出去而不经历任何的延迟。但在两个连续的LSP之间至少要经历5秒钟的间隔时间。当路由器收到一个表明邻接关系的变化的LSP时，会延迟5.5秒后运行SPF进程。周期性的SPF的运行需至少间隔10秒。在SPF进程运行或在处理从邻居处收到的LSP时，会暂缓数据传输。由于PRC的运行只涉及叶子信息的计算，当SPF整体执行时，PRC的运行将被阻止。这是由于在SPF整体执行之后，新的拓扑可能出现，将会影响IP路径解析。Cisco IOS中提供的命令可以修改表6-2中所示的默认间隔。可以使用以下的命令分别修改SPF间隔、PRC间隔和LSP生成间隔：

• isis spf-interval
• isis prc-interval
• isis lsp-gen-interval

第7章将讨论IS-IS协议网络设计的建议，并会深入讨论如何通过调整这些计时器以优化IS-IS协议的性能。同时，最近的一个IETF草案研究了IS-IS实施中的收敛特性并建议修改当前的标准和实施方法，从而能够实现毫秒级而不是现在的秒级别的收敛时间。