計(jì)算機(jī)網(wǎng)絡(luò)-西安電子科技大學(xué)個(gè)人主頁(yè)系統(tǒng)我的西電我的

1、,計(jì)算機(jī)通信網(wǎng),Lecture 5: 網(wǎng)絡(luò)層,,第 5 章 網(wǎng)絡(luò)層,5.1 網(wǎng)絡(luò)層的設(shè)計(jì)問(wèn)題5.2 路由算法 5.3 擁塞控制算法5.4 服務(wù)質(zhì)量5.5 網(wǎng)絡(luò)互聯(lián)5.6 Internet的網(wǎng)絡(luò)層,,第 5 章 網(wǎng)絡(luò)層,5.1 網(wǎng)絡(luò)層的設(shè)計(jì)問(wèn)題 5.1.1 存儲(chǔ)轉(zhuǎn)發(fā)數(shù)據(jù)包交換 5.1.2 提供給傳輸層的服務(wù) 5.1.3 無(wú)連接服務(wù)的實(shí)現(xiàn) 5.1.4

2、 面向連接服務(wù)的實(shí)現(xiàn) 5.1.5 虛電路與數(shù)據(jù)報(bào)網(wǎng)絡(luò)的比較,網(wǎng)絡(luò)層的功能,網(wǎng)絡(luò)層是OSI參考模型中的第三層 網(wǎng)絡(luò)層關(guān)系到通信子網(wǎng)的運(yùn)行控制，體現(xiàn)了網(wǎng)絡(luò)應(yīng)用環(huán)境中資源子網(wǎng)訪問(wèn)通信子網(wǎng)的方式，是OSI模型中面向數(shù)據(jù)通信的低三層(也即通信子網(wǎng))中最為復(fù)雜、關(guān)鍵的一層。 網(wǎng)絡(luò)層的目的是實(shí)現(xiàn)兩個(gè)端系統(tǒng)之間的數(shù)據(jù)透明傳送，具體功能包括路由選擇、阻塞控制和網(wǎng)際互連等 。,,5.1.1 存儲(chǔ)轉(zhuǎn)發(fā)數(shù)據(jù)包交換,5.1.2.提供給傳

3、輸層服務(wù),端點(diǎn)之間的通信是依靠通信子網(wǎng)中的節(jié)點(diǎn)間的通信來(lái)實(shí)現(xiàn)的 在分組交換方式中，通信子網(wǎng)向端系統(tǒng)提供虛電路和數(shù)據(jù)報(bào)兩種網(wǎng)絡(luò)服務(wù)，而通信子網(wǎng)內(nèi)部的操作也有虛電路和數(shù)據(jù)報(bào)兩種方式。通信子網(wǎng)的操作方式：虛電路操作方式和數(shù)據(jù)報(bào)操作方式網(wǎng)絡(luò)層提供的服務(wù)：虛電路服務(wù)和數(shù)據(jù)報(bào)服務(wù),,5.1.2 提供給傳輸層服務(wù),在計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域，網(wǎng)絡(luò)層應(yīng)該向運(yùn)輸層提供怎樣的服務(wù)（“面向連接”還是“無(wú)連接”）曾引起了長(zhǎng)期的爭(zhēng)論。爭(zhēng)論焦點(diǎn)的實(shí)質(zhì)就是：在計(jì)算機(jī)

4、通信中，可靠交付應(yīng)當(dāng)由誰(shuí)來(lái)負(fù)責(zé)？是網(wǎng)絡(luò)還是端系統(tǒng)？,,電信網(wǎng)的成功經(jīng)驗(yàn)讓網(wǎng)絡(luò)負(fù)責(zé)可靠交付,面向連接的通信方式，服務(wù)質(zhì)量是最主要的因素 建立虛電路(Virtual Circuit)，以保證雙方通信所需的一切網(wǎng)絡(luò)資源。 如果再使用可靠傳輸?shù)木W(wǎng)絡(luò)協(xié)議，就可使所發(fā)送的分組無(wú)差錯(cuò)按序到達(dá)終點(diǎn)。,,因特網(wǎng)采用的設(shè)計(jì)思路,網(wǎng)絡(luò)層向上只提供簡(jiǎn)單靈活的、無(wú)連接的、盡最大努力交付的數(shù)據(jù)報(bào)服務(wù)。網(wǎng)絡(luò)在發(fā)送分組時(shí)不需要先建立連接。每一個(gè)分組（即 IP

