計算機通信網(wǎng)絡(luò)技術(shù)及應(yīng)用第4章廣域網(wǎng)

第4章計算機廣域網(wǎng)及應(yīng)用

1

【本章目標】

?一般來說，大型的公用的計算機通信網(wǎng)絡(luò)

采用的是計算機廣域網(wǎng)技術(shù)。本章首先介

紹計算機廣域網(wǎng)的概念，廣域網(wǎng)網(wǎng)絡(luò)拓撲

結(jié)構(gòu)設(shè)計以及數(shù)據(jù)交換、路由選擇、流量

控制等通信網(wǎng)絡(luò)技術(shù)，然后介紹實現(xiàn)計算

機廣域網(wǎng)的常用的通信網(wǎng)絡(luò)標準和通信系

統(tǒng)，包括X.25、DDN、幀中繼、ATM等。

?重點是計算機廣域網(wǎng)中的通信網(wǎng)絡(luò)技術(shù)

2

【本章要點】

1計算機廣域網(wǎng)概念

2網(wǎng)絡(luò)拓撲結(jié)構(gòu)及其設(shè)計，主要是干線網(wǎng)拓撲結(jié)構(gòu)

俊計

3數(shù)據(jù)交換技術(shù)：電路交換技術(shù)，報文交換技術(shù)，

分組交換技術(shù)

4計算機網(wǎng)絡(luò)中流量控制及路徑選擇

5X.25網(wǎng)絡(luò)系統(tǒng)，中國公用分組交換數(shù)據(jù)網(wǎng)

CHINAPAC

6DDN數(shù)字數(shù)據(jù)網(wǎng)絡(luò)系統(tǒng)

7幀中繼網(wǎng)絡(luò)技術(shù)

8ATM網(wǎng)絡(luò)技術(shù)

3

4.1計算機廣域網(wǎng)概述

?廣域網(wǎng)（WideAreaNetwork,簡稱WAN）

是應(yīng)用遠程通信設(shè)施，為用戶提供對遠程

用戶之間快速信息交換的系統(tǒng)。也就是說,

廣域網(wǎng)是一種用遠程通信設(shè)施將相距較遠

的獨立的計算機連接起來組成的復(fù)合系統(tǒng)。

4

?廣域網(wǎng)的特點（與局域網(wǎng)相比）

-作用范圍廣

-通信介質(zhì)非專用

-通信方式多樣

-通信管理復(fù)雜

-通信效率較低

-服務(wù)范圍廣

-網(wǎng)絡(luò)性能側(cè)重于信息的傳輸

-投資大。局域網(wǎng)投資少，不需要很高的運行費

用

5

?廣域網(wǎng)的特點總結(jié)（與局域網(wǎng)相比）

-廣域網(wǎng)的基本特征是范圍大。

-一般采用公用通信設(shè)施，需支付通信費用。

6

?通信設(shè)施

-由于廣域網(wǎng)的作用范圍大，計算機網(wǎng)絡(luò)發(fā)展初

期采用了當時已有的覆蓋面大的電話網(wǎng)和模擬

專線完成通信。隨著網(wǎng)絡(luò)技術(shù)、通信技術(shù)和網(wǎng)

絡(luò)應(yīng)用的發(fā)展，遠程通信設(shè)施也得到了很大的

發(fā)展，并且在繼續(xù)發(fā)展中。以下是目前應(yīng)用于

廣域網(wǎng)的幾種遠程通信設(shè)施。

7

?通信設(shè)施

-公用電話網(wǎng)PSTN

-模擬專線

-X.25公用分組交換網(wǎng)

-數(shù)字數(shù)據(jù)網(wǎng)DDN

-幀中繼

-甚小天線終端VSAT

-綜合業(yè)務(wù)數(shù)字網(wǎng)（ISDN)

一IP網(wǎng)

8

?通信設(shè)施

-上述遠程通信設(shè)施本身就是通信網(wǎng)絡(luò)，可以傳

送數(shù)據(jù)，除非行業(yè)專用，都向社會公眾開放。

在這些通信網(wǎng)絡(luò)的基礎(chǔ)上組建計算機廣域網(wǎng),

簡化了廣域網(wǎng)的建設(shè)。目前，廣域網(wǎng)的建設(shè)一

般采用ATM網(wǎng)和DDN網(wǎng)及幀中繼、IP網(wǎng)。

-這些通信網(wǎng)絡(luò)是如何設(shè)計，如何工作的呢？接

下來進行深入的了解。

9

4.2網(wǎng)絡(luò)拓撲結(jié)構(gòu)及其設(shè)計

?4.2.1網(wǎng)絡(luò)拓撲設(shè)計的基本概念

?4.2.2本地接入網(wǎng)的拓撲設(shè)計

?423干線網(wǎng)的設(shè)計

10

4.5.1網(wǎng)絡(luò)拓撲設(shè)計的基本概念

