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

1、數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層使用的信道主要有以下兩種類(lèi)型： 點(diǎn)對(duì)點(diǎn)信道。這種信道使用一對(duì)一的點(diǎn)對(duì)點(diǎn)通信方式。 廣播信道。這種信道使用一對(duì)多的廣播通信方式，因此過(guò)程比較復(fù)雜。廣播信道上連接的主機(jī)很多，因此必須使用專(zhuān)用的共享信道協(xié)議來(lái)協(xié)調(diào)這些主機(jī)的數(shù)據(jù)發(fā) 第1頁(yè)/共132頁(yè)4.1 數(shù)據(jù)鏈路層的基本概念4.1.1 數(shù)據(jù)鏈路層的簡(jiǎn)單模型局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話(huà)網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從層次上來(lái)看數(shù)據(jù)的流動(dòng)第2頁(yè)/共1

2、32頁(yè)數(shù)據(jù)鏈路層的簡(jiǎn)單模型( ( 續(xù)）局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話(huà)網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動(dòng)第3頁(yè)/共132頁(yè)IP 數(shù)據(jù)報(bào)1010 0110幀取出數(shù)據(jù)鏈路層網(wǎng)絡(luò)層鏈路結(jié)點(diǎn) A結(jié)點(diǎn) B物理層數(shù)據(jù)鏈路層結(jié)點(diǎn) A結(jié)點(diǎn) B幀(a)(b)發(fā)送幀接收鏈路IP 數(shù)據(jù)報(bào)1010 0110幀裝入數(shù)據(jù)鏈路層傳送的是幀第4頁(yè)/共132頁(yè)4.1.2 鏈路和數(shù)據(jù)鏈路 鏈路(link)是一條無(wú)源的點(diǎn)到點(diǎn)的物理

3、線(xiàn)路段，中間沒(méi)有任何其他的交換結(jié)點(diǎn)。 一條鏈路只是一條通路的一個(gè)組成部分。 數(shù)據(jù)鏈路(data link) 除了物理線(xiàn)路外，還必須有通信協(xié)議來(lái)控制這些數(shù)據(jù)的傳輸。若把實(shí)現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路。 現(xiàn)在最常用的方法是使用適配器（即網(wǎng)卡）來(lái)實(shí)現(xiàn)這些協(xié)議的硬件和軟件。 一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層的功能。 第5頁(yè)/共132頁(yè)數(shù)據(jù)鏈路層像個(gè)數(shù)字管道 常常在兩個(gè)對(duì)等的數(shù)據(jù)鏈路層之間畫(huà)出一個(gè)數(shù)字管道，而在這條數(shù)字管道上傳輸?shù)臄?shù)據(jù)單位是幀。 早期的數(shù)據(jù)通信協(xié)議曾叫作通信規(guī)程(procedure)。因此在數(shù)據(jù)鏈路層，規(guī)程和協(xié)議是同義語(yǔ)。 結(jié)點(diǎn)結(jié)點(diǎn)幀幀第6頁(yè)/共132頁(yè)

4、74.1數(shù)據(jù)鏈路層的基本概念數(shù)據(jù)鏈路層的基本概念1 物理線(xiàn)路與數(shù)據(jù)鏈路物理線(xiàn)路與數(shù)據(jù)鏈路 線(xiàn)路線(xiàn)路 鏈路鏈路 邏輯線(xiàn)路邏輯線(xiàn)路 數(shù)據(jù)鏈路數(shù)據(jù)鏈路第7頁(yè)/共132頁(yè)4.2 三個(gè)基本問(wèn)題 (1) 幀定界(2) 透明傳輸(3) 差錯(cuò)控制 第8頁(yè)/共132頁(yè)4.2.1 幀定界 幀定界(framing)就是確定幀的界限。 幀結(jié)束幀首部IP 數(shù)據(jù)報(bào)幀的數(shù)據(jù)部分幀尾部 MTU數(shù)據(jù)鏈路層的幀長(zhǎng)從這里開(kāi)始發(fā)送幀開(kāi)始第9頁(yè)/共132頁(yè)用控制字符進(jìn)行幀定界的方法舉例 SOH裝在幀中的數(shù)據(jù)部分幀幀開(kāi)始符幀結(jié)束符發(fā)送在前EOT第10頁(yè)/共132頁(yè)4.2.2 透明傳輸SOHEOT出現(xiàn)了“EOT”被接收端當(dāng)作無(wú)效幀而丟棄被

5、接收端誤認(rèn)為是一個(gè)幀數(shù)據(jù)部分EOT完整的幀發(fā)送在前第11頁(yè)/共132頁(yè)解決透明傳輸問(wèn)題 發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符“SOH”或“EOT”的前面插入一個(gè)轉(zhuǎn)義字符“ESC”(其十六進(jìn)制編碼是 1B)。 字節(jié)填充(byte stuffing)或字符填充(character stuffing)接收端的數(shù)據(jù)鏈路層在將數(shù)據(jù)送往網(wǎng)絡(luò)層之前刪除插入的轉(zhuǎn)義字符。 如果轉(zhuǎn)義字符也出現(xiàn)數(shù)據(jù)當(dāng)中，那么應(yīng)在轉(zhuǎn)義字符前面插入一個(gè)轉(zhuǎn)義字符。當(dāng)接收端收到連續(xù)的兩個(gè)轉(zhuǎn)義字符時(shí)，就刪除其中前面的一個(gè)。 第12頁(yè)/共132頁(yè)SOHSOHESCSOHEOTESCESCzESCyESCzESCx原始數(shù)據(jù)EOTEOT經(jīng)過(guò)字節(jié)

6、填充后發(fā)送的數(shù)據(jù)字節(jié)填充字節(jié)填充字節(jié)填充字節(jié)填充發(fā)送在前幀開(kāi)始符幀結(jié)束符用字節(jié)填充法解決透明傳輸?shù)膯?wèn)題 第13頁(yè)/共132頁(yè)144.1 數(shù)據(jù)鏈路層的基本概念 數(shù)據(jù)鏈路層的主要功能 鏈路管理：數(shù)據(jù)鏈路的建立、維持和釋放。 幀同步 ：以幀為單位進(jìn)行傳送，接收方能從收到的比特流中準(zhǔn)確區(qū)分一幀的開(kāi)始和結(jié)束在什么地方。也稱(chēng)為幀定界。 流量控制：防止接收端被發(fā)送端淹沒(méi)(overwhelm)，速度匹配 差錯(cuò)控制：在計(jì)算機(jī)通信中，一般都要求極低的比特差錯(cuò)率。為此，廣泛的采樣了編碼技術(shù)。分為前向糾錯(cuò)和差錯(cuò)檢測(cè)兩種。第14頁(yè)/共132頁(yè)154.1 數(shù)據(jù)鏈路層的基本概念 將數(shù)據(jù)和控制信息區(qū)分開(kāi) 透明傳輸：不管什么比

7、特流，都能傳輸 尋址：在多點(diǎn)連接的情況下，保證每一幀都能正確送到目的地。收方也應(yīng)知道發(fā)方是哪個(gè)站。n數(shù)據(jù)鏈路層協(xié)議數(shù)據(jù)鏈路層協(xié)議 為實(shí)現(xiàn)數(shù)據(jù)鏈路控制功能為實(shí)現(xiàn)數(shù)據(jù)鏈路控制功能而制定的規(guī)程或協(xié)議。而制定的規(guī)程或協(xié)議。第15頁(yè)/共132頁(yè)164.3 差錯(cuò)控制方法差錯(cuò)控制方法4.3.1 為什么要設(shè)計(jì)數(shù)據(jù)鏈路層為什么要設(shè)計(jì)數(shù)據(jù)鏈路層 在原始物理傳輸線(xiàn)路上傳輸數(shù)據(jù)信號(hào)是有差錯(cuò)的；在原始物理傳輸線(xiàn)路上傳輸數(shù)據(jù)信號(hào)是有差錯(cuò)的； 設(shè)計(jì)數(shù)據(jù)鏈路層的主要目的：設(shè)計(jì)數(shù)據(jù)鏈路層的主要目的： 將有差錯(cuò)的物理線(xiàn)路改進(jìn)成無(wú)差錯(cuò)的數(shù)據(jù)鏈路；將有差錯(cuò)的物理線(xiàn)路改進(jìn)成無(wú)差錯(cuò)的數(shù)據(jù)鏈路； 方法方法 差錯(cuò)檢測(cè)差錯(cuò)檢測(cè) 差錯(cuò)控制差錯(cuò)控

