計算機網(wǎng)絡 課件第6章網(wǎng)絡層

1、12主要內(nèi)容（主要內(nèi)容（1）6.1網(wǎng)絡層概述網(wǎng)絡層概述6.2路由算法路由算法6.2.1最優(yōu)化原則最優(yōu)化原則6.2.2最短路徑路由算法最短路徑路由算法6.2.3洪泛算法洪泛算法6.2.4距離向量路由算法距離向量路由算法6.2.5鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法6.2.6分層路由分層路由6.2.7移動主機的路由移動主機的路由3主要內(nèi)容（主要內(nèi)容（2）6.3擁塞控制算法擁塞控制算法6.3.1擁塞控制的基本原理擁塞控制的基本原理6.3.2擁塞控制算法擁塞控制算法6.4網(wǎng)絡互連網(wǎng)絡互連 6.4.1級聯(lián)虛電路級聯(lián)虛電路 6.4.2無連接網(wǎng)絡互連無連接網(wǎng)絡互連 6.4.3隧道技術隧道技術 6.4.4互聯(lián)網(wǎng)路

2、由互聯(lián)網(wǎng)路由 6.4.5分段分段 6.4.6防火墻防火墻4主要內(nèi)容（主要內(nèi)容（3）6.5 INTERNET網(wǎng)絡層協(xié)議網(wǎng)絡層協(xié)議6.6.1 IP協(xié)議協(xié)議6.6.2 Internet控制協(xié)議控制協(xié)議6.6.3 內(nèi)部網(wǎng)關路由協(xié)議：內(nèi)部網(wǎng)關路由協(xié)議：OSPF6.6.4 外部網(wǎng)關路由協(xié)議：外部網(wǎng)關路由協(xié)議：BGP56.16.1 網(wǎng)絡層概述（網(wǎng)絡層概述（1 1） ISO 定義定義 網(wǎng)絡層為一個網(wǎng)絡連接的兩個傳送實體間交網(wǎng)絡層為一個網(wǎng)絡連接的兩個傳送實體間交換網(wǎng)絡服務數(shù)據(jù)單元提供功能和規(guī)程的方法，換網(wǎng)絡服務數(shù)據(jù)單元提供功能和規(guī)程的方法，它使傳送實體獨立于路由選擇和交換的方式。它使傳送實體獨立于路由選擇和交換

3、的方式。 網(wǎng)絡層是處理端到端傳輸?shù)淖畹蛯印＞W(wǎng)絡層是處理端到端傳輸?shù)淖畹蛯印?網(wǎng)絡層要解決的關鍵問題是了解通信子網(wǎng)絡層要解決的關鍵問題是了解通信子網(wǎng)的拓撲結(jié)構(gòu)，選擇路由。網(wǎng)的拓撲結(jié)構(gòu)，選擇路由。66.16.1 網(wǎng)絡層概述（網(wǎng)絡層概述（2 2） 網(wǎng)絡層設計的有關問題網(wǎng)絡層設計的有關問題 為傳輸層提供服務為傳輸層提供服務 面向連接服務面向連接服務 傳統(tǒng)電信的觀點：通信子網(wǎng)應該提供可傳統(tǒng)電信的觀點：通信子網(wǎng)應該提供可靠的、面向連接的服務?？康?、面向連接的服務。 無連接服務無連接服務 Internet的觀點：通信子網(wǎng)無論怎么設的觀點：通信子網(wǎng)無論怎么設計都是不可靠的，因此網(wǎng)絡層只需提供無計都是不可靠的，

4、因此網(wǎng)絡層只需提供無連接服務。連接服務。 IP/ATM786.16.1 網(wǎng)絡層概述（網(wǎng)絡層概述（3 3） 網(wǎng)絡層的內(nèi)部組織網(wǎng)絡層的內(nèi)部組織 虛電路（虛電路（virtual circuit） 數(shù)據(jù)報（數(shù)據(jù)報（datagram） 虛電路子網(wǎng)與數(shù)據(jù)報子網(wǎng)的比較虛電路子網(wǎng)與數(shù)據(jù)報子網(wǎng)的比較 路由器內(nèi)存空間與帶寬的權衡路由器內(nèi)存空間與帶寬的權衡虛電路方式，路由器需要維護虛電路虛電路方式，路由器需要維護虛電路的狀態(tài)信息；的狀態(tài)信息；數(shù)據(jù)報方式，每個數(shù)據(jù)報都攜帶完整數(shù)據(jù)報方式，每個數(shù)據(jù)報都攜帶完整的目的的目的/源地址，浪費帶寬源地址，浪費帶寬96.16.1 網(wǎng)絡層概述（網(wǎng)絡層概述（4 4） 連接建立時間與地

5、址查找時間的權衡連接建立時間與地址查找時間的權衡虛電路需要在建立連接時花費時間虛電路需要在建立連接時花費時間數(shù)據(jù)報則在每次路由時過程復雜數(shù)據(jù)報則在每次路由時過程復雜 服務質(zhì)量與可靠性的權衡服務質(zhì)量與可靠性的權衡虛電路方式很容易保證服務質(zhì)量虛電路方式很容易保證服務質(zhì)量QoS(Quality of Service)，適用于實適用于實時操作，但比較脆弱。時操作，但比較脆弱。數(shù)據(jù)報不太容易保證服務質(zhì)量，但是數(shù)據(jù)報不太容易保證服務質(zhì)量，但是對于通信線路的故障，適應性很強。對于通信線路的故障，適應性很強。 106.16.1 網(wǎng)絡層概述（網(wǎng)絡層概述（5 5） 網(wǎng)絡層為傳輸層提供的服務網(wǎng)絡層為傳輸層提供的服務

6、- 面向連接服務：將復雜的功能放在網(wǎng)絡層面向連接服務：將復雜的功能放在網(wǎng)絡層(通信子網(wǎng)通信子網(wǎng))。- 無連接服務：將復雜的功能放在傳輸層。無連接服務：將復雜的功能放在傳輸層。 通信子網(wǎng)提供的服務（面向連接或無連接）通信子網(wǎng)提供的服務（面向連接或無連接）與通信子網(wǎng)結(jié)構(gòu)（虛電路或數(shù)據(jù)報）沒有必與通信子網(wǎng)結(jié)構(gòu)（虛電路或數(shù)據(jù)報）沒有必然聯(lián)系。然聯(lián)系。 服務與子網(wǎng)結(jié)構(gòu)的不同組合的例子服務與子網(wǎng)結(jié)構(gòu)的不同組合的例子11網(wǎng)絡層設計要點網(wǎng)絡層設計要點存儲轉(zhuǎn)發(fā)分組交換存儲轉(zhuǎn)發(fā)分組交換向傳輸層提供的服務向傳輸層提供的服務無連接服務的實現(xiàn)無連接服務的實現(xiàn)面向連接服務的實現(xiàn)面向連接服務的實現(xiàn)虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比

