計(jì)算機(jī)通信包交換

高華廣學(xué)出版社

第5章計(jì)算機(jī)通信一包交換

-包交換技術(shù)一數(shù)據(jù)報(bào)和虛電路

?差錯(cuò)檢測(cè)

?差錯(cuò)控制

?流量控制

?路由選擇

?擁塞控制

高華廣學(xué)出浙?社

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

包交換技術(shù)(packetswitching)

數(shù)據(jù)報(bào)方式:為每個(gè)包單獨(dú)選擇路徑

X

高華廣學(xué)出浙?社

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

包交換技術(shù)(packetswitching)

虛電路方式:在源和目標(biāo)間先建立路徑

高華廣學(xué)出版社_

2廠fFJ/zteayf1'?N/?A

包交換技術(shù)(packetswitching)

—數(shù)據(jù)報(bào)和虛電路

?每個(gè)包獨(dú)立傳遞，結(jié)點(diǎn)為包逐個(gè)選擇路徑，這

種包稱(chēng)為數(shù)據(jù)報(bào)(datagram)o

?虛電路(virtual-circuit),即邏輯連接(logical

connection)是在主機(jī)之間事先建立的一條傳輸

路徑，如X?A?B?E?Y,以后X和Y之間的包就在

此路徑傳輸。它類(lèi)似線路交換網(wǎng)中的一條電路。

但這條路徑不是專(zhuān)用的，它是和其它包、其它

連接共享的。包在每個(gè)結(jié)點(diǎn)仍要作短暫存儲(chǔ)，

和其它包一起放在輸出隊(duì)列轉(zhuǎn)發(fā)。

清華廣學(xué)出版社-

;二ZJ7/上W夕A"REFF二

包交換技術(shù)(packetswitching)

—數(shù)據(jù)報(bào)和虛電路方式比較

?數(shù)據(jù)報(bào)方式更原始，更靈活，可以繞過(guò)

擁塞區(qū)和故障點(diǎn)，所以具有健壯性.??。

但數(shù)據(jù)報(bào)會(huì)錯(cuò)序；

■虛電路方式保證包的傳遞順序，容易實(shí)

現(xiàn)差錯(cuò)控制；

?兩個(gè)主機(jī)交換大量數(shù)據(jù)時(shí)，虛電路方式

更有效，若只交換少量包，數(shù)據(jù)報(bào)方式

更快。

高華方學(xué)出版社

差錯(cuò)檢測(cè)

?奇偶校驗(yàn)(paritycheck)

?校驗(yàn)和(checksum)

?循環(huán)冗余校驗(yàn)碼CRC(CyclicRedundancy

Check)

?差錯(cuò)檢測(cè)的局限性

高華十學(xué)出版社

奇偶校驗(yàn)

?奇偶校驗(yàn)：在所發(fā)送的每個(gè)字符后面添加一個(gè)

校驗(yàn)位，稱(chēng)為奇偶位(paritybit)。

?偶校驗(yàn)：字符中有奇數(shù)個(gè)1則添加1，有偶數(shù)個(gè)1

則添加0。如1110010添加0成為11100100o

字符連同校驗(yàn)位中1的總數(shù)為偶數(shù)。

?奇校驗(yàn)：字符中有奇數(shù)個(gè)1則添加0,有偶數(shù)個(gè)1

則添加1。如1110010添加1成為11100101o

字符連同校驗(yàn)位中1的總數(shù)為奇數(shù)。

■奇偶校驗(yàn)?zāi)軝z測(cè)什么差錯(cuò)？

能檢測(cè)奇數(shù)位差錯(cuò)，不能檢測(cè)偶數(shù)位差錯(cuò)。

唐華十學(xué)出版畫(huà)

校驗(yàn)和

?有的協(xié)議層在包頭設(shè)置一個(gè)校驗(yàn)和字段。

?若校驗(yàn)和是16位的字段，發(fā)送方在發(fā)送前將待

校驗(yàn)的字符串分成若干長(zhǎng)度為16位的段，每個(gè)

段看成二進(jìn)制數(shù)，進(jìn)行相加等運(yùn)算，結(jié)果填入

校驗(yàn)和字段。

?校驗(yàn)和可以檢測(cè)一位錯(cuò)誤，一位以上的錯(cuò)誤不

一定能檢測(cè)出來(lái)。

?校驗(yàn)和是較簡(jiǎn)單的差錯(cuò)檢測(cè)，是計(jì)算代價(jià)和檢

