Chapter3數(shù)據(jù)鏈路層PPT課件

1、1Chapter 3 數(shù)據(jù)鏈路層2應(yīng)用層應(yīng)用層傳輸層傳輸層網(wǎng)絡(luò)層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層物理層物理層主要功能主要功能成幀：成幀：在接收方從比特流中恢復(fù)出幀，關(guān)鍵是確定幀開始和結(jié)束的地方，也稱之為幀定界數(shù)據(jù)幀數(shù)據(jù)幀可靠傳輸：可靠傳輸：差錯(cuò)校驗(yàn)：在發(fā)送方，給數(shù)據(jù)加尾部，用于差錯(cuò)校驗(yàn) 流量控制：如何避免一個(gè)快速的發(fā)送方淹沒(méi)掉一個(gè)慢速的接收方信道（信道（鏈路）多路訪問(wèn)：鏈路）多路訪問(wèn)：如何尋址以及控制對(duì)共享信道（鏈路）的訪問(wèn)，為此在數(shù)據(jù)鏈路層引入了一個(gè)特殊的子層，即介質(zhì)訪問(wèn)控制子層相關(guān)協(xié)議相關(guān)協(xié)議HDLC（High-Level Data Link Control）PPP（Point to Point

2、 Protocol）CSMA/CDCSMA/CA點(diǎn)對(duì)點(diǎn)點(diǎn)對(duì)點(diǎn)鏈路鏈路多路訪問(wèn)多路訪問(wèn)/共享鏈路共享鏈路3Chapter 3 數(shù)據(jù)鏈路層n3.1數(shù)據(jù)鏈路層的功能n3.2差錯(cuò)檢測(cè)與糾正n3.3基本數(shù)據(jù)鏈路協(xié)議n3.4滑動(dòng)窗口（Slide Windows）協(xié)議n3.5面向位的協(xié)議HDLCn3.6 Internet中的數(shù)據(jù)鏈路層4Chapter 3 數(shù)據(jù)鏈路層n3.1數(shù)據(jù)鏈路層的功能n3.2差錯(cuò)檢測(cè)與糾正n3.3基本數(shù)據(jù)鏈路協(xié)議n3.4滑動(dòng)窗口（Slide Windows）協(xié)議n3.5面向位的協(xié)議HDLCn3.6 Internet中的數(shù)據(jù)鏈路層53.1數(shù)據(jù)鏈路層的功能n向網(wǎng)絡(luò)層提供良好的服務(wù)接口向網(wǎng)絡(luò)

3、層提供良好的服務(wù)接口n將物理層的比特流編成幀將物理層的比特流編成幀n差錯(cuò)控制差錯(cuò)控制n流量控制流量控制數(shù)據(jù)鏈路層協(xié)議的位置6ph: physical Layerdl: data link layerPDU: Protocol Data Unit (message at application layer, packet at network layer, frame at dl, and bit at ph)物理層提供物理層提供不可靠的比不可靠的比特傳輸服務(wù)特傳輸服務(wù)端口端口數(shù)據(jù)鏈數(shù)據(jù)鏈路層協(xié)議路層協(xié)議73.1.1為網(wǎng)絡(luò)層提供服務(wù)n無(wú)確認(rèn)、無(wú)連接的服務(wù)無(wú)確認(rèn)、無(wú)連接的服務(wù)n發(fā)送方不需要建立連接

4、就向接收方發(fā)送發(fā)送方不需要建立連接就向接收方發(fā)送獨(dú)立獨(dú)立的數(shù)據(jù)幀，的數(shù)據(jù)幀，而接收方也不需要對(duì)收到的幀進(jìn)行確認(rèn)而接收方也不需要對(duì)收到的幀進(jìn)行確認(rèn)n有確認(rèn)、無(wú)連接的服務(wù)有確認(rèn)、無(wú)連接的服務(wù)n發(fā)送方不需要建立連接就向接收方發(fā)送發(fā)送方不需要建立連接就向接收方發(fā)送獨(dú)立獨(dú)立的數(shù)據(jù)幀，的數(shù)據(jù)幀，但接收方需要對(duì)收到的幀但接收方需要對(duì)收到的幀進(jìn)行確認(rèn)進(jìn)行確認(rèn)n面向連接的服務(wù)面向連接的服務(wù)n發(fā)送方與接收方在通信前要先建立連接，然后在此連發(fā)送方與接收方在通信前要先建立連接，然后在此連接上互相傳輸數(shù)據(jù)幀，每一個(gè)幀都被編號(hào)，保證數(shù)據(jù)接上互相傳輸數(shù)據(jù)幀，每一個(gè)幀都被編號(hào)，保證數(shù)據(jù)鏈路層保證傳送的幀被對(duì)方收到，且鏈路層保

5、證傳送的幀被對(duì)方收到，且只收到一次只收到一次，并，并且且確保接收幀的順序確保接收幀的順序，雙方通信完畢后拆除連接，雙方通信完畢后拆除連接83.1.2成幀(framing)n為什么要成幀？為什么要成幀？n物理層傳輸比特流時(shí)可能發(fā)生錯(cuò)誤，如何處理？物理層傳輸比特流時(shí)可能發(fā)生錯(cuò)誤，如何處理？在數(shù)據(jù)鏈路層重發(fā)！在數(shù)據(jù)鏈路層重發(fā)！n數(shù)據(jù)鏈路層以幀為單位重發(fā)數(shù)據(jù)鏈路層以幀為單位重發(fā)n在共享鏈路上，發(fā)送方以幀為單位來(lái)競(jìng)爭(zhēng)對(duì)共享鏈在共享鏈路上，發(fā)送方以幀為單位來(lái)競(jìng)爭(zhēng)對(duì)共享鏈路的訪問(wèn)路的訪問(wèn)n將比特流劃分成幀的方法將比特流劃分成幀的方法n字符計(jì)數(shù)法字符計(jì)數(shù)法n含字節(jié)填充的分界符法含字節(jié)填充的分界符法n含位填充的

