OSPF | LSDB 链路状态数据库 / SPF 算法 / 实验

注：本文为 “OSPF | LSDB / SPF ” 相关文章合辑。

LSDB 和 SPF 算法

潇湘浪子的蹋马骨汤发布 2019-02-15 23:58:46

1. 链路状态数据库 (LSDB)

链路状态协议除了执行洪泛扩散链路状态通告（LSA）以及发现邻居等任务外，其第三个任务是建立链路状态数据库。链路状态数据库将接收到的 LSA 以一系列记录的形式存储。尽管 LSA 中包含年龄、序列号及其他信息，但这些信息主要用于管理 LSA 的洪泛扩散进程。对于最短路径的决策进程而言，通告路由器 ID、连接网络和邻居路由器以及网络与邻居相关联的代价，是至关重要的信息。

LSA 中包含两类通用信息：
1.路由器链路信息：通过三元组（路由器 ID，邻居 ID，代价）来通告邻居路由器。其中，代价指的是该链路到邻居的代价。
2.末梢网络信息：使用三元组（路由器 ID，网络 ID，代价）来通告与路由器直接相连的末梢网络。

最短路径优先算法对路由器链路信息进行计算，以构建到达每台路由器的最短路径树，随后利用末梢网络信息添加网络。

在这里插入图片描述

上述图示中的网络包含路由器以及路由器之间的链路。为简化展示，图中未包含末梢网络。需注意，部分链路两端的代价并不相同。这是因为代价是依据接口的出站方向进行计算的，且在一个网络中，所有链路的代价并非必须完全一致。例如，从路由器 RB 到路由器 RC 的链路代价为 1，而对于同一条链路，从 RC 到 RB 的代价则为 5。

以下为拓扑图所示网络的链路状态数据库的大致内容：

在这里插入图片描述

2.SPF 算法

SPF 算法中的三个数据库：

1.树数据库：通过向该数据库中添加链路，实现向最短路径树中添加分支。当算法执行完毕时，此数据库能够描述最短路径树。
2.候选对象数据库：按照规定的顺序，从链路状态数据库中复制链路至该数据库，作为向树数据库添加的候选对象。算法结束时，该数据库为空。
3.链路状态数据库：存储着网络中的所有链路。

SPF 算法计算过程：

第 1 步：路由器对树数据库进行初始化，将自身设定为树的根节点，其代价为 0。
第 2 步：查看链路状态数据库，将所有描述通向根节点的路由器邻居链路的三元组添加至候选对象数据库中。
第 3 步：计算从根节点到每条链路的代价，将候选对象数据库中代价最小的链路添加到树数据库中。若存在两条或多条链路到根节点的最小代价相同，则选择其中一条进行添加。
第 4 步：检查已添加到树数据库中的邻居 ID，除了已经添加到树数据库中的三元组之外，将链路状态数据库中描述路由器邻居的三元组全部添加到候选对象数据库中。
第 5 步：若候选对象数据库中仍有剩余表项，则返回第 3 步继续执行。若候选对象数据库为空，则终止算法。在算法终止时，树数据库中的每个单一的邻居 ID 表项将对应表示一台路由器，此时，最短路径树构建完成。
第 6 步：添加末梢网络，至此，SPF 算法执行完毕。

以拓扑图中的路由器 A 为例，计算其最短路径树：

在这里插入图片描述

OSPF 之链路状态数据库 LSDB

晚风挽着浮云发布 2022-02-04 14:47:00

OSPF 链路状态数据库

原理概述：

开放最短路径优先（OSPF）是一种基于链路状态的动态路由协议。在 OSPF 网络中，每台 OSPF 路由器都会生成相应的链路状态通告（LSA），并将这些 LSA 进行通告。路由器在接收到 LSA 后，会将其存储在链路状态数据库（LSDB）中。

LSA 存在多种不同的类型，不同类型的 LSA 具有不同的功能和作用，以下为几种常见的 LSA 类型介绍：

1.Type-1 LSA (Router LSA)：每台路由器均会产生此类 LSA，用于描述路由器的直连链路状态以及开销值。Type-1 LSA 仅能在所属区域内部进行泛洪，无法泛洪到其他区域。

2.Type-2 LSA (Network LSA)：由指定路由器（DR）产生，主要用于描述该 DR 所在网段的网络掩码，以及该网段内连接的路由器信息。Type-2 LSA 同样只能在所属区域内部泛洪，不能泛洪到其他区域。

