跳到主要内容

14. 链路状态数据库老化 (Aging The Link State Database)

                                 Action taken in state

Circumstances Backup All other states

LSA has been No acknowledgment No acknowledgment flooded back out sent. sent. receiving interface (see Section 13, step 5b).

LSA is more Delayed acknowledg- Delayed acknowledg- recent than database ment sent if adver- ment sent. copy, but was not tisement received flooded back out from Designated receiving interface Router, otherwise do nothing

LSA is a duplicate, Delayed acknowledg- No acknowledgment and was treated as ment sent if adver- sent. an implied acknow- tisement received ledgment (see from Designated Section 13, step Router, otherwise 7a). do nothing

LSA is a duplicate, Direct acknowledg- Direct acknowledg- and was not treated ment sent. ment sent. as an implied acknowledgment.

LSA's LS age is Direct acknowledg- Direct acknowledg- equal to MaxAge, ment sent. ment sent. and there is no current instance of the LSA in the link state database, and none of router's neighbors are in states Exchange or Loading (see Section 13, step 4).

         Table 19: 发送 link state acknowledgements.


    取决于接口状态. 如果接口状态为 DR 或 Backup, 则使用目的地 AllSPFRouters. 在所有其他状态中, 使用目的地 AllDRouters. 在非广播网络上, 延迟的 Link State Acknowledgment packets 必须在每条邻接上分别单播发送, 即发送给状态 >= Exchange 的邻居.

    通过一个示例最容易解释为什么上述报文要作为多播发送. 考虑 Figure 15 中描绘的网络配置. 假设 RT4 已被选为 Network N3 的 Designated Router, RT3 被选为 Backup Designated Router. 当 Router RT4 向 Network N3 泛洪一个新的 LSA 时, routers RT1, RT2 和 RT3 会收到它. 这些路由器不会把该 LSA 泛洪回 net N3, 但它们仍必须确保自己的链路状态数据库与相邻邻居保持同步. 因此 RT1, RT2 和 RT4 都在等待看到来自 RT3 的确认. 同样, RT4 和 RT3 也都在等待看到来自 RT1 和 RT2 的确认. 通过多播发送确认最能实现这一点.

    Backup DR 的确认逻辑略有不同, 原因是它们在 LSA 泛洪期间执行的功能不同 (见 Section 13.3, step 4).


13.6.  重传 LSA (Retransmitting LSAs)

    从某条邻接泛洪出去的 LSA 会放入该邻接的 Link state retransmission list. 为确保泛洪可靠, 这些 LSA 会一直重传直到被确认. 重传之间的时间长度是可按接口配置的值 RxmtInterval. 如果接口上该值设置过低, 会导致不必要重传. 如果该值设置过高, 在丢包时泛洪速度可能受到影响.

    多个重传的 LSA 可能可以放入单个 Link State Update packet. 当要重传 LSA 时, 应只发送一个 Link State Update packet 能容纳的数量. 当某些 LSA 被确认时, 或在重传定时器下一次触发时, 可以发送另一包重传.

    携带重传的 Link State Update Packets 始终直接发送给邻居. 在多路访问网络上, 这意味着重传直接发送到邻居的 IP 地址. 将每个 LSA 复制到出向 Link State Update packet 时, 必须将其 LS age 增加 InfTransDelay (该值必须 > 0), 直到 LS age 字段达到最大值 MaxAge.

    如果相邻路由器 down, 重传可能持续到邻接被 OSPF 的 Hello Protocol 销毁. 当邻接被销毁时, Link state retransmission list 被清空.


13.7.  接收 link state acknowledgments

    收到的 Link State Acknowledgment packet 在交给泛洪过程之前已经经过许多一致性检查. 特别是, 它已与某个特定邻居关联. 如果该邻居处于低于 Exchange 的状态, 则丢弃该 Link State Acknowledgment packet.

    否则, 对 Link State Acknowledgment packet 中的每个确认执行以下步骤:

    o   被确认的 LSA 是否在该邻居的 Link state retransmission list 中有实例? 如果没有, 检查下一个确认. 否则:

    o   如果该确认针对的是列表中包含的同一实例, 从列表中移除该项并检查下一个确认. 否则:

    o   记录该可疑确认, 并检查下一个.

14. 链路状态数据库老化 (Aging The Link State Database)

每个 LSA 都有一个 LS age 字段. LS age 以秒表示. 当 LSA 包含在路由器数据库中时, 其 LS age 字段会递增. 此外, 当 LSA 被复制到 Link State Update Packet 以从特定接口泛洪出去时, 其 LS age 会增加 InfTransDelay.

LSA 的 LS age 永远不会递增超过 MaxAge. age 为 MaxAge 的 LSA 不用于路由表计算. 当路由器老化其链路状态数据库时, 某个 LSA 的 LS age 可能达到 MaxAge.[21] 此时, 路由器必须尝试从路由域中清除该 LSA. 这只需像新产生 LSA 一样重新泛洪 MaxAge LSA 即可 (见 Section 13.3).

