第9章 路由協(xié)議概述

1、要求：要求：1掌握路由表建立和維護的兩種方式：靜態(tài)配置和動掌握路由表建立和維護的兩種方式：靜態(tài)配置和動態(tài)交換路由信息；態(tài)交換路由信息；2掌握掌握Internet的路由體系結(jié)構(gòu)的路由體系結(jié)構(gòu),特別是自治系統(tǒng)特別是自治系統(tǒng)AS的的概念和作用；概念和作用；3掌握兩種路由更新算法掌握兩種路由更新算法:矢量距離算法和矢量距離算法和SPF算法。算法。路由協(xié)議解決的問題：路由協(xié)議解決的問題：如何獲得路由表？如何獲得路由表？H1H2R1R5R2R3R4路徑：路徑：H1-R1-R2-R4-H2問題：問題：（1）路由器的路由表如何獲?。浚┞酚善鞯穆酚杀砣绾潍@??？（2）為什么選擇這條路徑？）為什么選擇這條路徑？（3

2、）假設(shè)）假設(shè)R2與與R4的連接斷掉，如何通知的連接斷掉，如何通知R1？（4）在）在Internet中，是否每個路由器都必須了解其中，是否每個路由器都必須了解其它路由器的情況？它路由器的情況？兩種方式：兩種方式：靜態(tài)配置靜態(tài)配置and動態(tài)路由交換動態(tài)路由交換1.靜態(tài)配置：管理員手工配置和更新路由表靜態(tài)配置：管理員手工配置和更新路由表優(yōu)點：優(yōu)點：節(jié)省路由器的處理時間、存儲空間以及網(wǎng)絡(luò)節(jié)省路由器的處理時間、存儲空間以及網(wǎng)絡(luò)帶寬帶寬缺陷：缺陷：對于鏈路故障及拓撲結(jié)構(gòu)變化的響應(yīng)速度慢對于鏈路故障及拓撲結(jié)構(gòu)變化的響應(yīng)速度慢H1H2R1R5R2R3R4適用環(huán)境：適用環(huán)境：拓撲相對穩(wěn)定，路由器個數(shù)較少拓撲相對

3、穩(wěn)定，路由器個數(shù)較少2.動態(tài)路由信息交換：利用路由協(xié)議交換路由信息，并動態(tài)路由信息交換：利用路由協(xié)議交換路由信息，并根據(jù)拓撲結(jié)構(gòu)的變化動態(tài)更新路由表根據(jù)拓撲結(jié)構(gòu)的變化動態(tài)更新路由表優(yōu)點：優(yōu)點：自動適應(yīng)鏈路故障及拓撲結(jié)構(gòu)的變化自動適應(yīng)鏈路故障及拓撲結(jié)構(gòu)的變化缺陷：缺陷：耗費路由器的處理時間、存儲空間以及網(wǎng)絡(luò)帶耗費路由器的處理時間、存儲空間以及網(wǎng)絡(luò)帶寬寬適用環(huán)境：適用環(huán)境：路由器較多的大規(guī)模網(wǎng)絡(luò)路由器較多的大規(guī)模網(wǎng)絡(luò)H1H2R1R5R2R3R4（1）路徑存在性）路徑存在性（2）路徑最優(yōu)性）路徑最優(yōu)性1.路徑存在性路徑存在性路由表的兩個普遍特點：路由表的兩個普遍特點：（1）路由表中不包含到達所有目的

4、地的路由）路由表中不包含到達所有目的地的路由（2）路由表中存在默認路由）路由表中存在默認路由要求：要求：（1）單個路由器為連接關(guān)系所做的貢獻是局部的）單個路由器為連接關(guān)系所做的貢獻是局部的（2）所有路由器組成的系統(tǒng)是完備的）所有路由器組成的系統(tǒng)是完備的問題：如何確保各個路由器維護信息的一致性？問題：如何確保各個路由器維護信息的一致性？答案：答案：不同路由器更新路由表的信息是一致的，使不同路由器更新路由表的信息是一致的，使得它們對網(wǎng)絡(luò)拓撲結(jié)構(gòu)有著一致性的認識。得它們對網(wǎng)絡(luò)拓撲結(jié)構(gòu)有著一致性的認識。2.路由度量路由度量問題：問題：如何確定一條路徑是最優(yōu)的？如何確定一條路徑是最優(yōu)的？解答：解答：選擇

