https://zhuanlan.zhihu.com/p/97957818

鏈路狀態(tài)路由選擇協(xié)議又稱為最短路徑優(yōu)先協(xié)議或分布式數(shù)據(jù)庫協(xié)議，它基于Edsger Dijkstra的最短路徑優(yōu)先（SPF）算法。 [1] 它比距離矢量路由協(xié)議復(fù)雜得多，但基本功能和配置卻很簡單，算法易理解。鏈路狀態(tài)協(xié)議從網(wǎng)絡(luò)或者網(wǎng)絡(luò)的限定區(qū)域內(nèi)的所有其他路由器處收集信息，最終每個鏈路狀態(tài)路由器上都有一個相同的有關(guān)網(wǎng)絡(luò)的信息。并且每臺路由器都可以獨立的計算各自的最優(yōu)路徑。

路由協(xié)議

鏈路狀態(tài)路由協(xié)議是層次式的，網(wǎng)絡(luò)中的路由器并不向鄰居傳遞“路由項”，而是通告給鄰居一些鏈路狀態(tài)。與距離矢量路由協(xié)議相比，鏈路狀態(tài)協(xié)議對路由的計算方法有本質(zhì)的差別。距離矢量協(xié)議是平面式的，所有的路由學(xué)習(xí)完全依靠鄰居，交換的是路由項。鏈路狀態(tài)協(xié)議只是通告給鄰居一些鏈路狀態(tài)。運行該路由協(xié)議的路由器不是簡單地從相鄰的路由器學(xué)習(xí)路由，而是把路由器分成區(qū)域，收集區(qū)域的所有的路由器的鏈路狀態(tài)信息，根據(jù)狀態(tài)信息生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，每一個路由器再根據(jù)拓?fù)浣Y(jié)構(gòu)計算出路由。 [1]

工作過程

一、了解直連網(wǎng)絡(luò)

每臺路由器了解其自身的鏈路（即與其直連的網(wǎng)絡(luò)）。這通過檢測哪些接口處于工作狀態(tài)（包括第3層地址）來完成。

對于鏈路狀態(tài)路由協(xié)議來說，直連鏈路就是路由器上的一個接口，與距離矢量協(xié)議和靜態(tài)路由一樣，鏈路狀態(tài)路由協(xié)議也需要下列條件才能了解直連鏈路：正確配置了接口IP地址和子網(wǎng)掩碼并激活接口，并將接口包括在一條network語句中。

二、向鄰居發(fā)送Hello數(shù)據(jù)包

每臺路由器負(fù)責(zé)“問候”直連網(wǎng)絡(luò)中的相鄰路由器。與EIGRP路由器相似，鏈路狀態(tài)路由器通過直連網(wǎng)絡(luò)中的其他鏈路狀態(tài)路由器互換Hello數(shù)據(jù)包來達到此目的。

路由器使用Hello協(xié)議來發(fā)現(xiàn)其鏈路上的所有鄰居，形成一種鄰接關(guān)系，這里的鄰居是指啟用了相同的鏈路狀態(tài)路由協(xié)議的其他任何路由器。這些小型Hello數(shù)據(jù)包持續(xù)在兩個鄰接的鄰居之間互換，以此實現(xiàn)“保持激活”功能來監(jiān)控鄰居的狀態(tài)。如果路由器不再收到某鄰居的Hello數(shù)據(jù)包，則認(rèn)為該鄰居已無法到達，該鄰接關(guān)系破裂。

三、建立鏈路狀態(tài)數(shù)據(jù)包

每臺路由器創(chuàng)建一個鏈路狀態(tài)數(shù)據(jù)包（LSP），其中包含與該路由器直連的每條鏈路的狀態(tài)。這通過記錄每個鄰居的所有相關(guān)信息，包括鄰居ID、鏈路類型和帶寬來完成。一旦建立了鄰接關(guān)系，即可創(chuàng)建LSP，并僅向建立鄰接關(guān)系的路由器發(fā)送LSP。LSP中包含與該鏈路相關(guān)的鏈路狀態(tài)信息、序列號、過期信息。