为新形成的邻接创建 Database summary list 时, 链路状态数据库中存在的任何 MaxAge LSA 都会加入邻居的 Link state retransmission list, 而不是加入邻居的 Database summary list. 更多细节见 Section 10.3.

一旦同时满足 a) MaxAge LSA 不再包含在任何邻居 Link state retransmission lists 中, 且 b) 路由器的任何邻居都不处于 Exchange 或 Loading 状态, 就必须立即将该 MaxAge LSA 从路由器链路状态数据库中移除.

在链路状态数据库老化过程中, 当 LSA 的 LS age 达到 CheckAge 的倍数时, 应验证其 LS checksum. 如果 LS checksum 不正确, 则检测到程序或内存错误, 路由器自身至少应重启.


14.1.  LSA 的提前老化 (Premature aging of LSAs)

    可以通过将 LSA 的 LS age 设置为 MaxAge、保持其 LS sequence number 不变, 然后重新泛洪该 LSA, 从路由域中清除 LSA. 此过程与清除 LS age 自然达到 MaxAge 值的 LSA 走同样流程 (见 Section 14). 特别是, 一旦 a) MaxAge LSA 不再包含在任何邻居 Link state retransmission lists 中, 且 b) 路由器的任何邻居都不处于 Exchange 或 Loading 状态, 就从路由器链路状态数据库中移除 MaxAge LSA. 我们把将 LSA 的 LS age 设置为 MaxAge 称为 "premature aging".

    当 self-originated LSA 的 sequence number 字段即将回绕时, 使用 premature aging. 此时, 当前 LSA 实例 (其 LS sequence number 为 MaxSequenceNumber) 必须提前老化并从路由域中清除, 然后才能产生 sequence number 等于 InitialSequenceNumber 的新实例. 更多信息见 Section 12.1.6.

    当例如路由器先前通告的某条外部路由不再可达时, 也可以使用 premature aging. 在这种情况下, 路由器可以通过 premature aging 从路由域中清除其 AS-external-LSA. 此过程优于替代方案, 即为该目的地产生一个指定 metric 为 LSInfinity 的新 LSA. 在泛洪过程中意外收到 self-originated LSAs 时, 也会使用 premature aging (见 Section 13.4).

    路由器只能提前老化自己的 self-originated LSAs. 路由器不得提前老化由其他路由器产生的 LSA. 当满足以下任一条件时, LSA 被视为 self-originated: 1) LSA 的 Advertising Router 等于路由器自身的 Router ID; 或 2) LSA 是 network-LSA, 且其 Link State ID 等于路由器自身某个 IP 接口地址.

15. 虚链路 (Virtual Links)

单一 backbone area (Area ID = 0.0.0.0) 不能断开, 否则 Autonomous System 的某些区域将变得不可达. 为建立/维护 backbone 连通性, 可以通过非 backbone 区域配置虚链路. 虚链路用于连接物理上分离的 backbone 组件. 虚链路的两个端点是 area border routers. 虚链路必须在两台路由器中都配置. 每台路由器中的配置信息由另一虚端点 (另一台 area border router), 以及两台路由器共有的非 backbone 区域 (称为 Transit area) 组成. 虚链路不能通过 stub areas 配置 (见 Section 3.6).

虚链路被视为属于 backbone、并连接两台 area border routers 的未编号点到点网络. 会尝试在虚链路上建立邻接关系. 当该邻接建立时, 虚链路将包含在 backbone router-LSAs 中, 与 backbone area 相关的 OSPF 报文将流经该邻接. 本文档将这种邻接称为 "virtual adjacency".

在每个端点路由器中, 通过检查到另一端点路由器的路由表条目来发现虚链路的代价和可用性. 该条目的关联区域必须是配置的 Transit area. 这称为虚链路的对应路由表条目. 当虚链路的对应路由表条目变为可达时, 虚链路发生 InterfaceUp 事件. 相反, 当其路由表条目变为不可达时发生 InterfaceDown 事件. 换句话说, 虚链路的可用性由两个端点之间是否存在一条通过 Transit area 的 intra-area path 决定. 注意, 如果虚链路底层路径代价大于十六进制 0xffff (router-LSA 中接口代价的最大大小), 则应认为该虚链路不可运行, 即与路径不存在一样处理.

关于虚链路的其他细节如下:

o   AS-external-LSAs NEVER 在虚邻接上泛洪. 这会重复工作, 因为相同的 AS-external-LSAs 已经在虚链路的 Transit area 中泛洪. 出于同样原因, 在 Database Exchange 过程中, 不会在虚邻接上汇总 AS-external-LSAs.

o   虚链路的代价 NOT configured. 它定义为两个定义它的 area border routers 之间 intra-area path 的代价. 该代价出现在虚链路的对应路由表条目中. 当虚链路代价变化时, 应为 backbone area 产生新的 router-LSA.

o   正如虚链路的代价和可用性由路由表构建过程决定 (通过构造到另一端点的路由表条目), 虚接口的 IP interface address 和虚邻居的 IP address 也由该过程决定. 它们在通过虚链路发送 OSPF 协议报文时使用. 注意, 当一个或两个虚链路端点通过未编号点到点链路连接到 Transit area 时, 可能无法计算虚接口的 IP 地址和/或虚邻居的 IP 地址, 从而导致虚链路失败.

