1、第三章 數(shù)據(jù)鏈路層,數(shù)據(jù)鏈路層功能 差錯(cuò)檢測(cè)和糾正 數(shù)據(jù)鏈路協(xié)議 協(xié)議描述與驗(yàn)證 鏈路通信協(xié)議舉例, 3.1 數(shù)據(jù)鏈路層功能,基本功能：,將物理層提供的原始的傳送比特流的可能出錯(cuò)的物理連接改造成為邏輯上無(wú)差錯(cuò)的數(shù)據(jù)鏈路。 最基本的服務(wù)就是將源機(jī)器網(wǎng)絡(luò)層來(lái)的數(shù)據(jù)可靠地傳輸?shù)较噜徆?jié)點(diǎn)的目標(biāo)機(jī)網(wǎng)絡(luò)層 。, 3.1 數(shù)據(jù)鏈路層功能(續(xù)),要完成的特定功能： 主要有如何將比特組合成幀（frame） 處理傳輸中出現(xiàn)的差錯(cuò) 鏈路管理即管理數(shù)據(jù)鏈路層連接的建立、維持和釋放，調(diào)節(jié)發(fā)送方的發(fā)送速率不至于使較慢的接收方不能承受,3.1.1 幀同步,字節(jié)計(jì)數(shù)法 字符填充法 比特填充法 違例編碼法,3.1.1 幀同步(

2、續(xù)),1.字節(jié)計(jì)數(shù)法,一個(gè)字符流(a) 無(wú)差錯(cuò)(b)有一個(gè)差錯(cuò),3.1.1 幀同步(續(xù)),2.字符填充的首尾定界符法,(a) 有標(biāo)志字節(jié)作為分界的幀 (b) 4個(gè)字節(jié)填充前后的字節(jié)序列的例子,3.1.1 幀同步(續(xù)),3.比特填充的首尾標(biāo)志法,(a) 原始的數(shù)據(jù) (b) 線路上的數(shù)據(jù) (c) 刪除填充之后存儲(chǔ)在接收方存儲(chǔ)器中的數(shù)據(jù),3.1.1 幀同步(續(xù)),4.違例編碼法,在物理層采用特定的比特編碼方法時(shí)采用。 如曼徹斯特編碼方法中，將數(shù)據(jù)比特1編碼成高-低電平對(duì)，而將數(shù)據(jù)比特0編碼成低-高電平對(duì)。高-高電平或低-低電平對(duì)在這里是違例的，可以借用這些違例編碼的序列來(lái)界定幀的開(kāi)始和結(jié)束。,3.1

3、.2 差錯(cuò)控制,由差錯(cuò)控制碼產(chǎn)生的校驗(yàn)和可以檢查出一幀在傳輸中是否發(fā)生了錯(cuò)誤。一旦檢查出錯(cuò)誤后，通常采用反饋重發(fā)的方法來(lái)糾正錯(cuò)誤。 實(shí)現(xiàn)復(fù)雜一點(diǎn)的機(jī)制，要用： 保留己發(fā)的幀：以便出錯(cuò)后重發(fā) 計(jì)時(shí)器 (timer)：避免無(wú)限等待 幀編號(hào) ：保證每幀最終都能正確地交付給接收方網(wǎng)絡(luò)層一次,3.1.3 流量控制,流量控制處理的是發(fā)送方發(fā)送能力大于接收方接收能力的問(wèn)題，其實(shí)際是要控制發(fā)送方的數(shù)據(jù)流量。 數(shù)據(jù)鏈路層控制的是相鄰兩節(jié)點(diǎn)間數(shù)據(jù)鏈路上的流量，以后再運(yùn)輸層中講的是控制從源端到目標(biāo)端間的端對(duì)端流量。,3.1.4 鏈路管理,無(wú)確認(rèn)的無(wú)連接服務(wù) 有確認(rèn)的無(wú)連接服務(wù) 正向應(yīng)答 反向應(yīng)答 雙向應(yīng)答 有確認(rèn)的

4、面向連接服務(wù),3.2差錯(cuò)檢測(cè)和糾正,為什么需要差錯(cuò)檢測(cè)？,有如下原因造成信號(hào)幅度、頻率和相位的衰減或畸變（又稱(chēng)為失真）： 線路本身電氣特性造成的隨機(jī)噪聲(熱噪聲)影響 電信號(hào)在線路上產(chǎn)生反射造成的回音效應(yīng) 相鄰線路間的串?dāng)_以及各種外界因素（如大氣中閃電、開(kāi)關(guān)的跳火、外界強(qiáng)電流磁場(chǎng)的變化和電源的波動(dòng)等）,3.2 差錯(cuò)檢測(cè)和糾正(續(xù)),差錯(cuò)： 數(shù)據(jù)通信中，前面的原因就會(huì)造成接收端收到的二進(jìn)制數(shù)位（或稱(chēng)為碼元）和發(fā)送端實(shí)際發(fā)送的二進(jìn)制數(shù)位不一致 什么是差錯(cuò)檢測(cè)與校正？ 在實(shí)用的通信系統(tǒng)中一定要能發(fā)現(xiàn)（檢測(cè)）這種差錯(cuò)。 能采用措施糾正（校正），把差錯(cuò)控制在所能允許的盡可能小的范圍內(nèi)。,3.2 差錯(cuò)檢測(cè)