四、將鏈路狀態(tài)數(shù)據(jù)包泛洪給鄰居

每臺路由器將LSP泛洪到所有鄰居，然后鄰居將收到的所有LSP存儲到數(shù)據(jù)庫中。接著，各個鄰居將LSP泛洪給自己的鄰居，直到區(qū)域中的所有路由器均收到那些LSP為止。每臺路由器會在本地數(shù)據(jù)庫中存儲鄰居發(fā)來的LSP的副本。

路由器將其鏈路狀態(tài)信息泛洪到路由區(qū)域內(nèi)的其他所有鏈路狀態(tài)路由器，它一旦收到來自鄰居的LSP，不經(jīng)過中間計算，立即將這個LSP從除接收該LSP的接口以外的所有接口發(fā)出，此過程在整個路由區(qū)域內(nèi)的所有路由器上形成LSP的泛洪效應(yīng)。距離矢量路由協(xié)議則不同，它必須首先運行貝爾曼-福特算法來處理路由更新，然后才將它們發(fā)送給其他路由器;而鏈路狀態(tài)路由協(xié)議則在泛洪完成后再計算SPF算法，因此達到收斂狀態(tài)的速度比距離矢量路由協(xié)議快得多。LSP在路由器初始啟動期間、或路由協(xié)議過程啟動期間、或在每次拓?fù)浒l(fā)生更改（包括鏈路接通或斷開）時、或是鄰接關(guān)系建立、破裂時發(fā)送，并不需要定期發(fā)送。

五、構(gòu)建鏈路狀態(tài)數(shù)據(jù)庫

每臺路由器使用數(shù)據(jù)庫構(gòu)建一個完整的拓?fù)鋱D并計算通向每個目的網(wǎng)絡(luò)的最佳路徑。就像擁有了地圖一樣，路由器現(xiàn)在擁有關(guān)于拓?fù)渲兴心康牡匾约巴ㄏ蚋鱾€目的地的路由的詳圖。SPF算法用于構(gòu)建該拓?fù)鋱D并確定通向每個網(wǎng)絡(luò)的最佳路徑。所有的路由器將會有共同的拓?fù)鋱D或拓?fù)錁?，但是每一個路由器獨立確定到達拓?fù)鋬?nèi)每一個網(wǎng)絡(luò)的最佳路徑。

在使用鏈路狀態(tài)泛洪過程將自身的LSP傳播出去后，每臺路由器都將擁有來自整個路由區(qū)域內(nèi)所有鏈路狀態(tài)路由器的LSP，都可以使用SPF算法來構(gòu)建SPF樹。這些LSP存儲在鏈路狀態(tài)數(shù)據(jù)庫中。有了完整的鏈路狀態(tài)數(shù)據(jù)庫，即可使用該數(shù)據(jù)庫和最短路徑優(yōu)先（SPF）算法來計算通向每個網(wǎng)絡(luò)的首選（即最短）路徑。 [2-3]

協(xié)議優(yōu)點

與距離矢量路由協(xié)議相比，有如下優(yōu)點：

創(chuàng)建拓?fù)鋱D

鏈路狀態(tài)路由協(xié)議會創(chuàng)建拓?fù)鋱D，即SPF樹，而距離矢量路由協(xié)議沒有網(wǎng)絡(luò)的拓?fù)鋱D，僅有一個網(wǎng)絡(luò)列表，其中列出了通往各個網(wǎng)絡(luò)的開銷（距離）和下一跳路由器（方向）。因為鏈路狀態(tài)路由協(xié)議會交換鏈路狀態(tài)信息，所以SPF算法可以構(gòu)建網(wǎng)絡(luò)的SPF樹，有了SPF樹，路由器可獨立確定通向每個網(wǎng)絡(luò)的最短路徑。

快速收斂

