3章-數(shù)據(jù)鏈路層課件

1、計(jì)算機(jī)網(wǎng)絡(luò)第 3 章 數(shù)據(jù)鏈路層計(jì)算機(jī)網(wǎng)絡(luò)第 3 章 數(shù)據(jù)鏈路層第3章 數(shù)據(jù)鏈路層3.1 數(shù)據(jù)鏈路層概述3.2 幀同步功能3.3 流量控制功能3.4 差錯(cuò)檢測(cè)（重點(diǎn)）第3章 數(shù)據(jù)鏈路層3.1 數(shù)據(jù)鏈路層概述3.1 數(shù)據(jù)鏈路層概述數(shù)據(jù)鏈路層是OSI參考模型中的第二層,介乎于物理層和網(wǎng)絡(luò)層之間，在物理層所提供的服務(wù)的基礎(chǔ)上向網(wǎng)絡(luò)層提供服務(wù)。數(shù)據(jù)鏈路層的作用是對(duì)物理層傳輸原始比特流的功能的加強(qiáng)，將物理層提供的可能出錯(cuò)的物理連接改造成為邏輯上無差錯(cuò)的數(shù)據(jù)鏈路，即使之對(duì)網(wǎng)絡(luò)層表現(xiàn)為一條無差錯(cuò)的鏈路。數(shù)據(jù)鏈路層在相鄰結(jié)點(diǎn)的物理連接上為網(wǎng)絡(luò)層建立、維持、釋放鏈路連接，并在鏈路連接上可靠地、正確地傳送鏈路層協(xié)

2、議數(shù)據(jù)單元(通常稱為幀-Frame)3.1 數(shù)據(jù)鏈路層概述數(shù)據(jù)鏈路層是OSI參考模型中的第二層,數(shù)據(jù)鏈路層的簡(jiǎn)單模型局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(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)數(shù)據(jù)鏈路層的簡(jiǎn)單模型局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 數(shù)據(jù)鏈路層的簡(jiǎn)單模型( 續(xù)）局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)

3、絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動(dòng)數(shù)據(jù)鏈路層的簡(jiǎn)單模型( 續(xù)）局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2第3章-數(shù)據(jù)鏈路層課件3.1 使用點(diǎn)對(duì)點(diǎn)信道的數(shù)據(jù)鏈路層3.1.1 數(shù)據(jù)鏈路和幀 鏈路(link)是一條無源的點(diǎn)到點(diǎn)的物理線路段，中間沒有任何其他的交換結(jié)點(diǎn)。一條鏈路只是一條通路的一個(gè)組成部分。數(shù)據(jù)鏈路(data link) 除了物理線路外，還必須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實(shí)現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路?，F(xiàn)在最常用的方法是使用適配器（即網(wǎng)卡）來實(shí)現(xiàn)這些協(xié)議的硬件和軟

4、件。一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層的功能。 3.1 使用點(diǎn)對(duì)點(diǎn)信道的數(shù)據(jù)鏈路層3.1.1 數(shù)據(jù)鏈路和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ù)鏈路層傳送的是幀IP 數(shù)據(jù)報(bào)1010 0110幀取出數(shù)據(jù)網(wǎng)絡(luò)層鏈路結(jié)點(diǎn)3.1.2 三個(gè)基本問題 (1) 封裝成幀(2) 透明傳輸(3) 差錯(cuò)控制 3.1.2 三個(gè)基本問題 (1) 封裝成幀3.2 幀同步功能為了使傳輸中發(fā)生差錯(cuò)后只將出錯(cuò)的有限數(shù)據(jù)進(jìn)行重發(fā)，數(shù)據(jù)鏈路層將比特流組織成以幀為單位傳送。幀的組織結(jié)構(gòu)必須設(shè)

5、計(jì)成使接收方能夠明確的從物理層收到的比特流中區(qū)分出幀的起始與終止，這就是幀同步要解決的問題。同步的方法字符填充的首尾定界符法比特填充的首尾定界符法3.2 幀同步功能為了使傳輸中發(fā)生差錯(cuò)后只將出錯(cuò)的有限數(shù)據(jù)進(jìn)1. 封裝成幀封裝成幀(framing)就是在一段數(shù)據(jù)的前后分別添加首部和尾部，然后就構(gòu)成了一個(gè)幀。確定幀的界限。首部和尾部的一個(gè)重要作用就是進(jìn)行幀定界。 幀結(jié)束幀首部IP 數(shù)據(jù)報(bào)幀的數(shù)據(jù)部分幀尾部 MTU數(shù)據(jù)鏈路層的幀長(zhǎng)開始發(fā)送幀開始1. 封裝成幀封裝成幀(framing)就是在一段數(shù)據(jù)的前用控制字符進(jìn)行幀定界的方法舉例 SOH裝在幀中的數(shù)據(jù)部分幀幀開始符幀結(jié)束符發(fā)送在前EOT用控制字符進(jìn)

6、行幀定界的方法舉例 SOH裝在幀中的數(shù)據(jù)部分幀幀2. 透明傳輸SOHEOT出現(xiàn)了“EOT”被接收端當(dāng)作無效幀而丟棄被接收端誤認(rèn)為是一個(gè)幀數(shù)據(jù)部分EOT完整的幀發(fā)送在前2. 透明傳輸SOHEOT出現(xiàn)了“EOT”被接收端當(dāng)作無效解決透明傳輸問題發(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)義

7、字符時(shí)，就刪除其中前面的一個(gè)。 解決透明傳輸問題發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符“SOSOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始數(shù)據(jù)EOTEOT經(jīng)過字節(jié)填充后發(fā)送的數(shù)據(jù)字節(jié)填充字節(jié)填充字節(jié)填充字節(jié)填充發(fā)送在前幀開始符幀結(jié)束符用字節(jié)填充法解決透明傳輸?shù)膯栴} SOHSOHSOHEOTSOHESCESCEOTESCSOHESC3.2.2 比特填充的首尾定界符法在前面介紹的字符分界法中存在一個(gè)大的不足，那就是它僅依靠8位模式。而事實(shí)上，并不是所有的字符編碼都使用8位模式，如UNICODE編碼就使用了16位編碼方式。 “比特填充的首尾界定符法”是以一組特定的

8、比特模式（如01111110）來標(biāo)志一幀的起始與終止，它允許任意長(zhǎng)度的位碼，也允許任意每個(gè)字符有任意長(zhǎng)度的位。3.2.2 比特填充的首尾定界符法在前面介紹的字符分界法中存透明傳輸 發(fā)送端：若發(fā)現(xiàn)要發(fā)送的數(shù)據(jù)中有 5 個(gè)連續(xù) 1，則立即填入一個(gè) 0。接收端：對(duì)幀中的數(shù)據(jù)比特流進(jìn)行掃描。每當(dāng)發(fā)現(xiàn) 5 個(gè)連續(xù)1時(shí)，就把這 5 個(gè)連續(xù) 1 后的一個(gè) 0 刪除。透明傳輸 發(fā)送端：0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0信息字段中出現(xiàn)了和標(biāo)志