5、數(shù)據(jù)報(bào)）獨(dú)立發(fā)送，與其前后的分組無(wú)關(guān)（不進(jìn)行編號(hào)）。網(wǎng)絡(luò)層不提供服務(wù)質(zhì)量的承諾。即所傳送的分組可能出錯(cuò)、丟失、重復(fù)和失序（不按序到達(dá)終點(diǎn)），當(dāng)然也不保證分組傳送的時(shí)限。,,第 5 章 網(wǎng)絡(luò)層,5.1 網(wǎng)絡(luò)層的設(shè)計(jì)問(wèn)題 5.1.1 存儲(chǔ)轉(zhuǎn)發(fā)數(shù)據(jù)包交換 5.1.2 提供給傳輸層的服務(wù) 5.1.3 無(wú)連接服務(wù)的實(shí)現(xiàn) 5.1.4 面向連接服務(wù)的實(shí)現(xiàn) 5.1.5

6、 虛電路與數(shù)據(jù)報(bào)網(wǎng)絡(luò)的比較,5.1.3無(wú)連接服務(wù)的實(shí)現(xiàn),,,應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層,,應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層,5.1.3無(wú)連接服務(wù)的實(shí)現(xiàn),,,,,,,,,,,,,,H1,,,,,,H2,,,,,IP 數(shù)據(jù)報(bào),丟失,H1 發(fā)送給 H2 的分組可能沿著不同路徑傳送,,,,應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層,,應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層,5.1.4 面向連接服務(wù)的實(shí)現(xiàn),,,,,,

7、,,,,,,,H1,,,,,,H2,,,,虛電路,H1 發(fā)送給 H2 的所有分組都沿著同一條虛電路傳送,,虛電路是邏輯連接,虛電路表示這只是一條邏輯上的連接，分組都沿著這條邏輯連接按照存儲(chǔ)轉(zhuǎn)發(fā)方式傳送，而并不是真正建立了一條物理連接。請(qǐng)注意，電路交換的電話通信是先建立了一條真正的連接。因此分組交換的虛連接和電路交換的連接只是類似，但并不完全一樣。,,虛電路建立實(shí)例,,,盡最大努力交付的好處,由于傳輸網(wǎng)絡(luò)不提供端到端的可靠傳輸服務(wù)，這就

8、使網(wǎng)絡(luò)中的路由器可以做得比較簡(jiǎn)單，而且價(jià)格低廉（與電信網(wǎng)的交換機(jī)相比較）。如果主機(jī)（即端系統(tǒng)）中的進(jìn)程之間的通信需要是可靠的，那么就由網(wǎng)絡(luò)的主機(jī)中的運(yùn)輸層負(fù)責(zé)（包括差錯(cuò)處理、流量控制等）。采用這種設(shè)計(jì)思路的好處是：網(wǎng)絡(luò)的造價(jià)大大降低，運(yùn)行方式靈活，能夠適應(yīng)多種應(yīng)用。因特網(wǎng)能夠發(fā)展到今日的規(guī)模，充分證明了當(dāng)初采用這種設(shè)計(jì)思路的正確性。,5.1.5虛電路與數(shù)據(jù)報(bào)網(wǎng)絡(luò)的對(duì)較,,第 5 章 網(wǎng)絡(luò)層,5.2 路由算法 5.2.

9、1 優(yōu)化原則 5.2.2 最短路徑算法 5.2.3 泛洪算法 5.2.4 距離矢量算法 5.2.5 鏈路狀態(tài)路由 5.2.6 層次路由 5.2.7 廣播路由 5.2.8 組播路由 5.2.9 選播路由 5.2.10 移動(dòng)主機(jī)路由 5.2.11 自組織網(wǎng)絡(luò)路由,5.2 路由算法,通信子網(wǎng)為網(wǎng)絡(luò)源節(jié)點(diǎn)和目的節(jié)