有幾個原因使得鏈路狀態(tài)路由協(xié)議比距離矢量路由協(xié)議具有更快的收斂速度。收到一個鏈路狀態(tài)數(shù)據(jù)包（LSP）后鏈路狀態(tài)路由協(xié)議便立即將該LSP從除接收該LSP的接口以外的所有接口泛洪出去。使用距離矢量路由協(xié)議的路由器需要處理每個路由更新，并且在更新完路由表后才能將更新從路由器接口泛洪出去，即使對觸發(fā)更新也是如此。因此鏈路狀態(tài)路由協(xié)議可更快達到收斂狀態(tài)。不過EIGRP是一個明顯的例外。

事件驅(qū)動更新

在初始LSP泛洪之后，鏈路狀態(tài)路由協(xié)議僅在拓?fù)浒l(fā)生改變時才發(fā)出LSP。該LSP僅包含受影響鏈路的信息。與某些距離矢量路由協(xié)議不同的是，鏈路狀態(tài)路由協(xié)議不會定期發(fā)送更新。

層次式設(shè)計

鏈路狀態(tài)路由協(xié)議，如OSPF和IS-IS使用了區(qū)域的概念。多個區(qū)域形成了層次化的網(wǎng)絡(luò)結(jié)構(gòu)，這有利于路由聚合（匯總），還便于將路由問題隔離在一個區(qū)域內(nèi)。 [2] [4]

協(xié)議要求

現(xiàn)代鏈路狀態(tài)路由協(xié)議設(shè)計旨在盡量降低對內(nèi)存、CPU和帶寬的影響。使用并配置多個區(qū)域可減小鏈路狀態(tài)數(shù)據(jù)庫。劃分多個區(qū)域還可限制在路由域內(nèi)泛洪的鏈路狀態(tài)信息的數(shù)量，并可僅將LSP發(fā)送給所需的路由器。 [1]

內(nèi)存要求

與距離矢量路由協(xié)議相比，鏈路狀態(tài)路由協(xié)議通常需要占用更多的內(nèi)存、CPU處理時間和帶寬。對內(nèi)存的要求源于鏈路狀態(tài)數(shù)據(jù)庫的使用和創(chuàng)建SPF樹的需要。

處理器要求

與距離矢量路由協(xié)議相比，鏈路狀態(tài)路由協(xié)議可能還需要占用更多的CPU處理時間。與Bellman-Ford等距離矢量算法相比，SPF算法需要更多的CPU處理時間，因為鏈路狀態(tài)路由協(xié)議會創(chuàng)建完整的拓?fù)鋱D。

帶寬要求

鏈路狀態(tài)數(shù)據(jù)包泛洪會對網(wǎng)絡(luò)的可用帶寬產(chǎn)生負(fù)面影響。這應(yīng)該只出現(xiàn)在路由器初始啟動過程中，但在不穩(wěn)定的網(wǎng)絡(luò)中也可能導(dǎo)致問題。

協(xié)議比較

如今，用于IP路由的鏈路狀態(tài)路由協(xié)議有兩種。

最短路徑優(yōu)先（OSPF）

OSPF由IETF的OSPF工作組設(shè)計，OSPF的開發(fā)始于1987年，如今正在使用的有OSPFv2和OSPFv3兩個版本。OSPF的大部分工作由John Moy完成。

中間系統(tǒng)到中間系統(tǒng)（IS-IS）

IS-IS由ISO設(shè)計的，它的雛形由DEC開發(fā)，名為DECnet Phase V，首席設(shè)計師是Radia Perlman.

IS-IS最初是為OSI協(xié)議簇而非TCP/IP協(xié)議簇而設(shè)計的，后來，集成化IS-IS，即雙IS-IS添加了對IP網(wǎng)絡(luò)的支持，盡管IS-IS路由協(xié)議一直主要供ISP和電信公司使用，但已有越來越多的企業(yè)開始使用IS-IS。

兩者既有很多共同點，也有很多不同之處。有很多分別擁護OSPF和IS-IS的派別，它們從未停止過對雙方優(yōu)缺點的討論和爭辯。

ospf與is-is的相似之處

無類別；

使用鏈路狀態(tài)數(shù)據(jù)庫和Dijkstra算法；

