SPF算法介紹

當鍊路狀态路由算法建構完LSDB後，接下來節要調用SPF算法，對LSDB内的LSA進行處理，計算出所有路徑。SPF算法在《Routing TCP/IP volmun I》的OSPF章節中有描述。

SPF算法簡單描述如下（LSDB已收斂）：

一、標明根節點；

二、周遊該標明節點的所有直連節點。周遊過程中，若根與某節點的分支為

l 新分支，則添加該分支到分支清單，并記錄分支的權重、根的下一跳；

l 已存在于分支清單，則與分支清單中已存在分支的權重值比較優劣，并把較優值更新到分支清單中；

l 已存在于權重清單，則忽略；

三、把分支清單中的最優分支移出至權重清單，并標明該分支的節點；

四、若分支清單非空，則繼續步驟三；否則算法結束。

算法結束後，權重清單即為最短路徑樹，用于生成路由表或其它後續工作。

下面舉個簡單例子，箭頭方向為節點配置鍊路權重（metric），注意權重是單向的，修改權重一般情況下要確定兩端一緻。a為運作SPF算法的節點，LSDB已收斂：

<a href="http://blog.51cto.com/attachment/201207/162254240.png" target="_blank"></a>

*下述顯示含義為節點(下一跳) 權重

一、SPF把a、b、c、d、e、f、g、h置為未周遊狀态，并以本節點（R1）為根。添加a(a)到權重清單，權重為0，下一跳為a。接着周遊a的直連節點b、c、d，并把b(b) 50，c(c) 85，d(d) 20添加到分支清單。其中d(d)的權重最優，為20。添加d(d)到權重清單，權重為20，下一跳為d，并標明d；

二、周遊d所有連接配接的節點。這裡d-b 20，d-c 20，d-g 20，d-h 20。分支清單中b(b)從50改為40，下一跳改為d；c(c)從85改為40，下一跳改為d；添加g(d) 40，h(d) 40。這時分支清單包含：b(d) 40，c(d) 40,g(d) 40,h(d) 40。添加b(d)到權重清單，權重為40，下一跳為d，并標明b；

三、周遊b所有連接配接的節點。這裡分支為b-e 80，b-d 20，由于d已以被添加到權重清單，不再考慮。分支清單中添加e(d) 120。這時分支清單包含：c(d) 40，g(d) 40，h(d) 40，e(d) 120。添加c(d)到權重清單，權重為40，下一跳為d，并標明c；

四、周遊c。這裡分支為c-f 20，c-d 20，由于d已被添加到權重清單，不再考慮。分支清單添加f(d) 60。這時分支清單包含：g(d) 40，h(d) 40，e(d) 120，f(d) 60。添加g(d) 到權重清單，權重為40，下一跳為d，并標明g；

五、周遊g。g分支為g-e 20，g-h 50。分支清單修改e(d) 60。這時分支清單包含：h(d) 40，e(d) 60，f(d) 60。添加h(d)到權重清單，權重為40，下一跳為d，并標明h；

六、周遊h。h分支為h-g 50，h-f 20。g已被添加到權重清單，不考慮；而a-d-c-f和a-d-h-f同為60，下一跳同為d，該新分支與分支清單中的分支并無差異。這時分支清單包含：e(d) 60，f(d) 60。添加e(d)到權重清單，權重為60，下一跳為d，并標明e；

七、周遊e。分支為e-b 80，e-g 20，由于b、g已在權重清單，分支清單無需改變，為f(d) 60。添加f(d)到權重清單，權重為60，下一跳為d。

八、由于分支清單為空，是以SPF算法結束。這時權重清單為：

節點

a

d

b

c

g

e

f

權重

下一跳

20

40

60

本文轉自 gole_huang 51CTO部落格，原文連結:http://blog.51cto.com/golehuang/920865