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

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

2、這條路徑？（3）假設(shè)）假設(shè)R2與與R4的連接斷掉，如何通知的連接斷掉，如何通知R1？（4）在）在Internet中，是否每個(gè)路由器都必須了解其中，是否每個(gè)路由器都必須了解其它路由器的情況？它路由器的情況？9.2路由表的建立和維護(hù)路由表的建立和維護(hù)兩種方式：兩種方式：靜態(tài)配置靜態(tài)配置and動(dòng)態(tài)路由交換動(dòng)態(tài)路由交換1.靜態(tài)配置：管理員手工配置和更新路由表靜態(tài)配置：管理員手工配置和更新路由表優(yōu)點(diǎn)：優(yōu)點(diǎn)：節(jié)省路由器的處理時(shí)間、存儲(chǔ)空間以及網(wǎng)絡(luò)節(jié)省路由器的處理時(shí)間、存儲(chǔ)空間以及網(wǎng)絡(luò)帶寬帶寬缺陷：缺陷：對(duì)于鏈路故障及拓?fù)浣Y(jié)構(gòu)變化的響應(yīng)速度慢對(duì)于鏈路故障及拓?fù)浣Y(jié)構(gòu)變化的響應(yīng)速度慢H1H2R1R5R2R3R4

3、適用環(huán)境：適用環(huán)境：拓?fù)湎鄬?duì)穩(wěn)定，路由器個(gè)數(shù)較少拓?fù)湎鄬?duì)穩(wěn)定，路由器個(gè)數(shù)較少2.動(dòng)態(tài)路由信息交換：利用路由協(xié)議交換路由信息，并動(dòng)態(tài)路由信息交換：利用路由協(xié)議交換路由信息，并根據(jù)拓?fù)浣Y(jié)構(gòu)的變化動(dòng)態(tài)更新路由表根據(jù)拓?fù)浣Y(jié)構(gòu)的變化動(dòng)態(tài)更新路由表優(yōu)點(diǎn)：優(yōu)點(diǎn)：自動(dòng)適應(yīng)鏈路故障及拓?fù)浣Y(jié)構(gòu)的變化自動(dòng)適應(yīng)鏈路故障及拓?fù)浣Y(jié)構(gòu)的變化缺陷：缺陷：耗費(fèi)路由器的處理時(shí)間、存儲(chǔ)空間以及網(wǎng)絡(luò)帶耗費(fèi)路由器的處理時(shí)間、存儲(chǔ)空間以及網(wǎng)絡(luò)帶寬寬適用環(huán)境：適用環(huán)境：路由器較多的大規(guī)模網(wǎng)絡(luò)路由器較多的大規(guī)模網(wǎng)絡(luò)H1H2R1R5R2R3R49.3選路涉及到的選路涉及到的2個(gè)關(guān)鍵問題個(gè)關(guān)鍵問題（1）路徑存在性）路徑存在性（2）路徑最優(yōu)性）路

4、徑最優(yōu)性1.路徑存在性路徑存在性路由表的兩個(gè)普遍特點(diǎn)：路由表的兩個(gè)普遍特點(diǎn)：（1）路由表中不包含到達(dá)所有目的地的路由）路由表中不包含到達(dá)所有目的地的路由（2）路由表中存在默認(rèn)路由）路由表中存在默認(rèn)路由要求：要求：（1）單個(gè)路由器為連接關(guān)系所做的貢獻(xiàn)是局部的）單個(gè)路由器為連接關(guān)系所做的貢獻(xiàn)是局部的（2）所有路由器組成的系統(tǒng)是完備的）所有路由器組成的系統(tǒng)是完備的問題：如何確保各個(gè)路由器維護(hù)信息的一致性？問題：如何確保各個(gè)路由器維護(hù)信息的一致性？答案：答案：不同路由器更新路由表的信息是一致的，使不同路由器更新路由表的信息是一致的，使得它們對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有著一致性的認(rèn)識(shí)。得它們對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有著一致性

