OSPF協(xié)議及鏈路狀態(tài)算法鏈路狀態(tài)〔Link-State〕算法L-S算法的根本概念L-S算法的動(dòng)態(tài)特性L-S算法的性能分析L-S算法與D-V算法的比較OSPF協(xié)議鏈路狀態(tài)算法的根本概念鏈路狀態(tài)算法的根本概念鏈路狀態(tài)法的計(jì)算舉例最短路徑算法計(jì)算結(jié)果每個(gè)路由器周期性地收集和發(fā)送信息主動(dòng)測(cè)試其到所有鄰居的鏈接狀態(tài)〔度量值〕向所有的路由器發(fā)送〔播送〕自己擁有的狀態(tài)信息得到一個(gè)全網(wǎng)的、動(dòng)態(tài)的邏輯鏈路狀態(tài)〔L-S〕圖每個(gè)路由器刷新自己的路由表當(dāng)L-S變化時(shí)，用最短路徑優(yōu)先(SPF)算法重新計(jì)算本地路由DCAB鏈路狀態(tài)算法的根本概念__________________________________________________________________________________________路由表SPF算法拓?fù)鋽?shù)據(jù)庫〔L-S圖〕SPF樹L-S包AEDCB212113最短路徑算法計(jì)算加權(quán)無向圖〔即L-S圖〕中兩個(gè)結(jié)點(diǎn)之間的最短路徑對(duì)每結(jié)點(diǎn)賦以標(biāo)注{D(v),NP(v)}鏈路狀態(tài)法的計(jì)算舉例F3552其中自變量v：無向圖中的結(jié)點(diǎn)函數(shù)D(v)：到目前為止，從源點(diǎn)到結(jié)點(diǎn)v的最短路徑〔邊長之和〕函數(shù)NP(v)：沿從源點(diǎn)到結(jié)點(diǎn)v且與其相鄰的前一結(jié)點(diǎn)最短路徑算法計(jì)算結(jié)果AEDCB212113源點(diǎn)A到所有結(jié)點(diǎn)的最短路徑F3552DFEABC11212L-S圖SPF樹

L-S算法的動(dòng)態(tài)特性建立路由表的初始過程發(fā)現(xiàn)新的網(wǎng)絡(luò)路由表的維護(hù)發(fā)現(xiàn)拓?fù)渥兓薷耐負(fù)鋽?shù)據(jù)庫計(jì)算SPF樹修改路由表ACBa0 a1 b0 b1 c0 c1L-S建立路由表的初始過程ACBL-S網(wǎng)絡(luò)發(fā)現(xiàn)過程剖析C發(fā)現(xiàn)直連網(wǎng)絡(luò)和構(gòu)造包含發(fā)現(xiàn)信息的L-S報(bào)文(LSP)向全網(wǎng)播送接收全網(wǎng)的其他路由器發(fā)來的L-S報(bào)文根據(jù)收集的信息建立拓?fù)鋽?shù)據(jù)庫啟動(dòng)SPF算法以C為源點(diǎn)計(jì)算SPF樹建立到達(dá)所有信宿的路由表〔端口和代價(jià)〕c1LSPc0〔1〕發(fā)現(xiàn)拓?fù)渥兓疉EDCBF

NetXNetXDownNetXDownLSPLSP發(fā)現(xiàn)網(wǎng)絡(luò)X不可達(dá)構(gòu)造LSP向全網(wǎng)播送發(fā)現(xiàn)網(wǎng)絡(luò)X不可達(dá)構(gòu)造LSP向全網(wǎng)播送〔2〕修改拓?fù)鋽?shù)據(jù)庫AEDCBF

NetX全網(wǎng)具有相同的L-S邏輯圖。AEDCBF

NetX〔3〕各自重新計(jì)算SPF樹223311525AEDCBF

NetX根據(jù)各自計(jì)算的SPF樹刷新路由表〔4〕修改各自的路由表a0a1a2NetY路由表路由表路由表路由表路由表221L-S算法的性能分析優(yōu)點(diǎn)代價(jià)路由刷新問題線路傳輸速率不同網(wǎng)絡(luò)運(yùn)行狀態(tài)不同解決方法L-S算法的優(yōu)點(diǎn)所有路由器具有相同的網(wǎng)絡(luò)拓?fù)渲R(shí)〔L-S圖〕一次性、無修改地向全網(wǎng)播送LSP路由器根據(jù)全局信息維護(hù)各自的路由表保證鏈路狀態(tài)信息的單向傳播保證算法的收斂性L-S算法的代價(jià)SPF算法計(jì)算和拓?fù)鋽?shù)據(jù)庫需要更多的CPU和內(nèi)存資源網(wǎng)絡(luò)啟動(dòng)時(shí)的擴(kuò)散路由信息需要占用很多帶寬資源線路傳輸速率不同產(chǎn)生的影響E應(yīng)該選擇哪棵SPF樹？NetXDownNetXupNetXDown來自D來自A慢NetXE收到的LSP開始NetX down后來NetX up網(wǎng)絡(luò)的一局部已經(jīng)啟動(dòng)，而另一局部正待啟動(dòng)網(wǎng)絡(luò)的一局部刷新速度快，而另一局部刷新速度慢造成網(wǎng)絡(luò)的不同局部學(xué)習(xí)擁有不同的L-S圖網(wǎng)絡(luò)運(yùn)行狀態(tài)不同產(chǎn)生的影響D-V和L-S算法的比較D-V通過與鄰居的信息交換獲得網(wǎng)絡(luò)拓?fù)渲R(shí)路由計(jì)算是增加路由器之間的站點(diǎn)數(shù)〔hops〕定期刷新路由：收斂慢向相鄰站點(diǎn)傳送路由表的副本L-S全網(wǎng)獲得共同的全局性網(wǎng)絡(luò)拓?fù)渲R(shí)〔L-S圖〕計(jì)算到達(dá)其他站點(diǎn)的最短路徑〔SPF準(zhǔn)那么〕觸發(fā)刷新：收斂快向其他站點(diǎn)發(fā)送鏈路狀態(tài)的動(dòng)態(tài)變化平衡混合路由選擇第三種路由選擇協(xié)議將D-V和L-S兩種結(jié)合起來，稱為平衡混合路由協(xié)議。1、用度量更精確的距離矢量來確定到達(dá)目的網(wǎng)絡(luò)的最正確路徑。