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

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

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

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

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

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

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

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

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

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

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

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

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

13、困難。 具有非法目的地址的數據報形成選路回路具有非法目的地址的數據報形成選路回路契機：契機：NSFNET的引入的引入R2RnR1ARPANET主干網主干網主機主機2主機主機1NSFNET主干網主干網主機主機4主機主機3選路模式：選路模式：各主干網內部按核心結構方式進行選路各主干網內部按核心結構方式進行選路各核心網關擁有對另一部分的默認路由。各核心網關擁有對另一部分的默認路由。 核心核心C1核心核心C2核心核心C1內網點的內網點的非法目的分組非法目的分組x到核心到核心C2的的默認路由默認路由P1到核心到核心C1的的默認路由默認路由P2Internet主干網主干網NAP1NAP2NAPnNSP1N

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