3.Type-3 LSA (Network Summary LSA)：由区域边界路由器（ABR）产生。ABR 路由器会将其所连接区域的 Type-1 和 Type-2 LSA 转换为 Type-3 LSA，以描述区域间的路由信息。Type-3 LSA 可以在整个自治域（AS, Autonomous System）内部进行泛洪，但不能泛洪到完全末梢区域（Totally Stub 区域）和完全非纯末梢区域（Totally NSSA, Not-So-Stubby Area）。

4.Type-4 LSA (ASBR Summary LSA)：由自治系统边界路由器（ASBR）所在区域的 ABR 产生，用于描述到达 ASBR 的路由信息。Type-4 LSA 可以在整个 AS 内部泛洪，但不能泛洪到末梢区域（Stub 区域）、完全末梢区域、非纯末梢区域（NSSA 区域）和完全非纯末梢区域中。

5.Type-5 LSA (AS External LSA)：由 ASBR 产生，用于描述到达 AS 外部网络的路由信息。Type-5 LSA 能够在整个 AS 内部泛洪，但不能泛洪到末梢区域、完全末梢区域、NSSA 区域和完全 NSSA 区域中。

6.Type-6 LSA (Group Membership LSA)：在组播 OSPF（MOSPF）中，用于标识组播组成员，应用于用户组播路由。

7.Type-7 LSA (NSSA LSA)：由 NSSA 区域或完全 NSSA 区域的 NSSA ASBR 产生，用于描述到达 AS 外部的路由信息。Type-7 LSA 仅能出现在所属的 NSSA 区域或完全 NSSA 区域内部。

实验目的：

深入理解 OSPF 中不同类型 LSA 的具体作用。
熟悉 OSPF 中不同类型 LSA 的泛洪范围。
掌握 LSA 中重要字段的含义。

实验拓扑：

1：首先基础配置

1.R1：

#
interface GigabitEthernet0/0/0ip address 10.0.12.1 255.255.255.0
#
interface GigabitEthernet0/0/1
#
interface GigabitEthernet0/0/2
#
interface NULL0
#
interface LoopBack0ip address 10.0.1.1 255.255.255.255
#
interface LoopBack1ip address 192.168.1.1 255.255.255.0

2.R2：

#
interface GigabitEthernet0/0/0ip address 10.0.12.2 255.255.255.0
#
interface GigabitEthernet0/0/1ip address 10.0.235.2 255.255.255.0
#
interface GigabitEthernet0/0/2
#
interface NULL0
#
interface LoopBack0ip address 10.0.2.2 255.255.255.255

3.R3：

#
interface GigabitEthernet0/0/0ip address 10.0.34.3 255.255.255.0
#
interface GigabitEthernet0/0/1ip address 10.0.235.3 255.255.255.0
#
interface GigabitEthernet0/0/2
#
interface NULL0
#
interface LoopBack0ip address 10.0.3.3 255.255.255.255

4.R4：

#
interface GigabitEthernet0/0/0ip address 10.0.34.4 255.255.255.0
#
interface GigabitEthernet0/0/1
#
interface GigabitEthernet0/0/2
#
interface NULL0
#
interface LoopBack0ip address 10.0.4.4 255.255.255.255
#
interface LoopBack1ip address 172.16.1.1 255.255.255.0

5.R5：

#
interface GigabitEthernet0/0/0ip address 10.0.235.5 255.255.255.0
#
interface GigabitEthernet0/0/1
#
interface GigabitEthernet0/0/2
#
interface NULL0
#
interface LoopBack0ip address 10.0.5.5 255.255.255.255

2：配置 OSPF 路由协议

1.R1：

#
ospf 1area 0.0.0.1network 10.0.1.1 0.0.0.0network 10.0.12.0 0.0.0.255network 192.168.1.0 0.0.0.255

2.R2：

#
ospf 1area 0.0.0.0network 10.0.235.0 0.0.0.255area 0.0.0.1network 10.0.2.2 0.0.0.0network 10.0.12.0 0.0.0.255

3.R3：

#
ospf 1area 0.0.0.0network 10.0.235.0 0.0.0.255area 0.0.0.2network 10.0.3.3 0.0.0.0network 10.0.34.0 0.0.0.255

4.R4：

#
ospf 1area 0.0.0.2network 10.0.4.4 0.0.0.0network 10.0.34.0 0.0.0.255network 172.16.1.0 0.0.0.255

5.R5：

#
ospf 1area 0.0.0.0network 10.0.5.5 0.0.0.0network 10.0.235.0 0.0.0.255

在 R3 上查看 OSPF 的指定路由器（DR）与备份指定路由器（BDR）的选举情况：

由上述结果可知，在 R2、R3、R5 组成的广播网络中，当前 R5 被选举为 DR，R2 被选举为 BDR。接下来查看每台路由器的路由表：
1.R1：