9、字段 F 完全一樣的 8 比特組合發(fā)送端在 5 個(gè)連續(xù) 1 之后填入 0 比特再發(fā)送出去在接收端把 5 個(gè)連 續(xù)1之后的 0 比特刪除會(huì)被誤認(rèn)為是標(biāo)志字段 F 發(fā)送端填入 0 比特接收端刪除填入的 0 比特零比特填充0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 例題：PPP協(xié)議使用同步傳輸技術(shù)傳送比特串0110111111111100。試問經(jīng)過零比特填充后變成怎樣的比特串?若接收端收到的PPP幀的數(shù)據(jù)部分是0001110111110111110110，問刪除發(fā)送端加入的零比特后變成怎樣的比特串? 答案：（1） 011011111011111000 （2） 000111011111

10、-11111-110例題：PPP協(xié)議使用同步傳輸技術(shù)傳送比特串011011111第3章-數(shù)據(jù)鏈路層課件3.3 流量控制功能(傳輸層TCP來講)流量控制是指一組過程限制發(fā)送方在等待確認(rèn)前能夠發(fā)送的數(shù)據(jù)量保證發(fā)送實(shí)體發(fā)送的數(shù)據(jù)不超出接收實(shí)體接收數(shù)據(jù)的能力防止緩沖溢出3.3 流量控制功能(傳輸層TCP來講)流量控制是指一組過程 ？發(fā)送方：？接收方：？傳輸過程：！解決這些問題，是鏈路層的主要任務(wù)。！針對(duì)這些問題所制定的通信規(guī)程就是數(shù)據(jù)鏈路層的通信協(xié)議。以多快的速度發(fā)送數(shù)據(jù)幀，即每幀之間相隔多長(zhǎng)時(shí)間？如何確認(rèn)對(duì)方是否收到數(shù)據(jù)？是否接收到正確的數(shù)據(jù)幀？如何告訴發(fā)送方？能及時(shí)處理接收到的數(shù)據(jù)幀嗎？在數(shù)據(jù)鏈路

11、層上傳輸數(shù)據(jù)幀會(huì)出錯(cuò)嗎？會(huì)丟失數(shù)據(jù)幀嗎？數(shù)據(jù)鏈路層功能 ？發(fā)送方：？接收方：？傳輸過程：！解決這些問題，是鏈路層的3.3.1 完全理想化的數(shù)據(jù)傳輸數(shù)據(jù)鏈路層主機(jī) A緩存主機(jī) B數(shù)據(jù)鏈路AP2AP1緩存發(fā)送方接收方幀高層幀3.3.1 完全理想化的數(shù)據(jù)傳輸數(shù)據(jù)鏈路層主緩存主數(shù)據(jù)鏈路A完全理想化的數(shù)據(jù)傳輸所基于的兩個(gè)前提1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時(shí)上交主機(jī)。完全理想化的數(shù)據(jù)傳輸所基于的兩個(gè)前提1： 鏈路是理想的傳輸具有簡(jiǎn)單的流量控制DATA0ACKACKACKDATA2DATA1假設(shè)：鏈路是理想化的

12、，所傳輸?shù)臄?shù)據(jù)不會(huì)出錯(cuò)也不會(huì)丟失。協(xié)議算法協(xié)議思想：協(xié)調(diào)、控制接收方、發(fā)送方的速度。等待；將收到的數(shù)據(jù)幀上交主機(jī)；發(fā)送應(yīng)答信息；轉(zhuǎn)到第一步發(fā)出一幀；等待；直到收到ACK才發(fā)送下一幀發(fā)送方接收方2 停止等待協(xié)議具有簡(jiǎn)單的流量控制DATA0ACKACKACKDATA2DA兩種情況的對(duì)比（傳輸均無差錯(cuò)）ABDATADATADATADATA送主機(jī) B送主機(jī) B送主機(jī) B送主機(jī) BABDATA送主機(jī) BDATA送主機(jī) B時(shí)間不需要流量控制需要流量控制兩種情況的對(duì)比（傳輸均無差錯(cuò)）ABDATADATADATAD實(shí)用的停止等待協(xié)議時(shí)間ABDATA0送主機(jī)ACKDATA1送主機(jī)ACK(a) 正常情況ABDAT

13、A0DATA0送主機(jī)ACK(c) 數(shù)據(jù)幀丟失重傳tout丟失 ！ABDATA0送主機(jī)ACKDATA0丟棄ACK(d) 確認(rèn)幀丟失重傳tout丟失 ！ABDATA0NAKDATA0送主機(jī)ACK(b) 數(shù)據(jù)幀出錯(cuò)重傳出錯(cuò)四種情況實(shí)用的停止等待協(xié)議時(shí)ABDATA0送ACKDATA1送ACK超時(shí)計(jì)時(shí)器的作用結(jié)點(diǎn)A發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)，就啟動(dòng)一個(gè)超時(shí)計(jì)時(shí)器(timeout timer)。計(jì)時(shí)器又稱為定時(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í)間”。 超時(shí)計(jì)時(shí)器的

14、作用結(jié)點(diǎn)A發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)，就啟動(dòng)一個(gè)超時(shí)計(jì)時(shí)解決重復(fù)幀的問題 使每一個(gè)數(shù)據(jù)幀帶上不同的發(fā)送序號(hào)。每發(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)收到過同樣的數(shù)據(jù)幀并且也交給了主機(jī) B。但此時(shí)結(jié)點(diǎn) B 還必須向 A 發(fā)送確認(rèn)幀 ACK，因?yàn)?B 已經(jīng)知道 A 還沒有收到上一次發(fā)過去的確認(rèn)幀 ACK。 解決重復(fù)幀的問題 使每一個(gè)數(shù)據(jù)幀帶上不同的發(fā)送序號(hào)。每發(fā)送一幀的編號(hào)問題 任何一個(gè)編號(hào)系統(tǒng)的序號(hào)所占用的比特?cái)?shù)一定是有限的。因此，經(jīng)過一段時(shí)間后，發(fā)送序號(hào)就會(huì)重復(fù)。 序號(hào)占用的比特?cái)?shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷就越小。

15、 對(duì)于停止等待協(xié)議，由于每發(fā)送一個(gè)數(shù)據(jù)幀就停止等待，因此用一個(gè)比特來編號(hào)就夠了。一個(gè)比特可表示 0 和 1 兩種不同的序號(hào)。 幀的編號(hào)問題 任何一個(gè)編號(hào)系統(tǒng)的序號(hào)所占用的比特?cái)?shù)一定是有限幀的發(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ū)分開新的數(shù)據(jù)幀和重傳的數(shù)據(jù)幀了。 幀的發(fā)送序號(hào) 數(shù)據(jù)幀中的發(fā)送序號(hào) N(S) 以 0 和 1 停止等待協(xié)議的算法這里不使用否認(rèn)幀（實(shí)用的數(shù)據(jù)鏈路層協(xié)議大都是這樣的），而且確認(rèn)幀帶有序號(hào) n。按照習(xí)慣的表示法，ACKn 表示“第 n 1 號(hào)幀已經(jīng)收到

