計(jì)算機(jī)網(wǎng)絡(luò)與信息安全課件

第3章

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

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

3.1基本概念

鏈路：一條無源的點(diǎn)到點(diǎn)的物理線路段。

數(shù)據(jù)鏈路：鏈路+規(guī)程（控制數(shù)據(jù)傳輸）。

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

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

在不太可靠的物理鏈路上實(shí)現(xiàn)可靠的數(shù)據(jù)傳輸。

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈3

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

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

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

結(jié)束的地方；

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

傳或糾錯；

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

接收；

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

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

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

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈

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

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

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

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

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

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

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

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

差錯檢測和糾正

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

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

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

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

通信信道的噪聲：

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

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

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

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

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

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

差錯評價(jià)指標(biāo)

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

Pe=Ne/N

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

誤比特率：

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

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

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

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

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

差錯控制的基本方式

①反饋糾錯

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

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

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

②前向糾錯

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

置，并糾正錯碼。

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

③混合糾錯

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

通過反饋信息請求發(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)系

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

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

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

稱監(jiān)督碼）。

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

碼字的檢錯與糾錯能力

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

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

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

10001001

十10100011

00101010

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

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

碼字編碼的海明距離

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

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

稱為該碼字編碼的海明距離d。

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

下）的錯誤。

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

以下）的錯誤。

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

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

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

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

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

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

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

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

000、OIL101>110;

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

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

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

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

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

誤碼控制編碼的分類

按冗余碼的控制功能分：

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

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

糾錯檢錯的常用方法

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

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

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

泛使用。

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

糾錯碼：海明碼

海明在1950年提出的可糾正一位錯的編碼方法。

用r個(gè)校驗(yàn)位構(gòu)造出r個(gè)校驗(yàn)關(guān)系式來指示一位錯

碼的n（=m+r）種可能位置及表示無差錯。

碼字排列：從最左邊位開始依次編號（1、2、…、n）;

r個(gè)校驗(yàn)位:在2k的位置（1、2、4、8、…）;

m個(gè)數(shù)據(jù)位：在其余位（3、5、6、7、9、…）。

r的確定：r2-r>m+1;（.r2>n+l=m+r+l）

例如：4個(gè)信息位D1D2D3D4,3個(gè)校驗(yàn)位尸滬2尸3。

碼位號一?blb2b3b4b5b6b7

碼字fPI|P2|D1|P3|D2|D3|D4|

7/

孑交驗(yàn)位

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈14

確定校驗(yàn)關(guān)系:

錯碼位號

碼字位號海明位S4S2S1

b1P1001

b2P2010

b3D1011

b4P3100

b5D2101

b6D3110

b7D4111

無錯碼000Pl=b3十b5十b7

廣A友LL、送辛工端山：yP2=b3十b6十b7

IP3=b5十b6十b7

（編碼）

采用偶校驗(yàn)Y

rSl=bl十b3十b50b7

接收端：yS2=b2?b3?b6十b7

（解碼）JS4=b4?b5?b6?b7

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

海明示例：發(fā)送端

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

海明示例：接收端

____________r-差錯位

收到的發(fā)送碼——aI?？诳趌ololilol

b1b2b3b4b5b6b7

P1P2D1P3D2D3D4

SiXXXX

S2XXXX

S4XXXX

rSl=bl十b3十b5十b7=1

接收端：JS2=b2十b3十b6十b7=1

(解碼)IS4=b4十b5十b6十b7=1

檢錯：S4s2s1=111。000,

,?,有差錯！差錯位是b7(D4);

糾錯：b7位變反！

I數(shù)據(jù)：去掉校驗(yàn)位，數(shù)據(jù)=1011,

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

海明編碼解碼一簡便法

b1b2b3b4b5b6b7

例數(shù)據(jù)=尸7|尸2|1I尸3l0I1I1]

1011,b3=011

編碼簡便法：將碼字中為1的各位

fb6=110

碼字位號表示為二進(jìn)制碼，再按U十b7=111

模2求和，所得結(jié)果就是校驗(yàn)碼。

P3P2P1=010

b1b2b3b4b5b6b7

發(fā)送的碼字:

收到的碼字:

b2=010

解碼簡便法：將碼字中為1的各位

碼字位號表示為二進(jìn)制碼，再按b3=011

U十b6=110

模2求和，若和為0,則無差錯。

若和不為0,則指明差錯的位號。S4S2S1=111一

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

海明示例：數(shù)據(jù)=1100001(m=7,r=4)

b1b2b3b4b5b6b7b8b9b10b11

1XXXXXX

2XXXXXX

4XXXX

8XXXX

P1P21P3100P4001

b3=0011