2.R2：

3.R3：

4.R4：

5.R5：

从上述路由表信息可以看出，每台路由器均已获取到非直连网络的路由条目。接下来使用 ping 命令检测网络的连通性：

由 ping 命令的结果可知，各个网段之间的通信正常。

区域 1 为普通区域，区域 2 为非纯末梢区域（NSSA 区域），区域 1 的 R1 和区域 2 的 R4 都需要引入 Loopback 1 接口所连接的外部网络路由。在 R1 和 R4 上使用路由策略（Route-Policy）精确匹配 Loopback 1 接口的直连路由，并将其引入 OSPF 进程。

R1:
#
ospf 1import-route direct route-policy 10area 0.0.0.1network 10.0.1.1 0.0.0.0network 10.0.12.0 0.0.0.255network 192.168.1.0 0.0.0.255
#
route-policy 10 permit node 1if-match acl 2000
R4:
#
ospf 1description mcuimport-route direct route-policy 10area 0.0.0.2network 10.0.4.4 0.0.0.0network 10.0.34.0 0.0.0.255network 172.16.1.0 0.0.0.255
#
route-policy 10 permit node 1if-match acl 2000

配置完成后，在 R5 上查看由 R1 和 R4 引入的两条路由：

从图中可以看出，在 R5 的路由表中，这两条路由都显示为 O_ASE，且优先级与开销也都相同，不同之处是这两条路由的下一跳，因为它们是由不同的路由器发送给 R5 的。

3：查看 Type-1 LSA，Type-2 LSA，Type-3 LSA

在区域 0 的 R5 上查看链路状态数据库（LSDB）。

可以看到，R5 的 LSDB 中共有 5 种 LSA，它们分别是路由器链路通告（Router LSA，或称 Type-1 LSA）、网络链路通告（Network LSA，或称 Type-2 LSA）、网络汇总链路通告（Sum-Net LSA，或称 Type-3 LSA，Network Summary LSA）、自治系统边界路由器汇总链路通告（Sum-Asbr LSA，或称 Type-4 LSA、ASBR Summary LSA）和外部链路通告（External LSA，或称 Type-5 LSA，AS External LSA）。

在 R5 上查看 Router-ID 为 10.0.2.2 产生的 Router LSA 的详细信息：

显示信息中的部分参数含义如下：
-Type：在显示信息中，Type 表示 LSA 的类型，此处表示的是 Router LSA。不同类型的 LSA 作用和泛洪区域范围不同。Router LSA 描述了路由器的直连链路或接口，泛洪范围为所在区域内部，以便本区域其他路由器了解其直连链路或接口的状态信息。
-Ls id：对于 Router LSA，Ls id 就是产生该 Router LSA 的路由器的 Router-ID。
-Adv rtr：Adv rtr 描述了 LSA 由哪台路由器产生。对于 Router LSA 来讲，Adv rtr 就是产生该 Router LSA 的路由器的 Router-ID。
-Seq#：每条 LSA 都会维护一个 Seq#（序列号），产生这条 LSA 的路由器默认每 30 秒的周期泛洪这条 LSA，每次泛洪时，序列号加 1。LSA 的序列号越大，表明这条 LSA 越新。
-Chksum：chksum（校验和）用于校验 LSA 的完整性。所有的 LSA 都会保存在路由器的 LSDB 中，每 5 分钟会计算一次。如果路由器收到同一条 LSA 且序列号相同，则会比较它们的校验和，校验和越大，相应的 LSA 越新。
-Ls age：Ls age 指 LSA 的老化时间，表示 LSA 已经存活了多长时间，最大值为 3600 秒。当一台路由器产生一条 LSA 时，会将 LSA 的老化时间设置为 0。LSA 产生之后，无论是停留在路由器的 LSDB 内，还是在传递过程中，老化时间都会不断增加。为防止因 LSA 过期造成路由回馈，路由器会每隔 30 分钟泛洪自己产生的 LSA。若序列号与校验和的比较都无法确定最新的 LSA 时，则会比较老化时间。在 LSDB 中，如果老化时间相差大于 15 分钟以上，则 Ls age 的值越小，说明 LSA 越新；如果相差在 15 分钟内，则认为两条 LSA 一样。

在上述显示信息中，Link count 以上的参数信息通常被称为 LSA 头部信息，Link count 及以下部分为具体的链路描述信息。Link count 标识了这条 LSA 描述的链路信息数量。对于点到点（P-2-P）链路类型，Link ID 是指链路上邻居接口的 IP 地址；对于传输网络（TranNet）链路类型，Link ID 是指 DR 接口的 IP 地址。Data 是指自身接口的 IP 地址，Link Type 是指接口的链路类型，Metric 是指路由器自己到达这条链路的 Cost 值。需要说明的是，OSPF 协议会把广播（Broadcast）和非广播多路访问（NBMA）这两种具有多路访问能力的网络都视为 TransNet 网络。

