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

第3章

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

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

3.1基本概念

?鏈路：一條無(wú)源的點(diǎn)到點(diǎn)的物理線路段，中間沒(méi)有

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

結(jié)點(diǎn)結(jié)點(diǎn)

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

的傳輸）。

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

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

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

據(jù)傳輸。

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

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

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

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

結(jié)束的地方；

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

傳或糾錯(cuò)；

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

接收；

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

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

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

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

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

①無(wú)確認(rèn)的無(wú)連接的服務(wù)：

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

②有確認(rèn)的無(wú)連接的服務(wù)：

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

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

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

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

差錯(cuò)檢測(cè)和糾正

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

隨機(jī)差錯(cuò)：具有獨(dú)立性，與前后碼元無(wú)關(guān)。

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

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

通信信道的噪聲：

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

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

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

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

沖擊噪聲是引起差錯(cuò)的主要原因。

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

差錯(cuò)評(píng)價(jià)指標(biāo)

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

Pe=Ne/N

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

誤比特率：

錯(cuò)傳的比特?cái)?shù)與所傳輸總比特?cái)?shù)之比。

在二進(jìn)制碼元時(shí)，誤比特率=誤碼率。

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

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

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

差錯(cuò)控制的基本方式

①反饋糾錯(cuò)

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

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

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

②前向糾錯(cuò)

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

置，并糾正錯(cuò)碼。

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

③混合糾錯(cuò)

少量差錯(cuò)在接收端自動(dòng)糾正，若超出自行糾正能力時(shí)，

通過(guò)反饋信息請(qǐng)求發(fā)送端重發(fā)。

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

誤碼控制基本原理

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

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

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

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

來(lái)實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。

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

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

稱監(jiān)督碼）。

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

碼字的檢錯(cuò)與糾錯(cuò)能力

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

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

的個(gè)數(shù)。

10001001

十10100011

00101010

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

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

碼字編碼的海明距離

對(duì)于一種碼字編碼，在這個(gè)碼字集合中，可得到

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

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

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

下）的錯(cuò)誤。

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

以下）的錯(cuò)誤。

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

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

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

示例：偶校驗(yàn)的檢錯(cuò)與糾錯(cuò)能力

例：對(duì)于偶校驗(yàn)（使每個(gè)碼字中都有偶數(shù)個(gè)1）

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

冗余碼為1位（偶校驗(yàn)位）

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

000、OIL101、110;

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

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

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

寄校驗(yàn)的檢錯(cuò)能力與偶校驗(yàn)一樣。

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

誤碼控制編碼的分類

按冗余碼的控制功能分：

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

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

糾錯(cuò)檢錯(cuò)的常用方法

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

②奇偶校驗(yàn)碼：方法簡(jiǎn)單，檢錯(cuò)能力差。

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

泛使用。

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

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

特點(diǎn)：實(shí)現(xiàn)容易，檢錯(cuò)能力強(qiáng)，廣泛使用。

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

碼字組成：

數(shù)據(jù)碼CRC校驗(yàn)碼

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

n位

編碼與解碼的計(jì)算采用二進(jìn)制比特序列多項(xiàng)式。

二進(jìn)制比特序列多項(xiàng)式：

m1

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

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