7、較虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較12存儲轉(zhuǎn)發(fā)分組交換存儲轉(zhuǎn)發(fā)分組交換 存儲轉(zhuǎn)發(fā)是計算機網(wǎng)絡的基本功能；存儲轉(zhuǎn)發(fā)是計算機網(wǎng)絡的基本功能； 當網(wǎng)絡出現(xiàn)擁塞時，將需要發(fā)送的分組存儲起來，當網(wǎng)絡出現(xiàn)擁塞時，將需要發(fā)送的分組存儲起來，一旦網(wǎng)絡出現(xiàn)空閑再發(fā)送出去。一旦網(wǎng)絡出現(xiàn)空閑再發(fā)送出去。13向傳輸層提供的服務向傳輸層提供的服務 在網(wǎng)絡層在網(wǎng)絡層/傳輸層的接口面上，網(wǎng)絡層向傳輸層提供服務。傳輸層的接口面上，網(wǎng)絡層向傳輸層提供服務。 在設計網(wǎng)絡層服務時，需要考慮下列目標：在設計網(wǎng)絡層服務時，需要考慮下列目標：（1）所提供的服務應該獨立于路由器技術；）所提供的服務應該獨立于路由器技術；（2）路由器的數(shù)量、類型

8、和拓撲關系對于傳輸層來說應該是）路由器的數(shù)量、類型和拓撲關系對于傳輸層來說應該是不可見的；不可見的；（3）傳輸層可以使用的網(wǎng)絡地址應該有一種統(tǒng)一的編址方案，）傳輸層可以使用的網(wǎng)絡地址應該有一種統(tǒng)一的編址方案，甚至可以跨越多個甚至可以跨越多個LAN和和WAN。問題的焦點：網(wǎng)絡層應該給傳輸層提供的服務有兩種問題的焦點：網(wǎng)絡層應該給傳輸層提供的服務有兩種:（1）面向連接的服務；）面向連接的服務；（2）面向無連接的服務。）面向無連接的服務。14無連接服務的實現(xiàn)無連接服務的實現(xiàn) 所謂無連接的服務：即在發(fā)送過程中，所有的分組所謂無連接的服務：即在發(fā)送過程中，所有的分組都被獨立地傳送到子網(wǎng)中，不需要事先建立

9、連接；都被獨立地傳送到子網(wǎng)中，不需要事先建立連接；這樣的分組通常稱為數(shù)據(jù)報（這樣的分組通常稱為數(shù)據(jù)報（datagram）；）；這樣這樣的子網(wǎng)稱為數(shù)據(jù)報子網(wǎng)（的子網(wǎng)稱為數(shù)據(jù)報子網(wǎng)（datagram subnet）。）。將分組數(shù)據(jù)分成4個部分，通過網(wǎng)絡從H1發(fā)送到H2每個路由器都有一個路由表，每個分組根據(jù)相關的路由表選擇路徑從源主機達到目的主機。15面向連接服務的實現(xiàn)面向連接服務的實現(xiàn) 所謂面向連接是指：在發(fā)送數(shù)據(jù)分組之前，必須首先建立所謂面向連接是指：在發(fā)送數(shù)據(jù)分組之前，必須首先建立起一條從源路由器到目標路由器之間的路徑。這個連接稱起一條從源路由器到目標路由器之間的路徑。這個連接稱為一個為一個V

10、C（Virtual Circuit，虛電路），這個子網(wǎng)稱為虛電虛電路），這個子網(wǎng)稱為虛電路子網(wǎng)（路子網(wǎng)（ Virtual Circuit subnet）。）。在數(shù)據(jù)發(fā)送之前，首先建立連接，這個連接產(chǎn)生了一條虛電路。以后的數(shù)據(jù)分組都沿著這條虛電路發(fā)送。虛電路對網(wǎng)絡線路是敏感的，即若線路發(fā)生故障會影響數(shù)據(jù)分組的傳輸。16虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較1718小結(jié)（小結(jié)（1 1） 網(wǎng)絡層的地位網(wǎng)絡層的地位 位于數(shù)據(jù)鏈路層和傳輸層之間，使用數(shù)據(jù)鏈位于數(shù)據(jù)鏈路層和傳輸層之間，使用數(shù)據(jù)鏈路層提供的服務，為傳輸層提供服務；路層提供的服務，為傳輸層提供服務； 通信子網(wǎng)的最高層；通信子

11、網(wǎng)的最高層； 處理端到端傳輸?shù)淖畹蛯?。處理端到端傳輸?shù)淖畹蛯印?網(wǎng)絡層的作用網(wǎng)絡層的作用 屏蔽各種不同類型網(wǎng)絡之間的差異，實現(xiàn)互屏蔽各種不同類型網(wǎng)絡之間的差異，實現(xiàn)互連連 了解通信子網(wǎng)的拓撲結(jié)構(gòu)，選擇路由，實現(xiàn)了解通信子網(wǎng)的拓撲結(jié)構(gòu)，選擇路由，實現(xiàn)報文的網(wǎng)絡傳輸報文的網(wǎng)絡傳輸19小結(jié)（小結(jié)（2 2） 網(wǎng)絡層的兩種實現(xiàn)方式網(wǎng)絡層的兩種實現(xiàn)方式 ： 數(shù)據(jù)報和虛電路數(shù)據(jù)報和虛電路- 都屬于分組交換，采用存儲轉(zhuǎn)發(fā)機制。都屬于分組交換，采用存儲轉(zhuǎn)發(fā)機制。- 數(shù)據(jù)報數(shù)據(jù)報(datagram)：每個分組被單獨路由，分組每個分組被單獨路由，分組帶有全網(wǎng)唯一的地址帶有全網(wǎng)唯一的地址- 虛電路虛電路(virtua

12、l circuit)：先在源端和目的端之間先在源端和目的端之間建立一條虛電路，所有分組沿虛電路按次序存儲建立一條虛電路，所有分組沿虛電路按次序存儲轉(zhuǎn)發(fā)，最后拆除虛電路。在虛電路中，每個分組轉(zhuǎn)發(fā)，最后拆除虛電路。在虛電路中，每個分組無須進行路徑選擇。無須進行路徑選擇。 網(wǎng)絡層提供的服務網(wǎng)絡層提供的服務- 面向連接的服務和無連接的服務。面向連接的服務和無連接的服務。206.26.2 路由算法（路由算法（1 1） 路由算法：是網(wǎng)絡層軟件的一部分，它負責確定一個進來的路由算法：是網(wǎng)絡層軟件的一部分，它負責確定一個進來的分組應該被傳送到哪一條輸出線路上。分組應該被傳送到哪一條輸出線路上。 如果子網(wǎng)內(nèi)部使

13、用了數(shù)據(jù)報，那么路由器必須針對每一個到如果子網(wǎng)內(nèi)部使用了數(shù)據(jù)報，那么路由器必須針對每一個到達的數(shù)據(jù)分組重新選擇路徑，因為從上一次選擇路徑之后，達的數(shù)據(jù)分組重新選擇路徑，因為從上一次選擇路徑之后，最佳的路徑可能已經(jīng)改變了。最佳的路徑可能已經(jīng)改變了。 如果子網(wǎng)內(nèi)部使用了虛電路，那么只有當一個新的虛電路被如果子網(wǎng)內(nèi)部使用了虛電路，那么只有當一個新的虛電路被建立起來的時候，才需要確定路由路徑。建立起來的時候，才需要確定路由路徑。 路由算法可以分成兩大類：路由算法可以分成兩大類：（1）非自適應的）非自適應的（2）自適應的）自適應的這個算法不會根據(jù)當前測量或者估計的流量和拓撲結(jié)構(gòu)來調(diào)整它們的路由決策，相反

