計(jì)算機(jī)網(wǎng)絡(luò)第5章數(shù)據(jù)鏈路層課件

第5章數(shù)據(jù)鏈路層

5.1基本概念

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

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

輸）。

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

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

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

的數(shù)據(jù)傳輸。

學(xué)習(xí)重點(diǎn):兩臺(tái)機(jī)器之間實(shí)現(xiàn)可靠、有效的

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

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

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

地方；

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

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

錯(cuò)；

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

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

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

設(shè)計(jì)要點(diǎn)；1）向網(wǎng)絡(luò)層提供一個(gè)定義良好的服務(wù)接口

2）處理傳輸錯(cuò)誤

3）調(diào)節(jié)數(shù)據(jù)流，確保慢速的接收方不會(huì)被除快

速的發(fā)送方淹沒。

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

最主要的服務(wù)是將數(shù)據(jù)從源機(jī)器的網(wǎng)絡(luò)層傳輸?shù)侥?/p>

標(biāo)機(jī)器的網(wǎng)絡(luò)層.

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

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

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

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

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

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

5.1.3成幀方法

①字符計(jì)數(shù)法：

在幀頭部指明幀內(nèi)字符數(shù)。

問題：由于傳輸差錯(cuò)導(dǎo)致計(jì)數(shù)值被“篡改”；

CharactercountOnecharacter

笫1幀計(jì)數(shù)值笫J幀計(jì)數(shù)值

(a)51|2345671898|01234j5687890123

Frame1Frame2Frame3Frame4

5characters5characters8characters8characters

第1幀第4幀

5個(gè)字符Error第2幀的計(jì)數(shù)值出錯(cuò)8個(gè)字符

(b)5123476789801234

Frame1Frame2Nfwa被誤認(rèn)為是第3幀的計(jì)數(shù)值

(Wrong)charactercount

圖3-3

②字符填充首尾界符法：

以ASCII字符DLE和STX作為幀的頭部，DLE

和ETX作為幀的尾部(DLE=10H>STX=

02H、ETX=03H)

技術(shù)：如何避免二進(jìn)制數(shù)據(jù)可能與幀的頭尾標(biāo)志

相同？

，原始數(shù)據(jù)|A||DLE||STX||B

/-----------------------------------------------------------------------------------------------------------------------------

線上數(shù)據(jù)|O￡E||STX||'A|[D]E][5E1||STX||B

幀頭飛二幀尾

插入的DLE

接收數(shù)據(jù)

(刪除填充的DLE)ADLESTXB

③位填充首尾標(biāo)志法：

以一個(gè)特定的字節(jié)信息作為幀的頭尾標(biāo)志；

如01111110；為了避免與原始數(shù)據(jù)比特

組合相同，發(fā)送方在數(shù)據(jù)中遇到5個(gè)連續(xù)

的1時(shí)，自動(dòng)在其后插入一個(gè)0；接收方

在新抿中遇到5個(gè)詫緯的1后面跟著一個(gè)

原始數(shù)據(jù)011011111TM11101111110

I!\\\\\

線上數(shù)據(jù)011111100110111110111110101111101001111110

幀頭T_幀尾

填充的位

接收數(shù)據(jù)

（刪除填充位）01101111111111101111110

5.1.4差錯(cuò)控制

差錯(cuò)產(chǎn)生的原因主要由通信信道的噪聲引

起，通信信道噪聲分為二種:

(1)熱噪聲：由傳輸介質(zhì)導(dǎo)體的電子熱運(yùn)

動(dòng)產(chǎn)生。幅度較小，是產(chǎn)生隨機(jī)差錯(cuò)的主

要根源；

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

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

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

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

■(1)誤碼率：錯(cuò)傳的碼元數(shù)與所傳輸碼元總數(shù)

之比。

■Pe=Ne/N

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

兀數(shù)。

■(2)誤比特率：

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

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

■差錯(cuò)控制的基本方式如下：

■(1)反饋糾錯(cuò)

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

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

止。

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

■(2)前向糾錯(cuò)

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

