路由算法補(bǔ)充知識

關(guān)于路由算法補(bǔ)充知識1. 路由算法需要考慮的基本因素1）路由算法的設(shè)計(jì)目標(biāo)2）選擇最佳路由的度量參數(shù)第2頁,共48頁，2024年2月25日，星期天1）路由算法的設(shè)計(jì)目標(biāo)優(yōu)化：根據(jù)一定的優(yōu)化準(zhǔn)則選擇最佳路徑的能力簡單：利用最少的物理資源、提供最有效的功能穩(wěn)定：經(jīng)受得住各種惡劣環(huán)境的考驗(yàn)，故障率低收斂：跟隨路由更新信息變化重新計(jì)算，快速取 得全網(wǎng)一致的最佳路由靈活：快速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境和變化第3頁,共48頁，2024年2月25日，星期天2）選擇最佳路由的度量參數(shù)路徑長度由網(wǎng)絡(luò)管理員定義每條網(wǎng)絡(luò)鏈路的代價（cost），從源到宿的代價總和為路徑長度。以路徑中的站點(diǎn)（hop）為單位，從源到宿的站點(diǎn)數(shù)之和為路徑長度。可靠性 鏈路數(shù)據(jù)傳輸?shù)目煽啃裕ㄕ`碼率）延遲 數(shù)據(jù)包從源到宿需要花費(fèi)的傳輸時間帶寬 鏈路的最大傳輸能力以及網(wǎng)絡(luò)流量負(fù)載 網(wǎng)絡(luò)資源（例如路由器的CPU）的使用率通信代價 占用通信線路的費(fèi)用第4頁,共48頁，2024年2月25日，星期天2. 路由選擇算法1）缺省路徑2）靜態(tài)路由3）動態(tài)路由—距離向量法4）動態(tài)路由—鏈路狀態(tài)法第5頁,共48頁，2024年2月25日，星期天1）缺省路徑（DefaultRoute）什么是缺省路徑？對那些在路由表中未包含其路由選擇信息的信宿（網(wǎng)絡(luò)/主機(jī)）設(shè)定的缺省路徑在路由表中信宿地址取值0.0.0.0(Default)缺省路徑的作用對所有自治系統(tǒng)以外的信宿都采用缺省路徑簡化路由計(jì)算，提高尋徑效率，縮短表長第6頁,共48頁，2024年2月25日，星期天缺省路徑舉例網(wǎng)絡(luò)A網(wǎng)絡(luò)DRdb0c0f0e0DefaultRde0DefaultRdf0DefaultRa b0DefaultRa c0RaRcRbRfRe第7頁,共48頁，2024年2月25日，星期天2）靜態(tài)路由靜態(tài)路由的概念靜態(tài)路由工作原理路由配置舉例故障舉例（網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化）用人工修改配置排除故障第8頁,共48頁，2024年2月25日，星期天靜態(tài)路由的概念由網(wǎng)絡(luò)管理員設(shè)置路由表簡單、有效，適于結(jié)構(gòu)簡單的網(wǎng)絡(luò)不適于拓?fù)浣Y(jié)構(gòu)和傳輸流量經(jīng)常改變的復(fù)雜網(wǎng)絡(luò)第9頁,共48頁，2024年2月25日，星期天靜態(tài)路由舉例網(wǎng)絡(luò)A網(wǎng)絡(luò)C網(wǎng)絡(luò)BRa路由表網(wǎng)絡(luò)B Rb a2網(wǎng)絡(luò)C Rc a3Rb路由表網(wǎng)絡(luò)A Ra b3網(wǎng)絡(luò)C Rc b2Rc路由表網(wǎng)絡(luò)B Rb c2網(wǎng)絡(luò)A Ra c3a1a3a2c3c2c1b2b3b1RaRbRc第10頁,共48頁，2024年2月25日，星期天鏈路發(fā)生故障網(wǎng)絡(luò)A網(wǎng)絡(luò)C網(wǎng)絡(luò)BRb路由表網(wǎng)絡(luò)A Ra b3網(wǎng)絡(luò)C Rc b2Rc路由表網(wǎng)絡(luò)B Rb c2網(wǎng)絡(luò)A Ra c3a1a3a2c3c2c1b2b3b1??Ra路由表網(wǎng)絡(luò)B Rb a2網(wǎng)絡(luò)C Rc a3RaRbRc第11頁,共48頁，2024年2月25日，星期天解決辦法：人工修改網(wǎng)絡(luò)A網(wǎng)絡(luò)C網(wǎng)絡(luò)BRb路由表網(wǎng)絡(luò)A Rc b2網(wǎng)絡(luò)C Rc b2Rc路由表網(wǎng)絡(luò)B Rb c2網(wǎng)絡(luò)A Ra c3a1a3a2c3c2c1b2b3b1！！不適于網(wǎng)絡(luò)變化！Ra路由表網(wǎng)絡(luò)B Rc a3網(wǎng)絡(luò)C Rc a3RaRbRc第12頁,共48頁，2024年2月25日，星期天靜態(tài)路由算法洪泛（flooding）算法：向著除了進(jìn)入鏈路以外的其他鏈路轉(zhuǎn)發(fā)；隨機(jī)算法：隨機(jī)選擇下一跳；（概率）分流算法：按照鏈路（靜態(tài)）帶寬（速率）選擇下一跳第13頁,共48頁，2024年2月25日，星期天3）距離向量算法Distance-VectorD-V算法的基本概念D-V算法的動態(tài)特性D-V算法的收斂性問題及其解決辦法D-V算法小結(jié)第14頁,共48頁，2024年2月25日，星期天A路由表距離向量算法的基本概念周期性地相互傳遞信息每個路由器向與它相鄰的站點(diǎn)發(fā)送一個包含它到所有其他路由器的距離的向量（最短路徑或最小代價）維護(hù)各自的路由表路由器根據(jù)鄰居發(fā)送的距離—向量的動態(tài)信息啟動算法，更新路由表DCAB路由表C路由表B第15頁,共48頁，2024年2月25日，星期天D-V路由選擇算法舉例第16頁,共48頁，2024年2月25日，星期天距離向量法的計(jì)算舉例ADECB718221計(jì)算從E經(jīng)相鄰站點(diǎn)A、B和D到達(dá)信宿A、B、C和D的最小代價D(destination,neighbor)得從E到達(dá)信宿的最佳路徑（最小代價）路由表最小代價D(des,nei)E的路由表第17頁,共48頁，2024年2月25日，星期天距離向量路由算法原路由不經(jīng)過N但距離大新路由不一定最優(yōu)，但，原路由可能故障原路為無窮大，則取代為經(jīng)N、長度為C的路由第18頁,共48頁，2024年2月25日，星期天D-V網(wǎng)絡(luò)發(fā)現(xiàn)過程剖析 1 1 ACB40.0.0.0up到達(dá)信宿40.0.0.0的路由變化如果網(wǎng)絡(luò)中的最長路徑為N，則算法經(jīng)過N次迭代計(jì)算后收斂。即第N步之后，網(wǎng)上的所有路由器都獲得到達(dá)信宿40.0.0.0的路由信息。第19頁,共48頁，2024年2月25日，星期天D-V發(fā)現(xiàn)鏈路斷開 1 1 ACB40.0.0.0down到達(dá)信宿40.0.0.0的路由變化C與B之間的對話：我得不到信宿40.0.0.0的任何路由信息，你能告訴我如何到達(dá)信宿嗎？我可以到達(dá)信宿，距離為1。（傳播了一條過時的錯誤信息）既然如此，我選擇經(jīng)過你到達(dá)信宿的路徑，距離為2。

第20頁,共48頁，2024年2月25日，星期天距離向量法的收斂性問題及解決辦法問題逐站傳遞更新信息，算法的收斂速度慢有可能出現(xiàn)各站路由信息不一致后果在站點(diǎn)間構(gòu)成更新路由的路徑環(huán)（RoutingLoops）計(jì)數(shù)至無窮大（CounttoInfinity）解決辦法定義路徑代價的最大值（Maximum）提高收斂速度第21頁,共48頁，2024年2月25日，星期天 1 1 ACB40.0.0.0down到達(dá)信宿40.0.0.0的路由變化

路徑環(huán)（RoutingLoop）問題這條錯誤的路由信息在C與B之間不斷復(fù)制和修改，并在網(wǎng)絡(luò)中傳播（殃及A），形成路徑傳播的環(huán)路。第22頁,共48頁，2024年2月25日，星期天 1 1 ACB40.0.0.0down到達(dá)信宿40.0.0.0的路由變化

嚴(yán)重后果：計(jì)數(shù)至無窮大第23頁,共48頁，2024年2月25日，星期天 1 1 ACB40.0.0.0down到達(dá)信宿40.0.0.0的路由變化（定義Hop最大值為16）

解決辦法：定義距離的最大值收斂！第24頁,共48頁，2024年2月25日，星期天加速收斂的方法水平分割（SplitHorizon）毒性逆轉(zhuǎn)（PoisonReverse）保持計(jì)時（Hold-DownTimers）觸發(fā)更新（TriggeredUpdates）加速方法的綜合應(yīng)用舉例第25頁,共48頁，2024年2月25日，星期天距離向量算法小結(jié)路徑選擇采用最短路徑準(zhǔn)則，計(jì)算D信宿(距離，下站)；每個站點(diǎn)只知道自己和鄰居的局部信息，在自己的刷新周期到來時，根據(jù)鄰居的路由變化重新啟動算法；算法的收斂速度慢（特別是對網(wǎng)絡(luò)崩潰）造成全網(wǎng)信息的不一致，導(dǎo)致產(chǎn)生路徑環(huán)，使計(jì)數(shù)至無窮大；當(dāng)路徑環(huán)產(chǎn)生時，定義距離的最大值可防止算法進(jìn)入死循環(huán)，解決計(jì)數(shù)至無窮大問題；各種加速收斂方法的目的在于避免路徑環(huán)的形成，但不能從根本上杜絕這一現(xiàn)象的發(fā)生；在具體的路由協(xié)議中，各種加速收斂方法往往綜合使用。第26頁,共48頁，2024年2月25日，星期天4）鏈路狀態(tài)（Link-State）算法L-S算法的基本概念L-S算法的動態(tài)特性L-S算法的性能分析L-S算法與D-V算法的比較OSPF協(xié)議第27頁,共48頁，2024年2月25日，星期天鏈路狀態(tài)算法的基本概念鏈路狀態(tài)算法的基本概念鏈路狀態(tài)法的計(jì)算舉例Dijkatra算法計(jì)算結(jié)果第28頁,共48頁，2024年2月25日，星期天每個路由器周期性地收集和發(fā)送信息主動測試其到所有鄰居的鏈接狀態(tài)（度量值）向所有的路由器發(fā)送（廣播）自己擁有的狀態(tài)信息得到一個全網(wǎng)的、動態(tài)的邏輯鏈路狀態(tài)（L-S）圖每個路由器刷新自己的路由表當(dāng)L-S變化時，用最短路徑優(yōu)先(SPF)算法重新計(jì)算本地路由DCAB鏈路狀態(tài)算法的基本概念__________________________________________________________________________________________路由表SPF算法拓?fù)鋽?shù)據(jù)庫（L-S圖）SPF樹L-S包第29頁,共48頁，2024年2月25日，星期天AEDCB212113Dijkatra最短路徑算法計(jì)算加權(quán)無向圖（即L-S圖）中兩個結(jié)點(diǎn)之間的最短路徑對每結(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的最短路徑中與V相鄰的前一結(jié)點(diǎn)第30頁,共48頁，2024年2月25日，星期天Dijkatra算法計(jì)算結(jié)果AEDCB212113源點(diǎn)A到所有結(jié)點(diǎn)的最短路徑F3552DFEABC11212L-S圖SPF樹

第31頁,共48頁，2024年2月25日，星期天L-S算法的動態(tài)特性建立路由表的初始過程發(fā)現(xiàn)新的網(wǎng)絡(luò)路由表的維護(hù)發(fā)現(xiàn)拓?fù)渥兓薷耐負(fù)鋽?shù)據(jù)庫計(jì)算SPF樹修改路由表第32頁,共48頁，2024年2月25日，星期天ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1 b0 b1 c0 c1L-S建立路由表的初始過程第33頁,共48頁，2024年2月25日，星期天ACB40.0.0.0L-S網(wǎng)絡(luò)發(fā)現(xiàn)過程剖析C發(fā)現(xiàn)直連網(wǎng)絡(luò)30.0.0.0和40.0.0.0構(gòu)造包含發(fā)現(xiàn)信息的L-S報文(LSP)向全網(wǎng)廣播接收全網(wǎng)的其他路由器發(fā)來的L-S報文根據(jù)收集的信息建立拓?fù)鋽?shù)據(jù)庫啟動SPF算法以C為源點(diǎn)計(jì)算SPF樹建立到達(dá)所有信宿的路由表（端口和代價）c1LSP30.0.0.0c0第34頁,共48頁，2024年2月25日，星期天（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)廣播第35頁,共48頁，2024年2月25日，星期天（2）修改拓?fù)鋽?shù)據(jù)庫AEDCBF

NetX全網(wǎng)具有相同的L-S邏輯圖。第36頁,共48頁，2024年2月25日，星期天AEDCBF

NetX（3）各自重新計(jì)算SPF樹2233115251第37頁,共48頁，2024年2月25日，星期天AEDCBF

NetX根據(jù)各自計(jì)算的SPF樹刷新路由表（4）修改各自的路由表a0a1a2NetY路由表路由表路由表路由表路由表221第38頁,共48頁，2024年2月25日，星期天L-S算法的性能分析優(yōu)點(diǎn)代價路由刷新問題線路傳輸速率不同網(wǎng)絡(luò)運(yùn)行狀態(tài)不同解決辦法第39頁,共48頁，2024年2月25日，星期天L-S算法的優(yōu)點(diǎn)所有路由器具有相同的網(wǎng)絡(luò)拓?fù)渲R（L-S圖）一次性、無修改地向全網(wǎng)廣播LSP路由器根據(jù)全局信息維護(hù)各自的路由表保證鏈路狀態(tài)信息的單向傳播保證算法的收斂性第40頁,共48頁，2024年2月25日，星期天L-S算法的代價SPF算法計(jì)算和拓?fù)鋽?shù)據(jù)庫需要更多的CPU和內(nèi)存資源網(wǎng)絡(luò)啟動時的擴(kuò)散路由信息（flood）需要占用很多帶寬資源第41頁,共48頁，2024年2月25日，星期天線路傳輸速率不同產(chǎn)生的影響E應(yīng)該選擇哪棵SPF樹？NetXDownNetXupNetXDown來自D來自A慢NetXE收到的LSP開始NetX down后來NetX up第42頁,共48頁，2024年2月25日，星期天網(wǎng)絡(luò)的一部分已經(jīng)啟動，而另一部分正待啟動網(wǎng)絡(luò)的一部分刷新速度快，而另一部分刷新速度慢造成網(wǎng)絡(luò)的不同部分擁有不同的L-S圖網(wǎng)絡(luò)運(yùn)行狀態(tài)不同產(chǎn)生的影響第43頁,共48頁，2024年2月25日，星期天L-S對問題的解決辦法減少對資源的需求盡可能降低路由刷新頻度用Multicast取代Broadcast(