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