測(cè)能力之間的一種權(quán)衡。

循環(huán)冗余校驗(yàn)碼CRC

一附加幀校驗(yàn)序列FCS

CRC常用在數(shù)據(jù)鏈路層，附加的校驗(yàn)序列稱(chēng)為

幀校驗(yàn)序列FCS(FrameCheckSequence),它是

基于CRC計(jì)算的，這里只介紹CRC,記為F

左位〃位

M

高華十學(xué)出版社

循環(huán)冗余校驗(yàn)碼CRC

一幀校驗(yàn)CRC碼F的計(jì)算

?M表示被發(fā)送的位串，設(shè)為左位。

尸是什1位的標(biāo)準(zhǔn)位串，r<k,

M、尸都看作二進(jìn)制數(shù)。

?當(dāng)用尸除時(shí)得商。和余數(shù)A,余數(shù)

A就作為幀校驗(yàn)CRC碼R它至少比尸

少一位，可看作〃位。網(wǎng)中傳輸?shù)氖荰,

T看作二進(jìn)制數(shù)，則

T=2rM+F=(QP+R)+R

高華大學(xué)出版社

循環(huán)冗余校驗(yàn)碼CRC—校驗(yàn)的原理

?這里的算術(shù)運(yùn)算以2為模，即加不進(jìn)位、

減不借位。對(duì)任何二進(jìn)制數(shù)X,x+x=o,

所以7="，即T能被尸除盡。

?如果收到的丁不能被尸除盡，則丁在傳

輸中一定發(fā)生差錯(cuò)。

?如果收到的T能被尸除盡，是不是T在

傳輸中一定沒(méi)有差錯(cuò)呢？

高華廣學(xué)出浙?社

循環(huán)冗余校驗(yàn)碼CRC—例子

例：給定玲=1101011101,P=101101,計(jì)算廠

1111001000<Q

101101/110101110100000

101101

110001

101101

111001

101101

101000

101101

101100

101101

1000余數(shù)R

循環(huán)冗余校驗(yàn)碼CRC—問(wèn)題

?25M=110101110100000,/=火=01000,

T=25M+F=110101110101000c

?如果收到的T=110101010101000,則它

不能被尸除盡，傳輸中有錯(cuò)，錯(cuò)了一位。

?如果收到的7=111111111111000,它仍

能被尸除盡，但錯(cuò)了四位。

?CRC校驗(yàn)無(wú)法檢測(cè)能被尸除盡的錯(cuò)誤碼。

循環(huán)冗余校驗(yàn)碼CRC

—多項(xiàng)式運(yùn)算的觀點(diǎn)

■每個(gè)二進(jìn)制數(shù)都對(duì)應(yīng)一個(gè)多項(xiàng)式，多項(xiàng)

式系數(shù)對(duì)應(yīng)二進(jìn)制位。上例中數(shù)X,P,

。，R(M=1101011101,尸=101101,

2=1111001000,火=01000)等對(duì)應(yīng)：

M(x)=x9+x8+x6+x4+x3+x2+1

P(x)=X5+X3+X2+1,...

x5M(x)=Q(x)P(x)+A(x)

高華力學(xué)出胸社

循環(huán)冗余校驗(yàn)碼CRC

一生成多項(xiàng)式P(x)

?T(x)=xrM(x)+R(x)

=Q(x)P(x)+i?(x)+R(x)

=g(x)P(x)

?位次)多項(xiàng)式尸(x)稱(chēng)為生成多項(xiàng)式，余式

R(x)對(duì)應(yīng)P生成的CRC碼。

■若傳輸中無(wú)差錯(cuò)，T(x)能被P(x)整除，

但能整除不一定傳輸無(wú)差錯(cuò)。有差錯(cuò)即

T(x)變成T(x)+E(x)。

高華十學(xué)出版社

循環(huán)冗余校驗(yàn)碼CRC

一生成多項(xiàng)式P(x)的選擇

?若P(x)至少包含兩項(xiàng)，.則可檢測(cè)所有一位錯(cuò)誤。

一位錯(cuò)誤部分￡(%)=￡,尸(x)不苛能除盡￡。

?若P(x)是不可約多項(xiàng)式，且?guī)L(zhǎng)〃不大于尸(X)

的周期，則可檢測(cè)所有兩位錯(cuò)誤。不可約多項(xiàng)

式尸(x)的周期e是使尸(x)能除盡d+1的最小整數(shù)

