路由算法補充知識

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