計算機網絡-西安電子科技大學個人主頁系統(tǒng)我的西電我的

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

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

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

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

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

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

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

8、使網絡中的路由器可以做得比較簡單，而且價格低廉（與電信網的交換機相比較）。如果主機（即端系統(tǒng)）中的進程之間的通信需要是可靠的，那么就由網絡的主機中的運輸層負責（包括差錯處理、流量控制等）。采用這種設計思路的好處是：網絡的造價大大降低，運行方式靈活，能夠適應多種應用。因特網能夠發(fā)展到今日的規(guī)模，充分證明了當初采用這種設計思路的正確性。,5.1.5虛電路與數(shù)據報網絡的對較,,第 5 章 網絡層,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 移動主機路由 5.2.11 自組織網絡路由,5.2 路由算法,通信子網為網絡源節(jié)點和目的節(jié)

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

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

12、定是采用靜態(tài)路由選擇策略，還是動態(tài)路由選擇策略。,,第 5 章 網絡層,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 移動主機路由 5.2.11 自組織網絡路由,5.2.1 最優(yōu)化原則,在討論某個特殊算法之前，有必要指出即使在不知道詳細的通信子網拓撲結構和通信量的情況下，也可能對最優(yōu)路由作出總體上的斷言。 這種斷言被稱作最優(yōu)化原則， 它斷言，如果路由器J在從路由器I到K的最佳路由上， 那么從J到K的最佳線路就會在同一路由之中。為理解這些，假設從I到J的路由為rl，而路由其余部分稱為r2。如果J到K還有在一條比r2更好的路由，那么

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

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

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

17、態(tài)路由,,第 5 章 網絡層,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 移動主機路由 5.2.

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

19、tra算法,Dijkstra算法,算法要求每個節(jié)點用從源節(jié)點沿已知最佳路徑到本節(jié)點的距離來標注。1、開始所有節(jié)點標注為無窮大2、改變與源點相鄰節(jié)點的標注3、找到新標注點中的最小的點M4、以M為新工作點，標注其相鄰節(jié)點（若某點曾經標記過，并且新標記小于老標記，則更新其標記）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，權值為10,利用Dijkstra算法求A到D的最短通路,5.2.3.泛洪算法,又稱為：泛射路由選擇法一個網絡節(jié)點從某條線路收到一個分組后，再向除該線路外的所有線路重復發(fā)送收到分組。結果，最先到

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

24、擴散的路徑中改進成選擇擴散法，僅發(fā)送到與正確方向接近的那些線路上。,,第 5 章 網絡層,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 移動主機路由 5.2.11 自組織網絡路由,動態(tài)路由選擇算法,靜態(tài)路由選擇算法不考慮網絡的當前負載情況，現(xiàn)代計算機網絡通常使用動態(tài)的路由算法。節(jié)點的路由選擇要依靠網絡當前的狀態(tài)信息來決定的策略，稱動態(tài)路由選擇策略，也稱為自適應路由選擇算法。這種策略能較好地適應網絡流量、拓撲結構的變化，有利于改善網絡的性能。但由于算法復雜，會增加網絡的負擔。 距離矢量路由算法鏈路狀態(tài)路由算法,,,,5.2.5

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

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

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

29、放的最短路徑優(yōu)先協(xié)議，就用到了鏈路狀態(tài)路由算法。,,第 5 章 網絡層,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 移動主機路由 5.2.11 自組織網絡路由,,,區(qū)域(region)→簇(cluster)→區(qū)(zone)→群(group)→…,Hierarchical routing.,5.2.7 廣播路由,給所用的目標發(fā)送一個分組，這稱為廣播，為實現(xiàn)廣播，提出以下方法：第一種，不要求子網既有任何特別性的廣播方法：讓源主機簡單地給每一個目標單獨發(fā)送一個分組；第二種，多目標路由。使用這種方法，每個分組或者包含一組目標，或者包含

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

32、如果是，該路由器將把這個廣播分組復制轉發(fā)到除輸入線路外的所有線路。如果不是，則這個分組將被廢棄。優(yōu)點：效率相對合理，而且容易實現(xiàn),逆向路徑轉發(fā),匯集樹第一跳：F,H,N,J;第二跳：A,D,M,O,G；第三跳: C,E,K；第四跳:B,L 逆向路徑轉發(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）生成樹是通信子網的一個子集，能將所有路由器連接起來，并且沒有回路；匯集樹是最佳路由集合如果每個路由器知道它的哪些線路屬于生成樹，則將收到的廣播包拷貝到輸入線路以外的所有其它生成樹線路上；算法評價優(yōu)點：最優(yōu)利用帶寬，產生最小數(shù)目的分組缺點：每個路由器都需要構造生成樹鏈路狀態(tài)路由算法可以使用距離

34、矢量路由算法不可以使用,5.2.8 組播路由,能夠給一些有明確定義的組發(fā)送消息，這些組的成員數(shù)量雖然很多，但是與整個網絡規(guī)模相比很小，給這樣一個組發(fā)送消息成為多點播送，簡稱多播，又稱組播，它的路由算法稱為多播路由選擇。多播傳送需要對組進行管理。,多播路由選擇,,,,,,,,,,,,,,,,,,,,,,,,,,,,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,一個子網,最左邊路由器的生成樹,小組1的多點播送樹,小組2的多點播送樹,5.2.9 移動主機路由,1、永久不會移動的主機稱為固定主機，它們通過銅線或者光纖連線到網絡中。2、遷移主機，它們基本上也是固定的，但是經常會從一個固定的站點移動到另一個固定的站點，并且只有當它們物理上連接到網絡的時候才使用網絡。3、漫游主機，是在移動過程中執(zhí)行計算，它們希望在移動的時候還能保持與網絡的連接。我們使用術語移動主機來代表這類主機，

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