第6章---網(wǎng)絡(luò)層

1、第6章 網(wǎng)絡(luò)層,6.1 網(wǎng)絡(luò)層服務(wù)及其實現(xiàn)6.2 路由選擇6.3 交通控制6.3 交通控制,6.1 網(wǎng)絡(luò)層服務(wù)及其實現(xiàn),6.1.1 面向連接的服務(wù)和無連接的服務(wù) 網(wǎng)絡(luò)層為傳輸層提供服務(wù)。一般來說網(wǎng)絡(luò)層在IMP中運行,傳輸層在主機中運行,因此網(wǎng)絡(luò)層與傳輸層之間的界面就是通信子網(wǎng)和用戶之間的界面,網(wǎng)絡(luò)層提供的服務(wù)就是通信子網(wǎng)為用戶提供的服務(wù)。ISO為網(wǎng)絡(luò)層定義了兩種服務(wù)——面向連接的服務(wù)(ISO

2、8348)和無連接的服務(wù)(ISO8473)。,關(guān)于網(wǎng)絡(luò)層應(yīng)該提供什么樣的服務(wù)的問題在ISO內(nèi)部有相當(dāng)大的爭議。代表電信公司的一方,出于行業(yè)習(xí)慣,認為通信網(wǎng)絡(luò)應(yīng)該提供面向連接的服務(wù)。因為傳統(tǒng)的電話網(wǎng)絡(luò)服務(wù)就是面向連接的(但是電路交換的)。另一方以ARPA網(wǎng)為代表,堅持網(wǎng)絡(luò)層只提供無連接的服務(wù),畢竟ARPA網(wǎng)以這種方式已成功地運行多年了。,由圖6.1可以看出,從數(shù)據(jù)鏈路層開始都向上面的鄰層分別提供面向連接的服務(wù)和無連接的服務(wù),只有物理層提供

3、一種服務(wù),即透明地傳輸比特流。在傳輸層和網(wǎng)絡(luò)層,對上層的任何一種服務(wù)(面向連接的或無連接的)都可以用下層的任何一種服務(wù)實現(xiàn)。,圖6.1 OSI參考模型中面向連接的服務(wù)和無連接的服務(wù),6.1.2數(shù)據(jù)報和虛電路 一種自然的想法是在通信子網(wǎng)內(nèi)部用數(shù)據(jù)報方式實現(xiàn)無連接的網(wǎng)絡(luò)服務(wù),用虛電路實現(xiàn)面向連接的網(wǎng)絡(luò)服務(wù)。 四種組合中有三種是可供選擇的: (1)內(nèi)部虛電路實現(xiàn)

4、面向連接的服務(wù)。 (2)內(nèi)部數(shù)據(jù)報實現(xiàn)面向連接的服務(wù)。 (3)內(nèi)部數(shù)據(jù)報實現(xiàn)無連接的服務(wù)。 (4)內(nèi)部虛電路實現(xiàn)無連接的服務(wù)。,下面介紹幾種具體網(wǎng)絡(luò)中實現(xiàn)網(wǎng)絡(luò)服務(wù)的方法。 (1)ARPANET。 ARPANET提供兩種服務(wù),并分別稱其為數(shù)據(jù)報服務(wù)和虛電路服務(wù),但是在通信子網(wǎng)內(nèi)部只有數(shù)據(jù)報一種實現(xiàn)方法。

5、 (2)TYMNET。TYMNET 網(wǎng)絡(luò)是美國Tymshare公司于70年代建成的商用計算機通信網(wǎng),目前它的服務(wù)范圍已擴展到加拿大和歐洲地區(qū)。TYMNET網(wǎng)絡(luò)內(nèi)部用虛電路支持面向連接的網(wǎng)絡(luò)服務(wù),網(wǎng)絡(luò)把用戶主機看作是字符流(而不是分組流)的源。,圖6.2 TYMNET的虛電路,圖6.3TYMNET的幀和分組的格式(a)幀(物理記錄)格式 (b)分組(邏輯記錄)格式,在其他常見的網(wǎng)絡(luò)中,提供的服務(wù)和

