計算機網(wǎng)絡(luò)課件

上海理工大學(xué)計算機工程學(xué)院

第3章

數(shù)據(jù)鏈路層

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層2

3.1基本概念

?鏈路：一條無源的點到點的物理線路段，中間沒有

任何其他的交換結(jié)點。

結(jié)點結(jié)點

?數(shù)據(jù)鏈路：鏈路+規(guī)程（通信協(xié)議來控制這些數(shù)據(jù)

的傳輸）。

A數(shù)據(jù)鏈路層的作用：

■通過一些數(shù)據(jù)鏈路層協(xié)議（即鏈路控制規(guī)

程），在不太可靠的物理鏈路上實現(xiàn)可靠的數(shù)

據(jù)傳輸。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層3

數(shù)據(jù)鏈路層的主要功能

①鏈路管理：數(shù)據(jù)鏈路的建立、維持和釋放；

②幀同步：收方能從收到的比特流中區(qū)分一幀開始和

結(jié)束的地方；

③差錯控制：收方收到有差錯的數(shù)據(jù)幀時，能檢錯重

傳或糾錯；

④流量控制：發(fā)方發(fā)送數(shù)據(jù)的速率必須使收方來得及

接收；

⑤透明傳輸：不管所傳數(shù)據(jù)是什么樣的比特組合，收

方都能正確接收。并能將數(shù)據(jù)與控制信息分開；

⑥尋址：保證每一幀都能發(fā)送到目的站。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層

為網(wǎng)絡(luò)層提供的服務(wù)

①無確認的無連接的服務(wù)：

適用于誤碼率很低的通信信道；或語音通信；

②有確認的無連接的服務(wù)：

適用于誤碼率很高的通信信道；如無線通信；

③有確認的面向連接的服務(wù)：

適用于通信要求較高（可靠性、實時性）的情況

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層5

差錯檢測和糾正

差錯：接收的與發(fā)送的數(shù)據(jù)不一致。

隨機差錯：具有獨立性，與前后碼元無關(guān)。

突發(fā)差錯：相鄰多個數(shù)據(jù)位出錯。

差錯產(chǎn)生的原因

通信信道的噪聲：

①熱噪聲：由傳輸介質(zhì)導(dǎo)體的電子熱運動產(chǎn)生。幅

度較小，是產(chǎn)生隨機差錯的主要根源。

②沖擊噪聲：由外界電磁干擾產(chǎn)生，幅度較大，

是產(chǎn)生突發(fā)差錯的主要根源。

沖擊噪聲是引起差錯的主要原因。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層6

差錯評價指標

誤碼率：錯傳的碼元數(shù)與所傳輸碼元總數(shù)之比。

Pe=Ne/N

其中，N—傳輸?shù)拇a元總數(shù)，Ne一錯傳的的碼元數(shù)

誤比特率：

錯傳的比特數(shù)與所傳輸總比特數(shù)之比。

在二進制碼元時，誤比特率=誤碼率。

普通電話線路：Pe=IO/?io-6

大多數(shù)通信系統(tǒng)：Pe=10-5?10-9

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層7

差錯控制的基本方式

①反饋糾錯

在接收端能發(fā)現(xiàn)差錯，但不能確定錯碼的位置，通過反

饋信息請求發(fā)送端重發(fā)，直到接收端肯定確認為止。

適用于雙工通信和非實時通信系統(tǒng)。

②前向糾錯

在接收端不僅能發(fā)現(xiàn)錯碼，而且還能夠確定錯碼的位

置，并糾正錯碼。

適用于單工通信和實時通信系統(tǒng)。

③混合糾錯

少量差錯在接收端自動糾正，若超出自行糾正能力時，

通過反饋信息請求發(fā)送端重發(fā)。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層8

誤碼控制基本原理

為了能判斷傳送的信息數(shù)據(jù)是否有誤，在傳送

時增加必要的附加判斷數(shù)據(jù)；在不發(fā)生誤碼的情況

之下，附加判斷數(shù)據(jù)是完全多余的，但如果發(fā)生誤

碼，即可利用信息數(shù)據(jù)與附加數(shù)據(jù)之間的特定關(guān)系

來實現(xiàn)檢錯和糾錯。

即，為了使數(shù)據(jù)碼具有檢錯和糾錯能力，應(yīng)當

