第5章數(shù)據(jù)鏈路層第5章數(shù)據(jù)鏈路層15.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)可靠、有效的通信而涉及到的一些算法。5.1基本概念2數(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ā)送方淹沒。數(shù)據(jù)鏈路層的主要功能：35.1.2為網(wǎng)絡(luò)層提供的服務(wù)最主要的服務(wù)是將數(shù)據(jù)從源機(jī)器的網(wǎng)絡(luò)層傳輸?shù)侥繕?biāo)機(jī)器的網(wǎng)絡(luò)層.①無確認(rèn)的無連接的服務(wù)：(P56)適用于誤碼率很低的通信信道；或語音通信；②有確認(rèn)的無連接的服務(wù)：適用于誤碼率很高的通信信道；如無線通信；③有確認(rèn)的面向連接的服務(wù)：適用于通信要求較高（可靠性、實(shí)時(shí)性）的情況5.1.2為網(wǎng)絡(luò)層提供的服務(wù)最主要的服務(wù)是將數(shù)據(jù)從源機(jī)器的45.1.3成幀方法①字符計(jì)數(shù)法：在幀頭部指明幀內(nèi)字符數(shù)。問題：由于傳輸差錯(cuò)導(dǎo)致計(jì)數(shù)值被“篡改”；5.1.3成幀方法①字符計(jì)數(shù)法：5②字符填充首尾界符法：以ASCII字符DLE和STX作為幀的頭部，DLE和ETX作為幀的尾部（DLE＝10H、STX＝02H、ETX＝03H）技術(shù)：如何避免二進(jìn)制數(shù)據(jù)可能與幀的頭尾標(biāo)志相同？發(fā)送方在數(shù)據(jù)中遇到DLE時(shí)，自動(dòng)在其前后插入一個(gè)DLE;接收方在數(shù)據(jù)中遇到單個(gè)DLE時(shí),可確定幀界;遇到2個(gè)DLE時(shí)，自動(dòng)刪除一個(gè)DLE。②字符填充首尾界符法：6③位填充首尾標(biāo)志法：以一個(gè)特定的字節(jié)信息作為幀的頭尾標(biāo)志；如01111110；為了避免與原始數(shù)據(jù)比特組合相同，發(fā)送方在數(shù)據(jù)中遇到5個(gè)連續(xù)的1時(shí)，自動(dòng)在其后插入一個(gè)0；接收方在數(shù)據(jù)中遇到5個(gè)連續(xù)的1后面跟著一個(gè)0，自動(dòng)將此0刪除。③位填充首尾標(biāo)志法：75.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ò)的主要原因。5.1.4差錯(cuò)控制8差錯(cuò)評價(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ò)評價(jià)指標(biāo)如下：9差錯(cuò)控制的基本方式如下：（1）反饋糾錯(cuò)