6、實現(xiàn)方法也各不相同,DECnet網(wǎng)絡(luò)層用數(shù)據(jù)報提供無連接的網(wǎng)絡(luò)服務(wù),面向連接的服務(wù)由上層實現(xiàn)SNA則和TYMNET一樣,網(wǎng)絡(luò)層用虛電路提供面向連接的網(wǎng)絡(luò)服務(wù)。這4種網(wǎng)絡(luò)提供的服務(wù)和實現(xiàn)方法表示在表6―1中。,表6―1 網(wǎng)絡(luò)服務(wù)及其實現(xiàn)方法,6.2 路由選擇,網(wǎng)絡(luò)層的主要功能是把數(shù)據(jù)分組從源結(jié)點傳送到目標結(jié)點,所以為傳送的數(shù)據(jù)分組選擇合適的路徑就是網(wǎng)絡(luò)層要解決的關(guān)鍵問題。路徑選擇算法的好壞關(guān)系到網(wǎng)絡(luò)資源的利用率和網(wǎng)絡(luò)性能的高低。,無論

7、采用什么樣的路由選擇算法,路由選擇過程都涉及到下面一些問題: (1)測量(或獲取)有關(guān)路由選擇的網(wǎng)絡(luò)參數(shù) (2)把路由信息傳播到適當(dāng)?shù)木W(wǎng)絡(luò)結(jié)點(網(wǎng)管中心或有關(guān)的轉(zhuǎn)發(fā)結(jié)點) (3)計算和更新路由表 (4)根據(jù)路由表的信息對傳送中的分組進行調(diào)度。,圖6.4 網(wǎng)絡(luò)信息流的振蕩,6.2.1 最短通路算法 最短通路的更一般的說

8、法是最少費用通路。通路的費用是組成通路的各段鏈路的費用的累加和,一段鏈路的費用則可根據(jù)網(wǎng)絡(luò)的設(shè)計目標不同而指定為線路容量,線路延遲,隊列長度或可用資源數(shù)量等。無論采用哪種費用準則,都可用一個數(shù)表示費用的值。于是,如圖6.5所表示的那樣,最小費用通路問題就歸結(jié)為加權(quán)圖中的最短通路問題,這個問題的算法已經(jīng)定型。,圖6.5 加權(quán)圖中的最短通路,假定結(jié)點1為源結(jié)點,則 (1)初始化:置N=｛1｝,對每一個vN,置D(v)

9、=l(1,v) (2)重復(fù):找出一個結(jié)點w∈N,且D(w)是最小的,把w加入N。然后對所有不屬于N的結(jié)點v按下式更新D(v): D(v)=Min［D(v),D(w)+l(w,v)］ 對圖6.5應(yīng)用這個算法,可得到表6―2,產(chǎn)生的最短通路樹表示在圖6.6(a)中。圖6.6(b)是為結(jié)點1計算出的路由表,該表指明通向各個目標結(jié)點的轉(zhuǎn)發(fā)路徑。,表6―2 Dijk

10、stra算法,圖6.6 計算最短通路的例 (a)最短通路樹 (b)結(jié)點1的路由表,搜索過程如下:(1)初始化:置D(1)=0,所有非目標結(jié)點都加上標志(·,∞)(2)重復(fù):對每一個非目標結(jié)點v用下式更新D(v): D(v)=Min［D(w)+l(v,w)］其中結(jié)點w為v的相鄰結(jié)點。,表6―3 Ford&Fulkerson算法,6.2.2 路由選擇策略

11、 1.固定式路由選擇 這是一種最簡單的路由選擇策略。每一對源和目標之間的通路都是按照某種最小費用準則預(yù)先選擇好的,并存儲在網(wǎng)絡(luò)中某些地方。在設(shè)計網(wǎng)絡(luò)路由時依據(jù)的費用準則不能與網(wǎng)絡(luò)的動態(tài)參數(shù)(例如通信量的分布)有關(guān),至多在網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化時才重新計算一次全網(wǎng)的路由。固定式路由選擇的實現(xiàn)可采用路由表法。例如,對圖6.5的網(wǎng)絡(luò)應(yīng)用前面介紹的最短通路算法可為各個結(jié)點產(chǎn)生路由表,如圖6.7所示。,圖6.7 固定式路