8、制 流量控制流量控制 作用：改善數(shù)據(jù)傳輸質(zhì)量，向網(wǎng)絡(luò)層提供高質(zhì)量的服作用：改善數(shù)據(jù)傳輸質(zhì)量，向網(wǎng)絡(luò)層提供高質(zhì)量的服務(wù)。務(wù)。第16頁(yè)/共132頁(yè)17傳輸差錯(cuò)傳輸差錯(cuò)產(chǎn)生過(guò)程產(chǎn)生過(guò)程第17頁(yè)/共132頁(yè)184.3.2 差錯(cuò)控制編碼原理和方法：q原理：q編碼：在向信道發(fā)送數(shù)據(jù)前，先按照某種關(guān)系將信息位加上一定的冗余位（r位），構(gòu)成一個(gè)碼字再發(fā)送。q校驗(yàn)：接收端收到碼字后查看信息位和冗余位，并檢查它們之間的關(guān)系，以發(fā)現(xiàn)傳輸過(guò)程是否有差錯(cuò)發(fā)生。q檢錯(cuò)碼：能自動(dòng)發(fā)現(xiàn)差錯(cuò)的編碼。q糾錯(cuò)碼：不僅能發(fā)現(xiàn)差錯(cuò)，且能自動(dòng)糾錯(cuò)。q編碼效率R：碼字中信息位(k位）所占的比例。 R=k/n=k/(k+r)是衡量編碼性能好

9、壞的一個(gè)重要參數(shù)編碼效率越高，則信道中用來(lái)傳送信息碼元的有效利用率越高。第18頁(yè)/共132頁(yè)19差錯(cuò)控制方法1.1.自動(dòng)請(qǐng)求重發(fā)糾錯(cuò)自動(dòng)請(qǐng)求重發(fā)糾錯(cuò)ARQ(Automatic-Repeat-reQuestARQ(Automatic-Repeat-reQuest) ) 方法：方法： 在發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)單元進(jìn)行差錯(cuò)編碼，接收端收到碼組后，按編碼規(guī)則校驗(yàn)有無(wú)錯(cuò)碼，并把校驗(yàn)結(jié)果通過(guò)反向信道反饋到發(fā)送端。如無(wú)錯(cuò)碼，就反饋繼續(xù)發(fā)送信號(hào)。如有錯(cuò)碼，就反饋重發(fā)信號(hào)，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端正確收到為止。 只需用檢錯(cuò)碼只需用檢錯(cuò)碼 必須有雙向信道將差錯(cuò)通知對(duì)方必須有雙向信道將差錯(cuò)通

10、知對(duì)方 發(fā)送方要有數(shù)據(jù)緩沖區(qū)，存放已發(fā)出的數(shù)據(jù)，以便出發(fā)送方要有數(shù)據(jù)緩沖區(qū)，存放已發(fā)出的數(shù)據(jù)，以便出現(xiàn)差錯(cuò)可重新發(fā)送現(xiàn)差錯(cuò)可重新發(fā)送優(yōu)點(diǎn)：檢錯(cuò)碼構(gòu)造簡(jiǎn)單，插入的監(jiān)督碼位不多，設(shè)備不太復(fù)雜。缺點(diǎn)：實(shí)時(shí)性差，且必須有反向信道，通信效率低。第19頁(yè)/共132頁(yè)20差錯(cuò)控制機(jī)制差錯(cuò)控制機(jī)制 反饋重發(fā)機(jī)制反饋重發(fā)機(jī)制 第20頁(yè)/共132頁(yè)212.前向糾錯(cuò)方式FEC前向糾錯(cuò)方式FEC(Forward-Error Correction)方法：前向糾錯(cuò)系統(tǒng)中，發(fā)送端的信道編碼器將輸入前向糾錯(cuò)系統(tǒng)中，發(fā)送端的信道編碼器將輸入數(shù)據(jù)序列按某種規(guī)則變換成能夠糾正錯(cuò)誤的碼，接收數(shù)據(jù)序列按某種規(guī)則變換成能夠糾正錯(cuò)誤的碼，

11、接收端的譯碼器根據(jù)編碼規(guī)律不僅可以檢測(cè)出錯(cuò)碼，而且端的譯碼器根據(jù)編碼規(guī)律不僅可以檢測(cè)出錯(cuò)碼，而且能夠確定錯(cuò)碼的位置并自動(dòng)糾正。能夠確定錯(cuò)碼的位置并自動(dòng)糾正。所以，所以，F(xiàn)ECFEC不求助不求助于反向操作，故稱(chēng)為于反向操作，故稱(chēng)為“前向糾錯(cuò)前向糾錯(cuò)”。優(yōu)點(diǎn)：不需要反饋信道，也不存在由于反復(fù)重發(fā)而延誤時(shí)間，實(shí)時(shí)性好。 缺點(diǎn)：附加的監(jiān)督碼較多，傳輸效率低，糾錯(cuò)設(shè)備比檢錯(cuò)設(shè)備復(fù)雜。第21頁(yè)/共132頁(yè)22 混合方式HEC 發(fā)送端發(fā)送同時(shí)具有檢錯(cuò)和糾錯(cuò)能力的碼，接收端發(fā)送端發(fā)送同時(shí)具有檢錯(cuò)和糾錯(cuò)能力的碼，接收端收到碼后，檢查錯(cuò)誤情況，如果錯(cuò)誤少于糾錯(cuò)能力，收到碼后，檢查錯(cuò)誤情況，如果錯(cuò)誤少于糾錯(cuò)能力，則

12、自行糾正；如果錯(cuò)誤很多，超出糾錯(cuò)能力，但未超則自行糾正；如果錯(cuò)誤很多，超出糾錯(cuò)能力，但未超出檢錯(cuò)能力，即能判決有無(wú)錯(cuò)碼而不能判決錯(cuò)碼的位出檢錯(cuò)能力，即能判決有無(wú)錯(cuò)碼而不能判決錯(cuò)碼的位置，此時(shí)收端自動(dòng)通過(guò)反向信道發(fā)出信號(hào)要求發(fā)端重置，此時(shí)收端自動(dòng)通過(guò)反向信道發(fā)出信號(hào)要求發(fā)端重發(fā)發(fā)。q 在數(shù)據(jù)通信和計(jì)算機(jī)網(wǎng)絡(luò)中，幾乎都采用ARQARQ差錯(cuò)控制技術(shù)。在采用無(wú)線(xiàn)電信道的通信系統(tǒng)中，由于信道誤碼率較高，大多采用HECHEC方式的差錯(cuò)控制技術(shù)。3.混合方式HEC第22頁(yè)/共132頁(yè)23q 反饋校驗(yàn) 反饋校驗(yàn)方式又稱(chēng)回程校驗(yàn)。反饋校驗(yàn)方式又稱(chēng)回程校驗(yàn)。 接收端把收到的數(shù)據(jù)序列原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)送端，發(fā)端將原

13、發(fā)送的數(shù)據(jù)接收端把收到的數(shù)據(jù)序列原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)送端，發(fā)端將原發(fā)送的數(shù)據(jù)序列與返送回的數(shù)據(jù)序列比較。如果發(fā)現(xiàn)錯(cuò)誤，則發(fā)送端進(jìn)行重發(fā)，直到發(fā)端序列與返送回的數(shù)據(jù)序列比較。如果發(fā)現(xiàn)錯(cuò)誤，則發(fā)送端進(jìn)行重發(fā)，直到發(fā)端沒(méi)有發(fā)現(xiàn)錯(cuò)誤為止。沒(méi)有發(fā)現(xiàn)錯(cuò)誤為止。 優(yōu)點(diǎn)：不需要糾錯(cuò)、檢錯(cuò)的編解碼器，設(shè)備簡(jiǎn)單。 缺點(diǎn)：需要有雙向信道，實(shí)時(shí)性差，且每一信碼都相當(dāng)于至少傳送了兩次，所以傳輸效率低。4.反饋檢驗(yàn)第23頁(yè)/共132頁(yè)24圖 差錯(cuò)控制的基本類(lèi)型第24頁(yè)/共132頁(yè)254.3.3 檢錯(cuò)碼與糾錯(cuò)碼檢錯(cuò)碼與糾錯(cuò)碼 糾錯(cuò)碼糾錯(cuò)碼： 每個(gè)傳輸?shù)姆纸M帶上足夠的冗余信息；每個(gè)傳輸?shù)姆纸M帶上足夠的冗余信息； 接收端能發(fā)現(xiàn)并

