9-路由協(xié)議概述課件

第9章路由協(xié)議概述——《網(wǎng)絡(luò)協(xié)議分析》第9章路由協(xié)議概述——《網(wǎng)絡(luò)協(xié)議分析》1主要內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)主要內(nèi)容1、引言2基本要求掌握路由表建立和維護(hù)的兩種方式：靜態(tài)配置和動態(tài)交換路由信息；掌握兩種路由更新算法:矢量距離算法和SPF算法;掌握Internet的路由體系結(jié)構(gòu)，特別是自治系統(tǒng)AS的概念和作用.基本要求掌握路由表建立和維護(hù)的兩種方式：靜態(tài)配置和動態(tài)交換路3學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言4問題的提出

問題：（1）為什么選擇這條路徑？（2）路由器的路由表如何獲取?（3）假設(shè)R2與R4的連接斷掉，如何通知R1？（4）在Internet中，是否每個路由器都必須了解其它路由器的情況？H1H2R1R5R2R3R4路徑：H1-R1-R2-R4-H2問題的提出問題：H1H2R1R5R2R3R4路徑：H1-R5學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言6路由表的建立和維護(hù)

靜態(tài)配置：管理員手工配置和更新路由表優(yōu)點(diǎn)：節(jié)省路由器的處理時(shí)間、存儲空間以及網(wǎng)絡(luò)帶寬缺陷：對于鏈路故障及拓?fù)浣Y(jié)構(gòu)變化的響應(yīng)速度慢兩種方式：靜態(tài)配置和動態(tài)路由交換H1H2R1R5R2R3R4適用環(huán)境：拓?fù)湎鄬Ψ€(wěn)定，路由器個數(shù)較少路由表的建立和維護(hù)靜態(tài)配置：管理員手工配置和更新路由表兩種7利用路由協(xié)議交換路由信息，并根據(jù)拓?fù)浣Y(jié)構(gòu)的變化動態(tài)更新路由表優(yōu)點(diǎn)：自動適應(yīng)鏈路故障及拓?fù)浣Y(jié)構(gòu)的變化缺陷：耗費(fèi)網(wǎng)絡(luò)帶寬、路由器的處理時(shí)間和存儲空間適用環(huán)境：路由器較多的大規(guī)模網(wǎng)絡(luò)H1H2R1R5R2R3R4動態(tài)路由信息交換利用路由協(xié)議交換路由信息，并根據(jù)拓?fù)浣Y(jié)構(gòu)的變化動態(tài)更新路由8學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言9什么是選路？1230111到達(dá)分組首部的值選路算法本地轉(zhuǎn)發(fā)表首部值輸出鏈路01000101011110013221

集中式分布式轉(zhuǎn)發(fā)表的配置方法：靜態(tài)：人工配置動態(tài)：選路協(xié)議什么是選路？1230111到達(dá)分組首部的值選路算法本地轉(zhuǎn)發(fā)表10選路涉及到的2個關(guān)鍵問題（1）路徑存在性（2）路徑最優(yōu)性選路涉及到的2個關(guān)鍵問題（1）路徑存在性11路徑存在性路由器采用“下一跳”選路；路由表的兩個普遍特點(diǎn)：（1）路由表中不包含到達(dá)所有目的地的路由（2）路由表中存在默認(rèn)路由這表明：（1）單個路由器為連接關(guān)系所做的貢獻(xiàn)是局部的（2）所有路由器組成的系統(tǒng)是完備的路徑存在性路由器采用“下一跳”選路；12問題：如何確定一條路徑是最優(yōu)的？選擇不同的度量指標(biāo)：（1）帶寬（2）延遲（靜態(tài)指標(biāo)）（3）負(fù)載（4）可靠性（動態(tài)指標(biāo)）（5）跳數(shù)（6）其它指標(biāo)，比如代價(jià)理想情況：綜合利用以上各指標(biāo)缺陷：選擇動態(tài)度量要素可能會造成路由震蕩實(shí)現(xiàn)：簡單的算法僅考慮一個要素，復(fù)雜的則綜合考慮（如DUAL）最常用的：基于跳數(shù)路由度量問題：如何確定一條路徑是最優(yōu)的？（1）帶寬13學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言14選路算法

