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

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

5.1基本概念

■鏈路：一條無源的點到點的物理線路段。

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

輸）。

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

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

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

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

學習重點:兩臺機器之間實現(xiàn)可靠、有效的

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

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

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

地方；

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

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

錯；

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

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

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

設(shè)計要點；1）向網(wǎng)絡層提供一個定義良好的服務接口

2）處理傳輸錯誤

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

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

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

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

標機器的網(wǎng)絡層.

①無確認的無連接的服務：（P56）

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

②有確認的無連接的服務：

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

③有確認的面向連接的服務：

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

5.1.3成幀方法

①字符計數(shù)法：

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

問題：由于傳輸差錯導致計數(shù)值被“篡改”；

CharactercountOnecharacter

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

(a)51|2345671898|01234j5687890123

Frame1Frame2Frame3Frame4

5characters5characters8characters8characters

第1幀第4幀

5個字符Error第2幀的計數(shù)值出錯8個字符

(b)5123476789801234

Frame1Frame2Nfwa被誤認為是第3幀的計數(shù)值

(Wrong)charactercount

圖3-3

②字符填充首尾界符法：

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

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

02H、ETX=03H)

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

相同？

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

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

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

幀頭飛二幀尾

插入的DLE

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

(刪除填充的DLE)ADLESTXB

③位填充首尾標志法：

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

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

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

的1時，自動在其后插入一個0；接收方

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

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

I!\\\\\

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

幀頭T_幀尾

填充的位

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

（刪除填充位）01101111111111101111110

5.1.4差錯控制

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

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

(1)熱噪聲：由傳輸介質(zhì)導體的電子熱運

動產(chǎn)生。幅度較小，是產(chǎn)生隨機差錯的主

要根源；

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

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

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

■差錯評價指標如下：

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

之比。

■Pe=Ne/N

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

兀數(shù)。

■(2)誤比特率：

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

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

■差錯控制的基本方式如下：

■(1)反饋糾錯

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

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

止。

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

■(2)前向糾錯

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

并匈正錯誤。

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

■(3)混合糾錯

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

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

5J.5流控制

?基于反饋的流控制

?基于速率的流控制

5.2錯誤檢測和糾正

碼字的檢錯與糾錯能力

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

海明距離：兩個碼字之間對應碼元位的不同

碼元的個數(shù)。

10001001

十10100011

00101010

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

碼字編碼的海明距離

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

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

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

離d。

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

任何t個（或t個以下）的錯誤。

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

任何e個（或e個以下）的錯誤。

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

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

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

碼為1位（偶校驗位）

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

000>011、101>110；

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

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

D>=2t+1

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

D>=e+1

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

誤碼控制編碼的分類

按冗余碼的控制功能分:

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

錯。叫前向糾錯

糾錯檢錯的常用方法

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

率低。

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

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

能力強，廣泛使用。

5.2.1糾錯碼:海明碼

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

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

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

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

r個校驗位：在2k的位置（1、2、4、8、…）；

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

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

例如：4個信息位D1D2D3D4,3個校驗位尸7尸2尸3。

碼位號一＞b1b2b3b4b5b6b7

碼字一尸3lD21D3lD4l

7-

校驗位

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

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

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

■碼字組成：

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

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

\

II位=m位+

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

二進制比特序列多項式：

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

生成多項式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)生成校驗碼；

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

對于多項式的運算：采用模2計算(加法不進位，減法不借

位)；加減法是一樣的。

模2計算即是異或運算。

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

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

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

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

k個比特。

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

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

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

冗余碼的計算

■用二進制的模2運算進行2"乘M的運

算，這相當于在M后面添加。個0。

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

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

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

位，即R是。位。

冗余碼的計算舉例

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

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

■被除數(shù)是101001000o

循環(huá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運算的結(jié)果是：商6?=110101,

余數(shù)R=001o

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

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

即：101001001,共（k+位。

檢測出差錯

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

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

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

個比特出現(xiàn)了差錯。

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

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

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

小。

流行的生成多項式有:

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+/

檢測能力：

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

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

CRC的實現(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

跟著斷開連接。

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

域網(wǎng)中廣泛使用的校驗方法是_(1)_,CRC-16標準

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

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

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

存息碼字是10110,由計算出來的CRC校驗碼是

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

(2)A2B4C16D32

(3)A自動糾錯B報告上層協(xié)議C自動請求重發(fā)D重

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

(4)A0100B1010C0111D1111

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

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

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

面的余數(shù)。

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

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

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

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

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

可靠的傳輸？

■答：作二進制除法，1101011011

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

檢驗序列是1110.

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

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

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

本課重點

■掌握CRC冗余校驗碼的計算.

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

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

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

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

物理鏈路

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

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

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

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

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

（不考慮流量控制問題）

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

層不需要：

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

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

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

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

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

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

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

■初步協(xié)議：

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

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

件檢驗），如果無差錯，回送一個確認幀ACK,否

則,回送一個否認幀NAK。

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

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

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

發(fā)送端接收端

間V\

(a)正常情況

死鎖現(xiàn)象:

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

遠等待下去。如何解決？

解決方法：

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

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

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

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

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

Tout也稱重傳時間

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

若應答幀丟失，按照超

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

重復幀，如何解決？

解決方法：

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

號Ns,如果接收端收到相同序

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

(d)應答幀丟失

個ACK。

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

其它附加控制信息

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

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

個bit);

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

不一樣，

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

~——JL~——?

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

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

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

DID2丟棄重復幀D2D3

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

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

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

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

ARQ協(xié)議:

接收端R<-0

等待<

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

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

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

重傳時間tout的選擇

ou太長，浪費時間,

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

out“額外，，應答幀

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

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

幀序號

接收端_

狀態(tài)序號R

棄

棄

棄

丟

去

去

基

D錯D4

■如何解決？

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

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

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

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

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

總時間-等待時間

信道利用率Cr=

傳送一幀的總時間

忽略應答幀長度和處理時間：

Tf+2Td1+277/C

L

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

示例

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

單程傳輸時延Td=250ms,

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

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

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

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

LIxlO3

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

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

,2Tdecr2X20X10-3X4X103X50%,

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

1-Cr1-50%

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

■目的：提高信道利用率。

■方法：

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

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

時，

■再控制重發(fā)。

■實現(xiàn)要求：

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

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

■常用協(xié)議：

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

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

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

n)