14、自動(dòng)糾正傳輸差錯(cuò)。接收端能發(fā)現(xiàn)并自動(dòng)糾正傳輸差錯(cuò)。 檢錯(cuò)碼檢錯(cuò)碼: : 分組僅包含足以使接收端發(fā)現(xiàn)差錯(cuò)的冗余信息；分組僅包含足以使接收端發(fā)現(xiàn)差錯(cuò)的冗余信息； 接收端能發(fā)現(xiàn)出錯(cuò)，但不能確定哪一比特是錯(cuò)的，并且自己不能糾正傳輸差錯(cuò)。接收端能發(fā)現(xiàn)出錯(cuò)，但不能確定哪一比特是錯(cuò)的，并且自己不能糾正傳輸差錯(cuò)。 第25頁(yè)/共132頁(yè)26常用的檢錯(cuò)碼常用的檢錯(cuò)碼 奇偶校驗(yàn)碼奇偶校驗(yàn)碼 垂直奇（偶）校驗(yàn)垂直奇（偶）校驗(yàn) 水平奇（偶）校驗(yàn)水平奇（偶）校驗(yàn)水平垂直奇（偶）校驗(yàn)（方陣碼）水平垂直奇（偶）校驗(yàn)（方陣碼） 循環(huán)冗余編碼循環(huán)冗余編碼CRC 目前應(yīng)用最廣的檢錯(cuò)碼編碼方法之一目前應(yīng)用最廣的檢錯(cuò)碼編碼方法之一第2

15、6頁(yè)/共132頁(yè)27常用的簡(jiǎn)單差錯(cuò)控制編碼 奇偶校驗(yàn)碼 通過(guò)增加冗余位來(lái)使碼字中“1”的個(gè)數(shù)保持奇數(shù)或偶數(shù)的編碼方法 是一種檢錯(cuò)碼 可分為垂直奇偶校驗(yàn)、水平奇偶校驗(yàn)和水平垂直奇偶校驗(yàn)第27頁(yè)/共132頁(yè)28奇偶校驗(yàn)碼（一）：垂直奇偶校驗(yàn) 將所要傳輸?shù)臄?shù)據(jù)進(jìn)行分組，在每一組的信息位后增加一位冗余位，使每組檢驗(yàn)碼中“1”的個(gè)數(shù)成為奇數(shù)或偶數(shù)。 偶檢驗(yàn)： 奇檢驗(yàn)：信息位信息位 pqppqqIIIIIIIII.212222111211發(fā)送順序r1 r2 . rq冗余位第28頁(yè)/共132頁(yè)29 可邊發(fā)送邊產(chǎn)生冗余位，并插入發(fā)送，或在接收時(shí)邊接收邊進(jìn)行校驗(yàn)并去掉校驗(yàn)位。 編碼效率：R=p/(p+1) 這種

16、奇偶校驗(yàn)方法能檢測(cè)出每列中所有奇數(shù)位的錯(cuò)，但檢測(cè)不出偶數(shù)位的錯(cuò)。對(duì)于突發(fā)錯(cuò)誤來(lái)說(shuō)，奇數(shù)位錯(cuò)與偶數(shù)位錯(cuò)的概率接近于相等，因而對(duì)差錯(cuò)的漏檢率接近于12。第29頁(yè)/共132頁(yè)30奇偶校驗(yàn)碼（二）：水平奇偶校驗(yàn) 將所要傳輸?shù)臄?shù)據(jù)進(jìn)行分組，對(duì)各組中同一位的數(shù)據(jù)進(jìn)行校驗(yàn)，從而形成一組校驗(yàn)碼。 水平奇偶校驗(yàn)不但可以檢測(cè)各段同一位上的奇數(shù)錯(cuò)，而且可以檢測(cè)出突發(fā)長(zhǎng)度p的所有突發(fā)錯(cuò)誤。 要等發(fā)送的完整信息塊到齊后才能產(chǎn)生冗余 要使用記憶寄存器 它的編碼和檢測(cè)實(shí)現(xiàn)都要復(fù)雜一些。第30頁(yè)/共132頁(yè)31LRC-水平冗余檢驗(yàn)水平冗余檢驗(yàn)1110011111011101001110011010100110101010A

17、block of bits is organized in a table(rows and columns)第31頁(yè)/共132頁(yè)32奇偶校驗(yàn)碼（三）：水平垂直奇偶校驗(yàn)q 同時(shí)進(jìn)行水平奇偶校驗(yàn)和垂直校驗(yàn)q 檢錯(cuò)能力q 檢測(cè)出所有3位或3位以下的錯(cuò)誤q 奇數(shù)位錯(cuò)q 突發(fā)長(zhǎng)度 P+1的突發(fā)錯(cuò)誤q 很大部分偶數(shù)位錯(cuò)q 糾錯(cuò)能力q 僅在某一行和某一列中奇數(shù)位錯(cuò)時(shí)，就能確定錯(cuò)碼的位置在該行和該列的交叉處，從而糾正它第32頁(yè)/共132頁(yè)33 循環(huán)冗余碼一般說(shuō)來(lái)，糾錯(cuò)碼的編碼效率總不及檢錯(cuò)碼的編碼效率，因而在通信中用得較多的還是檢錯(cuò)碼和ARQ方式。奇偶校驗(yàn)碼作為一種檢錯(cuò)碼雖然簡(jiǎn)單，但是漏檢率太高。 在計(jì)算機(jī)

18、網(wǎng)絡(luò)和數(shù)據(jù)通信中，用得最廣泛的檢錯(cuò)碼是一種漏檢率低也便于實(shí)現(xiàn)的循環(huán)冗余碼CRC(Cyclic Redundancy Code)。循環(huán)冗余檢驗(yàn)的原理 第33頁(yè)/共132頁(yè)34常用的簡(jiǎn)單差錯(cuò)控制編碼 循環(huán)冗余碼 CRCCRC碼又稱(chēng)為多項(xiàng)式碼。碼又稱(chēng)為多項(xiàng)式碼。 任何一個(gè)由二進(jìn)制數(shù)位串組成的代碼都可由一個(gè)只含有任何一個(gè)由二進(jìn)制數(shù)位串組成的代碼都可由一個(gè)只含有0 0和和1 1兩個(gè)系數(shù)的多項(xiàng)式建立一一對(duì)應(yīng)的關(guān)系。兩個(gè)系數(shù)的多項(xiàng)式建立一一對(duì)應(yīng)的關(guān)系。 110001110001，表示成多項(xiàng)式，表示成多項(xiàng)式 x x5 5 + x + x4 4 + 1 + 1第34頁(yè)/共132頁(yè)35循環(huán)冗余碼 (CRC) 循環(huán)

19、冗余碼（CRC碼，多項(xiàng)式編碼）110001，表示成多項(xiàng)式 x5 + x4 + 1 生成多項(xiàng)式P(x)發(fā)方、收方事前商定； n次(n+1位)生成多項(xiàng)式的高位和低位必須為1生成多項(xiàng)式必須比傳輸信息對(duì)應(yīng)的多項(xiàng)式短模2運(yùn)算：加法不進(jìn)位，減法不去位，除法中的減法仍然采用模2運(yùn)算第35頁(yè)/共132頁(yè)36循環(huán)冗余檢驗(yàn)的原理 在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗(yàn) CRC 的檢錯(cuò)技術(shù)。 假設(shè)待傳送的數(shù)據(jù) M = 1010001101（共k bit）。我們?cè)贛的后面再添加供差錯(cuò)檢測(cè)用的 n bit 冗余碼一起發(fā)送。 第36頁(yè)/共132頁(yè)37冗余碼的計(jì)算 用二進(jìn)制的模 2 運(yùn)算進(jìn)行 2n 乘 M 的運(yùn)算，

20、這相當(dāng)于在 M 后面添加 n 個(gè) 0。 得到的 (k + n) bit 的數(shù)除以事先選定好的長(zhǎng)度為 (n + 1) bit 的數(shù) P，得出商是 Q 而余數(shù)是 R，余數(shù) R 比除數(shù) P 至少要少1 個(gè)比特。 第37頁(yè)/共132頁(yè)38冗余碼的計(jì)算舉例 設(shè) n = 5, P = 110101，模 2 運(yùn)算的結(jié)果是：商 Q = 1101010110， 余數(shù)R = 01110。 將余數(shù) R 作為冗余碼添加在數(shù)據(jù) M 的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或 2nM + R。 第38頁(yè)/共132頁(yè)39 1101010110 Q 商 除數(shù) P 110101 1010001101000