5、的認(rèn)識(shí)。2.路由度量路由度量問題：?jiǎn)栴}：如何確定一條路徑是最優(yōu)的？如何確定一條路徑是最優(yōu)的？解答：解答：選擇不同的度量指標(biāo)選擇不同的度量指標(biāo)（1）帶寬（靜態(tài)指標(biāo)）帶寬（靜態(tài)指標(biāo)）（2）延遲）延遲（3）負(fù)載）負(fù)載（4）可靠性）可靠性（5）跳數(shù)）跳數(shù)（6）其它指標(biāo)，比如代價(jià)）其它指標(biāo)，比如代價(jià)理想情況：理想情況：綜合利用以上各指標(biāo)綜合利用以上各指標(biāo)缺陷：缺陷：可能會(huì)造成路由震蕩可能會(huì)造成路由震蕩實(shí)現(xiàn)：實(shí)現(xiàn)：簡(jiǎn)單的算法僅考慮一個(gè)要素，復(fù)雜的則綜合簡(jiǎn)單的算法僅考慮一個(gè)要素，復(fù)雜的則綜合考慮（如考慮（如DUAL）最常用的：最常用的：基于跳數(shù)基于跳數(shù)9.4選路算法選路算法（1）非自適應(yīng)）非自適應(yīng)（2）自適

6、應(yīng)）自適應(yīng)1.非自適應(yīng)算法非自適應(yīng)算法（1）不考慮當(dāng)前的拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)流量）不考慮當(dāng)前的拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)流量（2）設(shè)置中心路由器，由管理員預(yù)先為每個(gè)路由器）設(shè)置中心路由器，由管理員預(yù)先為每個(gè)路由器設(shè)置路由表設(shè)置路由表（3）拓?fù)浒l(fā)生變化時(shí)，由管理員操作中心路由器，）拓?fù)浒l(fā)生變化時(shí)，由管理員操作中心路由器，更新路由表更新路由表（4）適用于規(guī)模小，拓?fù)浣Y(jié)構(gòu)變化少的網(wǎng)絡(luò)）適用于規(guī)模小，拓?fù)浣Y(jié)構(gòu)變化少的網(wǎng)絡(luò)2.自適應(yīng)自適應(yīng)算法算法（1）矢量）矢量-距離算法距離算法（2）鏈路狀態(tài)算法）鏈路狀態(tài)算法（1）矢量距離路由算法矢量距離路由算法(Bellman、Bellman-Ford和和Ford-Fulkerson

7、算法算法)思想：思想：以跳數(shù)作為度量值，通過交換路由表，計(jì)算出以跳數(shù)作為度量值，通過交換路由表，計(jì)算出所有已知的最短路由，更新路由表。所有已知的最短路由，更新路由表。表項(xiàng)格式：表項(xiàng)格式：跳數(shù)：跳數(shù)：從源站到目的站間所經(jīng)過的路由器數(shù)目。從源站到目的站間所經(jīng)過的路由器數(shù)目。步驟：步驟：初始化初始化:路由器啟動(dòng)時(shí)，對(duì)每個(gè)直接相連的網(wǎng)絡(luò)生路由器啟動(dòng)時(shí)，對(duì)每個(gè)直接相連的網(wǎng)絡(luò)生成一個(gè)表項(xiàng)，成一個(gè)表項(xiàng)，hop數(shù)都為數(shù)都為0。路由交換路由交換:路由器周期性向相鄰路由器廣播自己的路由器周期性向相鄰路由器廣播自己的整個(gè)路由表。整個(gè)路由表。(交換信息是交換信息是)路由表更新路由表更新:路由器每收到一個(gè)鄰站的路由表，

8、即路由器每收到一個(gè)鄰站的路由表，即更新自己的路由表。更新自己的路由表。(假設(shè)假設(shè)K收到收到J的路由表的路由表)(1)K不知道目的站，則不知道目的站，則加入加入(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)

