SPF計算過程
概述
講完了LSDB我們來看SPF計算過程。這個過程會比較複雜，大家可以去反複的練習，學習一下：
- Phase 1：建構SPF樹
- 根據Router-LSA和Network-LSA中的拓普資訊，建構SPF樹幹。
- Phase 2：計算最優路由。
- 基于SPF樹幹和Router-LSA、Network-LSA的路由資訊，計算最優路由。
1、首先SPF算法我們要根據Router-LSA和Network-LSA中的拓撲資訊來去建構一個SPT樹幹。也就是說現在我相當于要種一顆樹，對于這棵樹來說它的枝幹是最重要的，我把枝幹搭起來之後，我再在上面去長葉子。
什麼是葉子呢？
對于OSPF來說，它的路由就是挂在樹幹上的葉子，也就是第二個步驟，計算一個最優的路由。
2、基于SPF樹幹和Router-LSA和Network-LSA中的路由資訊，來去計算一個最優路由。
這是SPF算法的兩個過程：
- 首先計算拓撲資訊，這個拓撲資訊就類似于它的樹幹。
- 第二個，有了樹幹我再把路由葉子挂在這個樹幹上，并且在計算完成之後我必須要保證這顆拓撲樹是無環的拓撲樹。
執行個體
我們來看一下具體是怎麼去建構SPF樹的：
在我們的網絡中每一台路由器都有自己的拓撲樹，每一台路由器都認為自身是樹的根節點。
這裡就以RTA為例，RTA的拓撲樹就認為我是根的開始，那麼RTA就會作為根節點。然後去檢視我自己的LSDB，并且是我自己生成的1類LSA。然後我就會看到兩個拓撲資訊，最後一個是路由資訊，我們先不看，先要建構樹的話我們要看拓撲資訊。
這裡的兩個拓撲資訊，一個是廣播多路通路網絡，一個是點對點，我們先來看廣播多路通路網絡：
Link ID：
10.1.12.2，這個是我們DR的接口IP。
Data：
10.1.12.1。這個是我連接配接DR的接口IP位址。這個時候我就知道了，我有個DR的接口IP位址是10.1.12.1。
然後第二個是我們的點對點網絡：
Link id：
3.3.3.3，這個很明顯是一個拓撲資訊，我有一個鄰居它的Router-id是3.3.3.3。
data：
我連接配接這個鄰居的接口IP位址是10.1.13.1，是我自己的接口IP位址，這是兩個需要去注意的拓撲資訊。
然後我們把它加入到候選清單中。這個時候我們就可以畫出一個節點，這個節點是DR，DR的接口IP位址是10.1.12.1。
我們可以看到這個點對點的網絡其實就結束了，它再往下展開也沒有什麼可以展開的了。但是這個廣播多路通路網絡或者是NBMA網絡肯定是可以往下展開的，因為我們不知道他具體的拓撲資訊。
我們這裡隻知道DR，那麼DROther是誰呢，我們不知道，是以我們還需要去檢視對應的2類LSA。
那麼2類LSA由誰去生成呢？就是10.1.12.2去生成。
我們可以檢視DR的LSDB【display ospf lsdb network 10.1.12.2】，去檢視DR的接口IP位址生成的LSA。
在這裡我們根據2類LSA，我們可以發現這個廣播多路通路和非廣播多路通路網絡中，隻有兩台路由器：
- 一條是RTB，2.2.2.2。
- 另外一台是RTA，1.1.1.1。
那麼我們就大概知道了這個拓撲資訊。實際上它們兩個是直連的。我們可以認為中間的黃色路由器是一個僞節點，即一個虛拟的節點，不需要去管它。
此時RTA的拓撲資訊我們都已經看完了，我們知道它有一個廣播多路通路網絡，或者是非廣播多路通路網絡。我們還知道它有一個點對點的鄰居關系。
接着我們就要繼續往下面去看，我們可以去看什麼？
因為我們知道我有一個鄰居是RTB，我們就可以【display ospf lsdb router 2.2.2.2】，這裡就是去檢視2.2.2.2這台路由器的router-LSA，即1類LSA。在這裡我們可以看到有3條資訊：
Link Type：
第一條資訊是TransNet。
Link ID：
10.1.12.2。
Data：
10.1.12.2。
這裡我們可以看到，我和DR相連的接口IP是相同的，證明2.2.2.2這個路由器就是DR。
這個是一個小技巧的判斷，如果Link ID和data是一緻的，就說明我們這個路由器在本網絡中就是一個DR的角色。
我們可以發現這個網段在之前是一個RTA和RTB的鄰居關系，這個類型描述的就是RTA和RTB的鄰居關系，我們已經看過了，不用再看了。
接着我們發現一個新的Link id和data都為10.1.235.2，可以看到link id和我的data完全一緻：
Link id：
DR的接口IP位址。
Data：
我與DR相連的接口IP位址。
兩個人完全一緻說明RTB這個路由器是一個DR，但是隻能判斷自己是DR，具體這個DR連接配接哪一個BDR，連接配接哪一個DRother我也不清楚。
我們先知道這個資訊。然後接着往後看：
Link id：
4.4.4.4。
Data：
10.1.24.2。
Link Type：
點對點。說明我有一個點對點的鄰居關系。
Metric：
48。
那麼我們把後面兩個有用的資訊再去加入到候選清單中：
在這裡這個候選清單中，我們首先第一個節點是RTB這台DR，即10.1.235.2，這裡我們要計算它的開銷。
- 這裡從RTA到RTB的開銷是1，再從RTB到MA網絡的開銷又是1，是以它的開銷最後是等于2的。
- 然後第二個，4.4.4.4也是一緻的，我們從RTA到RTB，它的一個開銷是1，此時RTB到另一個鄰居的關系，即4.4.4.4也就是RTD。此時RTB到我的點對點鄰居4.4.4.4的開銷是48，總共為49.
我們可以看一下，假如我們還有一個路由器是48，此時RTB到達4.4.4.4的開銷是48。再去換算的話就是累加的，RTA到達RTB的開銷是1，RTB到4.4.4.4的開銷是48，加起來就是49了。
這個是一個簡單的帶寬的疊加，我們可以注意一下。
接着往後看，在之前我們針對于RTB的檢視中，我們可以發現RTB在另外的一個網段也是一個DR的角色。
這個網段是10.1.235.2的這個網段，現在我們就想看一下，具體10.1.235.2它的DR和BDR、DRother的鄰居關系是什麼樣的呢？
一樣的，我們【display ospf lsdb network 10.1.235.2】，在這裡我們可以看到在這一個MA網段中我們可以看到有3個鄰居，RTB、RTC和RTE這三個鄰居關系。
是以我們可以把網絡畫出來，除了RTB在這個網絡中還連接配接了兩台路由器，RTC和RTE，即3.3.3.3和5.5.5.5。
此時再去計算RTA到RTC和RTE的Metric值，這個計算是很簡單的：
RTA到達RTB的Metric值是1，然後RTB到達其他的RTC、RTE的Metric值也是1，那麼兩個疊加起來就等于2了，這個是非常簡單的。
然後我們再去注意一下，在這個候選清單的過程中我們發現之前有一個點對點的鄰居關系。我們可以回顧一下：
在最早最早開始的時候，我們去檢視RTA上自己生成的1類LSA的時候，我們可以看到RTA和RTC有一個點對點的鄰居關系Metric是48。
然後經過我們繼續往下去周遊，去計算的時候，我們發現針對于這個RTC，我們還有另外的路徑可以走，相當于有兩條路：
- 一種是通過P2P的路徑去走。
- 一種是通過MA網絡的路走過去。
通過MA網絡的路走到RTC，它的Metric值明顯要小，隻有2。而通過點對點的路徑走過去，要48的開銷，比較大。
是以我們把這個候選節點給它删掉，因為它并不是一個最優的路徑。
接着我們繼續往後看，在RTB上面，其實我們已經把RTB所有的路由資訊都看完了，接着就到了RTC，也就是3.3.3.3。
在RTC上我們繼續來看一下：
- 我們可以看到它有兩個路由資訊10.1.235.2，這個路由資訊其實就是下面這一塊，這塊我們已經檢查過了，不用再去檢查。
- 另外就是1.1.1.1，也就是RTC這個路由器，它和RTA之間還互連着。這個互連的鄰居關系是點對點的。
其實這個鍊路類型的話，我們也在RTA的1類LSA中檢視過了，也就是我們上面提到過的被删掉的候選路徑。
接着我們來看RTE，最後一台路由器，為什麼要看最後一台路由器呢？因為其實最開始的4.4.4.4我們已經有了相應的鄰居關系，其實可以不用去檢視了。
當然如果我們想去檢視的話也可以檢視一遍，當然去檢視的話情況是和RTC一緻的，我們會發現它裡面的類型都已經在之前的周遊中已經描述過了，這是一個比較多餘的動作，我們在這裡因為時間關系省略了。
如果我們想去看一下RTD，即4.4.4.4的鄰居的關系，包括網絡的資訊，也是可以的。
最後我們來看一下RTE，5.5.5.5這個路由器的1類LSA。
檢視1類LSA：
- 首先我們的TransNet網絡我們已經看過了，就不用再看了。
- 接着我們再來檢視點對點網絡，發現點對點網絡有一個鄰居關系是4.4.4.4。我們可以看到在圖中可能是這樣子，但是我們明顯看到這已經是一個環路了。
我們之前就講過了SPF樹是一個無環的最短路徑樹，我們必須要保證它是沒有環路的。
我們可以看一下，要保證沒有環路是很簡單的，我們選擇從RTA到達4.4.4.4的最優路徑就能保證無環了。
我們現在這裡有兩條路：
- RTA->RTB->4.4.4.4。
- RTA->RTB->5.5.5.5->4.4.4.4。
我們選擇一個最優的路線走就可以了。通過這個圖中很明顯：
- 從RTA到達4.4.4.4，經過RTA->RTB->4.4.4.4這條路線的話，它的Metric值是1+48，最後等于49。
- 另外一條計算RTA->RTB->5.5.5.5->4.4.4.4，RTB到達多路通路網絡，再通過5.5.5.5，再到4.4.4.4，這條路線的Metric的值明顯是更大的。即1+1+48，很明顯是等于50。
這裡并不是一個最優的鍊路，是以我們就不去選它，最後我們把候選加入到總的清單的是，開銷為49的路徑。
計算最優路由
- 從根節點開始一次添加各節點LSA中的路由資訊。
- 添加順序為各節點加入SPF樹的順序。
最後我們從RTA出發，計算出了RTA自己的SPF樹。然後根據這個SPF樹，我們知道StubNet，我們把每一個StubNet都加入到樹幹上去，這個時候就相當于加入了不同的葉子。
然後我們再根據SPF樹，去計算出到每一個葉子的Metric值，來進行一個累加和疊加，這個就是我們計算最優路徑的一個過程。