21、00 2nM 被除數(shù) 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余數(shù)循環(huán)冗余檢驗(yàn)的原理說(shuō)明 第39頁(yè)/共132頁(yè)40 舉例舉例：1 1 0 0 1 1發(fā)送數(shù)據(jù)比特序列CRC校驗(yàn)碼比特序列1 0 0 1帶CRC校驗(yàn)碼的發(fā)送數(shù)據(jù)比特序列1 1 0 0 1 1 1 0 0 11 1 0 0 11 1 0 0 11 1 0 0 11 1 0 0 101 0 0 0 0 11 1 0 0 1 1 0 0 0 01 1 0 0 1G(x)1 1 0 0 11 0 0 0 01 1

22、 0 0 11 0 0 1R(x)1 0 0 0 0 1Q(x)f(x).xk發(fā)送方接收方第40頁(yè)/共132頁(yè)41 CRC碼基本思想校驗(yàn)和（checksum）加在幀尾，使帶校驗(yàn)和的幀的多項(xiàng)式能被P(x)除盡；收方接收時(shí)，用P(x)去除它，若有余數(shù)，則檢測(cè)傳輸出錯(cuò)。 是否得出的余數(shù)為0，就一定沒(méi)有差錯(cuò)？第41頁(yè)/共132頁(yè)幀檢驗(yàn)序列 FCS 在數(shù)據(jù)后面添加上的冗余碼稱(chēng)為幀檢驗(yàn)序列 FCS (Frame Check Sequence)。 循環(huán)冗余檢驗(yàn) CRC 和幀檢驗(yàn)序列 FCS并不等同。 CRC 是一種常用的檢錯(cuò)方法，而 FCS 是添加在數(shù)據(jù)后面的冗余碼。 FCS 可以用 CRC 這種方法得出，

23、但 CRC 并非用來(lái)獲得 FCS 的唯一方法。 第42頁(yè)/共132頁(yè)接收端對(duì)收到的每一幀進(jìn)行 CRC 檢驗(yàn) (1) 若得出的余數(shù) R = 0，則判定這個(gè)幀沒(méi)有差錯(cuò)，就接受(accept)。 (2) 若余數(shù) R 0，則判定這個(gè)幀有差錯(cuò)，就丟棄。 但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。 只要經(jīng)過(guò)嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù) P，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很小。 第43頁(yè)/共132頁(yè)應(yīng)當(dāng)注意 僅用循環(huán)冗余檢驗(yàn) CRC 差錯(cuò)檢測(cè)技術(shù)只能做到無(wú)差錯(cuò)接受(accept)。 “無(wú)差錯(cuò)接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們都能以非常接近于 1 的概率認(rèn)為這些幀

24、在傳輸過(guò)程中沒(méi)有產(chǎn)生差錯(cuò)”。 也就是說(shuō)：“凡是接收端數(shù)據(jù)鏈路層接受的幀都沒(méi)有傳輸差錯(cuò)”（有差錯(cuò)的幀就丟棄而不接受）。 要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認(rèn)和重傳機(jī)制。 第44頁(yè)/共132頁(yè)45標(biāo)準(zhǔn)標(biāo)準(zhǔn)CRC生成多項(xiàng)式生成多項(xiàng)式G（x） CRC-12 G（x）= x12+x11+x3+x2+x+1 CRC-16 G（x）= x16+x15+x2+1 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 嚴(yán)格挑選，使用位數(shù)較多的除數(shù)，出現(xiàn)檢

25、測(cè)不到的差錯(cuò)的概率幾乎為嚴(yán)格挑選，使用位數(shù)較多的除數(shù)，出現(xiàn)檢測(cè)不到的差錯(cuò)的概率幾乎為0第45頁(yè)/共132頁(yè)46 Stop-and-Wait Protocol(SWP) GO BACK N(GBN) Selective Repeat Protocol(SRP)4.4 數(shù)據(jù)鏈路層協(xié)議第46頁(yè)/共132頁(yè)474.4.1 Stop-and-Wait Protocol(SWP) 完全理想化的數(shù)據(jù)傳輸 先研究一下數(shù)據(jù)鏈路層的模型。第47頁(yè)/共132頁(yè)4.4.1 Stop-and-Wait Protocol(SWP)數(shù)據(jù)鏈路層的簡(jiǎn)單模型局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話(huà)

26、網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從層次上來(lái)看數(shù)據(jù)的流動(dòng) 完全理想化的數(shù)據(jù)傳輸 先研究一下數(shù)據(jù)鏈路層的模型。第48頁(yè)/共132頁(yè)49數(shù)據(jù)鏈路層的簡(jiǎn)單模型( ( 續(xù)）局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話(huà)網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動(dòng)第49頁(yè)/共132頁(yè)501.

27、完全理想化的數(shù)據(jù)傳輸數(shù)據(jù)鏈路層主機(jī) A緩存主機(jī) B數(shù)據(jù)鏈路AP2AP1緩存發(fā)送方接收方幀高層幀4.4.1 Stop-and-Wait Protocol(SWP)第50頁(yè)/共132頁(yè)51完全理想化的數(shù)據(jù)傳輸所基于的兩個(gè)假定 假定 1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。 假定 2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來(lái)得及收下，并及時(shí)上交主機(jī)。 這個(gè)假定就相當(dāng)于認(rèn)為：接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不會(huì)低于發(fā)送端發(fā)送數(shù)據(jù)的速率。 第51頁(yè)/共132頁(yè)522 .具有最簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議 現(xiàn)在去掉上述的第二個(gè)假定。但是，仍然保留第一個(gè)假定，即主機(jī) A 向主機(jī)

28、B傳輸數(shù)據(jù)的信道仍然是無(wú)差錯(cuò)的理想信道。然而現(xiàn)在不能保證接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不低于發(fā)送端發(fā)送數(shù)據(jù)的速率。 由收方控制發(fā)方的數(shù)據(jù)流，乃是計(jì)算機(jī)網(wǎng)絡(luò)中流量控制的一個(gè)基本方法。 第52頁(yè)/共132頁(yè)53具有最簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議算法在發(fā)送結(jié)點(diǎn)： (1) 從主機(jī)取一個(gè)數(shù)據(jù)幀。 (2) 將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。 (3) 將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。 (4) 等待。 (5) 若收到由接收結(jié)點(diǎn)發(fā)過(guò)來(lái)的信息(此信息 的格式與內(nèi)容可由雙方事先商定好)，則 從主機(jī)取一個(gè)新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)。第53頁(yè)/共132頁(yè)54具有最簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議算法（續(xù)）在接收結(jié)點(diǎn)： (1)

29、 等待。 (2) 若收到由發(fā)送結(jié)點(diǎn)發(fā)過(guò)來(lái)的數(shù)據(jù)幀， 則將其放入數(shù)據(jù)鏈路層的接收緩存。 (3) 將接收緩存中的數(shù)據(jù)幀上交主機(jī)。 (4) 向發(fā)送結(jié)點(diǎn)發(fā)一信息，表示數(shù)據(jù)幀已 經(jīng)上交給主機(jī)。 (5) 轉(zhuǎn)到(1)。第54頁(yè)/共132頁(yè)55兩種情況的對(duì)比（傳輸均無(wú)差錯(cuò)）ABDATADATADATADATA送主機(jī) B送主機(jī) B送主機(jī) B送主機(jī) BABDATA送主機(jī) BDATA送主機(jī) B時(shí)間不需要流量控制需要流量控制第55頁(yè)/共132頁(yè)563 實(shí)用的停止等待協(xié)議時(shí)間ABDATA0送主機(jī)ACKDATA1送主機(jī)ACK(a) 正常情況正常情況ABDATA0DATA0送主機(jī)ACK(c) 數(shù)據(jù)幀丟失數(shù)據(jù)幀丟失重傳tou

30、t丟失 ！ABDATA0送主機(jī)ACKDATA0丟棄ACK(d) 確認(rèn)幀丟失確認(rèn)幀丟失重傳tout丟失 ！ABDATA0NAKDATA0送主機(jī)ACK(b) 數(shù)據(jù)幀出錯(cuò)數(shù)據(jù)幀出錯(cuò)重傳出錯(cuò)四種情況第56頁(yè)/共132頁(yè)57超時(shí)計(jì)時(shí)器的作用 結(jié)點(diǎn)A發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)，就啟動(dòng)一個(gè)超時(shí)計(jì)時(shí)器(timeout timer)。 計(jì)時(shí)器又稱(chēng)為定時(shí)器。 若到了超時(shí)計(jì)時(shí)器所設(shè)置的重傳時(shí)間 tout而仍收不到結(jié)點(diǎn) B 的任何確認(rèn)幀，則結(jié)點(diǎn) A 就重傳前面所發(fā)送的這一數(shù)據(jù)幀。 一般可將重傳時(shí)間選為略大于“從發(fā)完數(shù)據(jù)幀到收到確認(rèn)幀所需的平均時(shí)間”。 第57頁(yè)/共132頁(yè)58解決重復(fù)幀的問(wèn)題 使每一個(gè)數(shù)據(jù)幀帶上不同的發(fā)送序號(hào)