(例如/+34+1的周期是32768)。

兩位錯(cuò)誤部分￡(x)=￡+0,2〃，六孔。不妨設(shè)

i>j,則￡+/=/(1門(mén)+1)。由于

P(x)除不盡工門(mén)+1。另外尸(%)只要多于一項(xiàng)就

除不盡力。所以尸(x).??除不盡￡(x)。

高華十學(xué)出版社

循環(huán)冗余校驗(yàn)碼CRC

一生成多項(xiàng)式P(x)的選擇(續(xù))

?若P(x)包含因子(x+1),則可檢測(cè)所有奇數(shù)位錯(cuò)。

奇數(shù)位錯(cuò)誤部分￡(x)的項(xiàng)數(shù)為奇數(shù)，它不可能

被尸(x)除盡，因?yàn)?x+1)不可能為奇數(shù)項(xiàng)多項(xiàng)式

的因子。［可找尸(x)=(x+1)G(x),G(x)為周期大

于幀長(zhǎng)的不可約多項(xiàng)式］

?若尸(x)是包含常數(shù)項(xiàng)的r次多項(xiàng)式，則可檢測(cè)

長(zhǎng)度Vr的突發(fā)性錯(cuò)誤。這種錯(cuò)誤部分￡(、)=

一+%1+...+￡=￡(爐色+…+1),尸(%)包含常數(shù)項(xiàng),

所以尸(x)不能除盡工1,又尸(x)為r次，大于括

號(hào)中的多項(xiàng)式次數(shù)，也不能除盡它。

高華方學(xué)出版社

循環(huán)冗余校驗(yàn)碼CRC

—常用的16位CRC標(biāo)準(zhǔn)生成多項(xiàng)式

CRC-16：X16+%15+%2+1

CRC-CCITT：X16+X12+X5+1

清華十孚出版社

/?Jt7r'f、?^Z9^'/

循環(huán)冗余校驗(yàn)碼CRC

—CRC的計(jì)算電路例

CRC計(jì)算過(guò)程可以用異或門(mén)電路和移位寄存器來(lái)

實(shí)現(xiàn)，移位寄存器共”立，異或門(mén)最多尸位，它們

正好對(duì)應(yīng)/次生成多項(xiàng)式尸(x)最高次項(xiàng)以外的項(xiàng)。

輸入位

<------

P=101101的CRC計(jì)算電路

薄監(jiān)十字出版社=

差錯(cuò)檢測(cè)的局限性

?差錯(cuò)檢測(cè)都是在包中附加校驗(yàn)信息和數(shù)據(jù)一起

傳輸。任何差錯(cuò)檢測(cè)方法都只能檢測(cè)到某些錯(cuò)

誤，都不是完美的。

?在網(wǎng)絡(luò)結(jié)點(diǎn)的鏈路層幾乎都有CRC校驗(yàn)，檢測(cè)

逐段鏈路傳輸錯(cuò)誤。誰(shuí)做校驗(yàn)？

?在主機(jī)的網(wǎng)絡(luò)層和傳輸層，如IPv4、TCP、

UDP都有校驗(yàn)和，主要檢測(cè)數(shù)據(jù)在主機(jī)或路由

器發(fā)生的錯(cuò)誤。需不需要？夠不夠？…

高華廣學(xué)出版社

差錯(cuò)檢測(cè)的局限性

?Paxsonl997經(jīng)統(tǒng)計(jì)分析發(fā)現(xiàn)：通過(guò)鏈路層CRC

校驗(yàn)的包約0.02%有校驗(yàn)和錯(cuò)誤。

?Stone等1998-1999收集了22億個(gè)包，其中48萬(wàn)

個(gè)包有IP,UDP或TCP校驗(yàn)和錯(cuò)誤。有主機(jī)

軟、硬件錯(cuò)誤，路由器內(nèi)存錯(cuò)誤等。（不要太相

信硬件!）

?校驗(yàn)和是必要的，它和CRC互相補(bǔ)充。..?

?網(wǎng)絡(luò)結(jié)點(diǎn)對(duì)包做差錯(cuò)檢測(cè)，發(fā)現(xiàn)錯(cuò)誤后丟棄包。

如何恢復(fù)，就是差錯(cuò)控制。

jyjft.___rjf/r」t<J*J.

差錯(cuò)控制

確認(rèn)消息：?停-等(確認(rèn)):每發(fā)