5、和糾正(續(xù)),傳輸差錯(cuò)的特性 常用的檢差碼循環(huán)冗余碼 海明碼,3.2.1 傳輸差錯(cuò)的特性,噪聲分類(lèi)： 信道所固有的，持續(xù)存在的隨機(jī)熱噪聲。 可引起隨機(jī)性差錯(cuò) 由于外界特定的短暫原因所造成的沖擊噪聲。 可引起突發(fā)性差錯(cuò) 噪聲比較： 隨機(jī)錯(cuò)通常較少 沖擊噪聲的幅度可以相當(dāng)大 ，它是傳輸中產(chǎn)生差錯(cuò)的重要原因,3.2.1 傳輸差錯(cuò)的特性(續(xù)),Pe誤碼率,衡量一個(gè)信道質(zhì)量的重要參數(shù)是誤碼率， 通常用10的負(fù)若干次方來(lái)標(biāo)志信道的誤碼率Pe。,3.2.1 傳輸差錯(cuò)的特性(續(xù)),差錯(cuò)控制編碼的原理：,信息位：要發(fā)送的數(shù)據(jù) 冗余位：在向信道發(fā)送之前，先按照某種關(guān)系加上一定的冗余位 發(fā)送與接收的過(guò)程： 發(fā)送時(shí)：

6、信息位+冗余位構(gòu)成碼字發(fā)送； 接收時(shí)：收到碼字后查看信息位和冗余位，并檢查它們之間的關(guān)系（校驗(yàn)過(guò)程），以發(fā)現(xiàn)傳輸過(guò)程中是否有差錯(cuò)發(fā)生。,3.2.1 傳輸差錯(cuò)的特性(續(xù)),差錯(cuò)控制編碼分類(lèi)：,檢錯(cuò)碼:能自動(dòng)發(fā)現(xiàn)差錯(cuò)的編碼 糾錯(cuò)碼:不僅能發(fā)現(xiàn)差錯(cuò)而且能自動(dòng)糾正差錯(cuò)的編碼,3.2.1 傳輸差錯(cuò)的特性(續(xù)),衡量編碼性能的參數(shù) 編碼效率R :就是碼字中信息位所占的比例。 若碼字中信息位為k位，編碼時(shí)外加冗余位為r位，則編碼后得到的碼字長(zhǎng)為n = k + r位。,判定規(guī)律：編碼效率越高，即R越大，則信道中用來(lái)傳送信息碼元的有效利用率就越高。,3.2.1 傳輸差錯(cuò)的特性(續(xù)),差錯(cuò)控制基本形式,(1)自動(dòng)

7、請(qǐng)求重發(fā)ARQ （Automatic ReQuest for Repeat),只需少量冗余碼就能獲得很低的誤碼率，檢錯(cuò)效果較好。但必須有反饋信道，信道干擾大時(shí)，效率會(huì)降低。,3.2.1 傳輸差錯(cuò)的特性(續(xù)),(2)前向糾錯(cuò)FEC (Forward Error Correction),無(wú)需反饋信道，能用于單向通信，但FEC差錯(cuò)控制碼與信道的差錯(cuò)統(tǒng)計(jì)特性有關(guān)，傳輸效率不高。,3.2.1 傳輸差錯(cuò)的特性(續(xù)),除非在單向傳輸或?qū)崟r(shí)要求特別高（FEC由于不需要重發(fā)，實(shí)時(shí)性較好）等場(chǎng)合外，數(shù)據(jù)通信中使用更多的還是ARQ差錯(cuò)控制方式。 也可以將上述兩者混合使用，即當(dāng)碼字中的差錯(cuò)個(gè)數(shù)在糾正能力以內(nèi)時(shí)，直接進(jìn)

