1、第第9章章 路由協議概述路由協議概述主要內容主要內容1、引言、引言2、路由表的建立與維護、路由表的建立與維護3、路徑確定、路徑確定4、路由算法、路由算法5、Internet路由體系發展路由體系發展6、大規模網絡拓撲發現、大規模網絡拓撲發現基本要求基本要求掌握路由表建立和維護的兩種方式：靜態配置和動態交換掌握路由表建立和維護的兩種方式：靜態配置和動態交換路由信息；路由信息；掌握兩種路由更新算法掌握兩種路由更新算法:矢量距離算法和矢量距離算法和SPF算法算法;掌握掌握Internet的路由體系結構，特別是自治系統的路由體系結構，特別是自治系統AS的概念的概念和作用和作用.學習內容學習內容1、引言、

2、引言2、路由表的建立與維護、路由表的建立與維護3、路徑確定、路徑確定4、路由算法、路由算法5、Internet路由體系發展路由體系發展6、大規模網絡拓撲發現、大規模網絡拓撲發現問題的提出問題的提出 問題：問題：（1）為什么選擇這條路徑？）為什么選擇這條路徑？（2）路由器的路由表如何獲取）路由器的路由表如何獲取?（3）假設）假設R2與與R4的連接斷掉，如何通知的連接斷掉，如何通知R1？（4）在）在Internet中，是否每個路由器都必須了解其它路由器中，是否每個路由器都必須了解其它路由器的情況？的情況？H1H2R1R5R2R3R4路徑：路徑：H1-R1-R2-R4-H2學習內容學習內容1、引言、

3、引言2、路由表的建立與維護、路由表的建立與維護3、路徑確定、路徑確定4、路由算法、路由算法5、Internet路由體系發展路由體系發展6、大規模網絡拓撲發現、大規模網絡拓撲發現路由表的建立和維護路由表的建立和維護 v靜態配置：管理員靜態配置：管理員手工手工配置和更新路由表配置和更新路由表優點：節省路由器的處理時間、存儲空間以及網絡帶寬優點：節省路由器的處理時間、存儲空間以及網絡帶寬缺陷：對于鏈路故障及拓撲結構變化的響應速度慢缺陷：對于鏈路故障及拓撲結構變化的響應速度慢兩種方式：靜態配置兩種方式：靜態配置 和和 動態路由交換動態路由交換H1H2R1R5R2R3R4適用環境：拓撲相對穩定，路由器個

4、數較少適用環境：拓撲相對穩定，路由器個數較少v 利用利用路由協議路由協議交換路由信息，并根據拓撲結構的變化動態更交換路由信息，并根據拓撲結構的變化動態更新路由表新路由表優點：自動適應鏈路故障及拓撲結構的變化優點：自動適應鏈路故障及拓撲結構的變化缺陷：耗費網絡帶寬、路由器的處理時間和存儲空間缺陷：耗費網絡帶寬、路由器的處理時間和存儲空間適用環境：路由器較多的大規模網絡適用環境：路由器較多的大規模網絡H1H2R1R5R2R3R4動態路由信息交換動態路由信息交換學習內容學習內容1、引言、引言2、路由表的建立與維護、路由表的建立與維護3、路徑確定、路徑確定4、路由算法、路由算法5、Internet路由

5、體系發展路由體系發展6、大規模網絡拓撲發現、大規模網絡拓撲發現什么是選路？什么是選路？1230111到達分組首部的值到達分組首部的值選路算法選路算法本地轉發表本地轉發表首部值首部值輸出鏈路輸出鏈路01000101011110013221 集中式集中式 分布式分布式轉發表的配置方法：轉發表的配置方法： 靜態：人工配置靜態：人工配置 動態：選路協議動態：選路協議選路涉及到的選路涉及到的2個關鍵問題個關鍵問題（1）路徑存在性）路徑存在性 （2）路徑最優性）路徑最優性路徑存在性路徑存在性路由器采用路由器采用“下一跳下一跳”選路；選路；路由表的兩個普遍特點：路由表的兩個普遍特點：（1）路由表中不包含到達