?正確認(rèn)ACK(positive一個(gè)包就等待確認(rèn)。

acknowledgement)和超?后退N：連發(fā)數(shù)包等

時(shí)重發(fā)。確認(rèn)。順序接收累計(jì)

?負(fù)確認(rèn)NACK或REJ(鏈確認(rèn)，第左個(gè)包錯(cuò)，從

路層)和重發(fā)。第左個(gè)包開(kāi)始全重發(fā)。

■確認(rèn)消息可以?shī)A帶在發(fā)?選擇重發(fā):連發(fā)數(shù)包

送數(shù)據(jù)包的包頭，稱(chēng)為等確認(rèn)，只重發(fā)出錯(cuò)

捎帶確認(rèn)(piggybacking)。的包。接收方需暫存

已到達(dá)錯(cuò)序包…。

膏華大學(xué)出版社

停-等

發(fā)送方接收方發(fā)送方接收方發(fā)送方接收方

包

超

時(shí)ACK1

重

發(fā)

io

ACK1

丟棄

重復(fù)

包0

包丟失ACK丟失

序號(hào)是否需要?

后退N（g『back-N）接收方

發(fā)送方

包0U

包1卜ACK2

包2卜

包3V-ACK4

包4寸

包5超tACK4

代巨絕包5,6,7

包6時(shí)t

重發(fā)第4

ACK5

重發(fā)黃？ACK7

重發(fā)自Q

重發(fā)磊

高均大學(xué)出演

后退N（go-backN（續(xù)）接收方

發(fā)送方

包0

包1ACK2

包2

包3[ACK4

包4\暇矗5,6

包5

包6

重發(fā)包4jACK5

重發(fā),24ACK7

重發(fā)射

包7

包0

港華，二學(xué)出版粒

選擇重發(fā)

接收方

發(fā)送方

包0

包1ACK2

包2

包3ACK4

包4NACK4

包5暫存包5,6

包6ACK7

重發(fā)黑

包

7ACK1

包0

包1

包2

高華十字出版M

選擇重發(fā)一問(wèn)題

2殳

接收方

包0

包1

包2

包3

包4

包5

包

發(fā)

r一10

包

二6ACK6

包7ACK6

012345670123

發(fā)送窗口接收窗口

清華,二字出砂包

選擇重發(fā)一對(duì)窗口的限制

方

2送

接收方

包o

包-1

包2

包3

ACK4

重發(fā)包0

01234567

發(fā)送窗口接收窗口

序號(hào)3位(0—7)

信'm，二字五㈤夕社.-

2V廠/?"AT『'6e?F/Cr

流量控制(flowcontrol)

?控制發(fā)送方流量，使接收方有緩沖可用。

?“?！龅取绷骺刈詈?jiǎn)單，但網(wǎng)絡(luò)帶寬利用率低。

ARPANET的NCP采用“停-等”。

?“滑動(dòng)窗口流控(slidingwindowflowcontrol)”

技術(shù)。通信雙方準(zhǔn)備好各自的接收緩沖，稱(chēng)為

接收窗口，通告給對(duì)方，作為對(duì)方的發(fā)送窗口。

發(fā)送窗口是發(fā)送方在收到確認(rèn)前可發(fā)送的最大

數(shù)據(jù)量。

?2?5層都可有流控,。...

高華廣學(xué)出浙?社

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

流量控缶U(Howcontrol)(續(xù))

一滑動(dòng)窗口流控

窗口滑動(dòng)

123456789101112

窗口滑動(dòng)

已確認(rèn)

123456789101112

已確乎—窗口滑動(dòng)

01|2|34|5l6l7loll2I3I4I5I6I7

路由選擇

-路由器（或交換機(jī)）的主要功能就是為主機(jī)

存儲(chǔ)、轉(zhuǎn)發(fā)包。為包確定一條從源通過(guò)

若干路由器（或交換機(jī)）到達(dá)目標(biāo)的最優(yōu)路

徑，將包從源主機(jī)傳送到目標(biāo)主機(jī)。

?路由選擇的基本概念

?基本路由算法

路由選擇的基本概念

—由誰(shuí)選擇？

路由器(或交換機(jī))選擇。它們只為包選擇

到達(dá)目標(biāo)的最優(yōu)路徑的下一站，稱(chēng)之為

路由選擇(routing)。它們都有一張路由表,

包含所有可能到達(dá)的目標(biāo)和到達(dá)目標(biāo)的

最優(yōu)路徑的下一站。