用Hello分組來建立和維護毗鄰關(guān)系；

用區(qū)域來組建層次化拓?fù)洌恢С謪^(qū)域間路由匯總；

在多路訪問型網(wǎng)絡(luò)中選舉指定路由器；

鏈路狀態(tài)的表示方式、時效（aging）和度量值；

更新，判斷和洪泛擴散；

收斂能力；

用與isp主干網(wǎng)絡(luò)；

ospf與is-is的不同之處

is-is不會選舉BDR；

當(dāng)有新的路由器加入時；isis會重新選舉；

每當(dāng)DR發(fā)生改變時，就會洪泛一批新的LSA；

isis路由器和全部鄰接路由器都建立毗鄰關(guān)系，而不只和DR建立；

ospf與is-is區(qū)域間的其它不同之處

ospf基于一個主干中心，其他區(qū)域都鏈接在主干上（區(qū)域邊界落在ABR之內(nèi)，每一條鏈路只屬于一個區(qū)域）；

isis中區(qū)域邊界落在鏈路上（每一個isis路由器完全屬于一個第2層區(qū)域）；

ospf單個區(qū)域支持50個路由器，isis支持100個；

ospf有更多特性，包括路由標(biāo)簽、完全末梢區(qū)域、NSSA、以及虛擬鏈路。 [1]

對于isis來說，區(qū)域邊界位于鏈路上，這樣可以顯著減少協(xié)議數(shù)據(jù)單元PDU(LSP)的使用，從而使一個區(qū)域中有更多的路由器。就cpu的使用效率和路由更新處理來說，isis更有效率，不僅是因為isis的鏈路狀態(tài)通告比ospf少，還因為isis添加和刪除前綴的操作比較少。isis對區(qū)域中的每臺路由器只使用一個鏈路狀態(tài)分組，其中包括重發(fā)布前綴。使用默認(rèn)定時器，isis比ospf更快的發(fā)現(xiàn)路由失效，從而收斂更快。isis中的定時器比ospf的更具可調(diào)性，所以能達到更精確的調(diào)節(jié)粒度。

參考資料

1.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B1%5D_67350Rick Graziani Allan Johnson．思科網(wǎng)絡(luò)技術(shù)學(xué)院教程-路由協(xié)議和概念．北京：人民郵電出版社，2015.3

2.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B2%5D_67350（美）阿齊茲，（美）馬蒂．IP路由協(xié)議疑難解析：人民郵電出版社，2013.7

3.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B3%5D_67350尹淑玲．交換與路由技術(shù)教程：武漢大學(xué)出版社，2012.11

4.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B4%5D_67350沈鑫剡．路由和交換技術(shù) ：清華大學(xué)出版社，2013.2

如果說距離矢量路由協(xié)議提供的是路標(biāo)，那么鏈路狀態(tài)路由協(xié)議提供的就是地圖。每個鏈路狀態(tài)路由器上都有一張完整的網(wǎng)絡(luò)圖。鏈路狀態(tài)協(xié)議不同于距離矢量協(xié)議“依照傳聞”進行路由選擇的工作方式。每臺鏈路狀態(tài)路由器從對等路由器那里獲取的都是“第一手”的信息。每臺路由器都會將一些關(guān)于自己，關(guān)于本地直連鏈路以及這些鏈路的狀態(tài)和關(guān)于所有直連鄰居的信息傳送給另一臺路由器，接受到信息的路由器都會將該類信息做一個拷貝，但絕不修改信息。最終的目的是每臺路由器都有一個相同的有關(guān)網(wǎng)絡(luò)的信息。并且每臺路由器都可以獨立的計算各自的最優(yōu)路徑。

鏈路狀態(tài)協(xié)議有時也叫最短路徑優(yōu)先協(xié)議或叫分布式數(shù)據(jù)庫協(xié)議，該類協(xié)議是圍繞一個著名的算法——E.W.Dijkstra的最短路徑算法設(shè)計的。

常見的鏈路狀態(tài)協(xié)議有