1.非自適應(yīng)算法不考慮當(dāng)前的拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)流量設(shè)置中心路由器，由管理員預(yù)先為每個路由器設(shè)置路由表拓?fù)浒l(fā)生變化時(shí)，由管理員操作中心路由器，更新路由表適用于規(guī)模小，拓?fù)浣Y(jié)構(gòu)變化少的網(wǎng)絡(luò)1.非自適應(yīng)2.自適應(yīng)選路算法1.非自適應(yīng)算法1.非自適應(yīng)15(1)矢量-距離算法(2)鏈路狀態(tài)算法(1)矢量距離路由算法(Bellman、Bellman-Ford和Ford-Fulkerson算法)思想：以跳數(shù)作為度量值，通過交換路由表，計(jì)算出所有已知的最短路由，并更新路由表。自適應(yīng)算法

--矢量距離路由算法表項(xiàng)格式：<目的網(wǎng)絡(luò)，距離（跳數(shù)hop），下一站>跳數(shù)：從源站到目的站間所經(jīng)過的路由器數(shù)目。

(1)矢量-距離算法(2)鏈路狀態(tài)算法(1)16如何建立路由表?

初始化：路由器啟動時(shí)，對每個直接相連的網(wǎng)絡(luò)生成一個表項(xiàng)，hop數(shù)都為0。

路由交換：路由器周期性向相鄰路由器廣播自己的整個路由表。路由表更新迭代更新，直至獲得整個AS的路由信息。如何建立路由表?初始化：路由器啟動時(shí)，對每個直接相連的網(wǎng)絡(luò)17112131FEDCBA51612151314141611151一開始，各路由表只有到相鄰路由器的信息網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1“4”表示“從本路由器到網(wǎng)

4”“1”表示“距離是

1”“”表示“直接交付”11FEDCBA5121318112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后A說：“我到網(wǎng)1的距離是1。”因此B現(xiàn)在也可以到網(wǎng)1，距離是2，經(jīng)過A?！?12131416111FEDCBA5121319112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后A說：“我到網(wǎng)2的距離是1?！币虼薆現(xiàn)在也可以到網(wǎng)2，距離是2，經(jīng)過A?！?1FEDCBA5121320112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后A說：“我到網(wǎng)3的距離是1?！钡?/p>

B

沒有必要繞道經(jīng)過路由器

A再到達(dá)網(wǎng)

3，因此這一項(xiàng)目不變。11FEDCBA5121321112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后C說：“我到網(wǎng)4的距離是1。”但

B

沒有必要繞道經(jīng)過路由器

C再到達(dá)網(wǎng)

4，因此這一項(xiàng)目不變。11FEDCBA5121322112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后C說：“我到網(wǎng)6的距離是1。”因此B現(xiàn)在也可以到網(wǎng)6，距離是2，經(jīng)過C?！?1FEDCBA5121323最終所有的路由器的路由表都更新了FEDCBA11213142B52E63B1122A32A43A5162F12E22D33C42C516113B23B32B4152F61網(wǎng)2網(wǎng)6網(wǎng)5網(wǎng)1網(wǎng)3網(wǎng)412A2132A43A5162F12A22A314153C62C最終所有的路由器的路由表都更新了FEDCBA11124例子

目的網(wǎng)絡(luò) 下一個路由器 到目的地的跳數(shù)

w

A 2

y B 2

z B 7

x -- 1 …. …. ....wxyzACDB在路由器D中的選路表…例子目的網(wǎng)絡(luò) 下一個路由器25例子(續(xù))

目的網(wǎng)絡(luò) 下一個路由器到目的地的跳數(shù)

w

A 2

y

B 2

z

BA 75

x

-- 1

…. …. ....D的選路表wxyzACDB目的地下一個跳

w

--

x

--z

C

4