路由選擇的基本概念

—靜態(tài)路由

?路由表可以是靜態(tài)的：路由表在設(shè)置后一般不

再改變。靜態(tài)路由信息由管理員手工配置。當(dāng)

網(wǎng)絡(luò)變化時(shí)，可由人工更新配置。

■靜態(tài)路由的缺點(diǎn)是它不會(huì)隨網(wǎng)絡(luò)結(jié)構(gòu)變化而變

化。

?靜態(tài)路由的優(yōu)點(diǎn)是路由器之間無(wú)需交換路由信

息，可以不占用網(wǎng)絡(luò)帶寬。

?靜態(tài)路由可以在簡(jiǎn)單的網(wǎng)絡(luò)環(huán)境，或速率較低

的網(wǎng)段使用。在撥號(hào)線路上也常使用。

演畢7,二學(xué)出版社

路由選擇的基本概念

一動(dòng)態(tài)路由

?大型網(wǎng)絡(luò)的主干結(jié)點(diǎn)需要采用動(dòng)態(tài)路由:

網(wǎng)絡(luò)情況變化時(shí)，路由表要隨時(shí)更新。

動(dòng)態(tài)路由信息由路由器與鄰機(jī)自動(dòng)交換、

自動(dòng)更新。但動(dòng)態(tài)路由有路由擺動(dòng)問(wèn)題

（routeflapping）。

?動(dòng)態(tài)路由的實(shí)現(xiàn)需要兩個(gè)功能：

交換路由信息（通過(guò)路由協(xié)議）；

計(jì)算和更新路由表（通過(guò)路由算法）。

清華二字

7td1

/7,Jr[p卜卜;/、/T押*§*-、F?J

路由選擇的基本概念

一什么時(shí)候選擇？

?若包交換采用數(shù)據(jù)報(bào)方式，則每個(gè)包到

達(dá)路由器（或交換機(jī)）時(shí)，為之選擇路由。

?若包交換采用虛電路方式，則在虛電路

建立時(shí)選定路徑，在虛電路撤消前，不

再為包作路由選擇。

■若采用靜態(tài)路由，從某源到某目標(biāo)的所

有包都按配置路由轉(zhuǎn)發(fā)，數(shù)據(jù)報(bào)方式和

虛電路方式?jīng)]有差別。

路由選擇的基本概念

—什么是所謂“最優(yōu)路徑”？

路由表包含最優(yōu)路徑信息，最優(yōu)的度量:

?帶寬：鏈路的數(shù)據(jù)容量；

?時(shí)延：包從源送達(dá)目標(biāo)所需時(shí)間；

?可靠性：鏈路的誤碼率；

?負(fù)載：路由器資源占用情況；

?跳(hop)數(shù)：路徑經(jīng)過(guò)的路由器數(shù)目；

?費(fèi)用。

高華廣學(xué)出浙?社

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

路由選擇的基本概念

—“距離”最短的路徑

各種度量可抽象為“距離”，它可表示時(shí)延、

跳數(shù)等。這樣，網(wǎng)絡(luò)可用有標(biāo)號(hào)圖表示：

3

24

2291

1

135

高華廣學(xué)出浙?社

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

基本路由算法

—由網(wǎng)絡(luò)圖計(jì)算（結(jié)點(diǎn)1）路由表

目標(biāo)距離下一立占

基本路由算法

?距離向量路由算法DV(DistanceVector

routingalgorithm)

告訴鄰居我的世界。每處有一個(gè)路牌。

?鏈路狀態(tài)路由算法LS(LinkStaterouting

algorithm)

告訴世界我的鄰居。每處有一張地圖。

■兩種算法的比較

距離向量路由算法一簡(jiǎn)介

算法目的：求網(wǎng)絡(luò)圖結(jié)點(diǎn)，的距離向量l）i和后

繼結(jié)點(diǎn)向量Si。A表示從，到圖中其它各點(diǎn)的

最短距離，E表示從，到達(dá)其它結(jié)點(diǎn)的最短路

徑上的下一站。

是一種迭代算法。先給出各結(jié)點(diǎn)的Qi，￡初值,

以后每個(gè)結(jié)點(diǎn)向鄰結(jié)點(diǎn)通報(bào)自己的距離向量及

后繼結(jié)點(diǎn)向量值（告訴鄰居我的世界），任一結(jié)點(diǎn)

，再根據(jù)鄰結(jié)點(diǎn)信息更新自己的。i，4。