給定用戶終端的位置,給定吞吐量、時延和可靠性要求,設(shè)

計網(wǎng)絡(luò)的結(jié)構(gòu)，進行流量和容量分配，使費用最小。

設(shè)全網(wǎng)共有N個節(jié)點；則有N(N-l)/2個可能的點到

點傳輸鏈路，這些鏈路的每一種組合都是一種網(wǎng)絡(luò)

結(jié)構(gòu)。故總的結(jié)構(gòu)數(shù)為：

2N(N-1)12

11

基本步驟

結(jié)構(gòu)微調(diào)

N

12

干線網(wǎng)一般為分布式結(jié)構(gòu)，本地接入網(wǎng)一般為星形和總線形“

干線網(wǎng)的描述

干線，比喻很重要的路線，一般指城市公共交通線

路網(wǎng)中的主要線路，江河或溪流的主河道等。

干線網(wǎng)：網(wǎng)絡(luò)中的主要線路組成的網(wǎng)絡(luò)。核心網(wǎng)。

例如：校園干線網(wǎng)，CHINADDN干線網(wǎng)

此類概念還有骨干網(wǎng)。

骨干：比喻在總體中起主要作用的人或事物。

目前我國4大骨干網(wǎng)：中國公用計算機互聯(lián)網(wǎng)

(CHINANET)>中國金橋信息網(wǎng)(CHINAGBN)、

中國教育和科研計算機網(wǎng)(CERNET)、中國科技網(wǎng)

(CSTNET)o

14

接入網(wǎng)的描述

?接入網(wǎng)是指干線網(wǎng)到用戶終端之間的所有設(shè)備。

其長度一般為幾百米到幾公里，因而被形象地稱

為“最后一公里，

?由于骨干網(wǎng)一般采用光纖結(jié)構(gòu)，傳輸速度快，因

止匕，接入網(wǎng)便成為了整個網(wǎng)絡(luò)系統(tǒng)的瓶頸。

?接入網(wǎng)的接入方式包括銅線（普通電話線）接入、

光纖接入、光纖同軸電纜（有線電視電纜）混合

接入、無線接入和以太網(wǎng)接入等幾種方式。

15

拓撲設(shè)計的一般方法

(1)干線網(wǎng)設(shè)計：

?根據(jù)可靠性要求設(shè)計連接結(jié)構(gòu)。

?根據(jù)時延和吞吐量要求分配各線路容量。

(2)本地接入網(wǎng)

?集中器選址

?用戶點分配

?終端布局

(3)具體方法：優(yōu)化決策問題

?建立數(shù)學模型。

?理論分析或計算機模擬求最佳解。

16

422本地接入網(wǎng)設(shè)計

由于不同的集中器選址方案對應(yīng)于不同的用戶點

分配方案故其步驟如下：

設(shè)有m個可供集中器選擇的地址，加IMP共m+1

個，可供選擇的方案共有

2m(m+l)/2

按照選址個數(shù)逐步增加或逐步減少的順序，依次計

算集中器個數(shù)相等時的最小費用，并將后一次算得

的費用與前一次比較，若小于前一次則繼續(xù)算；否

則，前一次的方案為最佳方案。

17

012................................mm+1

顯然這必須掌握在固定集中器位置情況下進行

用戶點分配使費用最小的方法。

18

453干線網(wǎng)設(shè)計

1、設(shè)計過程

(1)根據(jù)可靠性設(shè)計結(jié)構(gòu)；

(2)根據(jù)時延和吞吐量要求按費用最小準則，

分配業(yè)務(wù)流量和鏈路容量；

(3)計算時延和吞吐量，若不滿足要求則重新

開始，若滿足要求則

(4)計算費用

(5)擾動優(yōu)化.

19

2、結(jié)構(gòu)設(shè)計

?邊連通度

?節(jié)點連通度

邊連通度為2,節(jié)點連通度為1的網(wǎng)絡(luò)

20

初始連接結(jié)構(gòu)的生成：鏈路赤字法

若可靠性要求是使網(wǎng)絡(luò)圖的點連通度大于等于k+i,采用鏈路赤字法的想法就是

生產(chǎn)一個圖度數(shù)等于k+l的初始拓撲。

初始連接結(jié)構(gòu)的生成步驟如下：

?(1)給所有節(jié)點隨機地順序編號，對每個節(jié)點賦予

個k+1的鏈路赤字。

?(2)選擇一個赤字最大的節(jié)點，若有多個節(jié)點赤字都

是最大，選序號小的那個X。

?(3)在無邊和X直接相連的節(jié)點中選擇一個赤字最大

的節(jié)點Y,若有多個可選，可以按照某種意義選擇一個

最合適的節(jié)點：比如與X距離最近、或者信息流量最大

等，若還有多個可以選擇，選序號小的那個。

?(4)連接XY,并將X和Y的鏈路赤字各減去L

?重復(fù)(2)、(3)、(4),直到所有節(jié)點的鏈路赤字