并匈正錯(cuò)誤。

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

■(3)混合糾錯(cuò)

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

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

5J.5流控制

?基于反饋的流控制

?基于速率的流控制

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

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

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

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

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

10001001

十10100011

00101010

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

碼字編碼的海明距離

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

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

最小的海明距離稱為該碼字編碼的海明距

離d。

■定理1：如果d22t+1,則該編碼可糾正

任何t個(gè)（或t個(gè)以下）的錯(cuò)誤。

■定理2：如果d2e+15則該編碼可檢測(cè)出

任何e個(gè)（或e個(gè)以下）的錯(cuò)誤。

示例：偶校驗(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)過偶校驗(yàn)編碼，其碼字集合：

000>011、101>110；

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

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

D>=2t+1

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

D>=e+1

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

誤碼控制編碼的分類

按冗余碼的控制功能分:

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

錯(cuò)。叫前向糾錯(cuò)

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

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

率低。

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

③循環(huán)冗余編碼(CRC)：實(shí)現(xiàn)容易，檢錯(cuò)

能力強(qiáng)，廣泛使用。

5.2.1糾錯(cuò)碼:海明碼

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

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

（=m+r）種可能位置及表示無差錯(cuò)。

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

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

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

r的確定：r2—r+1;（Vr2+1=m+r+1）

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

碼位號(hào)一＞b1b2b3b4b5b6b7

碼字一尸3lD21D3lD4l

7-

校驗(yàn)位

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

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

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

■碼字組成：

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

發(fā)送的碼字bm-10,,^2b。

\

II位=m位+

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

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

M(x)=b〃zxM/+???+^H+.??+bjX+b0

其中，，=?；?，i>0,共〃?位

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

可表示為：M(x)=1*x5+1*x4+0,x3+0*x21,x1

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

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

r

G(x)=grx+...+g,x'+...+g1x+gO

其中，g=。或7,rm’20,g,W0,g°W0,共r+1位

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

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

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

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

位)；加減法是一樣的。

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

循環(huán)冗余檢驗(yàn)的原理

■在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循

環(huán)冗余檢驗(yàn)CRC的檢錯(cuò)技術(shù)。

■在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組

k個(gè)比特。

■假設(shè)待傳送的一組數(shù)據(jù)M=101001

（現(xiàn)在k=6）。我們?cè)贛的后面再添

加供差錯(cuò)檢測(cè)用的n位冗余碼一起發(fā)送。

冗余碼的計(jì)算

■用二進(jìn)制的模2運(yùn)算進(jìn)行2"乘M的運(yùn)

算，這相當(dāng)于在M后面添加。個(gè)0。

■得到的（k+n）位的數(shù)除以事先選定好

的長(zhǎng)度為（。+1）位的除數(shù)P,得出商

是Q而余數(shù)是R,余數(shù)R比除數(shù)P少1

位，即R是。位。

冗余碼的計(jì)算舉例

■現(xiàn)在k=G,M=101001o

■除數(shù)P=1101，貝!］。二31

■被除數(shù)是101001000o

循環(huán)冗余檢驗(yàn)的原理說明

110101-Q（商）

尸（除數(shù)）-1101|1O1OQ1QOO-2〃M（被除數(shù)）

1101jH

1110^5”

HOI:"

onnH

poopijj

1110”

1101；i

-QTTOs

0000i

Tioo

1101

"00?-R（余數(shù)），作為FCS

■模2運(yùn)算的結(jié)果是：商6?=110101,

余數(shù)R=001o

■把余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后

面發(fā)送出去。發(fā)送的數(shù)據(jù)是：2nM+R

即：101001001,共（k+位。

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

■接收方對(duì)接收到的數(shù)據(jù)除以同樣的除數(shù),只要得

出的余數(shù)R不為0,就表示檢測(cè)到了差錯(cuò)。

■但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾

個(gè)比特出現(xiàn)了差錯(cuò)。

■一旦檢測(cè)出差錯(cuò)，就丟棄這個(gè)出現(xiàn)差錯(cuò)的幀。