高華十學(xué)出版社

距離向量路由算法一例

結(jié)點(diǎn)1，2,3,4,5的初始路由信

息分別是：

DI=(021，8,8)，SI=(-23…)

D2=(2,023,8),S2=(1<93A)

D3=(120,M),S3=(12-4)

D4=S39O,1),S4=(23,-,5)

D5=(oo?oo?oo?l50)5S5=(???4r)

清華7二字出z

*'.??,(f/,??iLJ*.*?-**'IJ?/'?"/?rn.Li,J.t￡.4T^rgn:c'A；

*_/jjj、9jjj_//Jj，?)'i?■.f「J*_/_/

距離向量路由算法一例(續(xù))

結(jié)點(diǎn)2收到鄰結(jié)點(diǎn)1,3,4的路由信息后，

將自己的路由信息。2,S2更新如下：

minMZhk+Oki)=。21，左=1,3,4

.*.。21'=。21，S21'=S21，

同理。2/=。為，S2j'=S2j,/=2,3,4

miru(Z)2k+Qk5)=。24+。45=3+1,

。2'=(2,0,2,3,3+1),S2，=(l,-,3,4,4)

高華廣字出版社

距離向量路由算法一例（續(xù)）

結(jié)點(diǎn)1,2,3,4,5的路由信息穩(wěn)定值為:

1=(0,2,1,5,6),H=(-,2,3,2,2)

2=(2,0,2,3,4),$2=(1,-,3,4,4)

32,0,5,6),$3=(1,2,-,2,2)

43,5,0,1),S4=(2,2,2,5)

54,6,1,0),S5=(4,4,4,4,-)

距離向量路由算法

初始值：Da=0,Sii=-，若，與，相鄰，Dij為i與

）的距離，Sij=j,若不相鄰,Dij=8,兩待定。

算法（結(jié)點(diǎn)，收到相鄰結(jié)點(diǎn)左的Qk和Sk后，把

A和S更新為。?！辏?/p>

對(duì)于j從1到n

｛選相鄰結(jié)點(diǎn)V，滿(mǎn)足［（Av+Qvj尸minkCAk+。?）］

則｛=DYN+Z）vj9S『=Siv）

清蚱7二字td或衽，...J標(biāo)防獷品而;，一

■!r2JI?「廠，§少J-\?fJfk'PJrrlyr》'Jic*r

距離向量路由算法一問(wèn)題

計(jì)數(shù)到無(wú)限(count-to-infinity)問(wèn)題：

?上例,若結(jié)點(diǎn)4到5的線路故障,結(jié)點(diǎn)4更新

路由信息:。4=(535,0產(chǎn)),S4=(2,22-,)o

?0=(35,。25,-35,。45)，,=615,$25)邑5,^45)°

故障后，0=(6468),5=(2,42)。

?按算法更新。,S：0=(6,867),3=(232,2)。

?再更新：￡>=(7,8711),5=(331,2)。

?再更新：。=(89811),S=(3,3J,2),…。

清華7,二學(xué)出版社二總工

*7*Fjy?'，『、f、ur尹，t?F尸（Fr

鏈路狀態(tài)路由算法一簡(jiǎn)介

?由McQuillan等提出，稱(chēng)為最短路徑優(yōu)先SPF

（ShortestPathFirst）算法，于1979年用于

ARPANETo

?每個(gè)結(jié)點(diǎn)周期地向所有結(jié)點(diǎn)擴(kuò)散本結(jié)點(diǎn)鏈路狀

態(tài)信息（告訴世界我的鄰居）。每個(gè)結(jié)點(diǎn)維持一

個(gè)網(wǎng)絡(luò)拓?fù)湫畔?shù)據(jù)庫(kù)，也稱(chēng)鏈路狀態(tài)庫(kù)，有

全部結(jié)點(diǎn)的鏈路狀態(tài)信息，即網(wǎng)絡(luò)拓?fù)鋱D。每

個(gè)結(jié)點(diǎn)可以利用Dijkstra最短路徑算法求出以

本結(jié)點(diǎn)為根的最短路徑樹(shù)，得到路由表。

清華廣學(xué)出版社

/171>j*DyhJ；）、,FF黃，ftf9^it^~

鏈路狀態(tài)路由算法一例

上例中，用C表示結(jié)點(diǎn)鏈路

狀態(tài)信息中的距離向量:

。1=(0,2,1,00,00)