16、，現(xiàn)在期望接收第 n 號(hào)幀”。ACK1 表示“0 號(hào)幀已收到，現(xiàn)在期望接收的下一幀是 1 號(hào)幀”；ACK0 表示“1 號(hào)幀已收到，現(xiàn)在期望接收的下一幀是 0 號(hào)幀”。 停止等待協(xié)議的算法這里不使用否認(rèn)幀（實(shí)用的數(shù)據(jù)鏈路層協(xié)議大都停止等待協(xié)議的要點(diǎn)連續(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è)副本。 停止等待協(xié)議的要點(diǎn)連續(xù)出現(xiàn)相同發(fā)送序號(hào)的數(shù)據(jù)幀，表明發(fā)送端進(jìn)停止等待協(xié)議的要點(diǎn)實(shí)用的 CRC

17、檢驗(yàn)器都是用硬件完成的。CRC 檢驗(yàn)器能夠自動(dòng)丟棄檢測(cè)到的出錯(cuò)幀。因此所謂的“丟棄出錯(cuò)幀”，對(duì)上層軟件或用戶來說都是感覺不到的。發(fā)送端對(duì)出錯(cuò)的數(shù)據(jù)幀進(jìn)行重傳是自動(dòng)進(jìn)行的，因而這種差錯(cuò)控制體制常簡(jiǎn)稱為 ARQ (Automatic Repeat reQuest)，直譯是自動(dòng)重傳請(qǐng)求，但意思是自動(dòng)請(qǐng)求重傳。 停止等待協(xié)議的要點(diǎn)實(shí)用的 CRC 檢驗(yàn)器都是用硬件完成的。停止等待協(xié)議的定量分析設(shè) tf 是一個(gè)數(shù)據(jù)幀的發(fā)送時(shí)間，且數(shù)據(jù)幀的長(zhǎng)度是固定不變的。顯然，數(shù)據(jù)幀的發(fā)送時(shí)間 tf 是數(shù)據(jù)幀的長(zhǎng)度 lf (bit)與數(shù)據(jù)的發(fā)送速率 C (bit/s)之比，即 tf = lf /C = lf /C (s)

18、 （3-1） 發(fā)送時(shí)間 tf 也就是數(shù)據(jù)幀的發(fā)送時(shí)延。數(shù)據(jù)幀沿鏈路傳到結(jié)點(diǎn)B還要經(jīng)歷一個(gè)傳播時(shí)延 tp。結(jié)點(diǎn) B 收到數(shù)據(jù)幀要花費(fèi)時(shí)間進(jìn)行處理，此時(shí)間稱為處理時(shí)間 tpr，發(fā)送確認(rèn)幀 ACK 的發(fā)送時(shí)間為 ta。 停止等待協(xié)議的定量分析設(shè) tf 是一個(gè)數(shù)據(jù)幀的發(fā)送時(shí)間，且數(shù)停止等待協(xié)議中數(shù)據(jù)幀和確認(rèn)幀的發(fā)送時(shí)間關(guān)系 ABDATADATAACK傳播時(shí)延 tp處理時(shí)間 tpr確認(rèn)幀發(fā)送時(shí)間 ta傳播時(shí)延 tp處理時(shí)間 tprtT時(shí)間兩個(gè)成功發(fā)送的數(shù)據(jù)幀之間的最小時(shí)間間隔數(shù)據(jù)幀的發(fā)送時(shí)間tf設(shè)置的重傳時(shí)間tout停止等待協(xié)議中數(shù)據(jù)幀和確認(rèn)幀的發(fā)送時(shí)間關(guān)系 ABDATADA重傳時(shí)間 重傳時(shí)間的作用是：

19、數(shù)據(jù)幀發(fā)送完畢后若經(jīng)過了這樣長(zhǎng)的時(shí)間還沒有收到確認(rèn)幀，就重傳這個(gè)數(shù)據(jù)幀。 為方便起見，我們?cè)O(shè)重傳時(shí)間為 tout = tp + tpr+ ta + tp + tpr 設(shè)上式右端的處理時(shí)間 tpr 和確認(rèn)幀的發(fā)送時(shí)間 ta 都遠(yuǎn)小于傳播時(shí)延 tp，因此可將重傳時(shí)間取為兩倍的傳播時(shí)延，即 tout = 2tp兩個(gè)發(fā)送成功的數(shù)據(jù)幀之間的最小時(shí)間間隔是 tT = tf + tout = tf + 2tp重傳時(shí)間 重傳時(shí)間的作用是：數(shù)據(jù)幀發(fā)送完畢后若經(jīng)過了這樣長(zhǎng)的停止等待協(xié)議 ARQ 的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：比較簡(jiǎn)單 。缺點(diǎn)：通信信道的利用率不高，也就是說，信道還遠(yuǎn)遠(yuǎn)沒有被數(shù)據(jù)比特填滿。為了克服這一缺點(diǎn)，就產(chǎn)生

20、了另外兩種協(xié)議，即連續(xù) ARQ 和選擇重傳 ARQ。這將在后面進(jìn)一步討論。 停止等待協(xié)議 ARQ 的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：比較簡(jiǎn)單 。例：信道的數(shù)據(jù)傳輸速率為4Kbps,傳播延遲時(shí)間20ms（未注明往返則指單程），求幀長(zhǎng)在什么范圍內(nèi)才使停等協(xié)議的信道利用率達(dá)到50%以上。（注：信道利用率：指信道用于發(fā)送數(shù)據(jù)幀的時(shí)間在所有信道占用時(shí)間中的百分比）例：信道的數(shù)據(jù)傳輸速率為4Kbps,傳播延遲時(shí)間20ms（未解析：已知信道的數(shù)據(jù)傳輸速率B=4kbps=4000bps，信道的單向傳播時(shí)延R=20ms=0.02s，一幀的幀長(zhǎng)為L(zhǎng)。在停止等待協(xié)議中，協(xié)議忙的時(shí)間為數(shù)據(jù)發(fā)送的時(shí)間=L/B，協(xié)議空閑的時(shí)間為數(shù)據(jù)發(fā)送后

21、等待確認(rèn)幀返回的時(shí)間=2R。則要使停止等待協(xié)議的效率至少為50%，即要求信道利用率至少為50%。因?yàn)樾诺览寐蕯?shù)據(jù)發(fā)送時(shí)延/（傳播時(shí)延數(shù)據(jù)發(fā)送時(shí)延），則有：L/B/(L/B2R)50%可得，L2BR=240000.02=160(b)因此，當(dāng)幀長(zhǎng)大于等于160比特時(shí)，停止等待協(xié)議的效率至少為50%。解析：已知信道的數(shù)據(jù)傳輸速率B=4kbps=4000bps，3 連續(xù) ARQ 協(xié)議在發(fā)送完一個(gè)數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個(gè)數(shù)據(jù)幀。如果這時(shí)收到了接收端發(fā)來的確認(rèn)幀，那么還可以接著發(fā)送數(shù)據(jù)幀。由于減少了等待時(shí)間，整個(gè)通信的吞吐量就提高了。 3 連續(xù) ARQ 協(xié)議在發(fā)送完一個(gè)數(shù)