8、行糾正；當(dāng)碼字中的差錯(cuò)個(gè)數(shù)超出糾正能力時(shí)，則檢出差錯(cuò)令其重發(fā)來(lái)糾正差錯(cuò)。,3.2.2 常用的檢錯(cuò)碼CRC,1.奇偶校驗(yàn)碼,(1)偶校驗(yàn),奇偶校驗(yàn)碼是通過(guò)增加冗余位來(lái)使得碼字中“1”的個(gè)數(shù)保持奇或偶數(shù)的編碼方法。 如信息組中各碼元為I1,I2,I3,I4, ,In， 則發(fā)送的信息組碼元是I1,I2,I3,I4, ,Inr,(2)奇校驗(yàn),3.2.2常用的檢錯(cuò)碼(續(xù)),只能檢測(cè)出每個(gè)信息組中奇數(shù)個(gè)碼元錯(cuò)，檢測(cè)不出偶數(shù)個(gè)碼元錯(cuò)。,編碼效率為：,3.2.2常用的檢錯(cuò)碼(續(xù)),能邊發(fā)送邊產(chǎn)生冗余位，同時(shí)也能邊接收邊校驗(yàn)。能發(fā)現(xiàn)每列中的奇數(shù)位錯(cuò)，對(duì)突發(fā)錯(cuò)誤的漏檢率接近50%。,編碼效率為：,發(fā)送順序,(3)

9、垂直奇偶校驗(yàn),3.2.2常用的檢錯(cuò)碼(續(xù)),發(fā)送順序,能發(fā)現(xiàn)所有長(zhǎng)度小于等于P的突發(fā)性錯(cuò)及水平方向的奇數(shù)個(gè)錯(cuò)，但發(fā)送和接收必須要等待整塊信息到齊后才能進(jìn)行。,編碼效率為：,(4)水平奇偶校驗(yàn),3.2.2常用的檢錯(cuò)碼(續(xù)),發(fā)送順序,能發(fā)現(xiàn)所有3位及3位以下的錯(cuò)誤、奇數(shù)位錯(cuò)和大部分偶數(shù)位錯(cuò)，能發(fā)現(xiàn)所有突發(fā)長(zhǎng)度小于等于p+1的突發(fā)性錯(cuò)，并具有一位的糾錯(cuò)能力。,編碼效率為：,(5)水平垂直奇偶校驗(yàn),3.2.2常用的檢錯(cuò)碼(續(xù)),水平垂直奇偶校驗(yàn)不僅可檢錯(cuò)，還可用來(lái)糾正部分差錯(cuò)。 垂直奇偶校驗(yàn)有時(shí)又稱(chēng)為縱向奇偶校驗(yàn) 水平奇偶校驗(yàn)有時(shí)又稱(chēng)為橫向奇偶校驗(yàn) 水平垂直奇偶校驗(yàn)則又稱(chēng)為縱橫奇偶校驗(yàn),3.2.2常

10、用的檢錯(cuò)碼(續(xù)),2.循環(huán)冗余碼(CRCCycle Redundancy Check) 又稱(chēng)為多項(xiàng)式碼。這是因?yàn)槿魏我粋€(gè)由二進(jìn)制數(shù)位串組成的代碼都可以和一個(gè)只含有0和1兩個(gè)系數(shù)的多項(xiàng)式建立一一對(duì)應(yīng)的關(guān)系。,3.2.2常用的檢錯(cuò)碼(續(xù)),假設(shè)信息流長(zhǎng)度為k位，冗余流長(zhǎng)度為r位 ，則發(fā)送的信息是k位信息位后面再加上r位冗余位，即 ：T(x)=Xr*K(x)+R(x) 由于R(x)是Xr*K(x)除以G(x)的余數(shù)， 即：Xr*K(x)=G(x)*Q(x)+R(x) 接收方得：T(x)= G(x)*Q(x)+R(x)+R(x) 所以，T(x)= G(x)*Q(x),3.2.2常用的檢錯(cuò)碼(續(xù)),例：

11、K(x)= X6+X4+X0，G(x)= X4+X2+X1+X0，求R(x)。,X4* K(x)= X10+X8+X4，即比特流為10100010000,1,11010,0,0,1,11010,1,1,1,11010,11010,1101,余數(shù)為1101，所以R(x)= X3+X2+X0,1,11011,0,0,1,11001,1,1,1,11100,10111,0,3.2.2常用的檢錯(cuò)碼(續(xù)),G(x)有一些特征：,若G(x)含有(x+1)因子，可檢測(cè)出所有奇數(shù)位錯(cuò)； 若G(x)不含有x因子，即G(x)中含有常數(shù)項(xiàng)1，就能檢測(cè)出所有突發(fā)長(zhǎng)度小于等于r的突發(fā)性錯(cuò)； 若G(x)不含有x因子，且對(duì)

12、任何0en-1的e，除不盡xe+1，則能檢測(cè)出所有的雙錯(cuò)； 若G(x)不含有x因子，則對(duì)突發(fā)長(zhǎng)度為r+1的突發(fā)錯(cuò)誤的漏檢率為2-(r-1)； 若G(x)不含有x因子，則對(duì)突發(fā)長(zhǎng)度大于r+1的突發(fā)錯(cuò)誤的漏檢率為2-r。,3.2.2常用的檢錯(cuò)碼(續(xù)),CRC-12：G(x)=X12+X11+X3+X2+X+1 CRC-16：G(x)=X16+X15+X2+1（IBM公司） CRC-CCITT：G(x)=X16+X12+X5+1 CRC-32：G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7 +X5+X4+X2+X+1,若適當(dāng)選取G(x)，使其含有（x+1）因子、