OSPF：開放式最短路徑優(yōu)先協(xié)議

IS-IS:中間系統(tǒng)到中間系統(tǒng)協(xié)議

鏈路狀態(tài)協(xié)議的工作過程：

第一步：每臺路由器都與自己的鄰居建立鄰接關(guān)系。

第二步：每臺路由器都向自己的鄰居發(fā)送鏈路狀態(tài)通告（LSA）的數(shù)據(jù)單元。路由器對自己的每條鏈路都會生成一條鏈路狀態(tài)通告，用于標(biāo)記該條鏈路及鏈路狀態(tài)，指示路由器接口到鏈路的代價度量值及鏈路所連接的所有鄰居。每個鄰居收到鏈路狀態(tài)通告后將向它的鄰居洪泛這些通告。

第三步：每臺路由器都會將自己收到的LSA拷貝并存入到本地的鏈路狀態(tài)數(shù)據(jù)庫（LSDB）中。若每臺路由都正常工作，那么所有路由器的鏈路狀態(tài)數(shù)據(jù)庫中的網(wǎng)絡(luò)信息都會是相同的。

第四步：基于本地的鏈路狀態(tài)數(shù)據(jù)庫網(wǎng)路信息，使用最短路徑優(yōu)先算法計算出到每臺路由器的最短路徑。接著鏈路狀態(tài)協(xié)議會通過查詢鏈路狀態(tài)數(shù)據(jù)，找到每臺路由器所連接的子網(wǎng)，并把這些信息輸入到路由表中。

鄰居

鄰居發(fā)現(xiàn)是建立鏈路狀態(tài)環(huán)境并運行的第一步。使用Hello協(xié)議完成鄰居發(fā)現(xiàn)。Hello協(xié)議定義了一個Hello數(shù)據(jù)的格式和交換數(shù)據(jù)包并處理數(shù)據(jù)包信息的過程。

Hello數(shù)據(jù)包中至少包含路由ID（router ID）和發(fā)送數(shù)據(jù)包的網(wǎng)絡(luò)地址。路由器ID是用來將路由在網(wǎng)絡(luò)中唯一的標(biāo)識。

當(dāng)兩臺路由器之間確認(rèn)為鄰居關(guān)系時，它們之間就要進行數(shù)據(jù)同步即交換和確定數(shù)據(jù)庫信息直到數(shù)據(jù)庫相同為止。為了執(zhí)行數(shù)據(jù)庫同步，鄰居之間必須建立鄰接關(guān)系。即它們必須就某些參數(shù)達成一致。通過Hello數(shù)據(jù)包建立鄰接關(guān)系，鏈路狀態(tài)就可以在受控的方式下交換信息。與距離矢量協(xié)議相比，鏈路狀態(tài)協(xié)議僅在配置了路由選擇協(xié)議的接口上廣播更新信息。

除了發(fā)現(xiàn)鄰居建立鄰接關(guān)系的作用外，Hello數(shù)據(jù)包還可以作為監(jiān)視鄰接關(guān)系的握手信息。如果沒有在特定的時間內(nèi)從鄰接路由器接收到Hello數(shù)據(jù)包，就認(rèn)為鄰居不可達。隨即鄰接關(guān)系解除。

鏈路狀態(tài)洪泛擴散

在建立鄰接關(guān)系后路由器發(fā)送LSA。LSA被洪泛給每臺路由器，路由器保存收到的LSA，并繼續(xù)向自己的鄰居洪泛（除接收接口外的其他所有配置接口）。這個過程就體現(xiàn)出鏈路狀態(tài)協(xié)議的優(yōu)秀之處，因為LSA是立刻被轉(zhuǎn)發(fā)的，而在距離矢量協(xié)議中所有路由器在接收到更新信息后都必須先將自己路由表更新才會向鄰居轉(zhuǎn)發(fā)更新信息，觸發(fā)更新也是如此。因此，當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時，鏈路狀態(tài)協(xié)議收斂的速度會遠遠快于距離矢量協(xié)議。