10、點(diǎn)提供了多條傳輸路徑的可能性。網(wǎng)絡(luò)節(jié)點(diǎn)在收到一個(gè)分組后后，要確定向下一節(jié)點(diǎn)傳送的路徑，這就是路由選擇，路由選擇是網(wǎng)絡(luò)層要實(shí)現(xiàn)的基本功能。在數(shù)據(jù)報(bào)方式中，網(wǎng)絡(luò)節(jié)點(diǎn)要為每個(gè)分組路由做出選擇；而在虛電路方式中，只需在連接建立時(shí)確定路由。路由選擇包括兩個(gè)基本操作，即最佳路徑的判定和網(wǎng)間信息包的傳送。確定路由選擇的策略稱路由算法。,,,算法必須是正確的和完整的。 算法在計(jì)算上應(yīng)簡(jiǎn)單。 算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓?，這就是說(shuō)，要

11、有自適應(yīng)性（魯棒性）。 算法應(yīng)具有穩(wěn)定性。 算法應(yīng)是公平的。 算法應(yīng)是最佳的。,理想的路由算法,設(shè)計(jì)路由算法時(shí)要考慮諸多技術(shù)要素。,首先，考慮是選擇最短路由還是選擇最佳路由；其次，要考慮通信子網(wǎng)是采用虛電路的還是采用數(shù)據(jù)報(bào)的操作方式；其三，是采用分布式路由算法，即每節(jié)點(diǎn)均為到達(dá)的分組選擇下一步的路由，還是采用集中式路由算法，即由中央節(jié)點(diǎn)或始發(fā)節(jié)點(diǎn)來(lái)決定整個(gè)路由；其四，要考慮關(guān)于網(wǎng)絡(luò)拓樸、流量和延遲等網(wǎng)絡(luò)信息的來(lái)源；最后，確

12、定是采用靜態(tài)路由選擇策略，還是動(dòng)態(tài)路由選擇策略。,,第 5 章 網(wǎng)絡(luò)層,5.2 路由算法 5.2.1 優(yōu)化原則 5.2.2 最短路徑算法 5.2.3 泛洪算法 5.2.4 距離矢量算法 5.2.5 鏈路狀態(tài)路由 5.2.6 層次路由 5.2.7 廣播路由 5.2.8 組播路由 5.2.9 選播路由 5

13、.2.10 移動(dòng)主機(jī)路由 5.2.11 自組織網(wǎng)絡(luò)路由,5.2.1 最優(yōu)化原則,在討論某個(gè)特殊算法之前，有必要指出即使在不知道詳細(xì)的通信子網(wǎng)拓?fù)浣Y(jié)構(gòu)和通信量的情況下，也可能對(duì)最優(yōu)路由作出總體上的斷言。 這種斷言被稱作最優(yōu)化原則， 它斷言，如果路由器J在從路由器I到K的最佳路由上， 那么從J到K的最佳線路就會(huì)在同一路由之中。為理解這些，假設(shè)從I到J的路由為rl，而路由其余部分稱為r2。如果J到K還有在一條比r2更好的路由，那么

14、它可以同r1聯(lián)系起來(lái)，以改進(jìn)從I到K的路由，這與r1r2是最優(yōu)路由的斷言相悖。,5.2.1 最優(yōu)化原則,作為最優(yōu)化原則的一個(gè)直接結(jié)果，可知，從所有源端到目地端的最佳路由集合，形成了以目的地為根的樹。這樣一棵樹稱為匯集樹， 如下圖所示，其中距離度量單位是站點(diǎn)數(shù)。應(yīng)當(dāng)指出的是，匯集樹并不惟一，共他具有相同的路由尺度的樹也有可能存在。所有路由選擇算法的目的就是為所有路由器找出并使用匯集樹。,5.2.1 最優(yōu)化原則,(a) A netwo

15、rk. (b) A sink tree for router B.,5.2.1 最優(yōu)化原則,因?yàn)閰R集樹是一棵樹，它不包含任何循環(huán)。因此每個(gè)分組可在有限的步長(zhǎng)之內(nèi)送達(dá)。實(shí)際上，現(xiàn)實(shí)并不那么簡(jiǎn)單，在操作過(guò)程中鏈路或路由器都有可能卸下或重新裝上。而且，我們必須弄清，是否每個(gè)路由器都得單獨(dú)地獲取計(jì)算其匯集樹的信息，或者用其他方法來(lái)獲取信息。不管怎樣，最優(yōu)化原則和匯集樹為路由選擇算法提供了一個(gè)測(cè)量標(biāo)準(zhǔn)。,路由選擇,路由算法有兩類：,非自適應(yīng)