13、常數(shù)項(xiàng)不為0、且周期大于等于n，那末，由此G(x)作為生成多項(xiàng)式產(chǎn)生的CRC碼可檢測(cè)所有的雙錯(cuò)、奇數(shù)個(gè)錯(cuò)和突發(fā)長(zhǎng)度不大于r的突發(fā)性錯(cuò)及（1-2-(r-1)）的突發(fā)長(zhǎng)度為r+1的突發(fā)錯(cuò)和（1-2-r）的突發(fā)長(zhǎng)度大于r+1的突發(fā)性錯(cuò)。,幾種常用的CRC生成多項(xiàng)式：,3.2.4 循環(huán)冗余碼(續(xù)),G(x)=Xr+gr-1Xr-1+gr-2Xr-2+g1X+1,除以G（x）的運(yùn)算用移位寄存器和半加器來(lái)實(shí)現(xiàn)的硬件編碼圖：,3.2.2常用的檢錯(cuò)碼(續(xù)),例：K(x)= X6+X4+X0，G(x)= X4+X2+X1+X0，要求畫(huà)出硬件編碼器圖，并根據(jù)該編碼器求出冗余信息R(x)。,輸入 L R0 R1 R

14、2 R3 輸出 初始化 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1,3.2.3 常用的糾錯(cuò)碼海明碼,1.正反碼,一種簡(jiǎn)單的能夠糾正差錯(cuò)的編碼，其中冗余位的個(gè)數(shù)與信息位個(gè)數(shù)相同。冗余位與信息位或者完全相同或者完全相反，由信息位中“1”的個(gè)數(shù)來(lái)決定。,如信息有K位，冗余位為R位，則 ：,3.2.3 常用的糾錯(cuò)碼(續(xù)),接收方的校驗(yàn)過(guò)程：,

15、再根據(jù)檢驗(yàn)碼的情況來(lái)判斷傳輸中是否有錯(cuò)：,全“0” 無(wú)錯(cuò) 只有一個(gè)“0” 信息位有一位錯(cuò),位置對(duì)應(yīng)于檢驗(yàn)碼中“0”位置 只有一個(gè)“1” 冗余位有一位錯(cuò),位置對(duì)應(yīng)于檢驗(yàn)碼中“1”位置 其它情況有兩位以上差錯(cuò),3.2.3 常用的糾錯(cuò)碼(續(xù)),例：發(fā)送0101101011，在下列情況下判斷接收方收到數(shù)據(jù)正確與否？,收到比特流,0101101011 1101101011 0101101010 1101111011 1101011010,其中信息位,合成碼,校驗(yàn)碼,結(jié)論,信息位中1個(gè)數(shù),01011,00000,奇數(shù),00000,傳輸正確,11011,10000,偶數(shù),01111,第1信息位錯(cuò),01011

16、,00001,奇數(shù),00001,第5冗余位錯(cuò),11011,00000,偶數(shù),11111,兩位以上出錯(cuò),11010,00000,奇數(shù),00000,傳輸正確,3.2.3 常用的糾錯(cuò)碼(續(xù)),正反碼能檢測(cè)出全部2位差錯(cuò)和大部分2位以上的錯(cuò)，具有一位的糾錯(cuò)能力。 編碼效率較低，只能用于信息位較短的場(chǎng)合。 編碼效率為:50%,3.2.3 常用的糾錯(cuò)碼(續(xù)),2.海明碼(Hamming) 在偶校驗(yàn)中,信息位是n位(anan-1a1),加上一位偶校驗(yàn)a0 ,其中：,接收端，監(jiān)督關(guān)系式為（S稱(chēng)為檢驗(yàn)因子）:,如果數(shù)據(jù)位有n位，冗余位有r位，接收方會(huì)收到n+r位信息。要使得接收方能糾正一位差錯(cuò)，就必須能分辨出n

17、+r+1種情況。而r位冗余位能表達(dá)2r種情況，因此n和r一定要滿足:,3.2.3 常用的糾錯(cuò)碼(續(xù)),將碼字每一位字左至右進(jìn)行編號(hào)，最左邊為第一位。 凡編號(hào)為2的乘冪的位（1、2、4、8等）都是冗余校驗(yàn)位，其余是數(shù)據(jù)位。 將每個(gè)數(shù)據(jù)位的編號(hào)展開(kāi)成2的乘冪之和，該數(shù)據(jù)位只由展開(kāi)式中的校驗(yàn)位校驗(yàn)。 每個(gè)校驗(yàn)位連同其所負(fù)責(zé)的所有數(shù)據(jù)位一起構(gòu)成偶校驗(yàn)。,編碼構(gòu)成：,3.2.3 常用的糾錯(cuò)碼(續(xù)),例：對(duì)a的ASCII碼1100001構(gòu)成海明碼。,解：n=7，因此r要為4,構(gòu)成海明碼后一共為11位。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 1+2 1+4 2+4 1+2+4

