計算機(jī)網(wǎng)絡(luò)教程.ppt

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

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

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

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

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

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

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

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

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

10、用的檢錯碼(續(xù)),2.循環(huán)冗余碼(CRCCycle Redundancy Check) 又稱為多項式碼。這是因為任何一個由二進(jìn)制數(shù)位串組成的代碼都可以和一個只含有0和1兩個系數(shù)的多項式建立一一對應(yīng)的關(guān)系。,3.2.2常用的檢錯碼(續(xù)),假設(shè)信息流長度為k位，冗余流長度為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常用的檢錯碼(續(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常用的檢錯碼(續(xù)),G(x)有一些特征：,若G(x)含有(x+1)因子，可檢測出所有奇數(shù)位錯； 若G(x)不含有x因子，即G(x)中含有常數(shù)項1，就能檢測出所有突發(fā)長度小于等于r的突發(fā)性錯； 若G(x)不含有x因子，且對

12、任何0en-1的e，除不盡xe+1，則能檢測出所有的雙錯； 若G(x)不含有x因子，則對突發(fā)長度為r+1的突發(fā)錯誤的漏檢率為2-(r-1)； 若G(x)不含有x因子，則對突發(fā)長度大于r+1的突發(fā)錯誤的漏檢率為2-r。,3.2.2常用的檢錯碼(續(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ù)項不為0、且周期大于等于n，那末，由此G(x)作為生成多項式產(chǎn)生的CRC碼可檢測所有的雙錯、奇數(shù)個錯和突發(fā)長度不大于r的突發(fā)性錯及（1-2-(r-1)）的突發(fā)長度為r+1的突發(fā)錯和（1-2-r）的突發(fā)長度大于r+1的突發(fā)性錯。,幾種常用的CRC生成多項式：,3.2.4 循環(huán)冗余碼(續(xù)),G(x)=Xr+gr-1Xr-1+gr-2Xr-2+g1X+1,除以G（x）的運(yùn)算用移位寄存器和半加器來實現(xiàn)的硬件編碼圖：,3.2.2常用的檢錯碼(續(xù)),例：K(x)= X6+X4+X0，G(x)= X4+X2+X1+X0，要求畫出硬件編碼器圖，并根據(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 常用的糾錯碼海明碼,1.正反碼,一種簡單的能夠糾正差錯的編碼，其中冗余位的個數(shù)與信息位個數(shù)相同。冗余位與信息位或者完全相同或者完全相反，由信息位中“1”的個數(shù)來決定。,如信息有K位，冗余位為R位，則 ：,3.2.3 常用的糾錯碼(續(xù)),接收方的校驗過程：,

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

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

17、+r+1種情況。而r位冗余位能表達(dá)2r種情況，因此n和r一定要滿足:,3.2.3 常用的糾錯碼(續(xù)),將碼字每一位字左至右進(jìn)行編號，最左邊為第一位。 凡編號為2的乘冪的位（1、2、4、8等）都是冗余校驗位，其余是數(shù)據(jù)位。 將每個數(shù)據(jù)位的編號展開成2的乘冪之和，該數(shù)據(jù)位只由展開式中的校驗位校驗。 每個校驗位連同其所負(fù)責(zé)的所有數(shù)據(jù)位一起構(gòu)成偶校驗。,編碼構(gòu)成：,3.2.3 常用的糾錯碼(續(xù)),例：對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 常用的糾錯碼(續(xù)),對接收方來說，利用監(jiān)督關(guān)系式對收到的數(shù)據(jù)進(jìn)行運(yùn)算，得到校驗因子S0S1S2S3，再根據(jù)下表進(jìn)行判斷。,3.2.3 常用的糾錯碼(續(xù)),信息位越長，編碼效率就越高，但不能適用于數(shù)據(jù)傳輸中突發(fā)性差錯的控制。,編碼效率為：R=n/(n+r),為了能讓海明碼用于檢測數(shù)據(jù)傳輸中突發(fā)性差錯，可以采用和水平奇偶校驗碼相類似的水平海明碼。,特點：, 3.3數(shù)據(jù)鏈路協(xié)議,停等協(xié)議 順序接收管道協(xié)議 選擇重傳協(xié)議 流量控制和滑動窗口機(jī)制,3.3.1 停等協(xié)議(Stop and Wait),3.3.1 停等協(xié)議(續(xù)),ACK,

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

20、別為P1和P2。,則每個數(shù)據(jù)幀不能正確發(fā)送和收到ACK的概率為： P=1-(1-P1)(1-P2) 最終發(fā)送成功所需的平均發(fā)送次數(shù)為:,所以平均重傳次數(shù)為:,3.3.1 停等協(xié)議(續(xù)),總的時間為：,信道的有效利用率為：,超時間隔必須滿足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，可求到最佳幀長度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ā)出多個未被確認(rèn)的幀，幀號就不能僅采用一位（只有0和1兩種幀號），而要采用多位幀號才能區(qū)分 。 凡是被發(fā)送出去尚未被確認(rèn)的幀都可能出錯或丟失而要求重發(fā)，因而都要保留下來。這就要求發(fā)送方有較大的發(fā)送緩沖區(qū)保留準(zhǔn)備重發(fā)的幀。,3.3.2 順序接收管道協(xié)議(續(xù)),出錯,被數(shù)據(jù)鏈路層丟棄的幀,又稱“回退n”（go back n）,幀號字段的位數(shù)m要滿足：,3.3.2 順序接收管道協(xié)議(續(xù)),回退n的缺陷：允許已發(fā)送未被確認(rèn)的幀越多，可能要退回來重發(fā)的幀也越多 改進(jìn)：發(fā)送窗口 為了控制發(fā)送方的發(fā)送速度以及受發(fā)

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

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

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

25、采取相應(yīng)的動作，并從一個狀態(tài)轉(zhuǎn)換成另一個狀態(tài)，我們稱為狀態(tài)的變遷或轉(zhuǎn)換（transition）,3.4.1 有限狀態(tài)機(jī)模型(續(xù)),發(fā)送方狀態(tài)：,0 發(fā)送了0號幀 1 發(fā)送了1號幀,接收方狀態(tài)：,0期待接收0號幀 1期待接收1號幀,信道狀態(tài)：,0信道上有0號幀 1信道上有1號幀 A信道上有ACK幀 S信道處于空幀,以最簡單的數(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號幀 1信道上有1號幀 S信道處于空幀,反向信道狀態(tài)：,A信道上有ACK幀 S信道處于空幀,前面圖中Ack幀是不帶確認(rèn)幀號的，將狀態(tài)進(jìn)一步細(xì)化，如：若將傳送數(shù)據(jù)幀的正向信道和傳送Ack幀的反向信道分開。,3.4.1 有限狀態(tài)機(jī)模型(續(xù)),正反向信道分開的狀態(tài)變遷圖,3.4.2 Petri網(wǎng)模型,由德國學(xué)者C. A. Petri首先提出的一種描述方法 本質(zhì)上也是一種有限狀態(tài)機(jī)模型，但是它允許多種狀態(tài)變遷同時交叉發(fā)生，對于異步并發(fā)過程的描述更為方便 Petri網(wǎng)的描述中有四種基本元素：位置（place）、標(biāo)記（

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

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

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

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

31、器。若應(yīng)該為終止位處采樣到邏輯值0，說明同步或者傳輸有問題，該次采樣的字符作廢，不被接收。,3.5.2 面向字符的同步規(guī)程,通信控制字符 :序始(SOH),文始(STX),組終(ETB),文終(ETX),同步(SYN),送畢(EOT),詢問(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)稱為數(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）來完成所需的“透明”,3.5.2 面向字符的同步規(guī)程(續(xù)),采用字符填充來實現(xiàn)數(shù)據(jù)透明傳輸?shù)哪芰Α?將每個獨(dú)立的控制字符都作為普通的數(shù)據(jù)字符對待，因而它可以出現(xiàn)在數(shù)據(jù)正文段中，而不具有通信控制的含義 。 而只有在這些字符緊隨著一個DLE轉(zhuǎn)義字符后面時才具有通信控制的含義 。,3.5.2 面向字符的同步規(guī)程(續(xù)),同步比異步的優(yōu)點：,避免了異步方式中許多起始和終止信號，信道的有效利用率提高了（特別是在傳輸較長的數(shù)據(jù)時）。 由于有標(biāo)題字段，可以具備更為復(fù)雜的通信控制能

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