16、,自適應(yīng),靜態(tài)路由,動(dòng)態(tài)路由,路由表固定,路由表定時(shí)刷新,,,,,路由協(xié)議,簡(jiǎn)便、可靠、易行，適用于負(fù)荷穩(wěn)定、拓?fù)浣Y(jié)構(gòu)變化不大的網(wǎng)絡(luò),算法復(fù)雜，會(huì)增加網(wǎng)絡(luò)負(fù)擔(dān)，但能夠改善網(wǎng)絡(luò)的性能，并有利于流量控制,兩類路由算法,非自適應(yīng)算法離線時(shí)計(jì)算好，網(wǎng)絡(luò)啟動(dòng)時(shí)下載到路由器中；靜態(tài)路由自適應(yīng)算法獲取信息的來(lái)源不同 – 本地、相鄰路由器、改變路由的時(shí)間不同 – 每隔δt秒隨負(fù)載變化路由優(yōu)化的度量方法不同 – 距離、跳數(shù)、估計(jì)的傳輸時(shí)間動(dòng)

17、態(tài)路由,,第 5 章 網(wǎng)絡(luò)層,5.2 路由算法 5.2.1 優(yōu)化原則 5.2.2 最短路徑算法 5.2.3 泛洪算法 5.2.4 距離矢量算法 5.2.5 鏈路狀態(tài)路由 5.2.6 層次路由 5.2.7 廣播路由 5.2.8 組播路由 5.2.9 選播路由 5.2.10 移動(dòng)主機(jī)路由 5.2.

18、11 自組織網(wǎng)絡(luò)路由,靜態(tài)路由選擇算法,靜態(tài)路由選擇策略不用測(cè)量也不需利用網(wǎng)絡(luò)信息，這種策略按某種固定規(guī)則進(jìn)行路由選擇；可分為最短路由選擇法、擴(kuò)散法和基于流量的路由選擇法。,5.2.2.最短路由選擇法,基本思想: 建立一個(gè)子網(wǎng)圖,圖中的每個(gè)節(jié)點(diǎn)代表一臺(tái)路由器,每條弧線代表一條通信線路(鏈路),弧上的數(shù)字代表該線路的權(quán)重。為了在一對(duì)給定的路由器之間選擇一條路由路徑，路由算法只需在圖中找到這對(duì)節(jié)點(diǎn)之間的最短路徑即可。最著名的Dijks

19、tra算法,Dijkstra算法,算法要求每個(gè)節(jié)點(diǎn)用從源節(jié)點(diǎn)沿已知最佳路徑到本節(jié)點(diǎn)的距離來(lái)標(biāo)注。1、開始所有節(jié)點(diǎn)標(biāo)注為無(wú)窮大2、改變與源點(diǎn)相鄰節(jié)點(diǎn)的標(biāo)注3、找到新標(biāo)注點(diǎn)中的最小的點(diǎn)M4、以M為新工作點(diǎn)，標(biāo)注其相鄰節(jié)點(diǎn)（若某點(diǎn)曾經(jīng)標(biāo)記過(guò)，并且新標(biāo)記小于老標(biāo)記，則更新其標(biāo)記）5、返回第3步,利用Dijkstra算法求A到D的最短通路,,,,,,,,,,,,,,,,,,,,A,B(2,A),E(∞,-),G(6,A),,C(∞,-)

20、,F(∞,-),H(∞,-),D(∞,-),,,,,,,,,,,,,,,,,,,,A,B(2,A),E(4,B),G(6,A),,C(9,B),F(∞,-),H(∞,-),D(∞,-),利用Dijkstra算法求A到D的最短通路,,,,,,,,,,,,,,,,,,,,A,B(2,A),E(4,B),G(5,E),,C(9,B),F(6,E),H(∞,-),D(∞,-),,,,,,,,,,,,,,,,,,,,A,B(2,A),E(4,B)