18、 1+8 2+8 1+2+8,監(jiān)督關(guān)系式為：,冗余位為：,3.2.3 常用的糾錯(cuò)碼(續(xù)),對(duì)接收方來(lái)說(shuō)，利用監(jiān)督關(guān)系式對(duì)收到的數(shù)據(jù)進(jìn)行運(yùn)算，得到校驗(yàn)因子S0S1S2S3，再根據(jù)下表進(jìn)行判斷。,3.2.3 常用的糾錯(cuò)碼(續(xù)),信息位越長(zhǎng)，編碼效率就越高，但不能適用于數(shù)據(jù)傳輸中突發(fā)性差錯(cuò)的控制。,編碼效率為：R=n/(n+r),為了能讓海明碼用于檢測(cè)數(shù)據(jù)傳輸中突發(fā)性差錯(cuò)，可以采用和水平奇偶校驗(yàn)碼相類(lèi)似的水平海明碼。,特點(diǎn)：, 3.3數(shù)據(jù)鏈路協(xié)議,停等協(xié)議 順序接收管道協(xié)議 選擇重傳協(xié)議 流量控制和滑動(dòng)窗口機(jī)制,3.3.1 停等協(xié)議(Stop and Wait),3.3.1 停等協(xié)議(續(xù)),ACK,

19、ACK,1.正常情況：,3.3.1 停等協(xié)議(續(xù)),超時(shí),ACK,2.數(shù)據(jù)幀丟失：,3.3.1 停等協(xié)議(續(xù)),NAK,ACK,3.數(shù)據(jù)幀出錯(cuò)：,3.3.1 停等協(xié)議(續(xù)),ACK,4.應(yīng)答幀丟失 ：,3.3.1 停等協(xié)議(續(xù)),5.停等協(xié)議的信道利用率,假設(shè)信道容量為B(bps)，幀長(zhǎng)為L(zhǎng)(bits)，所以一幀的實(shí)際發(fā)送時(shí)間為L(zhǎng)/B，如果信號(hào)的傳播時(shí)間為R(s)，則其信道利用率為：,(L/B)/(L/B+2R)=L/(2RB+L),3.3.1 停等協(xié)議(續(xù)),設(shè)幀內(nèi)有效數(shù)據(jù)長(zhǎng)度為D(bits)，幀頭和幀尾長(zhǎng)度為H(bits)，等待ACK超時(shí)間隔為T(mén)(s)，數(shù)據(jù)幀和ACK幀出錯(cuò)以及丟失的概率分

20、別為P1和P2。,則每個(gè)數(shù)據(jù)幀不能正確發(fā)送和收到ACK的概率為： P=1-(1-P1)(1-P2) 最終發(fā)送成功所需的平均發(fā)送次數(shù)為:,所以平均重傳次數(shù)為:,3.3.1 停等協(xié)議(續(xù)),總的時(shí)間為：,信道的有效利用率為：,超時(shí)間隔必須滿足TH/B+2R,為使U最大,可取T= H/B+2R,得:,3.3.1 停等協(xié)議(續(xù)),若進(jìn)一步假定信道的比特誤碼率是E，且各比特間相互獨(dú)立，則1-P1=(1-E)L，1-P2=(1-E)H ，代入,令UD=0，可求到最佳幀長(zhǎng)度Dopt：,由于通常E-0，所以可得 ：,3.3.1 停等協(xié)議(續(xù)),6. 停等協(xié)議的捎帶確認(rèn),3.3.2 順序接收管道協(xié)議,使用管道協(xié)

21、議： 可以提高信道的有效利用率，就要允許發(fā)送方不等確認(rèn)幀返回就再連續(xù)發(fā)送若干幀 。 由于允許連續(xù)發(fā)出多個(gè)未被確認(rèn)的幀，幀號(hào)就不能僅采用一位（只有0和1兩種幀號(hào)），而要采用多位幀號(hào)才能區(qū)分 。 凡是被發(fā)送出去尚未被確認(rèn)的幀都可能出錯(cuò)或丟失而要求重發(fā)，因而都要保留下來(lái)。這就要求發(fā)送方有較大的發(fā)送緩沖區(qū)保留準(zhǔn)備重發(fā)的幀。,3.3.2 順序接收管道協(xié)議(續(xù)),出錯(cuò),被數(shù)據(jù)鏈路層丟棄的幀,又稱(chēng)“回退n”（go back n）,幀號(hào)字段的位數(shù)m要滿足：,3.3.2 順序接收管道協(xié)議(續(xù)),回退n的缺陷：允許已發(fā)送未被確認(rèn)的幀越多，可能要退回來(lái)重發(fā)的幀也越多 改進(jìn)：發(fā)送窗口 為了控制發(fā)送方的發(fā)送速度以及受發(fā)

