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

關(guān)于路由算法補(bǔ)充知識(shí)第一頁，共四十八頁，2022年，8月28日1. 路由算法需要考慮的基本因素1）路由算法的設(shè)計(jì)目標(biāo)2）選擇最佳路由的度量參數(shù)第二頁，共四十八頁，2022年，8月28日1）路由算法的設(shè)計(jì)目標(biāo)優(yōu)化：根據(jù)一定的優(yōu)化準(zhǔn)則選擇最佳路徑的能力簡(jiǎn)單：利用最少的物理資源、提供最有效的功能穩(wěn)定：經(jīng)受得住各種惡劣環(huán)境的考驗(yàn)，故障率低收斂：跟隨路由更新信息變化重新計(jì)算，快速取 得全網(wǎng)一致的最佳路由靈活：快速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境和變化第三頁，共四十八頁，2022年，8月28日2）選擇最佳路由的度量參數(shù)路徑長(zhǎng)度由網(wǎng)絡(luò)管理員定義每條網(wǎng)絡(luò)鏈路的代價(jià)（cost），從源到宿的代價(jià)總和為路徑長(zhǎng)度。以路徑中的站點(diǎn)（hop）為單位，從源到宿的站點(diǎn)數(shù)之和為路徑長(zhǎng)度?？煽啃?鏈路數(shù)據(jù)傳輸?shù)目煽啃裕ㄕ`碼率）延遲 數(shù)據(jù)包從源到宿需要花費(fèi)的傳輸時(shí)間帶寬 鏈路的最大傳輸能力以及網(wǎng)絡(luò)流量負(fù)載 網(wǎng)絡(luò)資源（例如路由器的CPU）的使用率通信代價(jià) 占用通信線路的費(fèi)用第四頁，共四十八頁，2022年，8月28日2. 路由選擇算法1）缺省路徑2）靜態(tài)路由3）動(dòng)態(tài)路由—距離向量法4）動(dòng)態(tài)路由—鏈路狀態(tài)法第五頁，共四十八頁，2022年，8月28日1）缺省路徑（DefaultRoute）什么是缺省路徑？對(duì)那些在路由表中未包含其路由選擇信息的信宿（網(wǎng)絡(luò)/主機(jī)）設(shè)定的缺省路徑在路由表中信宿地址取值0.0.0.0(Default)缺省路徑的作用對(duì)所有自治系統(tǒng)以外的信宿都采用缺省路徑簡(jiǎn)化路由計(jì)算，提高尋徑效率，縮短表長(zhǎng)第六頁，共四十八頁，2022年，8月28日缺省路徑舉例網(wǎng)絡(luò)A網(wǎng)絡(luò)DRdb0c0f0e0DefaultRde0DefaultRdf0DefaultRa b0DefaultRa c0RaRcRbRfRe第七頁，共四十八頁，2022年，8月28日2）靜態(tài)路由靜態(tài)路由的概念靜態(tài)路由工作原理路由配置舉例故障舉例（網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化）用人工修改配置排除故障第八頁，共四十八頁，2022年，8月28日靜態(tài)路由的概念由網(wǎng)絡(luò)管理員設(shè)置路由表簡(jiǎn)單、有效，適于結(jié)構(gòu)簡(jiǎn)單的網(wǎng)絡(luò)不適于拓?fù)浣Y(jié)構(gòu)和傳輸流量經(jīng)常改變的復(fù)雜網(wǎng)絡(luò)第九頁，共四十八頁，2022年，8月28日靜態(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第十頁，共四十八頁，2022年，8月28日鏈路發(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第十一頁，共四十八頁，2022年，8月28日解決辦法：人工修改網(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第十二頁，共四十八頁，2022年，8月28日靜態(tài)路由算法洪泛（flooding）算法：向著除了進(jìn)入鏈路以外的其他鏈路轉(zhuǎn)發(fā)；隨機(jī)算法：隨機(jī)選擇下一跳；（概率）分流算法：按照鏈路（靜態(tài)）帶寬（速率）選擇下一跳第十三頁，共四十八頁，2022年，8月28日3）距離向量算法Distance-VectorD-V算法的基本概念D-V算法的動(dòng)態(tài)特性D-V算法的收斂性問題及其解決辦法D-V算法小結(jié)第十四頁，共四十八頁，2022年，8月28日A路由表距離向量算法的基本概念周期性地相互傳遞信息每個(gè)路由器向與它相鄰的站點(diǎn)發(fā)送一個(gè)包含它到所有其他路由器的距離的向量（最短路徑或最小代價(jià)）維護(hù)各自的路由表路由器根據(jù)鄰居發(fā)送的距離—向量的動(dòng)態(tài)信息啟動(dòng)算法，更新路由表DCAB路由表C路由表B第十五頁，共四十八頁，2022年，8月28日D-V路由選擇算法舉例第十六頁，共四十八頁，2022年，8月28日距離向量法的計(jì)算舉例ADECB718221計(jì)算從E經(jīng)相鄰站點(diǎn)A、B和D到達(dá)信宿A、B、C和D的最小代價(jià)D(destination,neighbor)得從E到達(dá)信宿的最佳路徑（最小代價(jià)）路由表最小代價(jià)D(des,nei)E的路由表第十七頁，共四十八頁，2022年，8月28日距離向量路由算法原路由不經(jīng)過N但距離大新路由不一定最優(yōu)，但，原路由可能故障原路為無窮大，則取代為經(jīng)N、長(zhǎng)度為C的路由第十八頁，共四十八頁，2022年，8月28日D-V網(wǎng)絡(luò)發(fā)現(xiàn)過程剖析 1 1 ACB40.0.0.0up到達(dá)信宿的路由變化如果網(wǎng)絡(luò)中的最長(zhǎng)路徑為N，則算法經(jīng)過N次迭代計(jì)算后收斂。即第N步之后，網(wǎng)上的所有路由器都獲得到達(dá)信宿的路由信息。第十九頁，共四十八頁，2022年，8月28日D-V發(fā)現(xiàn)鏈路斷開 1 1 ACB40.0.0.0down到達(dá)信宿的路由變化C與B之間的對(duì)話：我得不到信宿40.0.0.0的任何路由信息，你能告訴我如何到達(dá)信宿嗎？我可以到達(dá)信宿，距離為1。（傳播了一條過時(shí)的錯(cuò)誤信息）既然如此，我選擇經(jīng)過你到達(dá)信宿的路徑，距離為2。第二十頁，共四十八頁，2022年，8月28日距離向量法的收斂性問題及解決辦法問題逐站傳遞更新信息，算法的收斂速度慢有可能出現(xiàn)各站路由信息不一致后果在站點(diǎn)間構(gòu)成更新路由的路徑環(huán)（RoutingLoops）計(jì)數(shù)至無窮大（CounttoInfinity）解決辦法定義路徑代價(jià)的最大值（Maximum）提高收斂速度第二十一頁，共四十八頁，2022年，8月28日 1 1 ACB40.0.0.0down到達(dá)信宿的路由變化路徑環(huán)（RoutingLoop）問題這條錯(cuò)誤的路由信息在C與B之間不斷復(fù)制和修改，并在網(wǎng)絡(luò)中傳播（殃及A），形成路徑傳播的環(huán)路。第二十二頁，共四十八頁，2022年，8月28日 1 1 ACB40.0.0.0down到達(dá)信宿的路由變化嚴(yán)重后果：計(jì)數(shù)至無窮大第二十三頁，共四十八頁，2022年，8月28日 1 1 ACB40.0.0.0down到達(dá)信宿的路由變化（定義Hop最大值為16）解決辦法：定義距離的最大值收斂！第二十四頁，共四十八頁，2022年，8月28日加速收斂的方法水平分割（SplitHorizon）毒性逆轉(zhuǎn)（PoisonReverse）保持計(jì)時(shí)（Hold-DownTimers）觸發(fā)更新（TriggeredUpdates）加速方法的綜合應(yīng)用舉例第二十五頁，共四十八頁，2022年，8月28日距離向量算法小結(jié)路徑選擇采用最短路徑準(zhǔn)則，計(jì)算D信宿(距離，下站)；每個(gè)站點(diǎn)只知道自己和鄰居的局部信息，在自己的刷新周期到來時(shí)，根據(jù)鄰居的路由變化重新啟動(dòng)算法；算法的收斂速度慢（特別是對(duì)網(wǎng)絡(luò)崩潰）造成全網(wǎng)信息的不一致，導(dǎo)致產(chǎn)生路徑環(huán)，使計(jì)數(shù)至無窮大；當(dāng)路徑環(huán)產(chǎn)生時(shí)，定義距離的最大值可防止算法進(jìn)入死循環(huán)，解決計(jì)數(shù)至無窮大問題；各種加速收斂方法的目的在于避免路徑環(huán)的形成，但不能從根本上杜絕這一現(xiàn)象的發(fā)生；在具體的路由協(xié)議中，各種加速收斂方法往往綜合使用。第二十六頁，共四十八頁，2022年，8月28日4）鏈路狀態(tài)（Link-State）算法L-S算法的基本概念L-S算法的動(dòng)態(tài)特性L-S算法的性能分析L-S算法與D-V算法的比較OSPF協(xié)議第二十七頁，共四十八頁，2022年，8月28日鏈路狀態(tài)算法的基本概念鏈路狀態(tài)算法的基本概念鏈路狀態(tài)法的計(jì)算舉例Dijkatra算法計(jì)算結(jié)果第二十八頁，共四十八頁，2022年，8月28日每個(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ù)庫(kù)（L-S圖）SPF樹L-S包第二十九頁，共四十八頁，2022年，8月28日AEDCB212113Dijkatra最短路徑算法計(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的最短路徑（邊長(zhǎng)之和）函數(shù)NP(v)：沿源點(diǎn)到結(jié)點(diǎn)v的最短路徑中與V相鄰的前一結(jié)點(diǎn)第三十頁，共四十八頁，2022年，8月28日Dijkatra算法計(jì)算結(jié)果AEDCB212113源點(diǎn)A到所有結(jié)點(diǎn)的最短路徑F3552DFEABC11212L-S圖SPF樹第三十一頁，共四十八頁，2022年，8月28日L-S算法的動(dòng)態(tài)特性建立路由表的初始過程發(fā)現(xiàn)新的網(wǎng)絡(luò)路由表的維護(hù)發(fā)現(xiàn)拓?fù)渥兓薷耐負(fù)鋽?shù)據(jù)庫(kù)計(jì)算SPF樹修改路由表第三十二頁，共四十八頁，2022年，8月28日ACBa0 a1 b0 b1 c0 c1L-S建立路由表的初始過程第三十三頁，共四十八頁，2022年，8月28日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ù)庫(kù)啟動(dòng)SPF算法以C為源點(diǎn)計(jì)算SPF樹建立到達(dá)所有信宿的路由表（端口和代價(jià)）c1LSPc0第三十四頁，共四十八頁，2022年，8月28日（1）發(fā)現(xiàn)拓?fù)渥兓疉EDCBFNetXNetXDownNetXDownLSPLSP發(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)廣播第三十五頁，共四十八頁，2022年，8月28日（2）修改拓?fù)鋽?shù)據(jù)庫(kù)AEDCBFNetX全網(wǎng)具有相同的L-S邏輯圖。第三十六頁，共四十八頁，2022年，8月28日AEDCBFNetX（3）各自重新計(jì)算SPF樹2233115251第三十七頁，共四十八頁，2022年，8月28日AEDCBFNetX根據(jù)各自計(jì)算的SPF樹刷新路由表（4）修改各自的路由表a0a1a2NetY路由表路由表路由表路由表路由表221第三十八頁，共四十八頁，2022年，8月28日L-S算法的性能分析優(yōu)點(diǎn)代價(jià)路由刷新問題線路傳輸速率不同網(wǎng)絡(luò)運(yùn)行狀態(tài)不同解決辦法第三十九頁，共四十八頁，2022年，8月28日L-S算法的優(yōu)點(diǎn)所有路由器具有相同的網(wǎng)絡(luò)拓?fù)渲R(shí)（L-S圖）一次性、無修改地向全網(wǎng)廣播LSP路由器根據(jù)全局信息維護(hù)各自的路由表保證鏈路狀態(tài)信息的單向傳播保證算法的收斂性第四十頁，共四十八頁，2022年，8月28日L-S算法的代價(jià)SPF算法計(jì)算和拓?fù)鋽?shù)據(jù)庫(kù)需要更多的CPU和內(nèi)存資源網(wǎng)絡(luò)啟動(dòng)時(shí)的擴(kuò)散路由信息（flood）需要占用很多帶寬資源第四十一頁，共四十八頁，2022年，8月28日線路傳輸速率不同產(chǎn)生的影響E應(yīng)該選擇哪棵SPF樹？NetXDownNetXupNetXDown來自D來自A慢NetXE收到的LSP開始NetX down后來NetX up第四十二頁，共四十八頁，2022年，8月28日網(wǎng)絡(luò)的一部分已經(jīng)啟動(dòng)，而另一部分正待啟動(dòng)網(wǎng)絡(luò)的一部分刷新速度快，而另一部分刷新速度慢造成網(wǎng)絡(luò)的不同部分擁有不同的L-S圖網(wǎng)絡(luò)運(yùn)行狀態(tài)不同產(chǎn)生的影響第四十三頁，共四十八頁，2022年，8月28日L-S對(duì)問題的解決辦法減少對(duì)資源的需求盡可能降低路由刷新頻度用Multicast取代Broadcast(flood)將網(wǎng)