值沒有正數(shù)為止。

3、流量分配

?根據(jù)初始拓撲，進行流量分配，也就是說,

對端到端的信息流選擇路徑。路徑的選擇

可以采用Dijkstra算法來找到最短通路。

22

網(wǎng)絡(luò)圖的Dijkstra算法

?也稱最短路徑算法，基本思路：前向搜索

符號定義:

N=網(wǎng)絡(luò)中所有節(jié)點的集合

?S=源節(jié)點

?M=已由算法歸并的節(jié)點的集合

?L(i,j)=節(jié)點i與j之間鏈路的權(quán)值；若兩個節(jié)

點間沒有直接連接則為8

-c(n)=算法求得的當前從S到n的最少花費

路由的花費

23

Dijkstra算法算法步驟

1.初始化

?M={S}

?C(n)=L(S,n)fornwS

?2.從軍在M中的相鄰節(jié)點中找出一個具有和節(jié)點S的最

少花費路由的節(jié)舄并且把該節(jié)點規(guī)約進M也可以表

不如下：

?尋找wcM,使得C(w)=MinC(j)把w加入到M中。/w)o

?3.更新最少花費路徑

?C(n)=min[C(n),C(n)+L(w,n)]對所有ngM。

?如果后一項為最小值，則從S到n的路徑變?yōu)閺腟到w的

路徑再加上從w到n的鏈路。

?4.重復(fù)步驟2和3,直到M=N。

整個矗署颼懿麒都雕承繇震疆舞器

最佳路由已經(jīng)確定，直至M擴大到所有布點。24

in

CN

(

S0

8*

母W

6

R

s0

Ks

(

o<

c

e?

i

s

x

a

:2?端對端信息量和路由

端點123456

縣虧

1094174

12123126415156

2908324

212326426526

3480332

321323435356

4133034

46214624343546

5723305

515625353456

6442450

651626536465

26

4、容量計算（容量分配）

一種最簡單的方*

1信道XiCi

法是均勻分配。

1121420

一種方法是按比2231220

例分配。鏈路的334610

容量是與鏈路上4151120

信息流量成正比。5561350

664810

還有可能比較隨7261020

意分配，例如：853820

27

4、容量計算（續(xù)）

較好的方法：根據(jù)延遲時間限制要求，即通過網(wǎng)

絡(luò)的平均延遲時間小于等于某個給定值，通過延

遲時間的限定值確定各鏈路的容量。

F=f（Ci,Xi,r,T*）

F：總費用；Ci：鏈路i的容量；Xi：鏈路i的

業(yè)務(wù)量；「：總業(yè)務(wù)吞吐量；T*：網(wǎng)絡(luò)平均時延

（限定值）。

通過F對Ci的多元函數(shù)的極值即可得到容量分配結(jié)

果。

28

4、容量計算(續(xù))

一條鏈路的平均時延Ti=l/(PCiXi),其中1/口

是以比特為單位的報文分組平均長度；Ci是該鏈

路的容量，單位是比特/秒；入i是平均流量，單

位是分組/秒。對所有的每條鏈路上的時延Ti,可

以計算出最大時延，按每條鏈路上的信息量為權(quán)

進行加權(quán)平均，就可以求出分組通過該網(wǎng)絡(luò)中一

條鏈路的平均時延T=E(入i*Ti)/E(Xi)o

TWT*

一條鏈路的費用Fi=di*Ci+Xi,簡單地，F(xiàn)i=Ci

總費用F=LFi

當關(guān)于Ci的多元函數(shù)F取最小值時，Ci即為所求。29

3

每段鏈路的平均延遲計算舉例（13=800比特

/：/分組)

毫

€i?信j道入i（分CiUTi

秒

組/秒(Kbps)Ci

11214202591

22312202577

33461012.5154

41511202571

556135062.520

66481012.5222

72610202567

8538202559

82C=170Kbpsso

T=E(Xi*Ti)/E(Xi)=114毫秒，非最優(yōu)！!

5、根據(jù)第4步得到的容量，計算時延和吞吐

1=1t,若不滿足要求則重新開始，若滿足要

求則計算網(wǎng)絡(luò)建設(shè)的費用

?6、擾動優(yōu)化，以期得到更優(yōu)的結(jié)構(gòu)。

31

4.3數(shù)據(jù)交換技術(shù)

?4.3.1電路交換技術(shù)

?4.3.2報文交換技術(shù)

?4.3.3分組交換技術(shù)

?4.3.4幾種交換方式的比較

32

4.3數(shù)據(jù)交換技術(shù)

這是網(wǎng)絡(luò)通信的

特點之一。

數(shù)據(jù)交換技術(shù)是

■

=

指在任意拓撲結(jié)0

_

構(gòu)的通信網(wǎng)絡(luò)中,

——

通過網(wǎng)絡(luò)節(jié)點的一

實現(xiàn)任意兩個節(jié)M

點之間數(shù)據(jù)傳輸

的技術(shù)。

33

4.3數(shù)據(jù)交換技術(shù)

34

4.3.1電路交換技術(shù)圖示

35

電路交換舉例

?A和B通話經(jīng)過四個交換機

?通話在A到B的連接上進行

36

電路交換舉例

?C和D通話只經(jīng)過一個本地交換機

?通話在C到D的連接上進行

交

換

機

中

繼線

交

換

aD機

戶

線

用

中

A3繼線B

交CD

換

機cb

Cr

Ccp

Cb

交

c換機b

P

D

戶線

用

D

37

432報文交換技術(shù)

其傳輸方式為“存儲——轉(zhuǎn)發(fā)”方式。存儲轉(zhuǎn)發(fā)原理如圖

1-30所示。

信

息

緩

處

沖

輸理輸

存;出

和

入、儲

轉(zhuǎn)

發(fā)

圖1-30存儲轉(zhuǎn)發(fā)原理圖

38

報文交換技術(shù)圖示

39

4.3.3分組交換技術(shù)

?每一個數(shù)據(jù)段前面添加上首部構(gòu)成分組。

------------------報文-----------------

數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)