22、據(jù)幀后，不是停下來等待連續(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連續(xù) ARQ 協(xié)議的工作原理 DATA0DATA1DATA2需要注意： (1)

23、接收端只按序接收數(shù)據(jù)幀。雖然在有差錯(cuò)的 2號(hào)幀之后接著又收到了正確的 3 個(gè)數(shù)據(jù)幀，但接收端都必須將這些幀丟棄，因?yàn)樵谶@些幀前面有一個(gè) 2 號(hào)幀還沒有收到。雖然丟棄了這些不按序的無差錯(cuò)幀，但應(yīng)重復(fù)發(fā)送已發(fā)送過的最后一個(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)幀。依此類推。 需要注意： (1) 接收端只按序接收數(shù)據(jù)幀。雖然在有差錯(cuò)的 需要注意： (3) 結(jié)點(diǎn) A 在每發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)都要設(shè)置該幀的超時(shí)計(jì)時(shí)器。如果在所設(shè)置的超時(shí)時(shí)間內(nèi)收到確認(rèn)幀，就立即將超時(shí)計(jì)時(shí)器清零。但

24、若在所設(shè)置的超時(shí)時(shí)間到了而未收到確認(rèn)幀，就要重傳相應(yīng)的數(shù)據(jù)幀（仍需重新設(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 又稱為Go-back-N ARQ，意思是當(dāng)出現(xiàn)差錯(cuò)必須重傳時(shí)，要向回走 N 個(gè)幀，然后再開始重傳。 需要注意： (3) 結(jié)點(diǎn) A 在每發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)都要設(shè)置4 選擇重傳ARQ協(xié)議 GO-BACK-N可能將已正確傳送到目的方的幀再重傳一遍，這顯然是一種浪費(fèi)。另一種效率更高的策略是當(dāng)接收方發(fā)現(xiàn)某幀出錯(cuò)后，其后繼續(xù)送來的正確的幀雖然不能立即遞交給接收方的高層

25、，但接收方仍可收下來，存放在緩沖區(qū)中，同時(shí)要求發(fā)送方重新傳送出錯(cuò)的那一幀。一旦收到重新傳來的幀后，就可以和已存于緩沖區(qū)中的其余幀一并按正確的順序遞交高層。這種方法稱為選擇重發(fā)，其工作過程如圖所示。圖中2號(hào)幀的否認(rèn)返回信息NAK2要求發(fā)送方選擇重發(fā)2號(hào)幀。顯然，選擇重發(fā)減少了浪費(fèi)，但要求接收方有足夠大的緩沖區(qū)空間。 選擇重發(fā)ARQ原理示意4 選擇重傳ARQ協(xié)議 GO-BACK-N可能將已正5 滑動(dòng)窗口協(xié)議 在使用連續(xù)ARQ協(xié)議時(shí)，在沒收到應(yīng)答時(shí)，實(shí)際上不能無限制的發(fā)送數(shù)據(jù)。因?yàn)椋?、重傳太多會(huì)花費(fèi)較多的時(shí)間，增大開銷；2、發(fā)送序號(hào)也占用比特?cái)?shù)。 因此應(yīng)對(duì)已發(fā)送出去而未被確認(rèn)的數(shù)據(jù)幀的數(shù)目加以限制

26、，這就是滑動(dòng)窗口所要研究的內(nèi)容。5 滑動(dòng)窗口協(xié)議 在使用連續(xù)ARQ協(xié)議時(shí)，在沒收到應(yīng)答滑動(dòng)窗口的概念發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口 。發(fā)送窗口用來對(duì)發(fā)送端進(jìn)行流量控制。發(fā)送窗口的大小 WT 代表在還沒有收到對(duì)方確認(rèn)信息的情況下發(fā)送端最多可以發(fā)送多少個(gè)數(shù)據(jù)幀。 滑動(dòng)窗口的概念發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口 。01234567012發(fā)送窗口WT不允許發(fā)送這些幀允許發(fā)送 5 個(gè)幀(a)01234567012不允許發(fā)送這些幀還允許發(fā)送 4 個(gè)幀WT已發(fā)送(b)01234567012不允許發(fā)送這些幀WT已發(fā)送(c)01234567012不允許發(fā)送這些幀還允許發(fā)送 3 個(gè)幀WT已發(fā)送

27、已發(fā)送并已收到確認(rèn)(d)01234567012發(fā)送窗口WT不允許發(fā)送這些幀允許發(fā)送 接收端設(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)。 接收端設(shè)置接收窗口 在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入不允許接收這些幀01234567012WR準(zhǔn)備接收 0 號(hào)幀(a)不允許接收這些幀01234567

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

29、行。例如，當(dāng)采用 3 bit 編碼時(shí)，發(fā)送窗口的最大值是 7 而不是 8。 發(fā)送窗口的最大值 當(dāng)用 n 個(gè)比特進(jìn)行編號(hào)時(shí)，若接收窗口的大后退 N幀ARQ協(xié)議，發(fā)送窗口不能大于2k1 ，接收窗口大小為1 說明：假定幀編號(hào)字段為3位長(zhǎng)，發(fā)送窗口尺寸為8(顯然不能大于8)。當(dāng)發(fā)送器收到一個(gè)單獨(dú)的ACK1后（這意味接收器期望接收第1幀及其之后的幀），把窗口推進(jìn)到后沿為1，前沿為0的位置，即發(fā)送窗口現(xiàn)在包含的幀號(hào)為l、2、3、4、5、6、7和0。如果這時(shí)又收到一個(gè)捎帶回的ACK1，發(fā)送器如何動(dòng)作呢？這后一個(gè)ACK1可能表示窗口中的所有幀都未曾接收，也可能意味著窗口中的幀都已正確接收。然而，如果規(guī)定窗口的

30、大小為7，則就可以避免這種二義性 后退 N幀ARQ協(xié)議，發(fā)送窗口不能大于2k1 ，接收窗口大選擇重發(fā)ARQ協(xié)議 W發(fā)=W收2k1若假設(shè)幀編號(hào)為3位，發(fā)送和接收窗口大小都是7，考慮下面的情況；(1) 發(fā)送窗口和接收窗口中的幀編號(hào)都是0到6；(2) 發(fā)送站發(fā)出0到6號(hào)幀，但尚未得到肯定應(yīng)答，窗口不能向前滑動(dòng)；(3) 接收站正確地接收了0至6號(hào)幀，發(fā)出了肯定應(yīng)答ACK7（注意，這個(gè)應(yīng)答信號(hào)表示0至6號(hào)幀已收到，下面期望收到7號(hào)及其以后的幀），因而接收窗口向前滑動(dòng)，新的窗口中的幀編號(hào)為7、0、1、2、3、4和5； (4) ACK7丟失，發(fā)送站定時(shí)器超時(shí)，重發(fā)0號(hào)幀；(5) 接收站收到0號(hào)幀并看到該幀編

