然后算法再次迭代. 当候选列表变为空时, 算法终止.
以下步骤详细描述该算法. 请记住, 我们正在为 Area A 计算最短路径树. 下文所有关于链路状态数据库查找的引用, 都是从 Area A 的数据库进行查找.
(1) 初始化算法的数据结构. 清空候选顶点列表. 将最短路径树初始化为只包含根节点, 即执行计算的路由器. 将 Area A 的 TransitCapability 设置为 FALSE.
(2) 将刚加入树的顶点称为 vertex V. 检查与 vertex V 关联的 LSA. 这是基于 Vertex ID 在 Area A 的链路状态数据库中进行的一次查找. 如果这是 router-LSA, 并且 router-LSA 的 bit V (见 Section A.4.2) 被置位, 则将 Area A 的 TransitCapability 设置为 TRUE. 无论如何, LSA 描述的每条链路都会给出到相邻顶点的代价. 对于每条被描述的链路, 假设它连接 vertex V 和 vertex W:
(a) 如果这是到 stub network 的链路, 则检查 V 的 LSA 中的下一条链路. 到 stub network 的链路将在最短路径计算的第二阶段考虑.
(b) 否则, W 是一个 transit vertex (路由器或 transit network). 在 Area A 的链路状态数据库中查找 vertex W 的 LSA (router-LSA 或 network-LSA). 如果该 LSA 不存在, 或其 LS age 等于 MaxAge, 或它没有指回 vertex V 的链路, 则检查 V 的 LSA 中的下一条链路.[23]
(c) 如果 vertex W 已经在最短路径树上, 则检查 LSA 中的下一条链路.
(d) 计算从根到 vertex W 的结果路径的链路状态代价 D. D 等于到 vertex V 的最短路径 (已计算) 的链路状态代价, 加上 vertex V 与 vertex W 之间链路所通告的代价. 如果 D:
o 大于候选列表中 vertex W 已有的值, 则检查下一条链路.
o 等于候选列表中 vertex W 的值, 则计算使用该通告链路所产生的下一跳集合. 该计算的输入是目的地 (W) 及其父节点 (V). 该计算见 Section 16.1.1. 这一跳集合应加入候选列表中 W 已有的下一跳值.
o 小于候选列表中 vertex W 的值, 或者 W 尚未出现在候选列表中, 则将候选列表中 W 的条目设置为表示其到根的距离为 D. 同时计算使用该通告链路所产生的下一跳列表, 并相应设置 W 的下一跳值. 下一跳计算在 Section 16.1.1 中描述; 它以目的地 (W) 及其父节点 (V) 作为输入.
(3) 如果到达此步骤时候选列表为空, 则 transit vertices 的最短路径树已经完全构建, 本阶段过程终止. 否则, 选择候选列表中距离根最近的顶点, 将其加入最短路径树, 并在此过程中从候选列表中移除. 注意, 当有多个顶点同样最接近根时, 必须先选择网络顶点再选择路由器顶点, 这样才能必然找到所有等价代价路径. 这与 OSPF 多播路由扩展 (MOSPF) 所使用的改进 Dijkstra 算法中引入的平局决策规则一致.
(4) 可能修改路由表. 对于被修改的路由表条目, 关联区域将设置为 Area A, 路径类型将设置为 intra-area, 代价将设置为新发现最短路径的计算距离.
如果新加入的顶点是 area border router 或 AS boundary router, 则添加一个目的类型为 "router" 的路由表条目. 关联 router-LSA 中的 Options 字段被复制到路由表条目的 Optional capabilities 字段. 将新加入的顶点称为 Router X. 如果 Router X 是执行计算的路由器某条虚链路的端点, 并且该虚链路使用 Area A 作为 Transit area, 则声明该虚链路 up; 虚接口的 IP 地址被设置为上面为 Router X 计算出的出接口的 IP 地址; 虚邻居的 IP 地址被设置为 Router X 的接口地址, 该地址包含在 Router X 的 router-LSA 中, 并指回最短路径树的根. 等价地说, 这就是指回最短路径树上 Router X 父顶点的接口 (类似 Section 16.1.1 中的计算).
如果新加入的顶点是 transit network, 则定位该网络的路由表条目. 该条目的 Destination ID 是 IP 网络号, 可通过将 Vertex ID (Link State ID) 与其关联的子网掩码 (位于关联 network-LSA 的主体中) 相与获得. 如果路由表条目已存在, 即路由表中已经安装了一条到该目的地的 intra-area route, 则说明多个顶点映射到了同一个 IP 网络. 例如, 在建立新的 Designated Router 时可能出现这种情况. 此时, 只有当新找到的路径同样短, 且当前路由表条目的 Link State Origin 的 Link State ID 小于新加入顶点的 LSA 时, 才应覆盖当前路由表条目.
如果该网络没有路由表条目, 即通常情况, 则应添加一个到该 IP 网络的路由表条目. 该路由表条目的 Link State Origin 应设置为新加入顶点的 LSA.
(5) 返回 Step 2 以迭代算法.
stub networks 在该过程的第二阶段被加入树中. 在此阶段, 会再次检查所有路由器顶点. 那些在上述第一阶段已被判定为不可达的顶点会被丢弃. 对于每个可达的路由器顶点, 称为 V, 会在链路状态数据库中找到关联的 router-LSA. 然后检查该 LSA 中出现的每条 stub network link, 并执行以下步骤:
(1) 计算 stub network 距离根的距离 D. D 等于从根到路由器顶点的距离 (在阶段 1 中计算), 加上 stub network link 所通告的代价. 将该距离与到该 stub network 的当前最佳代价比较. 比较方式是查找该 stub network 当前的路由表条目. 如果计算出的距离 D 更大, 则继续检查 LSA 中的下一条 stub network link.
(2) 如果到达此步骤, 则必须更新该 stub network 的路由表条目. 计算使用该 stub network link 会产生的下一跳集合. 该计算见 Section 16.1.1; 其输入是目的地 (stub network) 和父顶点 (路由器顶点). 如果距离 D 与当前路由表代价相同, 则只需将这一下一跳集合加入路由表条目的下一跳列表. 在这种情况下, 路由表已经有一个 Link State Origin. 如果该 Link State Origin 是 router-LSA, 且其 Link State ID 小于 V 的 Router ID, 则将 Link State Origin 重置为 V 的 router-LSA.
否则, D 小于路由表代价. 通过将路由表条目的代价设置为 D, 并将该条目的下一跳列表设置为新计算出的集合, 来覆盖当前路由表条目. 将该路由表条目的 Link State Origin 设置为 V 的 router-LSA. 然后继续检查下一条 stub network link.
对第二阶段中添加或修改的所有路由表条目, 关联区域将设置为 Area A, 路径类型将设置为 intra-area. 当可达 router-LSA 的列表耗尽时, 第二阶段完成. 此时, 与 Area A 关联的所有区域内路由都已确定.
本规范不要求使用上述两阶段方法计算最短路径树. 但是, 如果使用其他算法, 必须生成相同的树. 因此需要注意, transit vertices 之间的链路必须是双向的, 才能被纳入上述树中. 还应说明, 存在更高效的树计算算法; 例如 [Ref1] 中描述的 incremental SPF algorithm.
16.1.1. 下一跳计算 (The next hop calculation)
本节解释如何计算到某个目的地时应使用的当前下一跳集合. 每个下一跳由用于向目的地转发报文的出接口, 以及下一跳路由器的 IP 地址 (如果有) 组成. 每当发现到目的地的更短路径时, 都会调用下一跳计算. 这可能发生在最短路径树计算的任一阶段 (见 Section 16.1). 在最短路径树计算的阶段 1 中, 当目的地被加入候选列表, 或当候选列表中目的地的条目被修改时 (Stage 1 的 Step 2d), 会找到更短路径. 在阶段 2 中, 每当目的地的路由表条目被修改时 (Stage 2 的 Step 2), 就会发现更短路径.
在最短路径树计算期间, 随着发现越来越短的路径, 可能会多次重新计算到目的地所使用的下一跳集合. 最终, 目的地的路由表条目总会反映绝对最短路径所产生的下一跳.
下一跳计算的输入是 a) 目的地, 以及 b) 当前从根 (执行计算的路由器) 到该目的地的最短路径中的父节点. 该父节点始终是 transit vertex, 即始终是路由器或 transit network.
如果在目的地与根之间当前的最短路径上至少有一个中间路由器, 则目的地直接继承父节点的下一跳集合. 否则, 有两种情况. 第一种情况是父顶点就是根, 即执行计算的路由器自身. 这意味着目的地要么是直连网络, 要么是直连路由器. 此时出接口就是连接到目的网络/路由器的 OSPF 接口. 如果目的地是一个通过 Point-to-MultiPoint network 连接到执行计算路由器的路由器, 则可以通过检查该目的地的 router-LSA 来确定目的地的下一跳 IP 地址: 每条指回执行计算路由器且 Link Data 字段属于该 Point-to-MultiPoint network 的链路, 都提供一个下一跳路由器的 IP 地址. 如果目的地是直连网络, 或是通过点到点接口连接到执行计算路由器的路由器, 则不需要下一跳 IP 地址. 如果目的地是通过虚链路连接到执行计算路由器的路由器, 则下一跳的设置应推迟到 Section 16.3 的计算中进行.
第二种情况是, 父顶点是一个直接连接执行计算路由器和目的路由器的网络. 此时通过检查目的地的 router-LSA 来确定下一跳列表. 对于 router-LSA 中每条指回父网络的链路, 该链路的 Link Data 字段都给出一个下一跳路由器的 IP 地址. 随后可以从下一跳 IP 地址推导出要使用的出接口, 或者从父网络继承该出接口.
16.2. 计算跨区域路由 (Calculating the inter-area routes)
跨区域路由通过检查 summary-LSA 来计算. 如果路由器与多个区域都有活动连接, 则只检查 backbone summary-LSA. 连接到单一区域的路由器检查该区域的 summary-LSA. 无论哪种情况, 下文检查的 summary-LSA 都属于某一个区域的链路状态数据库, 将该区域称为 Area A.