6、所有目的地的路由）路由表中不包含到達所有目的地的路由（2）路由表中存在默認路由）路由表中存在默認路由這表明：這表明：（1）單個路由器為連接關系所做的貢獻是局部的）單個路由器為連接關系所做的貢獻是局部的（2）所有路由器組成的系統是完備的）所有路由器組成的系統是完備的問題：如何確定一條路徑是最優的？問題：如何確定一條路徑是最優的？ 選擇不同的度量指標：選擇不同的度量指標：（1）帶寬）帶寬 （2）延遲）延遲 （靜態指標）（靜態指標） （3）負載）負載 （4）可靠性）可靠性 （動態指標）（動態指標） （5）跳數）跳數（6）其它指標，比如代價）其它指標，比如代價理想情況：綜合利用以上各指標理想情況：綜合

7、利用以上各指標缺陷：選擇動態度量要素可能會造成路由震蕩缺陷：選擇動態度量要素可能會造成路由震蕩實現：簡單的算法僅考慮一個要素，復雜的則綜合考慮（如實現：簡單的算法僅考慮一個要素，復雜的則綜合考慮（如DUAL）最常用的：基于跳數最常用的：基于跳數路由度量路由度量學習內容學習內容1、引言、引言2、路由表的建立與維護、路由表的建立與維護3、路徑確定、路徑確定4、路由算法、路由算法5、Internet路由體系發展路由體系發展6、大規模網絡拓撲發現、大規模網絡拓撲發現選路算法選路算法 1. 非自適應算法非自適應算法 不考慮當前的拓撲結構和網絡流量不考慮當前的拓撲結構和網絡流量 設置設置中心路由器中心路由

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

9、最短路由，并更新路由表。，并更新路由表。自適應算法自適應算法-矢量距離路由算法矢量距離路由算法表項格式：表項格式： 跳數：從源站到目的站間所經過的路由器數目。跳數：從源站到目的站間所經過的路由器數目。 如何建立路由表如何建立路由表? 初始化：初始化：路由器啟動時，對每個直接相連的網絡生成一個路由器啟動時，對每個直接相連的網絡生成一個表項，表項，hop數都為數都為0。 路由交換：路由器周期性向相鄰路由器廣播自己的整個路路由交換：路由器周期性向相鄰路由器廣播自己的整個路由表。由表。路由表更新路由表更新迭代更新，直至獲得整個迭代更新，直至獲得整個AS的路由信息。的路由信息。1 1 2 1 3 1 F

10、EDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 一開始，各路由表只有到相鄰路由器的信息一開始，各路由表只有到相鄰路由器的信息網網 3網網 2網網 4網網 6網網 5網網 1“4”表示表示“從本路由從本路由器到網器到網 4”“1”表示表示“距離是距離是 1”“ ”表示表示“直接交付直接交付”1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相鄰路由器收到相鄰路由器 A 和和 C 的路由表的路由表網網 3網網 2網網 4網網 6網網 5網網 11 1 2 1 3 1 4

11、 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后A 說：說：“我到網我到網 1 的距離是的距離是 1。”因此因此 B 現在也可以到網現在也可以到網 1，距離是距離是 2，經過，經過 A。”1 1 2 1 3 1 4 1 6 1 1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相鄰路由器收到相鄰路由器 A 和和 C 的路由表的路由表網網 3網網 2網網 4網網 6網網 5網網 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后A 說：

12、說：“我到網我到網 2 的距離是的距離是 1。”因此因此 B 現在也可以到網現在也可以到網 2，距離是距離是 2，經過，經過 A。”1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相鄰路由器收到相鄰路由器 A 和和 C 的路由表的路由表網網 3網網 2網網 4網網 6網網 5網網 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后A 說：說：“我到網我到網 3 的距離是的距離是 1。”但但 B 沒有必要繞道經過路由器沒有必要繞道經過路由器 A再到達網再到達

13、網 3，因此這一項目不變。，因此這一項目不變。1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相鄰路由器收到相鄰路由器 A 和和 C 的路由表的路由表網網 3網網 2網網 4網網 6網網 5網網 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后C 說：說：“我到網我到網 4 的距離是的距離是 1。”但但 B 沒有必要繞道經過路由器沒有必要繞道經過路由器 C再到達網再到達網 4，因此這一項目不變。，因此這一項目不變。1 1 2 1 3 1 FEDCBA5

14、1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相鄰路由器收到相鄰路由器 A 和和 C 的路由表的路由表網網 3網網 2網網 4網網 6網網 5網網 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后C 說：說：“我到網我到網 6 的距離是的距離是 1。”因此因此 B 現在也可以到網現在也可以到網 6，距離是距離是 2，經過，經過 C。”最終所有的路由器的路由表都更新了最終所有的路由器的路由表都更新了FEDCBA1 1 2 1 3 1 4 2 B5 2 E6 3 B1 1 2 2 A3 2 A4