31、號(hào)落在接收窗口內(nèi)，以為是新的0號(hào)幀而保存起來。認(rèn)為7號(hào)幀丟失了（其實(shí)發(fā)送站從未發(fā)出過），并繼續(xù)接收重復(fù)發(fā)來的1、2、3、4和5號(hào)幀。選擇重發(fā)ARQ協(xié)議 W發(fā)=W收2k13.4差錯(cuò)控制功能3.4差錯(cuò)控制功能1、差錯(cuò)的特性 通信信道中的噪聲主要有熱噪聲和沖擊噪聲：熱噪聲，是由傳輸媒體的電子熱運(yùn)動(dòng)產(chǎn)生的，這類噪聲主要是信道中存在的隨機(jī)噪聲（白噪聲）引起的隨機(jī)性差錯(cuò)；特點(diǎn)是隨機(jī)存在，幅度小，與頻率無關(guān)，而且是單個(gè)碼元出現(xiàn)差錯(cuò)，碼元間互不影響。沖擊噪聲，是由外界電磁干擾引起的，這類噪聲主要是信道中的脈沖干擾、信號(hào)衰落和瞬時(shí)中斷等因素造成的突發(fā)性差錯(cuò)；特點(diǎn)是幅度大，持續(xù)時(shí)間長(zhǎng)，而且是成批碼元突發(fā)性錯(cuò)誤，前

32、后碼元的差錯(cuò)具有一定的相關(guān)性。1、差錯(cuò)的特性 通信信道中的噪聲主要有熱噪聲和沖擊噪聲：雖然可以采用屏蔽、改善線路質(zhì)量、選擇有效的編碼方式等措施來減少噪聲，但還不能完全消除噪聲的影響。也就是說，在傳輸數(shù)據(jù)時(shí)，或多或少總會(huì)出現(xiàn)差錯(cuò)。通常，使用誤碼率Pe來衡量信道的傳輸質(zhì)量，即： Pe = 雖然可以采用屏蔽、改善線路質(zhì)量、選擇有效的編碼方式等措施來減為了減少傳輸差錯(cuò)，通常采用以下兩種方法：（1）改善線路質(zhì)量。加強(qiáng)線路本身的抗干擾能力，是減少差錯(cuò)最根本的途徑。例如，現(xiàn)在的網(wǎng)絡(luò)系統(tǒng)中越來越多地使用光纖傳輸系統(tǒng)，其誤碼率已低于109，這就從根本上提高了信道的傳輸質(zhì)量。但是，這種改善是以較大的投入為代價(jià)的。

33、 （2）差錯(cuò)的檢測(cè)與糾正。這是一種主動(dòng)式的差錯(cuò)控制措施。它的主要思想是：對(duì)所傳輸?shù)臄?shù)據(jù)進(jìn)行抗干擾編碼，并以此來檢測(cè)和校正傳輸中的錯(cuò)誤。 為了減少傳輸差錯(cuò)，通常采用以下兩種方法：2、差錯(cuò)控制編碼信號(hào)在物理信道中傳輸時(shí)，會(huì)造成信號(hào)的失真。在數(shù)據(jù)通信中，將會(huì)使接收端收到的二進(jìn)制數(shù)位和發(fā)送端實(shí)際發(fā)送的二進(jìn)制數(shù)位不一致，從而造成由“0”變成“1”或由“1”變成“0”的差錯(cuò)。2、差錯(cuò)控制編碼信號(hào)在物理信道中傳輸時(shí)，會(huì)造成信號(hào)的失真。在差錯(cuò)控制就是指在通信過程中，發(fā)現(xiàn)、檢測(cè)錯(cuò)誤，對(duì)差錯(cuò)進(jìn)行糾正。最常用的差錯(cuò)控制方法是差錯(cuò)控制編碼 最簡(jiǎn)單的差錯(cuò)控制方法是將每一個(gè)數(shù)據(jù)發(fā)送兩遍。接收方將這兩遍數(shù)據(jù)比較如有不同，即

34、可認(rèn)定出錯(cuò)了。這樣做將使傳輸速率大大下降， 數(shù)據(jù)本身傳輸時(shí)間要加倍，且逐位比較也要花費(fèi)大量時(shí)間。差錯(cuò)控制就是指在通信過程中，發(fā)現(xiàn)、檢測(cè)錯(cuò)誤，對(duì)差錯(cuò)進(jìn)行糾正。 差錯(cuò)控制最常用的技術(shù)是在每個(gè)數(shù)據(jù)單元中加入一些稱為“冗余碼”的附加數(shù)位(差錯(cuò)控制編碼)。這種技術(shù)之所以被稱為“冗余校驗(yàn)技術(shù)”,因?yàn)橐坏﹤鬏敱淮_認(rèn)無誤，那些附加的冗余數(shù)位便被自動(dòng)丟棄。 發(fā)送的碼字=信息位+冗余位 （輸入密碼或告訴對(duì)方電話號(hào)碼兩遍，第二遍給出的即為“冗余位”） 信息位要發(fā)送的數(shù)據(jù) 冗余位差錯(cuò)控制編碼第3章-數(shù)據(jù)鏈路層課件差錯(cuò)的控制編碼差錯(cuò)控制編碼可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼能自動(dòng)發(fā)現(xiàn)差錯(cuò)的編碼；不能糾正錯(cuò)誤糾錯(cuò)碼不僅能發(fā)現(xiàn)差

35、錯(cuò)而且能自動(dòng)糾正差錯(cuò)的編碼 差錯(cuò)的控制編碼差錯(cuò)控制編碼可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)差錯(cuò)的控制方法差錯(cuò)控制方法分兩類，一類是自動(dòng)請(qǐng)求重發(fā)ARQ，另一類是前向糾錯(cuò)FEC 自動(dòng)請(qǐng)求重發(fā)ARQ，當(dāng)接收端發(fā)現(xiàn)差錯(cuò)時(shí)，就設(shè)法通知發(fā)送端重發(fā)，直到收到正確的碼字為止。ARQ方式只使用檢錯(cuò)碼 前向糾錯(cuò)FEC ，接收端不但能發(fā)現(xiàn)差錯(cuò)，而且能確定二進(jìn)制碼元發(fā)生錯(cuò)誤的位置，從而加以糾正。差錯(cuò)的控制方法差錯(cuò)控制方法分兩類，一類是自動(dòng)請(qǐng)求重發(fā)ARQ，循環(huán)冗余校驗(yàn)(CRC) Cyclic Redundancy Check在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗(yàn) CRC 的檢錯(cuò)技術(shù)。CRC基于二進(jìn)制除法在CRC中，在數(shù)據(jù)