21、,G(5,E),,C(9,B),F(6,E),H(9,G),D(∞,-),,,,,,,,,,,,,,,,,,,,A,B(2,A),E(4,B),G(5,E),,C(9,B),F(6,E),H(8,F),D(∞,-),,,,,,,,,,,,,,,,,,,,A,B(2,A),E(4,B),G(5,E),,C(9,B),F(6,E),H(8,F),D(10,H),,,,,,,,,,,,,,,,,,,,A,B(2,A),E(4,B),G(5,E

22、),,C(9,B),F(6,E),H(8,F),D(10,H),,,,,,,,,,,,,,,,,,,,A,B(2,A),E(4,B),G(5,E),,C(9,B),F(6,E),H(8,F),D(10,H),最短通路為：A-B-E-F-H-D，權(quán)值為10,利用Dijkstra算法求A到D的最短通路,5.2.3.泛洪算法,又稱為：泛射路由選擇法一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)從某條線路收到一個(gè)分組后，再向除該線路外的所有線路重復(fù)發(fā)送收到分組。結(jié)果，最先到

23、達(dá)目的的節(jié)點(diǎn)的一個(gè)或若干個(gè)分組肯定經(jīng)過(guò)了最短的路徑，而且所有可能的路徑都被嘗試過(guò)。 沒(méi)有考慮網(wǎng)路負(fù)載 應(yīng)用：強(qiáng)壯性要求很高的場(chǎng)合 ，只要源、目間有一條信道存在，仍能保證數(shù)據(jù)的可靠傳送 。也可用于廣播式數(shù)據(jù)交換中。 進(jìn)行網(wǎng)絡(luò)的最短路徑及最短傳輸延遲的測(cè)試。無(wú)線網(wǎng)絡(luò)中,泛洪算法,產(chǎn)生大量的重復(fù)分組，解決辦法：每個(gè)分組頭包含站計(jì)數(shù)器，每經(jīng)過(guò)一個(gè)站點(diǎn)計(jì)數(shù)器減一。當(dāng)計(jì)數(shù)器為0時(shí)就扔掉分組。記錄下分組擴(kuò)散的路徑，防止第二次再擴(kuò)散到已

24、擴(kuò)散的路徑中改進(jìn)成選擇擴(kuò)散法，僅發(fā)送到與正確方向接近的那些線路上。,,第 5 章 網(wǎng)絡(luò)層,5.2 路由算法 5.2.1 優(yōu)化原則 5.2.2 最短路徑算法 5.2.3 泛洪算法 5.2.4 距離矢量算法 5.2.5 鏈路狀態(tài)路由 5.2.6 層次路由 5.2.7 廣播路由 5.2.8 組播路由 5.2.9

25、選播路由 5.2.10 移動(dòng)主機(jī)路由 5.2.11 自組織網(wǎng)絡(luò)路由,動(dòng)態(tài)路由選擇算法,靜態(tài)路由選擇算法不考慮網(wǎng)絡(luò)的當(dāng)前負(fù)載情況，現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)通常使用動(dòng)態(tài)的路由算法。節(jié)點(diǎn)的路由選擇要依靠網(wǎng)絡(luò)當(dāng)前的狀態(tài)信息來(lái)決定的策略，稱動(dòng)態(tài)路由選擇策略，也稱為自適應(yīng)路由選擇算法。這種策略能較好地適應(yīng)網(wǎng)絡(luò)流量、拓?fù)浣Y(jié)構(gòu)的變化，有利于改善網(wǎng)絡(luò)的性能。但由于算法復(fù)雜，會(huì)增加網(wǎng)絡(luò)的負(fù)擔(dān)。 距離矢量路由算法鏈路狀態(tài)路由算法,,,,5.2.5

26、鏈路狀態(tài)路由,1979年以前，ARPANET一直使用距離矢量路由算法，而在此后，則被替換為鏈路狀態(tài)路由算法。每個(gè)路由器需要完成以下工作：1．發(fā)現(xiàn)它的鄰居節(jié)點(diǎn)，并知道其網(wǎng)絡(luò)地址2．測(cè)量到它各鄰居節(jié)點(diǎn)點(diǎn)的延遲或開銷3．組裝一個(gè)分組以告之它剛知道的所有4．將這個(gè)分組發(fā)送給所合其他路由器。5．計(jì)算到每個(gè)其他路由器的最短路徑。,,發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址；路由器啟動(dòng)后，通過(guò)發(fā)送HELLO包發(fā)現(xiàn)鄰居結(jié)點(diǎn)；測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的

