13. 泛洪过程
- 泛洪过程（The Flooding Procedure）
Link State Update 报文提供了泛洪（flooding）LSA 的机制。一个
Link State Update 报文可以包含若干不同的 LSA，并把每个 LSA 从其
始发点向外泛洪一跳。为使泛洪过程可靠，每个 LSA 必须被单独确认。
确认通过 Link State Acknowledgment 报文传输。多个独立的确认也可以
组合到单个报文中。
泛洪过程在收到 Link State Update 报文时开始。在把收到的报文交给
泛洪过程之前，已经对其做了许多一致性检查（见 8.2 节）。特别地，
该 Link State Update 报文已经与某个特定的邻居和某个特定的区域
相关联。如果该邻居的状态低于 Exchange，则应丢弃该报文而不做进一步
处理。
除 AS-external-LSA 外，所有类型的 LSA 都与某个特定区域关联。但是，
LSA 中并不包含区域字段。LSA 所属的区域必须由 Link State Update
报文头部推断得出。
对于 Link State Update 报文中包含的每个 LSA，执行以下步骤：
(1) 验证该 LSA 的 LS checksum。如果校验和结果无效，则丢弃该 LSA，
并从该 Link State Update 报文中取下一个。
(2) 检查该 LSA 的 LS type。如果 LS type 未知，则丢弃该 LSA，并从
该 Link State Update 报文中取下一个。本规范定义了 LS type
1-5（见 4.3 节）。
(3) 否则，如果这是一个 AS-external-LSA（LS type = 5），而该区域
已被配置为 stub 区域，则丢弃该 LSA，并从该 Link State Update
报文中取下一个。AS-external-LSA 不会被泛洪进入/贯穿 stub
区域（见 3.6 节）。
(4) 否则，如果该 LSA 的 LS age 等于 MaxAge，且路由器的链路状态
数据库中当前不存在该 LSA 的实例，且路由器的所有邻居都不处于
Exchange
或 Loading 状态，则执行以下动作：a) 通过向发送方邻居回送一个
Link State Acknowledgment 报文来确认收到该 LSA（见 13.5 节）；
b) 丢弃该 LSA，并检查 Link State Update 报文中所列的下一个
LSA（如果有的话）。
(5) 否则，找出当前包含在路由器链路状态数据库中的该 LSA 实例。
如果没有数据库副本，或者收到的 LSA 比数据库副本更新（关于
判断哪个 LSA 更新，见下面的 13.1 节），则必须执行以下步骤：
(a) 如果已存在数据库副本，且该数据库副本是通过泛洪接收并且
安装至今不足 MinLSArrival 秒，则丢弃这个新的 LSA（不对其
进行确认），并检查 Link State Update 报文中所列的下一个
LSA（如果有的话）。
(b) 否则，立即把这个新 LSA 从路由器接口的某个子集泛洪出去
（见 13.3 节）。在某些情况下（例如接收接口的状态为 DR，
且该 LSA 是从 Backup DR 以外的路由器收到的），该 LSA 会
被泛洪回接收接口。这种情况应被记录下来，供后续的确认
处理使用（13.5 节）。
(c) 从所有邻居的 Link state retransmission list 中移除当前的
数据库副本。
(d) 把新的 LSA 安装进链路状态数据库（替换当前的数据库副本）。
这可能导致路由表计算被调度执行。此外，用当前时间（即
接收到它的时间）为该新 LSA 打上时间戳。在 MinLSArrival
秒过去之前，泛洪过程不能覆盖这个新安装的 LSA。LSA 的安装
过程在 13.2 节中进一步讨论。
(e) 可能需要通过从接收接口回送一个 Link State Acknowledgment
报文来确认收到该 LSA。这将在下面的 13.5 节中解释。
(f) 如果这个新 LSA 表明它是由接收路由器自身始发的（即被认为
是 self-originated LSA，自始发 LSA），则路由器必须采取
特殊动作：或者更新该 LSA，或者在某些情况下把它从路由域中
清除。关于如何检测并随后处理自始发 LSA 的说明，见 13.4 节。
(6) 否则，如果发送方邻居的 Link state request list 上存在该 LSA
的一个实例，说明 Database Exchange 过程中发生了错误。此时，
通过为该发送方邻居生成邻居事件 BadLSReq 来重启 Database
Exchange 过程，并停止处理该 Link State Update 报文。
(7) 否则，如果收到的 LSA 与数据库副本是同一个实例（即二者都不
更新），则应执行以下两个步骤：
(a) 如果该 LSA 列在接收 adjacency 的 Link state retransmission
list 中，说明路由器自身正在等待该 LSA 的确认。路由器应把
收到的 LSA 视为一次确认，将该 LSA 从 Link state
retransmission list 中移除。这被称为"隐式确认"（implied
acknowledgment）。这种情况应被记录下来，供后续的确认处理
使用（13.5 节）。
(b) 可能需要通过从接收接口回送一个 Link State Acknowledgment
报文来确认收到该 LSA。这将在下面的 13.5 节中解释。
(8) 否则，数据库副本更新。如果该数据库副本的 LS age 等于 MaxAge
且 LS sequence number 等于 MaxSequenceNumber，则直接丢弃收到
的 LSA 而不确认它。（此时该 LSA 的 LS 序列号正在回绕，
MaxSequenceNumber 的 LSA 必须被彻底清除，然后才能引入任何
新的 LSA 实例。）否则，只要该数据库副本在最近 MinLSArrival
秒内没有在 Link State Update 中被发送过，就把数据库副本封装
在一个 Link State Update 报文中回送给发送方邻居。该 Link
State Update 报文应当直接发送给该邻居。这样做时，不要把
该 LSA 的数据库副本放到邻居的 Link state retransmission list
上，也不要确认收到的（较旧的）LSA 实例。
13.1. 判断哪个 LSA 更新
当路由器遇到某个 LSA 的两个实例时，它必须判断哪个更新。上文
在把收到的 LSA 与其数据库副本比较时就发生了这种情况。在
adjacency 建立过程中进行的 Database Exchange 过程中，也必须
做这种比较。
一个 LSA 由它的 LS type、Link State ID 和 Advertising Router
标识。对于同一 LSA 的两个实例，使用 LS sequence number、
LS age 和 LS checksum 字段来判断哪个实例更新：
o LS 序列号较新的 LSA 更新。关于 LS 序列号空间的解释见
12.1.6 节。如果两个实例的 LS 序列号相同，则：
o 如果两个实例的 LS 校验和不同，则 LS 校验和较大（按 16 位
无符号整数比较）的实例被认为更新。
o 否则，如果只有其中一个实例的 LS age 字段被设为 MaxAge，
则年龄为 MaxAge 的实例被认为更新。
o 否则，如果两个实例的 LS age 字段相差超过 MaxAgeDiff，
则 LS age 较小（较年轻）的实例被认为更新。
o 否则，两个实例被认为是相同的。
13.2. 把 LSA 安装进数据库
无论是作为泛洪的结果，还是新的自始发 LSA，把一个新 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-LSA 和 network-LSA
必须重新计算整张路由表，从每个区域的最短路径计算开始
（而不仅仅是链路状态数据库发生变化的那个区域）。之所以
不能把最短路径计算限制在单个发生变化的区域，是因为 AS
boundary router 可能属于多个区域。当前提供最佳路由的那个
区域发生变化，可能迫使路由器改用由另一个区域提供的
intra-area 路由。[19]
Summary-LSA
必须重新计算通向该 summary-LSA 所描述目的地的最佳路由
（见 16.5 节）。如果该目的地是一台 AS boundary router，
则可能还需要重新检查所有 AS-external-LSA。
AS-external-LSA
必须重新计算通向该 AS-external-LSA 所描述目的地的最佳
路由（见 16.6 节）。
另外，当新 LSA 被安装时，该 LSA 的任何旧实例都必须从数据库中
移除。这个旧实例还必须从所有邻居的 Link state retransmission
list 中移除（见第 10 节）。
13.3. 泛洪过程的下一步
当收到一个新的（且更新的）LSA 时，必须把它从路由器接口的某个
集合泛洪出去。本节描述泛洪过程的第二部分（第一部分是第 13 节
中发生的处理），即选择出向接口，并把该 LSA 加入相应邻居的
Link state retransmission list。泛洪过程的这一部分还包括对
邻居 Link state request list 的维护。
本节同样适用于泛洪路由器自身刚刚始发的 LSA（见 12.4 节）。
对于这些 LSA，本节提供了泛洪过程的全部内容（即不执行第 13 节
的处理，因为例如该 LSA 并非从邻居收到，因此不需要被确认）。
取决于 LSA 的 LS type，该 LSA 只能从某些特定接口泛洪出去。
这些接口由下文定义，被称为"合格接口"（eligible interfaces）：
AS-external-LSA（LS Type = 5）
AS-external-LSA 在整个 AS 中泛洪，但 stub 区域除外
（见 3.6 节）。合格接口是路由器的所有接口，但不包括
virtual link 以及那些接入 stub 区域的接口。
所有其他 LS type
所有其他类型都专属于单个区域（Area A）。
合格接口是所有接入 Area A 的接口。如果 Area A 是
backbone，则这还包括所有的 virtual link。
链路状态数据库必须在与上述合格接口关联的所有 adjacency 上
保持同步。这通过在每个合格接口上执行以下步骤来实现。应当注意，
如果所连接的邻居很有可能已经收到了该 LSA，该过程可能决定不
从某个特定接口泛洪该 LSA。但在这些情况下，泛洪过程必须绝对
确保邻居最终确实收到该 LSA，因此该 LSA 仍会被加入每条
adjacency 的 Link state retransmission list。对每个合格接口：
(1) 检查连接到该接口的每个邻居，以确定它们是否必须收到这个
新 LSA。对每个邻居执行以下步骤：
(a) 如果邻居的状态低于 Exchange，则它不参与泛洪，应检查
下一个邻居。
(b) 否则，如果该 adjacency 尚未达到 full（邻居状态为
Exchange 或 Loading），则检查与该 adjacency 关联的
Link state request list。如果列表上存在该新 LSA 的
一个实例，说明相邻路由器已经拥有该 LSA 的一个实例。
把新 LSA 与邻居的副本比较：
o 如果新 LSA 较旧，则检查下一个邻居。
o 如果两个副本是同一实例，则把该 LSA 从 Link state
request list 中删除，并检查下一个邻居。[20]
o 否则，新 LSA 更新。把该 LSA 从 Link state request
list 中删除。
(c) 如果这个新 LSA 就是从该邻居收到的，则检查下一个邻居。
(d) 到这一步，我们尚不能确定该邻居拥有这个新 LSA 的最新
实例。把新 LSA 加入该 adjacency 的 Link state
retransmission list。这确保了泛洪过程是可靠的；该 LSA
将按一定间隔重传，直到看到来自该邻居的确认。
(2) 路由器现在必须决定是否从该接口泛洪这个新 LSA。如果在上一
步中，该 LSA 没有被加入任何 Link state retransmission
list，则不需要从该接口泛洪该 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 报文（把新 LSA 作为其内容）。
当该 LSA 被复制进出向的 Link State Update 报文时，其
LS age 必须增加 InfTransDelay（该值必须 > 0），直到
LS age 字段达到最大值 MaxAge。
在 broadcast 网络上，Link State Update 报文以组播方式发送。
为该 Link State Update 报文指定的目的 IP 地址取决于接口
的状态。如果接口状态为 DR 或 Backup，则应使用
地址 AllSPFRouters。否则，应使用地址 AllDRouters。
在非 broadcast 网络上，必须以单播方式向每个邻接邻居
（即处于 Exchange 或更高状态的邻居）分别发送 Link State
Update 报文。这些报文的目的 IP 地址就是各邻居的 IP 地址。
13.4. 接收自始发的 LSA
路由器通过泛洪过程收到自始发（self-originated）LSA 是一种常见
现象。当出现以下情形之一时，即检测到一个自始发 LSA：1) 该 LSA
的 Advertising Router 等于路由器自己的 Router ID；或 2) 该 LSA
是一个 network-LSA，且其 Link State ID 等于路由器自己的某个
IP 接口地址。
但是，如果收到的自始发 LSA 比路由器实际始发的最后一个实例更新，
则路由器必须采取特殊动作。收到这样的 LSA 表明：路由域中存在
由该路由器在上次重启之前始发的 LSA。在大多数情况下，路由器
随后必须把该 LSA 的 LS 序列号提升到比收到的 LS 序列号大 1，
并始发该 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（后一种情况应当很罕见，它表明自始发该 LSA 以来
路由器的 Router ID 已发生改变）。在所有这些情况下，不应更新
该 LSA，而应通过把收到的 LSA 的 LS age 增加到 MaxAge 并重新
泛洪，把它从路由域中清除（见 14.1 节）。
13.5. 发送 Link State Acknowledgment 报文
每个新收到的 LSA 都必须被确认。这通常通过发送 Link State
Acknowledgment 报文来完成。不过，确认也可以通过发送 Link
State Update 报文隐式地完成（见第 13 节的步骤 7a）。
多个确认可以组合到单个 Link State Acknowledgment 报文中。
这样的报文从收到这些 LSA 的接口回送出去。该报文可以用两种方式
之一发送：延迟发送并由间隔定时器触发，或者直接发送给某个特定
邻居。所采用的具体确认策略取决于收到该 LSA 时的具体情形。
发送延迟确认可以达到几个目的：1) 便于把多个确认打包进单个
Link State Acknowledgment 报文；2) 使单个 Link State
Acknowledgment 报文能够（通过组播）同时向多个邻居表示确认；
3) 使连接到共同网络的各台路由器所发送的 Link State
Acknowledgment 报文随机化。路由器延迟传输之间的固定间隔必须
很短（小于 RxmtInterval），否则将导致不必要的重传。
直接确认是在收到重复 LSA 时，直接发送给某个特定邻居的。直接
确认在收到重复报文时立即发送。在多路访问网络上，这些确认被
直接发送到邻居的 IP 地址。
发送 Link State Acknowledgment 报文的确切过程在表 19 中描述。
收到 LSA 时的各种情形列在左栏。随后采取的确认动作列在右侧
两栏之一中。该动作取决于相关接口的状态；处于 Backup 状态的
接口与处于所有其他状态的接口行为不同。延迟确认必须被送达与
该接口关联的所有邻接路由器。在 broadcast 网络上，这通过以
组播方式发送延迟的 Link State Acknowledgment 报文来实现。
所使用的目的 IP 地址取决于