…. …...D從A收到通告…例子(續(xù))目的網(wǎng)絡(luò) 下一個26路由表的更新路由器每收到一個鄰站的路由表，即更新自己的路由表。(假設(shè)K收到J的路由表)(1)K不知道目的站，則加入；(2)有通過J的更短路，則替換；(3)原下站為J的距離有變化，則修改。路由表的更新路由器每收到一個鄰站的路由表，即更新自己27例：目的站距離下一跳網(wǎng)絡(luò)10直接網(wǎng)絡(luò)20直接網(wǎng)絡(luò)48路由器L網(wǎng)絡(luò)175路由器M網(wǎng)絡(luò)246路由器J網(wǎng)絡(luò)302路由器Q網(wǎng)絡(luò)422路由器J目的站距離網(wǎng)絡(luò)12網(wǎng)絡(luò)43網(wǎng)絡(luò)176網(wǎng)絡(luò)214網(wǎng)絡(luò)245網(wǎng)絡(luò)3010網(wǎng)絡(luò)423目的站距離下一跳網(wǎng)絡(luò)10直接網(wǎng)絡(luò)20直接網(wǎng)絡(luò)44J（替換）網(wǎng)絡(luò)175路由器M網(wǎng)絡(luò)246路由器J網(wǎng)絡(luò)302路由器Q網(wǎng)絡(luò)424J（修改）網(wǎng)絡(luò)215J（增加）路由器每收到一個鄰站的路由表，即更新自己的路由表。(假設(shè)K收到J的路由表)(1)K不知道目的站，則加入；(2)有通過J的更短路，則替換；(3)原下站為J的距離有變化，則修改。例：目的站距離下一跳網(wǎng)絡(luò)10直接網(wǎng)絡(luò)20直接網(wǎng)絡(luò)48路由器L28關(guān)于距離向量算法的說明優(yōu)點(diǎn)：CPU和內(nèi)存開銷小缺點(diǎn)：容易引發(fā)路由更新不一致問題：路由信息傳播速度緩慢，計(jì)算結(jié)果容易出錯。消耗帶寬較多。適用于規(guī)模不太大的、拓?fù)浣Y(jié)構(gòu)變化不頻繁的環(huán)境。關(guān)于距離向量算法的說明優(yōu)點(diǎn)：29（2）鏈路狀態(tài)路由算法

-最短路徑優(yōu)先SPF

思想：通過交換鏈路狀態(tài)，讓AS中的每個路由器都有一張?jiān)揂S的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。節(jié)點(diǎn)：路由器；邊：鏈路;使用Dijkstra算法求最短路徑，計(jì)算該路由器到其它目的站的最短路徑，然后更新路由表。優(yōu)點(diǎn)：①每個路由器使用相同的原始數(shù)據(jù)，具有良好的收斂性。②每個路由器的鏈路狀態(tài)報(bào)文大小取決于直接鏈路的數(shù)量，具有較好的規(guī)?？蓴U(kuò)展性。（2）鏈路狀態(tài)路由算法

-最短路徑優(yōu)先SPF思想：30步驟①鏈路狀態(tài)檢測：向直接相鄰的路由器周期性發(fā)測試報(bào)文，檢查路由器狀態(tài)，并按“n中取k”原則進(jìn)行狀態(tài)檢查。②路由信息廣播：路由器周期性地（或某鏈路狀態(tài)變化時(shí)）廣播它所連接的各個鏈路狀態(tài)(洪泛)。③路由表更新：收到鏈路狀態(tài)的路由器更新自己的網(wǎng)絡(luò)拓?fù)鋱D，并用Dijkstra算法計(jì)算最短路徑。步驟①鏈路狀態(tài)檢測：向直接相鄰的路由器周期性發(fā)測試報(bào)文，檢31關(guān)于鏈路狀態(tài)算法的說明缺點(diǎn)：需要較高的CPU性能優(yōu)點(diǎn)：收斂性好規(guī)模可擴(kuò)展性好關(guān)于鏈路狀態(tài)算法的說明缺點(diǎn)：32學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言33Internet路由體系的發(fā)展

路由體系的內(nèi)容：如何對Internet中的路由器進(jìn)行劃分、管理和控制，以便有效地交換路由信息。路由體系的重要性：決定了互聯(lián)網(wǎng)的運(yùn)行效率。Internet路由體系的發(fā)展：（1）最早的核心路由體系（2）隨后的對等主干路由體系（3）當(dāng)前的自治系統(tǒng)路由體系Internet路由體系的發(fā)展路由體系的內(nèi)容：如何對Int34核心體系結(jié)構(gòu)（分層樹型）ARPANET主干網(wǎng)本地網(wǎng)絡(luò)2本地網(wǎng)絡(luò)2本地網(wǎng)絡(luò)mk1k2kn核心路由器G1G2Gk外圍路由器核心路由器:構(gòu)成核心系統(tǒng)，集中管理，提供到所有目的地的路由。外圍路由器:為外出數(shù)據(jù)報(bào)提供默認(rèn)路由,發(fā)往某核心網(wǎng)關(guān);將核心路由器傳入的數(shù)據(jù)報(bào)投遞到直連的物理網(wǎng)絡(luò)。核心體系結(jié)構(gòu)（分層樹型）ARPANET主干網(wǎng)本地網(wǎng)絡(luò)2本地網(wǎng)35Internet的對等主干結(jié)構(gòu)