編碼.b5=0101

那‘十b11=1011

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

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

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

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

碼字組成:

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

發(fā)送的碼字片.1…b2b0

n位m位+r位

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

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

m1

M(x)=bm_1x"+…+力聲，+...+bjX+b0

其中，力尸0或I,m-10,共機(jī)位

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

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

594

可表示為：M(x)=1*X+1X+0?X3+Q.x2+l?x+1

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

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

r

G(x)=gtx+???+g盧i+...+g]X+g0

其中，g尸?；騃,r>i>o,g10?go=°，共r+1位

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

發(fā)送端：通過G(x)生成校驗(yàn)碼；

接收端：通過G(x)校驗(yàn)接收的碼字。

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

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

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

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

在發(fā)送端：

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

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

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

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

=。(%)+

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

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

=2(%)

G(x)A⑴共r個(gè)bit位

2.發(fā)送M⑴?M+R(x):即,M(x)-xr-R(x)

實(shí)際上，把CRC校驗(yàn)碼區(qū)㈤附加到數(shù)據(jù)碼拉⑴

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

送傳輸。

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

在接收端：

接收到府(x).M+我(%)后，按如下操作進(jìn)行校驗(yàn):

人

M(x)-xr+K(x)Q(x)為商

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

若以W{w：無錯

有錯

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

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

例：設(shè)數(shù)據(jù)碼拉⑴=110011,

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

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

M(x)-xr…J(x)

----------=0(%)+------

G(x)G(x)

100001―商Q(X)

G(x)-^11001/1100110000<—M(x)-xr

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

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

11001法，

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

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

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

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

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

接收端:采用生成多項(xiàng)式G(x)=x4+x3+l(即11001)

接收到府(%)./+我(%后，按如下操作進(jìn)行校驗(yàn):

人人

M(x)-xr+7f(x)⑺+器Q⑴為商

G(x)為余數(shù)

若￡(x){=0無錯

W0有錯

100001―商Q(x)

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

z11001

11001

11001

余數(shù)石⑴無差錯！

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

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

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

II

接收端收到的碼字=1100100001,

突發(fā)工錯

100001―商Q(x)

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

z11001

00001

11001

—11000<-余數(shù)E(X)

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

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

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

例：設(shè)數(shù)據(jù)M⑴=11100110,G(x)=11001,r=4

求CRC校驗(yàn)碼K(x).?

10110110―商Q(x)

G(x).11001/111001100000<r-M(X)-Xr

111001

10111

11001

11100

11001

發(fā)送碼：10100

M(x)xr+R(x)11001

=11100110011011010

------v------11001

數(shù)據(jù)位校驗(yàn)位y—----―^0110—余數(shù)R(x)

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈27

流行的生成多項(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+x75+x2+l

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

檢測能力：

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

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

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

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

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

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

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

3.2停止等待協(xié)議

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

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

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

物理鏈路

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

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

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

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

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

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

發(fā)送端接收端

（不考慮流量控制問題）

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

層不需要：

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

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

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

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

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

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

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

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

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

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

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

③等待；

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

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

①等待；

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

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

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

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

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

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

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

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

初步協(xié)議：

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

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

如果無差錯，回送一個(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ù)鏈32

(a)正常情況

___一一六摹薪箍『33

死鎖現(xiàn)象:

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

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

解決方法：

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

送完一個(gè)數(shù)據(jù)幀時(shí)，就啟動它；

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

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

Tout也稱重傳時(shí)間

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

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

重復(fù)幀差錯:發(fā)送端接收端

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

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

幀，如何解決？

解決方法：

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

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

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

回送一個(gè)ACK。

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

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

其它附加控制信息

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

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

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

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

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

狀態(tài)序號S,Ofl0gi

發(fā)送端I重

幀序號4O

接收端_

狀態(tài)序號廣o0-1

D2丟棄重復(fù)幀D2D3

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

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

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

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

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

ARQ協(xié)議:

接收端

一重傳

一重傳

變序號->

一變序號

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

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

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

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

“額外”應(yīng)答幀

狀態(tài)序號S-Ofl1f0Of111-00-?1

發(fā)送順?重發(fā)

??

幀序號N卜三OO

接收端

狀態(tài)序號R

D1丟棄差錯丟棄丟棄D4D5

如何解決？

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

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

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

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

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

數(shù)據(jù)傳輸率c,數(shù)據(jù)幀長度L

總時(shí)間-等待時(shí)間

信道利用率Cr=

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

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

1

Tf+2Td

l+2Td—

L

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

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

示例

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

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

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

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

信道手1用率Cr==------------------------=3.8%

'c”"50x103

1+2Td—l+2x0.250--------

LIxlO3

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

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

2Tdecr2X20X10-3X4X103X50%

TL=--------------=--=--1-6--0---(-b--it-)--------------------

1-Cr1-50%

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

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

目的：提高信道利用率。

方法：

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

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

再控制重發(fā)。

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

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

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

常用協(xié)議：

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

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

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

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

①方式1：

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

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

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

人

、辛±111

友送犧1I2I3I4I53I46789

接收端12343456789

A丟棄

差錯

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

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

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

②方式2:

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

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

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

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

幀。

差錯

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

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

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

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

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

重傳

?

3

收

接?山

3而

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

暫存于緩存中

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈44

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

多個(gè)數(shù)據(jù)幀出錯情況

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈45

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

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

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

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

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

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

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

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

滑動窗口協(xié)議：

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

制。

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

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈46

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

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

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

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

發(fā)送序號：

一般采用n位bit進(jìn)行編號（0?2口?1）。

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

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

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

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

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

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

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

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

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

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

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

接收窗口（在接收端）

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

些幀。

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

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

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

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

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

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

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈49

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

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

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

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

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

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

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

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

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

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

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

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

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

，/、、"XUJ

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

0234567DO上

D1層

回234567DO

ACK10返34567D1

0|12|34567rD2

Dl.touf

重發(fā)DIIACK201國4567D2

0運(yùn)34567

D1

012回567

ACK1

012回567D3D1丟棄

D4

012|3-4]567!D3

D4

101234^6]7-

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

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

送

上

層

DO

D1

D2

D3

D4

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

應(yīng)答幀被“篡改，，情況:NAKfACK

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

叵234567沖

區(qū)

叵234567DO

012345670叵34567

0117Tl45670叵34567D2

叵

012|34|567034567

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

0[121345670叵34567

重發(fā)D1D4丟棄

0[12]345670[TT|34567DI

01[23\456701[U|4567

丟棄ACK1

01[131456701[2314567D2D3

0123[T5167

0123[TT]67D4D5

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

重疊問題

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

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

01234567

[0]123|4567

木

重復(fù)D1?3丟棄

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

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

避免重疊問題

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

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

01234567

01234567

out

重發(fā)

0123^567

0123|4567

丟棄

01234567

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

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈55

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

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

01231567

012314567

0123|4567

0123|4567

重復(fù)幀D0?7

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

n

所以，W^<2-lo

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

累積確認(rèn)方法

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

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

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

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

發(fā)送窗口Ws=4

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

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

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

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

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

當(dāng)Ws?7y>2Td+7y時(shí)：Cr^100%

當(dāng)發(fā)送端

G—WsTf二Ws

?療+2竊］+2"C

L接收端

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

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

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

優(yōu)化原則：

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

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

Ws

由

Cr*r

l+2Td—

L

令Cr=100%

Ws^2Td—^-l

L

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

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

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

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈60

示例

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

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

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

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

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

閹LIxlO3

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

2Tde2x0.02x56x1()3

數(shù)據(jù)幀長度L=?320(bit)

Ws-18-1

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

用率如何？

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

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

ARQ協(xié)議：

發(fā)送窗口胭=1,接收窗口防=1

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

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

發(fā)送窗口冊＞1,接收窗口防二1。

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

發(fā)送窗口冊＞1,接收窗口防〉1,且

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

3.5數(shù)據(jù)鏈路層示例

分類:

「異步型(等待式協(xié)議)

數(shù)據(jù)鏈路層協(xié)議1「面向字符(BSC,ARPADLC)

。同步型<面向字節(jié)計(jì)數(shù)(DDCMP)

I面向比特(HDLC,SDLC,

ADCCP,LAPB,…)

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

高級數(shù)據(jù)鏈路控制HDLC

1976年，ISO提出HDLC(High-levelDataLinkControl)

適用范圍:

計(jì)算機(jī)一計(jì)算機(jī)、計(jì)算機(jī)一終端、終端一終端

三種類型的站：

主站：主要功能是發(fā)送命令（包括數(shù)據(jù)），接收響

應(yīng)，負(fù)責(zé)整個(gè)鏈路的控制（如系統(tǒng)的初始、流

控、差錯恢復(fù)等）；

次站：主要功能是接收命令，發(fā)送響應(yīng)，配合主站完

成鏈路的控制；

復(fù)合站：同時(shí)具有主、次站功能，既發(fā)送又接收命令

和響應(yīng)，并負(fù)責(zé)整個(gè)鏈路的控制。

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

HDLC的鏈路構(gòu)型

非平衡配置（主從配置）

主站控制整個(gè)鏈路工作。主站發(fā)出的幀叫命令；從

站發(fā)出的幀叫響應(yīng)。

適合把智能和半智能的終端連接到計(jì)算機(jī)。

>

主站~―1口從站

—FJ<------響應(yīng)

占一占式

/Itt/lit>-v

主站f|命令A(yù)|~~>|命令B|_>|命令C|~~>

從站A從站B從站C

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

HDLC的鏈路構(gòu)型

平衡配置

復(fù)合站具有主站和從站的功能。地位平等。

適合于計(jì)算機(jī)和計(jì)算機(jī)之間的連接

命響應(yīng)>

復(fù)合站A復(fù)合站B

命令/響應(yīng)

?不支持多點(diǎn)平衡配置。

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈66

HDLC的基本操作模式

A正常響應(yīng)模式NRM:

適用于非平衡構(gòu)型。只有當(dāng)從站得到主站的許可

（主站向從站發(fā)出探詢）后，從站才能發(fā)起一次一幀

或多幀數(shù)據(jù)的傳輸響應(yīng)。

?異步響應(yīng)模式ARM:

適用于點(diǎn)—點(diǎn)式非平衡構(gòu)型。從站不必等待主站

的許可，就可發(fā)起一次傳輸。但主站和從站的地位不

變。

?異步平衡模式ABM:

適用于復(fù)合站的平衡構(gòu)型。雙方具有同等能力，

任何一個(gè)復(fù)合站可隨時(shí)傳輸幀。

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈67

HDLC的幀的類型

＞信息幀（I幀）

用來傳輸用戶數(shù)據(jù);

幀標(biāo)志地址控制數(shù)據(jù)幀校驗(yàn)幀標(biāo)志

＞監(jiān)控幀（S幀）

用來傳輸控制信息（如流量和差錯控制信息）；

幀標(biāo)志地址控制幀校驗(yàn)幀標(biāo)志

＞無序號幀（U幀）

用來傳輸網(wǎng)絡(luò)管理信息;

幀標(biāo)志地址控制管理信息幀校驗(yàn)幀標(biāo)志

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈68

HDLC的幀結(jié)構(gòu)

bit88/168可變16/328

幀標(biāo)志地址控制數(shù)據(jù)幀校驗(yàn)幀標(biāo)志

幀標(biāo)志（Flag）

定界符為01111110=7EH（零比特填充法）。

地址域（Address）

A主站發(fā)出的幀為目的地址，即表示命令幀；

A從站發(fā)出的幀為源地址，即表示響應(yīng)幀；

A有效地址為254個(gè)（通常為8位，可擴(kuò)展到16位）

■全1的8位地址表示廣播（所有次站接收）；

■全0的8位地址是無效地址。

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈69

HDLC的幀結(jié)構(gòu)

bit88/168可變16/328

幀標(biāo)志地址控制數(shù)據(jù)幀校驗(yàn)幀標(biāo)志

校驗(yàn)區(qū)間,

透明傳輸區(qū)間

/____________________________________

數(shù)據(jù)域（Data）

?任意比特串或字符串（有上限）

校驗(yàn)和（Checksum）

?循環(huán)冗余校驗(yàn)（CRC），生成多項(xiàng)式：

■CRC-CCITTG（x）=x16+x12+x5+l

■或G（x）=x32+x26+x23+x22+x16+x12+x11+x10+

x8+x7+x5+x4+x2+x+1

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈70

HDLC幀的控制域

控制域(Control)

標(biāo)識幀的類型和功能，使對方站執(zhí)行特定的操作。

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈71

HDLC幀的控制域一信息幀

bit1313

信息幀0N(s)P/FN(R)

N(s)-發(fā)送序號

表示當(dāng)前發(fā)送的信息幀的序號，使用滑動窗口技

術(shù)，3位序號，發(fā)送窗口冊=7;

N(r)-接收序號(確認(rèn)序號)

表示本站期望收到的幀的發(fā)送序號，而不是最后

一個(gè)已收到的幀序號；

它具有捎帶確認(rèn)功能。

陳家琪計(jì)算機(jī)網(wǎng)絡(luò)與信息安全-第3章數(shù)據(jù)鏈72

復(fù)合站A復(fù)合站B

ftHDLC幀的捎帶確認(rèn)-BI

1信息幀U

標(biāo)志A0F=00數(shù)據(jù)CRC才不志

目的站地址本幀序號心』J.一

信心、幀

標(biāo)志CRC數(shù)據(jù)1F=00B標(biāo)志

捎帶確認(rèn)本幀序號目的站地址

信息幀

標(biāo)志A1F=01數(shù)據(jù)CRC才不志

本幀序號捎帶確認(rèn)

信息幀

標(biāo)志CRC