在接收端能發(fā)現(xiàn)差錯(cuò)，但不能確定錯(cuò)碼的位置，通過反饋信息請求發(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í)，通過反饋信息請求發(fā)送端重發(fā)。差錯(cuò)控制的基本方式如下：105.1.5流控制基于反饋的流控制基于速率的流控制5.1.5流控制115.2錯(cuò)誤檢測和糾正5.2錯(cuò)誤檢測和糾正12碼字的檢錯(cuò)與糾錯(cuò)能力碼字(n位)＝數(shù)據(jù)碼(m位)+冗余碼(r位)。海明距離：兩個(gè)碼字之間對應(yīng)碼元位的不同碼元的個(gè)數(shù)。碼字的檢錯(cuò)與糾錯(cuò)能力碼字(n位)＝數(shù)據(jù)碼(m位)+冗余碼(r13碼字編碼的海明距離對于一種碼字編碼，在這個(gè)碼字集合中，可得到所有任意兩個(gè)碼字的海明距離，其中最小的海明距離稱為該碼字編碼的海明距離d。定理1：如果d≥2t+1,則該編碼可糾正任何t個(gè)(或t個(gè)以下)的錯(cuò)誤。定理2：如果d≥e+1,則該編碼可檢測出任何e個(gè)(或e個(gè)以下)的錯(cuò)誤。一般情況下，冗余位越多(即r越大)，檢錯(cuò)糾錯(cuò)能力越強(qiáng)，但相應(yīng)的編碼效率也隨之降低了。碼字編碼的海明距離對于一種碼字編碼，在這個(gè)碼字集合中，可得到14示例：偶校驗(yàn)的檢錯(cuò)與糾錯(cuò)能力例：對于偶校驗(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ù)定理1，該編碼不能糾正任何錯(cuò)誤(t＝0)。D>=2t+1根據(jù)定理2，該編碼可檢測出任何1個(gè)錯(cuò)誤(e＝1)。D>=e+1奇校驗(yàn)的檢錯(cuò)能力與偶校驗(yàn)一樣。示例：偶校驗(yàn)的檢錯(cuò)與糾錯(cuò)能力例：對于偶校驗(yàn)（使每個(gè)碼字中都有15誤碼控制編碼的分類按冗余碼的控制功能分:①糾錯(cuò)碼：在接收端能發(fā)現(xiàn)并自動(dòng)糾正差錯(cuò)。叫前向糾錯(cuò)糾錯(cuò)檢錯(cuò)的常用方法①海明碼：可糾錯(cuò)和檢錯(cuò)，實(shí)現(xiàn)復(fù)雜，效率低。②奇偶校驗(yàn)碼：方法簡單，檢錯(cuò)能力差。③循環(huán)冗余編碼(CRC)：實(shí)現(xiàn)容易，檢錯(cuò)能力強(qiáng)，廣泛使用。誤碼控制編碼的分類按冗余碼的控制功能分:165.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≥m+1;（∵r2≥n＋1=m+r+1）例如：4個(gè)信息位D1D2D3D4，3個(gè)校驗(yàn)位P1P2P3。5.2.1糾錯(cuò)碼：海明碼海明在1950年提出的可糾正一位錯(cuò)的175.2.2檢錯(cuò)碼：循環(huán)冗余碼－CRC碼特點(diǎn)：實(shí)現(xiàn)容易，檢錯(cuò)能力強(qiáng)，廣泛使用。常結(jié)合反饋重傳法來保證信息的可靠傳輸。碼字組成：5.2.2檢錯(cuò)碼：循環(huán)冗余碼－CRC碼特點(diǎn)：實(shí)現(xiàn)容易，檢錯(cuò)能18例：若數(shù)據(jù)碼＝110011，可表示為：M(x)=1·x5+1·x4+0·x3+0·x2+1·x+1即：M(x)=x5+x4+x+1。生成多項(xiàng)式G(x)：G(x)=grxr+...+gixi+...+g1x+g0其中,gi=0或1,r≥i≥0,gr

≠0,g0

≠0,共r+1位G(x)被通信雙方事先共同選定使用：發(fā)送端：通過G(x)生成校驗(yàn)碼；接收端：通過G(x)校驗(yàn)接收的碼字。對于多項(xiàng)式的運(yùn)算：采用模2計(jì)算（加法不進(jìn)位，減法不借位）；加減法是一樣的。模2計(jì)算即是異或運(yùn)算。例：若數(shù)據(jù)碼＝110011，19循環(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）。我們在M的后面再添加供差錯(cuò)檢測用的n位冗余碼一起發(fā)送。循環(huán)冗余檢驗(yàn)的原理在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗20冗余碼的計(jì)算用二進(jìn)制的模

2

運(yùn)算進(jìn)行2n乘M的運(yùn)算，這相當(dāng)于在M后面添加n個(gè)0。得到的(k+n)位的數(shù)除以事先選定好的長度為(n+1)位的除數(shù)P，得出商是Q而余數(shù)是R，余數(shù)R比除數(shù)P少1位，即R是n位。冗余碼的計(jì)算用二進(jìn)制的模2運(yùn)算進(jìn)行2n乘M的運(yùn)21冗余碼的計(jì)算舉例現(xiàn)在k=6,M=101001。除數(shù)P=1101，則n=3,被除數(shù)是2nM=101001000。冗余碼的計(jì)算舉例現(xiàn)在k=6,M=101001。22

110101

←

Q

(商)P(除數(shù))→

1101101001000

←

2nM(被除數(shù))

1101

1110

1101

0111

0000

1110

1101

0110

0000

1100

1101

001←R(余數(shù))，作為FCS

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

23模2運(yùn)算的結(jié)果是：商Q=110101，余數(shù)R=001。把余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去。發(fā)送的數(shù)據(jù)是：2nM+R

即：101001001，共(k+n)位。模2運(yùn)算的結(jié)果是：商Q=110101，24檢測出差錯(cuò)接收方對接收到的數(shù)據(jù)除以同樣的除數(shù),只要得出的余數(shù)R不為0，就表示檢測到了差錯(cuò)。但這種檢測方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。一旦檢測出差錯(cuò)，就丟棄這個(gè)出現(xiàn)差錯(cuò)的幀。只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)P，那么出現(xiàn)檢測不到的差錯(cuò)的概率就很小很小。檢測出差錯(cuò)接收方對接收到的數(shù)據(jù)除以同樣的除數(shù),只要得出的余數(shù)25數(shù)據(jù)鏈路層示例課件261數(shù)據(jù)鏈路(即邏輯鏈路)與鏈路(即物理鏈路)有何區(qū)別?“電路接通了”與”數(shù)據(jù)鏈路接通了”的區(qū)別何在?答：數(shù)據(jù)鏈路與鏈路的區(qū)別在于數(shù)據(jù)鏈路出鏈路外，還必須有一些必要的規(guī)程來控制數(shù)據(jù)的傳輸，因此，數(shù)據(jù)鏈路比鏈路多了實(shí)現(xiàn)通信規(guī)程所需要的硬件和軟件?！半娐方油恕北硎炬溌穬啥说慕Y(jié)點(diǎn)交換機(jī)已經(jīng)開機(jī)，物理連接已經(jīng)能夠傳送比特流了，但是，數(shù)據(jù)傳輸并不可靠，在物理連接基礎(chǔ)上，再建立數(shù)據(jù)鏈路連接，才是“數(shù)據(jù)鏈路接通了”，此后，由于數(shù)據(jù)鏈路連接具有檢測、確認(rèn)和重傳功能，才使不太可靠的物理鏈路變成可靠的數(shù)據(jù)鏈路，進(jìn)行可靠的數(shù)據(jù)傳輸當(dāng)數(shù)據(jù)鏈路斷開連接時(shí)，物理電路連接不一定跟著斷開連接。1數(shù)據(jù)鏈路(即邏輯鏈路)與鏈路(即物理鏈路)有何區(qū)別?“272為了進(jìn)行差錯(cuò)控制,必須對傳送的數(shù)據(jù)進(jìn)行校驗(yàn).在局域網(wǎng)中廣泛使用的校驗(yàn)方法是_(1)___,CRC-16標(biāo)準(zhǔn)規(guī)定生成多項(xiàng)式為G(x)=x16+X15+x2+1,它產(chǎn)生的校驗(yàn)碼是__(2)__位,接收端發(fā)現(xiàn)錯(cuò)誤后采取的措施是__(3)__.如果CRC的生成多項(xiàng)式是G(x)=x4+x+1,信息碼字是10110,由計(jì)算出來的CRC校驗(yàn)碼是__(4)_.(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)請求重發(fā)D重新生成原始數(shù)據(jù)(4)A0100B1010C0111D11112為了進(jìn)行差錯(cuò)控制,必須對傳送的數(shù)據(jù)進(jìn)行校驗(yàn).在局域網(wǎng)中28書上作業(yè)練習(xí):P845-41要發(fā)送的數(shù)據(jù)為1101011011。采用CRC的生成多項(xiàng)式是P（X）=X4+X+1。試求應(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ù)鏈路層的傳輸是否就變成了可靠的傳輸？

書上作業(yè)練習(xí):P845-41要發(fā)送的數(shù)據(jù)為110101129答：作二進(jìn)制除法，1101011011000010011得余數(shù)1110，添加的檢驗(yàn)序列是1110.作二進(jìn)制除法，兩種錯(cuò)誤均可發(fā)現(xiàn)僅僅采用了CRC檢驗(yàn)，缺重傳機(jī)制，數(shù)據(jù)鏈路層的傳輸還不是可靠的傳輸。答：作二進(jìn)制除法，11010110110000130本課重點(diǎn)掌握CRC冗余校驗(yàn)碼的計(jì)算.本課重點(diǎn)掌握CRC冗余校驗(yàn)碼的計(jì)算.315.3基本數(shù)據(jù)鏈路協(xié)議數(shù)據(jù)鏈路協(xié)議主要考慮的問題：①避免所傳送的數(shù)據(jù)可能出現(xiàn)差錯(cuò)和丟失；②使發(fā)方發(fā)送數(shù)據(jù)的速率適應(yīng)收方的接收能力。5.3基本數(shù)據(jù)鏈路協(xié)議數(shù)據(jù)鏈路協(xié)議主要考慮的問題：32理想化的數(shù)據(jù)傳輸假設(shè)1：所傳送的數(shù)據(jù)即不會(huì)出現(xiàn)差錯(cuò)和也不會(huì)丟失；不考慮差錯(cuò)控制問題）假設(shè)2：接收端的數(shù)據(jù)接收速率足夠快，有能力接收發(fā)送端的數(shù)據(jù)發(fā)送率。（不考慮流量控制問題）在理想化的條件下，數(shù)據(jù)鏈路層不需要：①差錯(cuò)控制協(xié)議；②流量控制協(xié)議；就可保證數(shù)據(jù)的正確傳輸。理想化的數(shù)據(jù)傳輸假設(shè)1：所傳送的數(shù)據(jù)即不會(huì)出現(xiàn)差錯(cuò)和也不會(huì)丟33實(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ù)幀。實(shí)用的停止等待協(xié)議（ARQ）去掉假設(shè)1；去掉假設(shè)2。34數(shù)據(jù)鏈路層示例課件35死鎖現(xiàn)象：當(dāng)出現(xiàn)幀丟失時(shí)，發(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ù)幀。Tout也稱重傳時(shí)間死鎖現(xiàn)象：當(dāng)出現(xiàn)幀丟失時(shí)，發(fā)送端永36重復(fù)幀差錯(cuò)：若應(yīng)答幀丟失，按照超時(shí)重發(fā)方法，接收端將收到重復(fù)幀，如何解決？解決方法：給每個(gè)數(shù)據(jù)幀附加不同的發(fā)送序號(hào)Ns，如果接收端收到相同序號(hào)的數(shù)據(jù)幀,則丟棄,并回送一個(gè)ACK。重復(fù)幀差錯(cuò)：若應(yīng)答幀丟失，按照超37發(fā)送序號(hào)需要多少位?對于ARQ協(xié)議，發(fā)送序號(hào)有0和1即可(只需1個(gè)bit);每發(fā)一個(gè)新的數(shù)據(jù)幀，發(fā)送序號(hào)就和上次發(fā)送的不一樣，重發(fā)的數(shù)據(jù)幀發(fā)送序號(hào)不變。發(fā)送序號(hào)需要多少位?對于ARQ協(xié)議，發(fā)送序號(hào)有0和138ARQ協(xié)議：ARQ協(xié)議：39重傳時(shí)間tout的選擇若Tout太長，浪費(fèi)時(shí)間，若Tout太短，過早重傳數(shù)據(jù)，產(chǎn)生“額外”應(yīng)答幀。如何解決？提示：在確認(rèn)幀ACK和否認(rèn)幀NAK中附加序號(hào)。重傳時(shí)間tout的選擇若Tout太長，浪費(fèi)時(shí)間，40停止等待協(xié)議的信道利用率停止等待協(xié)議的信道利用率41數(shù)據(jù)鏈路層示例課件42連續(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協(xié)議（selectiverepeat）連續(xù)ARQ協(xié)議目的：提高信道利用率。43回退N幀ARQ協(xié)議（gobackn）①方式1：反饋否認(rèn)幀NAK（含出錯(cuò)的數(shù)據(jù)幀發(fā)送序號(hào)）。再從出錯(cuò)的數(shù)據(jù)幀開始重傳。要求：發(fā)送端要求有一個(gè)能存儲(chǔ)N個(gè)數(shù)據(jù)幀的緩沖區(qū)。接收端只需能存儲(chǔ)一個(gè)數(shù)據(jù)幀的緩沖?；赝薔幀ARQ協(xié)議（gobackn）①方式1：44②方式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ù)幀及后繼的幀。②方式2：45選擇重發(fā)ARQ協(xié)議（selectiverepeat）目的：進(jìn)一步提高信道利用率。方法：只重傳出現(xiàn)差錯(cuò)的數(shù)據(jù)幀或者超時(shí)的數(shù)據(jù)幀。要求：在接收端要設(shè)置具有相當(dāng)容量的緩存空間。選擇重發(fā)ARQ協(xié)議（selectiverepeat）目的：46選擇重發(fā)ARQ協(xié)議－工作原理示意圖選擇重發(fā)ARQ協(xié)議－工作原理示意圖475.4滑動(dòng)窗口協(xié)議（SlidingWindowsprotocol）①當(dāng)未被確認(rèn)的數(shù)據(jù)幀數(shù)目太多時(shí)；只要有一幀出錯(cuò)，就有很多數(shù)據(jù)幀需要重傳，因而增大開銷。②為了對發(fā)送出去的大量未被確認(rèn)的數(shù)據(jù)幀進(jìn)行編號(hào)，每個(gè)數(shù)據(jù)幀的發(fā)送序號(hào)也要占用較多的比特?cái)?shù)，因而又增大了開銷。對于連續(xù)ARQ協(xié)議，采用了發(fā)送端不等待確認(rèn)幀返回就可連續(xù)發(fā)送幀，存在問題：滑動(dòng)窗口協(xié)議：對發(fā)送端已發(fā)送出去但未被確認(rèn)的幀的數(shù)目加以限制。在發(fā)送端和接收端分別設(shè)置發(fā)送窗口和接收窗口。5.4滑動(dòng)窗口協(xié)議（SlidingWindowspro48發(fā)送窗口（在發(fā)送端）目的：用來對發(fā)送端進(jìn)行流量控制。發(fā)送窗口尺寸Ws：在還沒有收到應(yīng)答幀的情況下，發(fā)送端最多可以連續(xù)發(fā)送數(shù)據(jù)幀的個(gè)數(shù)。發(fā)送序號(hào)：一般采用n位bit進(jìn)行編號(hào)（0～2n-1）。若n=3；則用3位bit進(jìn)行編號(hào)（0～7）。發(fā)送窗口（在發(fā)送端）目的：用來對發(fā)送端進(jìn)行流量控制。49·發(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ù)幀?！ぐl(fā)送端只能連續(xù)發(fā)送窗口內(nèi)的數(shù)據(jù)幀；50接收窗口（在接收端）目的：用來控制可以接收哪些數(shù)據(jù)幀而不可以接收哪些幀。接收窗口Wr：只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收窗口內(nèi)，才允許將該數(shù)據(jù)幀收下；否則，丟棄。接收窗口（在接收端）目的：用來控制可以接收哪些數(shù)據(jù)幀而不可以51如果Wr=1，意味著只能按順序接收數(shù)據(jù)幀。如果Wr較大，有可能會(huì)出現(xiàn)數(shù)據(jù)幀的失序。差錯(cuò)情況：設(shè)Wr=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)幀，讓對方重新發(fā)送1號(hào)數(shù)據(jù)幀。如果Wr=1，意味著只能按順序接收數(shù)據(jù)幀。52應(yīng)答幀丟失情況應(yīng)答幀丟失情況53應(yīng)答幀被“篡改”情況:ACK→NAK應(yīng)答幀被“篡改”情況:ACK→NAK54數(shù)據(jù)鏈路層示例課件55重疊問題在接收前后，接收窗口范圍內(nèi)的有效序號(hào)出現(xiàn)重疊。重疊問題在接收前后，接收窗口范圍內(nèi)的有效序號(hào)出現(xiàn)重疊。56避免重疊問題為了避免重疊問題，接收窗口尺寸Wr≤2n/2。避免重疊問題為了避免重疊問題，接收窗口尺寸Wr≤2n/2。57發(fā)送窗口的最大尺寸值發(fā)送窗口的最大尺寸值58累積確認(rèn)方法接收端在連續(xù)接收若干個(gè)正確的數(shù)據(jù)幀以后，對最后一個(gè)數(shù)據(jù)幀發(fā)回確認(rèn)幀。累積確認(rèn)方法接收端在連續(xù)接收若干個(gè)正確的數(shù)據(jù)幀以59窗口控制協(xié)議的信道利用率窗口控制協(xié)議的信道利用率60窗口控制協(xié)議的信道利用率設(shè)：單程傳輸時(shí)延Td，數(shù)據(jù)幀發(fā)送時(shí)間Tf，數(shù)據(jù)傳輸率C，數(shù)據(jù)幀長度L，窗口尺寸Ws在正常傳輸情況下，忽略應(yīng)答幀長度和處理時(shí)間：窗口控制協(xié)議的信道利用率設(shè)：單程傳輸時(shí)延Td，數(shù)據(jù)幀發(fā)送時(shí)61依據(jù)信道利用率進(jìn)行窗口尺寸的選擇優(yōu)化原則：發(fā)送端收到窗口中第一個(gè)已發(fā)數(shù)據(jù)幀的確認(rèn)時(shí)，正好發(fā)完窗口中的最后一個(gè)數(shù)據(jù)幀。Ws大于上述選擇，則Cr=100%，但浪費(fèi)緩沖區(qū)；Ws小于上述選擇，則Cr<100%，發(fā)送端需要等待應(yīng)答而使發(fā)送停頓。依據(jù)信道利用率進(jìn)行窗口尺寸的選擇優(yōu)化原則：62示例例：衛(wèi)星信道：單程傳輸時(shí)延Td＝250ms，數(shù)據(jù)傳輸率C＝50kb/s，數(shù)據(jù)幀長度L＝1000bit，在已知條件不變的情況下，設(shè)置L=160bit，信道利用率如何？示例例：衛(wèi)星信道：63ARQ協(xié)議、連續(xù)ARQ協(xié)議的窗口尺寸ARQ協(xié)議：發(fā)送窗口Ws＝1，接收窗口Wr＝1連續(xù)ARQ協(xié)議:·回退N幀ARQ協(xié)議：發(fā)送窗口Ws＞1，接收窗口Wr=1?！みx擇重發(fā)連續(xù)ARQ協(xié)議：發(fā)送窗口Ws＞1，接收窗口Wr＞1，且Wr≤Ws。ARQ協(xié)議、連續(xù)ARQ協(xié)議的窗口尺寸ARQ協(xié)議：64重難點(diǎn)講解與練習(xí)1流量和差錯(cuò)控制1)差錯(cuò)控制方法:A自動(dòng)請求重發(fā)(AutomaticRepeatRequest,ARQ)B前向糾錯(cuò)2)形成兩種重要的流控制A選擇重發(fā)ARQ協(xié)議:只重發(fā)出錯(cuò)幀B后退N幀ARQ協(xié)議:退回到出錯(cuò)幀重難點(diǎn)講解與練習(xí)1流量和差錯(cuò)控制65效率分析公式:1停等協(xié)議:假設(shè)線路不出錯(cuò),則如出錯(cuò)概率為P,則(其中a=tp/tf,可理解為線路的幀計(jì)數(shù)長度)2選擇重發(fā)ARQ協(xié)議,假設(shè)發(fā)送窗口的大小為W,則不出錯(cuò)時(shí)為:如果對出錯(cuò)進(jìn)行重發(fā),設(shè)出錯(cuò)概率為P,則效率分析公式:663后退N幀:當(dāng)W>=2a+1,N近似等于2a+1,則當(dāng)W<2a+1,N=W.則3后退N幀:67例1:已知數(shù)據(jù)幀長為1000bit,幀頭為64bit,數(shù)據(jù)速率為500kb/s,線路傳播延遲為5ms,則1)信道無差錯(cuò),采用停等協(xié)議,求利用率2)滑動(dòng)窗口為大窗口,求窗口至少為多大?3)設(shè)P=0.01,用選擇重發(fā)ARQ協(xié)議,窗口大小W=4,求利用率.解:1)a=Tp/TfTp=5Tf=1064/500a=5X500/1064=2.35E=0.182)所謂大窗口就是W>=2a+1,由上面知a=2.35故w>=2X2.35+1=5.7取w=6例1:已知數(shù)據(jù)幀長為1000bit,幀頭為64bit,數(shù)據(jù)683)P一般比較小,在分母看作為0,故得:由于w=4,2a+1=5.7,為小窗口,W=w(1-p)/2a+1=4X(1-0.01)/5.7=0.693)695.5協(xié)議1.協(xié)議開發(fā)過程5.5協(xié)議1.協(xié)議開發(fā)過程70協(xié)議的形式描述描述方法：①有限狀態(tài)機(jī)采用狀態(tài)流程圖進(jìn)行描述。②事件狀態(tài)表采用表格進(jìn)行描述。③結(jié)構(gòu)化程序采用程序代碼進(jìn)行描述。④Petri網(wǎng)模型采用狀態(tài)流程圖進(jìn)行描述。協(xié)議的形式描述描述方法：71有限狀態(tài)機(jī)模型FSMFSM協(xié)議描述方法也稱狀態(tài)轉(zhuǎn)移圖。特點(diǎn)：易懂、易理解和易于實(shí)現(xiàn)。組成：狀態(tài)圓和有向弧。有限狀態(tài)機(jī)模型FSMFSM協(xié)議描述方法也稱狀態(tài)轉(zhuǎn)移圖。72Petri網(wǎng)模型德國C.A.Petrit提出(1962,博士論文)。4個(gè)基本元素：位置：系統(tǒng)可能處于的狀態(tài)；用圓圈表示。轉(zhuǎn)換：改變狀態(tài)；用線段表示。有向?。何恢门c轉(zhuǎn)換之間的相互依賴關(guān)系；用弧線表示。標(biāo)記：系統(tǒng)當(dāng)前處于的狀態(tài)；在圓圈中用黑點(diǎn)表示。Petri網(wǎng)模型德國C.A.Petrit提出(1962,博士73數(shù)據(jù)鏈路層示例課件74數(shù)據(jù)鏈路層示例分類：數(shù)據(jù)鏈路層示例分類：75高級(jí)數(shù)據(jù)鏈路控制HDLC1976年，ISO提出HDLC（High-levelDataLinkControl）適用范圍：計(jì)算機(jī)—計(jì)算機(jī)、計(jì)算機(jī)—終端、終端—終端三種類型的站：主站：主要功能是發(fā)送命令（包括數(shù)據(jù)），接收響應(yīng)，負(fù)責(zé)整個(gè)鏈路的控制（如系統(tǒng)的初始、流控、差錯(cuò)恢復(fù)等）；次站：主要功能是接收命令，發(fā)送響應(yīng)，配合主站完成鏈路的控制；復(fù)合站：同時(shí)具有主、次站功能，既發(fā)送又接收命令和響應(yīng)，并負(fù)責(zé)整個(gè)鏈路的控制。高級(jí)數(shù)據(jù)鏈路控制HDLC1976年，ISO提出HDLC（Hi76HDLC的鏈路構(gòu)型非平衡配置主站控制整個(gè)鏈路工作。主站發(fā)出的幀叫命令；次站發(fā)出的幀叫響應(yīng)。適合把智能和半智能的終端連接到計(jì)算機(jī)。HDLC的鏈路構(gòu)型非平衡配置77HDLC的鏈路構(gòu)型平衡配置復(fù)合站具有主站和次站的功能。地位平等。適合于計(jì)算機(jī)和計(jì)算機(jī)之間的連接HDLC的鏈路構(gòu)型平衡配置78HDLC的基本操作模式正規(guī)響應(yīng)模式NRM：適用于點(diǎn)—點(diǎn)式和多點(diǎn)式兩種非平衡構(gòu)型。只有當(dāng)主站向次站發(fā)出探詢后，次站才能獲得傳輸幀的許可。異步響應(yīng)模式ARM：適用于點(diǎn)—點(diǎn)式非平衡構(gòu)型和主站—次站式平衡構(gòu)型。次站可以隨時(shí)傳輸幀，不必等待主站的探詢。異步平衡模式ABM：適用于通信雙方都是復(fù)合站的平衡構(gòu)型，也采用異步響應(yīng)，雙方具有同等能力。HDLC的基本操作模式正規(guī)響應(yīng)模式NRM：79HDLC的幀結(jié)構(gòu)幀標(biāo)志（Flag）定界符為01111110＝7EH（零比特填充法）。地址域（Address）多終端線路，用來區(qū)分終端；點(diǎn)到點(diǎn)線路，有時(shí)用來區(qū)分命令和響應(yīng)。–若是接收該幀的站的地址，則該幀是命令幀；–若是發(fā)送該幀的站的地址，則該幀是響應(yīng)幀。HDLC的幀結(jié)構(gòu)幀標(biāo)志（Flag）80HDLC的幀結(jié)構(gòu)有效地址為254個(gè)（通常為8位，可擴(kuò)展到16位）–全1的8位地址表示廣播（所有次站接收）；–全0的8位地址是無效地址?？刂朴颍–ontrol）標(biāo)識(shí)幀的類型和功能，使對方站執(zhí)行特定的操作。–信息幀（Information幀）；–管理幀（Supervisory幀）；–無序號(hào)幀（Unnumbered幀）。HDLC的幀結(jié)構(gòu)有效地址為254個(gè)（通常為8位，可擴(kuò)展到1681HDLC的幀結(jié)構(gòu)數(shù)據(jù)域（Data）任意比特串或字符串（有上限）校驗(yàn)和（Checksum）循環(huán)冗余校驗(yàn)（CRC）生成多項(xiàng)式：HDLC的幀結(jié)構(gòu)數(shù)據(jù)域（Data）82控制域的格式Seq－發(fā)送序號(hào)使用滑動(dòng)窗口技術(shù)，3位序號(hào)，發(fā)送窗口Ws=7；Next－捎帶確認(rèn)接收站期望收到的幀序號(hào)，而不是最后一個(gè)已收到的幀序號(hào)；控制域的格式Seq－發(fā)送序號(hào)83控制域的格式P/F－詢問/終止