■只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)

尸，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很

小。

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

CRC-8:G㈤=X*+x2+x+/

CRC-12:G(x)=X12^-x11+x3+x24-1

CRC-16:G(x)=x/6+x/5+x2+l

CRC-CCITT:G(x)=x/+x〃+x5+/

檢測(cè)能力：

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

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

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

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

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

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

1數(shù)據(jù)鏈路（即邏輯鏈路）與鏈路（即物理

鏈路）有何區(qū)別？“電路接通了“與“數(shù)據(jù)

鏈路接通了”的區(qū)別何在？

■答：數(shù)據(jù)鏈路與鏈路的區(qū)別在于數(shù)據(jù)鏈路出鏈路外，還必須

有一些必要的規(guī)程來控制數(shù)據(jù)的傳輸，因此，數(shù)據(jù)鏈路比鏈

路多了實(shí)現(xiàn)通信規(guī)程所需要的硬件和軟件。

■“電路接通了”表示鏈路兩端的結(jié)點(diǎn)交換機(jī)已經(jīng)開機(jī)，物理連

接已經(jīng)能夠傳送比特流了，但是，數(shù)據(jù)傳輸并不可靠，在物

理連接基礎(chǔ)上，再建立數(shù)據(jù)鏈路連接，才是“數(shù)據(jù)鏈路接通

了”，此后，由于數(shù)據(jù)鏈路連接具有檢測(cè)、確認(rèn)和重傳功

能，才使不太可靠的物理鏈路變成可靠的數(shù)據(jù)鏈路，進(jìn)行可

靠的數(shù)據(jù)傳輸當(dāng)數(shù)據(jù)鏈路斷開連接時(shí)，物理電路連接不一定

跟著斷開連接。

2為了進(jìn)行差錯(cuò)控制,必須對(duì)傳送的數(shù)據(jù)進(jìn)行校驗(yàn).在局

域網(wǎng)中廣泛使用的校驗(yàn)方法是_(1)_,CRC-16標(biāo)準(zhǔn)

規(guī)定生成多項(xiàng)式為G(x)=x〔6+xi5+x2+1,它產(chǎn)生的

校驗(yàn)碼是__(2)__位，接收端發(fā)現(xiàn)錯(cuò)誤后采取的措施是

―(3)―,如果UMC的生成多項(xiàng)式是G(x)=x，+x+1,

存息碼字是10110,由計(jì)算出來的CRC校驗(yàn)碼是

(1)A奇偶檢驗(yàn)B海明碼C格雷碼D循環(huán)冗余校驗(yàn)

(2)A2B4C16D32

(3)A自動(dòng)糾錯(cuò)B報(bào)告上層協(xié)議C自動(dòng)請(qǐng)求重發(fā)D重

新生成原始數(shù)據(jù)

(4)A0100B1010C0111D1111

書上作業(yè)練習(xí):P84

5-41要發(fā)送的數(shù)據(jù)為1101011011。采用CRC的生

成多項(xiàng)式是P(X)=X4+X+1o試求應(yīng)添加在數(shù)據(jù)后

面的余數(shù)。

數(shù)據(jù)在傳輸過程中最后一個(gè)1變成了0,問接收端能

否發(fā)現(xiàn)？

若數(shù)據(jù)在傳輸過程中最后兩個(gè)1都變成了0,問接收

端能否發(fā)現(xiàn)？

采用CRC檢驗(yàn)后，數(shù)據(jù)鏈路層的傳輸是否就變成了

可靠的傳輸？

■答：作二進(jìn)制除法，1101011011

000010011得余數(shù)1110，添加的

檢驗(yàn)序列是1110.

■作二進(jìn)制除法，兩種錯(cuò)誤均可發(fā)現(xiàn)

■僅僅采用了CRC檢驗(yàn)，缺重傳機(jī)制，數(shù)據(jù)

鏈路層的傳輸還不是可靠的傳輸。

本課重點(diǎn)

■掌握CRC冗余校驗(yàn)碼的計(jì)算.