由上述信息可知，R2 的 Router LSA 描述了自己连接到某个 TransNet 网络，网络的 DR 接口的 IP 地址为 10.0.235.5（R5），自己使用 10.0.235.2 连接到该网络中，且到达这个网络的 Cost 值为 1。

Network LSA 由 DR 产生，其主要作用是描述 TransNet 网络的掩码信息以及连接到 TransNet 网络的路由器信息。在多路访问网络中，没必要每台路由器都产生 Network LSA，否则会导致 Network LSA 重复。

R5 是 TransNet 网络的 DR，在 R5 上查看它产生和发送的 Network LSA 的详细信息：

可以看到，这条 Network LSA 说明了 TransNet 网络的掩码为 255.255.255.0，连接到这个 TransNet 网络的路由器有 10.0.5.5（R5）、10.0.3.3（R3）。Network LSA 中未携带路径的开销，原因是 Router LSA 已经描述了自己到 TransNet 网络的 Cost 值。

在 R2、R3、R5 上查看区域 0 的 LSDB：

可以发现，R2、R3、R5 的 LSDB 中区域 0 的 Router LSA 和 Network LSA 完全一样。

Router LSA 和 Network LSA 可以完整描述本区域的网络拓扑，但这些 LSA 不能泛洪到其他区域。当 OSPF 网络包含多个区域时，仅依靠 Router LSA 和 Network LSA 无法进行区域间路由计算，区域间路由计算需要利用 Sum-Net LSA 来实现。ABR 路由器会将自己相连区域的 Router LSA 和 Network LSA 转换为 Sum-Net LSA，然后泛洪到其他区域。

R2 同时连接了区域 0 和区域 1，所以是一台 ABR 路由器。查看 R2 的 LSDB：

可以看到，R2 的区域 0 中有一条 LinkState ID 为 10.0.12.0 的 Sum-Net LSA，它的 AdvRouter 为 10.0.2.2。网段 10.0.12.0/24 本属于区域 1 的网络，现在被 ABR 路由器 R2 转换为 Sum-Net LSA 并泛洪到了区域 0 中。10.0.235.0/24 本属于区域 0 的网络，现在被 ABR 路由器 R2 转换为 Sum-Net LSA 并泛洪到了区域 1 中。实际上，Sum-Net LSA 是 ABR 利用自己相连区域的 Router-LSA 和 Network-LSA 计算得到的路由信息。

在 R2 上查看 LinkState ID 为 10.0.12.1 的这条 Sum-Net LSA 的详细信息：

可以看到，这条 LSA 的 Type 为 Sum-Net，Ls id 表明目的网络地址为 10.0.12.0，Net mask 表明目的网络的掩码为 255.255.255.0，metric 表明 ABR 路由器 R2 去往目的网络的 Cost 值为 1。

在 R5 上查看 LSDB，并查看路由表中关于 10.0.12.0/24 的路由信息：

可以看到，R5 的 LSDB 中存在 10.0.12.0 这条 Sum-Net LSA，R5 的路由表中关于 10.0.12.0/24 这条路由信息表明 R5 去往 10.0.12.0/24 的 Cost 为 2。R5 通过这条 Sum-Net LSA 得知网络中存在 10.0.12.0/24 网段，这个网段的 AdvRouter 为 10.0.2.2（R2），R2 到达 10.0.12.0/24 的 Cost 为 1，R5 和 R2 同属区域 0，所以 R5 可以通过 Router LSA 和 Network LSA 计算出自己到 R2 的 Cost 为 1。因此，R5 可以计算出自己到 10.0.12.0/24 的 Cost 值为 1 + 1 = 2。

区域间的路由是根据 Sum-Net LSA，并结合 Router LSA 及 Network-LSA 计算出来的。对于某个区域的一台 OSPF 路由器来说，它无需了解其他区域的链路状态信息，但可以通过 Sum-Net LSA 并结合 Router-LSA 及 Network-LSA 计算出区域间路由。计算区域间路由时，采用的不再是链路状态算法，而是距离矢量算法。

在 R2 上查看 LinkState ID 为 10.0.34.0/24 这条 LSA 的信息：

可以看到，10.0.34.0/24 属于区域 2 的网络，ABR 路由器 R3 将关于 10.0.34.0/24 的路由信息以 Sum-Net LSA 的方式通告进了区域 0，Cost 为 1。然后，ABR 路由器 R2 又继续将此信息以 Sum-Net LSA 的方式通告进了区域 0。