22、送緩沖區(qū)大小的制約等因素都要求對(duì)發(fā)送方已發(fā)出但尚未經(jīng)確認(rèn)的幀的數(shù)目加以限制，這個(gè)數(shù)目就是“發(fā)送窗口”。 落在這個(gè)窗口內(nèi)的幀號(hào)就是等待接收返回的Ack信息的幀號(hào)。由于幀號(hào)只有有限的位數(shù)，到一定時(shí)間后就又反復(fù)循環(huán)了。,3.3.3 選擇重傳(selective repeat)協(xié)議,出錯(cuò),暫存不送主機(jī),將2-6送主機(jī),針對(duì)回退n法的缺點(diǎn)作出改進(jìn)，若某一幀出錯(cuò)后，接收方對(duì)后面送來(lái)的正確的幀先收下，放在一個(gè)緩沖區(qū)，同時(shí)要求發(fā)送方重傳出錯(cuò)的幀，一旦收到后把原先暫存在緩沖區(qū)的其余幀一起按正確順序送往主機(jī)。,3.3.3 選擇重傳協(xié)議 (續(xù)),選擇重傳協(xié)議的優(yōu)點(diǎn)： 在某幀出錯(cuò)時(shí)減少了后面所有幀都要重傳的浪費(fèi) 但接

23、收方要有一個(gè)足夠大的緩沖區(qū)來(lái)暫存未按順序正確接收到的幀,3.3.4 流量控制的滑動(dòng)窗口機(jī)制,把順序接收的管道協(xié)議看成一種滑動(dòng)窗口協(xié)議(sliding window),發(fā)送窗口WT： 指發(fā)送端已發(fā)送但未被確認(rèn)的數(shù)據(jù)幀的數(shù)目 接收窗口WR： 指接收端允許接收的幀的數(shù)目 由于要求順序接收，所以接收窗口始終為1,3.3.4 流量控制的滑動(dòng)窗口機(jī)制(續(xù)),例:取幀號(hào)3位,發(fā)送窗口數(shù)為2,接收窗口數(shù)為1的滑動(dòng)窗口圖。,3.3.4 流量控制的滑動(dòng)窗口機(jī)制(續(xù)),可以用滑動(dòng)窗口的觀點(diǎn)來(lái)統(tǒng)一看待停等、回退n和選擇重傳這三種協(xié)議，其差別僅在其窗口的大小,3.3.4 流量控制的滑動(dòng)窗口機(jī)制(續(xù)),為何回退n的發(fā)送窗

24、口要小于等于2m-1 ？ 假設(shè)發(fā)送過(guò)程發(fā)送幀0到7；幀7的捎帶確認(rèn)回到發(fā)送過(guò)程；發(fā)送過(guò)程發(fā)送另外8幀，序號(hào)再次為0到7；現(xiàn)在幀7的另一個(gè)捎帶確認(rèn)到達(dá)。那么，是第二次發(fā)送的8幀都成功了還是全部丟失了？,3.3.4 流量控制的滑動(dòng)窗口機(jī)制(續(xù)),為何選擇重傳的發(fā)送窗口要小于等于2m-1 ？,3.4 協(xié)議描述與驗(yàn)證,由于協(xié)議的復(fù)雜性,因此要用一些形式化的、數(shù)字的確技術(shù)來(lái)描述和驗(yàn)證,有限狀態(tài)機(jī)FSM(Finite State Machine)模型 Petri網(wǎng)模型,3.4.1 有限狀態(tài)機(jī)模型,一種用來(lái)描述系統(tǒng)的常用方法,系統(tǒng)被描述成有限的狀態(tài)，在一定的前提條件下會(huì)發(fā)生一系列的輸入事件，這些事件使得系統(tǒng)