9、絡(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網(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中的每個(gè)路由器中的每個(gè)路由器都有一張?jiān)摱加幸粡堅(jiān)揂S的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。節(jié)點(diǎn)：路由器；邊：網(wǎng)絡(luò)。節(jié)點(diǎn)：路由器；邊：網(wǎng)絡(luò)。使用使用Dijkstra算法求最短路徑，計(jì)算該路由器到其算法求最短路徑，計(jì)算該路由器到其它目的站的最短路徑，然后更新路由表。它目的站的最短路徑，然后更

10、新路由表。優(yōu)點(diǎn)：優(yōu)點(diǎn)：每個(gè)路由器使用相同的原始數(shù)據(jù)，具有良好的每個(gè)路由器使用相同的原始數(shù)據(jù)，具有良好的收斂性。收斂性。每個(gè)路由器的鏈路狀態(tài)報(bào)文尺寸取決于只連鏈路每個(gè)路由器的鏈路狀態(tài)報(bào)文尺寸取決于只連鏈路的數(shù)量，具有較好的規(guī)?？蓴U(kuò)展性的數(shù)量，具有較好的規(guī)模可擴(kuò)展性（2）鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法-最短路徑優(yōu)先最短路徑優(yōu)先SPF 步驟：步驟：鏈路狀態(tài)檢測(cè)：鏈路狀態(tài)檢測(cè)：周期性發(fā)測(cè)試報(bào)文，檢查直接相周期性發(fā)測(cè)試報(bào)文，檢查直接相鄰的路由器狀態(tài)，并按鄰的路由器狀態(tài)，并按“n中取中取k”原則進(jìn)行狀態(tài)檢查原則進(jìn)行狀態(tài)檢查。路由信息廣播：路由信息廣播：路由器周期性廣播它的各個(gè)鏈路路由器周期性廣播它的各個(gè)

11、鏈路狀態(tài)。所有參與狀態(tài)。所有參與SPF的路由器負(fù)責(zé)轉(zhuǎn)發(fā)收到的鏈路狀的路由器負(fù)責(zé)轉(zhuǎn)發(fā)收到的鏈路狀態(tài)態(tài)。路由表更新：路由表更新：收到鏈路狀態(tài)的路由器更新自己的收到鏈路狀態(tài)的路由器更新自己的網(wǎng)絡(luò)拓?fù)鋱D，并用網(wǎng)絡(luò)拓?fù)鋱D，并用Dijkstra算法計(jì)算最短路徑算法計(jì)算最短路徑。9.5Internet路由體系的發(fā)展路由體系的發(fā)展 路由體系的內(nèi)容：路由體系的內(nèi)容：如何對(duì)如何對(duì)Internet中的路由器進(jìn)行劃中的路由器進(jìn)行劃分、管理和控制，以便有效地交換路由信息分、管理和控制，以便有效地交換路由信息路由體系的重要性：路由體系的重要性：決定了互聯(lián)網(wǎng)的運(yùn)行效率決定了互聯(lián)網(wǎng)的運(yùn)行效率Internet路由體系的發(fā)展：路

12、由體系的發(fā)展：（1）最早的核心路由體系）最早的核心路由體系（2）隨后的對(duì)等主干路由體系）隨后的對(duì)等主干路由體系（3）當(dāng)前的自治系統(tǒng)路由體系）當(dāng)前的自治系統(tǒng)路由體系 1.核心路由器與核心體系結(jié)構(gòu)核心路由器與核心體系結(jié)構(gòu) ARPANET主干網(wǎng)主干網(wǎng)本地網(wǎng)絡(luò)本地網(wǎng)絡(luò)2R2本地網(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)，集中管理中管理,提供到所有目的地的提供到所有目的地的路由。