按一定的規(guī)則在數(shù)據(jù)碼的基礎(chǔ)上增加一些冗余碼（又

稱監(jiān)督碼）。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層9

碼字的檢錯與糾錯能力

碼字（n位）=數(shù)據(jù)碼（m位）+冗余碼（r位）。

海明距離：兩個碼字之間對應(yīng)碼元位的不同碼元

的個數(shù)。

10001001

十10100011

00101010

有3位不同，所以，海明距離=3

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層10

碼字編碼的海明距離

對于一種碼字編碼，在這個碼字集合中，可得到

所有任意兩個碼字的海明距離，其中最小的海明距離

稱為該碼字編碼的海明距離（L

定理L如果d>2t+l,則該編碼可糾正任何t個（或t個以

下）的錯誤。

定理2：如果d>e+l,則該編碼可檢測出任何?個（或e個

以下）的錯誤。

一般情況下，冗余位越多（即r越大），檢錯糾錯

能力越強，但相應(yīng)的編碼效率也隨之降低了。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層11

示例：偶校驗的檢錯與糾錯能力

例：對于偶校驗（使每個碼字中都有偶數(shù)個1）

數(shù)據(jù)碼為2位（有用數(shù)據(jù)為00、01、10、11）

冗余碼為1位（偶校驗位）

有用數(shù)據(jù)經(jīng)過偶校驗編碼，其碼字集合：

000、OIL101、110;

該編碼的海明距離d=2,

根據(jù)定理1,該編碼不能糾正任何錯誤（t=0）。

根據(jù)定理2,該編碼可檢測出任何1個錯誤（e=l）o

寄校驗的檢錯能力與偶校驗一樣。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層12

誤碼控制編碼的分類

按冗余碼的控制功能分：

①糾錯碼：在接收端能發(fā)現(xiàn)并自動糾正差錯。

②檢錯碼：在接收端能發(fā)現(xiàn)差錯。

糾錯檢錯的常用方法

①海明碼：可糾錯和檢錯，實現(xiàn)復(fù)雜，效率低。

②奇偶校驗碼：方法簡單，檢錯能力差。

③循環(huán)冗余編碼(CRC):實現(xiàn)容易，檢錯能力強，廣

泛使用。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層13

檢錯碼：循環(huán)冗余碼一CRC碼

特點：實現(xiàn)容易，檢錯能力強，廣泛使用。

常結(jié)合反饋重傳法來保證信息的可靠傳輸。

碼字組成：

數(shù)據(jù)碼CRC校驗碼

發(fā)送的碼字…b2b03???r2rlr0

n位

編碼與解碼的計算采用二進制比特序列多項式。

二進制比特序列多項式：

m1

M(x)=bm_1x'+…+小聲'+...+bjX+b0

其中，力產(chǎn)0或I,5共機位

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層14

例：若數(shù)據(jù)碼=110011,

可表示為:M(x)=1-x5+l9x4+0?%3+0-x2+1-x+1

即：M(x)=x5+x4+x+1o

生成多項式G(x):

r

G(x)=g^+...+g^+...+g產(chǎn)+g0

其中,g產(chǎn)?；騃,r>i>0,g,wO>g°w0,共r+1位

G（x）被通信雙方事先共同選定使用：

發(fā)送端：通過6（切生成校驗碼；

接收端：通過仃⑴校驗接收的碼字。

對于多項式的運算：采用模2計算（加法不進

位，減法不借位）；加減法是一樣的。

模2計算即是異或運算。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層15

在發(fā)送端：

1.生成校驗碼:

把要發(fā)送的數(shù)據(jù)碼M⑴V去除G（x）,所得的余

數(shù)值就是循環(huán)冗余碼（簡稱CRC校驗碼）。

M(x)-xrR(x)。⑴為商

=。(%)+

G(x)G(x)尺⑴為余數(shù)（CRC校驗碼）

M(x)-xr-l?(x)G⑴共r+1個bit位,

=e（x）

G(x)?*-共r個bit位

2.發(fā)送R(x):即-R(x)

實際上，把CRC校驗碼&x）附加到數(shù)據(jù)碼■⑴

的后面，就構(gòu)成編碼多項式然后爰

送傳輸。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層16