14、路由選擇是預先在離線情況下計算好的，在網(wǎng)絡啟動的時候被下載到路由器中。這個過程有時也被稱為靜態(tài)路由。這個算法會根據(jù)當前測量或者估計的流量和拓撲結(jié)構(gòu)來調(diào)整它們的路由決策。21（1） 路由選擇時機： 網(wǎng)絡路由選擇算法是網(wǎng)絡層軟件的重要組成部分。路由選擇的頻度取決于選擇的時機。 面向連接面向連接VC服務：路由選擇的頻度低，服務：路由選擇的頻度低，既每次在呼叫建立連接時，需選擇一次既每次在呼叫建立連接時，需選擇一次路徑，后續(xù)的數(shù)據(jù)分組均沿已建立的路徑，后續(xù)的數(shù)據(jù)分組均沿已建立的VC路徑傳送（會話路徑選擇）；路徑傳送（會話路徑選擇）； 無連接的無連接的DG服務：路由選擇的頻度高。服務：路由選擇的頻度高。

15、22（2） 路由選擇算法： 要求：正確性簡單化健壯性（Robustness）穩(wěn)定性公平性（Fairness）最優(yōu)化23 指網(wǎng)絡中節(jié)點根據(jù)通信子網(wǎng)的運行狀況（可用的數(shù)據(jù)鏈路、各條鏈路中的信息流量），按照一定的策略選擇一可用的傳送路徑，將信息發(fā)往目的地DTE。ABCDEFGH路由選擇（或路徑控制）路由選擇（或路徑控制）246.2.16.2.1優(yōu)化原則優(yōu)化原則 最優(yōu)化原則：如果路由器最優(yōu)化原則：如果路由器J是在從路由器是在從路由器I到路由器到路由器K的最優(yōu)路徑上，那么，的最優(yōu)路徑上，那么，從從J到到K的最優(yōu)路徑也必定沿著同樣的路由路徑。的最優(yōu)路徑也必定沿著同樣的路由路徑。 最優(yōu)化原則的一個直接結(jié)果是

16、，從所有的源到一個指定目標的最優(yōu)路徑最優(yōu)化原則的一個直接結(jié)果是，從所有的源到一個指定目標的最優(yōu)路徑的集合構(gòu)成了一棵以目標節(jié)點為根的樹。這樣的樹稱為匯集樹。的集合構(gòu)成了一棵以目標節(jié)點為根的樹。這樣的樹稱為匯集樹。(a)一個子網(wǎng)(b)路由器B的匯集樹圖中的距離度量是跳數(shù)；由于匯集樹是一個樹，它不包含任何環(huán)，所以每個分組將在有限跳數(shù)之內(nèi)被遞交給目標主機。256.2.2最短路徑路由算法最短路徑路由算法屬于靜態(tài)路由算法屬于靜態(tài)路由算法 基本思想基本思想 構(gòu)建子網(wǎng)的拓撲圖，圖中的每個結(jié)點代表一個構(gòu)建子網(wǎng)的拓撲圖，圖中的每個結(jié)點代表一個路由器，每條弧代表一條通信線路。為了選擇路由器，每條弧代表一條通信線路。

17、為了選擇兩個路由器間的路由，算法在圖中找出最短路兩個路由器間的路由，算法在圖中找出最短路徑。徑。 測量路徑長度的方法測量路徑長度的方法 結(jié)點數(shù)量結(jié)點數(shù)量 地理距離地理距離 傳輸延遲傳輸延遲 距離、信道帶寬等參數(shù)的加權函數(shù)距離、信道帶寬等參數(shù)的加權函數(shù)26最短路徑路由最短路徑路由 采用跳數(shù)的方法來進行度量最短路徑；采用跳數(shù)的方法來進行度量最短路徑； 見下圖，我們希望找到從見下圖，我們希望找到從A到到D的最短路徑。的最短路徑。開始，將A標記為永久的選擇B為最短路徑從B選擇E為最短路徑修改其它節(jié)點的路徑從E選擇F為最短路徑從F選擇H為最短路徑從A到D的最短路徑為ABEFHD27Dijkstra算法算

18、法(1)Dijkstra算法算法 根據(jù)網(wǎng)絡拓撲，了解所有節(jié)點的鏈路代價根據(jù)網(wǎng)絡拓撲，了解所有節(jié)點的鏈路代價 通過鏈路狀態(tài)廣播知道網(wǎng)絡情況通過鏈路狀態(tài)廣播知道網(wǎng)絡情況 每個節(jié)點都有相同的信息每個節(jié)點都有相同的信息 從源節(jié)點到所有其它節(jié)點計算最短路徑從源節(jié)點到所有其它節(jié)點計算最短路徑 對這些節(jié)點給出路由表對這些節(jié)點給出路由表 反復查詢反復查詢: 通過通過k參數(shù)疊代，使得參數(shù)疊代，使得K到目標地址的最短路到目標地址的最短路徑徑28注意注意: c(i,j): 從從i到到j的代價，如果沒有直接連接，則代的代價，如果沒有直接連接，則代價為無窮大價為無窮大 D(v): 從源到目標地址從源到目標地址V的現(xiàn)行代

19、價的現(xiàn)行代價 p(v): 從源到從源到V的前一個節(jié)點的前一個節(jié)點 N: 所知道的所有最短路徑的集所知道的所有最短路徑的集Dijkstra算法算法(2)29Dijkstra算法算法: 實例實例步驟步驟012345開始開始 節(jié)點節(jié)點AADADEADEBADEBCADEBCFD(B),p(B)2 , A 2, A 2, A D(C),p(C)5, A 4, D 3, E 3, E D(D),p(D)1, A D(E),p(E)無窮大無窮大2, D D(F),p(F)無窮大無窮大無窮大無窮大4, E 4, E 4, E AEDCBF221311253530Dijsktras Algorithm1 In

20、itialization: 2 N = A 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infty 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost

21、to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N 316.2.3擴散法（擴散法（Flooding）（）（1）屬于靜態(tài)路由算法屬于靜態(tài)路由算法 基本思想基本思想 把收到的每一個包，向除了該包到來的線路外把收到的每一個包，向除了該包到來的線路外的所有輸出線路發(fā)送。的所有輸出線路發(fā)送。 主要問題主要問題 擴散要產(chǎn)生大量重復包。擴散要產(chǎn)生大量重復包。 解決措施解決措施 每個包頭包含站點計數(shù)器，每經(jīng)過一站計數(shù)器每個包頭包含站點計數(shù)器，每經(jīng)過一站計數(shù)器減減1，為，為0時則丟棄該

22、包；時則丟棄該包； 記錄包經(jīng)過的路徑記錄包經(jīng)過的路徑32擴散法圖例擴散法圖例ADCEB時延小時延小分組數(shù)量多，易阻塞分組數(shù)量多，易阻塞全路（擴散式）: 洪泛法（Flooding）336.2.3擴散法（擴散法（Flooding）（）（2） 選擇性擴散法（選擇性擴散法（selective flooding） 擴散法的一種改進。將進來的每個包僅發(fā)送擴散法的一種改進。將進來的每個包僅發(fā)送到與正確方向接近的線路上。到與正確方向接近的線路上。 應用情況應用情況 對路由器和線路的資源過于浪費，實際很少對路由器和線路的資源過于浪費，實際很少直接采用；直接采用； 具有極好的健壯性，可用于軍事應用；具有極好的健壯