6、分界標(biāo)志法含位填充的分界標(biāo)志法n物理層編碼違例法物理層編碼違例法標(biāo)識(shí)每一幀的起始標(biāo)識(shí)每一幀的起始和結(jié)束位置和結(jié)束位置9字符計(jì)數(shù)法n幀的幀頭描述幀的長(zhǎng)度幀的幀頭描述幀的長(zhǎng)度缺點(diǎn)：幀頭出錯(cuò)不光影響本數(shù)據(jù)幀，還影響后續(xù)的幀缺點(diǎn)：幀頭出錯(cuò)不光影響本數(shù)據(jù)幀，還影響后續(xù)的幀10含字節(jié)填充的分界符法含字節(jié)填充的分界符法n幀起始和結(jié)束用特殊字節(jié)標(biāo)志，稱為標(biāo)志字節(jié)幀起始和結(jié)束用特殊字節(jié)標(biāo)志，稱為標(biāo)志字節(jié)(Flag）若發(fā)送方數(shù)據(jù)鏈路層發(fā)送的數(shù)據(jù)中有標(biāo)志字節(jié)，則在它前面插入轉(zhuǎn)義字節(jié)若發(fā)送方數(shù)據(jù)鏈路層發(fā)送的數(shù)據(jù)中有標(biāo)志字節(jié)，則在它前面插入轉(zhuǎn)義字節(jié)（ESC），接收方的數(shù)據(jù)鏈路層將數(shù)據(jù)遞交個(gè)網(wǎng)絡(luò)層之前刪除轉(zhuǎn)義字節(jié)），接收

7、方的數(shù)據(jù)鏈路層將數(shù)據(jù)遞交個(gè)網(wǎng)絡(luò)層之前刪除轉(zhuǎn)義字節(jié)11含位填充的分界標(biāo)志法含位填充的分界標(biāo)志法n幀起始和結(jié)束為特殊的位模式幀起始和結(jié)束為特殊的位模式: 01111110若發(fā)送方數(shù)據(jù)鏈路層發(fā)送的數(shù)據(jù)中有若發(fā)送方數(shù)據(jù)鏈路層發(fā)送的數(shù)據(jù)中有5個(gè)連續(xù)的比特個(gè)連續(xù)的比特1時(shí)，則在輸出比特流時(shí)，則在輸出比特流中填充一個(gè)比特中填充一個(gè)比特0原始數(shù)據(jù)原始數(shù)據(jù)填充后的數(shù)據(jù)填充后的數(shù)據(jù)刪除填充后接收方數(shù)據(jù)數(shù)據(jù)刪除填充后接收方數(shù)據(jù)數(shù)據(jù)12物理層編碼違例法物理層編碼違例法n使用沒(méi)有用來(lái)表示數(shù)據(jù)比特的物理層比特使用沒(méi)有用來(lái)表示數(shù)據(jù)比特的物理層比特（即信號(hào)形式）來(lái)作為幀的起始和結(jié)束（即信號(hào)形式）來(lái)作為幀的起始和結(jié)束例如在物理

8、層編碼中，用例如在物理層編碼中，用 表示表示1，用用 表示表示0，則可用則可用 、 作為起始和結(jié)束標(biāo)志作為起始和結(jié)束標(biāo)志133.1.3差錯(cuò)控制n對(duì)于對(duì)于ARQ和和HEC，如果發(fā)送的數(shù)據(jù)丟失，那么接收方是不可能，如果發(fā)送的數(shù)據(jù)丟失，那么接收方是不可能進(jìn)行確認(rèn)的，怎么辦呢？進(jìn)行確認(rèn)的，怎么辦呢？n在發(fā)送方引入定時(shí)器，進(jìn)行在發(fā)送方引入定時(shí)器，進(jìn)行超時(shí)重發(fā)超時(shí)重發(fā)n為了避免相同的幀收到多次，需要對(duì)幀為了避免相同的幀收到多次，需要對(duì)幀進(jìn)行編號(hào)進(jìn)行編號(hào)n由于幀重發(fā)，需要處理幀亂序接收，所以幀編號(hào)一般為由于幀重發(fā)，需要處理幀亂序接收，所以幀編號(hào)一般為序列號(hào)序列號(hào)發(fā)發(fā)收收能發(fā)能發(fā)現(xiàn)錯(cuò)現(xiàn)錯(cuò)誤的誤的冗余冗余信息信

9、息確認(rèn)確認(rèn)檢錯(cuò)重發(fā)（檢錯(cuò)重發(fā)（ARQ）發(fā)發(fā)收收能糾能糾正錯(cuò)正錯(cuò)誤的誤的冗余冗余信息信息前向糾錯(cuò)（前向糾錯(cuò)（FEC）發(fā)發(fā)收收能發(fā)現(xiàn)能發(fā)現(xiàn)和糾正和糾正錯(cuò)誤的錯(cuò)誤的冗余信冗余信息息確認(rèn)確認(rèn)混合糾錯(cuò)檢錯(cuò)（混合糾錯(cuò)檢錯(cuò)（HEC）143.1.4流量控制n流量控制：避免一個(gè)快速的發(fā)送方淹沒(méi)慢速的接收方流量控制：避免一個(gè)快速的發(fā)送方淹沒(méi)慢速的接收方n基于反饋的流量控制基于反饋的流量控制n接收方通過(guò)反饋告訴發(fā)送方能夠發(fā)送多少數(shù)據(jù)，發(fā)送方常用接收方通過(guò)反饋告訴發(fā)送方能夠發(fā)送多少數(shù)據(jù)，發(fā)送方常用窗口機(jī)制來(lái)控制發(fā)送速率窗口機(jī)制來(lái)控制發(fā)送速率n基于速率的流量控制基于速率的流量控制n無(wú)反饋，通過(guò)協(xié)議內(nèi)置機(jī)制控制發(fā)送方發(fā)送

10、速率無(wú)反饋，通過(guò)協(xié)議內(nèi)置機(jī)制控制發(fā)送方發(fā)送速率發(fā)送方發(fā)送方2 3 4 5 6 7 8 9101112 13LARLFSSWS (Send Window Size)LAR:Last Ack received LFS: Last Frame Sent15Chapter 3 數(shù)據(jù)鏈路層n3.1數(shù)據(jù)鏈路層的功能n3.2差錯(cuò)檢測(cè)與糾正n3.3基本數(shù)據(jù)鏈路協(xié)議n3.4滑動(dòng)窗口（Slide Windows）協(xié)議n3.5面向位的協(xié)議HDLCn3.6 Internet中的數(shù)據(jù)鏈路層16檢錯(cuò)碼與糾錯(cuò)碼n檢錯(cuò)碼檢錯(cuò)碼：在發(fā)送數(shù)據(jù)中加入一定的冗余位，使接收方：在發(fā)送數(shù)據(jù)中加入一定的冗余位，使接收方能知道數(shù)據(jù)是否出錯(cuò)，

11、但不知道是哪里出錯(cuò)，這種編能知道數(shù)據(jù)是否出錯(cuò)，但不知道是哪里出錯(cuò)，這種編碼方法叫差錯(cuò)檢測(cè)碼，或簡(jiǎn)稱檢錯(cuò)碼碼方法叫差錯(cuò)檢測(cè)碼，或簡(jiǎn)稱檢錯(cuò)碼n糾錯(cuò)碼：糾錯(cuò)碼：在要發(fā)送的數(shù)據(jù)中加入足夠多的冗余位，使在要發(fā)送的數(shù)據(jù)中加入足夠多的冗余位，使接收方能糾正出錯(cuò)的位，這種編碼方法叫差錯(cuò)校正碼，接收方能糾正出錯(cuò)的位，這種編碼方法叫差錯(cuò)校正碼，或簡(jiǎn)稱糾錯(cuò)碼或簡(jiǎn)稱糾錯(cuò)碼n糾刪碼：既能檢錯(cuò)，又能糾錯(cuò)糾刪碼：既能檢錯(cuò)，又能糾錯(cuò)注：在數(shù)據(jù)通信中，位和比特、注：在數(shù)據(jù)通信中，位和比特、bit是同一個(gè)概念，可以混用是同一個(gè)概念，可以混用173.2.1海明距離n一幀由一幀由m個(gè)數(shù)據(jù)位（即報(bào)文）和個(gè)數(shù)據(jù)位（即報(bào)文）和r個(gè)冗余位個(gè)

12、冗余位（即校驗(yàn)位）組成，總長(zhǎng)度（即校驗(yàn)位）組成，總長(zhǎng)度n=m+r，此長(zhǎng)度，此長(zhǎng)度為為n的單元稱為的單元稱為n位位碼字碼字n兩個(gè)碼字不同的位的數(shù)目稱為兩個(gè)碼字不同的位的數(shù)目稱為海明距離海明距離(Hamming Distance) 例如，例如，10001001 與與10110001它們的海明距離為它們的海明距離為3n對(duì)于對(duì)于n位碼字的集合，只有位碼字的集合，只有2m個(gè)碼字是有效的，個(gè)碼字是有效的，在任意兩個(gè)有效碼字間找出具有最小海明距離在任意兩個(gè)有效碼字間找出具有最小海明距離的兩個(gè)碼字，該海明距離便定義為全部碼字的的兩個(gè)碼字，該海明距離便定義為全部碼字的海明距離。海明距離。18n一種編碼的檢錯(cuò)和糾

13、錯(cuò)能力取決于編碼后碼字的海明一種編碼的檢錯(cuò)和糾錯(cuò)能力取決于編碼后碼字的海明距離的大小距離的大小n為了檢測(cè)出為了檢測(cè)出d d位的錯(cuò)，需要使用距離為位的錯(cuò)，需要使用距離為d+1d+1的編碼的編碼例如：數(shù)據(jù)后加奇偶校驗(yàn)位，編碼后的海明距離為例如：數(shù)據(jù)后加奇偶校驗(yàn)位，編碼后的海明距離為2，能檢測(cè)，能檢測(cè)1位位錯(cuò)錯(cuò)n為了糾正為了糾正d d位的錯(cuò)，必須用距離為位的錯(cuò)，必須用距離為2d+12d+1的編碼的編碼例如有例如有4個(gè)有效碼字：它們是個(gè)有效碼字：它們是0000000000，0000011111，1111100000，1111111111，海明距離為，海明距離為5，能糾正，能糾正2位位錯(cuò)錯(cuò)Cd1C1d1

14、C2ddmin=d+1dmin=2d+1檢錯(cuò)檢錯(cuò)糾錯(cuò)糾錯(cuò)193.2.2單比特糾錯(cuò)碼n設(shè)計(jì)一種編碼，它有設(shè)計(jì)一種編碼，它有m個(gè)信息位和個(gè)信息位和r個(gè)校驗(yàn)位，個(gè)校驗(yàn)位，當(dāng)當(dāng)r滿足什么條件時(shí)，能糾正所有單比特錯(cuò)？滿足什么條件時(shí)，能糾正所有單比特錯(cuò)？ 對(duì)對(duì)2m個(gè)有效碼字的任何一個(gè)而言，有個(gè)有效碼字的任何一個(gè)而言，有n(n=m+r)個(gè)與個(gè)與該碼字距離為該碼字距離為1的無(wú)效碼字的無(wú)效碼字2m個(gè)有效碼字每一個(gè)都對(duì)應(yīng)有個(gè)有效碼字每一個(gè)都對(duì)應(yīng)有n+1個(gè)個(gè)各不相同各不相同的位模的位模式式 而而n位碼字的總的位模式數(shù)量為位碼字的總的位模式數(shù)量為2n個(gè)個(gè)(n+1)2m 2n 將將n=m+r代入代入(m+r+1)2m

15、2m+rm+r+1 2r 糾正單比特錯(cuò)誤所需校驗(yàn)位數(shù)量下界糾正單比特錯(cuò)誤所需校驗(yàn)位數(shù)量下界20校驗(yàn)位：校驗(yàn)位：1 （3，5，7，9，11） 2 （3，6，7，10，11） 4 （5，6，7） 8 （9，10，11） 3=1+2 5=1+4 6=2+4 7=1+2+4 9=1+8 10=2+8 11=1+2+8海明編碼海明編碼m=7，r=4，n=11，顯然，顯然11+1 24，采用偶校驗(yàn)采用偶校驗(yàn) n達(dá)到了糾正單比特錯(cuò)誤的校驗(yàn)位數(shù)量下界！達(dá)到了糾正單比特錯(cuò)誤的校驗(yàn)位數(shù)量下界！n碼字內(nèi)編號(hào)為碼字內(nèi)編號(hào)為2的冪的位是校驗(yàn)位，其余為信息位的冪的位是校驗(yàn)位，其余為信息位n對(duì)編號(hào)為對(duì)編號(hào)為K的信息位來(lái)說(shuō)，

16、的信息位來(lái)說(shuō)，K可以分解成可以分解成2的冪的和的冪的和n每個(gè)校驗(yàn)位的取值應(yīng)使得包括自己在內(nèi)的集合的奇偶值為偶數(shù)（或者奇數(shù)）每個(gè)校驗(yàn)位的取值應(yīng)使得包括自己在內(nèi)的集合的奇偶值為偶數(shù)（或者奇數(shù)）m+r+1 2r只能糾正單比特錯(cuò)！只能糾正單比特錯(cuò)！在接收方，如果校驗(yàn)在接收方，如果校驗(yàn)位位1不滿足偶校驗(yàn)，而不滿足偶校驗(yàn)，而其他校驗(yàn)位都滿足，其他校驗(yàn)位都滿足，則第則第1位出錯(cuò)，位出錯(cuò)，按列按列傳輸傳輸糾正糾正長(zhǎng)度長(zhǎng)度等于等于或小或小于列于列長(zhǎng)的長(zhǎng)的突發(fā)突發(fā)錯(cuò)誤錯(cuò)誤213.2.3檢錯(cuò)碼n在實(shí)際通信中使用糾錯(cuò)碼好還是檢錯(cuò)碼好呢？在實(shí)際通信中使用糾錯(cuò)碼好還是檢錯(cuò)碼好呢？n例：假設(shè)一個(gè)信道誤碼率是例：假設(shè)一個(gè)信道

17、誤碼率是10-6，且出錯(cuò)是孤立產(chǎn)生，且出錯(cuò)是孤立產(chǎn)生的（即只有單比特錯(cuò)），數(shù)據(jù)塊長(zhǎng)度為的（即只有單比特錯(cuò)），數(shù)據(jù)塊長(zhǎng)度為1000比特，傳比特，傳送送1M比特?cái)?shù)據(jù)比特?cái)?shù)據(jù)若采用糾錯(cuò)編碼，每個(gè)數(shù)據(jù)塊需要若采用糾錯(cuò)編碼，每個(gè)數(shù)據(jù)塊需要10個(gè)校驗(yàn)位個(gè)校驗(yàn)位（2101011），需要），需要10000個(gè)校驗(yàn)位；個(gè)校驗(yàn)位； 若采用檢錯(cuò)編碼，每個(gè)數(shù)據(jù)塊只需若采用檢錯(cuò)編碼，每個(gè)數(shù)據(jù)塊只需1個(gè)奇偶校驗(yàn)位，只個(gè)奇偶校驗(yàn)位，只需需1000個(gè)校驗(yàn)位和一個(gè)重傳數(shù)據(jù)塊，共需要個(gè)校驗(yàn)位和一個(gè)重傳數(shù)據(jù)塊，共需要2001比比特特n可靠性高的信道（例如光纖、電纜等）多采用檢錯(cuò)編可靠性高的信道（例如光纖、電纜等）多采用檢錯(cuò)編碼，但在