o   在每个端点用于 backbone 的 router-LSA 中, 虚链路表示为 Type 4 link, 其 Link ID 设置为虚邻居的 OSPF Router ID, Link Data 设置为虚接口的 IP 地址. 更多信息见 Section 12.4.1.

o   非 backbone 区域当且仅当它充当一条或多条完全邻接虚链路的 Transit area 时, 才能承载 transit data traffic, 即被视为 "transit area" (见 Sections 6 和 16.1 中的 TransitCapability). 将 backbone networks 汇总到这种区域时需要特殊处理 (见 Section 12.4.3), 路由计算期间也需要特殊处理 (见 Section 16.3).

o   虚链路配置 link state retransmissions 之间的时间 RxmtInterval. 该值应显著大于两台路由器之间的预期往返时延. 对虚链路来说这可能难以估计; 宁可把它设得过大.

16. 路由表计算 (Calculation of the routing table)

本节详细说明 OSPF 路由表计算. 路由器以其连接区域的链路状态数据库作为输入, 运行以下算法, 逐步构建路由表. 在每一步中, 路由器都必须访问链路状态数据库的单独片段, 例如某台路由器产生的 router-LSA. 该访问由 Section 12.2 中讨论的 lookup function 执行. lookup 过程可能返回 LS age 等于 MaxAge 的 LSA. 这样的 LSA 不应用于路由表计算, 并视为 lookup 过程失败.

OSPF 路由表组织在 Section 11 中解释. Sections 11.2 和 11.3 展示了两个路由表构建过程示例. 该过程可分为以下步骤:

(1) 当前路由表被置为无效. 路由表从头重新构建. 保存旧路由表, 以便识别路由表条目变化.

(2) 通过为每个连接区域构建最短路径树来计算 intra-area routes. 特别是, Destination Type 为 "area border router" 的所有路由表条目都在此步骤中计算. 此步骤分两部分描述. 首先只考虑路由器与 transit networks 之间的链路来构造树. 然后将 stub networks 纳入树中. 在区域最短路径树计算期间, 还会计算该区域的 TransitCapability, 供 Step 4 后续使用.

(3) 通过检查 summary-LSAs 来计算 inter-area routes. 如果路由器连接到多个区域, 即它是 area border router, 则只检查 backbone summary-LSAs.

(4) 在连接到一个或多个 transit areas 的 area border routers 中, 即 TransitCapability 被发现为 TRUE 的非 backbone 区域, 检查这些 transit areas 的 summary-LSAs, 以查看是否存在比上面 Steps 2-3 中找到的路径更好的经 transit areas 的路径.

(5) 通过检查 AS-external-LSAs 计算到外部目的地的路由. AS boundary routers (产生 AS-external-LSAs 的路由器) 的位置已在 steps 2-4 中确定.


Steps 2-5 在下文进一步详细解释.

这些计算导致的路由表条目变化可能使 OSPF 协议采取进一步动作. 例如, intra-area route 的变化会导致 area border router 产生新的 summary-LSAs (见 Section 12.4). 路由表变化导致的 OSPF 协议动作完整列表见 Section 16.7.


16.1.  计算区域的最短路径树

    该计算产生与某个区域关联的 intra-area routes 集合, 下文称该区域为 Area A. 路由器以自身为根计算最短路径树.[22] 这里最短路径树的形成分两个阶段完成. 第一阶段只考虑路由器和 transit networks 之间的链路. 使用 Dijkstra algorithm, 从链路状态数据库的这个子集形成一棵树. 第二阶段通过考虑到 stub networks 的链路, 将叶节点加入树中.

    该过程将使用 Section 2 中引入的图术语解释. 区域的链路状态数据库表示为有向图. 图的顶点是路由器、transit networks 和 stub networks. 过程的第一阶段只涉及 transit vertices (路由器和 transit networks) 及其连接链路. 在整个最短路径计算中, 每个 transit vertex 还关联以下数据:

    Vertex (node) ID
        一个 32 位编号, 与 vertex type (router 或 network) 一起唯一标识该顶点. 对 router vertices, Vertex ID 是路由器的 OSPF Router ID. 对 network vertices, 它是网络 Designated Router 的 IP 地址.

    An LSA
        每个 transit vertex 都有关联 LSA. 对 router vertices, 这是 router-LSA. 对 transit networks, 这是 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-LSAs 和 network-LSAs 中通告). 如果一条路径具有更小的链路状态代价, 就称它比另一条路径 "shorter".


    该过程第一阶段, 即 Dijkstra algorithm, 现在可概述如下. 在算法每次迭代中, 都有一个候选顶点列表. 从根到这些顶点的路径已经找到, 但不一定是最短路径. 但是, 到距离根最近的候选顶点的路径保证是最短的; 该顶点被加入最短路径树, 从候选列表中移除, 并检查其相邻顶点是否可能加入候选列表或修改候选列表. 该
最后于 更新