23、性，可用于軍事應用； 作為衡量標準評價其它路由算法。作為衡量標準評價其它路由算法。346.2.4距離向量路由算法（距離向量路由算法（1）距離向量路由算法（距離向量路由算法（Distance Vector Routing） 屬于動態(tài)路由算法屬于動態(tài)路由算法,也稱也稱Bellman-Ford路路由算法和由算法和Ford-Fulkerson算法，最初用算法，最初用于于ARPANET，被被RIP協(xié)議采用。協(xié)議采用。 基本思想基本思想 每個路由器維護一張表，表中給出了到每個每個路由器維護一張表，表中給出了到每個目的地的已知最佳距離和線路，并通過與目的地的已知最佳距離和線路，并通過與相鄰路由器交換距離信息

24、來更新表；交換距離信息來更新表； 以子網(wǎng)中其它路由器為表的索引，表項包括以子網(wǎng)中其它路由器為表的索引，表項包括兩部分：到達目的結(jié)點的最佳輸出線路，和兩部分：到達目的結(jié)點的最佳輸出線路，和到達目的結(jié)點所需時間或距離；到達目的結(jié)點所需時間或距離；356.2.4距離向量路由算法（距離向量路由算法（2）- 每隔一段時間，路由器向所有鄰居結(jié)點發(fā)送每隔一段時間，路由器向所有鄰居結(jié)點發(fā)送它到每個目的結(jié)點的距離表，同時它也接收它到每個目的結(jié)點的距離表，同時它也接收每個鄰居結(jié)點發(fā)來的距離表；每個鄰居結(jié)點發(fā)來的距離表；- 鄰居結(jié)點鄰居結(jié)點X發(fā)來的表中，發(fā)來的表中，X到路由器到路由器i的距離的距離為為Xi，本路由器

25、到本路由器到X的距離為的距離為m，則路由器則路由器經(jīng)過經(jīng)過X到到i的距離為的距離為Xi + m。根據(jù)不同鄰居發(fā)根據(jù)不同鄰居發(fā)來的信息，計算來的信息，計算Xi + m，并取最小值，更新并取最小值，更新本路由器的路由表；本路由器的路由表；36距離表數(shù)據(jù)結(jié)構(gòu)距離表數(shù)據(jù)結(jié)構(gòu) 例如：對于節(jié)點例如：對于節(jié)點X, 目標節(jié)點目標節(jié)點Y，節(jié)點節(jié)點X到到Y(jié)的的距離是通過鄰節(jié)點距離是通過鄰節(jié)點Z來計算的來計算的DX (Y,Z)c(X,Z) + min D Z (Y,w)=W37距離表距離表: 例子例子AEDCB781212D ()ABCDA1764B148911D5542E通過下列節(jié)點到目標節(jié)點的代價通過下列節(jié)點到

26、目標節(jié)點的代價目標節(jié)點目標節(jié)點D (C,D)Ec(E,D) + min D (C,w)Dw= 2+2 = 4D (A,D)Ec(E,D) + min D (A,w)Dw= 2+3 = 5D (A,B)Ec(E,B) + min D (A,w)Bw= 8+6 = 14loop!loop!38距離表給出路由表距離表給出路由表D ()ABCDA1764B148911D5542Ecost to destination viadestination ABCD A,1D,5D,4D,4Outgoing link to use, costdestinationDistance tableRouting ta

27、ble39圖圖6.9實例實例一個子網(wǎng)圖中列出了J從鄰居路由器接收到的延遲矢量。例如：A到B為12，A到C為25，A到D為40等。假定J到A，I，H，K的延遲分別為8，10，12，6。則：J到B是通過A到B，即為81220；J到C是通過I到C，即為101828；等等。對于所有其它的目標也執(zhí)行同樣的計算過程，最后得到新的J路由表。406.2.5鏈路狀態(tài)路由算法（鏈路狀態(tài)路由算法（1）鏈接鏈接-狀態(tài)狀態(tài)( L-S：Link-Status ) 算法，又稱最短路徑算法，又稱最短路徑優(yōu)先（優(yōu)先（SPF ：Shortest Path First）算法。算法。該算法原理：各網(wǎng)關主動測試所有與其相鄰網(wǎng)關之該算法

28、原理：各網(wǎng)關主動測試所有與其相鄰網(wǎng)關之間的狀態(tài)，即網(wǎng)關周期性地向相鄰的網(wǎng)關發(fā)出簡短間的狀態(tài)，即網(wǎng)關周期性地向相鄰的網(wǎng)關發(fā)出簡短的查詢報文，根據(jù)相鄰網(wǎng)關的響應判斷鏈接的狀態(tài)的查詢報文，根據(jù)相鄰網(wǎng)關的響應判斷鏈接的狀態(tài)（鏈路的通或斷，主機有否激活），這就是取名（鏈路的通或斷，主機有否激活），這就是取名L-S的原因；隨后各網(wǎng)關周期性地廣播其的原因；隨后各網(wǎng)關周期性地廣播其L-S信息；網(wǎng)信息；網(wǎng)關收到關收到L-S報文后，可刷新互連網(wǎng)拓撲，若報文后，可刷新互連網(wǎng)拓撲，若L-S發(fā)生發(fā)生變更，立即采用最短路徑（變更，立即采用最短路徑（Dijkstra）算法，刷新算法，刷新本地路由表。本地路由表。41每一個路

29、由器要求完成的工作每一個路由器要求完成的工作（1）發(fā)現(xiàn)它的鄰居節(jié)點，并知道其網(wǎng)絡地址；）發(fā)現(xiàn)它的鄰居節(jié)點，并知道其網(wǎng)絡地址；（2）測量到各鄰居節(jié)點的延遲或者開銷；）測量到各鄰居節(jié)點的延遲或者開銷；（3）構(gòu)造一個分組，分組中包含所有它剛剛）構(gòu)造一個分組，分組中包含所有它剛剛知道的信息；知道的信息；（4）將這個分組發(fā)送給所有其它的路由器；）將這個分組發(fā)送給所有其它的路由器；（5）計算出到每一個其它路由器的最短路徑。）計算出到每一個其它路由器的最短路徑。42 每個路由器創(chuàng)建三個單列的表，一個跟蹤直連的相鄰路由器，一個確定整個互連網(wǎng)的拓撲，一個用于路由表。 L-S路由器比任何V-D路由協(xié)議獲取更多互連

30、網(wǎng)信息。 L-S的IP路由協(xié)議的例子是整個鏈路狀態(tài)OSPF。 43發(fā)現(xiàn)鄰居節(jié)點發(fā)現(xiàn)鄰居節(jié)點 當一個路由器啟動的時候，它的第一個任務是找出哪些路當一個路由器啟動的時候，它的第一個任務是找出哪些路由器是它的鄰居。由器是它的鄰居。 實現(xiàn)方法：在每一條點到點線路上發(fā)送一個特殊的實現(xiàn)方法：在每一條點到點線路上發(fā)送一個特殊的HELLO分組。線路另一端的路由器回送一個應答說明它是誰。分組。線路另一端的路由器回送一個應答說明它是誰。 這些名字必須是全局唯一的，因為當一個遠程路由器以后這些名字必須是全局唯一的，因為當一個遠程路由器以后聽到有三個路由器連接到聽到有三個路由器連接到F上的時候，它必須能夠確定這三上的