12、由選擇,2. 擴散式路由選擇 擴散式路由選擇的原理如下:源結(jié)點把分組發(fā)送給每個相鄰結(jié)點,每個中間結(jié)點接收到分組后復(fù)制若干個拷貝,轉(zhuǎn)發(fā)給除輸入鏈路之外的其他各個相鄰結(jié)點,這樣同一分組的拷貝像洪水泛濫一樣,迅速布滿全網(wǎng),總有一個拷貝最先到達目標結(jié)點。 目標結(jié)點接收最先到達的分組后丟棄其余分組。使用擴散式路由選擇時,有可能發(fā)生分組被重復(fù)拷貝的情況,例如在圖6.8中結(jié)點2和3都收到了結(jié)點1發(fā)來的分組,它們拷貝后都要把分

13、組發(fā)往對方,形成了無謂的重復(fù)傳送。,圖6.8 擴散式路由選擇,擴散式路由選擇技術(shù)有兩個特性值得注意: (1)源和目標結(jié)點之間所有可能的通路都被試用了,這樣無論有多少鏈路或結(jié)點失效,只要有一條通路存在,分組總能到達目的地。 (2)由于所有通路都被利用了,必然有一個分組走了最短的通路最先到達目標結(jié)點。,3. 隨機式路由選擇 隨機式路由選擇與擴散式相比對網(wǎng)絡(luò)負載的增加

14、小得多。同時仍然保持了擴散式的簡單性和堅強性。 為了減少盲目性,可以對各個輸出鏈路指定不同的選擇概率。例如根據(jù)各個輸出鏈路數(shù)據(jù)速率用下式計算出每條鏈路的選擇概率:,4.自適應(yīng)式路由選擇 實現(xiàn)這種高標準的靈活的算法要付出更大的代價: (1)最佳路由的計算更復(fù)雜,更頻繁,因而開銷更大 (2)收集到的路由信息要傳播到計算路由的結(jié)點,或者計算的結(jié)果要傳

15、播到轉(zhuǎn)發(fā)分組的結(jié)點。這些都增加了網(wǎng)絡(luò)的負載 (3)自適應(yīng)算法對網(wǎng)絡(luò)參數(shù)的變化反應(yīng)太快會引起網(wǎng)絡(luò)流的振蕩,反應(yīng)太慢則得不到最佳路由,為減少這些風(fēng)險要經(jīng)常對算法本身的某些參數(shù)進行調(diào)整,這又增加了網(wǎng)絡(luò)管理的難度。,自適應(yīng)算法雖然有這些缺點,但是在大型公共網(wǎng)絡(luò)中仍然得到廣泛的應(yīng)用。因為這種算法的優(yōu)點也是明顯的: (1)能極大地改善網(wǎng)絡(luò)的性能,網(wǎng)絡(luò)的經(jīng)營者可以得到最大的吞吐率,網(wǎng)絡(luò)用戶則會明顯感到網(wǎng)絡(luò)

16、延遲很小 (2)能對網(wǎng)絡(luò)的通信量進行控制,避免或減緩網(wǎng)絡(luò)中擁擠和阻塞的發(fā)生(這一點后面還要詳細討論)。,通常根據(jù)路由信息的來源和進行路由決策的地點,把各種自適應(yīng)算法分為以下三類: (1)孤立式自適應(yīng)策略:利用本地信息進行分布式控制 (2)分布式自適應(yīng)策略:利用相鄰結(jié)點的信息進行分布式控制 (3)集中式自適應(yīng)策略:利用全網(wǎng)結(jié)點的信息進行集中

17、式控制。,圖6.9 孤立式自適應(yīng)路由選擇算法的例,6.2.3 路由選擇算法實例 1. ARPANET ARPANET的路由選擇算法經(jīng)過了多次修改,其中較大的變化有三次。下面分別介紹這三次變化及算法演變過程。 仍然用圖6.5的網(wǎng)絡(luò)為例,圖中各個鏈路上的數(shù)字代表鏈路延遲(即隊列長度)。根據(jù)這個圖,可計算出結(jié)點1的路由表如下:,1 1

18、 0 2 2 2 3 4 3 4 4 1 5 4 2 6 4 4,目標結(jié)點 下一 結(jié)點 延遲 時間,圖6.10 網(wǎng)絡(luò)延遲的例,假設(shè)經(jīng)過很短時間后,網(wǎng)絡(luò)中的鏈路延遲變成了圖6.10所示的那

