SPF演演算法

SPF演演算法是OSPF路由協議的基礎。SPF演演算法有時也被稱為Dijkstra演演算法，這是因為最短路徑優先演演算法SPF是Dijkstra發明的。

在這裡，鏈路帶寬以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的更新。