18、可靠性不高（例如無(wú)線）及單工信道中可能碼，但在可靠性不高（例如無(wú)線）及單工信道中可能需要糾錯(cuò)編碼需要糾錯(cuò)編碼檢錯(cuò)重發(fā)檢錯(cuò)重發(fā) (ARQ) vs 混合糾錯(cuò)檢錯(cuò)混合糾錯(cuò)檢錯(cuò) (HEC)校驗(yàn)位數(shù)量下界校驗(yàn)位數(shù)量下界m+r+1 2r3.2.3檢錯(cuò)碼檢錯(cuò)碼n多項(xiàng)式編碼也常稱為循環(huán)冗余校驗(yàn)碼多項(xiàng)式編碼也常稱為循環(huán)冗余校驗(yàn)碼 (CRC：Cyclic Redundancy Check)22數(shù)據(jù)的多項(xiàng)式表示：數(shù)據(jù)的多項(xiàng)式表示：m位的數(shù)據(jù)用位的數(shù)據(jù)用m項(xiàng)多項(xiàng)多項(xiàng)式表示，它的各項(xiàng)為項(xiàng)式表示，它的各項(xiàng)為X m-1X0，它的系，它的系數(shù)（數(shù)（0或者或者1）與數(shù)據(jù)中相應(yīng)的位對(duì)應(yīng)）與數(shù)據(jù)中相應(yīng)的位對(duì)應(yīng)例如：例如：11000

19、1可表示成可表示成X5+X4+123多項(xiàng)式編碼n編碼操作編碼操作n發(fā)送方：給定一個(gè)發(fā)送方：給定一個(gè)m位的數(shù)據(jù)，生成位的數(shù)據(jù)，生成r位的序列（也稱位的序列（也稱為幀檢驗(yàn)序列為幀檢驗(yàn)序列FCS，F(xiàn)rame Check Series），形成），形成（m+r）的碼字）的碼字(幀幀)，該碼字能被某個(gè)事先確定的多，該碼字能被某個(gè)事先確定的多項(xiàng)式整除項(xiàng)式整除n接收方：用相同的多項(xiàng)式去除收到的幀，如果無(wú)余數(shù)，接收方：用相同的多項(xiàng)式去除收到的幀，如果無(wú)余數(shù)，則認(rèn)為數(shù)據(jù)幀無(wú)差錯(cuò)。則認(rèn)為數(shù)據(jù)幀無(wú)差錯(cuò)。注：多項(xiàng)式編碼是建立在多項(xiàng)式運(yùn)算基礎(chǔ)之上的，多項(xiàng)式算術(shù)運(yùn)算的加減法都注：多項(xiàng)式編碼是建立在多項(xiàng)式運(yùn)算基礎(chǔ)之上的，多項(xiàng)