13、路由。外圍網(wǎng)關(guān)外圍網(wǎng)關(guān):為外出數(shù)據(jù)報(bào)提供為外出數(shù)據(jù)報(bào)提供默認(rèn)路由默認(rèn)路由,發(fā)往某核心網(wǎng)關(guān)發(fā)往某核心網(wǎng)關(guān);將將核心網(wǎng)關(guān)傳入的數(shù)據(jù)報(bào)投遞核心網(wǎng)關(guān)傳入的數(shù)據(jù)報(bào)投遞到直連的物理網(wǎng)絡(luò)。到直連的物理網(wǎng)絡(luò)。2.Internet的對(duì)等主干結(jié)構(gòu)的對(duì)等主干結(jié)構(gòu) 問題：?jiǎn)栴}：兩主干間多重接入，造成選路困難。兩主干間多重接入，造成選路困難。 具有非法目的地址的數(shù)據(jù)報(bào)形成選路回路具有非法目的地址的數(shù)據(jù)報(bào)形成選路回路契機(jī)：契機(jī)：NSFNET的引入的引入R2RnR1ARPANET主干網(wǎng)主干網(wǎng)主機(jī)主機(jī)2主機(jī)主機(jī)1NSFNET主干網(wǎng)主干網(wǎng)主機(jī)主機(jī)4主機(jī)主機(jī)3選路模式：選路模式：各主干網(wǎng)內(nèi)部按核心結(jié)構(gòu)方式進(jìn)行選路各主干網(wǎng)內(nèi)部按核

14、心結(jié)構(gòu)方式進(jìn)行選路各核心網(wǎng)關(guān)擁有對(duì)另一部分的默認(rèn)路由。各核心網(wǎng)關(guān)擁有對(duì)另一部分的默認(rèn)路由。 核心核心C1核心核心C2核心核心C1內(nèi)網(wǎng)點(diǎn)的內(nèi)網(wǎng)點(diǎn)的非法目的分組非法目的分組x到核心到核心C2的的默認(rèn)路由默認(rèn)路由P1到核心到核心C1的的默認(rèn)路由默認(rèn)路由P2目前的目前的Internet結(jié)構(gòu)結(jié)構(gòu) Internet主干網(wǎng)主干網(wǎng)NAP1NAP2NAPnNSP1NSP2NSPNISP1ISP1ISP1核心層核心層分布層分布層接入層接入層3.Internet中的自治系統(tǒng)結(jié)構(gòu)中的自治系統(tǒng)結(jié)構(gòu)AS(自治系統(tǒng)自治系統(tǒng))：出于選路目的，處于一個(gè)管理機(jī)構(gòu)出于選路目的，處于一個(gè)管理機(jī)構(gòu)控制之下的一組網(wǎng)絡(luò)和路由器?？刂浦碌囊唤M網(wǎng)絡(luò)和路由器。 如何限制選路信息的傳播如何限制選路信息的傳播? 參與交換路由信息的路由器群組規(guī)模不能太大。參與交換路由信息的路由器群組規(guī)模不能太大。指導(dǎo)原則：指導(dǎo)原則：（1）廣域網(wǎng)范圍）廣域網(wǎng)范圍12個(gè)路由器個(gè)路由器 （2）若干局域網(wǎng)范圍）若干局域網(wǎng)范圍60個(gè)路由器。個(gè)路由器。多主干下選路問題如何解決？多主干下選路問題如何解決？說明說明:（1）AS自治的主要內(nèi)容是選路自治自治的主要內(nèi)容是選路自治,AS可自由地選可自由地選擇路由算法；擇路由算法；（2）AS必須嚴(yán)格界定，并被賦予全局唯一的自治必須嚴(yán)格界定，并被賦予全局唯一的自治系統(tǒng)號(hào)系統(tǒng)號(hào)(NIC分配分配)；（3）主干網(wǎng)絡(luò)本身也構(gòu)