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