20、式算術(shù)運(yùn)算的加減法都等同于異或運(yùn)算等同于異或運(yùn)算24多項(xiàng)式編碼的推導(dǎo)設(shè)數(shù)據(jù)多項(xiàng)式表示為設(shè)數(shù)據(jù)多項(xiàng)式表示為M（X） m位序列位序列 事先約定的除數(shù)為事先約定的除數(shù)為G（X） r+1位序列位序列 幀校驗(yàn)序列幀校驗(yàn)序列FCS為為F（X） r位序列位序列加了校驗(yàn)序列的幀為加了校驗(yàn)序列的幀為T（X）=X r M（X）+F（X） m+r位序列位序列設(shè)設(shè)X r M（X）/G（X）=P（X）+R（X）/G（X）X r M（X）-R（X）/G（X）=P（X）在模在模2運(yùn)算中，加法與減法等同，取運(yùn)算中，加法與減法等同，取F（X）=R（X）就）就能使能使T（X）被）被G（X）整除）整除生成多項(xiàng)式，生成多項(xiàng)式，最高和

21、最低位最高和最低位必須為必須為125m=10, r=4T（X）=X r M（X）+F（X）26多項(xiàng)式編碼的檢錯(cuò)率n能夠檢測(cè)到所有的一位錯(cuò)誤能夠檢測(cè)到所有的一位錯(cuò)誤n若若G（X）包含因子）包含因子X(jué)+1，則可以檢測(cè)到奇數(shù)個(gè)位發(fā)生錯(cuò)誤，則可以檢測(cè)到奇數(shù)個(gè)位發(fā)生錯(cuò)誤n能檢驗(yàn)出所有長(zhǎng)度小于等于能檢驗(yàn)出所有長(zhǎng)度小于等于r的突發(fā)錯(cuò)誤的突發(fā)錯(cuò)誤n若突發(fā)長(zhǎng)度為若突發(fā)長(zhǎng)度為r+1，當(dāng)且僅當(dāng)錯(cuò)誤多項(xiàng)式與，當(dāng)且僅當(dāng)錯(cuò)誤多項(xiàng)式與G（X）相同時(shí)才被整除。根）相同時(shí)才被整除。根據(jù)突發(fā)錯(cuò)誤長(zhǎng)度的定義，其第據(jù)突發(fā)錯(cuò)誤長(zhǎng)度的定義，其第1位和最后位和最后1位必須是位必須是1，因此與，因此與G（X）完）完全相同的概率即誤判概率為全

22、相同的概率即誤判概率為(1/2)r-1（所有位模式等概率）（所有位模式等概率）n對(duì)于長(zhǎng)度大于對(duì)于長(zhǎng)度大于r+1的突發(fā)錯(cuò)誤，則誤判概率為的突發(fā)錯(cuò)誤，則誤判概率為(1/2)r（所有位模式等概率）（所有位模式等概率）E（X）中的每）中的每1位都對(duì)應(yīng)著原數(shù)據(jù)塊中出錯(cuò)的位，則對(duì)于位都對(duì)應(yīng)著原數(shù)據(jù)塊中出錯(cuò)的位，則對(duì)于長(zhǎng)度為長(zhǎng)度為k的突發(fā)性錯(cuò)誤，有：的突發(fā)性錯(cuò)誤，有：E（X）=Xi（Xk-1+1）G（X)為最高位和最低位均為為最高位和最低位均為1的的r階階多項(xiàng)式多項(xiàng)式(最高次項(xiàng)為最高次項(xiàng)為Xr)27常用的生成多項(xiàng)式國(guó)際標(biāo)準(zhǔn)nCRC-12=X12+X11+X3+X2+X+1nCRC-16= X16 +X15

23、+X2 +1nCRC-CCITT= X16 +X15 +X5 +1nCRC-32=X32+X26+X23 +X22 +X16 +X12 +X11 +X10 +X8 +X7 +X5 +X4 +X2+X+128Chapter 3 數(shù)據(jù)鏈路層n3.1數(shù)據(jù)鏈路層的功能n3.2差錯(cuò)檢測(cè)與糾正n3.3基本數(shù)據(jù)鏈路協(xié)議n3.4滑動(dòng)窗口（Slide Windows）協(xié)議n3.5面向位的協(xié)議HDLCn3.6 Internet中的數(shù)據(jù)鏈路層293.3基本數(shù)據(jù)鏈路協(xié)議n一個(gè)無(wú)限制的單工協(xié)議（一個(gè)無(wú)限制的單工協(xié)議（An Unrestricted Simplex Protocol）n停停-等協(xié)議（等協(xié)議（Stop-an

24、d-Wait Protocol）n有噪音信道的停有噪音信道的停-等協(xié)議（等協(xié)議（Stop-and-Wait Protocol for a Noisy Channel）303.3.1一個(gè)無(wú)限制的單工協(xié)議n假設(shè)：數(shù)據(jù)單向傳輸，收發(fā)雙方的網(wǎng)絡(luò)層一直假設(shè)：數(shù)據(jù)單向傳輸，收發(fā)雙方的網(wǎng)絡(luò)層一直處于就緒狀態(tài)，處理時(shí)間可忽略不計(jì)，接收緩處于就緒狀態(tài)，處理時(shí)間可忽略不計(jì)，接收緩沖空間無(wú)限大，信道不會(huì)損壞或丟失幀沖空間無(wú)限大，信道不會(huì)損壞或丟失幀n發(fā)送方無(wú)限循環(huán)地重復(fù)三個(gè)動(dòng)作：發(fā)送方無(wú)限循環(huán)地重復(fù)三個(gè)動(dòng)作：n從網(wǎng)絡(luò)層取分組從網(wǎng)絡(luò)層取分組構(gòu)造幀構(gòu)造幀發(fā)出幀。發(fā)出幀。 沒(méi)有任何差錯(cuò)控制和流量控制沒(méi)有任何差錯(cuò)控制和流量

25、控制n接收方也是無(wú)限循環(huán)地重復(fù)三個(gè)動(dòng)作：接收方也是無(wú)限循環(huán)地重復(fù)三個(gè)動(dòng)作：n等待事件（一個(gè)未損壞幀的到達(dá)）發(fā)生等待事件（一個(gè)未損壞幀的到達(dá)）發(fā)生幀到達(dá)后，幀到達(dá)后，從硬件緩沖中取出新到的幀從硬件緩沖中取出新到的幀將幀的數(shù)據(jù)部分傳給網(wǎng)將幀的數(shù)據(jù)部分傳給網(wǎng)絡(luò)層絡(luò)層全雙工：可以同時(shí)在兩個(gè)方向上發(fā)送數(shù)據(jù)全雙工：可以同時(shí)在兩個(gè)方向上發(fā)送數(shù)據(jù)半雙工：可以在兩個(gè)方向上發(fā)送數(shù)據(jù)，但某一時(shí)刻只能在一個(gè)方向上發(fā)送數(shù)據(jù)半雙工：可以在兩個(gè)方向上發(fā)送數(shù)據(jù)，但某一時(shí)刻只能在一個(gè)方向上發(fā)送數(shù)據(jù)單工：只能在某一個(gè)方向上發(fā)送數(shù)據(jù)單工：只能在某一個(gè)方向上發(fā)送數(shù)據(jù)313.3.2停-等協(xié)議n假設(shè)：接收緩沖只能存放假設(shè)：接收緩沖只能存

26、放一個(gè)幀，且信道無(wú)噪一個(gè)幀，且信道無(wú)噪n發(fā)送方在發(fā)送一幀后必須發(fā)送方在發(fā)送一幀后必須停止發(fā)送，等待接收方停止發(fā)送，等待接收方反反饋確認(rèn)饋確認(rèn)n接收方正確收到幀后向發(fā)接收方正確收到幀后向發(fā)送方發(fā)一反饋確認(rèn)短幀送方發(fā)一反饋確認(rèn)短幀（始終正確接收始終正確接收）n幀的發(fā)送和反饋嚴(yán)格交替幀的發(fā)送和反饋嚴(yán)格交替進(jìn)行，一般采用半雙工信進(jìn)行，一般采用半雙工信道道32噪音信道帶來(lái)的問(wèn)題n信道噪聲會(huì)導(dǎo)致幀信道噪聲會(huì)導(dǎo)致幀損壞損壞甚至甚至丟失丟失，需要引入，需要引入確認(rèn)重確認(rèn)重傳傳機(jī)制來(lái)提高可靠性機(jī)制來(lái)提高可靠性n幀損壞：有糾錯(cuò)碼，則嘗試糾錯(cuò)；若不能糾錯(cuò)，根據(jù)檢幀損壞：有糾錯(cuò)碼，則嘗試糾錯(cuò)；若不能糾錯(cuò)，根據(jù)檢錯(cuò)碼檢