19、樣。于是結(jié)點1收到了三個相鄰結(jié)點傳送的延遲矢量: D2 D3 D4 2 5 1 0 3 2 3 0

20、 5 2 5 0 4 1 6 6 3 8,由于d1,2=2,d1,3=5,d1,4=1,故對應(yīng)于3個延遲矢量可計算得到3個新的延遲矢量: 目標結(jié)點 D′2

21、 D′3 D′4 2 2 8 3 3 5 5 6 4 4 10 1 5 6

22、 6 7 6 8 8 9,然后取每行的最小者,可得到結(jié)點1的新路由表: 目標結(jié)點 下一結(jié)點 延遲時間 1 1 0 2 2 2

23、 3 3 5 4 4 1 5 3 6 6 3 8,計算過程是這樣的:首先測量最近10秒鐘的平均延遲,然后對這個值進行下面的處理: (1)利用簡單的M/M/1排隊模型,

24、把平均延遲轉(zhuǎn)換為鏈路利用率的估值。根據(jù)排隊論,利用率p可表示為延遲t的函數(shù): 其中,s為分組服務(wù)時間,即平均分組長度(600bit)/鏈路速率。,(2)用以前的利用率平滑上一步的計算結(jié)果,得出平均利用率: u(n+1)=0.5p(n+1)+0.5u(n) 其中u(n)表示在取樣時刻n的平均利用率,p(n+1)表示在取樣后的下一時刻根據(jù)第1

25、步計算的利用率。 (3)把鏈路費用表示為平均利用率的函數(shù),函數(shù)關(guān)系如圖6.11所示。最后得到的費用值實際上是變換了形式的線路時延。,2. TYMNET TYMNET是集中控制的網(wǎng)絡(luò),由一個運行管理程序的中心結(jié)點進行路由管理,管理程序記錄著每一條鏈路的固定費用值。 TYMNETI的特點是,在輕負載時,盡量使用高速鏈路,當(dāng)負載增加時,路由選擇算法能平滑地把負載分散

26、到低速鏈路上,同時各個轉(zhuǎn)發(fā)結(jié)點的處理開銷也很小。 TYMNETⅡ也對恢復(fù)過程進行了改進。,圖6.11 ARPANET的時延函數(shù),6.3 交通控制,6.3.1 交通控制技術(shù)的分類和分級 1.交通控制技術(shù)的分類 交通控制技術(shù)有三種類型,各有不同的控制目標,即流量控制,擁擠控制和防止死鎖。 (1)流量控制。 流量控制是指調(diào)節(jié)

27、兩點間的傳輸速率,即由接收方根據(jù)它的接收速率控制發(fā)送過程,避免出現(xiàn)來不及接收的情況,通常用某種形式的滑動窗口協(xié)議來實現(xiàn)流量控制。,圖6.12 有效吞吐率和網(wǎng)絡(luò)負載的關(guān)系,圖6.13 緩沖區(qū)干擾的例,圖6.14 緩沖區(qū)干擾引起的吞吐率衰減,(2) 擁擠控制。 擁擠控制不同于流量控制,它的目的是保持網(wǎng)絡(luò)中的分組數(shù)不要超過某一限度,因為一旦這一界限被打破,網(wǎng)絡(luò)性能將顯著下降。 分組在網(wǎng)絡(luò)中流

28、動類似于車輛在公路上行駛,重負載下的通信網(wǎng)絡(luò)更像是交通高峰時期的公路系統(tǒng)。,圖6.15 擁擠控制的效果,(3) 防止死鎖。 計算機網(wǎng)絡(luò)中發(fā)生死鎖和多任務(wù)操作系統(tǒng)中發(fā)生死鎖的情況是類似的,即多個用戶進程等待已分配的資源獲得釋放,并且進程對資源的等待和占用關(guān)系形成環(huán)路條件。 最簡單的一種死鎖是直接存儲—轉(zhuǎn)發(fā)死鎖。如圖6.16(a)所示,結(jié)點A和B通過一段鏈路直接相連,當(dāng)負載較重時,結(jié)點A中

