第3章數據鏈路層

*3.1數據鏈路層概述

3.2成幀與幀定界

3.3差錯檢測與校正方法

3.4差錯與流量控制協議

3.5協議描述與驗證

3.6數據鏈路層協議案例

12012SPLENG

3.1數據鏈路層概述

-鏈路層模型

網絡層卜參W網絡層

本地連接

網絡層

3.1數據鏈路層概述

■DL面臨的環境

發送方接收方

可能裝入太快

取出跟不上網絡層

網絡層■

SAP取

數據鏈路層|數據鏈路層

幀幀

SAP<H>SAP

物理層物理層

信道有噪聲，

bits可能出錯

2012SPLENG

3.1數據鏈路層概述

■鏈路層模型物理層

實現了把比特傳輸轉換成信號

傳輸、進入信道。

網絡層

需要把一個個分組送到對方網

絡層

鏈路層

組織一個個分組，用比特傳輸

實現逐個分組的傳輸和接收

4傳輸信號2012SPLENG

3.1數據鏈路層概述

-鏈路層的基本任務

Service（月艮務）

為上面的實體提供分組傳輸服務

LinkControl（鏈路百空制）

雙方通過配合，實現：〉

鏈路的使用規則，流量控制、匯聚分發等

ErrorContix）l（差錯控制）

發送：組織DU（frame）,方便對方檢查錯誤

、接收：檢測DU是否出錯，DU出錯的處理

Framing（幀同步）

發送：轉換成特定的bit傳輸形式，將Frame送出〉

、接收：界定每個frame的位置，取出frame

mmmmmmmwmiinAsynchronous

Synchronous

BIOCR012SPLENG

3.1數據鏈路層概述

■鏈路層任務模型

NetworkLayerDU可用的通信功能DU

62012SPLENG

3.1數據鏈路層概述

■鏈路層效率定義

■鏈路層

■有效數據率r=WiVT(ni；第i幀bit數，T：測量

總時間)

■物理層

■信道的速率Rb/s

■鏈路層效率：7]=r/R(7]W])

路

—Minm-M

72012SPLENG

LinkLayerServices

■三種服務的示意圖

連接請求

一一

FrameFrame_-----------

連接確認

?Frame

二_ack-

拆除請求

無確認無連接有確認無連接―------------一

^-—

拆除確認

有確認面向連接

2012SPLENG

LinkLayerServices

■三種可能的服務

■無確認的無連接服務

■無需對方許可，直接向對方發送Frame,對方不需要反饋確認信息

■優點：不受等待確認的拖累；缺點：frame傳輸可靠性不高

■信道效率：不等待確認，可提高信道效率，但傳輸出錯降低信道效率

■協議考慮：PDU中含源/目的地址

■有確認的無連接服務

■無需對方許可，直接向對方發送Frame,需要對方反饋確認信息

■優點：通過重傳增加了可靠性；缺點：受等待應答的拖累

-保持發送和確認間的正確對應關系所采取的措施會大大降低信道使用效率

■協議考慮：PDU編號，PDU中含源/目的地址、單幀確認，差錯檢

測與重傳

-有確認的面向連接服務

■需事先與對方溝通，雙方建立起一套復雜的發送、確認機制來實現恢復差

錯、排除重復、維持順序的可靠通信

■適合于有大量Frame傳輸的場合

■協議考慮：PDU編號、確認、差錯控制（丟棄錯幀和重復幀，請求

重發錯幀）

92012SPLENG

3.2成幀Framing穗

-成幀（或幀同步）：就是確定幀的界限（起與港

?通俗理解：

■發送方：在幀的前后各加入事先商定好的標記

-接收方：在bits中尋找標記來識別幀的起與止

■需要特別考慮：

-若數據與幀的起止標記相同時，發送方必須采取措施

-否則可能會引起接收方的誤斷

■成幀方法：「如何分黨:"一個

■字符計數法

■字符填充首尾界定法11010110100101101100111101

■位填充首尾界定法11100101010111000101010010

11010101011011010100100100

■物理層編碼違例法

102012SPLENG