25、采取相應(yīng)的動(dòng)作，并從一個(gè)狀態(tài)轉(zhuǎn)換成另一個(gè)狀態(tài)，我們稱(chēng)為狀態(tài)的變遷或轉(zhuǎn)換（transition）,3.4.1 有限狀態(tài)機(jī)模型(續(xù)),發(fā)送方狀態(tài)：,0 發(fā)送了0號(hào)幀 1 發(fā)送了1號(hào)幀,接收方狀態(tài)：,0期待接收0號(hào)幀 1期待接收1號(hào)幀,信道狀態(tài)：,0信道上有0號(hào)幀 1信道上有1號(hào)幀 A信道上有ACK幀 S信道處于空幀,以最簡(jiǎn)單的數(shù)據(jù)鏈路層停等協(xié)議為例,系統(tǒng)狀態(tài):(發(fā)送方狀態(tài)、接收方狀態(tài)、信道狀態(tài)),3.4.1 有限狀態(tài)機(jī)模型(續(xù)),(000),(01A),(111),(10A),(00S),(01S),(010),(11S),(101),(10S),3.4.1 有限狀態(tài)機(jī)模型(續(xù)),系統(tǒng)狀態(tài):(發(fā)送

26、方狀態(tài)，接收方狀態(tài)，正向數(shù)據(jù)信道狀態(tài)，反向Ack信道狀態(tài)）,正向信道狀態(tài)：,0信道上有0號(hào)幀 1信道上有1號(hào)幀 S信道處于空幀,反向信道狀態(tài)：,A信道上有ACK幀 S信道處于空幀,前面圖中Ack幀是不帶確認(rèn)幀號(hào)的，將狀態(tài)進(jìn)一步細(xì)化，如：若將傳送數(shù)據(jù)幀的正向信道和傳送Ack幀的反向信道分開(kāi)。,3.4.1 有限狀態(tài)機(jī)模型(續(xù)),正反向信道分開(kāi)的狀態(tài)變遷圖,3.4.2 Petri網(wǎng)模型,由德國(guó)學(xué)者C. A. Petri首先提出的一種描述方法 本質(zhì)上也是一種有限狀態(tài)機(jī)模型，但是它允許多種狀態(tài)變遷同時(shí)交叉發(fā)生，對(duì)于異步并發(fā)過(guò)程的描述更為方便 Petri網(wǎng)的描述中有四種基本元素：位置（place）、標(biāo)記（

27、token）、變遷（transition）和帶箭頭的孤線（arc）。,3.4.2 Petri網(wǎng)模型(續(xù)),具有2個(gè)位置和2個(gè)轉(zhuǎn)換的Petri網(wǎng),圓圈，表示可能進(jìn)入的狀態(tài) 位置中的小圓黑點(diǎn)，某個(gè)位置中有標(biāo)記就表示已處于該狀態(tài) 變遷用一根直線段來(lái)表示 在狀態(tài)變遷過(guò)程中，由于每個(gè)變遷的輸入弧線數(shù)并不一定與輸出弧線數(shù)相等，因而整個(gè)圖中的標(biāo)記數(shù)是不守恒的，可能增多或減少,3.4.2 Petri網(wǎng)模型(續(xù)),ACK幀不帶幀號(hào)停等協(xié)議的Petri圖,3.4.2 Petri網(wǎng)模型(續(xù)),ACG1ADF 表示觸發(fā)了變遷1 Petri網(wǎng)的任何所處狀態(tài)都可表示成無(wú)序的位置組合，且位置可重復(fù)出現(xiàn)。如變遷7：AAC，所

28、以ACG7ACCG。,3.5 鏈路通信協(xié)議舉例,起止式異步規(guī)程 面向字符的同步協(xié)議BSC 面向比特的同步規(guī)程HDLC 點(diǎn)對(duì)點(diǎn)協(xié)議PPP,3.5 鏈路通信協(xié)議舉例(續(xù)),異步協(xié)議 把每個(gè)字符看作一個(gè)獨(dú)立的信息，在每個(gè)字符起始處同步，但各個(gè)字符之間的間隔時(shí)間是可以變化的； 由于發(fā)送器和接收器近似于同一頻率的兩個(gè)時(shí)鐘（要兩個(gè)時(shí)鐘頻率嚴(yán)格完全相同是不可能的）能夠在一段短時(shí)間內(nèi)保持同步，就可以用字符起始處同步的時(shí)鐘來(lái)采樣該字符中的各位，而不需要每位都嚴(yán)格地同步了。,3.5 鏈路通信協(xié)議舉例(續(xù)),同步協(xié)議 把許多字符組織成一個(gè)數(shù)據(jù)塊（即幀），除在該數(shù)據(jù)塊的起始處同步外，還要在后面維持固定的時(shí)鐘，實(shí)際上是

29、發(fā)送端通過(guò)某種技術(shù)將時(shí)鐘混合到數(shù)據(jù)中一起發(fā)送出來(lái)，而接收端又從輸入數(shù)據(jù)中分離出時(shí)鐘來(lái) 。,3.5 鏈路通信協(xié)議舉例(續(xù)),同步與異步的主要區(qū)別在字符之間,同步是指連續(xù)傳送的字符之間是同步的 實(shí)現(xiàn)起來(lái)較復(fù)雜 ； 由于同步協(xié)議是許多字符組成一個(gè)數(shù)據(jù)塊發(fā)送的，它能更有效地利用信道，也便于實(shí)現(xiàn)差錯(cuò)控制和其它更強(qiáng)的控制功能 。 異步則指字符之間不是同步的 典型的異步數(shù)據(jù)鏈路層協(xié)議是起止式異步規(guī)程。,3.5.1 起止異步規(guī)程,傳輸過(guò)程中效率較低，但實(shí)現(xiàn)較容易，發(fā)送端時(shí)鐘漂移不會(huì)積累,它是一個(gè)字符一個(gè)字符傳輸?shù)?，字符與字符間沒(méi)有固定的時(shí)間間隔要求。,3.5.1 起止異步規(guī)程(續(xù)),上圖示出了一個(gè)頻率為位頻率

