SPF算法

SPF算法

SPF算法也被稱為Dijkstra算法,這是因為最短路徑優先算法SPF是由荷蘭計算機科學家狄克斯特拉於1959年提出的。 SPF算法將每一個路由器作為根(ROOT)來計算其到每一個目的地路由器的距離,每一個路由器根據一個統一的資料庫會計算出路由域的拓撲結構圖,該結構圖類似於一棵樹,在SPF算法中,被稱為最短路徑樹。

SPF算法是OSPF路由協定的基礎。SPF算法有時也被稱為Dijkstra算法,這是因為最短路徑優先算法SPF是Dijkstra發明的。SPF算法將每一個路由器作為根(ROOT)來計算其到每一個目的地路由器的距離,每一個路由器根據一個統一的資料庫會計算出路由域的拓撲結構圖,該結構圖類似於一棵樹,在SPF算法中,被稱為最短路徑樹。在OSPF路由協定中,最短路徑樹的樹幹長度,即OSPF路由器至每一個目的地路由器的距離,稱為OSPF的Cost,其算法為:Cost = 100×(10)^6/鏈路頻寬 .

在這裡,鏈路頻寬以bps來表示。也就是說,OSPF的Cost 與鏈路的頻寬成反比,頻寬越高,Cost越小,表示OSPF到目的地的距離越近。舉例來說,FDDI或快速乙太網的Cost為1,2M串列鏈路的Cost為48,10M乙太網的Cost為10等。

SPF算法是OSPF路由協定的基礎。在OSPF路由協定中,最短路徑樹的樹幹長度,即OSPF路由器至每一個目的地路由器的距離,稱為OSPF的Cost,其算法為:Cost = 100×10/鏈路頻寬。

SPF使用開銷(cost)作為度量值。開銷被分配到路由器的每個接口上,默認情況下,一個接口的開銷以100 M為基準自動計算得到。到某個特定目的地的路徑開銷是這台路由器到目的地之間的所有鏈路出接口的開銷之和。

為了從LSA資料庫中生成路由表,設備運行Dijkstra最短路徑優先算法構建最短路徑樹,以本設備自己作為路由樹的根。Dijkstra算法計算出到網路上每一個節點的開銷最低的路徑,設備將這些路徑的路由存入自己的路由表。

OSPF不是簡單地周期性廣播它所有的路由選擇信息。OSPF交換機使用hello報文保持鄰居關係。如果一台交換機在一段特定的時間內(dead-interval)沒有收到來自鄰居的hello報文,則認為這個鄰居可能已經不存在了。OSPF路由刷新是遞增式的,交換機通常只在拓撲結構發生改變時發出刷新信息。當LSA的年齡達到1800秒(LSA刷新間隔,LSRefreshTime)時,則傳送一個該LSA的更新。

相關詞條

相關搜尋

熱門詞條

聯絡我們