36、單元（比如一個(gè)字節(jié)）的后面附加一個(gè)稱為“循環(huán)冗余碼”或“CRC余數(shù)”的冗余數(shù)位串，使該數(shù)據(jù)單元可被另一個(gè)預(yù)先給定的二進(jìn)制數(shù)完全除盡。接收端將所接收的數(shù)據(jù)單元用同樣的二進(jìn)制數(shù)相除，如果無余數(shù)，則可認(rèn)為所接收的數(shù)據(jù)單元正確無誤，如果有余數(shù)，則認(rèn)定該數(shù)據(jù)單元已有差錯(cuò)。循環(huán)冗余校驗(yàn)(CRC) Cyclic Redundancy循環(huán)冗余校驗(yàn)碼 循環(huán)冗余校驗(yàn)編碼是通過多項(xiàng)式除法檢測(cè)錯(cuò)誤的。方法是將待傳輸?shù)臄?shù)據(jù)位串看成系數(shù)為0或1的多項(xiàng)式，如位串10011可表示為f(x)=x4+x+1.發(fā)送前收發(fā)雙方約定一個(gè)生成多項(xiàng)式G(x)(其最高階和最低階系數(shù)必為1)，發(fā)送方在數(shù)據(jù)位串的末尾加上校驗(yàn)和，使帶校驗(yàn)和的位串

37、多項(xiàng)式能被G(x)整除。接收方收到后用G(x)除多項(xiàng)式，若有余數(shù)，則傳輸有錯(cuò)循環(huán)冗余校驗(yàn)碼 循環(huán)冗余校驗(yàn)編碼是通過多項(xiàng)式除法檢測(cè)錯(cuò)誤1、若G(x)為r階，原始數(shù)據(jù)為m位，其多項(xiàng)式為M(x)，則在原始數(shù)據(jù)后面添加r個(gè)0，實(shí)際傳輸數(shù)據(jù)為m+r位，相應(yīng)多項(xiàng)式為xrM(x)。2、按模2除法用對(duì)應(yīng)于G(x)的位串去除對(duì)應(yīng)于xrM(x)的位串。3、按模2加法把xrM(x)的位串與余數(shù)相加，結(jié)果就是要傳送的帶校驗(yàn)和的數(shù)據(jù)多項(xiàng)式T(x)。1、若G(x)為r階，原始數(shù)據(jù)為m位，其多項(xiàng)式為M(x)，則例1 取生成多項(xiàng)式h（X）X4+X+1，假設(shè)欲發(fā)送的一段信息101100110，問在線路上傳輸?shù)拇a字是？解：由h(

38、X)X4+X+1得 生成的碼字為：10011，n為4在101100110后面添加n（此時(shí)n=4）個(gè)0，得到1011001100000 。 用1011001100000去除10011，得到余數(shù)為1000（保持n位，若不夠前面用0補(bǔ)上）把余數(shù)1000添加到要發(fā)送的數(shù)據(jù)101100110的后面，就是實(shí)際要傳送的碼字，為： 1011001101000 10101100010011 1011001100000 10011 10101 10011 11010 10011 10010 10011 1000例1 取生成多項(xiàng)式h（X）X4+X+1，假設(shè)欲發(fā)送的一段例3.已知：接收碼字:1100111001，生成

39、多項(xiàng)式:h(X)=X4+X3+1(r=4)求：碼字的正確性。若正確，則指出冗余碼和信息碼。解： 1)用接收到的碼字除以生成碼，余數(shù)為0，所以碼字正確。 2)因r=4，所以冗余碼是：1001，信息碼是:110011 例3.已知：接收碼字:1100111001，生成多項(xiàng)式:h(例4. 要發(fā)送的數(shù)據(jù)為1101。采用CRC的生成多項(xiàng)式是P(x)=x2+1 。試求應(yīng)添加在數(shù)據(jù)后面的余數(shù)。 數(shù)據(jù)在傳輸過程中要發(fā)送的數(shù)據(jù)1101變成1100，問接收端能否發(fā)現(xiàn)？能否發(fā)現(xiàn)那幾位發(fā)生錯(cuò)誤？ 若數(shù)據(jù)在傳輸過程中要發(fā)送的數(shù)據(jù)1101變成1000 ，問接收端能否發(fā)現(xiàn)？能否發(fā)現(xiàn)那幾位發(fā)生錯(cuò)誤？ 答：（1）添加的檢驗(yàn)序列為

40、10 （ 1101除以101）（2）數(shù)據(jù)在傳輸過程中要發(fā)送的數(shù)據(jù)1101變成1100 ，110010除以101，余數(shù)為01，不為0，接收端可以發(fā)現(xiàn)差錯(cuò)。（3）若數(shù)據(jù)在傳輸過程中要發(fā)送的數(shù)據(jù)1101變成1000 ， 100010除以101，余數(shù)為0，接收端不能發(fā)現(xiàn)差錯(cuò)。 例4. 要發(fā)送的數(shù)據(jù)為1101。采用CRC的生成多項(xiàng)式是P(檢錯(cuò)及糾錯(cuò)原理檢錯(cuò)及糾錯(cuò)原理信源產(chǎn)生的信息碼一般是由0、1序列表示的，其中0或1稱為碼元。假定在一碼組中任一碼字均是由n個(gè)碼元組成的，則碼組個(gè)數(shù)N2n構(gòu)成了一個(gè)全碼集，若將全碼集中所有碼組用來代表信息編碼，就不具有抗干擾的能力。為了更好地說明，假設(shè)由3個(gè)碼元組成8（23

41、）個(gè)碼組的全碼集，3位二進(jìn)制碼元共有8種可能的組合：000、001、010、011、100、101、110、111。如果這8種碼組都可傳遞消息，若在傳輸過程中發(fā)生一個(gè)誤碼，則一種碼組會(huì)錯(cuò)誤地變成另一種碼組。由于每一種碼組都可能出現(xiàn)，沒有多余的信息量，因此接收端不可能發(fā)現(xiàn)錯(cuò)誤，認(rèn)為發(fā)送的就是另一種碼組。信源產(chǎn)生的信息碼一般是由0、1序列表示的，其中0或1稱為碼元如果選其中000、011、101、110來傳送消息，這相當(dāng)于只傳遞00、01、10、11四種信息，而第3位是監(jiān)督位。保證碼組中“1”碼的個(gè)數(shù)為偶數(shù)。這4種碼組稱為許用碼組。另外4種碼組不滿足這種校驗(yàn)關(guān)系，稱為禁用碼組，它們?cè)诰幋a后的發(fā)送碼

42、元中不會(huì)出現(xiàn)。接收時(shí)一旦發(fā)現(xiàn)有禁用碼組，就表明傳輸過程中發(fā)生了錯(cuò)誤。用這種簡(jiǎn)單的校驗(yàn)關(guān)系可以發(fā)現(xiàn)1個(gè)或3個(gè)錯(cuò)誤，但不能糾正錯(cuò)誤。因?yàn)楫?dāng)接收到的碼組為禁用碼組時(shí)，比如為010，無法判斷發(fā)送的是哪個(gè)碼組。雖然原發(fā)送碼組為101的可能性很小(因?yàn)?個(gè)誤碼的概率一般很小)，但不能絕對(duì)排除，即使傳輸過程中只發(fā)生一個(gè)誤碼，也有三種可能的發(fā)送碼組即000、011和110。 假如進(jìn)一步將許用碼組限制為二種即000和111，顯然這樣可以發(fā)現(xiàn)所有2位以下的誤碼，若用來糾錯(cuò)，可以用最大似然準(zhǔn)則糾正1位錯(cuò)誤。如果選其中000、011、101、110來傳送消息，這相當(dāng)于一個(gè)編碼系統(tǒng)中任意兩個(gè)兩個(gè)碼組中對(duì)應(yīng)碼位上具有不同