契機(jī)：NSFNET的引入，網(wǎng)絡(luò)規(guī)模擴(kuò)大R2RnR1ARPANET主干網(wǎng)主機(jī)2主機(jī)1NSFNET主干網(wǎng)主機(jī)4主機(jī)3選路模式：①各主干網(wǎng)內(nèi)部按核心結(jié)構(gòu)方式進(jìn)行選路②各核心路由器擁有對另一部分的默認(rèn)路由。

Internet的對等主干結(jié)構(gòu)契機(jī)：NSFNET的引入，網(wǎng)36對等主干網(wǎng)存在的問題①兩主干間多重接入，造成選路困難。②具有非法目的地址的數(shù)據(jù)報(bào)形成選路回路核心C1核心C2核心C1內(nèi)網(wǎng)點(diǎn)的非法目的分組x到核心C2的默認(rèn)路由P1到核心C1的默認(rèn)路由P2對等主干網(wǎng)存在的問題①兩主干間多重接入，造成選路困難。核心37目前的Internet結(jié)構(gòu)（網(wǎng)狀）

Internet主干網(wǎng)NAP1NAP2NAPnNSP1NSP2NSPNISP1ISP1ISP1………………核心層分布層接入層目前的Internet結(jié)構(gòu)（網(wǎng)狀）Internet主干網(wǎng)N38如何限制選路信息的無限傳播？如何限制選路信息的傳播?參與交換路由信息的路由器群組規(guī)模不能太大。指導(dǎo)原則：（1）廣域網(wǎng)范圍≤12個路由器（2）若干局域網(wǎng)范圍≤60個路由器。如何限制選路信息的無限傳播？如何限制選路信息的傳播?39說明:(1)AS自治的主要內(nèi)容是選路自治,AS可自由地選擇路由算法；(2)AS必須嚴(yán)格界定，并被賦予全局唯一的自治系統(tǒng)號(NIC分配)；(3)主干網(wǎng)絡(luò)本身也構(gòu)成一個AS(教育網(wǎng)AS4538)。AS1R1主干網(wǎng)(AS)ASn……Internet中的自治系統(tǒng)結(jié)構(gòu)AS(自治系統(tǒng))：出于選路目的，處于一個管理機(jī)構(gòu)控制之下的一組網(wǎng)絡(luò)和路由器。限制了路由信息傳播的規(guī)模增強(qiáng)了擴(kuò)展性說明:AS1R1主干網(wǎng)(AS)ASn……Internet中的40（1）AS內(nèi)部：IGP，比如RIP、OSPF、IS-IS等；（2）AS之間：EGP，最常用的是BGP;（3）EGP通常是一種可達(dá)性協(xié)議。R1R2R3AS1AS2AS3IGP1IGP2IGP3EGP12EGP13EGP23Internet的路由管理模式（1）AS內(nèi)部：IGP，比如RIP、OSPF、IS-IS等；41舉例3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP會話iBGP會話138.16.64/24138.16.65/24138.16.66/24138.16.67/24138.16.64/22聚合當(dāng)AS2向AS1通告一個CIDR前綴,并承諾它將轉(zhuǎn)發(fā)任何指向該前綴的數(shù)據(jù)報(bào)，AS2能夠在它的通告中聚合前綴舉例3b1d3a1c2aAS3AS1AS21a2c2b1b342小結(jié)路由表配置方式有:靜態(tài)和動態(tài)兩種.選路問題涉及路徑存在性和路徑最優(yōu)性兩個問題.路由度量要素主要有:帶寬,延遲,負(fù)載,可靠性,跳數(shù).路由算法包括:非自適應(yīng)路由算法和自適應(yīng)路由算法.自適應(yīng)路由算法包括：向量距離算法和鏈路狀態(tài)算法.Internet路由體系經(jīng)歷了核心路由體系,對等主干網(wǎng)路由體系和自治系統(tǒng)路由體系三個發(fā)展階段.自治系統(tǒng)路由體系便于管理和控制.小結(jié)路由表配置方式有:靜態(tài)和動態(tài)兩種.43課堂作業(yè)P121，8題課堂作業(yè)P121，8題44課后作業(yè)課后認(rèn)真看教材,查閱參考書相應(yīng)部分的內(nèi)容。書面作業(yè)：P121，3,10,12題課后作業(yè)課后認(rèn)真看教材,查閱參考書相應(yīng)部分的內(nèi)容。45第9章路由協(xié)議概述——《網(wǎng)絡(luò)協(xié)議分析》第9章路由協(xié)議概述——《網(wǎng)絡(luò)協(xié)議分析》46主要內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)主要內(nèi)容1、引言47基本要求掌握路由表建立和維護(hù)的兩種方式：靜態(tài)配置和動態(tài)交換路由信息；掌握兩種路由更新算法:矢量距離算法和SPF算法;掌握Internet的路由體系結(jié)構(gòu)，特別是自治系統(tǒng)AS的概念和作用.基本要求掌握路由表建立和維護(hù)的兩種方式：靜態(tài)配置和動態(tài)交換路48學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言49問題的提出