31、時候，它必須能夠確定這三個路由器所提到的個路由器所提到的F是否是同一個路由器是否是同一個路由器F。為了發(fā)現(xiàn)鄰居節(jié)點，需要對LAN進行建模，在網(wǎng)絡拓撲中將LAN本身看作是一個節(jié)點。44測量線路開銷測量線路開銷 鏈路狀態(tài)路由算法要求每一個路由器知道它到各個鄰居節(jié)點之間的延鏈路狀態(tài)路由算法要求每一個路由器知道它到各個鄰居節(jié)點之間的延遲，或者至少有一個合理的估計值。遲，或者至少有一個合理的估計值。 為了決定這份延遲信息，最直接的辦法是在這條線路上發(fā)送一個特殊為了決定這份延遲信息，最直接的辦法是在這條線路上發(fā)送一個特殊的的ECHO分組，另一端必須回送一個應答。通過計算出往返時間，再分組，另一端必須回送一

32、個應答。通過計算出往返時間，再除以除以2，則發(fā)送方路由器就可以得到一個合理的延遲估計值。，則發(fā)送方路由器就可以得到一個合理的延遲估計值。 如果要想得到更好的結(jié)果，則可以多次執(zhí)行這樣的測試過程，然后取如果要想得到更好的結(jié)果，則可以多次執(zhí)行這樣的測試過程，然后取它們的平均值。它們的平均值。 但實際中還存在著負載，即兩個方向上的延遲是不對稱的。但實際中還存在著負載，即兩個方向上的延遲是不對稱的。如果考慮負載的話，負載會發(fā)生變化，有時CF最短，有時EI最短。很難確定最佳路徑。為了避免在選擇最佳路徑過程中的震蕩現(xiàn)象，利用先驗知識負載合理地分布在多條線路上。45創(chuàng)建鏈路狀態(tài)分組創(chuàng)建鏈路狀態(tài)分組 一旦所需要

33、的交換信息已經(jīng)收集到了，每個路由器的下一一旦所需要的交換信息已經(jīng)收集到了，每個路由器的下一步工作是建立一個包含所有這些數(shù)據(jù)的分組。步工作是建立一個包含所有這些數(shù)據(jù)的分組。 分組的內(nèi)容：發(fā)送方標識序列號年齡鄰居列表（包分組的內(nèi)容：發(fā)送方標識序列號年齡鄰居列表（包含這個鄰居的延遲）含這個鄰居的延遲）一個子網(wǎng)創(chuàng)建鏈路狀態(tài)分組有兩種：定期創(chuàng)建、當某一個重要事情發(fā)生的時候創(chuàng)建。46發(fā)布鏈路狀態(tài)分組發(fā)布鏈路狀態(tài)分組 鏈路狀態(tài)路由算法最技巧的部分是如何可靠地發(fā)布鏈路狀態(tài)分組。鏈路狀態(tài)路由算法最技巧的部分是如何可靠地發(fā)布鏈路狀態(tài)分組。 當分組被發(fā)布出去并且被安裝后，首先獲得分組的路由器將改變它們的當分組被發(fā)布

34、出去并且被安裝后，首先獲得分組的路由器將改變它們的路由路徑。路由路徑。 不同的路由器有可能使用不同版本的拓撲結(jié)構(gòu)，從而導致了不一致性、不同的路由器有可能使用不同版本的拓撲結(jié)構(gòu)，從而導致了不一致性、環(huán)、不可達的機器，或者其它的問題。環(huán)、不可達的機器，或者其它的問題。 發(fā)布鏈路狀態(tài)分組的思路：發(fā)布鏈路狀態(tài)分組的思路：（1）使用擴散法來發(fā)布鏈路狀態(tài)分組；）使用擴散法來發(fā)布鏈路狀態(tài)分組；（2）為了控制擴散過程，每一個分組包含一個序列號（隨著每個新的分組）為了控制擴散過程，每一個分組包含一個序列號（隨著每個新的分組而遞增）；而遞增）；（3）每個路由器記錄它所有（源路由器、序列號）對；）每個路由器記錄它所

35、有（源路由器、序列號）對；（4）當一個分組進來后，路由器檢查這個新的分組；）當一個分組進來后，路由器檢查這個新的分組；（5）如果是新的，就轉(zhuǎn)發(fā)該分組；）如果是新的，就轉(zhuǎn)發(fā)該分組；（6）如果它是一個重復分組，則將它丟棄；）如果它是一個重復分組，則將它丟棄；（7）如果分組的序列號小于當前最大序列號，則它將被當作過時分組而拒）如果分組的序列號小于當前最大序列號，則它將被當作過時分組而拒絕。絕。47 從從E發(fā)來的鏈路狀態(tài)包有兩個，一個經(jīng)過發(fā)來的鏈路狀態(tài)包有兩個，一個經(jīng)過EAB，另另一個經(jīng)過一個經(jīng)過EFB； 從從D發(fā)鏈路狀態(tài)包有兩個，一個經(jīng)過發(fā)鏈路狀態(tài)包有兩個，一個經(jīng)過DCB，另一個另一個經(jīng)過經(jīng)過DFB

36、；1:有事件發(fā)生；0：沒有事件發(fā)生486.2.5鏈路狀態(tài)路由算法（鏈路狀態(tài)路由算法（2） 鏈路狀態(tài)算法（鏈路狀態(tài)算法（LS）和距離向量算法和距離向量算法（DV）的比較的比較 路由信息的復雜性路由信息的復雜性 LS路由信息向全網(wǎng)發(fā)送路由信息向全網(wǎng)發(fā)送N節(jié)點，節(jié)點，E個連接的情況下，每個節(jié)點個連接的情況下，每個節(jié)點發(fā)送發(fā)送O(nE)的報文的報文 DV僅在鄰居節(jié)點之間交換僅在鄰居節(jié)點之間交換496.2.5鏈路狀態(tài)路由算法（鏈路狀態(tài)路由算法（3） 收斂（收斂（Convergence）速度速度 LS 使用最短路徑優(yōu)先算法，算法復雜度使用最短路徑優(yōu)先算法，算法復雜度為為O(n*2)n個結(jié)點（不包括源結(jié)點）

37、，需要個結(jié)點（不包括源結(jié)點），需要n*(n+1)/2 次比較次比較使用更有效的實現(xiàn)方法，算法復雜使用更有效的實現(xiàn)方法，算法復雜度可以達到度可以達到O(nlogn) 可能存在路由振蕩（可能存在路由振蕩（oscillations）506.2.5鏈路狀態(tài)路由算法（鏈路狀態(tài)路由算法（4） DV 收斂時間不定收斂時間不定可能會出現(xiàn)路由循環(huán)可能會出現(xiàn)路由循環(huán)count-to-infinity（無窮大）（無窮大）問題問題516.2.5鏈路狀態(tài)路由算法（鏈路狀態(tài)路由算法（5） 健壯性健壯性: 如果路由器不能正常工作會發(fā)生什如果路由器不能正常工作會發(fā)生什么么? LS結(jié)點會廣播錯誤的鏈路開銷結(jié)點會廣播錯誤的鏈路開