陳家琪計(jì)算機(jī)網(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

生成多項(xiàng)式G(x):

r

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

其中,g產(chǎn)。或I,r>i>0,g,wO>g°w0,共r+1位

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

發(fā)送端：通過(guò)6（切生成校驗(yàn)碼；

接收端：通過(guò)仃⑴校驗(yàn)接收的碼字。

對(duì)于多項(xiàng)式的運(yùn)算：采用模2計(jì)算（加法不進(jìn)

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

模2計(jì)算即是異或運(yùn)算。

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

在發(fā)送端：

1.生成校驗(yàn)碼:

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

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

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

=。(%)+

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

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

=e（x）

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

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

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

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

送傳輸。

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

在接收端：

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

驗(yàn)：

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

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

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

=0無(wú)錯(cuò)

W0有錯(cuò)

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

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

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

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

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

M(x)-xrR(x)

=。(%)+

G(x)G(x)

100001―商Q(x)

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

11001多項(xiàng)式運(yùn)算采用

10000二進(jìn)制模二算

11001法，

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

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

數(shù)據(jù)位校驗(yàn)位

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

CRC示例1：接收端一無(wú)差錯(cuò)

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

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

驗(yàn)：人人

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

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

=0無(wú)錯(cuò)

w0有錯(cuò)

100001―商Q(x)

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

z11001

11001

11001

余數(shù)成再無(wú)差錯(cuò)！

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

CRC示例1：接收端一有差錯(cuò)

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

接收端收到的碼字=1100100001,

突四錯(cuò)

100001―商Q(x)

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

'11001

00001

11001

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

￡(x)wO,檢測(cè)到差錯(cuò)!

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

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

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

求CRC校驗(yàn)碼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

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

流行的生成多項(xiàng)式有:

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

檢測(cè)能力：

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

所有長(zhǎng)度4r位的突發(fā)差錯(cuò)。

CRC的實(shí)現(xiàn)：

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

校驗(yàn)電路來(lái)實(shí)現(xiàn)。

②軟件：通過(guò)快速CRC校驗(yàn)軟件來(lái)實(shí)現(xiàn)。

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

3.2停止等待協(xié)議

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

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

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

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

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

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

失；（不考慮差錯(cuò)控制問(wèn)題）

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

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

發(fā)送端接收端

（不考慮流量控制問(wèn)題）

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

層不需要：

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

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

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

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

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

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

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

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

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

①?gòu)臄?shù)據(jù)鏈路層的發(fā)送緩存中取一個(gè)數(shù)據(jù)幀；

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

③等待；

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

在接收節(jié)點(diǎn)：

①等待；

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

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

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

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

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

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

考慮差錯(cuò)控制問(wèn)題f差錯(cuò)控制協(xié)議；

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

初步協(xié)議：

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

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

如果無(wú)差錯(cuò)，回送一個(gè)確認(rèn)幀ACK,

否則，回送一個(gè)否認(rèn)幀NAK。

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

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

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

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

(a)正常情況

死鎖現(xiàn)象:

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

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

解決方法：

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

發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)，就啟動(dòng)

它；

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

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

幀。

Tout也稱重傳時(shí)間

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

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

重復(fù)幀差錯(cuò):

發(fā)送端接收端

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

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

幀，如何解決？

解決方法：

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

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

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

回送一個(gè)ACK。

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

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

其它附加控制信息

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

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

對(duì)于ARQ協(xié)議，發(fā)送序號(hào)有0和1即可(只需1個(gè)bit);

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

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

L^QUt

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

發(fā)送端I重重

幀序號(hào)NS'E

接收端_

狀態(tài)序號(hào)丁oOfl

DlD2丟棄重復(fù)幀D2D3

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

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

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

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

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

ARQ協(xié)議:

接收端

一重傳

一重傳

變序號(hào)-?

一變序號(hào)

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

重傳時(shí)間tout的選擇

若Tout太長(zhǎng)，浪費(fèi)時(shí)間，

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

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

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

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

幀序號(hào)NS'A/叉X義及敘

接收端\添\泵,

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

差錯(cuò)丟棄丟棄

如何解決？

提示：在確認(rèn)幀ACK和否認(rèn)幀NAK中附加序號(hào)。

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

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

設(shè)：?jiǎn)纬虃鬏敃r(shí)延Td,

傳輸時(shí)間

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

;等待時(shí)間

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

八.工皿方總時(shí)間一等待時(shí)間

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

傳送一幀的總時(shí)間

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

C”.=1

療+2"1+2T"C

L

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

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

示例

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