。2=(2,0,2,3,8)

。3=(1,2,0,9,8)

04=3,3,9,0,1)

(00,00,00,

C5=1,0)

高華十學(xué)出版社

鏈路狀態(tài)路由算法一例(續(xù))

構(gòu)造以結(jié)點(diǎn)1為根的最短路徑樹(shù)(，用。1表示

從結(jié)點(diǎn)1到其它各結(jié)點(diǎn)的最短距離向量。

?第一步：樹(shù)只有根結(jié)點(diǎn)L3的初值取G，

2)i=(v0>,2,1,*co)o不在樹(shù)上的結(jié)點(diǎn)集合

記為L(zhǎng)￡={2,3,4,5}

?第二步：將L中與1最近的結(jié)點(diǎn)3加入樹(shù)，更新

3和乙2)i=(v0>,2,<1>,10,8),￡={2,4,5}。

?第三步：將L中與1最近的結(jié)點(diǎn)2加入樹(shù)，更新

3和￡：1)1=(<0>5<2>,<1>,5,00),￡={4,5}。

鏈路狀態(tài)路由算法一例(續(xù))

?第四步：將上中與1最近的結(jié)點(diǎn)4加入樹(shù)，更新

。1和乙1)1=(<0>,<2>,<1>,<5>,6),L={5}O

?第五步：將［中與1最近的結(jié)點(diǎn)5加入樹(shù)，更新

3和乙A=(vO>,<2>,<1>,<5>,<6>)?這

就是以結(jié)點(diǎn)1為根的最短路徑樹(shù)%。

-類(lèi)似地，可構(gòu)建以，為根的最短路徑樹(shù)北

?有了最短路徑樹(shù)就可以得到路由表。

高華尢學(xué)出版社

鏈路狀態(tài)路由算法一例（續(xù)）

高華廣學(xué)出版社

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

常量：可=除源結(jié)點(diǎn)S以外的網(wǎng)絡(luò)所有結(jié)點(diǎn)集合。

，表示下列值：Cii=O；若z?與，相鄰，則Cij

為邊長(zhǎng)；若，與，不相鄰，則Gj=R。

變量：&<=從源結(jié)點(diǎn)s到結(jié)點(diǎn)左的最短路徑的距離,

5$]<=從源結(jié)點(diǎn)s到結(jié)點(diǎn)左的最短路徑的下一站。

計(jì)算：從源結(jié)點(diǎn)到其它結(jié)點(diǎn)的最短路徑的距離向

量。和路徑的下一站向量S。

(1)初始化：L=M；Qsk=Csk；若。sk。00，則Ssk=左,

否則Ssk為空；

清華廣學(xué)出版社

/171>j*DyhJ；）、,FF黃，ftf9^it^~

鏈路狀態(tài)路由算法（續(xù)）

（2）循環(huán)（當(dāng)集合￡非空）

{找上中的某結(jié)點(diǎn)/對(duì)于￡中所有結(jié)點(diǎn)》

°su=miiiwQsw；若Qsu=°0

{S到上中的結(jié)點(diǎn)無(wú)路徑存在,報(bào)告錯(cuò)誤退出；

從￡中刪除〃;

對(duì)于每個(gè)v￡片￡n{〃的鄰結(jié)點(diǎn)},

{右Qsu+°UVVDsv

{Qsv=Qsu+CuV；Ssv=Ssu；}}

鏈路狀態(tài)路由協(xié)議

每個(gè)結(jié)點(diǎn)要：

?周期地學(xué)習(xí)其相鄰結(jié)點(diǎn)和相鄰結(jié)點(diǎn)的網(wǎng)絡(luò)地址;

?度量到相鄰結(jié)點(diǎn)的距離，即與它相連的所有鏈

路的當(dāng)前狀態(tài)；

?構(gòu)造鏈路狀態(tài)包LSP,描述與它相連的所有鏈

路當(dāng)前狀態(tài)；

?將LSP發(fā)給所有結(jié)點(diǎn)；

?在收齊了全部LSP后，計(jì)算到其它結(jié)點(diǎn)的最短

路徑。

清華十字出版社

jfJ、二廠,?二，卜｝

兩種算法的比較

距離向量路由算法：鏈路狀態(tài)路由算法：

?有“計(jì)數(shù)到無(wú)限”問(wèn)-路由器有相同的網(wǎng)絡(luò)

題。拓?fù)?，路由?jì)算的一

-路由器的路由信息從致性可保證。