15、 3 A5 1 6 2 F1 2 E2 2 D3 3 C4 2 C5 1 6 1 1 3 B2 3 B3 2 B4 1 5 2 F6 1 網網 2網網 6網網 5網網 1網網 3網網 41 2 A2 1 3 2 A4 3 A5 1 6 2 F1 2 A2 2 A3 1 4 1 5 3 C6 2 C例子例子 目的網絡目的網絡 下一個路由器下一個路由器 到目的地的跳數到目的地的跳數 wA2yB2 zB7x-1.wxyzACDB在路由器在路由器D中的選路表中的選路表例子例子( (續續) ) 目的網絡目的網絡 下一個路由器下一個路由器 到目的地的跳數到目的地的跳數 wA2yB2 zB A7 5x-1.

16、D的選路表的選路表wxyzACDB目的地目的地 下一個下一個 跳跳 w - - x - - z C 4 . .D從從A收到通告收到通告路由表的更新路由表的更新 路由器每收到一個鄰站的路由表，即更新自己的路由路由器每收到一個鄰站的路由表，即更新自己的路由表。表。(假設假設K收到收到J的路由表的路由表) (1) K不知道目的站，則加入不知道目的站，則加入 ； (2) 有通過有通過J的更短路，則替換的更短路，則替換 ； (3) 原下站為原下站為J的距離有變化，則修改的距離有變化，則修改 。例：例：目的站目的站距離距離下一跳下一跳網絡網絡10直接直接網絡網絡20直接直接網絡網絡48路由器路由器L網絡網

17、絡175路由器路由器M網絡網絡246路由器路由器J網絡網絡302路由器路由器Q網絡網絡422路由器路由器J目的站目的站距離距離網絡網絡12網絡網絡43網絡網絡176網絡網絡214網絡網絡245網絡網絡3010網絡網絡423目的站目的站距離距離下一跳下一跳網絡網絡10直接直接網絡網絡20直接直接網絡網絡44J（替換）（替換）網絡網絡175路由器路由器M網絡網絡246路由器路由器J網絡網絡302路由器路由器Q網絡網絡424J（修改）（修改）網絡網絡215J（增加）（增加）路由器每收到一路由器每收到一個鄰站的路由表，個鄰站的路由表，即更新自己的路即更新自己的路由表。由表。(假設假設K收收到到J的路由

18、表的路由表) (1) K不知道目不知道目的站，則加入的站，則加入 ； (2) 有通過有通過J的的更短路，則替換更短路，則替換 ； (3) 原下站為原下站為J的距離有變化，的距離有變化，則修改則修改 。關于距離向量算法的說明關于距離向量算法的說明優點：優點：CPU和內存開銷小和內存開銷小缺點：缺點：容易引發路由更新不一致問題：路由信息傳播速度容易引發路由更新不一致問題：路由信息傳播速度緩慢，計算結果容易出錯。緩慢，計算結果容易出錯。消耗帶寬較多。消耗帶寬較多。適用于規模不太大的、拓撲結構變化不頻繁的環境。適用于規模不太大的、拓撲結構變化不頻繁的環境。（2 2）鏈路狀態路由算法）鏈路狀態路由算法

19、- - 最短路徑優先最短路徑優先SPF 思想：思想：通過交換鏈路狀態，讓通過交換鏈路狀態，讓AS中的每個路由器都有一張該中的每個路由器都有一張該AS的網絡拓撲結構圖。的網絡拓撲結構圖。節點：路由器；節點：路由器；邊：鏈路邊：鏈路;使用使用Dijkstra算法求最短路徑，計算該路由器到其它目算法求最短路徑，計算該路由器到其它目的站的最短路徑，然后更新路由表。的站的最短路徑，然后更新路由表。優點：優點： 每個路由器使用相同的原始數據，具有每個路由器使用相同的原始數據，具有良好的收斂性良好的收斂性。 每個路由器的鏈路狀態報文大小取決于直接鏈路的數量，每個路由器的鏈路狀態報文大小取決于直接鏈路的數量，