問題：（1）為什么選擇這條路徑？（2）路由器的路由表如何獲取?（3）假設(shè)R2與R4的連接斷掉，如何通知R1？（4）在Internet中，是否每個路由器都必須了解其它路由器的情況？H1H2R1R5R2R3R4路徑：H1-R1-R2-R4-H2問題的提出問題：H1H2R1R5R2R3R4路徑：H1-R50學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言51路由表的建立和維護(hù)

靜態(tài)配置：管理員手工配置和更新路由表優(yōu)點(diǎn)：節(jié)省路由器的處理時(shí)間、存儲空間以及網(wǎng)絡(luò)帶寬缺陷：對于鏈路故障及拓?fù)浣Y(jié)構(gòu)變化的響應(yīng)速度慢兩種方式：靜態(tài)配置和動態(tài)路由交換H1H2R1R5R2R3R4適用環(huán)境：拓?fù)湎鄬Ψ€(wěn)定，路由器個數(shù)較少路由表的建立和維護(hù)靜態(tài)配置：管理員手工配置和更新路由表兩種52利用路由協(xié)議交換路由信息，并根據(jù)拓?fù)浣Y(jié)構(gòu)的變化動態(tài)更新路由表優(yōu)點(diǎn)：自動適應(yīng)鏈路故障及拓?fù)浣Y(jié)構(gòu)的變化缺陷：耗費(fèi)網(wǎng)絡(luò)帶寬、路由器的處理時(shí)間和存儲空間適用環(huán)境：路由器較多的大規(guī)模網(wǎng)絡(luò)H1H2R1R5R2R3R4動態(tài)路由信息交換利用路由協(xié)議交換路由信息，并根據(jù)拓?fù)浣Y(jié)構(gòu)的變化動態(tài)更新路由53學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言54什么是選路？1230111到達(dá)分組首部的值選路算法本地轉(zhuǎn)發(fā)表首部值輸出鏈路01000101011110013221

集中式分布式轉(zhuǎn)發(fā)表的配置方法：靜態(tài)：人工配置動態(tài)：選路協(xié)議什么是選路？1230111到達(dá)分組首部的值選路算法本地轉(zhuǎn)發(fā)表55選路涉及到的2個關(guān)鍵問題（1）路徑存在性（2）路徑最優(yōu)性選路涉及到的2個關(guān)鍵問題（1）路徑存在性56路徑存在性路由器采用“下一跳”選路；路由表的兩個普遍特點(diǎn)：（1）路由表中不包含到達(dá)所有目的地的路由（2）路由表中存在默認(rèn)路由這表明：（1）單個路由器為連接關(guān)系所做的貢獻(xiàn)是局部的（2）所有路由器組成的系統(tǒng)是完備的路徑存在性路由器采用“下一跳”選路；57問題：如何確定一條路徑是最優(yōu)的？選擇不同的度量指標(biāo)：（1）帶寬（2）延遲（靜態(tài)指標(biāo)）（3）負(fù)載（4）可靠性（動態(tài)指標(biāo)）（5）跳數(shù)（6）其它指標(biāo)，比如代價(jià)理想情況：綜合利用以上各指標(biāo)缺陷：選擇動態(tài)度量要素可能會造成路由震蕩實(shí)現(xiàn)：簡單的算法僅考慮一個要素，復(fù)雜的則綜合考慮（如DUAL）最常用的：基于跳數(shù)路由度量問題：如何確定一條路徑是最優(yōu)的？（1）帶寬58學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言59選路算法