5、不同的度量指標選擇不同的度量指標（1）帶寬（靜態(tài)指標）帶寬（靜態(tài)指標）（2）延遲）延遲（3）負載）負載（4）可靠性）可靠性（5）跳數(shù)）跳數(shù)（6）其它指標，比如代價）其它指標，比如代價理想情況：理想情況：綜合利用以上各指標綜合利用以上各指標缺陷：缺陷：可能會造成路由震蕩可能會造成路由震蕩實現(xiàn)：實現(xiàn)：簡單的算法僅考慮一個要素，復雜的則綜合簡單的算法僅考慮一個要素，復雜的則綜合考慮（如考慮（如DUAL）最常用的：最常用的：基于跳數(shù)基于跳數(shù)（1）非自適應(yīng)）非自適應(yīng)（2）自適應(yīng)）自適應(yīng)1.非自適應(yīng)算法非自適應(yīng)算法（1）不考慮當前的拓撲結(jié)構(gòu)和網(wǎng)絡(luò)流量）不考慮當前的拓撲結(jié)構(gòu)和網(wǎng)絡(luò)流量（2）設(shè)置中心路由器，由

6、管理員預先為每個路由器）設(shè)置中心路由器，由管理員預先為每個路由器設(shè)置路由表設(shè)置路由表（3）拓撲發(fā)生變化時，由管理員操作中心路由器，）拓撲發(fā)生變化時，由管理員操作中心路由器，更新路由表更新路由表（4）適用于規(guī)模小，拓撲結(jié)構(gòu)變化少的網(wǎng)絡(luò)）適用于規(guī)模小，拓撲結(jié)構(gòu)變化少的網(wǎng)絡(luò)2.自適應(yīng)自適應(yīng)算法算法（1）矢量）矢量-距離算法距離算法（2）鏈路狀態(tài)算法）鏈路狀態(tài)算法（1）矢量距離路由算法矢量距離路由算法(Bellman、Bellman-Ford和和Ford-Fulkerson算法算法)思想：思想：以跳數(shù)作為度量值，通過交換路由表，計算出以跳數(shù)作為度量值，通過交換路由表，計算出所有已知的最短路由，更新路由

7、表。所有已知的最短路由，更新路由表。表項格式：表項格式：跳數(shù)：跳數(shù)：從源站到目的站間所經(jīng)過的路由器數(shù)目。從源站到目的站間所經(jīng)過的路由器數(shù)目。步驟：步驟：初始化初始化:路由器啟動時，對每個直接相連的網(wǎng)絡(luò)生路由器啟動時，對每個直接相連的網(wǎng)絡(luò)生成一個表項，成一個表項，hop數(shù)都為數(shù)都為0。路由交換路由交換:路由器周期性向相鄰路由器廣播自己的路由器周期性向相鄰路由器廣播自己的整個路由表。整個路由表。(交換信息是交換信息是)路由表更新路由表更新:路由器每收到一個鄰站的路由表，即路由器每收到一個鄰站的路由表，即更新自己的路由表。更新自己的路由表。(假設(shè)假設(shè)K收到收到J的路由表的路由表)(1)K不知道目的站