31、。每發(fā)送一個(gè)新的數(shù)據(jù)幀就把它的發(fā)送序號(hào)加 1。 若結(jié)點(diǎn) B 收到發(fā)送序號(hào)相同的數(shù)據(jù)幀，就表明出現(xiàn)了重復(fù)幀。這時(shí)應(yīng)丟棄重復(fù)幀，因?yàn)橐呀?jīng)收到過(guò)同樣的數(shù)據(jù)幀并且也交給了主機(jī) B。 但此時(shí)結(jié)點(diǎn) B 還必須向 A 發(fā)送確認(rèn)幀 ACK，因?yàn)?B 已經(jīng)知道 A 還沒(méi)有收到上一次發(fā)過(guò)去的確認(rèn)幀 ACK。 第58頁(yè)/共132頁(yè)59幀的編號(hào)問(wèn)題 任何一個(gè)編號(hào)系統(tǒng)的序號(hào)所占用的比特?cái)?shù)一定是有限的。因此，經(jīng)過(guò)一段時(shí)間后，發(fā)送序號(hào)就會(huì)重復(fù)。 序號(hào)占用的比特?cái)?shù)越少，數(shù)據(jù)傳輸?shù)念~外開(kāi)銷(xiāo)就越小。 對(duì)于停止等待協(xié)議，由于每發(fā)送一個(gè)數(shù)據(jù)幀就停止等待，因此用一個(gè)比特來(lái)編號(hào)就夠了。 一個(gè)比特可表示 0 和 1 兩種不同的序號(hào)。 第5

32、9頁(yè)/共132頁(yè)60幀的發(fā)送序號(hào) 數(shù)據(jù)幀中的發(fā)送序號(hào) N(S) 以 0 和 1 交替的方式出現(xiàn)在數(shù)據(jù)幀中。 每發(fā)一個(gè)新的數(shù)據(jù)幀，發(fā)送序號(hào)就和上次發(fā)送的不一樣。用這樣的方法就可以使收方能夠區(qū)分開(kāi)新的數(shù)據(jù)幀和重傳的數(shù)據(jù)幀了。 第60頁(yè)/共132頁(yè)61可靠傳輸 雖然物理層在傳輸比特時(shí)會(huì)出現(xiàn)差錯(cuò)，但由于數(shù)據(jù)鏈路層的停止等待協(xié)議采用了有效的檢錯(cuò)重傳機(jī)制，數(shù)據(jù)鏈路層對(duì)上面的網(wǎng)絡(luò)層就可以提供可靠傳輸?shù)姆?wù)。 第61頁(yè)/共132頁(yè)62幀檢驗(yàn)序列 FCS 在數(shù)據(jù)后面添加上的冗余碼稱(chēng)為幀檢驗(yàn)序列 FCS (Frame Check Sequence)。 循環(huán)冗余檢驗(yàn) CRC 和幀檢驗(yàn)序列 FCS并不等同。 CRC

33、是一種常用的檢錯(cuò)方法，而 FCS 是添加在數(shù)據(jù)后面的冗余碼。 FCS 可以用 CRC 這種方法得出，但 CRC 并非用來(lái)獲得 FCS 的惟一方法。 第62頁(yè)/共132頁(yè)63檢測(cè)出差錯(cuò) 只要得出的余數(shù) R 不為 0，就表示檢測(cè)到了差錯(cuò)。 但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。 一旦檢測(cè)出差錯(cuò)，就丟棄這個(gè)出現(xiàn)差錯(cuò)的幀。 只要經(jīng)過(guò)嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù) P，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很小。 第63頁(yè)/共132頁(yè)64應(yīng)當(dāng)注意 僅用循環(huán)冗余檢驗(yàn) CRC 差錯(cuò)檢測(cè)技術(shù)只能做到無(wú)差錯(cuò)接受(accept)。 “無(wú)差錯(cuò)接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們

34、都能以非常接近于 1 的概率認(rèn)為這些幀在傳輸過(guò)程中沒(méi)有產(chǎn)生差錯(cuò)”。 也就是說(shuō)：“凡是接受的幀都沒(méi)有傳輸差錯(cuò)”（有差錯(cuò)的幀就丟棄而不接受）。 要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認(rèn)和重傳機(jī)制。 第64頁(yè)/共132頁(yè)654 停止等待協(xié)議的算法 這里不使用否認(rèn)幀（實(shí)用的數(shù)據(jù)鏈路層協(xié)議大都是這樣的），而且確認(rèn)幀帶有序號(hào) n。 按照習(xí)慣的表示法，ACKn 表示“第 n 1 號(hào)幀已經(jīng)收到，現(xiàn)在期望接收第 n 號(hào)幀”。 ACK1 表示“0 號(hào)幀已收到，現(xiàn)在期望接收的下一幀是 1 號(hào)幀”； ACK0 表示“1 號(hào)幀已收到，現(xiàn)在期望接收的下一幀是 0 號(hào)幀”。 第65頁(yè)/共132頁(yè)66在發(fā)送

35、結(jié)點(diǎn) (1) 從主機(jī)取一個(gè)數(shù)據(jù)幀，送交發(fā)送緩存。(2) V(S)0。 (3) N(S)V(S)。(4) 將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。 (5) 設(shè)置超時(shí)計(jì)時(shí)器。(6) 等待。 等待以下(7)和(8)這兩個(gè)事件中最先出現(xiàn)的一個(gè)(7) 收到確認(rèn)幀 ACKn， 若 n = 1 V(s)，則： 從主機(jī)取一個(gè)新的數(shù)據(jù)幀，放入發(fā)送緩存； V(S)1 V(S)，轉(zhuǎn)到 (3)。 否則，丟棄這個(gè)確認(rèn)幀，轉(zhuǎn)到(6)。 (8) 若超時(shí)計(jì)時(shí)器時(shí)間到，則轉(zhuǎn)到(4)。第66頁(yè)/共132頁(yè)67在接收結(jié)點(diǎn) (1) V(R)0。(2) 等待。(3) 收到一個(gè)數(shù)據(jù)幀； 若 N(S) = V(R)，則執(zhí)行(4)； 否則丟棄此數(shù)據(jù)幀

36、，然后轉(zhuǎn)到(6)。(4) 將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交上層軟件 （也就是數(shù)據(jù)鏈路層模型中的主機(jī)）。(5) V(R)1 V(R)。(6) nV(R)； 發(fā)送確認(rèn)幀 ACKn，轉(zhuǎn)到(2)。 第67頁(yè)/共132頁(yè)68停止等待協(xié)議的要點(diǎn) 只有收到序號(hào)正確的確認(rèn)幀 ACKn 后，才更新發(fā)送狀態(tài)變量 V(S)一次，并發(fā)送新的數(shù)據(jù)幀。 接收端接收到數(shù)據(jù)幀時(shí)，就要將發(fā)送序號(hào) N(S) 與本地的接收狀態(tài)變量 V(R) 相比較。 若二者相等就表明是新的數(shù)據(jù)幀，就收下，并發(fā)送確認(rèn)。 否則為重復(fù)幀，就必須丟棄。但這時(shí)仍須向發(fā)送端發(fā)送確認(rèn)幀 ACKn，而接收狀態(tài)變量 V(R) 和確認(rèn)序號(hào) n 都不變。 第68頁(yè)/共1

