当收到 Link State Update packet 时, 泛洪过程开始. 在收到的报文交给泛洪过程之前, 已经对其执行了许多一致性检查 (见 Section 8.2). 特别是, Link State Update packet 已经与某个特定邻居和某个特定区域关联. 如果该邻居处于低于 Exchange 的状态, 则应丢弃该报文且不再进一步处理.
除 AS-external-LSAs 之外, 所有类型的 LSA 都与特定区域关联. 但是, LSA 本身不包含区域字段. LSA 的区域必须从 Link State Update packet 头部推导出来.
对 Link State Update packet 中包含的每个 LSA, 执行以下步骤:
(1) 验证 LSA 的 LS checksum. 如果校验和无效, 丢弃该 LSA, 并从 Link State Update packet 中取下一个 LSA.
(2) 检查 LSA 的 LS type. 如果 LS type 未知, 丢弃该 LSA, 并从 Link State Update Packet 中取下一个 LSA. 本规范定义了 LS types 1-5 (见 Section 4.3).
(3) 否则, 如果这是 AS-external-LSA (LS type = 5), 且该区域已配置为 stub area, 则丢弃该 LSA, 并从 Link State Update Packet 中取下一个 LSA. AS-external-LSAs 不会被泛洪进入/遍及 stub areas (见 Section 3.6).
(4) 否则, 如果 LSA 的 LS age 等于 MaxAge, 并且路由器的链路状态数据库中当前没有该 LSA 的实例, 且路由器的任何邻居都不处于 Exchange 或 Loading 状态, 则执行以下操作: a) 通过向发送邻居回送 Link State Acknowledgment packet 来确认收到该 LSA (见 Section 13.5), 并且 b) 丢弃该 LSA, 检查 Link State Update packet 中列出的下一个 LSA (如果有).
(5) 否则, 找到路由器链路状态数据库中当前包含的该 LSA 实例. 如果没有数据库副本, 或收到的 LSA 比数据库副本更新 (关于如何判断哪个 LSA 更新, 见下文 Section 13.1), 则必须执行以下步骤:
(a) 如果已经存在数据库副本, 且该数据库副本是通过泛洪收到并在少于 MinLSArrival 秒之前安装的, 则丢弃新的 LSA (不确认), 并检查 Link State Update packet 中列出的下一个 LSA (如果有).
(b) 否则, 立即将新的 LSA 从路由器接口的某个子集泛洪出去 (见 Section 13.3). 在某些情况下, 例如接收接口状态为 DR 且 LSA 是从 Backup DR 以外的路由器收到的, 该 LSA 会被从接收接口泛洪回去. 应记录这一情况, 供确认过程后续使用 (Section 13.5).
(c) 从所有邻居的 Link state retransmission lists 中移除当前数据库副本.
(d) 将新的 LSA 安装到链路状态数据库中, 替换当前数据库副本. 这可能导致调度路由表计算. 此外, 使用当前时间, 即收到该 LSA 的时间, 为新的 LSA 加时间戳. 在 MinLSArrival 秒过去之前, 泛洪过程不能覆盖新安装的 LSA. Section 13.2 进一步讨论 LSA 安装过程.
(e) 可能通过从接收接口发回 Link State Acknowledgment packet 来确认收到该 LSA. 这在下文 Section 13.5 中解释.
(f) 如果这个新 LSA 指示它由接收路由器自身产生, 即被视为 self-originated LSA, 路由器必须采取特殊操作, 要么更新该 LSA, 要么在某些情况下将其从路由域中清除. 关于如何检测并随后处理 self-originated LSAs, 见 Section 13.4.
(6) 否则, 如果发送邻居的 Link state request list 上存在该 LSA 的实例, 则 Database Exchange process 中发生了错误. 在这种情况下, 通过为发送邻居生成邻居事件 BadLSReq 来重启 Database Exchange process, 并停止处理该 Link State Update packet.
(7) 否则, 如果收到的 LSA 与数据库副本是同一个实例, 即二者都不更新, 则应执行以下两个步骤:
(a) 如果该 LSA 列在接收邻接的 Link state retransmission list 中, 说明路由器自身正在等待该 LSA 的确认. 路由器应通过从 Link state retransmission list 中移除该 LSA, 将收到的 LSA 视为确认. 这称为 "implied acknowledgment". 应记录这一情况, 供确认过程后续使用 (Section 13.5).
(b) 可能通过从接收接口发回 Link State Acknowledgment packet 来确认收到该 LSA. 这在下文 Section 13.5 中解释.
(8) 否则, 数据库副本更新. 如果数据库副本的 LS age 等于 MaxAge 且 LS sequence number 等于 MaxSequenceNumber, 则直接丢弃收到的 LSA, 不进行确认. 在这种情况下, 该 LSA 的 LS sequence number 正在回绕, 必须先完全清除 MaxSequenceNumber LSA, 才能引入任何新的 LSA 实例. 否则, 只要数据库副本在最近 MinLSArrival 秒内没有被放入 Link State Update 发送过, 就把数据库副本封装在 Link State Update Packet 中发回发送邻居. Link State Update Packet 应直接发送给该邻居. 这样做时, 不要把该 LSA 的数据库副本放到邻居的 link state retransmission list 上, 也不要确认收到的较旧 LSA 实例.
13.1. 判断哪个 LSA 更新 (Determining which LSA is newer)
当路由器遇到一个 LSA 的两个实例时, 必须判断哪个更新. 上文将收到的 LSA 与其数据库副本比较时就发生了这种情况. 在邻接建立期间发生的 Database Exchange 过程中, 也必须进行这种比较.
LSA 由其 LS type, Link State ID 和 Advertising Router 标识. 对同一个 LSA 的两个实例, 使用 LS sequence number, LS age 和 LS checksum 字段来判断哪个实例更新:
o 具有较新 LS sequence number 的 LSA 更新. 关于 LS sequence number 空间的说明, 见 Section 12.1.6. 如果两个实例具有相同的 LS sequence number, 则:
o 如果两个实例具有不同的 LS checksums, 则 LS checksum 较大的实例 (按 16 位无符号整数看待时) 被认为更新.
o 否则, 如果只有一个实例的 LS age 字段设置为 MaxAge, 则 age 为 MaxAge 的实例被认为更新.
o 否则, 如果两个实例的 LS age 字段相差超过 MaxAgeDiff, 则 LS age 较小 (较年轻) 的实例被认为更新.
o 否则, 两个实例被认为相同.
13.2. 在数据库中安装 LSA (Installing LSAs in the database)
在数据库中安装新的 LSA, 无论是泛洪结果还是新产生的 self-originated LSA, 都可能导致 OSPF 路由表结构重新计算. 应将新 LSA 的内容与旧实例比较, 如果存在旧实例的话. 如果没有差异, 就不需要重新计算路由表. 将 LSA 与其前一个实例比较时, 以下都被视为内容差异:
o LSA 的 Options 字段发生变化.
o 一个 LSA 实例的 LS age 设置为 MaxAge, 而另一个没有.
o LSA 头部中的 length 字段发生变化.
o LSA 的主体, 即 20 字节 LSA 头部之外的任何内容, 发生变化. 注意, 这不包括 LS Sequence Number 和 LS Checksum 的变化.
如果内容不同, 则必须根据新 LSA 的 LS type 字段重新计算路由表的以下部分:
Router-LSAs and network-LSAs
必须重新计算整个路由表, 从每个区域的最短路径计算开始, 而不只是链路状态数据库发生变化的那个区域. 不能把最短路径计算限制在单个变化区域的原因, 与 AS boundary routers 可能属于多个区域这一事实有关. 当前提供最佳路由的区域发生变化, 可能迫使路由器使用另一个区域提供的 intra-area route.[19]
Summary-LSAs
必须重新计算到 summary-LSA 所描述目的地的最佳路由 (见 Section 16.5). 如果该目的地是 AS boundary router, 还可能需要重新检查所有 AS-external-LSAs.
AS-external-LSAs
必须重新计算到 AS-external-LSA 所描述目的地的最佳路由 (见 Section 16.6).
此外, 安装新的 LSA 时必须从数据库中移除该 LSA 的任何旧实例. 这个旧实例还必须从所有邻居的 Link state retransmission lists 中移除 (见 Section 10).
13.3. 泛洪过程的下一步 (Next step in the flooding procedure)
当收到新的且更新的 LSA 时, 必须从路由器接口的某个集合泛洪出去. 本节描述泛洪过程的第二部分, 第一部分是 Section 13 中发生的处理: 选择出接口, 并把 LSA 加入相应邻居的 Link state retransmission lists. 泛洪过程的这一部分还包括维护邻居的 Link state request lists.
本节同样适用于泛洪路由器自身刚刚产生的 LSA (见 Section 12.4). 对于这些 LSA, 本节提供完整的泛洪过程; 即不执行 Section 13 的处理, 因为例如该 LSA 不是从邻居收到的, 因而不需要确认.
根据 LSA 的 LS type, LSA 只能从某些接口泛洪出去. 这些接口按如下定义, 称为 eligible interfaces:
AS-external-LSAs (LS Type = 5)
AS-external-LSAs 会在整个 AS 中泛洪, stub areas 除外 (见 Section 3.6). eligible interfaces 是路由器的所有接口, 但不包括虚链路以及连接到 stub areas 的接口.
All other LS types
所有其他类型都特定于单个区域 (Area A). eligible interfaces 是所有连接到 Area A 的接口. 如果 Area A 是 backbone, 则包括所有虚链路.
在与上述 eligible interfaces 关联的所有邻接关系上, 链路状态数据库必须保持同步. 这是通过在每个 eligible interface 上执行以下步骤完成的. 应注意, 如果高度可能已连接邻居已经收到该 LSA, 该过程可能决定不从某个特定接口泛洪 LSA. 但是, 在这些情况下, 泛洪过程必须绝对确信邻居最终会收到该 LSA, 因此 LSA 仍会加入每个邻接关系的 Link state retransmission list. 对每个 eligible interface:
(1) 检查连接到该接口的每个邻居, 以判断它们是否必须接收新的 LSA. 对每个邻居执行以下步骤:
(a) 如果邻居处于低于 Exchange 的状态, 它不参与泛洪, 应检查下一个邻居.
(b) 否则, 如果邻接尚未完全建立 (邻居状态为 Exchange 或 Loading), 则检查与该邻接关联的 Link state request list. 如果列表中有新 LSA 的一个实例, 说明相邻路由器已经有该 LSA 的实例. 将新的 LSA 与邻居的副本比较:
o 如果新的 LSA 较旧, 则检查下一个邻居.
o 如果两个副本是同一个实例, 则从 Link state request list 中删除该 LSA, 并检查下一个邻居.[20]
o 否则, 新的 LSA 更新. 从 Link state request list 中删除该 LSA.
(c) 如果新的 LSA 是从该邻居收到的, 则检查下一个邻居.
(d) 此时我们不能确定该邻居已经拥有这个新 LSA 的最新实例. 将新的 LSA 加入该邻接的 Link state retransmission list. 这确保泛洪过程可靠; 该 LSA 会按间隔重传, 直到看到来自邻居的确认.
(2) 路由器现在必须决定是否从该接口泛洪新的 LSA. 如果在前一步中, 该 LSA 没有被加入任何 Link state retransmission lists, 则无需从该接口泛洪 LSA, 应检查下一个接口.
(3) 如果新的 LSA 是在此接口上收到的, 并且来自 Designated Router 或 Backup Designated Router, 则所有邻居很可能已经收到该 LSA. 因此, 检查下一个接口.
(4) 如果新的 LSA 是在此接口上收到的, 且接口状态为 Backup, 即路由器自身是 Backup Designated Router, 则检查下一个接口. Designated Router 会在此接口上执行泛洪. 不过, 如果 Designated Router 失效, 该路由器, 即 Backup Designated Router, 最终会重传这些更新.
(5) 如果到达此步骤, 必须从该接口泛洪 LSA. 从该接口发送 Link State Update packet, 并把新的 LSA 作为内容包含其中. 将 LSA 复制到出向 Link State Update packet 时, 必须把 LSA 的 LS age 增加 InfTransDelay (该值必须 > 0), 直到 LS age 字段达到最大值 MaxAge.
在广播网络上, Link State Update packets 会多播. 为 Link State Update Packet 指定的目的 IP 地址取决于接口状态. 如果接口状态为 DR 或 Backup, 应使用地址 AllSPFRouters. 否则, 应使用地址 AllDRouters.
在非广播网络上, 必须以单播方式向每个相邻邻居, 即处于 Exchange 或更高状态的邻居, 发送单独的 Link State Update packets. 这些报文的目的 IP 地址是邻居的 IP 地址.
13.4. 接收 self-originated LSAs (Receiving self-originated LSAs)
路由器通过泛洪过程收到 self-originated LSAs 是常见情况. 当满足以下任一条件时, 检测为 self-originated LSA: 1) LSA 的 Advertising Router 等于路由器自身的 Router ID, 或 2) 该 LSA 是 network-LSA, 且其 Link State ID 等于路由器自身某个 IP 接口地址.
但是, 如果收到的 self-originated LSA 比路由器实际产生的最后一个实例更新, 路由器必须采取特殊操作. 收到这样的 LSA 表明, 路由域中存在路由器上次重启之前产生的 LSA. 在大多数情况下, 路由器随后必须把 LSA 的 LS sequence number 提升到收到的 LS sequence number 之后的下一个值, 并产生该 LSA 的新实例.
路由器可能不再希望产生收到的 LSA. 可能的例子包括: 1) 该 LSA 是 summary-LSA 或 AS-external-LSA, 而路由器不再有到该目的地的可通告路由; 2) 该 LSA 是 network-LSA, 但路由器不再是该网络的 Designated Router; 或 3) 该 LSA 是 network-LSA, 其 Link State ID 是路由器自身的一个 IP 接口地址, 但其 Advertising Router 不等于路由器自身的 Router ID. 最后一种情况应很少见, 并表明路由器的 Router ID 自产生该 LSA 以来发生了变化. 在所有这些情况下, 不应更新该 LSA, 而应通过把收到的 LSA 的 LS age 增加到 MaxAge 并重新泛洪, 将该 LSA 从路由域中清除 (见 Section 14.1).
13.5. 发送 Link State Acknowledgment packets (Sending Link State Acknowledgment packets)
每个新收到的 LSA 都必须确认. 这通常通过发送 Link State Acknowledgment packets 完成. 不过, 也可以通过发送 Link State Update packets 隐式完成确认 (见 Section 13 的 step 7a).
多个确认可以组合到单个 Link State Acknowledgment packet 中. 这样的报文从收到 LSA 的接口发回. 该报文可以用两种方式之一发送: 延迟后在 interval timer 上发送, 或直接发送给某个特定邻居. 使用哪种具体确认策略取决于收到 LSA 时的情况.
发送延迟确认可实现几件事: 1) 便于把多个确认打包进单个 Link State Acknowledgment packet, 2) 使单个 Link State Acknowledgment packet 能够通过多播同时向多个邻居表示确认, 以及 3) 随机化连接到同一公共网络的各路由器发送的 Link State Acknowledgment packets. 路由器延迟发送之间的固定间隔必须较短 (小于 RxmtInterval), 否则会产生不必要的重传.
直接确认是响应收到重复 LSA 而直接发送给特定邻居的确认. 收到重复 LSA 时会立即发送直接确认. 在多路访问网络上, 这些确认直接发送到邻居的 IP 地址.
发送 Link State Acknowledgment packets 的精确过程在 Table 19 中描述. 收到 LSA 时的情况列在左列. 随后采取的确认动作列在右侧两列之一. 该动作取决于相关接口的状态; 状态为 Backup 的接口与所有其他状态的接口行为不同. 延迟确认必须递送给与该接口关联的所有相邻路由器. 在广播网络上, 这是通过把延迟的 Link State Acknowledgment packets 作为多播发送来完成的. 使用的 Destination IP address 取决于