8、，則不知道目的站，則加入加入(2)有通過有通過J的更短路，則的更短路，則替換替換(3)原下站為原下站為J的距離有變化，則的距離有變化，則修改修改目的站目的站距離距離下一跳下一跳網(wǎng)絡(luò)網(wǎng)絡(luò)10直接直接網(wǎng)絡(luò)網(wǎng)絡(luò)20直接直接網(wǎng)絡(luò)網(wǎng)絡(luò)48路由器路由器L網(wǎng)絡(luò)網(wǎng)絡(luò)175路由器路由器M網(wǎng)絡(luò)網(wǎng)絡(luò)246路由器路由器J網(wǎng)絡(luò)網(wǎng)絡(luò)302路由器路由器Q網(wǎng)絡(luò)網(wǎng)絡(luò)422路由器路由器J目的站目的站距離距離網(wǎng)絡(luò)網(wǎng)絡(luò)12網(wǎng)絡(luò)網(wǎng)絡(luò)43網(wǎng)絡(luò)網(wǎng)絡(luò)176網(wǎng)絡(luò)網(wǎng)絡(luò)214網(wǎng)絡(luò)網(wǎng)絡(luò)245網(wǎng)絡(luò)網(wǎng)絡(luò)3010網(wǎng)絡(luò)網(wǎng)絡(luò)423目的站目的站距離距離下一跳下一跳網(wǎng)絡(luò)網(wǎng)絡(luò)10直接直接網(wǎng)絡(luò)網(wǎng)絡(luò)20直接直接網(wǎng)絡(luò)網(wǎng)絡(luò)44J（替換）（替換）網(wǎng)絡(luò)網(wǎng)絡(luò)175路由器路由器M

9、網(wǎng)絡(luò)網(wǎng)絡(luò)246路由器路由器J網(wǎng)絡(luò)網(wǎng)絡(luò)302路由器路由器Q網(wǎng)絡(luò)網(wǎng)絡(luò)424J（修改）（修改）網(wǎng)絡(luò)網(wǎng)絡(luò)215J（增加）（增加）思想：思想：通過交換鏈路狀態(tài)，讓通過交換鏈路狀態(tài)，讓AS中的每個路由器中的每個路由器都有一張該都有一張該AS的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖。的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖。節(jié)點：路由器；邊：網(wǎng)絡(luò)。節(jié)點：路由器；邊：網(wǎng)絡(luò)。使用使用Dijkstra算法求最短路徑，計算該路由器到其算法求最短路徑，計算該路由器到其它目的站的最短路徑，然后更新路由表。它目的站的最短路徑，然后更新路由表。優(yōu)點：優(yōu)點：每個路由器使用相同的原始數(shù)據(jù)，具有良好的每個路由器使用相同的原始數(shù)據(jù)，具有良好的收斂性。收斂性。每個路由器的鏈路狀態(tài)

10、報文尺寸取決于只連鏈路每個路由器的鏈路狀態(tài)報文尺寸取決于只連鏈路的數(shù)量，具有較好的規(guī)?？蓴U展性的數(shù)量，具有較好的規(guī)模可擴展性步驟：步驟：鏈路狀態(tài)檢測：鏈路狀態(tài)檢測：周期性發(fā)測試報文，檢查直接相周期性發(fā)測試報文，檢查直接相鄰的路由器狀態(tài)，并按鄰的路由器狀態(tài)，并按“n中取中取k”原則進行狀態(tài)檢查原則進行狀態(tài)檢查。路由信息廣播：路由信息廣播：路由器周期性廣播它的各個鏈路路由器周期性廣播它的各個鏈路狀態(tài)。所有參與狀態(tài)。所有參與SPF的路由器負責轉(zhuǎn)發(fā)收到的鏈路狀的路由器負責轉(zhuǎn)發(fā)收到的鏈路狀態(tài)態(tài)。路由表更新：路由表更新：收到鏈路狀態(tài)的路由器更新自己的收到鏈路狀態(tài)的路由器更新自己的網(wǎng)絡(luò)拓撲圖，并用網(wǎng)絡(luò)拓撲圖

11、，并用Dijkstra算法計算最短路徑算法計算最短路徑。路由體系的內(nèi)容：路由體系的內(nèi)容：如何對如何對Internet中的路由器進行劃中的路由器進行劃分、管理和控制，以便有效地交換路由信息分、管理和控制，以便有效地交換路由信息路由體系的重要性：路由體系的重要性：決定了互聯(lián)網(wǎng)的運行效率決定了互聯(lián)網(wǎng)的運行效率Internet路由體系的發(fā)展：路由體系的發(fā)展：（1）最早的核心路由體系）最早的核心路由體系（2）隨后的對等主干路由體系）隨后的對等主干路由體系（3）當前的自治系統(tǒng)路由體系）當前的自治系統(tǒng)路由體系 1.核心路由器與核心體系結(jié)構(gòu)核心路由器與核心體系結(jié)構(gòu) ARPANET主干網(wǎng)主干網(wǎng)本地網(wǎng)絡(luò)本地網(wǎng)絡(luò)2

