14. 链路状态数据库的老化
在不同状态下采取的动作
情形 Backup 所有其他状态
_________________________________________________________________
LSA 已经 不发送确认。 不发送确认。
被泛洪回接收
接口（见
第 13 节，步骤 5b）。
_________________________________________________________________
LSA 比 如果该通告是从 发送延迟确认。
数据库副本更新，但 Designated Router
没有被泛洪回接收 收到的，则发送
接口 延迟确认；否则
不做任何事
_________________________________________________________________
LSA 是 如果该通告是从 不发送确认。
重复的，且被当作 Designated Router
隐式确认处理（见 收到的，则发送
第 13 节，步骤 7a）。 延迟确认；否则
不做任何事
_________________________________________________________________
LSA 是 发送直接确认。 发送直接确认。
重复的，且没有被
当作隐式确认
处理。
_________________________________________________________________
LSA 的 LS 发送直接确认。 发送直接确认。
age 等于
MaxAge，且链路状态
数据库中不存在该
LSA 的当前实例，
且路由器的所有邻居
都不处于 Exchange
或 Loading 状态（见
第 13 节，步骤 4）。
表 19：发送链路状态确认。
接口的状态。如果接口状态为 DR 或 Backup，则使用目的地址
AllSPFRouters。在所有其他状态下，使用目的地址 AllDRouters。
在非 broadcast 网络上，延迟的 Link State Acknowledgment 报文
必须在每条 adjacency 上（即状态 >= Exchange 的邻居）分别
以单播方式发送。
以组播方式发送上述报文的理由，用一个例子最能说明。考虑图 15
中描绘的网络配置。假设 RT4 已被选为网络 N3 的 Designated
Router，RT3 被选为 Backup Designated Router。当路由器 RT4 向
网络 N3 泛洪一个新 LSA 时，路由器 RT1、RT2 和 RT3 都会收到它。
这些路由器不会把该 LSA 泛洪回网络 N3，但它们仍必须确保自己的
链路状态数据库与其邻接邻居保持同步。因此 RT1、RT2 和 RT4 都在
等待看到来自 RT3 的确认。同样地，RT4 和 RT3 都在等待看到来自
RT1 和 RT2 的确认。以组播方式发送确认最能达成这一点。
Backup DR 的确认逻辑之所以略有不同，是因为它们在 LSA 泛洪
过程中表现不同（见 13.3 节，步骤 4）。
13.6. 重传 LSA
从某条 adjacency 泛洪出去的 LSA 会被放到该 adjacency 的 Link
state retransmission list 上。为确保泛洪是可靠的，这些 LSA
会被重传直到它们被确认。重传之间的时间间隔是一个可按接口配置
的值 RxmtInterval。如果
某个接口的该值设置得过低，将导致不必要的重传。如果该值设置
得过高，则在丢包情况下泛洪的速度可能受到影响。
若干个重传的 LSA 可以装进单个 Link State Update 报文。当需要
重传 LSA 时，只应发送能装入单个 Link State Update 报文的数量。
每当其中一些 LSA 被确认时，或在重传定时器下次触发时，可以再
发送一个重传报文。
携带重传内容的 Link State Update 报文总是直接发送给邻居。
在多路访问网络上，这意味着重传被直接发送到邻居的 IP 地址。
当每个 LSA 被复制进出向的 Link State Update 报文时，其 LS age
必须增加 InfTransDelay（该值必须 > 0），直到 LS age 字段
达到最大值 MaxAge。
如果相邻路由器宕机，重传可能会持续进行，直到该 adjacency 被
OSPF 的 Hello Protocol 销毁。当 adjacency 被销毁时，Link
state retransmission list 被清空。
13.7. 接收链路状态确认
在把收到的 Link State Acknowledgment 报文交给泛洪过程之前，
已经对其做了许多一致性检查。特别地，它已经与某个特定邻居
相关联。如果该邻居的状态低于 Exchange，则该 Link State
Acknowledgment 报文被丢弃。
否则，对于该 Link State Acknowledgment 报文中的每个确认，
执行以下步骤：
o 被确认的 LSA 在该邻居的 Link state retransmission list 上
是否有一个实例？如果没有，则检查下一个确认。否则：
o 如果该确认针对的是列表上所包含的同一实例，则把该条目从
列表中移除，并检查下一个确认。否则：
o 记录这个可疑的确认，并检查下一个。
14. 链路状态数据库的老化（Aging The Link State Database）
每个 LSA 都有一个 LS age 字段。LS age 以秒为单位表示。当 LSA 保存
在路由器的数据库中时，其 LS age 字段会不断增加。此外，当它被复制
进 Link State Update 报文以便从某个特定接口泛洪出去时，该 LSA 的
LS age 会增加 InfTransDelay。
LSA 的 LS age 绝不会增长超过 MaxAge 值。年龄为 MaxAge 的 LSA 不
用于路由表计算。随着路由器对其链路状态数据库进行老化，某个 LSA
的 LS age 可能达到 MaxAge。[21] 此时，路由器必须尝试把该 LSA 从
路由域中清除。做法很简单：就像它是一个新始发的 LSA 那样重新泛洪
这个 MaxAge LSA（见 13.3 节）。
在为一条新形成的 adjacency 创建 Database summary list 时，链路
状态数据库中存在的任何 MaxAge LSA 都被加入该邻居的 Link state
retransmission list，而不是该邻居的 Database summary list。
更多细节见 10.3 节。
一旦同时满足 a) 某个 MaxAge LSA 不再包含在任何邻居的 Link state
retransmission list 中，以及 b) 路由器的所有邻居都不处于 Exchange
或 Loading 状态，就必须立即把它从路由器的链路状态数据库中移除。
在对链路状态数据库进行老化的过程中，当某个 LSA 的 LS age 达到
CheckAge 的整数倍时，应验证其 LS checksum。如果 LS checksum 不
正确，则说明检测到了程序或内存错误，至少应当重启路由器自身。
14.1. LSA 的提前老化
可以通过把某个 LSA 的 LS age 设为 MaxAge（同时保持其 LS
序列号不变），然后重新泛洪该 LSA，从而把它从路由域中清除。
该过程与清除 LS age 自然达到 MaxAge 值的 LSA 遵循相同的流程
（见第 14 节）。特别地，一旦 a) 该 MaxAge LSA 不再包含在任何
邻居的 Link state retransmission list 中，以及 b) 路由器的
所有邻居都不处于 Exchange 或 Loading 状态，它就会从路由器的
链路状态数据库中被移除。我们把将 LSA 的 LS age 设为 MaxAge
的做法称为"提前老化"（premature aging）。
当自始发 LSA 的序列号字段需要回绕时，就会使用提前老化。此时，
当前的 LSA 实例（其 LS 序列号为 MaxSequenceNumber）必须先被
提前老化并从路由域中清除，然后才能始发一个序列号等于
InitialSequenceNumber 的新实例。更多信息见 12.1.6 节。
提前老化还可以用于以下情形，例如：路由器之前通告过的某条外部
路由已不再可达。在这种情况下，路由器可以通过提前老化把它的
AS-external-LSA 从路由域中清除。该做法优于另一种备选方案，
即为该目的地始发一个 metric 为 LSInfinity 的新 LSA。当在泛洪
过程中意外收到自始发 LSA 时，也会使用提前老化（见 13.4 节）。
路由器只能对它自己的自始发 LSA 进行提前老化。路由器不得对
由其他路由器始发的 LSA 进行提前老化。当出现以下情形之一时，
一个 LSA 被认为是自始发的：1) 该 LSA 的 Advertising Router
等于路由器自己的 Router ID；或 2) 该 LSA 是一个 network-LSA，
且其 Link State ID 等于路由器自己的某个 IP 接口地址。
15. 虚链路（Virtual Links）
单一的 backbone 区域（Area ID = 0.0.0.0）不能被分割，否则自治
系统中的某些区域将变得不可达。为了建立/维持 backbone 的连通性，
可以穿过非 backbone 区域配置 virtual link（虚链路）。virtual link
用于连接 backbone 中在物理上彼此分离的组成部分。virtual link 的
两个端点都是 area border router。该 virtual link 必须在两台路由器
上都进行配置。每台路由器上的配置信息包括：另一个虚拟端点（另一台
area border router），以及这两台路由器共有的那个非 backbone 区域
（称为 Transit area，转接区域）。virtual link 不能穿过 stub 区域
配置（见 3.6 节）。
virtual link 被当作一个属于 backbone、连接这两台 area border
router 的无编号 point-to-point 网络来对待。系统会尝试在该 virtual
link 上建立 adjacency。当这条 adjacency 建立后，该 virtual link
将被包含进 backbone 的 router-LSA 中，并且与 backbone 区域相关的
OSPF 报文将通过该 adjacency 流动。本文中把这样的 adjacency 称为
"virtual adjacency"（虚拟邻接）。
在每个端点路由器上，virtual link 的代价和可用性是通过检查另一个
端点路由器的路由表条目来发现的。（该条目的关联区域必须是所配置的
Transit area。）这被称为该 virtual link 的对应路由表条目。当
virtual link 的对应路由表条目变为可达时，就发生 InterfaceUp 事件。
反之，当其路由表条目变为不可达时，就发生 InterfaceDown 事件。
换言之，virtual link 的可用性由两个端点之间是否存在一条穿过
Transit area 的 intra-area 路径来决定。注意，如果某条 virtual link
的底层路径代价大于十六进制 0xffff（router-LSA 中接口代价的最大
取值），则应认为它不可运行（即视同该路径不存在）。
关于 virtual link 的其他细节如下：
o AS-external-LSA 绝不会在 virtual adjacency 上泛洪。这将是重复
劳动，因为同样的
AS-external-LSA 已经在该 virtual link 的 Transit area 中泛洪
过了。出于同样的原因，在 Database Exchange 过程中也不会在
virtual adjacency 上汇总 AS-external-LSA。
o virtual link 的代价不是配置出来的。它被定义为两台定义该链路
的 area border router 之间 intra-area 路径的代价。该代价出现
在该 virtual link 的对应路由表条目中。当 virtual link 的代价
发生变化时，应为 backbone 区域始发一个新的 router-LSA。
o 正如 virtual link 的代价和可用性由路由表构建过程决定（通过
构建另一端点的路由表条目），virtual interface 的 IP 接口地址
以及 virtual neighbor 的 IP 地址也是如此。这些地址在通过该
virtual link 发送 OSPF 协议报文时使用。注意，当 virtual link
的一个（或两个）端点是通过无编号 point-to-point 链路接入
Transit area 时，可能无法计算出 virtual interface 的 IP 地址
和/或 virtual neighbor 的 IP 地址，从而导致该 virtual link
失效。
o 在每个端点用于 backbone 的 router-LSA 中，该 virtual link 被
表示为一条 Type 4 链路，其 Link ID 设为 virtual neighbor 的
OSPF Router ID，Link Data 设为 virtual interface 的 IP 地址。
更多信息见 12.4.1 节。
o 当且仅当某个非 backbone 区域充当一条或多条完全邻接的 virtual
link 的 Transit area 时，它才能承载转接数据流量（即被认为是
一个 "transit area"）（见第 6 节和 16.1 节中的
TransitCapability）。在把 backbone 网络汇总进这样的区域时
（见 12.4.3 节），以及在路由计算过程中（见 16.3 节），都需要
对这类区域做特殊处理。
o 链路状态重传之间的时间 RxmtInterval 是为 virtual link 配置的。
它应当远大于两台路由器之间的预期往返时延。对 virtual link
而言这
可能难以估计；宁可把它设得过大也不要设得过小。
16. 路由表的计算（Calculation of the routing table）
本节详细说明 OSPF 路由表的计算。路由器以其所连接各区域的链路状态
数据库为输入，运行下面的算法，逐步构建它的路由表。在每一步中，
路由器都必须访问链路状态数据库中的各个独立条目（例如由某台特定
路由器始发的 router-LSA）。这种访问通过 12.2 节讨论的查找功能
执行。查找过程可能返回一个 LS age 等于 MaxAge 的 LSA。这样的 LSA
不应用于路由表计算，应当视同查找过程失败。
OSPF 路由表的组织结构在第 11 节中说明。路由表构建过程的两个示例
在 11.2 节和 11.3 节中给出。该过程可以分解为以下步骤：
(1) 使当前的路由表失效。路由表将从头重新构建。旧的路由表被保存
下来，以便识别路由表条目的变化。
(2) 通过为每个所连接的区域构建最短路径树来计算 intra-area 路由。
特别地，所有 Destination Type 为 "area border router" 的路由
表条目都在这一步中计算。这一步分两部分描述。首先只考虑路由器
与 transit network 之间的链路来构造这棵树。然后把 stub network
纳入该树。在计算区域最短路径树的过程中，还会计算该区域的
TransitCapability，供后面的步骤 4 使用。
(3) 通过检查 summary-LSA 计算 inter-area 路由。如果路由器接入
多个区域（即它是一台 area border router），则只检查 backbone
的 summary-LSA。
(4) 在连接到一个或多个 transit area（即 TransitCapability 被发现
为 TRUE 的非 backbone 区域）的 area border router 上，检查这些
transit area 的 summary-LSA，看看使用这些 transit area 是否
存在比上述步骤 2-3 中所找到的更优的路径。
(5) 通过检查 AS-external-LSA 计算通向外部目的地的路由。AS
boundary router（即始发 AS-external-LSA 的路由器）的位置已在
步骤 2-4 中确定。
步骤 2-5 将在下文进一步详细说明。
这些计算所引起的路由表条目变化，可能导致 OSPF 协议采取进一步的
动作。例如，intra-area 路由的变化将使 area border router 始发新的
summary-LSA（见 12.4 节）。关于路由表变化所引发的 OSPF 协议动作的
完整列表，见 16.7 节。
16.1. 计算区域的最短路径树
该计算产生与某个区域（下文称为 Area A）关联的 intra-area 路由
集合。路由器以自身为根计算最短路径树。[22] 这里最短路径树的
形成分两个阶段完成。在第一阶段，只考虑路由器与 transit network
之间的链路。使用 Dijkstra 算法，从链路状态数据库的这个子集
形成一棵树。在第二阶段，通过考虑到 stub network 的链路，把
叶子节点加入该树。
该过程将使用第 2 节中引入的图论术语来说明。区域的链路状态数据库
被表示为一张有向图。图的顶点是路由器、transit network 和 stub
network。该过程的第一阶段只涉及 transit 顶点（路由器和
transit network）及其连接链路。在整个最短路径计算过程中，
以下数据也与每个 transit 顶点关联：
Vertex (node) ID（顶点标识）
一个 32 位数字，它与顶点类型（router 或 network）一起
唯一标识该顶点。对于 router 顶点，Vertex ID 是该路由器的
OSPF Router ID。对于 network 顶点，它是该网络 Designated
Router 的 IP 地址。
An LSA（一个 LSA）
每个 transit 顶点都有一个关联的 LSA。对于 router 顶点，
这是一个 router-LSA。对于 transit network，这是一个
network-LSA（它实际上由该网络的 Designated Router 始发）。
无论哪种情况，该 LSA 的 Link State ID 总是等于上述的
Vertex ID。
List of next hops（下一跳列表）
从根到该顶点的当前最短路径集合所对应的下一跳列表。由于
等价多路径（equal-cost multipath）能力，可能存在多条最短
路径。每个下一跳指明在向该目的地转发流量时所使用的出向
路由器接口。在 broadcast、Point-to-MultiPoint 和 NBMA
网络上，下一跳还包括通向目的地路径上下一台路由器（如果
有的话）的 IP 地址。
Distance from root（距根的距离）
从根到该顶点的当前最短路径集合的链路状态代价。一条路径的
链路状态代价按其各组成链路的代价之和计算（这些代价在
router-LSA 和 network-LSA 中通告）。如果一条路径的链路
状态代价较小，就称它比另一条"更短"。
该过程的第一阶段（即 Dijkstra 算法）现在可以总结如下。在算法
的每次迭代中，都有一个候选顶点列表。从根到这些顶点的路径已被
找到，但不一定是最短的。不过，通向离根最近的那个候选顶点的
路径保证是最短的；该顶点被加入最短路径树，从候选列表中移除，
并检查它的相邻顶点，以便可能地把它们加入候选列表或修改候选
列表。该