分組2

Z-----------------------------------X

分組3

__________________

口/_______________________

請注意：現(xiàn)在左邊是‘前面”

40

分組交換的原理

?分組交換網(wǎng)以“分組”作為數(shù)據(jù)傳輸單元。

?依次把各分組發(fā)送到接收端（假定接收

端在左邊）。

分組1

Z----------------、

■~~-

--------------分組2

----------------------------------_

Z-_______________

■~贏~-

---------分組3

_____________________人____________________

■~~i-

41

分組交換的原理

?接收端收到分組后剝?nèi)ナ撞窟€原成報文。

分組1

■~S~-

--------------分組2

，---------------------------------------------------------------------------S

--------------分組3

--------------------------------__________________________

Z_______________________

收到的數(shù)據(jù)

42

分組交換網(wǎng)的示意圖

結(jié)點交換機

主機

叱向也發(fā)送分組

向H5發(fā)送分組

分組交換網(wǎng)〕

433分組交換技術(shù)

?1.數(shù)據(jù)報分組交換技術(shù)

數(shù)據(jù)報分組交換(DatagramSwitching)

是一種面向無連接的分組交換，當發(fā)送端發(fā)

送報文時，先將報文拆成若干分組，每個分

組攜帶地址信息和分組序號，選擇不同的路

徑傳輸?shù)侥康慕Y(jié)點。

44

4.3.3分組交換技術(shù)

?2.虛電路分組交換技術(shù)

?虛電路分組交換(VirtualCircuitSwitching)

是一種面向連接的分組交換，在發(fā)送分組前，

發(fā)送方與接收方預(yù)先要建立邏輯連接，即建

立一條虛電路，每個結(jié)點不必為分組作路由

選擇，所有分組都沿虛電路傳輸。

45

虛電路分組交換過程

46

三種交換過程的對比

47

4.3.4幾種交換方式的比較

數(shù)據(jù)包分組虛電路分組交

電路交換報文交換

方式特性交換換

傳輸通路性質(zhì)物理邏輯邏輯邏輯

通路的可用性專用共享共享共享

數(shù)據(jù)傳輸單元報文報文分組分組

通路建立要求呼叫建立不要求建立不要求建立要求呼叫建立

通路的維持通信期間維持不維持不維持通信期間維持

存儲一個分

節(jié)點存儲不要求存儲一個報文存儲一個分組

組

報文存儲轉(zhuǎn)發(fā)分組存儲轉(zhuǎn)分組存儲轉(zhuǎn)發(fā)

節(jié)點時延幾乎無時延

時延發(fā)時延時延

增加分組時有呼叫阻塞

過荷適應(yīng)性有呼叫阻塞增加報文時延

延增加分組時延

鏈路帶寬利用固定帶寬占用動態(tài)使用動態(tài)使用動態(tài)使用

48

幾個重要概念

-虛電路

?數(shù)據(jù)報?虛電路服務(wù)

?虛電路分組交換技術(shù)

?數(shù)據(jù)報服務(wù)

?數(shù)據(jù)報分組交換技術(shù)

?分組交換技術(shù)?虛電路方式

?報文交換技術(shù)?數(shù)據(jù)報方式

?電路交換技術(shù)

49

關(guān)于數(shù)據(jù)交換速度

?目前常用的數(shù)據(jù)交換技術(shù)有電路交換技術(shù)、

報文交換技術(shù)、分組交換技術(shù)和其它一些

高速的數(shù)據(jù)交換技術(shù)。

50

4.4計算機網(wǎng)絡(luò)中流量控制及路徑擇

?4.4.1計算機網(wǎng)絡(luò)中流量控制技術(shù)