成幀

-不同傳輸方式下的幀同步N

?同步傳輸方式（Sync,連續bit流）

■連續的bit流傳遞離散的Frame

■每個Frame都成為連續bit流中的一段，接收方識別并取

出Frame

■異步傳輸方式（Async,異步字節序列）

■每個Frame轉換為異步字節序列傳送，接收方收集字節

序列，還原Frame

■數據塊傳輸方式（Block）

■每個Frame形成一個數據塊傳送。

112012SPLENG

Sync信道的幀同步技術

■連續的bit流由若干Frame和它們間的空閑bit組成

■注意：frame中或空閑的bit都只有兩種取值：。或1

-關鍵問題：如何正確識別和提取bit流中的Frame部分？

■思路：假設空閑bit用某種特殊的bit模式(pattern)構成，而

Frame幣不會由現該pattern,則接收方就能夠正確設別和提

取Frame

■但：應該允許Frame包含任意數據，就肯定包含了這種Pattern。

■若能對Frame中出現的Pattern用某種變換方式消除，接收方提

取由Frame后，再通過反交換，恢復原來的Frame,該假設成

12特殊pattern2012SPLENG

Sync信道的幀同步技術

開始

■發送

開始■接收*檢測pattern

*否

發現

明描Framd

是Frame開始

*

否發現H存儲數據

是檢測

■pattern

Pattern變換

否發現

是Frame結束

否選擇

Pattern復原Frame

是■“易于變換

是

?■易于檢'測繼續

發送Frame，

■■易于反變換否

*

13結束士,LENG

Sync信道的幀同步技術

■位填充首尾定界法（’0'比特插入/刪除技術）奪

■Pattern=mi1111（r稱為定界標志F（Flag）

■Frame內F的變換和反變換（利用F中連續6個‘17的性

質）

■變換：

■Frame中如果出現連續5個'工，時，插入一個'0，

■提取

■從第一次出現非F開始，到重新出現F時的所有bit

■反變換

■Frame中出現連續5個時，刪除后面的1個'0，

■采用0工工工工工10的特點：

■變換與發送合一：發送連續5個加發一個'0，

廠接收與復原合一：連續接收5個V,下一bi曜楚”妒則

_____上-_」、?_t______I_____-r-tr___________、a、、._」LI_、r、__一__■____■_■_■_■_■___t______I,、、____

成幀

位填充首尾定界法

發送：在幀體部分出現連續5個1,無條件地插入一個0

01111110001010111101111101010111118111001001111110

接收：在幀體中掃描連續5個1,無條件去掉后面的0

00101011110111110101011111011110010

IMH1^'

152012SPLENG

位填充首尾定界法

■位填充（實現示意圖）

幀體幀體

__________________入__________________,____________入____________

...01111110011111101001111010110101010111111010101110101110111111001111110...

...01101010...

F檢測結果△

接收"0”bit

幀提取

刪除移位寄存器

2012SPLENG

位填充首尾定界法告滑

■軟件模擬

■intSend(char*pF,intLen){

■inti,j,c,msk,sn;

■sn=0;

■for(i=0;i<Len;i++){//循環幀的字節長度

■msk=1;

■forQ=0;j<8;j++){//8bit

■c=pF[i]&msk?l:0;測試第jbit

■msk<<=1;準備測試下一bit

■Xmitb(c);sn++;

■if(c)cnt++;elseent=0;//計算連續1的個數

■if(ent==5){Xmitb(O);ent=O;sn++;}

■)

■)

■returnsn;//回送發送總bit數

"假定函數Xmitb(c)：向信道發送c(1bit)2012SPLENG

Async信道的幀同步技術

■描述

■以字節(8bit)為單位的傳輸方式

■逐字節傳輸實現Frame傳輸

■幀同步討論

■Frame間留有足夠的時間間隔，以區分各個Frame

■對Frame傳輸能力有較大的影響

■Frame間的時間間隔不夠大，幀與幀區分易出錯

■兩種典型幀同步技術

■字節計數法

■字符填充首尾定界法

□口□□□口陽州口門口miyjUiyi