27、錯(cuò)，然后發(fā)送確認(rèn)幀告知幀錯(cuò)誤，發(fā)送方重傳幀錯(cuò)碼檢錯(cuò)，然后發(fā)送確認(rèn)幀告知幀錯(cuò)誤，發(fā)送方重傳幀n幀丟失：發(fā)送方收不到確認(rèn)幀，因此必須引入超時(shí)重傳幀丟失：發(fā)送方收不到確認(rèn)幀，因此必須引入超時(shí)重傳機(jī)制機(jī)制n設(shè)置定時(shí)器，超時(shí)時(shí)間值應(yīng)稍大于往返時(shí)間和接收方的接設(shè)置定時(shí)器，超時(shí)時(shí)間值應(yīng)稍大于往返時(shí)間和接收方的接收處理時(shí)間之和收處理時(shí)間之和n通過(guò)為幀編制通過(guò)為幀編制序列號(hào)序列號(hào)來(lái)解決重傳過(guò)程中的重復(fù)幀的來(lái)解決重傳過(guò)程中的重復(fù)幀的問(wèn)題，例如在簡(jiǎn)單停問(wèn)題，例如在簡(jiǎn)單停-等協(xié)議中只需等協(xié)議中只需1個(gè)比特個(gè)比特（“0”“1”，“1”“0”）333.3.3有噪音信道的停-等協(xié)議n收發(fā)雙方維護(hù)各自的幀序列號(hào)收發(fā)雙方維護(hù)各

28、自的幀序列號(hào)nN(S)：發(fā)送方當(dāng)前所發(fā)幀的序列號(hào)：發(fā)送方當(dāng)前所發(fā)幀的序列號(hào)nN(R)：接收方當(dāng)前所期待接收的幀序號(hào)：接收方當(dāng)前所期待接收的幀序號(hào)n發(fā)送方發(fā)送幀（序列號(hào)發(fā)送方發(fā)送幀（序列號(hào)N(S)） 并啟動(dòng)定時(shí)器并啟動(dòng)定時(shí)器n接收方收到幀后，對(duì)其序列號(hào)和接收方收到幀后，對(duì)其序列號(hào)和N(R)進(jìn)行比較：進(jìn)行比較：n若不等，則將其作為無(wú)效幀丟棄；若不等，則將其作為無(wú)效幀丟棄；n若相等則對(duì)其進(jìn)行校驗(yàn)，校驗(yàn)正確將若相等則對(duì)其進(jìn)行校驗(yàn)，校驗(yàn)正確將N(R)加加1并放入確并放入確認(rèn)幀中反饋回發(fā)送方；若校驗(yàn)出錯(cuò)，則丟棄幀，保持認(rèn)幀中反饋回發(fā)送方；若校驗(yàn)出錯(cuò)，則丟棄幀，保持N(R) 不變并放入確認(rèn)幀中反饋回發(fā)送方不

29、變并放入確認(rèn)幀中反饋回發(fā)送方n發(fā)送方若在規(guī)定的時(shí)間內(nèi)沒(méi)有收到接收方的確認(rèn)幀，發(fā)送方若在規(guī)定的時(shí)間內(nèi)沒(méi)有收到接收方的確認(rèn)幀，就認(rèn)為數(shù)據(jù)幀丟失，重發(fā)幀；若收到確認(rèn)幀，比較確就認(rèn)為數(shù)據(jù)幀丟失，重發(fā)幀；若收到確認(rèn)幀，比較確認(rèn)幀中的序列號(hào)和認(rèn)幀中的序列號(hào)和N(S)：n若相等，則保持若相等，則保持N(S)不變，重發(fā)幀不變，重發(fā)幀n若不等，則將確認(rèn)幀中的序列號(hào)賦予若不等，則將確認(rèn)幀中的序列號(hào)賦予N(S)，發(fā)送新的幀，發(fā)送新的幀（序列號(hào)（序列號(hào)N(S)）發(fā)送方每發(fā)送一幀，都重新啟動(dòng)定時(shí)器然后停下來(lái)等待其確認(rèn)幀發(fā)送方每發(fā)送一幀，都重新啟動(dòng)定時(shí)器然后停下來(lái)等待其確認(rèn)幀34停-等協(xié)議對(duì)信道利用率的影響n在時(shí)延大的信

30、道（如衛(wèi)星通信）中，停在時(shí)延大的信道（如衛(wèi)星通信）中，停-等協(xié)議的效率低！等協(xié)議的效率低！n考慮兩個(gè)地面站通過(guò)衛(wèi)星通信，典型的傳輸時(shí)間約為考慮兩個(gè)地面站通過(guò)衛(wèi)星通信，典型的傳輸時(shí)間約為270ms。假設(shè)一。假設(shè)一個(gè)幀的發(fā)送時(shí)間為個(gè)幀的發(fā)送時(shí)間為20ms，則從發(fā)送站開始發(fā)送算起，經(jīng)，則從發(fā)送站開始發(fā)送算起，經(jīng)20ms+ 270ms=290ms，數(shù)據(jù)幀才能到達(dá)目的站。假設(shè)不考慮目的站的處理，數(shù)據(jù)幀才能到達(dá)目的站。假設(shè)不考慮目的站的處理時(shí)間，且認(rèn)為確認(rèn)幀非常短，其發(fā)送時(shí)間可忽略不計(jì)，則又需時(shí)間，且認(rèn)為確認(rèn)幀非常短，其發(fā)送時(shí)間可忽略不計(jì)，則又需270ms確認(rèn)幀才能被發(fā)送站收到確認(rèn)幀才能被發(fā)送站收到信道的

31、利用率為：信道的利用率為：20ms/(290ms+270ms)=1/28，非常低！這是，非常低！這是由于每發(fā)一個(gè)幀之前都必須等待前一個(gè)幀的確認(rèn)幀由于每發(fā)一個(gè)幀之前都必須等待前一個(gè)幀的確認(rèn)幀n為了提高傳輸效率，可以設(shè)想讓發(fā)送站連續(xù)不斷地發(fā)送數(shù)據(jù)幀，當(dāng)發(fā)為了提高傳輸效率，可以設(shè)想讓發(fā)送站連續(xù)不斷地發(fā)送數(shù)據(jù)幀，當(dāng)發(fā)完第完第28幀數(shù)據(jù)后，恰好第幀數(shù)據(jù)后，恰好第1幀的確認(rèn)幀到達(dá)，根據(jù)確認(rèn)可緊接著發(fā)第幀的確認(rèn)幀到達(dá)，根據(jù)確認(rèn)可緊接著發(fā)第29幀或重發(fā)第幀或重發(fā)第1幀。以后，每過(guò)幀。以后，每過(guò)20ms（發(fā)一個(gè)幀）就有一個(gè)確認(rèn)幀到（發(fā)一個(gè)幀）就有一個(gè)確認(rèn)幀到達(dá)，這樣信道的利用率就大大地提高了達(dá)，這樣信道的利用率

32、就大大地提高了n允許發(fā)送站連續(xù)發(fā)送多個(gè)幀而不需等待確認(rèn)的做法稱作管道化允許發(fā)送站連續(xù)發(fā)送多個(gè)幀而不需等待確認(rèn)的做法稱作管道化（pipelining），屬于一種窗口（），屬于一種窗口（windows）機(jī)制）機(jī)制35Chapter 3 數(shù)據(jù)鏈路層n3.1數(shù)據(jù)鏈路層的功能n3.2差錯(cuò)檢測(cè)與糾正n3.3基本數(shù)據(jù)鏈路協(xié)議n3.4滑動(dòng)窗口（Slide Windows）協(xié)議n3.5面向位的協(xié)議HDLCn3.6 Internet中的數(shù)據(jù)鏈路層長(zhǎng)延遲信道/鏈路利用率n接收方確認(rèn)達(dá)到之前，發(fā)送方最大發(fā)送幀數(shù)量nwmax= 2BD+1nBD為帶寬（幀/秒）延遲（單向延遲）乘積n鏈路利用率上限：nw/(2BD+1)n