?442計算機網(wǎng)絡(luò)中路徑選擇方法

51

4.4.1計算機網(wǎng)絡(luò)中流量控制技術(shù)

52

4.4.1計算機網(wǎng)絡(luò)中流量控制技術(shù)

?擁塞：當網(wǎng)絡(luò)某部分或整個網(wǎng)絡(luò)中的報文量超過

一定值時，引起通過能力下降和時延增大的現(xiàn)象。

這是網(wǎng)絡(luò)通信特有的一種現(xiàn)象。

■擁塞控制的目的主要是提高網(wǎng)絡(luò)的吞吐率，即單

位時間傳輸?shù)膱笪牧俊?/p>

?流量控制是指通信收發(fā)雙方的通信速率和處理能

力的匹配，使得接收方能夠來得及處理接收到的

數(shù)據(jù)。

53

4.4.1計算機網(wǎng)絡(luò)中流量控制技術(shù)

計算機網(wǎng)絡(luò)流量控制就是要限制網(wǎng)絡(luò)各個部分的通信量，計

算機網(wǎng)絡(luò)中流量控制作用分散在網(wǎng)絡(luò)的各級，如圖4-4所示。

鏈路級

54

?各級擁塞控制的目的與主要方法

?1.鏈路級：防止兩個結(jié)點之間存儲一轉(zhuǎn)發(fā)緩沖區(qū)的擁塞。

?(1)當緩沖區(qū)或隊列占用達到一定限度時便停止接收報

文；

?(2)對經(jīng)過鏈路數(shù)不同的報文預(yù)留不同的緩沖區(qū)，對于接

近目的地的報文預(yù)留越大的緩沖區(qū)；

?(3)在每一結(jié)點對每一虛電路設(shè)置一個緩沖區(qū)的限定值。

?2.網(wǎng)絡(luò)端一端之間：防止網(wǎng)絡(luò)出口處緩沖區(qū)超限

?(1)滑動窗口控制

?(2)窗口末給ACK

?(3)SNA窗口控制

?3.網(wǎng)絡(luò)入口級：限制進入網(wǎng)絡(luò)的外來報文

?(1)許可證方式

?(2)輸入緩沖區(qū)限制方式

?(3)采用阻塞報文

?4.傳輸級：防止主機接收緩沖區(qū)溢出，防止往返延遲抖動太大

4.4.2計算機網(wǎng)絡(luò)中路徑選擇方法

這是網(wǎng)絡(luò)通信的特點

之一

路徑選擇方法（路由算

法）的目的，找到一條

從源到目的地的一條

“最好”路徑。

而“最好”路徑常常是

指具有最小花費的路

徑。

?通常稱為最短路徑。

56

分組交換網(wǎng)的示意圖

4.4.2計算機網(wǎng)絡(luò)中路徑選擇方法

分類：

?1.確定式路徑選擇(靜態(tài)路由選擇)

