第5章路由器與路由算法課件

第五章路由器與路由算法路由器的結構路由算法算法的分類距離矢量算法鏈路狀態(tài)算法移動路由算法.第五章路由器與路由算法路由器的結構.15.1路由器概述局域網(wǎng)（LAN）和撥號用戶需要通過路由器接入因特網(wǎng)因特網(wǎng)的通信子網(wǎng)由各種路由器互連而成路由器是上網(wǎng)的“必由之路”5.1.1路由器在因特網(wǎng)中的地位.5.1路由器概述局域網(wǎng)（LAN）和撥號用戶需要通過路由器25.1.2路由器結構概述路由器的兩個關鍵功能：運行路由算法/協(xié)議(RIP，OSPF，BGP)交換分組于輸入鏈路到輸出鏈路之間.5.1.2路由器結構概述路由器的兩個關鍵功能：.3輸入端口功能分散化的交換：按照給出的分組信宿，使用輸入端口的內(nèi)存中存儲的路由選擇表，查找輸出端口目標:以“線路速度”完成輸入端口的處理排隊:假如分組到達的數(shù)度快于轉(zhuǎn)發(fā)到交換網(wǎng)絡的（switchfabric）速度時緩存物理層：位流級的接收數(shù)據(jù)鏈路層：e.g.,Ethernet.輸入端口功能分散化的交換：物理層：數(shù)據(jù)鏈路層：.4三類交換網(wǎng)絡.三類交換網(wǎng)絡.5內(nèi)存交換（SwitchingViaMemory）第一代路由器:分組通過系統(tǒng)的（單個）CPU拷貝速度受到內(nèi)存帶寬的限制(每個分組需2次穿越系統(tǒng)總線)InputPortOutputPortMemorySystemBus.內(nèi)存交換（SwitchingViaMemory）第一代路6總線交換（SwitchingViaBus）分組通過一條共享的總線從輸入端口的內(nèi)存?zhèn)鬟f到輸出端口的內(nèi)存總線競爭：交換速率受限于總線的帶寬1Gb/s總線，Cisco1900：對訪問接入和企業(yè)級的路由器已經(jīng)足夠(但還不適應在區(qū)域或主干級線路上使用).總線交換（SwitchingViaBus）分組通過一條共7通過內(nèi)聯(lián)網(wǎng)絡交換（SwitchingViaAnInterconnectionNetwork）克服了總線帶寬的限制Banyannetworks，內(nèi)聯(lián)網(wǎng)絡技術在發(fā)展初期是用來連接多處理器系統(tǒng)中的處理器設計先進：把分組分割成固定長度的單元,再把這些單元送入交換網(wǎng)絡Cisco12000：通過內(nèi)聯(lián)網(wǎng)絡交換速度可達若干Gb/s.通過內(nèi)聯(lián)網(wǎng)絡交換（SwitchingViaAnInte8輸出端口的功能緩存：當來自交換網(wǎng)絡的分組到達速度高于傳輸速率時，需要進行緩存調(diào)度原則：從隊列中的分組中選擇傳輸.輸出端口的功能緩存：當來自交換網(wǎng)絡的分組到達速度高于傳輸速率9路由選擇算法抽象:圖中的結點是路由器圖中的線條為物理鏈路鏈路成本：延遲，費用￥，或擁塞的程度目標:在收發(fā)雙方的通信過程中為分組（所經(jīng)由的一系列路由器中）確定一條“好”的路徑路由選擇協(xié)議AEDCBF2213112535“好”路:一般為費用最低的路徑也可以另行定義5.2 路由算法.路由選擇算法抽象:目標:在收發(fā)雙方的通信過程中為分組（所經(jīng)10路由算法是網(wǎng)絡層軟件的一部分通信子網(wǎng)采用數(shù)據(jù)報分組交換方式，每個包都要做路由選擇；通信子網(wǎng)采用虛電路分組交換方式，只需在建立連接時做一次路由選擇。路由算法應具有的特性正確性（correctness）簡單性（simplicity）健壯性（robustness）穩(wěn)定性（stability）公平性（fairness）最優(yōu)性（optimality）5.2.1路由算法應具有的特性.路由算法是網(wǎng)絡層軟件的一部分5.2.1路由算法應具有的特性115.2.2路由算法分類全局或分散的信息?全局:所有路由器都有完整的拓撲邏輯，鏈路成本信息LS(LinkState)算法分散:路由器只了解物理上鄰接的路由器，了解到達這些路由器的鏈路成本DV(DistanceVector)算法靜態(tài)或動態(tài)的?靜態(tài):路由變化較少的情況動態(tài):路由變化較快的情況定期更新為了響應鏈路成本的變化.5.2.2路由算法分類全局或分散的信息?靜態(tài)或動態(tài)的?.12靜態(tài)路由由管理員手工配置。在網(wǎng)絡結構簡單、到目標點只有一條路徑的網(wǎng)絡中，只配置靜態(tài)路由就可正常工作。無自適應功能。當網(wǎng)絡出現(xiàn)問題或因其他原因引起拓撲變化時，靜態(tài)路由不會自動發(fā)生改變，必須要有網(wǎng)絡管理員的介入。路由算法簡單。動態(tài)路由路由器根據(jù)給定的路由算法，通過自學習，構造路由表。具有自適應功能。算法比較復雜。.靜態(tài)路由.135.2.3Internet路由表端口1端口2端口1端口2端口1端口2路由器A路由器B路由器C.5.2.3Internet路由表端口1端口2端口1端口2端14目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）直接端口10直接端口20（RB）1（RB）2目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）（RA）1直接端口10直接端口20（RC）1目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）（RB）2（RB）1直接端口10直接端口20路由器A的路由表路由器B的路由表路由器C的路由表.目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）1215..16Internet路由表包含內(nèi)容目的或網(wǎng)絡掩碼協(xié)議優(yōu)先級優(yōu)先權下一跳地址輸出接口影響路由權的屬性，如右圖。越小，路徑越好。帶寬時延負載可靠性跳數(shù)開銷.Internet路由表包含內(nèi)容目的或網(wǎng)絡掩碼帶寬.17Internet路由協(xié)議路由協(xié)議或路由種類優(yōu)先級缺省值路由算法DIRECT0OSPF10鏈路狀態(tài)算法INTERNALEIGRP50距離矢量算法STATIC60IGRP80距離矢量算法RIP100距離矢量算法IBGP130距離矢量算法OSPFASE150鏈路狀態(tài)EXTERNALEIGRP160距離矢量算法EBGP170距離矢量算法UNKNOWN255.Internet路由協(xié)議路由協(xié)議或路由種類優(yōu)先級缺省值路由算185.2.4最短路徑路由算法屬于靜態(tài)路由算法基本思想構建子網(wǎng)的拓撲圖，圖中的每個結點代表一個路由器，每條弧代表一條通信線路。為了選擇兩個路由器間的路由，算法在圖中找出最短路徑。測量路徑長度的方法結點數(shù)量地理距離傳輸延遲距離、信道帶寬等參數(shù)的加權函數(shù)計算方法：Dijkstra算法AEDCBF22131125最短路徑路由算法屬于靜態(tài)路由算法AEDCBF22195.2.5洪泛算法（Flooding）屬于靜態(tài)路由算法基本思想把收到的每一個包，向除了該包到來的線路外的所有輸出線路發(fā)送。主要問題洪泛要產(chǎn)生大量重復包。解決措施每個包頭包含站點計數(shù)器，每經(jīng)過一站計數(shù)器減1，為0時則丟棄該包；記錄包經(jīng)過的路徑.5.2.5洪泛算法（Flooding）屬于靜態(tài)路由算法20選擇性洪泛算法（selectiveflooding）基本思想洪泛法的一種改進。將進來的每個包僅發(fā)送到與正確方向接近的線路上；或者按一定的概率選擇發(fā)送。應用情況對路由器和線路的資源過于浪費，實際很少直接采用；具有極好的健壯性，可用于軍事應用；作為衡量標準評價其它路由算法。.選擇性洪泛算法（selectiveflooding）基本思215.2.6基于流量的路由算法（Flow-BasedRouting）屬于靜態(tài)路由算法基本思想既考慮拓撲結構，又兼顧網(wǎng)絡負荷；前提：每對結點間平均數(shù)據(jù)流是相對穩(wěn)定和可預測的；根據(jù)網(wǎng)絡帶寬和平均流量，可得出平均包延遲，因此路由選擇問題歸結為找產(chǎn)生網(wǎng)絡最小延遲的路由選擇算法。提前離線（off-line）計算。.5.2.6基于流量的路由算法（Flow-BasedRo22需要預知的信息網(wǎng)絡拓撲結構；通信量矩陣Fij；線路帶寬矩陣Cij；路由算法（可能是臨時的）。.需要預知的信息.23..241/=800bits根據(jù)排隊論，平均延遲T=1/(C-).1/=800bits.255.2.7距離矢量路由算法（DistanceVectorRouting）屬于動態(tài)路由算法，也稱Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP協(xié)議采用。基本思想每個路由器維護一張表，表中給出了到每個目的地的已知最佳距離和線路，并通過與相鄰路由器交換距離信息來更新表；.5.2.7距離矢量路由算法（DistanceVecto26每隔一段時間，路由器向所有鄰居結點發(fā)送它到每個目的結點的距離表，同時它也接收每個鄰居結點發(fā)來的距離表；鄰居結點X發(fā)來的表中，X到路由器i的距離為Xi，本路由器到X的距離為m，則路由器經(jīng)過X到i的距離為Xi+m。根據(jù)不同鄰居發(fā)來的信息，計算Xi+m，并取最小值，更新本路由器的路由表；注意：本路由器中的老路由表在計算中不被使用.每隔一段時間，路由器向所有鄰居結點發(fā)送它到每個目的結點的距離27..285.2.8鏈路狀態(tài)路由算法（LinkStateRouting）距離向量路由算法的主要問題選擇路由時，沒有考慮線路帶寬；路由收斂速度慢。鏈路狀態(tài)路由算法發(fā)現(xiàn)鄰居結點，并學習它們的網(wǎng)絡地址路由器啟動后，通過發(fā)送HELLO包發(fā)現(xiàn)鄰居結點兩個或多個路由器連在一個LAN時，引入人工結點.5.2.8鏈路狀態(tài)路由算法（LinkStateRout29..30測量到每個鄰居結點的延遲或開銷一種直接的方法是：發(fā)送一個要對方立即響應的ECHO包，來回時間除以2即為延遲。將所有學習到的內(nèi)容封裝成一個包包以發(fā)送方的標識符開頭，后面是序號、壽命和一個鄰居結點列表；列表中對應每個鄰居結點，都有發(fā)送方到它們的延遲或開銷；鏈路狀態(tài)包定期創(chuàng)建或發(fā)生重大事件時創(chuàng)建。.測量到每個鄰居結點的延遲或開銷.31..32將這個包發(fā)送給所有其它路由器基本思想：洪泛鏈路狀態(tài)包，為控制洪泛，每個包包含一個序號，每次發(fā)送新包時加1。路由器記錄信息對(源路由器，序號)，當一個鏈路狀態(tài)包到達時，若是新的，則分發(fā)；若是重復的，則丟棄；若序號比路由器記錄中的最大序號小，則認為過時而丟棄；存在的問題與改進序號循環(huán)使用會混淆，解決辦法：使用32位序號；路由器崩潰后，序號重置；序號出錯；.將這個包發(fā)送給所有其它路由器.33第二、三問題的解決辦法：增加年齡（age）域，每秒鐘年齡減1，為零則丟棄。鏈路狀態(tài)包到達后，延遲一段時間，并與其它已到達的來自同一路由器的鏈路狀態(tài)包比較序號，丟棄重復包，保留新包；鏈路狀態(tài)包需要應答；計算到每個其它路由器的最短路徑根據(jù)Dijkstra算法計算最短路徑實用協(xié)議OSPFIS-IS.第二、三問題的解決辦法：增加年齡（age）域，每秒鐘年齡減1345.2.9鏈路狀態(tài)算法（LS）和距離向量算法（DV）的比較算法復雜性LS路由信息向全網(wǎng)發(fā)送N節(jié)點，E個連接的情況下，每個節(jié)點發(fā)送O(nE)的報文DV僅在鄰居節(jié)點之間交換.5.2.9鏈路狀態(tài)算法（LS）和距離向量算法（DV）的比較35收斂（Convergence）速度LS使用最短路徑優(yōu)先算法，算法復雜度為O(n**2)n個結點（不包括源結點），需要n*(n+1)/2次比較使用更有效的實現(xiàn)方法，算法復雜度可以達到O(nlogn)可能存在路由振蕩（oscillations）（研究熱點問題）DV收斂時間不定可能會出現(xiàn)路由循環(huán)count-to-infinity問題.收斂（Convergence）速度.36健壯性:如果路由器不能正常工作會發(fā)生什么?LS結點會廣播錯誤的鏈路開銷每個結點只計算自己的路由表DV結點會廣播錯誤的路徑開銷每個結點的路由表被別的結點使用，錯誤會傳播到全網(wǎng).健壯性:如果路由器不能正常工作會發(fā)生什么?.37第五章路由器與路由算法路由器的結構路由算法算法的分類距離矢量算法鏈路狀態(tài)算法移動路由算法.第五章路由器與路由算法路由器的結構.385.1路由器概述局域網(wǎng)（LAN）和撥號用戶需要通過路由器接入因特網(wǎng)因特網(wǎng)的通信子網(wǎng)由各種路由器互連而成路由器是上網(wǎng)的“必由之路”5.1.1路由器在因特網(wǎng)中的地位.5.1路由器概述局域網(wǎng)（LAN）和撥號用戶需要通過路由器395.1.2路由器結構概述路由器的兩個關鍵功能：運行路由算法/協(xié)議(RIP，OSPF，BGP)交換分組于輸入鏈路到輸出鏈路之間.5.1.2路由器結構概述路由器的兩個關鍵功能：.40輸入端口功能分散化的交換：按照給出的分組信宿，使用輸入端口的內(nèi)存中存儲的路由選擇表，查找輸出端口目標:以“線路速度”完成輸入端口的處理排隊:假如分組到達的數(shù)度快于轉(zhuǎn)發(fā)到交換網(wǎng)絡的（switchfabric）速度時緩存物理層：位流級的接收數(shù)據(jù)鏈路層：e.g.,Ethernet.輸入端口功能分散化的交換：物理層：數(shù)據(jù)鏈路層：.41三類交換網(wǎng)絡.三類交換網(wǎng)絡.42內(nèi)存交換（SwitchingViaMemory）第一代路由器:分組通過系統(tǒng)的（單個）CPU拷貝速度受到內(nèi)存帶寬的限制(每個分組需2次穿越系統(tǒng)總線)InputPortOutputPortMemorySystemBus.內(nèi)存交換（SwitchingViaMemory）第一代路43總線交換（SwitchingViaBus）分組通過一條共享的總線從輸入端口的內(nèi)存?zhèn)鬟f到輸出端口的內(nèi)存總線競爭：交換速率受限于總線的帶寬1Gb/s總線，Cisco1900：對訪問接入和企業(yè)級的路由器已經(jīng)足夠(但還不適應在區(qū)域或主干級線路上使用).總線交換（SwitchingViaBus）分組通過一條共44通過內(nèi)聯(lián)網(wǎng)絡交換（SwitchingViaAnInterconnectionNetwork）克服了總線帶寬的限制Banyannetworks，內(nèi)聯(lián)網(wǎng)絡技術在發(fā)展初期是用來連接多處理器系統(tǒng)中的處理器設計先進：把分組分割成固定長度的單元,再把這些單元送入交換網(wǎng)絡Cisco12000：通過內(nèi)聯(lián)網(wǎng)絡交換速度可達若干Gb/s.通過內(nèi)聯(lián)網(wǎng)絡交換（SwitchingViaAnInte45輸出端口的功能緩存：當來自交換網(wǎng)絡的分組到達速度高于傳輸速率時，需要進行緩存調(diào)度原則：從隊列中的分組中選擇傳輸.輸出端口的功能緩存：當來自交換網(wǎng)絡的分組到達速度高于傳輸速率46路由選擇算法抽象:圖中的結點是路由器圖中的線條為物理鏈路鏈路成本：延遲，費用￥，或擁塞的程度目標:在收發(fā)雙方的通信過程中為分組（所經(jīng)由的一系列路由器中）確定一條“好”的路徑路由選擇協(xié)議AEDCBF2213112535“好”路:一般為費用最低的路徑也可以另行定義5.2 路由算法.路由選擇算法抽象:目標:在收發(fā)雙方的通信過程中為分組（所經(jīng)47路由算法是網(wǎng)絡層軟件的一部分通信子網(wǎng)采用數(shù)據(jù)報分組交換方式，每個包都要做路由選擇；通信子網(wǎng)采用虛電路分組交換方式，只需在建立連接時做一次路由選擇。路由算法應具有的特性正確性（correctness）簡單性（simplicity）健壯性（robustness）穩(wěn)定性（stability）公平性（fairness）最優(yōu)性（optimality）5.2.1路由算法應具有的特性.路由算法是網(wǎng)絡層軟件的一部分5.2.1路由算法應具有的特性485.2.2路由算法分類全局或分散的信息?全局:所有路由器都有完整的拓撲邏輯，鏈路成本信息LS(LinkState)算法分散:路由器只了解物理上鄰接的路由器，了解到達這些路由器的鏈路成本DV(DistanceVector)算法靜態(tài)或動態(tài)的?靜態(tài):路由變化較少的情況動態(tài):路由變化較快的情況定期更新為了響應鏈路成本的變化.5.2.2路由算法分類全局或分散的信息?靜態(tài)或動態(tài)的?.49靜態(tài)路由由管理員手工配置。在網(wǎng)絡結構簡單、到目標點只有一條路徑的網(wǎng)絡中，只配置靜態(tài)路由就可正常工作。無自適應功能。當網(wǎng)絡出現(xiàn)問題或因其他原因引起拓撲變化時，靜態(tài)路由不會自動發(fā)生改變，必須要有網(wǎng)絡管理員的介入。路由算法簡單。動態(tài)路由路由器根據(jù)給定的路由算法，通過自學習，構造路由表。具有自適應功能。算法比較復雜。.靜態(tài)路由.505.2.3Internet路由表端口1端口2端口1端口2端口1端口2路由器A路由器B路由器C.5.2.3Internet路由表端口1端口2端口1端口2端51目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）直接端口10直接端口20（RB）1（RB）2目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）（RA）1直接端口10直接端口20（RC）1目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）（RB）2（RB）1直接端口10直接端口20路由器A的路由表路由器B的路由表路由器C的路由表.目的網(wǎng)絡號下一個轉(zhuǎn)發(fā)路由器端口或IP地址度量（轉(zhuǎn)發(fā)次數(shù)）1252..53Internet路由表包含內(nèi)容目的或網(wǎng)絡掩碼協(xié)議優(yōu)先級優(yōu)先權下一跳地址輸出接口影響路由權的屬性，如右圖。越小，路徑越好。帶寬時延負載可靠性跳數(shù)開銷.Internet路由表包含內(nèi)容目的或網(wǎng)絡掩碼帶寬.54Internet路由協(xié)議路由協(xié)議或路由種類優(yōu)先級缺省值路由算法DIRECT0OSPF10鏈路狀態(tài)算法INTERNALEIGRP50距離矢量算法STATIC60IGRP80距離矢量算法RIP100距離矢量算法IBGP130距離矢量算法OSPFASE150鏈路狀態(tài)EXTERNALEIGRP160距離矢量算法EBGP170距離矢量算法UNKNOWN255.Internet路由協(xié)議路由協(xié)議或路由種類優(yōu)先級缺省值路由算555.2.4最短路徑路由算法屬于靜態(tài)路由算法基本思想構建子網(wǎng)的拓撲圖，圖中的每個結點代表一個路由器，每條弧代表一條通信線路。為了選擇兩個路由器間的路由，算法在圖中找出最短路徑。測量路徑長度的方法結點數(shù)量地理距離傳輸延遲距離、信道帶寬等參數(shù)的加權函數(shù)計算方法：Dijkstra算法AEDCBF22131125最短路徑路由算法屬于靜態(tài)路由算法AEDCBF22565.2.5洪泛算法（Flooding）屬于靜態(tài)路由算法基本思想把收到的每一個包，向除了該包到來的線路外的所有輸出線路發(fā)送。主要問題洪泛要產(chǎn)生大量重復包。解決措施每個包頭包含站點計數(shù)器，每經(jīng)過一站計數(shù)器減1，為0時則丟棄該包；記錄包經(jīng)過的路徑.5.2.5洪泛算法（Flooding）屬于靜態(tài)路由算法57選擇性洪泛算法（selectiveflooding）基本思想洪泛法的一種改進。將進來的每個包僅發(fā)送到與正確方向接近的線路上；或者按一定的概率選擇發(fā)送。應用情況對路由器和線路的資源過于浪費，實際很少直接采用；具有極好的健壯性，可用于軍事應用；作為衡量標準評價其它路由算法。.選擇性洪泛算法（selectiveflooding）基本思585.2.6基于流量的路由算法（Flow-BasedRouting）屬于靜態(tài)路由算法基本思想既考慮拓撲結構，又兼顧網(wǎng)絡負荷；前提：每對結點間平均數(shù)據(jù)流是相對穩(wěn)定和可預測的；根據(jù)網(wǎng)絡帶寬和平均流量，可得出平均包延遲，因此路由選擇問題歸結為找產(chǎn)生網(wǎng)絡最小延遲的路由選擇算法。提前離線（off-line）計算。.5.2.6基于流量的路由算法（Flow-BasedRo59需要預知的信息網(wǎng)絡拓撲結構；通信量矩陣Fij；線路帶寬矩陣Cij；路由算法（可能是臨時的）。.需要預知的信息.60..611/=800bits根據(jù)排隊論，平均延遲T=1/(C-).1/=800bits.625.2.7距離矢量路由算法（DistanceVectorRouting）屬于動態(tài)路由算法，也稱Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP協(xié)議采用?；舅枷朊總€路由器維護一張表，表中給出了到每個目的地的已知最佳距離和線路，并通過與相鄰路由器交換距離信息來更新表；.5.2.7距離矢量路由算法（DistanceVecto63每隔一段時間，路由器向所有鄰居結點發(fā)送它到每個目的結點的距離表，同時它也接收每個鄰居結點發(fā)來的距離表；鄰居結點X發(fā)來的表中，X到路由器i的距離為Xi，本路由器到X的距離為m，則路由器經(jīng)過X到i的距離為Xi+m。根據(jù)不同鄰居發(fā)來的信息，計算Xi+m，并取最小值，更新本路由器的路由表；注意：本路由器中的老路由表在計算中不被使用.每隔一段時間，路由器向所有鄰居結點發(fā)送它到每個目的結點的距離64..655.2.8鏈路狀態(tài)路由算法（LinkStateRouting）距離向量路由算法的主要問題選擇路由時，沒有考慮線路帶寬；路由收斂速度慢。鏈路狀態(tài)路由算法發(fā)現(xiàn)鄰居結點，并學習它們的網(wǎng)絡地址路由器啟動后，通過發(fā)送HELLO包