37、32頁(yè)69停止等待協(xié)議的要點(diǎn)（續(xù)） 連續(xù)出現(xiàn)相同發(fā)送序號(hào)的數(shù)據(jù)幀，表明發(fā)送端進(jìn)行了超時(shí)重傳。連續(xù)出現(xiàn)相同序號(hào)的確認(rèn)幀，表明接收端收到了重復(fù)幀。 發(fā)送端在發(fā)送完數(shù)據(jù)幀時(shí)，必須在其發(fā)送緩存中暫時(shí)保留這個(gè)數(shù)據(jù)幀的副本。這樣才能在出差錯(cuò)時(shí)進(jìn)行重傳。只有確認(rèn)對(duì)方已經(jīng)收到這個(gè)數(shù)據(jù)幀時(shí)，才可以清除這個(gè)副本。 第69頁(yè)/共132頁(yè)70停止等待協(xié)議的要點(diǎn)（續(xù)） 實(shí)用的 CRC 檢驗(yàn)器都是用硬件完成的。 CRC 檢驗(yàn)器能夠自動(dòng)丟棄檢測(cè)到的出錯(cuò)幀。因此所謂的“丟棄出錯(cuò)幀”，對(duì)上層軟件或用戶(hù)來(lái)說(shuō)都是感覺(jué)不到的。 發(fā)送端對(duì)出錯(cuò)的數(shù)據(jù)幀進(jìn)行重傳是自動(dòng)進(jìn)行的，因而這種差錯(cuò)控制體制常簡(jiǎn)稱(chēng)為 ARQ (Automatic Re

38、peat reQuest)，直譯是自動(dòng)重傳請(qǐng)求，但意思是自動(dòng)請(qǐng)求重傳。 第70頁(yè)/共132頁(yè)71停止等待協(xié)議 ARQ 的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：比較簡(jiǎn)單 。 缺點(diǎn)：通信信道的利用率不高，也就是說(shuō)，信道還遠(yuǎn)遠(yuǎn)沒(méi)有被數(shù)據(jù)比特填滿(mǎn)。 為了克服這一缺點(diǎn)，就產(chǎn)生了另外兩種協(xié)議，即連續(xù) ARQ 和選擇重傳 ARQ。這將在后面進(jìn)一步討論。 第71頁(yè)/共132頁(yè)724.4.2 GO BACK N(GBN)1 連續(xù) ARQ 協(xié)議的工作原理 在發(fā)送完一個(gè)數(shù)據(jù)幀后，不是停下來(lái)等待確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個(gè)數(shù)據(jù)幀。 如果這時(shí)收到了接收端發(fā)來(lái)的確認(rèn)幀，那么還可以接著發(fā)送數(shù)據(jù)幀。 由于減少了等待時(shí)間，整個(gè)通信的吞吐量就提高了

39、。 第72頁(yè)/共132頁(yè)73連續(xù) ARQ 協(xié)議的工作原理 DATA0DATA1DATA2DATA3DATA4DATA5重傳 DATA2重傳 DATA3ACK1ACK2ACK1 確認(rèn) DATA0ACK2 確認(rèn) DATA1DATA2 出錯(cuò)，丟棄DATA3 不按序，丟棄，重傳 ACK2DATA4 不按序，丟棄，重傳 ACK2DATA5 不按序，丟棄，重傳 ACK2ACK3ACK3 確認(rèn) DATA2ACK4 確認(rèn) DATA3ACK4重傳 DATA5重傳 DATA4超時(shí)重傳時(shí)間ABtout送交主機(jī)送交主機(jī)?ACK2ACK2ACK2第73頁(yè)/共132頁(yè)74需要注意： (1) 接收端只按序接收數(shù)據(jù)幀。雖然在

40、有差錯(cuò)的 2號(hào)幀之后接著又收到了正確的 3 個(gè)數(shù)據(jù)幀，但接收端都必須將這些幀丟棄，因?yàn)樵谶@些幀前面有一個(gè) 2 號(hào)幀還沒(méi)有收到。雖然丟棄了這些不按序的無(wú)差錯(cuò)幀，但應(yīng)重復(fù)發(fā)送已發(fā)送過(guò)的最后一個(gè)確認(rèn)幀（防止確認(rèn)幀丟失）。(2) ACK1 表示確認(rèn) 0 號(hào)幀 DATA0，并期望下次收到 1 號(hào)幀；ACK2 表示確認(rèn) 1 號(hào)幀 DATA1，并期望下次收到 2 號(hào)幀。依此類(lèi)推。 第74頁(yè)/共132頁(yè)75需要注意： (3) 結(jié)點(diǎn) A 在每發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)都要設(shè)置該幀的超時(shí)計(jì)時(shí)器。如果在所設(shè)置的超時(shí)時(shí)間內(nèi)收到確認(rèn)幀，就立即將超時(shí)計(jì)時(shí)器清零。但若在所設(shè)置的超時(shí)時(shí)間到了而未收到確認(rèn)幀，就要重傳相應(yīng)的數(shù)據(jù)幀（仍需

41、重新設(shè)置超時(shí)計(jì)時(shí)器）。 在等不到 2 號(hào)幀的確認(rèn)而重傳 2 號(hào)數(shù)據(jù)幀時(shí)，雖然結(jié)點(diǎn) A 已經(jīng)發(fā)完了 5 號(hào)幀，但仍必須向回走，將 2號(hào)幀及其以后的各幀全部進(jìn)行重傳。連續(xù) ARQ 又稱(chēng)為Go-back-N ARQ，意思是當(dāng)出現(xiàn)差錯(cuò)必須重傳時(shí)，要向回走 N 個(gè)幀，然后再開(kāi)始重傳。 第75頁(yè)/共132頁(yè)762 滑動(dòng)窗口的概念 發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口 。 發(fā)送窗口用來(lái)對(duì)發(fā)送端進(jìn)行流量控制。 發(fā)送窗口的大小 WT 代表在還沒(méi)有收到對(duì)方確認(rèn)信息的情況下發(fā)送端最多可以發(fā)送多少個(gè)數(shù)據(jù)幀。 第76頁(yè)/共132頁(yè)7701234567012發(fā)送窗口WT不允許發(fā)送這些幀允許發(fā)送 5 個(gè)幀(a)0123

42、4567012不允許發(fā)送這些幀還允許發(fā)送 4 個(gè)幀WT已發(fā)送(b)01234567012不允許發(fā)送這些幀WT已發(fā)送(c)01234567012不允許發(fā)送這些幀還允許發(fā)送 3 個(gè)幀WT已發(fā)送 已發(fā)送并已收到確認(rèn)(d)第77頁(yè)/共132頁(yè)78接收端設(shè)置接收窗口 在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。 若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將其丟棄。 在連續(xù) ARQ 協(xié)議中，接收窗口的大小 WR = 1。 只有當(dāng)收到的幀的序號(hào)與接收窗口一致時(shí)才能接收該幀。否則，就丟棄它。 每收到一個(gè)序號(hào)正確的幀，接收窗口就向前（即向右方）滑動(dòng)一個(gè)幀的位置。同時(shí)發(fā)送對(duì)該幀的確認(rèn)。

43、第78頁(yè)/共132頁(yè)79不允許接收這些幀01234567012WR準(zhǔn)備接收 0 號(hào)幀(a)不允許接收這些幀01234567012WR準(zhǔn)備接收 1 號(hào)幀已收到(b)不允許接收這些幀01234567012WR準(zhǔn)備接收 4 號(hào)幀已收到(c)第79頁(yè)/共132頁(yè)80滑動(dòng)窗口的重要特性 只有在接收窗口向前滑動(dòng)時(shí)（與此同時(shí)也發(fā)送了確認(rèn)），發(fā)送窗口才有可能向前滑動(dòng)。 收發(fā)兩端的窗口按照以上規(guī)律不斷地向前滑動(dòng)，因此這種協(xié)議又稱(chēng)為滑動(dòng)窗口協(xié)議。 當(dāng)發(fā)送窗口和接收窗口的大小都等于 1時(shí)，就是停止等待協(xié)議。 第80頁(yè)/共132頁(yè)81發(fā)送窗口的最大值 當(dāng)用 n 個(gè)比特進(jìn)行編號(hào)時(shí)，若接收窗口的大小為 1，則只有在發(fā)送窗