單程傳輸時(shí)延Td=250ms,

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

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

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

…一”"50x103

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

vLIxlO3

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

要使信道利用率達(dá)到50%,L=?

,2Tdecr2X20X10-3X4X103X50%

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

1-Cr1-50%

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

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

目的：提高信道利用率。

方法：

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

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

再控制重發(fā)。

實(shí)現(xiàn)要求：

數(shù)據(jù)幀需附加發(fā)送序號(hào)信息。否認(rèn)幀附加出錯(cuò)的

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

常用協(xié)議：

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

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

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

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

①方式1：

反饋否認(rèn)幀NAK(含出錯(cuò)的數(shù)據(jù)幀發(fā)送序號(hào))。再

從出錯(cuò)的數(shù)據(jù)幀開(kāi)始重傳。

往返時(shí)間退回3步重傳

榭

攵

山

立

而

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

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

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

②方式2:

不反饋否認(rèn)幀NAK。發(fā)送端采用超時(shí)機(jī)制。

發(fā)送端每發(fā)送一個(gè)數(shù)據(jù)幀就啟動(dòng)該幀計(jì)時(shí)器，

當(dāng)收到確認(rèn)幀后，計(jì)時(shí)器復(fù)位；如果直到超時(shí)

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

幀。

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

啟動(dòng)啟動(dòng)啟斐復(fù)位tout時(shí)時(shí)啟動(dòng)復(fù)位

發(fā)

接

差錯(cuò)

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

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

repeat)

目的：進(jìn)一步提高信道利用率。

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

幀。

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

重傳

送

發(fā)

榭

攵

差錯(cuò)、丟棄與4,5號(hào)一并送入上層

暫存于緩存中

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

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

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

滑動(dòng)窗口協(xié)議(SlidingWindows)

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

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

①當(dāng)未被確認(rèn)的數(shù)據(jù)幀數(shù)目太多時(shí)；只要有一幀出

錯(cuò)，就有很多數(shù)據(jù)幀需要重傳，因而增大開(kāi)銷(xiāo)。

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

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

數(shù)，因而又增大了開(kāi)銷(xiāo)。

滑動(dòng)窗口協(xié)議：

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

制。

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

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

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

目的：用來(lái)對(duì)發(fā)送端進(jìn)行流量控制。

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

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

發(fā)送序號(hào)：

一般采用n位bit進(jìn)行編號(hào)（0~2U）。

若n=3;則用3位bit進(jìn)行編號(hào)（0~7）。

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

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

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

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

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

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

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

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

確認(rèn)幀，則停止發(fā)送。等待1~5號(hào)確認(rèn)幀。

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

接收窗口（在接收端）

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

些幀。

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

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

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

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

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

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

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

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

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

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

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

并發(fā)出0號(hào)確認(rèn)幀；準(zhǔn)備接收1號(hào)數(shù)據(jù)幀。

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

而是0號(hào)數(shù)據(jù)幀，表明發(fā)出0號(hào)確認(rèn)幀發(fā)送端沒(méi)有

收到，因此再發(fā)送一次0號(hào)確認(rèn)幀，此時(shí)收到的0號(hào)數(shù)

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

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

失，因此發(fā)送1號(hào)否認(rèn)幀，讓對(duì)方重新發(fā)送1號(hào)數(shù)據(jù)

幀。