12、R2本地網(wǎng)絡(luò)本地網(wǎng)絡(luò)nRnARPANET主干網(wǎng)主干網(wǎng)本地網(wǎng)絡(luò)本地網(wǎng)絡(luò)2本地網(wǎng)絡(luò)本地網(wǎng)絡(luò)2本地網(wǎng)絡(luò)本地網(wǎng)絡(luò)m本地網(wǎng)絡(luò)本地網(wǎng)絡(luò)1R1核心路由器核心路由器k1k2kn核心路由器核心路由器G1G2Gk外圍路由器外圍路由器2.選路模式選路模式核心網(wǎng)關(guān)核心網(wǎng)關(guān):構(gòu)成核心系統(tǒng)，集構(gòu)成核心系統(tǒng)，集中管理中管理,提供到所有目的地的提供到所有目的地的路由。路由。外圍網(wǎng)關(guān)外圍網(wǎng)關(guān):為外出數(shù)據(jù)報提供為外出數(shù)據(jù)報提供默認路由默認路由,發(fā)往某核心網(wǎng)關(guān)發(fā)往某核心網(wǎng)關(guān);將將核心網(wǎng)關(guān)傳入的數(shù)據(jù)報投遞核心網(wǎng)關(guān)傳入的數(shù)據(jù)報投遞到直連的物理網(wǎng)絡(luò)。到直連的物理網(wǎng)絡(luò)。問題：問題：兩主干間多重接入，造成選路困難。兩主干間多重接入，造成選路

13、困難。 具有非法目的地址的數(shù)據(jù)報形成選路回路具有非法目的地址的數(shù)據(jù)報形成選路回路契機：契機：NSFNET的引入的引入R2RnR1ARPANET主干網(wǎng)主干網(wǎng)主機主機2主機主機1NSFNET主干網(wǎng)主干網(wǎng)主機主機4主機主機3選路模式：選路模式：各主干網(wǎng)內(nèi)部按核心結(jié)構(gòu)方式進行選路各主干網(wǎng)內(nèi)部按核心結(jié)構(gòu)方式進行選路各核心網(wǎng)關(guān)擁有對另一部分的默認路由。各核心網(wǎng)關(guān)擁有對另一部分的默認路由。 核心核心C1核心核心C2核心核心C1內(nèi)網(wǎng)點的內(nèi)網(wǎng)點的非法目的分組非法目的分組x到核心到核心C2的的默認路由默認路由P1到核心到核心C1的的默認路由默認路由P2Internet主干網(wǎng)主干網(wǎng)NAP1NAP2NAPnNSP1N

14、SP2NSPNISP1ISP1ISP1核心層核心層分布層分布層接入層接入層如何限制選路信息的傳播如何限制選路信息的傳播? 參與交換路由信息的路由器群組規(guī)模不能太大。參與交換路由信息的路由器群組規(guī)模不能太大。指導原則：指導原則：（1）廣域網(wǎng)范圍）廣域網(wǎng)范圍12個路由器個路由器 （2）若干局域網(wǎng)范圍）若干局域網(wǎng)范圍60個路由器。個路由器。多主干下選路問題如何解決？多主干下選路問題如何解決？說明說明:（1）AS自治的主要內(nèi)容是選路自治自治的主要內(nèi)容是選路自治,AS可自由地選可自由地選擇路由算法；擇路由算法；（2）AS必須嚴格界定，并被賦予全局唯一的自治必須嚴格界定，并被賦予全局唯一的自治系統(tǒng)號系統(tǒng)號(NIC分配分配)；（3）主干網(wǎng)絡(luò)本身也構(gòu)成一個）主干網(wǎng)絡(luò)本身也構(gòu)成一