38、銷每個結(jié)點只計算自己的路由表每個結(jié)點只計算自己的路由表 DV結(jié)點會廣播錯誤的路徑開銷結(jié)點會廣播錯誤的路徑開銷每個結(jié)點的路由表被別的結(jié)點使用，每個結(jié)點的路由表被別的結(jié)點使用，錯誤會傳播到全網(wǎng)錯誤會傳播到全網(wǎng)526.2.6分層路由分層路由分層路由（分層路由（Hierarchical Routing） 網(wǎng)絡規(guī)模增長帶來的問題網(wǎng)絡規(guī)模增長帶來的問題 路由器中的路由表增大；路由器中的路由表增大； 路由器為選擇路由而占用的內(nèi)存、路由器為選擇路由而占用的內(nèi)存、CPU時間時間和網(wǎng)絡帶寬增大。和網(wǎng)絡帶寬增大。 分層路由分層路由 分而治之的思想；分而治之的思想； 根據(jù)需要，將路由器分成區(qū)域（根據(jù)需要，將路由器分成

39、區(qū)域（regions）、）、聚類（聚類（clusters）、）、區(qū)（區(qū)（zones）和組和組（groups） Fig. 5-17，路由表由路由表由17項減為項減為7項。項。 分層路由帶來的問題分層路由帶來的問題 路由表中的路由不一定是最優(yōu)路由。路由表中的路由不一定是最優(yōu)路由。53546.2.7 廣播路由廣播路由 在網(wǎng)絡中如果給所有的目標發(fā)送同一個分組，這樣的傳輸在網(wǎng)絡中如果給所有的目標發(fā)送同一個分組，這樣的傳輸稱為廣播（稱為廣播（broadcasting）。）。 廣播的方法：廣播的方法：（1）簡單地給每個目標單獨發(fā)送一個分組；）簡單地給每個目標單獨發(fā)送一個分組；（2）擴散法；）擴散法；（3）多

40、目標路由；）多目標路由；（4）以發(fā)起廣播的路由器為根的匯集樹，或者生成樹；）以發(fā)起廣播的路由器為根的匯集樹，或者生成樹；（5）逆向路徑轉(zhuǎn)發(fā)）逆向路徑轉(zhuǎn)發(fā)一個子網(wǎng) 匯集樹 樹556.2.8 多播路由多播路由 采用一種辦法能夠給一些有明確定義的組采用一種辦法能夠給一些有明確定義的組發(fā)送消息，這些組的成員數(shù)量雖然很多，發(fā)送消息，這些組的成員數(shù)量雖然很多，但是與整個網(wǎng)絡規(guī)模相比卻很小，這樣一但是與整個網(wǎng)絡規(guī)模相比卻很小，這樣一個組發(fā)送消息稱為個組發(fā)送消息稱為多播多播（multicasting），），它的路由算法稱為多播路由。它的路由算法稱為多播路由。 多播傳輸要求對組進行管理。首先需要有多播傳輸要求對

41、組進行管理。首先需要有一種辦法來創(chuàng)建和銷毀組，并且允許進程一種辦法來創(chuàng)建和銷毀組，并且允許進程加入或者離開組。加入或者離開組。 多播傳輸關心的是，當一個進程加入組的多播傳輸關心的是，當一個進程加入組的時候，它需要把這個事實告訴它的主機。時候，它需要把這個事實告訴它的主機。 對于路由器來說，它們的哪些主機屬于哪對于路由器來說，它們的哪些主機屬于哪些組非常重要。些組非常重要。 當主機與組之間的從屬關系發(fā)生變化的時當主機與組之間的從屬關系發(fā)生變化的時候，主機必須將這些變化告訴路由器，或候，主機必須將這些變化告訴路由器，或者由路由器定期地詢問它們的主機。者由路由器定期地詢問它們的主機。 無論采用哪些一

42、種方式，路由器必須知道無論采用哪些一種方式，路由器必須知道它們的哪些主機屬于哪些組。它們的哪些主機屬于哪些組。 路由器再告訴它們的鄰居，所以，主機與路由器再告訴它們的鄰居，所以，主機與組的從屬信息再整個子網(wǎng)中傳播開來。組的從屬信息再整個子網(wǎng)中傳播開來。一個子網(wǎng)路由器生成樹組1的多播樹組2的多播樹566.2.9 移動主機的路由（移動主機的路由（1）移動主機分為兩類：（1）遷移主機（migratory host）：基本上是固定的，但是經(jīng)常會從一個固定的站點移動到另一個固定的站點，并且只有當它們物理上連接到網(wǎng)絡的時候才使用網(wǎng)絡。（2）漫游主機（roaming host）：實際上是在移動過程中執(zhí)行計算

43、，它們希望在移動的時候還能夠保持與網(wǎng)絡的連接。 以上兩類統(tǒng)稱為移動主機（mobile host）:是指那些離開了原始站點還想繼續(xù)連接網(wǎng)絡的主機。576.2.9 移動主機的路由（移動主機的路由（2）移動主機路由算法的目標： 能夠做到用移動主機的主地址給它們發(fā)送分組，而且不管這些主機在哪里，這些分組都能夠被遞交給它們。主要的問題：怎樣才能找到這些主機？查找主機的具體步驟：（1）注冊：當一臺新的主機進入一個區(qū)域，不管采用什么方式入網(wǎng)（連到LAN、漫游進入無線網(wǎng)），該主機必須在外部代理那里注冊自己；（2）注銷：當一臺主機離開網(wǎng)絡時，也應該宣布自己的離開請求，以便讓外部代理注銷自己，但往往主機采用關機（

44、大部分軟件都提供在關機后幾分鐘后自動注銷）58小結(jié)（小結(jié)（1 1） 最優(yōu)化原則最優(yōu)化原則路由算法的目的是找出并使用匯集樹。路由算法的目的是找出并使用匯集樹。 靜態(tài)路由算法靜態(tài)路由算法最短路徑路由算法最短路徑路由算法擴散算法擴散算法59小結(jié)（小結(jié)（2 2） 動態(tài)路由算法動態(tài)路由算法 距離向量路由算法距離向量路由算法 將自己（路由結(jié)點）對全網(wǎng)拓撲結(jié)構(gòu)的認將自己（路由結(jié)點）對全網(wǎng)拓撲結(jié)構(gòu)的認識告訴給鄰居識告訴給鄰居無窮計算問題，水平分裂算法無窮計算問題，水平分裂算法- 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法將自己將自己（路由結(jié)點）（路由結(jié)點）對鄰居的認識洪泛給對鄰居的認識洪泛給全網(wǎng)全網(wǎng) 分層路由分層路由

45、移動主機的路由移動主機的路由606.3 擁塞控制算法擁塞控制算法(1) 什么叫擁塞：當一個子網(wǎng)或者子網(wǎng)的一部分中出現(xiàn)太什么叫擁塞：當一個子網(wǎng)或者子網(wǎng)的一部分中出現(xiàn)太多分組的時候，網(wǎng)絡的性能開始下降。這種情況稱為多分組的時候，網(wǎng)絡的性能開始下降。這種情況稱為擁塞（擁塞（congestion）。）。當主機傳送到子網(wǎng)中的分組數(shù)量在子網(wǎng)的內(nèi)容范圍內(nèi)的時候，所有這些分組都可以遞交（除了有些受到傳輸錯誤的影響以外），被遞交的分組數(shù)量與發(fā)送的分組數(shù)量成正比。隨著流量的快速遞增，路由器不再能夠處理所有這些分組，于是它們開始丟失分組，在流量很高的時候，性能將嚴重惡化，幾乎沒有分組能夠被遞交。擁塞發(fā)生的因素很多。