29、的緩沖區(qū)迅速被流向B的分組占滿,而結(jié)點B中的緩沖區(qū)則被流向A的分組用完。,另外一種死鎖是間接存儲—轉(zhuǎn)發(fā)死鎖,這種死鎖表示在圖6.16(b)中。若每一個結(jié)點中的緩沖區(qū)都被發(fā)往下一個結(jié)點的分組占滿,使得每一個結(jié)點都不能接收新的分組,這樣就形成了等待回路,使信息無法流動。,圖6.16 存儲—轉(zhuǎn)發(fā)死鎖(a)直接死鎖 (b)間接死鎖,圖6.17 結(jié)構(gòu)化的緩沖池,圖6.18 分組通過結(jié)構(gòu)化緩沖,圖6.19裝配死鎖(a)裝配緩沖區(qū)死鎖

30、(b)重排序死鎖,2. 交通控制技術(shù)的分級 分組交換網(wǎng)中的各種交通控制技術(shù)可以分級實施,圖6.20畫出了通常的分級方法。,圖6.20 交通控制的分級,6.3.2 交通控制技術(shù)的實現(xiàn) 1. ARPANET中的交通控制 當(dāng)某一最大限制達到時,多余的分組被丟棄。緩沖池分配情況如圖6.21所示。ARPANET采用的這種緩沖區(qū)管理方法稱為最小分配最大限制的共享分配法。,圖

31、6.21 ARPANETIMP的緩沖區(qū)分配,2. TYMNET中的交通控制 TYMNET對虛電路實施網(wǎng)絡(luò)訪問級和跳步級兩級流控。管理程序在建立虛電路時根據(jù)要求的峰值數(shù)據(jù)速率指定沿路邏輯信道的緩沖區(qū)空間配額。各結(jié)點在允許的配額限制內(nèi)發(fā)送數(shù)據(jù),每發(fā)送一個字符,配額數(shù)減1。配額用完后,停止發(fā)送,等待恢復(fù)配額。在TYMNETⅡ中,由接收結(jié)點掌握恢復(fù)配額的時機,因為接收結(jié)點知道它在某個信道上接收了多少字符,也知道什么時

32、候配額用完,或者它的緩沖空間是否富裕。,3.SNA中的交通控制 SNA的交通控制機制是基于窗口步調(diào)的概念。網(wǎng)絡(luò)中的交通流量以窗口為單位度量,在得到接收端認可的情況下,發(fā)送端可以發(fā)送一個窗口所能容納的全部報文。(圖6.22中,窗口大小K=4)。,圖6.22 SNA的窗口步調(diào)機制,SNA的分組中有5bit的窗口步調(diào)機制,如表6―4所示。在每個窗口中發(fā)送的第一個分組把“虛路由步調(diào)請求”VRPRQ置位,表示請求允許發(fā)

33、送下一個窗口。接收結(jié)點收到VRPRQ后,發(fā)回已將“虛路由步調(diào)響應(yīng)”VRPRS置位的分組。如果接收結(jié)點無法為另外一個窗口分配緩沖資源,則暫緩發(fā)送VRPRS,直到有足夠的資源可用。,表6―4 SNA分組中的窗口步調(diào)機制,若PC≤WS-MIN,則維持其不變,若PC＞W(wǎng)S-MIN,則使PC=WS-MIN?？傊谌魏吻闆r下,WS均復(fù)位為WS-MIN,PC值小于等于WS-MIN。處理過程如圖6.23所示。,圖6.23 SNA虛電路窗口步調(diào)控制

34、,6.4 X.25公共數(shù)據(jù)網(wǎng),6.4.1 X.25建議概述 公共數(shù)據(jù)網(wǎng)PDN(PublicDataNetwork)是在整個國家或全世界范圍內(nèi)提供公共電信服務(wù)的數(shù)據(jù)通信網(wǎng)。,圖6.24表示三層之間的關(guān)系。本地的用戶數(shù)據(jù)傳送到X.25的分組層后,分組層在它前面加上包含控制信息的分組頭。分組頭和用戶數(shù)據(jù)組成的分組交給鏈路層后,鏈路層又加上幀頭和幀尾組成數(shù)據(jù)幀,然后由物理層送入通信子網(wǎng)。而幀頭和幀尾信息則由LAP-