5.3基本數(shù)據(jù)鏈路協(xié)議

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

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

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

物理鏈路

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

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

不會(huì)丟失；不考慮差錯(cuò)控制問題）

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

能力接收發(fā)送端的數(shù)據(jù)發(fā)送率發(fā)送端接收端

（不考慮流量控制問題）

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

層不需要：

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

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

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

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

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

考慮差錯(cuò)控制問題⑥差錯(cuò)控制協(xié)議；

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

■初步協(xié)議：

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

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

件檢驗(yàn)），如果無差錯(cuò)，回送一個(gè)確認(rèn)幀ACK,否

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

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

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

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

發(fā)送端接收端

間V\

(a)正常情況

死鎖現(xiàn)象:

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

遠(yuǎn)等待下去。如何解決？

解決方法：

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

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

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

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

(c)數(shù)據(jù)幀丟失

Tout也稱重傳時(shí)間

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

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

時(shí)重發(fā)方法，接收端將收到

重復(fù)幀，如何解決？

解決方法：

給每個(gè)數(shù)據(jù)幀附加不同的發(fā)送序

號(hào)Ns,如果接收端收到相同序

號(hào)的數(shù)據(jù)幀，則丟棄，并回送一

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

個(gè)ACK。

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

其它附加控制信息

發(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)不變。

~——JL~——?

狀態(tài)序號(hào)號(hào)OTI_0川_I_Jf0-

發(fā)送端n；八一JZA重\飛An

狀態(tài)序號(hào)0^1l^>0o高1A

DID2丟棄重復(fù)幀D2D3

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

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

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

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

ARQ協(xié)議:

接收端R<-0

等待<

收數(shù)據(jù)幀

存數(shù)據(jù)幀

變序號(hào)fR—l-R%發(fā)送ACK」

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

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

OU太短，過早重傳數(shù)據(jù)，產(chǎn)生"額外”應(yīng)答

out“額外，，應(yīng)答幀

狀態(tài)序號(hào)》Of11->00-1

發(fā)送犧!重發(fā)

幀序號(hào)

接收端_

狀態(tài)序號(hào)R

棄

棄

棄

丟

去

去

基

D錯(cuò)D4

■如何解決？

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

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

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

數(shù)據(jù)幀發(fā)送時(shí)間"；

數(shù)據(jù)傳輸率C數(shù)據(jù)幀長(zhǎng)度心

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

信道利用率Cr=

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

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

Tf+2Td1+277/C

L

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

示例

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

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

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

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

信道利用率Cr=——5——=-----------二----r=3.8%

l+2Td「1+2x0,250^^

LIxlO3

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

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

,2Tdecr2X20X10-3X4X103X50%,

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

1-Cr1-50%

連續(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ā)送序號(hào)信息。否認(rèn)幀附加出錯(cuò)的

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

■常用協(xié)議：

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

■②選擇重發(fā)ARQ加議(selectivereoeat)

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

n)

■①方式1：

■反饋否認(rèn)幀NAK（含出錯(cuò)的數(shù)據(jù)幀發(fā)送序

號(hào)）。再?gòu)某鲥e(cuò)的數(shù)據(jù)幀開始重傳。

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

沖區(qū)。

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

■②方式2：

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

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

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

到超時(shí)還沒有收到確認(rèn)幀，則重發(fā)該數(shù)據(jù)幀

及后繼的幀。

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

(selectiverepeat)

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

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

幀。

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

間C

重傳

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

暫存于緩存中

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

意圖

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

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

protocol)

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

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

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

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

增大了開銷。

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

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

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

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

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

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

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

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

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

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

■一般采用n位bit進(jìn)行編號(hào)（0?2n-i）o

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

■?發(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ù)幀，收到。號(hào)確認(rèn)幀，又收到卜3號(hào)確認(rèn)幀，

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

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

?轆船制觸懶2幀而不可以接

收哪些幀。

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

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

則,丟棄。

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

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

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

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

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

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

■差錯(cuò)情況：設(shè)l/l/r=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ā)送端沒有收到，因

此再發(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ù)幀。

