路由器中OPSF協議的SPF算法是什么
開放最短路徑優先OSPF(Open Shortest Path First)使用鏈路狀態算法來傳播選路信息，它使用SPF算法(Dijkstra算法)。其要點如下：
1、所有的路由器都維持一個鏈路狀態數據庫，只有可達鄰站的鏈路狀態信
息才存入鏈路狀態數據庫，這個數據庫實際上就是整個互連網的拓撲結構圖。而使用RIP協議的路由器只各自知道到所有目的網絡的下一站路由器，但卻不知道全網的拓撲結構。
2、OSPF讓每一個鏈路狀態都帶上一個32bit的序號(增長的速率不得超過每5秒1次)，序號越大狀態越新。每一個路由器用鏈路狀態數據庫中的數據，算出自己的路由表。
3、要網絡拓撲發生任何變化，鏈路狀態數據庫就能很快地進行更新，使各
個路由器能夠重新計算出新的路由表。
4、OSPF依靠各路由器之間的頻繁交換信息來建立鏈路狀態數據庫，并維持這數據庫在全網范圍內的一致性(鏈路狀態數據庫的同步)。
5、OSPF不象RIP使用運輸層的用戶數據報UDP進行傳送，而是直接用IP
數據報傳送，并且數據報很短。(圖1)
IP數據報首部(20字節) | OSPF報文首部(24字節) | 類型1至5的OSPF報文 |
由于一個路由器的鏈路狀態只涉及到與相鄰路由器的連通狀態，因而與整個互連網的規模無關。
二、基本概念
1、鏈路狀態：所謂一個路由器的“鏈路狀態”就是該路由器都和哪些網
絡或路由器相鄰，以及將數據發往這些網絡或路由器所需的費用。
2、自治系統：一般簡稱為AS。一個自治系統是一個互連網絡，其最重要的特點是它有權自主地決定在本系統內應采用何種路由選擇協議。
3、內部網關協議IGP：即在一個自治系統內部使用的路由選擇協議。
4、區域：OSPF允許進一步地將互連網劃分成一些區域。每個區域都包含一
組相鄰的網絡及所連接的主機，每個網關都必須被放置在其中的一個區域中。每一區域內的拓撲結構對區域外是不可見的。由于保持了區域拓撲的獨立性，因此路由選擇交換信息量比AS未被分隔時小。帶有多個接口的路由器可加入到多個區域，這些所謂的區域邊界路由器為每個區域維護一個單獨的拓撲數據庫。
5、鏈路狀態數據庫：是與路由器相關的網絡的整體結構圖，它包含從同一
區域中所有路由器接收的LSA(鏈路狀態通告：包含有關鏈路接口、所用計量標準及其他變量信息)。
6、OSPF主干：負責在兩個區域之間發送路由選擇信息，它由區域邊界路由
器、跨區域網絡及與其連接的路由器組成。運行OSPF的AS邊界路由器通過外部網關協議或配置信息了解外部路由。
7、指定的路由器：如果某個網絡上接有N個網關，則它們可形成N(N-1)/2個可能的鄰接。每當某個網關傳送一個報文時，它會向所有N-1個鄰接網關發送該報文，因而共傳送(N-1)?個鏈路狀態。當指定一個網關作為指定路由器后，每個網關都變得與指定路由器有鄰接關系，而與其它網關不存在鄰接關系，與特定網絡相連的N個網關之間僅有N-1個鄰接，傳送的信息量大為減少。指定路由器的另一項任務是為該網絡發送鏈路狀態通告，傳送鏈路狀態更新數據。
8、后備指定路由器：當多重接入網絡上的網關沒有選出指定路由器的時候，后備指定路由器成為指定路由器，再在余下的網關中選出新的后備指定路由器。此時N個網關之間可能有2N-3個鄰接關系。
三、OSPF分組格式
版本號（1） | 類型（1） | 數據分組長度（2） | 路由器ID（4） | 區域ID（4） | 校驗和（2） | 鑒別類型（2） | 鑒別（8） | 數據（可變） |
各字段含義如下(圖2)：
版本號字段：給出了OSPF的版本。
類型字段：OSPF共有五種報文類型：
類型1：Hello報文，用來發現和維持鄰站的可達性;
類型2：Database Description報文，向鄰站給出自己的鏈路狀態數據庫中的所有鏈路狀態項目的摘要信息;
類型3：Link State Request報文，向對方請求發送某些鏈路狀態項目的詳細信息;
類型4：Link State Update報文，用洪泛法向全網更新鏈路狀態;
類型5：Link State Acknowledgment報文，對鏈路更新報文的確認。
數據分組長度字段：OSPF分組的長度，包括分組首部。
路由器ID字段：標識數據分組的源地。
區域ID字段：標識分組所屬的區域。
校驗和字段：檢驗分組內容。
鑒別類型字段：所有OSPF協議路由器間的數據交換都需要被鑒別，保證只有可信賴的路由器才能傳送路由信息。
鑒別字段：包括鑒別信息。
數據：類型1至類型5的OSPF報文。
四、鏈路狀態數據庫的建立和更新
每個路由器定期發送一個鏈路狀態通告LSA，以提供有關路由器的鄰接信息，或通知其他路由器某個路由器的狀態改變了。通過把已經建立的鄰接路由器與連接狀態相比較，可以快速檢測出失效路由器，并適時修改網絡的鏈路狀態數據庫，每一路由器以其為根據計算一個最短路徑樹，該最短路徑樹提供一個路由選擇表。OSPF規定，每兩個相鄰路由器每隔10秒要交換一次Hello報文，以確知哪些鄰站是可達的。只有可達鄰站的鏈路狀態信息才存入鏈路狀態數據庫，并由此算出路由表來。若有40秒沒有收到某個相鄰路由器發來的Hello報文，則可認為該相鄰路由器不可達，應立即修改鏈路狀態數據庫，并重新計算路由表。
當一個路由器剛開始工作時，它只能通過Hello報文得知它有哪些相鄰的路由器在工作，以及將數據發往相鄰路由器所需的費用。OSPF讓每一個路由器用Database Description報文和相鄰路由器交換本數據庫中已有的鏈路狀態摘要信息(指出有哪些路由器的鏈路狀態信息已寫入數據庫)。之后路由器使用Link State Request報文向對方請求發送自己所缺的某些鏈路狀態項目的詳細信息。通過一系列的這種報文交換，全網的鏈路狀態數據庫就建立起來了。
在網絡運行的過程中，只要一個路由器的鏈路狀態發生變化，該路由器就要使用Link State Update報文，用洪泛法向全網更新鏈路狀態。當一個重復的報文到達時，網關丟棄該報文，而不發送它的副本。為了確保鏈路狀態數據庫與全網的狀態保持一致，OSPF還規定每隔一段時間，如30分鐘要刷新一次數據庫中的鏈路狀態。
五、OSPF的圖論模型
OSPF利用網絡拓撲的圖論模型來計算最短路徑。OSPF拓撲圖中的每個節點或者對應一個網關，或者對應一個網絡。如果網中兩實體存在物理連接，則OSPF圖在代表實體的兩個節點之間有一對有向邊，每個邊都有一個“權”。OSPF根據沿著花費最小的路徑轉發數據報的原則建立選路表。
六、OSPF的有限狀態機模型
有兩個原因使Hello對多重接入網絡特別重要。首先，網絡硬件并不檢查或報告網關的崩潰或重啟，為了互相保留對方的狀態信息，與多重接入網絡相連接的兩個網關必須交換分組。第二，與某個多重接入網絡相連接的任意兩個網關之間都能夠直接通信，因此OSPF必須防止這些網關形成過多的鄰接。
OSPF標準使用了一個有限狀態機來規范使用Hello的網關如何與相鄰網關交互作用。
一般來說，所有相鄰網關最初都處于DOWN狀態，表示并未準備通信。當一個網關接收到相鄰網關發出的Hello分組后，它將相鄰網關從DOWN狀態變遷到INIT狀態。在此之后，相鄰網關或者進入2-WAY狀態，或者進入EXSTART狀態。其中2-WAY狀態表示通信已經建立，但相鄰網關與該網關之間沒有鄰接關系，EXSTART狀態表示不但已經建立通信，而且兩個網關之間存在經過雙方協商同意的鄰接關系。
當協商結束時，網關開始交換鏈路狀態數據庫中的信息，以確保它們有完全相同的底層互連網拓撲圖。兩個相鄰網關中的一個成為“主網關”，它查詢另一個網關數據庫中的信息。非主網關返回數據庫描述分組，以通知主網關最近接收到的該拓撲圖中每條鏈路的信息。在建立鄰接關系時，交換信息尤其重要，因為在網絡斷連期間，某個網關中的信息可能變為過時的信息。每個拓撲信息分組中包含一個序號，因此網關能夠知道相鄰網關數據庫中的描述信息是否比該網關自身數據庫中的信息更新。在交換完成且所有拓撲信息都已裝載后，網關進入FULL狀態。在FULL狀態中，兩個網關定期交換分組，以保持連接。