■①方式1：

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

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

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

沖區(qū)。

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

■②方式2：

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

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

器，當收到確認幀后，計時器復位；如果直

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

及后繼的幀。

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

(selectiverepeat)

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

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

幀。

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

間C

重傳

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

暫存于緩存中

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

意圖

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

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

protocol)

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

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

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

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

增大了開銷。

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

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

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

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

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

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

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

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

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

■發(fā)送序號：

■一般采用n位bit進行編號（0?2n-i）o

■若n=3；則用3位bit進行編號（0?7）。

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

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

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

幀。

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

止發(fā)送新的數(shù)據(jù)幀。

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

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

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

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

收哪些幀。

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

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

則,丟棄。

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

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

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

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

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

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

■差錯情況：設(shè)l/l/r=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ā)生重復。

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

幀丟失，因此發(fā)送1號否認幀，讓對方重新發(fā)送

1號數(shù)據(jù)幀。

應鬻產(chǎn)

送

接收端Wr=2

上

廿6溫

回234S67M

M1E34S6"D1

ACKl

56加

%4567RD2

'CK2

Dl.toi擊

居3而4S61

1)1丟棄

QI，國。嗝

應答幀被“篡改”情況:ACK-NAK

送

上

層

DO

D1

D2

D3

D4

一嚴翼貞被“篡改”情況：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)的有效序號出現(xiàn)

重疊。

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

01234567<。酎儂

01234567

ACK07

重發(fā)

012314567kg

回123|4567

A

（重復Dl~3丟棄

01234567

應答幀全部丟失

避免重疊問題

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

/2

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

01234567

01234567

t'out<

重發(fā)

0123^567

0123|4567

丟棄

01234567

應答幀全部丟失

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

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

01234567

012314567

0123|4567

0123|4567

重復幀D0-7

應答幀全部丟失

所以，Ws<2^\.

累積確認方法

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

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

正常情況

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

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

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

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

■在正常傳輸情況下，忽略應答幀長度和處理時

rm.

當人時：Cr^100%

當％$?。＜2，"+?7時：

八Ws?TfWs

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

工"2Td—/

L

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

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

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

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

Ws

由c

l+2Td一

L

令Cr=100%

Hs^2Td—+\

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

濟區(qū)；、

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

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

示例

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

■單程傳輸時延2=250ms,

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

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

rifp

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

qLIxlO3

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

物證砧2Tde2x0.02x56x1()3

數(shù)據(jù)幀長度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。

重難點講解與練習

■1流量和差錯控制

■1)差錯控制方法：

■A自動請求重發(fā)(AutomaticRepeat

Request,ARQ)

■B前向糾錯

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

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

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

■效率分析公式：E-

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

不出錯，貝!JE二1一P

■如出錯概率為P,則2〃+1

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

為線路的碳計數(shù)長圉小7

2a+1

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

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

為W,則不出錯時為：〔2a+l

■3后退N幀:

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

\-p+np

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

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

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

2ap+l

■當W>=2a+1,N近

似等于2a+1,則

W(1—p)

E(w<2a+1)

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

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

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

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

■2）滑動窗口為大窗口,求窗口至少為多大？

■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)機

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

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

■采用表格進行描述。

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

■采用程序代碼進行描述。

■④Petri網(wǎng)模型

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

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

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

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

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

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

生相應的動作，所以

輸出事件為空

Petri網(wǎng)模型

■德國CAPetrit提出（1962,博士論

文）o

■4個基本元素：

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

Zj\O

轉(zhuǎn)換

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

■有向?。何恢门c轉(zhuǎn)換標記

系；用弧線表示。B

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

f1一發(fā)送第0幀

p累42—超時

3-發(fā)送第1幀

Expect1

接收第1幀4一超忖

5-:c0'：!/.\

6AckK

7一第1幀丟失

Process18一丟棄第0幀

接收9一丟棄第1幀

10一接收第0塊

Expert0111

接收第0貞

儲二ChannelReceiver's

statestatestate

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

■分類:

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

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

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

L面向比特(HDLCSDLC,

ADCCHLAPB,…)

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

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

LinkControl）

■適用范圍：

■計算機一計算機、計算機一終端、終端一終端

■三種類型的站：

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

理應，負責整個鏈路的控制（如系統(tǒng)的初始、流

控、

■差錯恢復等）；

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

站完成鏈路的控制；

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

令和而應.辛傳煮整個銖路島麻由1c

HDLC的鏈路構(gòu)型

■非平衡配置

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

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

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

機命令（B,

主站A<>次站B

-------響應（B）-------

多點式

HDLC的鏈路構(gòu)型

■平衡配置

■復合站具有主站和次站的功能。地位

平等。

適合于計算機和計算機之間的連接

命令（B）

響應（A）

點—點式

HDLC的基本操作模式

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

■