應(yīng)鬻產(chǎn)

送

接收端Wr=2

上

廿6溫

回234S67M

M1E34S6"D1

ACKl

56加

%4567RD2

'CK2

Dl.toi擊

居3而4S61

1)1丟棄

QI，國(guó)。嗝

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

送

上

層

DO

D1

D2

D3

D4

一嚴(yán)翼貞被“篡改”情況：NAKfACK

接收端Hr=2緩

沖

[0234567DO

》區(qū)

DI[023456

F■DO

0123456701Tl3456

ACK1

60|12|3456|D2

01fTJ56O|T13456

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

0|I2|3456:ofTl3456

重發(fā)D1D4丟棄I

0[O34567irr0|Tj]3456tD1

01PT1456i

D21H01FT1456t

丟棄ACK1

)D2D3

01[T14560456

C、3

0123416

12O?6TD4D5

重疊問題

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

重疊。

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

01234567<。酎儂

01234567

ACK07

重發(fā)

012314567kg

回123|4567

A

（重復(fù)Dl~3丟棄

01234567

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

避免重疊問題

■為了避免重疊問題，接收窗口尺寸WrW2n

/2

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

01234567

01234567

t'out<

重發(fā)

0123^567

0123|4567

丟棄

01234567

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

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

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

01234567

012314567

0123|4567

0123|4567

重復(fù)幀D0-7

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

所以，Ws<2^\.

累積確認(rèn)方法

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

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

正常情況

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

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

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

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

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

rm.

當(dāng)人時(shí)：Cr^100%

當(dāng)％$?。＜2，"+?7時(shí)：

八Ws?TfWs

Cr?------=.....—

工"2Td—/

L

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

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

:■優(yōu)化曾貝送I尾).收到算口圣塞工金已獎(jiǎng)攀藉囑的確

認(rèn)時(shí)，正好發(fā)完窗口中的最后一個(gè)數(shù)據(jù)幀。

Ws

由c

l+2Td一

L

令Cr=100%

Hs^2Td—+\

■l/1/s大于上述選擇，則Cr=100%，但浪費(fèi)緩

濟(jì)區(qū)；、

■l/l/s*、于上述選擇，則Crv100%，發(fā)送端需

要等待應(yīng)答而使發(fā)送停頓。

示例

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

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

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

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

rifp

窗口尺寸^v=2r</—+1=2x0.25-__^-+1=26

qLIxlO3

例：若，T(l=20ms5C=56kb/s,W=8,￡=?

物證砧2Tde2x0.02x56x1()3

數(shù)據(jù)幀長(zhǎng)度L=--—-=------------R320(bit)

Irs-18-1

■在已知條件不變的情況下，設(shè)置&160

bit,信道司用率如何？

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

口尺寸

■ARQ協(xié)議：

■發(fā)送窗口Ws=1,接收窗口Wr=1

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

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

■發(fā)送窗口IVs>1,接收窗口肘=1。

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

■發(fā)送窗口接收窗口例>1,且

l/l/rWWs。

重難點(diǎn)講解與練習(xí)

■1流量和差錯(cuò)控制

■1)差錯(cuò)控制方法：

■A自動(dòng)請(qǐng)求重發(fā)(AutomaticRepeat

Request,ARQ)

■B前向糾錯(cuò)

■2)形成兩種重要的流控制

■A選擇重發(fā)ARQ協(xié)議:只重發(fā)出錯(cuò)幀

■B后退N幀ARQ協(xié)議:退回到出錯(cuò)幀

■效率分析公式：E-

■1停等協(xié)議:假設(shè)線路21

不出錯(cuò)，貝!JE二1一P

■如出錯(cuò)概率為P,則2〃+1

■（其中a=tp/tf可理解

為線路的碳計(jì)數(shù)長(zhǎng)圉小7

2a+1

■2選擇重發(fā)ARQ協(xié)議，［i-P（W>2a+Y）

假設(shè)發(fā)送窗口的大〃￡=卬（1-P）(W<2a+1)