陳家琪計(jì)算機(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

陳家琪計(jì)算機(jī)網(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

陳家琪計(jì)算機(jī)網(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

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

重疊問(wèn)題

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

疊。

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

01234567

帥231456f

木

重復(fù)Dl~3丟棄

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

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

避免重疊問(wèn)題

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

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

01234567

0123|4567

丟棄

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

陳家琪計(jì)算機(jī)網(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

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

累積確認(rèn)方法

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

后，對(duì)最后一個(gè)數(shù)據(jù)幀發(fā)回確認(rèn)幀。

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

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

兩類情形:

發(fā)送窗口Ws=7

發(fā)送窗口Ws=4

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

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

設(shè)：?jiǎn)纬虃鬏敃r(shí)延Td,數(shù)據(jù)幀發(fā)送時(shí)間7J,

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

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

當(dāng)ws?7y>2nz+7y時(shí)：CEOO%

3廊均

當(dāng)Ws?7y〈2Td+2y時(shí)：

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

CL肱?療二肱

~Tf+2Td1+2TdC

L接收端iI0I1I2.

LTd]Tf\_血」

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

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

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

優(yōu)化原則：

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

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

Ws

由

Cr=r

l+2Td—

L

令0=100%

C

Ws^2Td—+l

L

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

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

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

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

示例

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

單程傳輸時(shí)延Td=250ms,

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

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

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

閹LIxlO3

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

2x0.02x56xl03

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

Ws-18-1

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

利用率如何？

陳家琪計(jì)算機(jī)網(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。

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

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

1.協(xié)議開(kāi)發(fā)過(guò)程

協(xié)

議

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

標(biāo)

準(zhǔn)

文

本協(xié)議綜合

協(xié)議形式描述

協(xié)

議協(xié)議驗(yàn)證

性

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

評(píng)

價(jià)

協(xié)議測(cè)試

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

協(xié)議的形式描述

描述方法：

①有限狀態(tài)機(jī)

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

②事件狀態(tài)表

采用表格進(jìn)行描述。

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

采用程序代碼進(jìn)行描述。

④Petri網(wǎng)模型

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

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

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

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

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

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

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

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

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

輸出事件為空

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

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

發(fā)送u而：

本地操作：[1]=啟動(dòng)定時(shí)器，[2]=本地狀態(tài)序號(hào)S加1

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

收到ACK;

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

接收端：

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

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

陳家琪計(jì)算機(jī)網(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:接收端準(zhǔn)備接收的數(shù)據(jù)幀

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

正常收發(fā)

42

3轉(zhuǎn)換定義

10A111

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

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

008

8:超時(shí)重發(fā)D1

10111「5:丟棄DO

丟棄

QD1丟失6:D1

ACK1丟失

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

事件狀態(tài)表

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

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

事件事件1事件2事件n

當(dāng)前狀背???

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

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

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

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

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

①任何必須滿足的條件;

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

③進(jìn)入的新?tīng)顟B(tài)。

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

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

,/、2.1X1

友送乂而:

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

超時(shí)

當(dāng)前狀基來(lái)數(shù)據(jù)ACKNAK

空閑1000

等待確認(rèn)0233

注：

0二出錯(cuò)情況，空閑

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

幀，等待確認(rèn)

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

3二啟動(dòng)定時(shí)器，重發(fā)數(shù)據(jù)幀，等待確認(rèn)

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

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

接收疆

事件收到

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

等待1

注：

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

NOTPl:發(fā)送NAK

Pl&NOTP0:發(fā)送ACK

其中，邏輯判定變量：

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

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

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

Petri網(wǎng)模型

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

4個(gè)基本元素：

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

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

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

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

轉(zhuǎn)換

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

C:Seq0ontheline

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

E:Seq1ontheline

1—發(fā)送第0幀

c第0幀在名

EmitOProcess0

02—超時(shí)

發(fā)送接收

3—發(fā)送第1幀

WaitExpect1

for丟失接收第14—超時(shí)

Ack0

TimeoutReject0

等待5一第。幀丟失

超時(shí)丟棄

6—Ack幀丟失

Ack鏈路上7一第1幀丟失

D

翳11Process18一丟棄第。幀

Ack

接收9一丟棄第1幀

丟失10一接收第0幀

等待Loss

WaitExpect011一接收第1幀

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

Ack1

Timeout

1Reject1

超時(shí)丟棄

丟失

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

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

Sender's信道ChannelReceiver's

state