1.非自適應(yīng)算法不考慮當(dāng)前的拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)流量設(shè)置中心路由器，由管理員預(yù)先為每個路由器設(shè)置路由表拓?fù)浒l(fā)生變化時(shí)，由管理員操作中心路由器，更新路由表適用于規(guī)模小，拓?fù)浣Y(jié)構(gòu)變化少的網(wǎng)絡(luò)1.非自適應(yīng)2.自適應(yīng)選路算法1.非自適應(yīng)算法1.非自適應(yīng)60(1)矢量-距離算法(2)鏈路狀態(tài)算法(1)矢量距離路由算法(Bellman、Bellman-Ford和Ford-Fulkerson算法)思想：以跳數(shù)作為度量值，通過交換路由表，計(jì)算出所有已知的最短路由，并更新路由表。自適應(yīng)算法

--矢量距離路由算法表項(xiàng)格式：<目的網(wǎng)絡(luò)，距離（跳數(shù)hop），下一站>跳數(shù)：從源站到目的站間所經(jīng)過的路由器數(shù)目。

(1)矢量-距離算法(2)鏈路狀態(tài)算法(1)61如何建立路由表?

初始化：路由器啟動時(shí)，對每個直接相連的網(wǎng)絡(luò)生成一個表項(xiàng)，hop數(shù)都為0。

路由交換：路由器周期性向相鄰路由器廣播自己的整個路由表。路由表更新迭代更新，直至獲得整個AS的路由信息。如何建立路由表?初始化：路由器啟動時(shí)，對每個直接相連的網(wǎng)絡(luò)62112131FEDCBA51612151314141611151一開始，各路由表只有到相鄰路由器的信息網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1“4”表示“從本路由器到網(wǎng)

4”“1”表示“距離是

1”“”表示“直接交付”11FEDCBA5121363112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后A說：“我到網(wǎng)1的距離是1。”因此B現(xiàn)在也可以到網(wǎng)1，距離是2，經(jīng)過A?！?12131416111FEDCBA5121364112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后A說：“我到網(wǎng)2的距離是1。”因此B現(xiàn)在也可以到網(wǎng)2，距離是2，經(jīng)過A?！?1FEDCBA5121365112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后A說：“我到網(wǎng)3的距離是1?！钡?/p>

B

沒有必要繞道經(jīng)過路由器

A再到達(dá)網(wǎng)

3，因此這一項(xiàng)目不變。11FEDCBA5121366112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后C說：“我到網(wǎng)4的距離是1?！钡?/p>

B

沒有必要繞道經(jīng)過路由器

C再到達(dá)網(wǎng)

4，因此這一項(xiàng)目不變。11FEDCBA5121367112131FEDCBA51612151314141611151路由器B收到相鄰路由器A和C的路由表網(wǎng)

3網(wǎng)

2網(wǎng)

4網(wǎng)

6網(wǎng)

5網(wǎng)

1112131416112A22A314162C更新后C說：“我到網(wǎng)6的距離是1?！币虼薆現(xiàn)在也可以到網(wǎng)6，距離是2，經(jīng)過C?！?1FEDCBA5121368最終所有的路由器的路由表都更新了FEDCBA11213142B52E63B1122A32A43A5162F12E22D33C42C516113B23B32B4152F61網(wǎng)2網(wǎng)6網(wǎng)5網(wǎng)1網(wǎng)3網(wǎng)412A2132A43A5162F12A22A314153C62C最終所有的路由器的路由表都更新了FEDCBA11169例子

目的網(wǎng)絡(luò) 下一個路由器 到目的地的跳數(shù)

w

A 2

y B 2

z B 7

x -- 1 …. …. ....wxyzACDB在路由器D中的選路表…例子目的網(wǎng)絡(luò) 下一個路由器70例子(續(xù))

目的網(wǎng)絡(luò) 下一個路由器到目的地的跳數(shù)

w

A 2

y

B 2

z

BA 75

x

-- 1

…. …. ....D的選路表wxyzACDB目的地下一個跳

w

--

