第6章---網絡層

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、 0 2 2 2 3 4 3 4 4 1 5 4 2 6 4 4,目標結點 下一 結點 延遲 時間,圖6.10 網絡延遲的例,假設經過很短時間后,網絡中的鏈路延遲變成了圖6.10所示的那

19、樣。于是結點1收到了三個相鄰結點傳送的延遲矢量: 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,故對應于3個延遲矢量可計算得到3個新的延遲矢量: 目標結點 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,然后取每行的最小者,可得到結點1的新路由表: 目標結點 下一結點 延遲時間 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、把平均延遲轉換為鏈路利用率的估值。根據(jù)排隊論,利用率p可表示為延遲t的函數(shù): 其中,s為分組服務時間,即平均分組長度(600bit)/鏈路速率。,(2)用以前的利用率平滑上一步的計算結果,得出平均利用率: u(n+1)=0.5p(n+1)+0.5u(n) 其中u(n)表示在取樣時刻n的平均利用率,p(n+1)表示在取樣后的下一時刻根據(jù)第1

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

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

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

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

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

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

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

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

33、送下一個窗口。接收結點收到VRPRQ后,發(fā)回已將“虛路由步調響應”VRPRS置位的分組。如果接收結點無法為另外一個窗口分配緩沖資源,則暫緩發(fā)送VRPRS,直到有足夠的資源可用。,表6―4 SNA分組中的窗口步調機制,若PC≤WS-MIN,則維持其不變,若PC＞WS-MIN,則使PC=WS-MIN。總之在任何情況下,WS均復位為WS-MIN,PC值小于等于WS-MIN。處理過程如圖6.23所示。,圖6.23 SNA虛電路窗口步調控制

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

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

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

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è)務機制要求使用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è)務機制要求使用7位順序號。P(S)字段由發(fā)送DTE按遞增的次序指定給每個發(fā)出的數(shù)據(jù)分組,P(R)字段捎帶了DTE期望從另外一端接收的下一個分組的序號。,4.分組排序 X.25能夠識別分組組成的序列,這個特點很有用

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