30、16倍的接收端時(shí)鐘。利用這個(gè)時(shí)鐘，接收端能在一個(gè)位周期1/16時(shí)間內(nèi)決定字符的開(kāi)始，并按如下步驟進(jìn)行后面各位采樣：,3.5.1 起止異步規(guī)程(續(xù)), 當(dāng)檢測(cè)到起始位下降前沿時(shí)將某個(gè)計(jì)數(shù)器清零。 16倍頻時(shí)鐘的每個(gè)脈沖使計(jì)數(shù)器加1。 當(dāng)計(jì)數(shù)器第一次到達(dá)值8時(shí)，表示已到達(dá)起始位的中間。此時(shí)采樣值應(yīng)為0，并把計(jì)數(shù)器清零。若采樣值不為0，那末表示一開(kāi)始檢測(cè)到的下降沿不是真正起始位的前沿，而可能只是一次干擾，此次檢測(cè)應(yīng)作廢。 以后，計(jì)數(shù)器每次到達(dá)值16時(shí)，就采樣輸入波形，將采樣到的數(shù)值暫存起來(lái)，并將計(jì)數(shù)器清零。采樣重復(fù)直至最后的終止位被采樣。 如果終止位采樣正確（為1），那么字符被接收，由暫存處裝入寄存

31、器。若應(yīng)該為終止位處采樣到邏輯值0，說(shuō)明同步或者傳輸有問(wèn)題，該次采樣的字符作廢，不被接收。,3.5.2 面向字符的同步規(guī)程,通信控制字符 :序始(SOH),文始(STX),組終(ETB),文終(ETX),同步(SYN),送畢(EOT),詢問(wèn)(ENQ),確認(rèn)(ACK),否認(rèn)(NAK),轉(zhuǎn)義(DLE),最早出現(xiàn)的是IBM公司的二進(jìn)制同步通信規(guī)程BSC(Binary Synchronous Communication)協(xié)議,ISO的標(biāo)準(zhǔn)稱(chēng)為數(shù)據(jù)通信系統(tǒng)的基本型控制規(guī)程(Basic mode control procedure for data communication system),3.5.2

32、面向字符的同步規(guī)程(續(xù)),幀格式,規(guī)程將特定模式字符作為普通數(shù)據(jù)字符處理 可以使用轉(zhuǎn)義字符DLE（Data Link Escape）來(lái)完成所需的“透明”,3.5.2 面向字符的同步規(guī)程(續(xù)),采用字符填充來(lái)實(shí)現(xiàn)數(shù)據(jù)透明傳輸?shù)哪芰Α?將每個(gè)獨(dú)立的控制字符都作為普通的數(shù)據(jù)字符對(duì)待，因而它可以出現(xiàn)在數(shù)據(jù)正文段中，而不具有通信控制的含義 。 而只有在這些字符緊隨著一個(gè)DLE轉(zhuǎn)義字符后面時(shí)才具有通信控制的含義 。,3.5.2 面向字符的同步規(guī)程(續(xù)),同步比異步的優(yōu)點(diǎn)：,避免了異步方式中許多起始和終止信號(hào)，信道的有效利用率提高了（特別是在傳輸較長(zhǎng)的數(shù)據(jù)時(shí)）。 由于有標(biāo)題字段，可以具備更為復(fù)雜的通信控制能

33、力，校驗(yàn)的功能也增強(qiáng)了。 面向字符的缺點(diǎn)： 它和特定的字符編碼集的關(guān)系過(guò)于密切，不利于兼容 。 為了實(shí)現(xiàn)“數(shù)據(jù)透明”而采用的字符填充方法，無(wú)論用硬件或軟件實(shí)現(xiàn)起來(lái)都較麻煩，而且它也要依賴于所采用的字符編碼集。,3.5.3 面向比特的同步規(guī)程,幀格式,典型代表是IBM公司的面向比特的同步數(shù)據(jù)鏈路控制規(guī)程SDLC (Synchronous Data Link Control)。 ANSI修改了該協(xié)議，變成了高級(jí)數(shù)據(jù)通信控制過(guò)程ADCCP (Advance Data Communication Control Procedure)。 ISO修改此協(xié)議變成了高級(jí)數(shù)據(jù)鏈路控制規(guī)程HDLC (High Level Data Link Control)。,3.5.3 面向比特的同步規(guī)程(續(xù)),比特位的填充,原始數(shù)據(jù) 011011111111111111100000011111000010 線上數(shù)據(jù) 011011111011111011111000000011111