20、具有具有較好的規模可擴展性較好的規模可擴展性。步驟步驟 鏈路狀態檢測：向鏈路狀態檢測：向直接相鄰的直接相鄰的路由器周期性發測試報文，路由器周期性發測試報文，檢查路由器狀態，并按檢查路由器狀態，并按“n中取中取k”原則進行狀態檢查原則進行狀態檢查 。 路由信息廣播：路由器周期性地（或某鏈路狀態變化時）路由信息廣播：路由器周期性地（或某鏈路狀態變化時）廣播廣播它所連接的各個鏈路狀態它所連接的各個鏈路狀態(洪泛洪泛)。 路由表更新：收到鏈路狀態的路由器更新自己的網絡拓撲路由表更新：收到鏈路狀態的路由器更新自己的網絡拓撲圖，并用圖，并用Dijkstra算法計算最短路徑算法計算最短路徑 。關于鏈路狀態算

21、法的說明關于鏈路狀態算法的說明缺點：缺點：需要較高的需要較高的CPU性能性能優點：優點：收斂性好收斂性好規模可擴展性好規模可擴展性好學習內容學習內容1、引言、引言2、路由表的建立與維護、路由表的建立與維護3、路徑確定、路徑確定4、路由算法、路由算法5、Internet路由體系發展路由體系發展6、大規模網絡拓撲發現、大規模網絡拓撲發現Internet路由體系的發展路由體系的發展 路由體系的內容：如何對路由體系的內容：如何對Internet中的路由器進行劃分、中的路由器進行劃分、管理和控制，以便有效地交換路由信息。管理和控制，以便有效地交換路由信息。路由體系的重要性：決定了互聯網的運行效率。路由體

22、系的重要性：決定了互聯網的運行效率。Internet路由體系的發展：路由體系的發展：（1）最早的核心路由體系）最早的核心路由體系（2）隨后的對等主干路由體系）隨后的對等主干路由體系（3）當前的自治系統路由體系）當前的自治系統路由體系 核心體系結構（分層樹型）核心體系結構（分層樹型）ARPANET主干網主干網本地網絡本地網絡2本地網絡本地網絡2本地網絡本地網絡mk1k2kn核心路由器核心路由器G1G2Gk外圍路由器外圍路由器 核心路由器核心路由器: 構成核心系構成核心系統，集中管理，提供到所統，集中管理，提供到所有目的地的路由。有目的地的路由。 外圍路由器外圍路由器: 為外出數據為外出數據報提供

23、默認路由報提供默認路由, 發往某核發往某核心網關心網關; 將核心路由器傳入將核心路由器傳入的數據報投遞到直連的物的數據報投遞到直連的物理網絡。理網絡。Internet的對等主干結構的對等主干結構 契機：契機：NSFNET的引入，網絡規模擴大的引入，網絡規模擴大R2RnR1ARPANET主干網主干網主機主機2主機主機1NSFNET主干網主干網主機主機4主機主機3選路模式：選路模式： 各主干網內部按核心結構方式進行選路各主干網內部按核心結構方式進行選路 各核心各核心路由器路由器擁有對另一部分的默認路由。擁有對另一部分的默認路由。 對等主干網存在的問題對等主干網存在的問題 兩主干間多重接入，造成選路

24、困難。兩主干間多重接入，造成選路困難。 具有非法目的地址的數據報形成選路回路具有非法目的地址的數據報形成選路回路核心核心C1核心核心C2核心核心C1內網點的內網點的非法目的分組非法目的分組x到核心到核心C2的的默認路由默認路由P1到核心到核心C1的的默認路由默認路由P2目前的目前的Internet結構（網狀）結構（網狀） Internet主干網主干網NAP1NAP2NAPnNSP1NSP2NSPNISP1ISP1ISP1核心層核心層分布層分布層接入層接入層如何限制選路信息的無限傳播？如何限制選路信息的無限傳播？如何限制選路信息的傳播如何限制選路信息的傳播? 參與交換路由信息的路由器群組規模不能

25、太大。參與交換路由信息的路由器群組規模不能太大。指導原則：指導原則： （1）廣域網范圍）廣域網范圍12個路由器個路由器 （2）若干局域網范圍）若干局域網范圍60個路由器。個路由器。說明說明:(1)AS自治的主要內容是選路自治自治的主要內容是選路自治, AS可自由地選擇路由算法；可自由地選擇路由算法； (2)AS必須嚴格界定，并被賦予全局唯一的自治系統號必須嚴格界定，并被賦予全局唯一的自治系統號(NIC分配分配)； (3)主干網絡本身也構成一個主干網絡本身也構成一個AS (教育網教育網AS4538)。AS1R1主干網主干網(AS)ASnInternet中的自治系統結構中的自治系統結構AS(自治系統自治系統)：出于選路目的，處于一個管理機構控制之下：出于選路目的，處于一個管理機構控制之下的的一組網絡和路由器一