在接收端：

接收到M(x)-xr+R(x)后，按如下操作進行校

驗：

M(x)-xr+R(x)?、E(x)。⑴為商

--------------------=0(x)4--------,人

G(x)G(x)石⑴為余數(shù)

=0無錯

W0有錯

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層17

CRC示例1：發(fā)送端

例：設(shè)數(shù)據(jù)碼版㈤=110011,

采用生成多項式G(x)=x4+x3+l(即11001),r=4

發(fā)送端：求CRC校驗碼

M(x)-xrR(x)

=。(%)+

G(x)G(x)

100001―商Q(x)

G(x)->11001/1100110000M(x)-xr

11001多項式運算采用

10000二進制模二算

11001法，

1001—余數(shù)R(x)即，異或運算

發(fā)送碼：M(x)xr+R(x)=1100111001

數(shù)據(jù)位校驗位

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層18

CRC示例1：接收端一無差錯

接收端:采用生成多項式G(x)=M+-+1(即iiooi)

接收到M(x)-xr+R(x)后，按如下操作進行校

驗：人人

M(x)-xr+R(x)=。(外+^^。㈤為商

G(x)E(x)為余數(shù)

=0無錯

w0有錯

100001―商Q(x)

G(x)-^11001/1100111001<-收到的發(fā)送碼而(%)./+我(%)

z11001

11001

11001

余數(shù)成再無差錯！

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層19

CRC示例1：接收端一有差錯

發(fā)送端發(fā)出的碼字=1100111001

接收端收到的碼字=1100100001,

突四錯

100001―商Q(x)

G(x)-^11001/1100100001收到的碼字曲(x).M+公(%)

'11001

00001

11001

—11000—余數(shù)￡(x)

￡(x)wO,檢測到差錯!

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層20

CRC示例2：發(fā)送端

例：設(shè)數(shù)據(jù)吊㈤=11100110,G(x>11001,r=4

求CRC校驗碼K(x).?

10110110―商Q(x)

G(x).11001/111001100000<—M(x)-xr

111001

10111

11001

11100

11001

發(fā)送碼：10100

M(x)-xr+R(x)11001

=11100110011011010

11001

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層21

流行的生成多項式有:

CRC-8:G(x)=x8+x2+x+l

CRC-12:G(x)-x12+xn+x3+x2+x+l

CRC-16:G(x)=x16+x15+x2+l

CRC-CCITT:G(x)=x16+x12+x5+l

檢測能力：

所有單個錯、奇數(shù)個錯和離散的二位錯。

所有長度4r位的突發(fā)差錯。

CRC的實現(xiàn)：

①硬件：采用多段移位寄存器及異或門組成CRC

校驗電路來實現(xiàn)。

②軟件：通過快速CRC校驗軟件來實現(xiàn)。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層22

3.2停止等待協(xié)議

數(shù)據(jù)鏈路協(xié)議主要考慮的問題:

①避免所傳送的數(shù)據(jù)可能出現(xiàn)差錯和丟失；

②使發(fā)方發(fā)送數(shù)據(jù)的速率適應(yīng)收方的接收能力。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層23

理想化的數(shù)據(jù)傳輸

假設(shè)1:所傳送的數(shù)據(jù)即不會出現(xiàn)差錯和也不會丟

失；（不考慮差錯控制問題）

假設(shè)2:接收端的數(shù)據(jù)接收速率足夠快，有能力接

收發(fā)送端的數(shù)據(jù)發(fā)送率。

發(fā)送端接收端

（不考慮流量控制問題）

在理想化的條件下，數(shù)據(jù)鏈路

層不需要：

①差錯控制協(xié)議；

②流量控制協(xié)議；時

就可保證數(shù)據(jù)的正確傳輸。間

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層24

最簡單流量控制的停止等待協(xié)議

保留假設(shè)1;去掉假設(shè)2?？紤]流量控制問題f流量控制協(xié)議

使發(fā)送端發(fā)送數(shù)據(jù)的速率適應(yīng)接收端的接收能力。

最簡單流量控制協(xié)議

在發(fā)送節(jié)點：發(fā)送端接收端

①從數(shù)據(jù)鏈路層的發(fā)送緩存中取一個數(shù)據(jù)幀；

②發(fā)送這個數(shù)據(jù)幀；

③等待；

④若收到由接收端的應(yīng)答信息，轉(zhuǎn)到①。

在接收節(jié)點：

①等待；

②接收由發(fā)送端發(fā)來的數(shù)據(jù)幀；

③將其存入數(shù)據(jù)鏈路層的接收緩存；

④發(fā)送應(yīng)答信息，表示數(shù)據(jù)幀已接收；轉(zhuǎn)到①

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層25

實用的停止等待協(xié)議（ARQ）

去掉假設(shè)1;去掉假設(shè)2。

考慮差錯控制問題f差錯控制協(xié)議；

考慮流量控制問題f流量控制協(xié)議；

初步協(xié)議：

①發(fā)送端發(fā)送數(shù)據(jù)幀后，等待接收端的應(yīng)答幀；

②接收端收到數(shù)據(jù)幀后，通過CRC校驗（一般用硬件檢驗）,

如果無差錯，回送一個確認幀ACK,

否則，回送一個否認幀NAK。

③發(fā)送端收到應(yīng)答幀，

如果是ACK,發(fā)送下一數(shù)據(jù)幀，

如果是NAK,重發(fā)數(shù)據(jù)幀。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層26

(a)正常情況

死鎖現(xiàn)象:

當出現(xiàn)幀丟失時，發(fā)送端永

遠等待下去。如何解決？發(fā)送端接收端

解決方法：

發(fā)送端設(shè)立一個超時計時器，

發(fā)送完一個數(shù)據(jù)幀時，就啟動

它；

如果在規(guī)定時間tout內(nèi)得不到應(yīng)答

幀，就判定為超時，重傳數(shù)據(jù)

幀。

Tout也稱重傳時間

（C）數(shù)據(jù)幀丟失

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層28

重復(fù)幀差錯:

發(fā)送端接收端

若應(yīng)答幀丟失，按照超時

重發(fā)方法，接收端將收到重復(fù)

幀，如何解決？

解決方法：

給每個數(shù)據(jù)幀附加不同的

發(fā)送序號Ns,如果接收端收到

相同序號的數(shù)據(jù)幀，則丟棄，并1F

回送一個ACK。

(d)應(yīng)答幀丟失

數(shù)據(jù)幀：幀頭HiNs數(shù)據(jù)CRC幀尾

其它附加控制信息

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層29

發(fā)送序號需要多少位？

對于ARQ協(xié)議，發(fā)送序號有0和1即可(只需1個bit);

每發(fā)一個送新的數(shù)據(jù)幀，發(fā)送序號就和上次發(fā)送的不一樣,

重發(fā)的數(shù)據(jù)幀發(fā)送序號不變。

L^QUt

狀態(tài)序號S,O->10

發(fā)送端I重重

幀序號NS'E

接收端_

狀態(tài)序號丁oOfl

DlD2丟棄重復(fù)幀D2D3

if(Ns==R)接收else丟棄

S-發(fā)送端本地狀態(tài)序號(Ibit)。

R-接收端本地狀態(tài)序號(lbit)o

Ns-發(fā)送端附加到數(shù)據(jù)幀上的序號(lbit)o

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層30

ARQ協(xié)議:

接收端

一重傳

一重傳

變序號-?

一變序號

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層31

重傳時間tout的選擇

若Tout太長，浪費時間，

若Tout太短，過早重傳數(shù)據(jù)，產(chǎn)生“額外”應(yīng)答幀。

，toutJ,額外”應(yīng)答幀

狀態(tài)序號11：1.011工'o4fI】

發(fā)送端^v^x/XA/XA/一

幀序號NS'A/叉X義及敘

接收端\添\泵,

狀態(tài)序號iio^i1111LoL1,

差錯丟棄丟棄

如何解決？

提示：在確認幀ACK和否認幀NAK中附加序號。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層32

停止等待協(xié)議的信道利用率

設(shè)：單程傳輸時延Td,

傳輸時間

數(shù)據(jù)幀發(fā)送時間療,

;等待時間

數(shù)據(jù)傳輸率C,數(shù)據(jù)幀長度L,Td,Td:

八.工皿方總時間一等待時間

信道利用率Cr=--------------------------

傳送一幀的總時間

忽略應(yīng)答幀長度和處理時間：

C”.=1

療+2"1+2T"C

L

數(shù)據(jù)幀L越短，信道利用率越低。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層33

示例

例：衛(wèi)星信道：

單程傳輸時延Td=250ms,

數(shù)據(jù)傳輸率。=50kb/s,

數(shù)據(jù)幀長度L=lkbit,

信道用1用率Cr=―1--=--------------------相=3.8%

…一”"50x103

1+2Tdl+2x0.250--------

vLIxlO3

例：若，Td=20ms,C=4kb/s,

要使信道利用率達到50%,L=?

,2Tdecr2X20X10-3X4X103X50%

L---------------=-----------------------------------=160(bit)

1-Cr1-50%

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層34

3.3連續(xù)ARQ協(xié)議

目的：提高信道利用率。

方法：

發(fā)送端發(fā)送完一個數(shù)據(jù)幀后，不停下來等待應(yīng)答

幀，而是連續(xù)再發(fā)送數(shù)據(jù)幀。當收到否認幀NAK時，

再控制重發(fā)。

實現(xiàn)要求：

數(shù)據(jù)幀需附加發(fā)送序號信息。否認幀附加出錯的

數(shù)據(jù)幀發(fā)送序號。

常用協(xié)議：

①回退N幀ARQ協(xié)議(gobackn)

②選擇重發(fā)ARQ協(xié)議(selectiverepeat)

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層35

回退N幀ARQ協(xié)議(gobackn)

①方式1：

反饋否認幀NAK(含出錯的數(shù)據(jù)幀發(fā)送序號)。再

從出錯的數(shù)據(jù)幀開始重傳。

往返時間退回3步重傳

榭

攵

山

立

而

要求：發(fā)送端要求有一個能存儲N個數(shù)據(jù)幀的緩沖區(qū)。

接收端只需能存儲一個數(shù)據(jù)幀的緩沖。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層36

②方式2:

不反饋否認幀NAK。發(fā)送端采用超時機制。

發(fā)送端每發(fā)送一個數(shù)據(jù)幀就啟動該幀計時器，

當收到確認幀后，計時器復(fù)位；如果直到超時

還沒有收到確認幀，則重發(fā)該數(shù)據(jù)幀及后繼的

幀。

T(l)T(2)T(3)T(2)T(3)T(3)T(3)

啟動啟動啟斐復(fù)位tout時時啟動復(fù)位

發(fā)

接

差錯

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層37

3.4選擇重發(fā)ARQ協(xié)議(selective

repeat)

目的：進一步提高信道利用率。

方法：只重傳出現(xiàn)差錯的數(shù)據(jù)幀或者超時的數(shù)據(jù)

幀。

要求：在接收端要設(shè)置具有相當容量的緩存空間。

重傳

送

發(fā)

榭

攵

差錯、丟棄與4,5號一并送入上層

暫存于緩存中

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層38

選擇重發(fā)ARQ協(xié)議一工作原理示意圖

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層39

滑動窗口協(xié)議(SlidingWindows)

對于連續(xù)ARQ協(xié)議，采用了發(fā)送端不等待確認

幀返回就可連續(xù)發(fā)送幀，存在問題：

①當未被確認的數(shù)據(jù)幀數(shù)目太多時；只要有一幀出

錯，就有很多數(shù)據(jù)幀需要重傳，因而增大開銷。

②為了對發(fā)送出去的大量未被確認的數(shù)據(jù)幀進行編

號，每個數(shù)據(jù)幀的發(fā)送序號也要占用較多的比特

數(shù)，因而又增大了開銷。

滑動窗口協(xié)議：

對發(fā)送端已發(fā)送出去但未被確認的幀的數(shù)目加以限

制。

在發(fā)送端和接收端分別設(shè)置發(fā)送窗口和接收窗口。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層40

發(fā)送窗口（在發(fā)送端）

目的：用來對發(fā)送端進行流量控制。

發(fā)送窗口尺寸Ws：在還沒有收到應(yīng)答幀的情況下,

發(fā)送端最多可以連續(xù)發(fā)送數(shù)據(jù)幀的個數(shù)。

發(fā)送序號：

一般采用n位bit進行編號（0~2U）。

若n=3;則用3位bit進行編號（0~7）。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層41

?發(fā)送端只能連續(xù)發(fā)送窗口內(nèi)的數(shù)據(jù)幀；

?每收到一個確認幀后，發(fā)送窗口的前、后沿順時針

旋轉(zhuǎn)一個號，并可以一個發(fā)送新的數(shù)據(jù)幀。

?若未應(yīng)答幀的數(shù)目等于發(fā)送窗口尺寸時，便停止發(fā)

送新的數(shù)據(jù)幀。

發(fā)送0~4號數(shù)據(jù)幀，收到0號確認幀，又收到1~3號確認幀，

若沒有收到它們的發(fā)送5號數(shù)據(jù)幀，繼續(xù)發(fā)送6、7、0號數(shù)據(jù)幀。

確認幀，則停止發(fā)送。等待1~5號確認幀。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層42

接收窗口（在接收端）

目的：用來控制可以接收哪些數(shù)據(jù)幀而不可以接收哪

些幀。

接收窗口防：只有當收到的數(shù)據(jù)幀的發(fā)送序號落入接

收窗口內(nèi)，才允許將該數(shù)據(jù)幀收下；否則，丟

收到0號數(shù)據(jù)幀后，

等待接收0號數(shù)據(jù)幀并發(fā)出0號確認幀又收到1~3號數(shù)據(jù)幀后,

等待接收1號數(shù)據(jù)幀。并發(fā)出1~3號確認幀，

等待接收4號數(shù)據(jù)幀。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層43

如果Wr=l9意味著只能按順序接收數(shù)據(jù)幀。

如果防較大，有可能會出現(xiàn)數(shù)據(jù)幀的失序。

差錯情況：設(shè)防=1；

若收到0號數(shù)據(jù)幀，接收窗口順時針旋轉(zhuǎn)一個號，

并發(fā)出0號確認幀；準備接收1號數(shù)據(jù)幀。

此時，如果收到的不是1號數(shù)據(jù)幀：

而是0號數(shù)據(jù)幀，表明發(fā)出0號確認幀發(fā)送端沒有

收到，因此再發(fā)送一次0號確認幀，此時收到的0號數(shù)

據(jù)幀必須丟棄，否則發(fā)生重復(fù)。

若是2號數(shù)據(jù)幀，表明發(fā)送端發(fā)出的1號數(shù)據(jù)幀丟

失，因此發(fā)送1號否認幀，讓對方重新發(fā)送1號數(shù)據(jù)

幀。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層44

應(yīng)答幀丟失情況

,?/?*XL±111

Ws=2發(fā)送順接收端Wr=2送

0234567上

層

回234567D0

返

01234567「ACK1034567D1

D01園4567

重發(fā)D1ACK2D2

0叵34567

012回567

ACK1

012回567D3D1丟棄

D4

012回567!D3

D4

101234^~6]7j

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層45