46、例如：多條輸入線路對同樣的輸出；慢速的處理器也可能引起擁塞。616.36.3 擁塞控制算法（擁塞控制算法（2 2） 擁塞產(chǎn)生的原因擁塞產(chǎn)生的原因 多個輸入對應一個輸出；多個輸入對應一個輸出； 慢速處理器；慢速處理器； 低帶寬線路。低帶寬線路。 解決辦法解決辦法 針對某個因素的解決方案，只能對提高網(wǎng)絡針對某個因素的解決方案，只能對提高網(wǎng)絡性能起到一點點好處，甚至可能僅僅是轉(zhuǎn)移性能起到一點點好處，甚至可能僅僅是轉(zhuǎn)移了影響性能的瓶頸；了影響性能的瓶頸； 需要全面考慮各個因素。需要全面考慮各個因素。62擁塞控制和流控制的區(qū)別擁塞控制和流控制的區(qū)別 擁塞控制的任務是確保子網(wǎng)能夠承載所到達的流量。這是一個

47、全局性的擁塞控制的任務是確保子網(wǎng)能夠承載所到達的流量。這是一個全局性的問題，涉及到各方面的行為，包括所有的主機、所有的路由器、路由器問題，涉及到各方面的行為，包括所有的主機、所有的路由器、路由器內(nèi)部的存儲轉(zhuǎn)發(fā)處理過程，以及所有可能會削弱子網(wǎng)承載容量的其它內(nèi)部的存儲轉(zhuǎn)發(fā)處理過程，以及所有可能會削弱子網(wǎng)承載容量的其它因素。因素。流控制問題：例如有一個1000Gbps的光纖網(wǎng)絡，一臺超級計算機試圖以1Gbps的速率給一臺個人計算機傳送一個文件。盡管這里并沒有擁塞（網(wǎng)絡本身沒有任何問題），但是流控制卻是需要的。以便強迫超級計算機經(jīng)常停下來，給個人計算機以喘息的機會。擁塞控制問題：例如有一個存儲轉(zhuǎn)發(fā)網(wǎng)絡

48、，線路為1Mbps，它有1000臺大型計算機，其中一半的機器正在試圖給另一半機器以100Kbps的速率傳送文件。這里的問題并不是快速的發(fā)送方會淹沒慢速的接收方，而是總流量超過了網(wǎng)絡的處理能力。流控制只與特定的發(fā)送方和特定的接收方之間的點到點流量有關。它的任流控制只與特定的發(fā)送方和特定的接收方之間的點到點流量有關。它的任務是，確保一個快速的發(fā)送方不會持續(xù)地以超過接收方能力的速率傳輸數(shù)據(jù)。務是，確保一個快速的發(fā)送方不會持續(xù)地以超過接收方能力的速率傳輸數(shù)據(jù)。流控制通常涉及到的做法是，接收方向發(fā)送方提供某種直接的反饋，以便告流控制通常涉及到的做法是，接收方向發(fā)送方提供某種直接的反饋，以便告訴另一端的情

49、形到底怎么樣。訴另一端的情形到底怎么樣。636.3.1 虛電路子網(wǎng)中的擁塞控制虛電路子網(wǎng)中的擁塞控制 準入技術（準入技術（admission controa）:一種廣泛應用的、防止已經(jīng)擁塞的子一種廣泛應用的、防止已經(jīng)擁塞的子網(wǎng)進一步惡化的技術是準入技術。網(wǎng)進一步惡化的技術是準入技術。q 準入技術的原理：一旦出現(xiàn)擁塞的信號，則不再創(chuàng)建虛電路，直到問題準入技術的原理：一旦出現(xiàn)擁塞的信號，則不再創(chuàng)建虛電路，直到問題排除為止。排除為止。q 在網(wǎng)絡系統(tǒng)中，在出現(xiàn)擁塞的情況下，企圖建立新的傳輸層連接將會失在網(wǎng)絡系統(tǒng)中，在出現(xiàn)擁塞的情況下，企圖建立新的傳輸層連接將會失敗。敗。q 在電話系統(tǒng)中，當一臺交換機超

50、過負載的時候，它也會采用準入控制的在電話系統(tǒng)中，當一臺交換機超過負載的時候，它也會采用準入控制的方法，不再送出撥號音。方法，不再送出撥號音。另一種方法是：允許建立新的虛電路，但是要謹慎地選擇路由器，使所有新的虛電路都繞開有問題的區(qū)域。省略掉擁塞的路由器和它們所有的線路。避開了擁塞的路由器。646.3.2 數(shù)據(jù)報子網(wǎng)中的擁塞控制數(shù)據(jù)報子網(wǎng)中的擁塞控制 由于每個數(shù)據(jù)報都需要走各自的路由，因此數(shù)據(jù)報子網(wǎng)與虛電路子的擁由于每個數(shù)據(jù)報都需要走各自的路由，因此數(shù)據(jù)報子網(wǎng)與虛電路子的擁塞控制方法是不太一樣的。塞控制方法是不太一樣的。 采用每臺路由器監(jiān)視它的輸出線路和其它資源的使用情況，采用合理的采用每臺路由

51、器監(jiān)視它的輸出線路和其它資源的使用情況，采用合理的方式，就可以控制它的擁塞。方式，就可以控制它的擁塞。 給出公式：給出公式：U新aU舊（1-a） fU新：這條線路最新的利用率，取值在0.0和1.0之間； U舊：這條線路過去的利用率，取值在0.0和1.0之間； f ：線路瞬時利用率；a：代表路由器忘記最新的歷史情況的概率。每當U超過了特定的閾值的時候，該輸出線路進入到一種“警告”狀態(tài)；路由器對每個新到來的分組都要進行檢查，看它的輸出線路是否處于警告狀態(tài)。如果是的話，就需要采取某種措施。656.3.3 負載丟棄負載丟棄 當網(wǎng)絡上任何一種方法都不能消除擁塞的時候，路由器可以當網(wǎng)絡上任何一種方法都不能

52、消除擁塞的時候，路由器可以進行進行負載脫落負載脫落（load shedding）。）。 負載脫落是指當路由器因為來不及處理分組而被淹沒的時候，負載脫落是指當路由器因為來不及處理分組而被淹沒的時候，只要將這些分組丟棄即可。例如：只要將這些分組丟棄即可。例如：某些視頻壓縮算法會定期地傳輸一個完整的幀，然后以幀差（與完整幀之間的差異）的形式傳輸后續(xù)的幀。在這種情況下，丟棄幀差中的分組顯然比丟棄完整幀中的分組要好的多?？紤]傳輸一個既包含ASCII文本又包含圖片的文檔。很顯然，丟棄某個圖象中的一行象素比丟掉一行可讀的文本帶來的損失要小的多。采用早期檢測可以避免擁塞的發(fā)生。由于路由器可能無法判斷哪一個源是

53、引起擁塞的罪魁，所以，路由器采用隨機地從擁塞隊列中選取分組。666.3.4 抖動控制抖動控制 對于象音頻流和視頻流這樣的應用，只要傳輸時間是恒定的，那么它就對于象音頻流和視頻流這樣的應用，只要傳輸時間是恒定的，那么它就不會介意到底需要不會介意到底需要20ms還是還是30ms才將分組遞交給目標主機。才將分組遞交給目標主機。 分組到達的變化量（即標準偏差）被稱為抖動（分組到達的變化量（即標準偏差）被稱為抖動（jitter）。）。比如：在高抖動的情況下，有的分組需要20ms到達，而其它的分組需要30ms到達，這將使得聲音或者電影質(zhì)量很不穩(wěn)定。高抖動的情形低抖動的情形通過計算出沿途每一跳的期望傳輸時間