对于 ABR 来说，如果在自己相连的某个区域的 LSDB 中存在某条 Sum-Net LSA，并且这条 Sum-Net LSA 的 AdvRouter 不是自己的 Router-ID 时，就会将这条 Sum-Net LSA 的 AdvRouter 修改为自己的 Router-ID，并重新计算自己到达这条 Sum-Net LSA 的 Cost 值，然后将其泛洪到与自己相连的其他区域中。

4：查看 Type-4 LSA 和 Type-5 LSA

路由器可以通过 Router LSA 和 Network LSA 计算区域内的路由，可以通过 Sum-Net LSA 并结合 Router LSA 和 Network LSA 计算区域间的路由，可以通过 Sum-Asbr LSA 和 External LSA 计算 AS 外部的路由。

R1 的 Loopback 1 是外部路由，被 ASBR 路由器 R1 引入到了 OSPF 网络中，查看 R1 的 LSDB：

可以看到，R1 的 LSDB 中存在一条 Type 为 External，LinkState ID 为 192.168.1.0，AdvRouter 为 10.0.1.1 的 LSA。在 R1 上查看这条 LSA 的其他信息：

可以看到，这条 LSA 的 Type 是 External，AdvRouter 为 10.0.1.1（R1）。这条 LSA 实际上是一条目的网络为 192.168.1.0/24 的 AS 外部路由，显示信息中的 E Type（External Type）的值为 2。

External LSA 可以在整个 AS 内部泛洪（但不能泛洪到 Stub 区域、Totally Stub 区域、NSSA 区域和 Totally NSSA 区域中），在泛洪过程中其各个参数不会改变。查看 R2、R3、R4、R5 的 LSDB 中是否也存在这条 LSA。

在 R5 上使用 display ospf abr-asbr 命令查看到达 ABR 和 ASBR 的 Cost 值：

可以看到，从 R5 到达 ABR 路由器 R2 的 Cost 值为 1，从 R5 到达 ASBR 路由器 R1 的 Cost 值为 2。由此可见，R5 其实是通过 Router LSA 和 Network LSA 先计算出到达 ABR 路由器 R2 的 Cost 值，然后加上 Sum-Asbr LSA 所表示的从 ABR 路由器 R2 到达 ASBR 路由器 R1 的 Cost 值。

[R1] ospf
[R1-ospf-1] un im
[R1-ospf-1] un import-route dir
[R1-ospf-1] un import-route direct

在 R5 上查看 LSDB：

5：查看 Type-7 LSA

NSSA 区域不允许 External LSA 存在，但 NSSA 区域允许通过 import-route 命令引入外部路由。那么，如何描述 NSSA 区域中的 AS 外部路由呢？NSSA 区域引入的外部路由不能以 External LSA 的形式出现，而是使用 NSSA LSA 来描述 NSSA 区域中的 AS 外部路由，且 NSSA LSA 只能出现在 NSSA 区域中。NSSA LSA 由 NSSA 区域的 NSSA ASBR 产生。

R4 为 NSSA 区域的 ASBR，查看 R4 的 LSDB：

可以看到，R4 为外部路由 172.16.1.0 产生了相应的 NSSA LSA。在 R4 上查看这条 LSA 的详细信息：

可以注意到，NSSA LSA 的参数信息基本上和 External LSA 相同。

NSSA LSA 是特殊类型的 LSA，只会出现在 NSSA 区域中，不能泛洪到其他任何区域。那么其他区域的路由器如何计算去往 NSSA LSA 所表示的外部网络的路由呢？

原来，NSSA 区域的 ABR 会将 NSSA LSA 转换为 External LSA，并泛洪到其他区域。

R3 为 NSSA 区域的 ABR 路由器，在 R3 上查看 LSDB 信息：

可以看到，由 10.0.4.4 产生的 NSSA LSA 被 R3 转换成了 External LSA，并泛洪到其他区域。

via:

链路状态与 SPF 算法解析 - CSDN 博客 潇湘浪子的蹋马骨汤于 2019-02-15 23:58:46 发布
https://blog.csdn.net/yueyadao/article/details/87398664
- SPF算法详解：最短路径优先原理与路由计算-CSDN博客
  https://blog.csdn.net/m0_37565736/article/details/114033861
OSPF 之链路状态数据库 LSDB_ospf lsdb-CSDN 博客 晚风挽着浮云于 2022-02-04 14:47:00 发布
https://blog.csdn.net/weixin_57636278/article/details/122783120