43、二進(jìn)制碼元的位數(shù)為兩碼組的距離，稱為漢明(Hamming)距，簡(jiǎn)稱碼距。在前面3位二進(jìn)制碼組的例子中，當(dāng)8種碼組均為許用碼組時(shí)，兩碼組間的最小距離為1，稱這種編碼的最小碼距為1，一般記為dmin = 1；當(dāng)選4種碼組為許用碼組時(shí)，最小碼距dmin = 2；當(dāng)用2種碼組作為許用碼組時(shí)，dmin = 3。一個(gè)編碼系統(tǒng)中任意兩個(gè)兩個(gè)碼組中對(duì)應(yīng)碼位上具有不同二進(jìn)制碼元對(duì)于分組碼一般有以下結(jié)論: 在一個(gè)碼組內(nèi)檢測(cè)e個(gè)誤碼，要求最小碼距 dmin e + 1 (3-9)在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，要求最小碼距 dmin 2t + 1 (3-10)在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，同時(shí)檢測(cè)e(et)個(gè)誤碼，要求最小碼

44、距 dmin t + e + 1 （3-11）對(duì)于分組碼一般有以下結(jié)論: 差錯(cuò)糾正Error Detection差錯(cuò)糾正Error Detection差錯(cuò)糾正的基本技術(shù)自動(dòng)請(qǐng)求重發(fā) (ARQ , Automatic Repeat Request） 自動(dòng)發(fā)現(xiàn)差錯(cuò)并要求對(duì)方重發(fā)正向糾錯(cuò) (FEC , Forward Error Correction） 自動(dòng)發(fā)現(xiàn)并糾正錯(cuò)誤ARQ只需檢錯(cuò)碼，編碼效率高，設(shè)備簡(jiǎn)單，但要求雙向信道，發(fā)送方要有數(shù)據(jù)緩沖區(qū)。FEC要用糾錯(cuò)碼，編碼效率低，設(shè)備復(fù)雜，但實(shí)時(shí)性好，只需單向信道。 數(shù)據(jù)通信中使用更多的還是ARQ差錯(cuò)控制方式。FEC常用于沒有反向信道發(fā)送請(qǐng)求重發(fā)信息（

45、如單工傳輸）或重發(fā)不經(jīng)濟(jì)的場(chǎng)合（如衛(wèi)星傳輸）。差錯(cuò)糾正的基本技術(shù)自動(dòng)請(qǐng)求重發(fā) (ARQ , Automa理論上，自動(dòng)糾正每一個(gè)二進(jìn)制代碼的傳輸差錯(cuò)是可以做到的。但糾錯(cuò)碼比檢錯(cuò)碼復(fù)雜得多，而且需要更多的冗余位。用于多位或突發(fā)差錯(cuò)糾錯(cuò)的位數(shù)太大的，以致大部分情況下，將使編碼效率低到不可接受的程度。為此，大部分糾錯(cuò)碼只限于處理1位、2位或3位差錯(cuò)。在數(shù)據(jù)通信中，最常用的糾錯(cuò)碼是所謂“漢明碼”(Hamming Code），是貝爾實(shí)驗(yàn)室的科學(xué)家R.W.Hamming 于1950年提出的，主要用來糾正1位差錯(cuò)。糾錯(cuò)碼Error-correcting Code理論上，自動(dòng)糾正每一個(gè)二進(jìn)制代碼的傳輸差錯(cuò)是可以

46、做到的。但糾1位差錯(cuò)的糾錯(cuò)Single-bit Error Correction奇偶校驗(yàn)可以檢測(cè)出1位差錯(cuò)的情況，方法是加上一個(gè)冗余的奇校驗(yàn)位或偶校驗(yàn)位。糾錯(cuò)則需確定其中哪位有差錯(cuò)。如果要確定一個(gè)ASCII字符（7位）中的某位差錯(cuò)，此時(shí)需要區(qū)別8種情況：沒差錯(cuò)，第1位錯(cuò)，第2位錯(cuò)，第7位錯(cuò)。于是，需要3個(gè)冗余位來表示8種不同的狀態(tài)（000 -111）。實(shí)際上，3位冗余是不夠的。因?yàn)?，冗余位本身也可能出現(xiàn)差錯(cuò)！1位差錯(cuò)的糾錯(cuò)Single-bit Error Corre糾錯(cuò)碼Error Correction糾錯(cuò)碼Error Correction冗余位Redundancy Bits如何計(jì)算為m位數(shù)據(jù)

47、糾錯(cuò)時(shí)所需的冗余位數(shù) r 呢? 此時(shí)數(shù)據(jù)傳輸?shù)目偽粩?shù)是m+r，且要求 r必須能夠至少表示 m+r+1 種狀態(tài)。其中，一種狀態(tài)表示無差錯(cuò)，m+r 種狀態(tài)分別表示在 m+r 位每個(gè)位置上發(fā)生的差錯(cuò)。由于r 位二進(jìn)制數(shù)可以表示2r種不同的狀態(tài),所以，2r必須大于或等于 m+r+1。 2 r m+r+1 如果m=7（ASCII代碼），則能滿足上式的最小 r 值是4。因?yàn)椋?24 7+4+1冗余位Redundancy Bits如何計(jì)算為m位數(shù)據(jù)糾錯(cuò)數(shù)據(jù)位數(shù) m 與冗余位數(shù) r 的關(guān)系 下表為一些可能的 m 值及其對(duì)應(yīng)的 r 值。數(shù)據(jù)位數(shù) m 與冗余位數(shù) r 的關(guān)系 下表為一些可能的 m 糾錯(cuò)原理冗余位的

48、定位 漢明碼可用于任何長(zhǎng)度的數(shù)據(jù)塊，并利用了上面討論的數(shù)據(jù)位數(shù)和冗余位數(shù)的關(guān)系。例如，一個(gè)7位ASCII碼要求4個(gè)冗余位，它們可以附加在數(shù)據(jù)位的后面，亦可散布在數(shù)據(jù)位之中。下圖中，各冗余位處于第1、2、4、8位（2的n次方處），分別用r1，r2，r4，r8表示。糾錯(cuò)原理冗余位的定位確定冗余位的位置在漢明碼中，每一個(gè)r位都是一組數(shù)據(jù)位的奇偶校驗(yàn)碼。用于計(jì)算7數(shù)據(jù)位4個(gè)r值（奇偶校驗(yàn)碼）的方案是： r1 : 第 1，3，5，7，9，11 位 r2 : 第 2，3，6，7，10，11 位 r3 : 第 4，5，6，7 位 r4 : 第 8，9，10，11 位確定冗余位的位置在漢明碼中，每一個(gè)r位都是