33、w為發(fā)送方在收到確認(rèn)之前允許發(fā)送幀數(shù)量36W越大，信道/鏈路利用率越高可通過(guò)窗口來(lái)控制發(fā)送方每次能夠發(fā)送的數(shù)據(jù)量373.4滑動(dòng)窗口（Slide Windows）協(xié)議n滑動(dòng)窗口協(xié)議是一種非?？煽俊⑦m用于各種條滑動(dòng)窗口協(xié)議是一種非?？煽俊⑦m用于各種條件的通用流量控制協(xié)議，特別是在效率、復(fù)雜件的通用流量控制協(xié)議，特別是在效率、復(fù)雜性及對(duì)緩沖區(qū)的需求等方面可作靈活調(diào)配性及對(duì)緩沖區(qū)的需求等方面可作靈活調(diào)配n主要的滑動(dòng)窗口協(xié)議有回退主要的滑動(dòng)窗口協(xié)議有回退n幀協(xié)議和選擇性幀協(xié)議和選擇性重傳協(xié)議兩種重傳協(xié)議兩種n實(shí)際上，有噪音信道的停實(shí)際上，有噪音信道的停-等協(xié)議就是滑動(dòng)窗等協(xié)議就是滑動(dòng)窗口協(xié)議的一個(gè)特例，

34、將?？趨f(xié)議的一個(gè)特例，將停-等協(xié)議中的幀序列等協(xié)議中的幀序列號(hào)從號(hào)從1位擴(kuò)展到位擴(kuò)展到n位（范圍為位（范圍為02n-1），收發(fā)），收發(fā)雙方維護(hù)的序列號(hào)也變?yōu)橐唤M序列號(hào)表，分別雙方維護(hù)的序列號(hào)也變?yōu)橐唤M序列號(hào)表，分別稱作稱作發(fā)送窗口發(fā)送窗口（sending window）和）和接收窗接收窗口口（receiving window）38發(fā)送窗口n發(fā)送窗口發(fā)送窗口就是發(fā)送方允許不等確認(rèn)而連續(xù)發(fā)送的幀的就是發(fā)送方允許不等確認(rèn)而連續(xù)發(fā)送的幀的序列號(hào)列表序列號(hào)列表n允許連續(xù)發(fā)送的幀的數(shù)量稱為發(fā)送允許連續(xù)發(fā)送的幀的數(shù)量稱為發(fā)送窗口尺寸窗口尺寸，表示為，表示為SWS。發(fā)送方必須有。發(fā)送方必須有SWS個(gè)輸出緩沖區(qū)

35、來(lái)存放個(gè)輸出緩沖區(qū)來(lái)存放SWS個(gè)數(shù)據(jù)幀的副本以備數(shù)據(jù)幀的重發(fā)個(gè)數(shù)據(jù)幀的副本以備數(shù)據(jù)幀的重發(fā)n當(dāng)發(fā)送方收到發(fā)送窗口下邊界幀的肯定確認(rèn)時(shí)，將發(fā)當(dāng)發(fā)送方收到發(fā)送窗口下邊界幀的肯定確認(rèn)時(shí)，將發(fā)送窗口整體向前滑動(dòng)，從輸出緩沖區(qū)中將下邊界及其送窗口整體向前滑動(dòng)，從輸出緩沖區(qū)中將下邊界及其之前的幀副本刪除之前的幀副本刪除發(fā)送方發(fā)送方下邊界幀即為接收方正確有序接收的發(fā)送窗口下邊界幀即為接收方正確有序接收的發(fā)送窗口中序列號(hào)最大的中序列號(hào)最大的幀幀例如接收方收到例如接收方收到1，3，4，5，如果收到，如果收到2，則，則下邊界幀為下邊界幀為5，發(fā)送方收到確認(rèn)后，發(fā)送方收到確認(rèn)后，LAR設(shè)為設(shè)為5LARLFSSWS滑

36、動(dòng)方向滑動(dòng)方向LAR: 已被確認(rèn)接收的幀的最大序列號(hào)已被確認(rèn)接收的幀的最大序列號(hào) LFS: 已已發(fā)送幀的最大序列號(hào)發(fā)送幀的最大序列號(hào)滑出的幀滑出的幀發(fā)送方發(fā)送的幀必須滿足：發(fā)送方發(fā)送的幀必須滿足：0LFS-LARSWS39接收窗口n接收窗口接收窗口是接收方允許接收的幀的是接收方允許接收的幀的序列號(hào)范圍序列號(hào)范圍n允許接收的幀的數(shù)量稱為接收窗口尺寸。同樣接收方允許接收的幀的數(shù)量稱為接收窗口尺寸。同樣接收方也必須設(shè)置相應(yīng)數(shù)量的輸入緩沖區(qū)來(lái)支持接收窗口也必須設(shè)置相應(yīng)數(shù)量的輸入緩沖區(qū)來(lái)支持接收窗口n對(duì)接收方收到的幀的序列號(hào)落在接收窗口外的幀被直對(duì)接收方收到的幀的序列號(hào)落在接收窗口外的幀被直接丟棄。落在

37、接收窗口內(nèi)的幀若校驗(yàn)正確：接丟棄。落在接收窗口內(nèi)的幀若校驗(yàn)正確：n當(dāng)接收幀不是接收窗口下邊界幀時(shí)，必須暫存在輸入緩沖區(qū)當(dāng)接收幀不是接收窗口下邊界幀時(shí)，必須暫存在輸入緩沖區(qū)n當(dāng)接收到接收窗口下邊界幀時(shí)，會(huì)將其連同后面連續(xù)的若干當(dāng)接收到接收窗口下邊界幀時(shí)，會(huì)將其連同后面連續(xù)的若干個(gè)檢驗(yàn)過(guò)的正確幀按順序交給網(wǎng)絡(luò)層，在發(fā)回確認(rèn)幀的同時(shí)個(gè)檢驗(yàn)過(guò)的正確幀按順序交給網(wǎng)絡(luò)層，在發(fā)回確認(rèn)幀的同時(shí)將接收窗口向前滑動(dòng)相應(yīng)的數(shù)量將接收窗口向前滑動(dòng)相應(yīng)的數(shù)量下邊界幀即為序列號(hào)為接收窗口下邊下邊界幀即為序列號(hào)為接收窗口下邊界的界的幀幀例如接收方收到例如接收方收到1，3，4，5，如果收到，如果收到2，則下邊界幀為則下邊界幀

38、為5，發(fā)送確認(rèn)發(fā)送確認(rèn)后，后，LFR設(shè)設(shè)為為5接收方接收方LFRLAFRWS正確有序正確有序接收的幀接收的幀LFR: 按序正確接收的幀的最大序列號(hào)按序正確接收的幀的最大序列號(hào) LAF: 可接收幀的最大序列號(hào)可接收幀的最大序列號(hào)接收方收到的幀的序列號(hào)必須滿足：接收方收到的幀的序列號(hào)必須滿足：0LAF-LFRRWS40停-等協(xié)議的窗口機(jī)制n幀的序列號(hào)長(zhǎng)度為1比特（01），發(fā)送窗口和接收窗口的尺寸都為1010101010101010101010101發(fā)送發(fā)送方方接收方接收方時(shí)間時(shí)間t01234541滑動(dòng)窗口示意圖01234567012345670123456701234567012345670123

39、4567012345670123456701234567012345670123456701234567發(fā)送方發(fā)送方接收方接收方n幀的序列號(hào)長(zhǎng)度為3比特（07），發(fā)送窗口和接收窗口的尺寸都設(shè)置為3時(shí)間時(shí)間t01234542捎帶確認(rèn)n在實(shí)際通信中，通常收發(fā)雙方都相互發(fā)送數(shù)據(jù)在實(shí)際通信中，通常收發(fā)雙方都相互發(fā)送數(shù)據(jù)n為了提高效率，可以將確認(rèn)信息放在數(shù)據(jù)幀中為了提高效率，可以將確認(rèn)信息放在數(shù)據(jù)幀中(幀頭幀頭ACK域域)連同數(shù)據(jù)一起發(fā)送給對(duì)方，這種方式稱為捎帶連同數(shù)據(jù)一起發(fā)送給對(duì)方，這種方式稱為捎帶確認(rèn)（確認(rèn)（piggybacking）n當(dāng)一方收到對(duì)方的數(shù)據(jù)幀后：當(dāng)一方收到對(duì)方的數(shù)據(jù)幀后：n若正好也有