為W,則不出錯(cuò)時(shí)為：〔2a+l

■3后退N幀:

------------(W>2a+l)

\-p+np

----P)--------------(W<2a+1)

(2a+1)(1一p+np)

E=-^-(W>=26Z+1)

2ap+l

■當(dāng)W>=2a+1,N近

似等于2a+1,則

W(1—p)

E(w<2a+1)

(2a+1)(1-p+vvp)

■例1：已知數(shù)據(jù)幀長(zhǎng)為1000bit,幀頭為64bit,數(shù)

據(jù)速率為500kb/s,線路傳播延遲為5ms,則

■1）信道無差錯(cuò),采用停等協(xié)議，求利用率

■2）滑動(dòng)窗口為大窗口,求窗口至少為多大？

■3）設(shè)佳9.01，用選擇重發(fā)ARQ協(xié)議，窗口大小

W=4,求利用率.

■解：1）a=Tp/TfTp=5Tf=1064/500

■a=5X500/1064=2.35

E=—

■E=0.f8+1

-2）所謂大窗口就是W>=2a+1,由上面知

a=2.35

■故w>=2X2,35+1=5.7

■取w=6

■3)1~P(W>2?+l)

]p+np

----WQ一P)------(W<2a+1)

(2a+1)(1-p+np)

■P一般比較小,在分母看作為0,故得:

1-P

-----(W>2a+1)

E

W(1-p)

-------<2〃+1)

(2a+1)

■由于w=4,2a+1=5.7,為小窗口,

■W=w(1-p)/2a+1=4X(1-

0.01)/5.7=0.69

5.5協(xié)議

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

協(xié)議的形式描述

■描述方法：

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

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

■②事件狀態(tài)表

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

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

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

■④Petri網(wǎng)模型

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

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

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

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

輸入事件1;輸出事件1輸入事件2

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

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

輸出事件為空

Petri網(wǎng)模型

■德國(guó)CAPetrit提出（1962,博士論

文）o

■4個(gè)基本元素：

■位置：系統(tǒng)可能處于的狀態(tài);用圓圈表

Zj\O

轉(zhuǎn)換

■轉(zhuǎn)換：改變狀態(tài)；用位置弧

■有向弧：位置與轉(zhuǎn)換標(biāo)記

系；用弧線表示。B

■標(biāo)記：系統(tǒng)當(dāng)前處于一一

f1一發(fā)送第0幀

p累42—超時(shí)

3-發(fā)送第1幀

Expect1

接收第1幀4一超忖

5-:c0'：!/.\

6AckK

7一第1幀丟失

Process18一丟棄第0幀

接收9一丟棄第1幀

10一接收第0塊

Expert0111

接收第0貞

儲(chǔ)二ChannelReceiver's

statestatestate

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

■分類:

廠異步型（等待式協(xié)議）

數(shù)據(jù)鏈路層協(xié)議3廠面向字符（BSC,ARPADLC）

＜同步型＜面向字節(jié)計(jì)數(shù)（DDCMP）

L面向比特(HDLCSDLC,

ADCCHLAPB,…)

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

■1976年，ISO提出HDLC（High-levelData

LinkControl）

■適用范圍：

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

■三種類型的站：

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

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

控、

■差錯(cuò)恢復(fù)等）；

■夢(mèng)：主要功能是接收命令，發(fā)送響應(yīng)，配合主

站完成鏈路的控制；

■基盒單工同夏堂圭、人達(dá)站功能，既發(fā)送又接收命

令和而應(yīng).辛傳煮整個(gè)銖路島麻由1c

HDLC的鏈路構(gòu)型

■非平衡配置

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

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

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

機(jī)命令（B,

主站A<>次站B

-------響應(yīng)（B）-------

多點(diǎn)式

HDLC的鏈路構(gòu)型

■平衡配置

■復(fù)合站具有主站和次站的功能。地位

平等。

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

命令（B）

響應(yīng)（A）

點(diǎn)—點(diǎn)式

HDLC的基本操作模式

■正規(guī)響應(yīng)模式NRM：

■