?(D泛送式

?(2)固定式

?(3)概率分配方式

?(4)基于流量的路由選擇

?2.適應(yīng)式路徑選擇(動態(tài)路由選擇)

?(D集中式

?(2)孤立式

?(3)混合式

?(4)分布式

58

泛送式

一個結(jié)點收到一個報文后,

隨即向相鄰的其他結(jié)點轉(zhuǎn)

發(fā)出去，直至到目的結(jié)點。

由于每個結(jié)點都是向J

圍的結(jié)點發(fā)送，故名泛送

式，網(wǎng)中會有許多多余的

報文在傳送，也叫擴散法O

為了防止報文在網(wǎng)中迂回傳送,常常給報文中加

一個壽命計數(shù)器，開始時令其等于網(wǎng)絡(luò)最遠距

離（路徑）中鏈路數(shù)，報文在傳送中每到達一

個結(jié)點計數(shù)器減1,當計數(shù)器為零時，報文即停

止繼續(xù)傳送。

59

泛送式路徑選擇方法簡單，但因報文重復(fù)量

大，只用于網(wǎng)絡(luò)負載很小或可靠性要求很

高的情況。這種方式的另一個特點是報文

從源結(jié)點到達目的結(jié)點所需的時間短。

泛送式可被用來分發(fā)信息、判斷可達性、找

到最短路徑

60

固定式路由選擇

■,

囤定式路由選擇：每一結(jié)點有一路徑表（路由表）,

路徑表由某種算法（例如最短路徑算法）求得,

確定后在運行中不再變。

路由表的每一項記錄著為了到達某個目的節(jié)

點而選擇的下一節(jié)點或鏈路，而不是記

錄到該目的節(jié)點的所有中間節(jié)點。

61

6

Bc

終進線站點路徑值

A

點BB2

IcD3

DDD1

ED2

FD4

(a)網(wǎng)絡(luò)(b)站點A的路徑表

62

報文到達一個結(jié)點后，根據(jù)目的地址查表，即可確

定應(yīng)采取哪條出線轉(zhuǎn)發(fā)報文。

?優(yōu)點：簡單，適合于在一個負載穩(wěn)定、拓撲變化

不大的網(wǎng)絡(luò)中運行。固定路由方法是一種使用較

多的簡單方法。

■缺點：靈活性較差，無法對網(wǎng)絡(luò)的擁塞和故障作

出反應(yīng)。63

概率分配方式

也稱隨機路由選擇算法，當分組到達節(jié)點

后，隨意選擇一條輸出線路進行轉(zhuǎn)發(fā)。

概率分配方式是每條出線被采用的概率事

先按一定算法加以確定，這一概率分配

在運行中也是固定的，概率分配方式可

獲得較小的平均路徑時延。

64

63

B

5

2

2

1

1

I)1E

3

?問題1：由A到F,在A,其路徑怎樣選擇?

?問題2:A節(jié)點的路由表是怎樣的？

65

概率數(shù)的分配考慮到了網(wǎng)絡(luò)的拓撲與容量,

但是還是有隨機性的，而且可能分組會一

直在網(wǎng)絡(luò)中傳遞，從而無法到達目的地。

由于隨機路由算法實際選擇的路由不一定

是最佳路由，因此增加了不必要的負載，

而且分組傳輸延遲也不可預(yù)料，所以這種

方法很少使用。

66

基于流量的路由選擇

基于流量的路由選擇算法(flow-basedrouting)就是

一種既考慮拓撲結(jié)構(gòu)又兼顧負載的靜態(tài)路由算法。

?其基本思路是：對某一給定的線路，如果已知負載量

與平均流?，那么可以根據(jù)排隊論的知識計算出該線

路上的平均分組延遲。由所有的線路平均延遲，可直

接計算出流量的加權(quán)平均值，從而得到整個網(wǎng)絡(luò)的平

均分組延遲。這樣找出網(wǎng)絡(luò)最小平均延遲就可以實現(xiàn)

最優(yōu)路由選擇。

-線路上的平均分組延遲T=1/(UC-入)其中1/口是以

比特為單位的報文分組平均長度；C是以該鏈路的容量,

容量單位是比特/秒；入是平均流量，單位是分組/秒。

67

孤立路由選擇

孤立式是將路徑確定權(quán)交給各結(jié)點，由各結(jié)點自

己決定的方式。例如：結(jié)點收到報文后，看哪

個出線的等待排隊最短，就將報文交哪個出線

發(fā)送?；蛘卟捎卯斍暗却犻L與固定式路徑表

相結(jié)合的方式，當隊長不超過一定值時按固定

式路徑表，否則按隊長；或者采取隊長與一個

權(quán)重系數(shù)之和為最小作為選擇條件。

總之，這種方式是只就本結(jié)點感受到的負載變化

來確定報文路徑，不與其他結(jié)點交換運行狀態(tài)

宿急。

68

2

9<

集中路由選擇

?集中式路由選擇：網(wǎng)絡(luò)中有一個路徑控制中心，

網(wǎng)絡(luò)中各結(jié)點的運行情況（隊長、近期報文傳送

量、相鄰的結(jié)點）定期送往控制中心，由控制中

心根據(jù)全網(wǎng)絡(luò)當前的實際情況計算出各結(jié)點的路

徑選擇方案，送往各個結(jié)點，修改各結(jié)點的路徑

表。

?這種方式的缺點是控制中心出現(xiàn)故障時影響到全

網(wǎng)工作，靠近控制中心的鏈路上的控制報文量很

大，在遠離控制中心的結(jié)點上路徑表的修改緩慢

70

分布式路由選擇

?分布式路由選擇：將路徑選擇權(quán)分散于各結(jié)點，

但又不像孤立式只根據(jù)本結(jié)點的情況，而是考慮

到其它結(jié)點的情況來修改路徑表。為了修改路徑

表，各結(jié)點之間需要定期傳送運行狀態(tài)的信息。

?分布式路由選擇根據(jù)來自于相鄰節(jié)點的信息，其

依據(jù)是每個節(jié)點知道到所有鄰居的花費O

?分布式路由選擇算法得到了廣泛的使用，具體分:

-距離向量路由選擇算法

-鏈路狀態(tài)路由選擇算法

71

分布路由選擇

?距離向量路由算法：

-每個節(jié)點都知道直接連接的鏈路花費(距離)，根據(jù)從

相鄰節(jié)點了解到的到目的地的路徑花費來計算。

-思路依據(jù)：

由K至D的最短路徑T(K,D)min

=由長經(jīng)K的所有鄰結(jié)點J至D的最短路徑MinT(K,D,J)

而T(K,D,J)=T(J,D)min+L(K,J)

其中：T(K,D,J)為由K經(jīng)結(jié)點J而至D的最短路徑

T(x,y)min為由x至y的最短路徑；

L(x,y)為由x至y的鏈路距離

-這是遞歸、分布式的路由計算方法

72

63

B

5

IF

1

I)1------(E

3

?D知道到A的距離1,到B、C、E的距離2、3、1

?E知道到C的距離1,到A、D、F的距離3、1、2

?D與E交換以上信息后，結(jié)果是？

73

無窮計數(shù)問題

-距離向量路由算法會遇到無窮計數(shù)問題。算法

的缺陷：對好消息反應(yīng)迅速，對壞消息反應(yīng)遲鈍。

ABCDE

ABCDE

1234初始

OOOOOO00初始

3234第1次交換后

18OO8第1次交換后

3434第2次交換后

12OO8第2次交換后

5454第3次交換后

1238第3次交換后

5656第4次交換后

1234第4次交換后

7676第5次交換后

7878第6次交換后

(a)

OOOOOO8

(b)

無限計算問題

74

鏈路狀態(tài)路由

?鏈路狀態(tài)路由

-每個節(jié)點了解全局網(wǎng)絡(luò)的拓撲和鏈路花費。

-每個節(jié)點最初知道相鄰鏈路的負載情況，并且

擴散給網(wǎng)絡(luò)中的所有節(jié)點

-每個節(jié)點都了解整個網(wǎng)絡(luò)的拓撲信息，從而按

照Dijkstra算法計算出到每個目的地的最短路

由

-鏈路狀態(tài)路由收斂更快，更加穩(wěn)定，更加復(fù)雜

75

確定式路徑選擇與動態(tài)路由選擇比較

?確定式路徑選擇特點：不根據(jù)實際測量的或估計

的網(wǎng)絡(luò)當前通信量和拓撲結(jié)構(gòu)來作路由選擇,

路由選擇是按照某種固定的規(guī)則、使用初始靜

態(tài)信息來進行的，故又稱為靜態(tài)路由、非自適

應(yīng)(non-adaptive)路由。

?應(yīng)用特點：路由很少變化，由網(wǎng)管人員人工配

置

-常用于規(guī)模很小的網(wǎng)絡(luò)。但有一個節(jié)點故障時沒法

自動發(fā)現(xiàn)和調(diào)整路由，需要人工干預(yù)

76

?動態(tài)路由特點：路由器之間交換路由信息，根

據(jù)它所了解到的網(wǎng)絡(luò)信息計算最佳路由，以設(shè)

法適應(yīng)網(wǎng)絡(luò)流量、拓撲的變化。現(xiàn)代計算機網(wǎng)

絡(luò)更多地使用動態(tài)路由方式。

盡管動態(tài)方式有很多的優(yōu)點，在設(shè)計時必須考慮

到：

?路由選擇算法非常復(fù)雜，故可能增加網(wǎng)絡(luò)節(jié)點

的處理負擔。

?大多數(shù)情況下，動態(tài)方式會使用別的節(jié)點來的

狀態(tài)信息來進行路由選擇，因此會增加網(wǎng)絡(luò)中

的負載。

?一個動態(tài)方式算法有時會因反應(yīng)太快而引起振

蕩，或者反應(yīng)太慢而起不到作用。77

3.層次路由、策略路由

?層次路由選擇，即將整個網(wǎng)絡(luò)分成若干個

區(qū)域，各個區(qū)域內(nèi)的節(jié)點只考慮本區(qū)域內(nèi)

的路由，而區(qū)域之間的路由選擇由各個區(qū)

域中某幾個節(jié)點(通常稱為邊界路由器)

負責完成。

?在實際實施路由選擇時，往往還需要從策

略上進行考慮，即所謂策略路由，有時更

多地稱為篡于策略(policies-based)的路

由O

78

4.5X.25網(wǎng)絡(luò)系統(tǒng)

?4.5.1X.25網(wǎng)絡(luò)概述

?452X.25通信協(xié)議

?4.5.3中國公用分組交換數(shù)據(jù)網(wǎng)

CHINAPAC

79

?4.5.1X.25網(wǎng)絡(luò)概述

-X.25建議：“工作在公用數(shù)據(jù)網(wǎng)上以分組方式工作的數(shù)

據(jù)終端設(shè)備DTE和數(shù)據(jù)電路端接設(shè)備DCE之間的接

□o”

-X.25是CCITT的一個建議，符合X.25建議的接口稱為

X.25接口，以X.25接口接入的數(shù)據(jù)通信網(wǎng)絡(luò)稱為X.25

網(wǎng)。

-X.25標準分物理層、數(shù)據(jù)鏈路層和分組層3個協(xié)議，分

別對應(yīng)于ISO/OSI參考模型的低3層。

80

?X.25網(wǎng)的構(gòu)成

-X.25網(wǎng)的基本結(jié)構(gòu)如圖4.1所示。通常采用兩級

結(jié)構(gòu)，根據(jù)業(yè)務(wù)流量、流向和地區(qū)設(shè)立一級和

二級交換中心。

-分組交換網(wǎng)由分組交換機、網(wǎng)絡(luò)管理中心、遠

程集中器與分組拆裝設(shè)備、分組終端和傳輸線

路等基本設(shè)備組成。

81

NMC集中器

圖4-1X2胸的基本結(jié)構(gòu)圖

82

①分組交換機。其作用是轉(zhuǎn)接、傳送接入本節(jié)點

的各類計算機、終端和鏈路間的信息。

②網(wǎng)管中心（NMC）。其作用使全網(wǎng)有效、協(xié)調(diào)地

運行，更好地發(fā)揮網(wǎng)絡(luò)性能，同時為網(wǎng)絡(luò)管理者

及用戶提供友好與方便的服務(wù)。

③分組終端。接入分組交換網(wǎng)的數(shù)據(jù)通信終端設(shè)

備,具有X.25協(xié)議接口O

④分組裝拆設(shè)備（PAD）。把非分組終端的簡單接

口規(guī)程與X.25協(xié)議相互轉(zhuǎn)換。

⑤遠程集中器（RCU）。對用戶終端進行遠程集

中。

83

452X.25通信協(xié)議

?X.25建議是X.25網(wǎng)的主要協(xié)議，它規(guī)定DTE與DCE之間

的接口，在本地DTE和遠程DTE之間提供了一個全雙工

的、同步的透明信道，使得本地DTE無須知道遠程DTE

的詳盡特性即可通信。

?DTE代表數(shù)據(jù)終端設(shè)備，是指接入網(wǎng)絡(luò)的設(shè)備，這些設(shè)

備可以是終端、前臺設(shè)備、主機、PC、執(zhí)行PAD功能

的交換機或集中器。DCE是指DTE所連接的入口或交換

節(jié)點，可以是調(diào)制解調(diào)器、線路耦合器以及其它設(shè)備。

?通信各層之間的信息關(guān)系如下圖示：

84

X25定義

X.25的層次關(guān)系

85

?452X.25通信協(xié)議

?X.25第一層

CCITT的X.21建議規(guī)定了在公用數(shù)據(jù)網(wǎng)上為同步工作的

DTE與DCE之間的通用接口。

?一般的接口特性包括以下幾方面：機械性接口;電氣性接口;

功能性接口;過程性接口。

86

452X.25通信協(xié)議

?X.25的第二層

本層也稱為幀層，與點對點數(shù)據(jù)鏈路控制規(guī)

程相對應(yīng)。

X.25的第二層選用了HDLC中的異步平衡方

式，簡稱LAPB。

規(guī)程要素與HDLC相同，幀格式符合HDLC

要求，幀中某些字段的內(nèi)容體現(xiàn)了X.25的特色。

87

?452X.25通信協(xié)議

■用戶數(shù)據(jù)以信息幀在DTE和DCE之間傳送，分組作為信

息幀中的信息字段，X.25的幀格式如圖所示

|F|A|C|分組數(shù)據(jù)|FCS|F

地址只有兩個值(DTE:A:3\DCE:B:1):DCE發(fā)送地址為A的

命令，接收地址為A的響應(yīng)；DTE發(fā)送地址為B的命令，接收地址為B的

響應(yīng)

控制字段可以有16位

FCS計算可以考慮標志字段

多鏈路規(guī)程

88

4.5.2X.25通信協(xié)議

■X.25第三層

X.25第三層也叫分組層，這一層是X.25的

核心，它規(guī)定了分組層DTE/DCE接口即如

何與對方DTE相連的DCE進行分組通信。包

括虛電路業(yè)務(wù)規(guī)程、分組格式、任選的用戶

補充業(yè)務(wù)的協(xié)商、流量控制及差錯恢復(fù)等內(nèi)

容。

89

X.25第三層

■虛電路

在X.25網(wǎng)中，兩個DTE之間傳輸數(shù)據(jù)的一個聯(lián)結(jié)

叫做虛電路。

圖4-11DTE之間的虛電路

90

虛電路邏輯電路

兩個DTE之間端到端的連接DTE與DCE之間的局部實體

兩個DTE可以使用不同邏輯電路只有一條虛電路能夠被指定到邏

輯電路上

虛電路是建立后才存在，但永久邏輯電路總是存在的，或是被分

虛電路固定存在配到虛電路上或處于準備狀態(tài)

類似于先進先出排隊類似一個I/O口

虛電路與邏輯電路的比較

91

X.25的層次關(guān)系

92

?X.25第三層

■網(wǎng)絡(luò)地址

網(wǎng)絡(luò)地址（DNA）用來區(qū)別DTE接入網(wǎng)絡(luò)的線

路，同時也區(qū)別了DTE。

標準：X.121編號制度的建議

示例：046030112345678

■用戶補充業(yè)務(wù)

X.25網(wǎng)將虛電路有關(guān)的通信參數(shù)作為用戶補充

業(yè)務(wù)由用戶自己選擇。

例如：擴展的幀