成幀——字符計數法

■也可稱為字節計數法

-假設一個字符由8位二進制數表示

■基本思想

-在幀頭的第1個字節指明幀內的字節數

■問題

■字節計數值可能在傳輸中出錯（被篡改）

■簡單、不可靠

DATA11101010001011100101010101011101010101011

發送0000010)1110101000101110000001100101010101011101010101011

I錯

接收1110101000101110000001100101010101011101010101011

192012SPLENG

字符填充首尾定界法

■思想

■與同步方式的位填充類似，不同的是以字節為單位

■方法：“定界字符”

■在幀體的前后都用某個特定的字節加以“定界”

■幀體中也可能出現該定界字符，通過變換消除

■接收時提取Frame后，通過反變換復原

■局限性：數據的長度總是以字符或其倍數為單位

■定界字符：F(Flag)=01111110

第曾第2幀

A

(\

麗麗匹

PLENG

字符填充首尾定界法1等移

-將F變換為某個其它字節(x)存在問題：下

■幀體中其它字節也可能出現X,反變換X9F時就出錯

■Frame體中定界字符的變換方法

■一字節到兩字節的變換,變換后幀體中不出現F

■幀體中的F和x都需要變換：F-^xy;x^xz

■y和z是另外選取的兩個字符，對y、z不再需要變換

■分析

■若幀體中出現xy

■變換：xy^(xz)y；反變換：xzy—xy,正確復原

■可以驗證：對幀體中出現F,x,y,z的任意順序的組合，只

對其中的所有F和x進行變換，反變換時都能正確復原

212012SPLENG

字符填充首尾定界法

■處理幀體內的特殊字符(RFC工662,異

步PPP)

■F=01111110(7e),定界字符

■X=Oinn(H(7d),稱為轉義字徉------^B=Frame[i++]

■y=01011110(5e)

■z=01011101(5d)

幀體

幀體填充后

22

I

練習

■分兩組：一組成幀，一組提取幀,

■分別用位填充法、計數法、字符填充法進行練習

■F=01111110,X、V、Z可自行定義

■可自定義若干幀來完成該練習

幀1:1001111111100000010111010100001001100011

幀2:110110110000000001100111

幀3:11000101111111111101001011011111

■思考

■字符填充法中，僅用F和x是否能夠實現，如能實

現，給出實現方法，如不能實現，請說明不能實

現的理由

232012SPLENG

字符填充首尾定界法

FLAG有效載荷域FLAG

原始字符填充以后

FLAGAESCFLAGB教材

PP.159

AESCBAESCESCB

AESCFLAGBAESCESCESCFLAGB

AESCESCBAESCESCESCESCB

有標志字節作為分界的幀字節填充前后的4個字節序列例子

ENG

塊傳輸信道的幀同步技術

■,

通信方式是塊傳輸方式，每個塊就是一個Frame

■塊傳輸方式

■每個Frame都帶有前導bit序列(preamble)和后續bit序列

(postamble),以確保Frame的實和尾能正確檢測和接收

■因此需要確定：

■Preamble結束和Frame開始的比特位置

■Frame結束和postamble開始的bit位置

■同步技術

■違例編碼法：利用信息bit的碼型特性，用非正常碼型來進行界定位置

postamblepreamble

塊傳輸信道的幀同步技術

■例1：曼切斯特編碼（lb/2b,10M以太網）

o=1=違例J=和K=

■Block=010101JKFramebodyKJ010101

■例2：4b/5b編碼（100M以太網）

■4bit數據映射成5bit碼組

■0000^11110,0001901001,…，1111^11101

■空閑911111,定界符1911000,定界符2f10001

■Block=0UHB］定界符:LFrameBody定界符201010工

■例3：8b/10b編碼（1000M以太網）

■8bit數據映射成工Obit碼組

■從1024個碼組中只需選取256個來代表8bit的各個值

■剩余1024?256個碼組可作為控制、定界等多種功能

262012SPLENG

塊傳輸信道的幀同步技術成幀

校驗和法

■利用ATM信元固定、且長度較短（53字力的

特性

■信元前4字節是頭部，第5字節是校驗和，使用循

環冗余校驗

■設40位寄存器，計算校驗和

■正確則可能發現了一個信元

■不正確則移一位，再次計算，直到得到一個信元

海」信元頭.信元體信元頭■信元體

Ibo

I

3.2成幀一討論與理解

■幀定界正確，請問幀一定無錯嗎？

■一個幀定界出錯，請問

■用字符計數法，后續的幀也不能正確識別嗎？為什么？

■用字符填充法和位填充法，情況又如何？

■位填充法比字符填充法有哪些優越性？

282012SPLENG

Framing小結

■不同的成幀技術以適應信道的不同傳輸體制

■需求：

■接收方易于提取、出錯時對后續幀的提取影響小

■較高的信道利用率、較簡單的實現

■位填充、字符計數、字符填充、違例編碼、校驗和

■與其它功能的關系

■實現的是信道上傳輸和接收幀的功能，不涉及幀的內容

■鏈路層其它功能直接對幀的處理，不受傳輸體制影響

292012SPLENG

3.3差錯檢測與糾正

■信道傳輸過程中（誤碼：；Of）

■隨機干擾：隨機錯（均勻性）

■突發干擾：突發錯（一定的突發長度）

■出錯處理

■檢錯：驗證是否出現了誤碼

■糾錯：找到誤碼的位置，糾正之

原碼

...01111110011111101001111010110101010111111010101110101110111111001111110...

出錯后3III

0111111001111101001111101101010101111101010111010111111111001111110...

Bit錯可能造成：

幀體錯——幀錯誤

定界錯——幀錯誤、幀丟失、多余幀

信道異常（多于個信道失序

3061）-----2012SPLENG

3.3差錯檢測與糾正

■如何理解數據傳輸中的差錯？

■一位錯就等于全幀錯

■關于誤碼率Pb與誤幀率Pe

■假設

-幀長度為N比特，誤碼率為Pb（設每比特出錯獨立）

■則

■比特正確率為：1-Pb

■N比特正確率為

（1-Pb）'

-幀出錯率（誤幀率）（一幀中至少一位錯）為

N

Pe=1-（1-Pb）?NPb（幀出錯的概率與幀成近似成正比）

312012SPLENG

3.3差錯檢測與糾正

■差錯控制，意味著：

-首先檢測出差錯

-然后是糾正差錯

■檢測差錯

■采用冗余編碼技術進行差錯檢驗編碼

■糾錯碼：不僅能檢測差錯，且能知道錯在哪兒

■檢錯碼：只能檢測差錯，但不知錯在哪

■糾正差錯

■前向糾錯FEC(ForwardErrorCorrection)

■用糾錯碼，收方檢錯并自動糾錯

■自動請求重發ARQ(AutomaticRequestforRepeat)

■用檢錯碼，收方檢錯通知發方重發恢復差錯

、-計算機網絡中常采用

322012SPLENG

3.3差錯檢測與糾正

?假設

■待傳數據為m位

■為檢測差錯，所需要的冗余位（校驗位）為r位

■則

■傳輸碼長度n=m+r

■通常采用糾錯碼或檢錯碼，即：

■按某種算法計算出校驗位

■然后將m位數據和r位校驗碼形成傳輸碼

■接收方根據相同的算法重新計算校驗位，判斷是否出錯

332012SPLENG

3.3差錯檢測與糾正

■一種直觀簡單的糾錯方法

■每個bit重傳三次：1^111;0^000

■如果3bit中有工bit錯，我們可以糾正過來

■101、110>0111111

■001、010、100900090

■如果3bit中有2bit或3bit全錯，則無法糾正了

■101今111?000?無法知道是:Lbit還是2bit錯

■將每個bit重傳2n+l次，n越大，糾錯能力越

強（傳輸效率越低）

■不管n如何取，我們仍不知道是否真的糾正了錯誤，

34只能認為增大了糾正錯誤的概率如2SPLENG

3.3.1糾錯碼海明碼

■海明距離(HammingDistance)教材P16^^63

■兩個等長碼對應位不同的個數，稱作這兩個碼的海明距

離

■例：0001111和0001100的海明距離為2

■某種編碼的任意兩個有效編碼之間的距離稱為該編

碼的海明距離

■結論1：檢出d個錯誤的檢錯碼，海明距離至少為d+工

■結論2：糾正d個錯誤的糾錯碼，海明距離至少為2d+：L

海明碼是一種能糾正一位錯的糾錯碼

352012SPLENG

3.3.1糾錯碼

■假設

■數據為m位

■則糾正一位錯的校驗碼「滿足

m+r+l<2r（證明：P163）

■例如:m=3,3+r+l<2rfr=3

■則海明碼碼長=m+r=6位

■海明碼的編碼為r與m的混排方式，規則為：

■檢驗位r的序號為2的整次幕1,2,4,8,……

■信息位m的序號為2的非整次寨，3,5,6,7…

■rlr21113r4m51Tl62012SPLENG

3.3.1糾錯碼一海明*

?假設數據為OIL該如何確定海明編碼?

■編碼應為：rlr21Tl3r41Tl51Tl6

■現已知：m3m5m6=011

-關鍵是確定rl、r2和r4

■「的計算方法

■首先找出哪些與rl、r2和r4相關的數據位

■將數據位數拆成2的整次塞相加

-如3=1+2fm3與r1和r2相關

■然后將與某r相關的數據位模2加（異或），結果為該r值

■與「工相關的數據位：m3、m5則「工=0十1=]

■與「2相關的數據位：m3、m6WiJr2=0?l=l

■與r4相關的數據位：m5>m6則=4=1十1=0

■得出：011的海明編碼為工10011

372012SPLENG

3.3.1糾錯碼

■已知：011的海明編碼為工工001工（rlr2m3r4m5m

■假設：編碼在傳輸中出了一位錯

■110011錯成110010

■接收方的糾錯規則

-首先：對于每個ri,將ri和與之相關的數據位進行依次異或

■結果為1,則記錄Ai=i（i為r的序號）

■結果為0,則記錄Ai=O

■然后累加，計算ZAi的值，結果等于幾就是該對應位出錯

■最后，將出錯位取反進行糾錯

■計算過程

■rl?m3十m5=l?0?1=0Al=0

■r2?m3十m6=1十0十0=1A2=2

■r4?m5?m6=0?1?0=1A4=4

■出錯位：SAi=Al+A2+A4=6

■晶I錯：110010—110011（差錯位取反）2O12SPLENG

3.3.2差錯檢測

■采用冗余編碼技術進行差錯檢驗編碼

■基本思想

■發送方：將待發數據按照某種規則加上一定的冗余位后,

進行傳輸，

■接收方：對收到的數據進行判斷，是否符合原規則，若

符合則無錯，不符合則出錯。

發送方接收方

線路傳輸

校驗C(x)=R(x)

無錯

計算校驗仍

計算校駛用I

C(x)#R(x)

7出錯

校驗碼R(x)C(x)R(x)

392012SPLENG

3.3.2差錯檢測一一檢錯碼

■奇偶校驗碼

■循環冗余碼CRC

■校驗和編碼

402012SPLENG

3.3.2差錯檢測一一奇偶校驗碼

■增加冗余位使信息碼中的“工”的個數為奇數或偶數

■奇校驗：“1”的個數為奇數

■偶校驗：的個數為偶數

■具體實現：信息位逐位進行模2加I（異或運算）

■al十a2十a3十a4十a5

■結果為0,偶校驗時校驗位為0,奇校驗時，校驗位為1

■結果為1,偶校驗時校驗位為1,奇校驗時，校驗位為0

■例信息字段奇校驗碼偶校驗碼

01100101100100110011

出錯為：001001,0、001001A

重新計算校驗和:

★

41不同則出錯2012SPLENG

糾正突發錯

數據組織成矩陣,

■發送時按列發送

■出現突發錯誤時，可按行糾正

1加101嗯01010

0D10110001001

100101001010

01001001000010

111010^1010101

422012SPLENG

3.3.2差錯檢測循環冗余碼蒸

■循環冗余碼(CRC:1011010

CyclicRedundancy

Code)教材p165~167

-對任意位二進制流，補充，000000(

m11000101

r個011100010模2力口

■用規定的r+1位除數進行求11000101

余計算，得到r位效驗碼01001110

00000000

■數據與r位效驗碼組成傳輸10011100

碼組11000101

-發送出去10110010

11000101

"TTTlHTnr

11000101

0101011(

m位數據0000000(

1010110

432012SPLENG

3.3.2差錯檢測一循環冗余碼

10110101010110

CRC校驗

■對收到的完整的數11000101I1011010101011C

據幀用發送方相同I11000101

11100000

的r+1位除數進行求11000101

余計算01001011

00000000

■余數為0則無錯10010110

11000101

10100111

11000101

11000101

11000101

0000000Q

0000000(1

000000。

442012SPLENG

3.3.2差錯檢測循環冗余碼管

■基于任何一個二進制位串組成的代碼，都可以與系

數只為0和1的多項式建立一一對應的關系。

■一個K位的數據可以看成是從xKT?X。次系數為。和

1的多項式

X4X3X2X1X0

數據:11011

多項式X4+x3+x+1

452012SPLENG

3.3.2差錯檢測循環冗余碼鋤

■1)基本思想：

■設：數據m位，對應多項式M(x),校驗碼為r位，對應多項式R(x)

■給定：生成多項式G(x),階數為r,r+1位，高位和低位系數為1

■發送方：將M(x)通過G(x)計算出帶校驗和的傳輸多項式T(x)

-接收方：將收到的帶校驗和的多項式T'(x)除以G(x),如有余數，

出錯，能除盡，無錯

■2)校驗碼與傳輸多項式的計算

■STEP1在m位數據之后加上r個0,數據位變成m+r位，對應多項式

X「M(X)

■STEP2計算校驗碼多項式：xrM(x)/G(x)(對應二進制位串模

2除)，余數為校驗碼，對應多項式為R(x)

■STEP3計算傳輸多項式：T(x)=xrM(x)+R(x),對應系

數位串為傳輸數據

★

462012SPLENG

3.3.2差錯檢測一循環冗余工

示例：數據：110110

■G(x)=x4+x+1對應位串工001工(除數)

■在數據后加4個0形成1101100000被除數，求余數

校驗：

110口11110011

100111101100000100111101100101

C1001110011

v

—?1000010000

1001110011

1100011010

1001110011

1011010011

1001110011

01010~

傳輸代碼（CRC碼）為：1101100101余數為口，表示校驗正確

472012SPLENG

3.3-2差錯檢測——冗余循環碼疆

■值得注意：

■多項式變為碼字時，首位對應最高次，中間的“0”不能丟

掉

■在計算中涉及的和均為模2運算（加、減結果一樣,

異或運算，相同為0,相異為工）

■模2除商工的原則：只要被除數的首位為工，且位數與除數相

同則商工，如上例中紅色雙向箭頭處（被除數為10000,除

數為1001工）

482012SPLENG

3.3-2差錯檢測——冗余循環碼耀

■CRC碼的檢錯性能（r個校驗位比特）

■所有單個錯

-所有2bit錯

-所有長度小于或等于r個bit的突發錯

■長度為r+1個比特的突發錯，漏檢率為：1/2^

■長度大于r+工比特的突發錯，漏檢率為：l/2r

■校驗和的計算一般都用硬件實現，有參考電路，也可用軟件

實現。硬件計算時是邊發邊計算，故通常校驗和在幀尾。

■常用的CRC多項式：

■CRC-8=x8+x2+x+1

■CRC-12=x12+x11+x3+x2+x+1

■CRC-16=x16+x15+x2+1

■CRC-CCITT=X16+x12+x5+1

■CRC-32

492012SPLENG

3.3-2差錯檢測——校驗和

■校驗和Checksum

■C語言：for(i=0;i<N;i++)Sum+=W[i]；

■基本思想：

■按一定大小進行累加

■累加結果產生進位，將進位累加到結果中

■最終累加結果取反，獲得校驗和

數據(16進制)ca73Oc1eca722201

計算16位校驗和ca73+Oc1e=d691

d691+ca72=1a103

1a103+2201=1c304

checksum=c304+1=3cfa

校驗后的數據：ca73Oc1eca7222013cfa

校驗=1+c304+3cfa=1+fffe=02012SPLENG

ErrorControl小結疆

-檢錯算法

■CRC,二進制異或除法，除數選擇重要

■Checksum,模65536力口法，軟件實現

■幀末尾附加了r-bit檢錯碼（也稱校驗碼）

-檢錯能力

■r越大，檢錯能力越強

■存在壞幀漏檢的概率

-應用

■發現并丟棄傳輸中出現的壞幀，保證繼續處理的幀基

本上是正確的

Frame校驗碼

作業4

1、請寫出通常采用的成幀方法及各種成幀法淵

點。假設幀標記符出錯，請問哪種成幀方法將

不能檢測到后續所有的幀？為什么？

2、如果待傳數據為1111111000111111,假

設采用“位填充法”成幀，請寫出幀內容。

3、假設待傳數據為100101,(1)計算校驗位r

的位數；(2)計算出傳輸該數據的海明碼

(要求步驟)

4、假設待傳數據為100101,采用CRC編碼，假

設生成多項式為G(X)=X4+1,計算出校驗

多項式R(X)o

522012SPLENG

3.4差錯與流量控制協議

■在計算機網絡中，差錯控制方式通常采用

自動請求重發（ARQ）

■ARQ基本思想：

-采用檢錯碼進行檢錯

■丟棄出錯的幀

■請求重傳出錯的幀■ARQ是一種保證PDU可靠傳輸的技術

■可用于各層協議中，不僅僅限于數據鏈路層

■對幀進行確認

■例如：

■典型的ARQ協議■X.25網絡的網絡層、數據鏈路層

■TCP/IP網絡中的傳送層

-停等協議

■回退N協議

-選擇性重傳協議

532012SPLENG

3.4差錯與流量控制協議

■3.4.1停一等協議

■3.4.2連續發送的滑動窗口協議的概念

■3.4.3回退N協議

■3.4.4選擇性重傳協議

■3.4.4雙向傳輸時的確認

■3.4.4流量控制

542012SPLENG

34?工停一等協議

■停一等協議：stopandwaitprotocol

■基本思想：

■每發送一個幀（PDU）,停下來等確認（應答）

-收到肯定應答，發送下一個新幀（PDU）

-收到否定應答，重發上次的幀?數據鏈路層的

鏈路層鏈路層PDU也稱為幀

?后續討論中幀

和PDU等同

網

絡

層

552012SPLENG

3.4,停一等協議

協議需要考慮以下情況

■幀丟失，將導致：

■接收方收不到PDU

-發送方收不到應答（ACK或NAK）

■應答丟失，將導致：

-發送方收不到應答（ACK或NAK）

■解決辦法：設置定時器T,超時重發

T

重傳

□重傳

562012SPLENG

3?4?1停一等協議

■還有問題要解決：

■連續丟失問題

■重發后仍收不到應答或接收方仍收不到PDU,一直重發下去?

-解決辦法：設置重發次數Nmax

■重復收幀問題

■ACK丟失，重發PDU,接收方收到重復幀而不知道

-措施：為PDU編號（01即可區別）

PDU

TT

重傳新重傳重復PDU

PDU?丟棄

PDU無編號PDU有編號

會出錯不出錯2012SPLENG

3?4?1停一等協議

■還有問題要解決：

■過早超時問題

■重發定時器T在應答到達發送方之前就超時

-導致接收方正確收到PDU,而發送方仍然重發

■如果過早超時，且ACK無編號，則

■出現發送PDU出錯

■措施：對應答編號

■請同學自己分析以下情況：

重復PDU

■過早超時，但和都編號時,

PDUACK丟棄

停等協議將如何工作？

發送方誤以為是對PDU

(1)的應答，故下一