40、數(shù)據(jù)需發(fā)給對(duì)方，則立即可使用捎帶確認(rèn)若正好也有數(shù)據(jù)需發(fā)給對(duì)方，則立即可使用捎帶確認(rèn)n若暫時(shí)沒(méi)有數(shù)據(jù)需發(fā)給對(duì)方或數(shù)據(jù)還未準(zhǔn)備好，則等待一定的若暫時(shí)沒(méi)有數(shù)據(jù)需發(fā)給對(duì)方或數(shù)據(jù)還未準(zhǔn)備好，則等待一定的時(shí)間，如果在該時(shí)間內(nèi)準(zhǔn)備好了數(shù)據(jù)，則可以使用捎帶確認(rèn)，時(shí)間，如果在該時(shí)間內(nèi)準(zhǔn)備好了數(shù)據(jù)，則可以使用捎帶確認(rèn)，如果未準(zhǔn)備好，為了防止對(duì)方等待時(shí)間過(guò)長(zhǎng)而超時(shí)重發(fā)，必須如果未準(zhǔn)備好，為了防止對(duì)方等待時(shí)間過(guò)長(zhǎng)而超時(shí)重發(fā)，必須立即發(fā)送一個(gè)單獨(dú)的確認(rèn)幀立即發(fā)送一個(gè)單獨(dú)的確認(rèn)幀n捎帶確認(rèn)通過(guò)對(duì)某一個(gè)幀的確認(rèn)來(lái)代替對(duì)該幀之前的捎帶確認(rèn)通過(guò)對(duì)某一個(gè)幀的確認(rèn)來(lái)代替對(duì)該幀之前的所有幀的確認(rèn)所有幀的確認(rèn)滑動(dòng)窗口協(xié)議n實(shí)現(xiàn)高效可靠

41、傳輸，支持流量控制實(shí)現(xiàn)高效可靠傳輸，支持流量控制n為解決為解決重重復(fù)幀和幀亂序問(wèn)題，幀中攜帶復(fù)幀和幀亂序問(wèn)題，幀中攜帶序列號(hào)序列號(hào)n通過(guò)通過(guò)確認(rèn)重傳確認(rèn)重傳解決幀損壞或者丟失解決幀損壞或者丟失問(wèn)題問(wèn)題n通過(guò)調(diào)整窗口大小實(shí)現(xiàn)流量控制通過(guò)調(diào)整窗口大小實(shí)現(xiàn)流量控制n發(fā)送窗口發(fā)送窗口就是發(fā)送方允許不等確認(rèn)而連續(xù)發(fā)送的幀的就是發(fā)送方允許不等確認(rèn)而連續(xù)發(fā)送的幀的序列號(hào)列表序列號(hào)列表n接收接收窗口窗口是接收方允許接收的幀的是接收方允許接收的幀的序列號(hào)序列號(hào)范圍范圍43發(fā)送方發(fā)送方LARLFSSWS滑動(dòng)方向滑動(dòng)方向滑出的幀滑出的幀接收方接收方LFRLAFRWS正確有序正確有序接收的幀接收的幀LAR: 已被確認(rèn)

42、接收的幀的最大序列號(hào)已被確認(rèn)接收的幀的最大序列號(hào) LFS: 已已發(fā)送幀的最大序列號(hào)發(fā)送幀的最大序列號(hào)LFR: 按序正確接收的幀的最大序列號(hào)按序正確接收的幀的最大序列號(hào) LAF: 可接收幀的最大序列號(hào)可接收幀的最大序列號(hào)主要的滑動(dòng)窗口協(xié)議有回退主要的滑動(dòng)窗口協(xié)議有回退n幀協(xié)議和選擇性重傳幀協(xié)議和選擇性重傳協(xié)議協(xié)議44n回退回退n幀協(xié)議中，發(fā)送窗口的尺寸大于幀協(xié)議中，發(fā)送窗口的尺寸大于1，而接收窗，而接收窗口的尺寸則等于口的尺寸則等于1n發(fā)送方保持一定數(shù)量的緩存來(lái)保存沒(méi)有確認(rèn)的數(shù)據(jù)幀，接發(fā)送方保持一定數(shù)量的緩存來(lái)保存沒(méi)有確認(rèn)的數(shù)據(jù)幀，接收方?jīng)]有緩存的要求收方?jīng)]有緩存的要求n某個(gè)幀出錯(cuò)或丟失，丟棄該

43、幀及其所有的后續(xù)幀，某個(gè)幀出錯(cuò)或丟失，丟棄該幀及其所有的后續(xù)幀，不作任何確認(rèn)不作任何確認(rèn)n發(fā)送方超時(shí)后需重發(fā)出錯(cuò)或丟失的幀及其后續(xù)所有發(fā)送方超時(shí)后需重發(fā)出錯(cuò)或丟失的幀及其后續(xù)所有的幀的幀回退n幀協(xié)議（go-back-n）45回退回退n幀協(xié)議舉例幀協(xié)議舉例在誤碼率高的情況下，會(huì)顯著降低信道的利用率在誤碼率高的情況下，會(huì)顯著降低信道的利用率重傳定時(shí)器超時(shí)46選擇性重傳協(xié)議（Selective Repeat）n發(fā)送和接收窗口的尺寸都大于發(fā)送和接收窗口的尺寸都大于1，兩者大小一般相同，兩者大小一般相同n接收方緩存出錯(cuò)幀之后的其它數(shù)據(jù)幀（落在接收窗口）接收方緩存出錯(cuò)幀之后的其它數(shù)據(jù)幀（落在接收窗口）n發(fā)

44、送方只需（超時(shí)）重發(fā)出錯(cuò)的幀，而不需重發(fā)其后的所有發(fā)送方只需（超時(shí)）重發(fā)出錯(cuò)的幀，而不需重發(fā)其后的所有后續(xù)幀后續(xù)幀n接收方正確收到重發(fā)的幀后，可對(duì)其后連續(xù)的已接收的正確接收方正確收到重發(fā)的幀后，可對(duì)其后連續(xù)的已接收的正確幀一起確認(rèn)（最大序列號(hào)的確認(rèn)），并交送網(wǎng)絡(luò)層幀一起確認(rèn)（最大序列號(hào)的確認(rèn)），并交送網(wǎng)絡(luò)層n發(fā)送端為每一個(gè)輸出緩存區(qū)設(shè)置一個(gè)定時(shí)器，定時(shí)器一旦超發(fā)送端為每一個(gè)輸出緩存區(qū)設(shè)置一個(gè)定時(shí)器，定時(shí)器一旦超時(shí)，相應(yīng)輸出緩存區(qū)中的幀就被重發(fā)。時(shí)，相應(yīng)輸出緩存區(qū)中的幀就被重發(fā)。47選擇性重傳協(xié)議選擇性重傳協(xié)議1. 發(fā)送方可以把重復(fù)發(fā)送方可以把重復(fù)ACK作為幀丟失的依據(jù)，實(shí)現(xiàn)快速重傳，例如上例中

45、，當(dāng)作為幀丟失的依據(jù)，實(shí)現(xiàn)快速重傳，例如上例中，當(dāng)發(fā)送方收到第二個(gè)發(fā)送方收到第二個(gè)ACK 1的時(shí)候，可以不用等待超時(shí)就直接重傳第的時(shí)候，可以不用等待超時(shí)就直接重傳第2幀幀2. 發(fā)送方在檢測(cè)到接收的幀發(fā)生錯(cuò)誤的時(shí)候，也可以針對(duì)該出錯(cuò)幀發(fā)送發(fā)送方在檢測(cè)到接收的幀發(fā)生錯(cuò)誤的時(shí)候，也可以針對(duì)該出錯(cuò)幀發(fā)送NAK，要求發(fā)送方重傳，但是這不適合幀在信道中丟失的情況要求發(fā)送方重傳，但是這不適合幀在信道中丟失的情況48幀序列號(hào)重疊幀序列號(hào)重疊現(xiàn)象：序列號(hào)空間有限，不斷遞增，會(huì)出現(xiàn)回繞現(xiàn)象：序列號(hào)空間有限，不斷遞增，會(huì)出現(xiàn)回繞假設(shè)序列號(hào)長(zhǎng)度為假設(shè)序列號(hào)長(zhǎng)度為n比特，則可用序列號(hào)數(shù)量為比特，則可用序列號(hào)數(shù)量為2n，