44、口的大小 WT 2n 1時(shí)，連續(xù) ARQ 協(xié)議才能正確運(yùn)行。 例如，當(dāng)采用 3 bit 編碼時(shí)，發(fā)送窗口的最大值是 7 而不是 8。 第81頁(yè)/共132頁(yè)823 信道利用率 由于每個(gè)數(shù)據(jù)幀都必須包括一定的控制信息(如幀的序號(hào)、地址、同步信息以及其他的一些控制信息)，所以即使連續(xù)不停地發(fā)送數(shù)據(jù)幀，信道利用率(即扣除全部的控制信息后的數(shù)據(jù)率與信道容量之比)也不可能達(dá)到 100 %。 當(dāng)出現(xiàn)差錯(cuò)時(shí)(這是不可避免的)，數(shù)據(jù)幀的不斷重傳將進(jìn)一步使信道利用率降低。 第82頁(yè)/共132頁(yè)83最佳幀長(zhǎng) 若數(shù)據(jù)幀的幀長(zhǎng)取得很短，那么控制信息在每一幀中所占的比例就增大，因而額外開(kāi)銷(xiāo)增大，這就導(dǎo)致信道利用率的下降。

45、 若幀長(zhǎng)取得太長(zhǎng)，則數(shù)據(jù)幀在傳輸過(guò)程中出錯(cuò)的概率就增大，于是重傳次數(shù)將增大，這也會(huì)使信道利用率下降。 由此可見(jiàn)，存在一個(gè)最佳幀長(zhǎng)，在此幀長(zhǎng)下信道的利用率最高。 第83頁(yè)/共132頁(yè)844.4.3 Selective Repeat Protocol(SRP) 可加大接收窗口，先收下發(fā)送序號(hào)不連續(xù)但仍處在接收窗口中的那些數(shù)據(jù)幀。等到所缺序號(hào)的數(shù)據(jù)幀收到后再一并送交主機(jī)。 選擇重傳 ARQ 協(xié)議可避免重復(fù)傳送那些本來(lái)已經(jīng)正確到達(dá)接收端的數(shù)據(jù)幀。 但我們付出的代價(jià)是在接收端要設(shè)置具有相當(dāng)容量的緩存空間。 對(duì)于選擇重傳 ARQ 協(xié)議，若用 n 比特進(jìn)行編號(hào)，則接收窗口的最大值受下式的約束WR 2n/2

46、(3-18) 第84頁(yè)/共132頁(yè)85選擇重發(fā)協(xié)議(ARP)原理：只有特定的丟失幀或損壞幀被重發(fā)。如果在傳輸中一幀被損壞，就返回一個(gè)NAK幀并且該幀不按照順序進(jìn)行重發(fā)。接收設(shè)備必須能夠?qū)σ呀邮盏膸M(jìn)行排序并能將重傳的幀插入到序列中的正確位置。為實(shí)現(xiàn)這種可選擇性，ARP系統(tǒng)與回退n幀系統(tǒng)有以下的不同： 接收設(shè)備必須具有排序的邏輯功能以便于對(duì)亂序接收的幀進(jìn)行排序。同時(shí)在發(fā)送了NAK幀后還必須有存儲(chǔ)所接收幀的功能，直到損壞的幀被替換。 發(fā)送設(shè)備必須具有查找機(jī)制來(lái)幫助它發(fā)現(xiàn)和選擇只需要重傳的幀。 接收方的緩沖區(qū)必須保存以前接收的所有幀，直到所有重傳的幀都被排序并且所有重復(fù)的幀都被識(shí)別出來(lái)并刪除。第85

47、頁(yè)/共132頁(yè)864.5 數(shù)據(jù)鏈路層的控制規(guī)程 數(shù)據(jù)同步：在數(shù)據(jù)傳輸過(guò)程中，為了使接收方能夠準(zhǔn)確接收數(shù)據(jù)，接收方必須知道發(fā)送方發(fā)送數(shù)據(jù)的起始位置和結(jié)束位置。 實(shí)現(xiàn)方法：異步規(guī)程和同步規(guī)程（面向字符和面向比特）第86頁(yè)/共132頁(yè)874.5.1 面向字符型協(xié)議實(shí)例面向字符型協(xié)議實(shí)例 什么是面向字符型協(xié)議什么是面向字符型協(xié)議? 以字符為控制傳輸信息的基本單元以字符為控制傳輸信息的基本單元 ASIIC碼：碼： 格式字符：格式字符：SOH（start of heading） STX（start of text） ETB（end of transmission block） ETX（end of tex

48、t） 控制字符：控制字符：ACK（acknowledge） NAK（negative acknowledge） ENQ（enquire） EOT（end of transmission） SYN（synchrous） DLE（data link escape）第87頁(yè)/共132頁(yè)88 面向字符型面向字符型BSC協(xié)議的數(shù)據(jù)報(bào)文格式：協(xié)議的數(shù)據(jù)報(bào)文格式：第88頁(yè)/共132頁(yè)894.5 典型數(shù)據(jù)鏈路層協(xié)議分析典型數(shù)據(jù)鏈路層協(xié)議分析 面向比特型面向比特型4.5.1 HDLC產(chǎn)生的背景產(chǎn)生的背景 面向字符型數(shù)據(jù)鏈路層協(xié)議的缺點(diǎn)面向字符型數(shù)據(jù)鏈路層協(xié)議的缺點(diǎn)： 報(bào)文格式不一樣；過(guò)多依賴(lài)字符編碼集，不利于兼

49、容。報(bào)文格式不一樣；過(guò)多依賴(lài)字符編碼集，不利于兼容。 傳輸透明性不好；傳輸透明性不好； 等待發(fā)送方式，傳輸效率低。等待發(fā)送方式，傳輸效率低。面向比特型協(xié)議的設(shè)計(jì)目標(biāo)面向比特型協(xié)議的設(shè)計(jì)目標(biāo)： 以比特作為傳輸控制信息的基本單元；以比特作為傳輸控制信息的基本單元； 數(shù)據(jù)幀與控制幀格式相同；數(shù)據(jù)幀與控制幀格式相同； 傳輸透明性好；傳輸透明性好； 連續(xù)發(fā)送，傳輸效率高。連續(xù)發(fā)送，傳輸效率高。第89頁(yè)/共132頁(yè)90SDLC (Synchronous Data Link Control) 19741974年，年，IBM IBM 公司推出了面向比特的規(guī)程公司推出了面向比特的規(guī)程SDLC (Synchron

50、ous Data Link Control)SDLC (Synchronous Data Link Control)。 后來(lái)后來(lái) ISO ISO 把把 SDLC SDLC 修改后稱(chēng)為修改后稱(chēng)為 HDLC (High-HDLC (High-level Data Link Control)level Data Link Control)，譯為高級(jí)數(shù)據(jù)，譯為高級(jí)數(shù)據(jù)鏈路控制，作為國(guó)際標(biāo)準(zhǔn)鏈路控制，作為國(guó)際標(biāo)準(zhǔn)ISO 3309ISO 3309。 CCITT CCITT 則將則將 HDLC HDLC 再修改后稱(chēng)為鏈路接入規(guī)再修改后稱(chēng)為鏈路接入規(guī)程程 LAP (Link Access Procedure)

51、LAP (Link Access Procedure)。不久，。不久，HDLC HDLC 的新版本又把的新版本又把 LAP LAP 修改為修改為 LAPBLAPB，“B B”表示平衡型表示平衡型(Balanced)(Balanced)，所以，所以 LAPB LAPB 叫做鏈叫做鏈路接入規(guī)程路接入規(guī)程( (平衡型平衡型) )。 第90頁(yè)/共132頁(yè)91HDLC HDLC是支持在點(diǎn)到點(diǎn)和多點(diǎn)鏈路上的半雙工和全雙工通信而設(shè)計(jì)的,它是面向比特的數(shù)據(jù)鏈路協(xié)議。 面向比特的協(xié)議：則將傳輸幀或包看作是單個(gè)比特的連續(xù)流，通過(guò)它們?cè)趲奈恢煤团c其他比特的組合模式來(lái)表達(dá)意義。根據(jù)內(nèi)嵌在比特模式中的信息的不同，面向

52、比特的協(xié)議中的控制信息可以是一個(gè)或多個(gè)比特。第91頁(yè)/共132頁(yè)92兩個(gè) DTE 通過(guò) DCE進(jìn)行通信的例子 Data terminal equipment(DTE):Data terminal equipment(DTE):數(shù)據(jù)終端設(shè)備數(shù)據(jù)終端設(shè)備 Data circuit-terminating equipment(DCE):Data circuit-terminating equipment(DCE):數(shù)據(jù)電路端接設(shè)備數(shù)據(jù)電路端接設(shè)備 DTEDTE產(chǎn)生數(shù)據(jù)產(chǎn)生數(shù)據(jù), ,并連同必要的控制字符一起傳送給并連同必要的控制字符一起傳送給DCEDCE。DCEDCE將信號(hào)轉(zhuǎn)將信號(hào)轉(zhuǎn)化成適合于傳輸介質(zhì)