27、延遲或開銷；一種直接的方法是：發(fā)送一個(gè)要對(duì)方立即響應(yīng)的ECHO包，來(lái)回時(shí)間除以2即為延遲。將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)分組；分組以發(fā)送方的標(biāo)識(shí)符開頭，后面是序號(hào)、年齡和一個(gè)鄰居結(jié)點(diǎn)列表；列表中對(duì)應(yīng)每個(gè)鄰居結(jié)點(diǎn)，都有發(fā)送方到它們的延遲或開銷；鏈路狀態(tài)分組定期創(chuàng)建或發(fā)生重大事件時(shí)創(chuàng)建。,鏈路狀態(tài)路由算法步驟,將這個(gè)分組發(fā)送給所有其它路由器；基本思想：擴(kuò)散法發(fā)布狀態(tài)分組，為控制洪泛，每個(gè)分組包含一個(gè)序號(hào)，每次發(fā)送新分組時(shí)加1。路由

28、器記錄信息對(duì)（源路由器，序號(hào)），當(dāng)一個(gè)鏈路狀態(tài)包到達(dá)時(shí)，若是新的，則分發(fā)；若是重復(fù)的，則丟棄；若序號(hào)比路由器記錄中的最大序號(hào)小，則認(rèn)為過(guò)時(shí)而丟棄；計(jì)算到每個(gè)其它路由器的最短路徑。根據(jù)Dijkstra算法計(jì)算最短路徑；,(a) A network. (b) The link state packets for this network.,鏈路狀態(tài)路由算法應(yīng)用,鏈路狀態(tài)路由算法被廣泛應(yīng)用于實(shí)際的網(wǎng)絡(luò)中。在因特網(wǎng)中被廣泛適用的OSPF開

29、放的最短路徑優(yōu)先協(xié)議，就用到了鏈路狀態(tài)路由算法。,,第 5 章 網(wǎng)絡(luò)層,5.2 路由算法 5.2.1 優(yōu)化原則 5.2.2 最短路徑算法 5.2.3 泛洪算法 5.2.4 距離矢量算法 5.2.5 鏈路狀態(tài)路由 5.2.6 分層路由 5.2.7 廣播路由 5.2.8 組播路由 5.2.9 選播路由 5

30、.2.10 移動(dòng)主機(jī)路由 5.2.11 自組織網(wǎng)絡(luò)路由,,,區(qū)域(region)→簇(cluster)→區(qū)(zone)→群(group)→…,Hierarchical routing.,5.2.7 廣播路由,給所用的目標(biāo)發(fā)送一個(gè)分組，這稱為廣播，為實(shí)現(xiàn)廣播，提出以下方法：第一種，不要求子網(wǎng)既有任何特別性的廣播方法：讓源主機(jī)簡(jiǎn)單地給每一個(gè)目標(biāo)單獨(dú)發(fā)送一個(gè)分組；第二種，多目標(biāo)路由。使用這種方法，每個(gè)分組或者包含一組目標(biāo)，或者包含

31、一個(gè)位圖，由該位圖來(lái)指定所期望的目標(biāo)；第四種，使用了以發(fā)起廣播的路由器為根的匯集樹，生成樹是子網(wǎng)的一個(gè)子集，它包含所有的路由器，但是不包含任何環(huán)；最后一種是逆向路徑轉(zhuǎn)發(fā)：當(dāng)路由器根本不知道任何關(guān)于生成樹的信息時(shí)，也要試圖達(dá)到前一種方法的近似效果。逆向路徑轉(zhuǎn)發(fā)的優(yōu)點(diǎn)是：它的效率相對(duì)合理，而且容易實(shí)現(xiàn)。,逆向路徑轉(zhuǎn)發(fā),基本思想：當(dāng)廣播分組到達(dá)一個(gè)路由器時(shí)，路由器對(duì)它進(jìn)行檢查，查看它到來(lái)的那條線路是否是通常用來(lái)給廣播源發(fā)送分組的那條線路，