54、，就可以對抖動加以控制。對于多個正在競爭同一條輸出線路的分組，路由器可以將預定時間提前到達的分組減慢，而落后的分組逐漸加速，就可以減緩抖動的程度。676.4 服務質(zhì)量服務質(zhì)量 前面我們討論的是減少擁塞和提高網(wǎng)絡性能。前面我們討論的是減少擁塞和提高網(wǎng)絡性能。 然而隨著多媒體網(wǎng)絡連接的需求增長，通常僅僅依靠這些然而隨著多媒體網(wǎng)絡連接的需求增長，通常僅僅依靠這些特殊的手段還不夠。特殊的手段還不夠。 除此之外還需要做更多的工作，以便通過網(wǎng)絡和協(xié)議的設除此之外還需要做更多的工作，以便通過網(wǎng)絡和協(xié)議的設計來保證服務質(zhì)量。計來保證服務質(zhì)量。導致網(wǎng)絡服務質(zhì)量問題出現(xiàn)的原因大致有兩類：（1）與網(wǎng)絡無關的因素業(yè)務

55、服務器過載；人為因素。（2）網(wǎng)絡的原因網(wǎng)絡設備原因；接入鏈路的容量；不均衡的流量分布導致的擁塞。686.4.1 需求需求 從一個源到目標的分組流稱為一個流（從一個源到目標的分組流稱為一個流（flow）。）。 在面向連接的網(wǎng)絡中，屬于同一個流的所有分組將會走同樣的路由路徑；在面向連接的網(wǎng)絡中，屬于同一個流的所有分組將會走同樣的路由路徑； 面向無連接的網(wǎng)絡中，它們可能會走不同的路徑。面向無連接的網(wǎng)絡中，它們可能會走不同的路徑。 每個流需求特征為：可靠性、延遲、抖動和帶寬。這四個特征合起來決每個流需求特征為：可靠性、延遲、抖動和帶寬。這四個特征合起來決定了一個流所要求的服務質(zhì)量（定了一個流所要求的服

56、務質(zhì)量（Quality of Service,QoS）696.4.2 獲得好的服務質(zhì)量所使用的技術獲得好的服務質(zhì)量所使用的技術 從網(wǎng)絡的角度看：從網(wǎng)絡的角度看：（1 1）當整個網(wǎng)絡發(fā)生擁塞時，設法盡量增加網(wǎng)絡資源。）當整個網(wǎng)絡發(fā)生擁塞時，設法盡量增加網(wǎng)絡資源。（2 2）根據(jù)網(wǎng)絡拓撲、流量和流向等因素合理優(yōu)化網(wǎng)絡的規(guī)劃）根據(jù)網(wǎng)絡拓撲、流量和流向等因素合理優(yōu)化網(wǎng)絡的規(guī)劃和設計，引導流量流向，盡量提高網(wǎng)絡資源的利用率。和設計，引導流量流向，盡量提高網(wǎng)絡資源的利用率。 從業(yè)務的角度看：從業(yè)務的角度看：（1 1）在）在IPIP網(wǎng)絡資源一定的情況下，在網(wǎng)絡資源一定的情況下，在IPIP網(wǎng)絡上提供有別于網(wǎng)絡上

57、提供有別于“盡力而為盡力而為”的其他類型的業(yè)務，即提供有區(qū)別的業(yè)務。的其他類型的業(yè)務，即提供有區(qū)別的業(yè)務。（2 2）在網(wǎng)絡有可能發(fā)生擁塞時，對服務質(zhì)量比較敏感的業(yè)務）在網(wǎng)絡有可能發(fā)生擁塞時，對服務質(zhì)量比較敏感的業(yè)務設置較高的優(yōu)先級，使其能夠盡量優(yōu)先得到服務。設置較高的優(yōu)先級，使其能夠盡量優(yōu)先得到服務。 但無論是采用什么樣的但無論是采用什么樣的QoSQoS模型，這些思路都以犧牲低優(yōu)先模型，這些思路都以犧牲低優(yōu)先級的業(yè)務為代價，來換取高優(yōu)先業(yè)務的級的業(yè)務為代價，來換取高優(yōu)先業(yè)務的QoSQoS保證。保證。70提供充足的資源提供充足的資源提供充足的資源：路由器的容量、緩沖提供充足的資源：路由器的容量、

58、緩沖區(qū)空間、帶寬，以保證分組能夠順利的區(qū)空間、帶寬，以保證分組能夠順利的通過。通過。充足的網(wǎng)絡資源是解決服務質(zhì)量問題的充足的網(wǎng)絡資源是解決服務質(zhì)量問題的關鍵。在網(wǎng)絡沒有擁塞時有無關鍵。在網(wǎng)絡沒有擁塞時有無QoSQoS機制都機制都行，因為即使是行，因為即使是“盡力而為盡力而為”的的IPIP包也包也能夠得到很好的服務。能夠得到很好的服務。這種方案的代價太昂貴。這種方案的代價太昂貴。71緩沖能力緩沖能力 在接收方，數(shù)據(jù)流在被遞交之前先緩存起來。將數(shù)據(jù)流緩存起來并不會在接收方，數(shù)據(jù)流在被遞交之前先緩存起來。將數(shù)據(jù)流緩存起來并不會影響到可靠性和帶寬，但會增加延遲，然而，這樣可以消除抖動。對于影響到可靠性

59、和帶寬，但會增加延遲，然而，這樣可以消除抖動。對于音頻和視頻點播，抖動是主要的問題，所以這項技術非常有用。音頻和視頻點播，抖動是主要的問題，所以這項技術非常有用。分組離開源主機分組到達緩沖區(qū)分組從緩沖區(qū)中移除開始播放出現(xiàn)停頓如果將增大緩沖區(qū)空間，使得分組在起始時間再多延遲一會兒，就可以解決這個問題。許多音頻或視頻播放器在開始播放之前需要先緩存10秒左右的流數(shù)據(jù)。例如：Windows Media Player、RealPlayer等72流量整形流量整形流量整形（流量整形（traffic shaping）是指調(diào)節(jié)數(shù)據(jù)傳輸?shù)氖侵刚{(diào)節(jié)數(shù)據(jù)傳輸?shù)钠骄俾剩ㄒ约巴话l(fā)性），在服務器端對流量進行平均速率（以及

60、突發(fā)性），在服務器端對流量進行平滑處理。平滑處理。當一個連接被建立起來時，用戶和子網(wǎng)對于他們之當一個連接被建立起來時，用戶和子網(wǎng)對于他們之間的電路上應該遵循什么樣的流量模式（即流量的間的電路上應該遵循什么樣的流量模式（即流量的形式）達成一致的協(xié)議。有時稱為服務等級協(xié)議形式）達成一致的協(xié)議。有時稱為服務等級協(xié)議（service level argreement）。）。流量整形技術可以減少擁塞，對于實時數(shù)據(jù)的傳輸流量整形技術可以減少擁塞，對于實時數(shù)據(jù)的傳輸非常重要，比如音頻和視頻連接等，它們有嚴格的非常重要，比如音頻和視頻連接等，它們有嚴格的服務質(zhì)量要求。服務質(zhì)量要求。73漏桶算法（漏桶算法（1）