應(yīng)答幀被“篡改”情況:ACKfNAK

小、乎J.UJ

Ws=2發(fā)送順接收端Wr=2送

上

0234567DO_

層

叵234567

ACKODO

0[11]34567ACK10垣34567D1

重發(fā)D1—NAK1

0五3456701園4567

DI------ACK2D2

'f012回567

0回34567ACK1

D1丟棄

甌

012567D3

D4

012回567D3

D4

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層46

…應(yīng)翻被“篡改”情況：NAKfACK

接收端Wr=2緩

沖

叵234567D0

區(qū)

D1叵234567

ACK0D0

0叵34567

01234567D2NAK1

ACK1

0[0]34567

01[23]4567D3_-ACK2D2

?0[0]34567

012|34|567D4NAK1

回退，重發(fā)D1D3丟棄

_--0-卮34567

0[12|34567D1JNAK1

重發(fā)D1D4丟棄

0[12]34567ACK1o[rr|34567D1

01|2-1]4567

D2品,ACK^01|23|4567

丟棄ACK1

01[23]456701[2314567D2D3

0123fTT|67

0123[TT]67D4D5

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層47

重疊問題

在接收前后，接收窗口范圍內(nèi)的有效序號出現(xiàn)重

疊。

Ws=4發(fā)送端接收端Wr=5

01234567

帥231456f

木

重復(fù)Dl~3丟棄

應(yīng)答幀全部丟失

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層48

避免重疊問題

為了避免重疊問題，接收窗口尺寸防42口/2。

Ws=4發(fā)送端接收端Wr=4

01234567

0123|4567

丟棄

應(yīng)答幀全部丟失

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層49

發(fā)送窗口的最大尺寸值

Ws=8發(fā)送端接收端Wr=4

0123R567

012314567

0123|4567

0123|4567

重復(fù)幀D0~7

應(yīng)答幀全部丟失

所以，WSV2LL

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層50

累積確認方法

接收端在連續(xù)接收若干個正確的數(shù)據(jù)幀以

后，對最后一個數(shù)據(jù)幀發(fā)回確認幀。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層51

窗口控制協(xié)議的信道利用率

兩類情形:

發(fā)送窗口Ws=7

發(fā)送窗口Ws=4

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層52

窗口控制協(xié)議的信道利用率

設(shè)：單程傳輸時延Td,數(shù)據(jù)幀發(fā)送時間7J,

數(shù)據(jù)傳輸率C,數(shù)據(jù)幀長度L,窗口尺寸Ws

在正常傳輸情況下，忽略應(yīng)答幀長度和處理時間:

當ws?7y>2nz+7y時：CEOO%

3廊均

當Ws?7y〈2Td+2y時：

發(fā)送端I0|1|2|345

CL肱?療二肱

~Tf+2Td1+2TdC

L接收端iI0I1I2.

LTd]Tf\_血」

顯然，Ws越大，信道利用率越高。||||

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層53

依據(jù)信道利用率進行窗口尺寸的選擇

優(yōu)化原則：

發(fā)送端收到窗口中第一個已發(fā)數(shù)據(jù)幀的確認時，正

好發(fā)完窗口中的最后一個數(shù)據(jù)幀。

Ws

由

Cr=r

l+2Td—

L

令0=100%

C

Ws^2Td—+l

L

Ws大于上述選擇，貝40=100%,但浪費緩沖區(qū)；

Ws小于上述選擇，則Cr<100%,發(fā)送端需要等待應(yīng)

答而使發(fā)送停頓。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層54

示例

例：衛(wèi)星信道：

單程傳輸時延Td=250ms,

數(shù)據(jù)傳輸率。=50kb/s,

數(shù)據(jù)幀長度L=1000bit,

窗口尺寸=—+1=2x0.25^—^-+1=26

閹LIxlO3

例：若，Td=20ms,C=56kb/s,Ws=8,L=?

2x0.02x56xl03

數(shù)據(jù)幀長度上=答了?320(bit)

Ws-18-1

在已知條件不變的情況下，設(shè)置L=160bit,信道

利用率如何？

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層55

ARQ協(xié)議、連續(xù)ARQ協(xié)議的窗口尺寸

ARQ協(xié)議：

發(fā)送窗口Ws=L接收窗口Wr=l

連續(xù)ARQ協(xié)議：

?回退N幀ARQ協(xié)議：

發(fā)送窗口那＞1,接收窗口Wr=L

?選擇重發(fā)連續(xù)ARQ協(xié)議：

發(fā)送窗口那＞1,接收窗口Wr＞L且Wr《Ws。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層56

3.5協(xié)議描述和測試

1.協(xié)議開發(fā)過程

協(xié)

議

協(xié)議設(shè)計

標

準

文

本協(xié)議綜合

協(xié)議形式描述

協(xié)

議協(xié)議驗證

性

能協(xié)議實現(xiàn)

評

價

協(xié)議測試

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層57

協(xié)議的形式描述

描述方法：

①有限狀態(tài)機

采用狀態(tài)流程圖進行描述。

②事件狀態(tài)表

采用表格進行描述。

③結(jié)構(gòu)化程序

采用程序代碼進行描述。

④Petri網(wǎng)模型

采用狀態(tài)流程圖進行描述。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層58

有限狀態(tài)機模型FSM

FSM協(xié)議描述方法也稱狀態(tài)轉(zhuǎn)移圖。

特點：易懂、易理解和易于實現(xiàn)。

組成：狀態(tài)圓和有向弧。

輸入事件1；輸出事件1輸入事件2

注：輸入事件2不產(chǎn)

生相應(yīng)的動作，所以

輸出事件為空

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層59

等待式ARQ協(xié)議一狀態(tài)轉(zhuǎn)移圖

發(fā)送u而：

本地操作：[1]=啟動定時器，[2]=本地狀態(tài)序號S加1

[3]=復(fù)位定時器

收到ACK;

收到NAK;[1],重發(fā)數(shù)據(jù)幀

接收端：

本地操作：[1]=本地狀態(tài)序號R加1,[2]=送網(wǎng)絡(luò)層

收到數(shù)據(jù)幀一；NAK收到數(shù)據(jù)幀+；[1],[2],ACK

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層60

等待式ARQ協(xié)議一狀態(tài)轉(zhuǎn)移圖

ACKO丟失3°丟失

DO丟失狀態(tài)定義

00-00

7

07

5X:發(fā)送端發(fā)送的數(shù)據(jù)幀

1

r00。01AY:接收端準備接收的數(shù)據(jù)幀

初始狀態(tài)Z:信道上的數(shù)據(jù)幀

正常收發(fā)

42

3轉(zhuǎn)換定義

10A111

1,2,3,4:正常收發(fā)

6D1丟失07:超時重發(fā)DO

008

8:超時重發(fā)D1

10111「5:丟棄DO

丟棄

QD1丟失6:D1

ACK1丟失

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層61

事件狀態(tài)表

由狀態(tài)轉(zhuǎn)移圖發(fā)展而來。

結(jié)構(gòu)：

事件事件1事件2事件n

當前狀背???

狀態(tài)1????????????

狀態(tài)2????????????

?????????記錄ij???

狀態(tài)m????????????

記錄包含的內(nèi)容：

①任何必須滿足的條件;

②事件發(fā)生后的動作；

③進入的新狀態(tài)。

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層62

等待式ARQ協(xié)議一事件狀態(tài)表

,/、2.1X1

友送乂而:

事件網(wǎng)絡(luò)層收到收到

超時

當前狀基來數(shù)據(jù)ACKNAK

空閑1000

等待確認0233

注：

0二出錯情況，空閑

1二啟動定時器，本地狀態(tài)序號S加1,發(fā)送數(shù)據(jù)

幀，等待確認

2=復(fù)位定時器，空閑

3二啟動定時器，重發(fā)數(shù)據(jù)幀，等待確認

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層63

等待式ARQ協(xié)議一事件狀態(tài)表

接收疆

事件收到

當前狀忐數(shù)據(jù)幀

等待1

注：

1=PO&P1:送網(wǎng)絡(luò)層，R力口1,發(fā)送ACK

NOTPl:發(fā)送NAK

Pl&NOTP0:發(fā)送ACK

其中，邏輯判定變量：

P0數(shù)據(jù)幀序號Ns=本地狀態(tài)序號R

P1數(shù)據(jù)幀的校驗正確

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層64

Petri網(wǎng)模型

德國C?A.Petrit提出（1962,博士論文）。

4個基本元素：

1.位置：系統(tǒng)可能處于的狀態(tài)；用圓圈表示。

2.轉(zhuǎn)換：改變狀態(tài)；用線段表示。

3.有向?。何恢门c轉(zhuǎn)換之間的相互依賴關(guān)系；用弧線表示。

4.標記：系統(tǒng)當前處于的狀態(tài)；在圓圈中用黑點表示。

轉(zhuǎn)換

陳家琪計算機網(wǎng)絡(luò)-第3章數(shù)據(jù)鏈路層65

C:Seq0ontheline

D:Ackontheline初始化系統(tǒng)，發(fā)送第。幀

E:Seq1ontheline

1—發(fā)送第0幀

c第0幀在名

EmitOProcess0

02—超時

發(fā)送接收

3—發(fā)送第1幀

WaitExpect1

for丟失接收第14—超時

Ack0

TimeoutReject0

等待5一第。幀丟失

超時丟棄

6—Ack幀丟失

Ack鏈路上7一第1幀丟失

D

翳11Process18一丟棄第。幀

Ack

接收9一丟棄第1幀

丟失10一接收第0幀

等待Loss

WaitExpect011一接收第1幀

forE第M貞在鏈路上接收第0巾

Ack1

Timeout

1Reject1

超時丟棄

丟失

發(fā)送端7Loss接收端

Y....................

Sender's信道ChannelReceiver's

state