相鄰的路由器傳播出

去，這個(gè)過(guò)程有延遲,?只發(fā)送本結(jié)點(diǎn)的鏈路

會(huì)出現(xiàn)路由不一致。狀態(tài)，交換信息量少

?交換整個(gè)路由表，交

換信息量大。

■簡(jiǎn)單，易于實(shí)現(xiàn)。

清華廣學(xué)出版社

jIjft.jf/r」J*J.

擁塞控制

?例：交通擁塞。在一定的時(shí)間間隔，當(dāng)對(duì)資源

的需求超過(guò)了可用資源時(shí)，擁塞就發(fā)生。

?設(shè)計(jì)問(wèn)題：道路（鏈路）容量不匹配加重?fù)砣?/p>

■管理問(wèn)題：資源分配的不合理，也會(huì)造成擁塞。

?網(wǎng)絡(luò)擁塞現(xiàn)象

?擁塞控制基本策略

-開(kāi)環(huán)控制

-閉環(huán)控制

-丟棄控制

高華力學(xué)出胸社

網(wǎng)絡(luò)擁塞現(xiàn)象

?網(wǎng)絡(luò)擁塞主要發(fā)生在路由器或包交換機(jī)。

?當(dāng)包到達(dá)的速率接近或超過(guò)包處理和轉(zhuǎn)發(fā)的速

率，就在路由器或交換機(jī)的緩沖區(qū)堆積而排起

隊(duì)來(lái)。

■擁塞現(xiàn)象是包的傳輸時(shí)延變大。若無(wú)緩沖可用

則包被丟棄，若引起超時(shí)重傳，擁塞加劇，導(dǎo)

致網(wǎng)絡(luò)吞吐量突然下降，稱(chēng)為“擁塞崩潰

(congestioncollapse)”。

高華廣學(xué)出浙?社

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

網(wǎng)絡(luò)擁塞現(xiàn)象

一網(wǎng)絡(luò)擁塞對(duì)吞吐量的影響

網(wǎng)絡(luò)吞吐量是數(shù)據(jù)通過(guò)網(wǎng)絡(luò)的傳送速率

吞吐量

擁塞對(duì)吞吐量的影響

一網(wǎng)絡(luò)擁塞對(duì)時(shí)延的影響

網(wǎng)絡(luò)無(wú)擁塞時(shí)，包只有傳播時(shí)延和交換時(shí)延，

擁塞的網(wǎng)絡(luò)還有隊(duì)列時(shí)延，隊(duì)列愈長(zhǎng)時(shí)延愈大。

負(fù)載

擁塞對(duì)時(shí)延的影響

擁塞控制基本策略一開(kāi)環(huán)控制

?開(kāi)環(huán)控制(open-loopcontrol)基于資源預(yù)約

和連接準(zhǔn)入控制,用于虛電路式包交換網(wǎng)。

?開(kāi)環(huán)即事先協(xié)商通信流參數(shù)，協(xié)商后不

管網(wǎng)絡(luò)是擁塞還是帶寬富裕，參數(shù)不能

動(dòng)態(tài)改變。在連接建立時(shí)申明數(shù)據(jù)速率

峰值、數(shù)據(jù)速率平均值、最大吞吐容量

等，請(qǐng)求被允許則連接建立，若資源不

夠則拒絕連接請(qǐng)求。

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

擁塞控制基本策略一開(kāi)環(huán)控制的漏桶(leaky

bucket)算法

□

漏桶算法

:厚駕媒嬰f式縱則”昌堤直翼崎骷姆，圣3

擁塞控制基本策略一開(kāi)環(huán)控制的令牌桶

(tokenbucket)算法

令牌桶算法

擁塞控制基本策略一閉環(huán)控制

?閉環(huán)控制(closed-loopcontrol)是一種動(dòng)態(tài)

控制系統(tǒng)，它包括反饋機(jī)制和控制機(jī)制。

?反饋機(jī)制允許網(wǎng)絡(luò)把擁塞情況通知數(shù)據(jù)

源。路由器(或交換機(jī))是監(jiān)控?fù)砣潭鹊?/p>

最好場(chǎng)所。

?顯式反饋和隱式反饋.??

?控制機(jī)制允許數(shù)據(jù)源調(diào)整給網(wǎng)絡(luò)的負(fù)載。

?窗口控制和速率控制

擁塞控制基本策略一丟棄控制

?當(dāng)路由器的資源（如緩沖