35、B實體用于控制數(shù)據(jù)鏈路的工作。,圖6.24 X.25三層之間的關(guān)系,6.4.2 X.25分組層協(xié)議PLP 1.虛電路的建立和清除 X.25的分組層提供虛電路服務(wù)。有兩種形式的虛電路:一種是虛呼叫VC(VirtualCalls),一種是永久虛電路PVC(PermanentVirtualCircuits)。虛呼叫是動態(tài)建立的虛電路,有呼叫建立,數(shù)據(jù)傳送和呼叫清除等幾個過程。,圖6.25

36、表示通過虛呼叫進行數(shù)據(jù)通信的例子。當(dāng)一個DTE想與遠方的DTE通信時首先要建立虛電路,于是它發(fā)送Call Requst分組,該分組中包含呼叫方和被呼方的地址以及它指定的虛電路代號。,圖6.25 X.25虛電路的建立和清除,虛電路的診斷分組保留之外,建立虛電路時可以使用其余的4095個代號,因而理論上說,一個DTE最多可建立4095個虛電路。這些虛電路多路復(fù)用DTE—DCE之間的物理鏈路,進行全雙工通信。一條虛電路可能對應(yīng)于一個應(yīng)用程序

37、,進程或終端。DTE發(fā)出或接收的每個分組都屬于某一個已存在或要建立的虛電路。,圖6.26 虛電路代號的分配,2. 分組類型和格式 X.25PLP使用的分組類型列在表6―5中。各種分組的格式大同小異,分別列于圖6.27(a)～(e)。,表6―5 X.25PLP分組類型,PLP協(xié)議把用戶數(shù)據(jù)分成一定大小的塊(一般為128字節(jié)),再加24位或32位的分組頭組成數(shù)據(jù)分組。 圖6.27(e)

38、表示的是Call Request分組的完整格式。分組類型字段對Call Request是0000101,對其他控制分組可能取別的值。,圖6.27 X.25分組格式 (a)3位順序號的數(shù)據(jù)分組(b)7位順序號的數(shù)據(jù)分組 (c)RR,RNR和REJ分組(3位順序號)(d)RR,RNR和REJ分組(7位順序號)(e)控制分組,圖6.27 X.25分組格式 (a)3位順序號的數(shù)據(jù)分組(b)7位順序號的數(shù)據(jù)分組 (c)RR,RNR和

39、REJ分組(3位順序號)(d)RR,RNR和REJ分組(7位順序號)(e)控制分組,3. 流控和差錯控制 X.25流控和差錯控制機制和HDLC是類似的。每個數(shù)據(jù)分組都包含發(fā)送順序號P(S)和接收順序號P(R),默認的順序號為3位,但是可以在建立虛電路時通過特別業(yè)務(wù)機制要求使用7位順序號。P(S)字段由發(fā)送DTE按遞增的次序指定給每個發(fā)出的數(shù)據(jù)分組,P(R)字段捎帶了DTE期望從另外一端接收的下一個分組的序號。

40、,3. 流控和差錯控制 X.25流控和差錯控制機制和HDLC是類似的。每個數(shù)據(jù)分組都包含發(fā)送順序號P(S)和接收順序號P(R),默認的順序號為3位,但是可以在建立虛電路時通過特別業(yè)務(wù)機制要求使用7位順序號。P(S)字段由發(fā)送DTE按遞增的次序指定給每個發(fā)出的數(shù)據(jù)分組,P(R)字段捎帶了DTE期望從另外一端接收的下一個分組的序號。,4.分組排序 X.25能夠識別分組組成的序列,這個特點很有用

41、。例如當(dāng)長的數(shù)據(jù)塊經(jīng)過一個只允許小分組通過的網(wǎng)絡(luò)時,要保持數(shù)據(jù)塊的完整性,就需要這個功能。事實上在網(wǎng)絡(luò)互連時,這是互聯(lián)網(wǎng)協(xié)議經(jīng)常遇到的問題。,B型分組中M和D位的設(shè)置按如下規(guī)則進行。若D=1,表示接收DTE向發(fā)送DTE送回的端到端應(yīng)答,這也是對整個完備分組序列的應(yīng)答。如果M=1,則表示后隨另一個完備分組序列。這樣,一個大的分組序列可以有其子序列,并且可以對大的分組序列進行分段的端到端應(yīng)答。圖6.28表示了分組排序的例子,其中,圖6.28