32、如果是，該路由器將把這個(gè)廣播分組復(fù)制轉(zhuǎn)發(fā)到除輸入線路外的所有線路。如果不是，則這個(gè)分組將被廢棄。優(yōu)點(diǎn)：效率相對(duì)合理，而且容易實(shí)現(xiàn),逆向路徑轉(zhuǎn)發(fā),匯集樹第一跳：F,H,N,J;第二跳：A,D,M,O,G；第三跳: C,E,K；第四跳:B,L 逆向路徑轉(zhuǎn)發(fā)第一跳：F,H,N,J;第二跳：A,D,E,K,G,O,M,O；第三跳: E,C,G,D.N,K；第四跳: H,B,L,H;第五跳：L,B,,匯集樹,,,,,,,,,,,,,,,,

33、,,,,,,,,,,,,,,,,,,,,,,,H,,廣播算法,利用匯集樹（sink tree）或生成樹（spanning tree）生成樹是通信子網(wǎng)的一個(gè)子集，能將所有路由器連接起來(lái)，并且沒(méi)有回路；匯集樹是最佳路由集合如果每個(gè)路由器知道它的哪些線路屬于生成樹，則將收到的廣播包拷貝到輸入線路以外的所有其它生成樹線路上；算法評(píng)價(jià)優(yōu)點(diǎn)：最優(yōu)利用帶寬，產(chǎn)生最小數(shù)目的分組缺點(diǎn)：每個(gè)路由器都需要構(gòu)造生成樹鏈路狀態(tài)路由算法可以使用距離

34、矢量路由算法不可以使用,5.2.8 組播路由,能夠給一些有明確定義的組發(fā)送消息，這些組的成員數(shù)量雖然很多，但是與整個(gè)網(wǎng)絡(luò)規(guī)模相比很小，給這樣一個(gè)組發(fā)送消息成為多點(diǎn)播送，簡(jiǎn)稱多播，又稱組播，它的路由算法稱為多播路由選擇。多播傳送需要對(duì)組進(jìn)行管理。,多播路由選擇,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,1,2,2,2,2,1,1,1,,,,,,,,,,,1,2,1,2,2,2,2,1,1,1,1,1,1,1,1,2,

35、2,2,2,2,一個(gè)子網(wǎng),最左邊路由器的生成樹,小組1的多點(diǎn)播送樹,小組2的多點(diǎn)播送樹,5.2.9 移動(dòng)主機(jī)路由,1、永久不會(huì)移動(dòng)的主機(jī)稱為固定主機(jī)，它們通過(guò)銅線或者光纖連線到網(wǎng)絡(luò)中。2、遷移主機(jī)，它們基本上也是固定的，但是經(jīng)常會(huì)從一個(gè)固定的站點(diǎn)移動(dòng)到另一個(gè)固定的站點(diǎn)，并且只有當(dāng)它們物理上連接到網(wǎng)絡(luò)的時(shí)候才使用網(wǎng)絡(luò)。3、漫游主機(jī)，是在移動(dòng)過(guò)程中執(zhí)行計(jì)算，它們希望在移動(dòng)的時(shí)候還能保持與網(wǎng)絡(luò)的連接。我們使用術(shù)語(yǔ)移動(dòng)主機(jī)來(lái)代表這類主機(jī)，

36、也就是說(shuō)，移動(dòng)主機(jī)是指那些離開了原始站點(diǎn)還想繼續(xù)連接網(wǎng)絡(luò)的主機(jī)。,移動(dòng)主機(jī)路由,移動(dòng)后重新計(jì)算路由；網(wǎng)絡(luò)層之上提供移動(dòng)；家鄉(xiāng)代理,Packet routing for mobile hosts.,5.2.9 移動(dòng)主機(jī)路由,移動(dòng)主機(jī)登錄到外地代理的過(guò)程1. 外地代理定期廣播一個(gè)分組，宣布自己的存在及其地址。2. 移動(dòng)主機(jī)登錄到外地代理，并給出其原來(lái)所在地的地址，當(dāng)前數(shù)據(jù)鏈路層地址以及一些安全性信息。3. 外地代理與移動(dòng)