53、的形式并將它發(fā)送到網(wǎng)絡(luò)中。當(dāng)信號(hào)到達(dá)另一端化成適合于傳輸介質(zhì)的形式并將它發(fā)送到網(wǎng)絡(luò)中。當(dāng)信號(hào)到達(dá)另一端時(shí)時(shí), ,將發(fā)生相反的過(guò)程。將發(fā)生相反的過(guò)程。EIA-232/ V.24 接口調(diào)制解調(diào)器DTE-ADTE-BDCE-ADCE-BEIA-232/ V.24 接口調(diào)制解調(diào)器網(wǎng) 絡(luò)第92頁(yè)/共132頁(yè)93station(站） 數(shù)據(jù)鏈路中不同類(lèi)型的DTE統(tǒng)稱(chēng)為“站”(station) 由計(jì)算機(jī)和終端組成，負(fù)責(zé)發(fā)送和接收幀。涉及三種類(lèi)型的站：Primary station(主站）：send information or command主要功能是發(fā)送命令（包括數(shù)據(jù)），接收響應(yīng)，負(fù)責(zé)整個(gè)鏈路的控制（如系統(tǒng)

54、的初始、流控、差錯(cuò)恢復(fù)等）；Secondary station(從站）：receive information or send response主要功能是接收命令，發(fā)送響應(yīng)，配合主站完成鏈路的控制；Compound station（組合站）： 同時(shí)具有主、次站功能，既發(fā)送又接收命令和響應(yīng)，并負(fù)責(zé)整個(gè)鏈路的控制。第93頁(yè)/共132頁(yè)944.5.2 數(shù)據(jù)鏈路的配置和數(shù)據(jù)傳送方式數(shù)據(jù)鏈路的配置和數(shù)據(jù)傳送方式數(shù)據(jù)鏈路的配置數(shù)據(jù)鏈路的配置 非平衡配置非平衡配置 平衡配置平衡配置非平衡配置中的主站與從站非平衡配置中的主站與從站 主站：控制數(shù)據(jù)鏈路的工作過(guò)程。主站發(fā)出命主站：控制數(shù)據(jù)鏈路的工作過(guò)程。主站發(fā)出

55、命令令 從站：接受命令，發(fā)出響應(yīng)，配合主站工作從站：接受命令，發(fā)出響應(yīng)，配合主站工作非平衡配置中的結(jié)構(gòu)特點(diǎn)非平衡配置中的結(jié)構(gòu)特點(diǎn) 點(diǎn)點(diǎn)- -點(diǎn)方式點(diǎn)方式 多點(diǎn)方式多點(diǎn)方式第94頁(yè)/共132頁(yè)95HDLC適用的鏈路配置 非平衡型 適合把智能和半智能的終端連接到計(jì)算機(jī)。 點(diǎn) 點(diǎn)式 多點(diǎn)式主站主站次站次站主站主站次站次站次站次站次站次站.第95頁(yè)/共132頁(yè)96非平衡配置方式非平衡配置方式正常響應(yīng)模式（正常響應(yīng)模式（normal response mode，NRM） 主站可以隨時(shí)向從站傳輸數(shù)據(jù)幀；主站可以隨時(shí)向從站傳輸數(shù)據(jù)幀； 從站只有在主站向它發(fā)送命令幀進(jìn)行探詢(xún)（從站只有在主站向它發(fā)送命令幀進(jìn)行探

56、詢(xún)（poll），），從站響應(yīng)后才可以向主站發(fā)送數(shù)據(jù)幀。從站響應(yīng)后才可以向主站發(fā)送數(shù)據(jù)幀。 異步響應(yīng)模式（異步響應(yīng)模式（asynchronous response mode，ARM） 主站和從站可以隨時(shí)相互傳輸數(shù)據(jù)幀；主站和從站可以隨時(shí)相互傳輸數(shù)據(jù)幀； 從站可以不需要等待主站發(fā)出探詢(xún)就可以發(fā)送數(shù)據(jù)；從站可以不需要等待主站發(fā)出探詢(xún)就可以發(fā)送數(shù)據(jù)； 主站負(fù)責(zé)數(shù)據(jù)鏈路的初始化、鏈路的建立、釋放與主站負(fù)責(zé)數(shù)據(jù)鏈路的初始化、鏈路的建立、釋放與差錯(cuò)恢復(fù)等功能。差錯(cuò)恢復(fù)等功能。第96頁(yè)/共132頁(yè)97數(shù)據(jù)鏈路的非平衡配置方式數(shù)據(jù)鏈路的非平衡配置方式第97頁(yè)/共132頁(yè)98平衡配置方式平衡配置方式 鏈路兩端的兩

57、個(gè)站都是復(fù)合站（鏈路兩端的兩個(gè)站都是復(fù)合站（combined station）；）； 復(fù)合站同時(shí)具有主站與從站的功能；復(fù)合站同時(shí)具有主站與從站的功能； 每個(gè)復(fù)合站都可以發(fā)出命令與響應(yīng)；每個(gè)復(fù)合站都可以發(fā)出命令與響應(yīng)； 平衡配置結(jié)構(gòu)中只有異步平衡模式平衡配置結(jié)構(gòu)中只有異步平衡模式（asynchronous balanced mode，ABM）；）； 異步平衡模式的每個(gè)復(fù)合站都可以平等地發(fā)異步平衡模式的每個(gè)復(fù)合站都可以平等地發(fā)起數(shù)據(jù)傳輸，而不需要得到對(duì)方復(fù)合站的許起數(shù)據(jù)傳輸，而不需要得到對(duì)方復(fù)合站的許可。可。組合站組合站組合站組合站適合于計(jì)算機(jī)和計(jì)算機(jī)之間的連接第98頁(yè)/共132頁(yè)99數(shù)據(jù)鏈路的平

58、衡配置方式數(shù)據(jù)鏈路的平衡配置方式第99頁(yè)/共132頁(yè)100數(shù)據(jù)傳輸模式（操作方式）Three modes of operations:normal response mode,asynchronous response mode and asynchronous balanced mode.（正常響應(yīng)，異步響應(yīng)和異步平衡方式） normal response mode:a secondary node cannot initiate a transfer,but can only respond to a poll request. 只有主站才能發(fā)起向從站的數(shù)據(jù)傳輸，從站只有向主站探詢(xún)后才能發(fā)

59、出響應(yīng)幀PSCR第100頁(yè)/共132頁(yè)101Asynchronous response mode:Asynchronous response mode:主站負(fù)責(zé)主站負(fù)責(zé)鏈路的邏輯連接、初始化和差錯(cuò)控制，而鏈路的邏輯連接、初始化和差錯(cuò)控制，而從站可以不需要主站探詢(xún)即可發(fā)送響應(yīng)幀。從站可以不需要主站探詢(xún)即可發(fā)送響應(yīng)幀。Asynchronous balanced modeAsynchronous balanced mode: :have have symmetric roles.symmetric roles.鏈路上的任何一個(gè)組鏈路上的任何一個(gè)組合站可在任意時(shí)刻發(fā)送命令，并且無(wú)須得合站可在任意時(shí)刻發(fā)

60、送命令，并且無(wú)須得到對(duì)方的明確允許，就可以傳送響應(yīng)幀到對(duì)方的明確允許，就可以傳送響應(yīng)幀。CCCRRC第101頁(yè)/共132頁(yè)1024.5.3 HDLC 的幀結(jié)構(gòu) 標(biāo)志字段 F (Flag) 為 6 個(gè)連續(xù) 1 加上兩邊各一個(gè) 0 共 8 bit。在接收端只要找到標(biāo)志字段就可確定一個(gè)幀的位置。 比特888可變168信息 Info標(biāo)志 F標(biāo)志 F地址 A控制 C幀檢驗(yàn)序列 FCS透明傳輸區(qū)間FCS 檢驗(yàn)區(qū)間第102頁(yè)/共132頁(yè)103Frame(HDLC) FLAG :Bit pattern 01111110 幀同步 To prevent the flag from occurring inside