46、不發(fā)生幀序列號(hào)重疊的條件為：，不發(fā)生幀序列號(hào)重疊的條件為：SWS+RWS 2nSWS：發(fā)送窗口大??；：發(fā)送窗口大小；RWS：接收窗口大?。航邮沾翱诖笮WSRWS，一般取，一般取SWS = RWS，則有，則有SWS 2n-1，RWS 2n-1說(shuō)明：這是接收窗口，表示接說(shuō)明：這是接收窗口，表示接收方能接收序列號(hào)收方能接收序列號(hào)04的幀，的幀，并不是說(shuō)接收到了這些幀并不是說(shuō)接收到了這些幀49Chapter 3 數(shù)據(jù)鏈路層n3.1數(shù)據(jù)鏈路層的功能n3.2差錯(cuò)檢測(cè)與糾正n3.3基本數(shù)據(jù)鏈路協(xié)議n3.4滑動(dòng)窗口（Slide Windows）協(xié)議n3.5面向位的協(xié)議HDLCn3.6 Internet中的數(shù)

47、據(jù)鏈路層503.5面向位的協(xié)議HDLCn高級(jí)數(shù)據(jù)鏈路控制（高級(jí)數(shù)據(jù)鏈路控制（ HDLC：High-Level Data Link Control）是由國(guó)際標(biāo)準(zhǔn)化組織制）是由國(guó)際標(biāo)準(zhǔn)化組織制定的定的面向面向位位（比特）（比特）的的有序鏈路層協(xié)議有序鏈路層協(xié)議n采用主從結(jié)構(gòu)，鏈路上一個(gè)主站控制多個(gè)從站，采用主從結(jié)構(gòu)，鏈路上一個(gè)主站控制多個(gè)從站，主站向從站發(fā)命令，從站向主站返回響應(yīng)主站向從站發(fā)命令，從站向主站返回響應(yīng)nHDLC中只有一個(gè)地址域，即從站的地址，在中只有一個(gè)地址域，即從站的地址，在命令幀中，它是目的地址，在響應(yīng)幀中，它是命令幀中，它是目的地址，在響應(yīng)幀中，它是源地址源地址提供基于滑動(dòng)窗口

48、、確認(rèn)和超時(shí)機(jī)制的可靠數(shù)據(jù)傳輸提供基于滑動(dòng)窗口、確認(rèn)和超時(shí)機(jī)制的可靠數(shù)據(jù)傳輸511.幀標(biāo)志序列：幀標(biāo)志序列：01111110，作為起始和結(jié)束標(biāo)志，在，作為起始和結(jié)束標(biāo)志，在數(shù)據(jù)位有數(shù)據(jù)位有5個(gè)連續(xù)的個(gè)連續(xù)的1出現(xiàn)時(shí)，就插入出現(xiàn)時(shí)，就插入1個(gè)個(gè)0（位填充）（位填充）2.地址域：在命令幀中表示目的地址，在響應(yīng)幀中表示地址域：在命令幀中表示目的地址，在響應(yīng)幀中表示源地址，全源地址，全1為廣播地址，全為廣播地址，全0為測(cè)試地址為測(cè)試地址3.控制域：序列號(hào)、確認(rèn)及其它用途控制域：序列號(hào)、確認(rèn)及其它用途1.校驗(yàn)和域：循環(huán)冗余校驗(yàn)（校驗(yàn)和域：循環(huán)冗余校驗(yàn)（G(x) = x16 + x12 + x5 + 1）

49、主站從站從站命令響應(yīng)52I幀幀S幀幀U幀幀Seq：發(fā)送方發(fā)送序列編號(hào)，這里是：發(fā)送方發(fā)送序列編號(hào)，這里是3比特比特Next：表示發(fā)送方準(zhǔn)備接收的序列號(hào)（捎帶確認(rèn)，尚未接收到的第一幀序列號(hào)）：表示發(fā)送方準(zhǔn)備接收的序列號(hào)（捎帶確認(rèn)，尚未接收到的第一幀序列號(hào)）Type：表示管理幀類型：表示管理幀類型P/F：在命令幀中作為詢問(wèn)，在響應(yīng)幀中表示數(shù)據(jù)發(fā)送結(jié)束：在命令幀中作為詢問(wèn)，在響應(yīng)幀中表示數(shù)據(jù)發(fā)送結(jié)束三種類型的幀三種類型的幀 信息幀（信息幀（I：Information）：用來(lái)實(shí)現(xiàn)信息的傳傳輸，含有信息字段）：用來(lái)實(shí)現(xiàn)信息的傳傳輸，含有信息字段 管理幀（管理幀（S：Supervision）：幀中不包含信

50、息字段，具有監(jiān)控鏈路的作）：幀中不包含信息字段，具有監(jiān)控鏈路的作用，并能對(duì)收到的幀進(jìn)行確認(rèn)用，并能對(duì)收到的幀進(jìn)行確認(rèn) 無(wú)序號(hào)幀（無(wú)序號(hào)幀（U：Unnumbered）：對(duì)數(shù)據(jù)鏈路進(jìn)行附加控制）：對(duì)數(shù)據(jù)鏈路進(jìn)行附加控制Control53Chapter 3 數(shù)據(jù)鏈路層n3.1數(shù)據(jù)鏈路層的功能n3.2差錯(cuò)檢測(cè)與糾正n3.3基本數(shù)據(jù)鏈路協(xié)議n3.4滑動(dòng)窗口（Slide Windows）協(xié)議n3.5面向位的協(xié)議HDLCn3.6 Internet中的數(shù)據(jù)鏈路層543.6 Internet中的數(shù)據(jù)鏈路層NAS接入接入服務(wù)器服務(wù)器No need for explicit addressing!主機(jī)主機(jī)553.6

51、.1 SLIP（Serial Line IP)1.IP分組用字符分組用字符END（0XC0）定界。）定界。2.如果在如果在IP分組中出現(xiàn)分組中出現(xiàn)END字符（字符（0XC0），就用），就用2字節(jié)字字節(jié)字符符0Xdb，0Xdc代替。代替。3.如果如果IP分組中有字節(jié)為分組中有字節(jié)為0Xdb，就用，就用0Xdb，0Xdd代替。代替。C0dbIP分組dbdbC0C0dcdd問(wèn)題：?jiǎn)栴}：1.沒(méi)有類型域，只能支持沒(méi)有類型域，只能支持IP分組分組 2.沒(méi)有校驗(yàn)沒(méi)有校驗(yàn)SLIP幀563.6.2 PPP(Point to Point Protocol)nPPP由以下由以下幾幾部分組成：部分組成：n串行鏈路上的數(shù)據(jù)的封裝方法串行鏈路上的數(shù)據(jù)的封裝方法n鏈路控制協(xié)議（鏈路控制協(xié)議（LCP：Link Control Protocol）：用來(lái)建立、配置、測(cè)試數(shù)據(jù)）：用來(lái)建立、配置、測(cè)試數(shù)據(jù)鏈路連接鏈路連接n認(rèn)證協(xié)議認(rèn)證協(xié)議(可選)：對(duì)撥號(hào)接入的用戶進(jìn)行認(rèn)：對(duì)撥號(hào)接入的用戶進(jìn)行認(rèn)證，以便于證，以便于計(jì)費(fèi)，例如計(jì)費(fèi)，例如PAP、CHAPn網(wǎng)絡(luò)網(wǎng)絡(luò)控制協(xié)議（控制協(xié)議（NCP）：）：對(duì)不同的網(wǎng)絡(luò)層協(xié)對(duì)不同的網(wǎng)絡(luò)層協(xié)議定義了對(duì)應(yīng)的網(wǎng)絡(luò)議定義了對(duì)應(yīng)的網(wǎng)絡(luò)控制協(xié)議，例如控制協(xié)議，例如IPCPPPP基本基本協(xié)議主要協(xié)議主要內(nèi)容內(nèi)