x

--z

C

4

…. …...D從A收到通告…例子(續(xù))目的網(wǎng)絡(luò) 下一個71路由表的更新路由器每收到一個鄰站的路由表，即更新自己的路由表。(假設(shè)K收到J的路由表)(1)K不知道目的站，則加入；(2)有通過J的更短路，則替換；(3)原下站為J的距離有變化，則修改。路由表的更新路由器每收到一個鄰站的路由表，即更新自己72例：目的站距離下一跳網(wǎng)絡(luò)10直接網(wǎng)絡(luò)20直接網(wǎng)絡(luò)48路由器L網(wǎng)絡(luò)175路由器M網(wǎng)絡(luò)246路由器J網(wǎng)絡(luò)302路由器Q網(wǎng)絡(luò)422路由器J目的站距離網(wǎng)絡(luò)12網(wǎng)絡(luò)43網(wǎng)絡(luò)176網(wǎng)絡(luò)214網(wǎng)絡(luò)245網(wǎng)絡(luò)3010網(wǎng)絡(luò)423目的站距離下一跳網(wǎng)絡(luò)10直接網(wǎng)絡(luò)20直接網(wǎng)絡(luò)44J（替換）網(wǎng)絡(luò)175路由器M網(wǎng)絡(luò)246路由器J網(wǎng)絡(luò)302路由器Q網(wǎng)絡(luò)424J（修改）網(wǎng)絡(luò)215J（增加）路由器每收到一個鄰站的路由表，即更新自己的路由表。(假設(shè)K收到J的路由表)(1)K不知道目的站，則加入；(2)有通過J的更短路，則替換；(3)原下站為J的距離有變化，則修改。例：目的站距離下一跳網(wǎng)絡(luò)10直接網(wǎng)絡(luò)20直接網(wǎng)絡(luò)48路由器L73關(guān)于距離向量算法的說明優(yōu)點(diǎn)：CPU和內(nèi)存開銷小缺點(diǎn)：容易引發(fā)路由更新不一致問題：路由信息傳播速度緩慢，計(jì)算結(jié)果容易出錯。消耗帶寬較多。適用于規(guī)模不太大的、拓?fù)浣Y(jié)構(gòu)變化不頻繁的環(huán)境。關(guān)于距離向量算法的說明優(yōu)點(diǎn)：74（2）鏈路狀態(tài)路由算法

-最短路徑優(yōu)先SPF

思想：通過交換鏈路狀態(tài)，讓AS中的每個路由器都有一張?jiān)揂S的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。節(jié)點(diǎn)：路由器；邊：鏈路;使用Dijkstra算法求最短路徑，計(jì)算該路由器到其它目的站的最短路徑，然后更新路由表。優(yōu)點(diǎn)：①每個路由器使用相同的原始數(shù)據(jù)，具有良好的收斂性。②每個路由器的鏈路狀態(tài)報(bào)文大小取決于直接鏈路的數(shù)量，具有較好的規(guī)模可擴(kuò)展性。（2）鏈路狀態(tài)路由算法

-最短路徑優(yōu)先SPF思想：75步驟①鏈路狀態(tài)檢測：向直接相鄰的路由器周期性發(fā)測試報(bào)文，檢查路由器狀態(tài)，并按“n中取k”原則進(jìn)行狀態(tài)檢查。②路由信息廣播：路由器周期性地（或某鏈路狀態(tài)變化時(shí)）廣播它所連接的各個鏈路狀態(tài)(洪泛)。③路由表更新：收到鏈路狀態(tài)的路由器更新自己的網(wǎng)絡(luò)拓?fù)鋱D，并用Dijkstra算法計(jì)算最短路徑。步驟①鏈路狀態(tài)檢測：向直接相鄰的路由器周期性發(fā)測試報(bào)文，檢76關(guān)于鏈路狀態(tài)算法的說明缺點(diǎn)：需要較高的CPU性能優(yōu)點(diǎn)：收斂性好規(guī)?？蓴U(kuò)展性好關(guān)于鏈路狀態(tài)算法的說明缺點(diǎn)：77學(xué)習(xí)內(nèi)容1、引言2、路由表的建立與維護(hù)3、路徑確定4、路由算法5、Internet路由體系發(fā)展6、大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)學(xué)習(xí)內(nèi)容1、引言78Internet路由體系的發(fā)展

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