49、一組數(shù)據(jù)位的奇偶校r1和r2值的計(jì)算r1和r2值的計(jì)算r4和r8值的計(jì)算r4和r8值的計(jì)算 糾錯(cuò)碼的計(jì)算為了搞清楚這種技術(shù)后面的竅門，不妨看看每一數(shù)位的位置號(hào)（用二進(jìn)制表示）。r1位使用的是所有位置號(hào)右側(cè)為1開頭的數(shù)位。r2使用的是所有位置號(hào)第2位為1的數(shù)位，以此類推。 糾錯(cuò)碼的計(jì)算為了搞清楚這種技術(shù)后面的竅門，不妨看看每一數(shù)位示例：各r位值的計(jì)算假設(shè)使用偶校驗(yàn)。示例：各r位值的計(jì)算假設(shè)使用偶校驗(yàn)。假設(shè)上述數(shù)據(jù)發(fā)送后，接收端收到的:10010100101（第7位差錯(cuò)）。 此時(shí)接收端取出接收結(jié)果，并使用與發(fā)送端相同的方法計(jì)算出一組新的奇偶校驗(yàn)碼。然后將這些奇偶校驗(yàn)碼按r的順序（r8,r4,r2,

50、r1）組成一個(gè)二進(jìn)制數(shù)。本例中，組成的二進(jìn)制數(shù)是0111（十進(jìn)制數(shù)7），這就是準(zhǔn)確的差錯(cuò)位置。一旦找出差錯(cuò)位，接收端即可將該位的值反轉(zhuǎn)，以糾正差錯(cuò)。檢錯(cuò)與糾錯(cuò)1假設(shè)上述數(shù)據(jù)發(fā)送后，接收端收到的:10010100101檢錯(cuò)確定校驗(yàn)關(guān)系假設(shè)要傳輸?shù)男畔⑽籯=4，要構(gòu)造海明碼,必須滿足上述不等式2rm+r+1，則有r3,確定校驗(yàn)關(guān)系假設(shè)要傳輸?shù)男畔⑽籯=4，要構(gòu)造海明碼,必須滿足將每個(gè)信息位的位置寫成用2的冪次之和的形式，即 7=22+21+20 6=22+21 5=22+20 3=21+20將每個(gè)信息位的位置寫成用2的冪次之和的形式，即 從上式可得，I4要參與r2,r1和r0的生成，I3參與r2和

51、r1的生成，I2參與r2,r0的生成，I1參與r1和r0的生成。即r2和I4， I3， I2構(gòu)成偶校驗(yàn)；r1和I4， I3， I1構(gòu)成偶校驗(yàn)； r0和I4， I2， I1構(gòu)成校驗(yàn)；于是有以下公式： r2=I4+I3+I2r1=I4+I3+I1r0=I4+I2+I1于是，接收端使用以下關(guān)系式對(duì)這三個(gè)偶校驗(yàn)關(guān)系進(jìn)行驗(yàn)證：s2=r2+I4+I3+I2 s1=r1+I4+I3+I1 s0=r0+I4+I2+I1其中s2，s1，s0稱為校正因子。若沒有錯(cuò)，三個(gè)校正因子都為0，若不全為0，則有錯(cuò)誤發(fā)生，錯(cuò)誤的位置在S=s2s1s0處，將該位取反即得到正確的數(shù)據(jù)。 從上式可得，I4要參與r2,r1和r0的生

52、成，3.6 數(shù)據(jù)鏈路層協(xié)議3.6 數(shù)據(jù)鏈路層協(xié)議3.6 因特網(wǎng)的點(diǎn)對(duì)點(diǎn)協(xié)議 PPP3.6.1 PPP 協(xié)議的工作原理現(xiàn)在全世界使用得最多的數(shù)據(jù)鏈路層協(xié)議是點(diǎn)對(duì)點(diǎn)協(xié)議 PPP (Point-to-Point Protocol)。用戶使用撥號(hào)電話線接入因特網(wǎng)時(shí)，一般都是使用 PPP 協(xié)議。 3.6 因特網(wǎng)的點(diǎn)對(duì)點(diǎn)協(xié)議 PPP3.6.1 PPP 用戶撥號(hào)入網(wǎng)的示意圖 路由器調(diào)制解調(diào)器調(diào)制解調(diào)器因特網(wǎng)服務(wù)提供者(ISP)用戶家庭撥號(hào)電話線 使用 TCP/IP 的 PPP 連接使用 TCP/IP 的 客戶進(jìn)程路由選擇 進(jìn)程至因特網(wǎng)PC 機(jī)用戶撥號(hào)入網(wǎng)的示意圖 路由器調(diào)制解調(diào)器調(diào)制解調(diào)器因特網(wǎng)服務(wù)提一個(gè)發(fā)

53、送方、一個(gè)接收方、一段鏈路：比廣播鏈路容易處理:無媒體訪問控制不需要明確的MAC編址如：撥號(hào)鏈路、ISDN鏈路PPP (Point to point protocol), 提供了一種在點(diǎn)對(duì)點(diǎn)的鏈路上封裝多協(xié)議數(shù)據(jù)報(bào)（IP、IPX和AppleTalk）的標(biāo)準(zhǔn)方法。協(xié)議常用于家庭用戶與ISP通過撥號(hào)建立連接 時(shí)使用的數(shù)據(jù)鏈路層協(xié)議。 PPP協(xié)議介紹一個(gè)發(fā)送方、一個(gè)接收方、一段鏈路：比廣播鏈路容易處理: PPP協(xié)議的功能能夠控制數(shù)據(jù)鏈路的建立；允許多個(gè)PPP物理連接綁定在一起作為一條單獨(dú)的邏輯連接。支持多種網(wǎng)絡(luò)層協(xié)議(IP 、IPX 和AppleTalk) AppleTalk)；可運(yùn)行在多種類型的鏈路上（串行/并行，同 步/異步能夠有效進(jìn)行錯(cuò)誤檢測(cè)（CRC）；支持驗(yàn)證（PAP,CHAP）有協(xié)商選項(xiàng)，能夠?qū)W(wǎng)絡(luò)層的地址和數(shù)據(jù)壓縮 等進(jìn)行協(xié)商。 PPP協(xié)議的功能能夠控制數(shù)據(jù)鏈路的建立；PPP 協(xié)議 1992 年制訂了 PPP 協(xié)議。經(jīng)過 1993 年和 1994 年的修訂，現(xiàn)在的 PPP 協(xié)議已成為因特網(wǎng)的正式標(biāo)準(zhǔn)RFC 1661。 PPP協(xié)議有三個(gè)組成部分 一個(gè)將 IP 數(shù)據(jù)報(bào)封裝到串行鏈路的方法。鏈路控制協(xié)議 LCP (Link Control Protocol)。網(wǎng)絡(luò)控制協(xié)議 NCP (Network Control Protocol)。 P