第2講_協(xié)議設(shè)計(差錯控制技術(shù))

1、2022-2-2差錯控制技術(shù)2-1 網(wǎng)網(wǎng) 絡(luò)絡(luò) 協(xié)協(xié) 議議 工工 程程 第第 2 講：協(xié)議設(shè)計講：協(xié)議設(shè)計2022-2-2差錯控制技術(shù)2-2第第 2 講：協(xié)議設(shè)計講：協(xié)議設(shè)計2.1 協(xié)議模型協(xié)議模型2.2 協(xié)議設(shè)計的基本內(nèi)容協(xié)議設(shè)計的基本內(nèi)容2.3 協(xié)議設(shè)計方法協(xié)議設(shè)計方法2.4 差錯控制技術(shù)差錯控制技術(shù)2.5 流量控制技術(shù)流量控制技術(shù)2022-2-2差錯控制技術(shù)2-3差錯控制技術(shù)：內(nèi)容提綱差錯控制技術(shù)：內(nèi)容提綱2.4.1 差錯類型差錯類型2.4.2 差錯檢測技術(shù)差錯檢測技術(shù)2.4.3 差錯控制技術(shù)差錯控制技術(shù)2.4.4 差錯控制與層次的關(guān)系差錯控制與層次的關(guān)系2022-2-2差錯控制技術(shù)2-

2、4差錯控制：概述差錯控制：概述v網(wǎng)絡(luò)通信的目的是通過網(wǎng)絡(luò)在應(yīng)用進(jìn)程間傳輸網(wǎng)絡(luò)通信的目的是通過網(wǎng)絡(luò)在應(yīng)用進(jìn)程間傳輸信息，任何數(shù)據(jù)丟失或損壞都將對通信雙方產(chǎn)信息，任何數(shù)據(jù)丟失或損壞都將對通信雙方產(chǎn)生重要的影響。生重要的影響。 v差錯控制差錯控制是指在網(wǎng)絡(luò)通信過程中發(fā)現(xiàn)是指在網(wǎng)絡(luò)通信過程中發(fā)現(xiàn)(檢測檢測)差差錯，并采取措施糾正，把差錯限制在錯，并采取措施糾正，把差錯限制在所允許所允許的的盡可能小的范圍內(nèi)的技術(shù)和方法。盡可能小的范圍內(nèi)的技術(shù)和方法。 v差錯控制的目的是為了差錯控制的目的是為了提高數(shù)據(jù)傳輸?shù)目煽啃蕴岣邤?shù)據(jù)傳輸?shù)目煽啃?，但是任何一種差錯控制方法均但是任何一種差錯控制方法均不可能糾正所有不可

3、能糾正所有可能出現(xiàn)的差錯?？赡艹霈F(xiàn)的差錯。 2022-2-2差錯控制技術(shù)2-5差錯控制：概述差錯控制：概述 (續(xù)續(xù))v差錯控制主要有兩種途徑：差錯控制主要有兩種途徑：硬件途徑硬件途徑。這種途徑選用高可靠性的設(shè)備和傳輸媒。這種途徑選用高可靠性的設(shè)備和傳輸媒體體(如光纖如光纖)及相應(yīng)的輔助措施及相應(yīng)的輔助措施(如如屏蔽屏蔽)來提高傳輸?shù)膩硖岣邆鬏數(shù)目煽啃??？煽啃浴?軟件途徑軟件途徑。這種途徑通過通信協(xié)議來實現(xiàn)差錯控制。這種途徑通過通信協(xié)議來實現(xiàn)差錯控制。在通信協(xié)議中，通過差錯控制編碼在通信協(xié)議中，通過差錯控制編碼(包括檢錯碼和前包括檢錯碼和前向糾錯碼向糾錯碼)實現(xiàn)的差錯檢測、肯定確認(rèn)、超時重傳、實

4、現(xiàn)的差錯檢測、肯定確認(rèn)、超時重傳、否認(rèn)重傳、選擇重傳等措施來實現(xiàn)差錯控制。否認(rèn)重傳、選擇重傳等措施來實現(xiàn)差錯控制。 2022-2-2差錯控制技術(shù)2-6差錯類型差錯類型v根據(jù)差錯發(fā)生的位置，分為三種類型：根據(jù)差錯發(fā)生的位置，分為三種類型：通信鏈路差錯通信鏈路差錯指有關(guān)通信鏈路上故障、干擾造成的傳輸錯誤問題指有關(guān)通信鏈路上故障、干擾造成的傳輸錯誤問題 路由差錯路由差錯 有關(guān)傳輸報文在路由過程中阻塞、丟失、死鎖以及有關(guān)傳輸報文在路由過程中阻塞、丟失、死鎖以及報文順序錯而造成傳輸?shù)牟铄e問題報文順序錯而造成傳輸?shù)牟铄e問題通信結(jié)點差錯通信結(jié)點差錯 有關(guān)通信中某結(jié)點的資源限制、環(huán)境條件或文本不有關(guān)通信中某結(jié)

5、點的資源限制、環(huán)境條件或文本不符、協(xié)議同步關(guān)系以及操作錯誤、硬件故障等，可符、協(xié)議同步關(guān)系以及操作錯誤、硬件故障等，可能影響通信鏈路的正確聯(lián)接或正常通常的錯誤中斷能影響通信鏈路的正確聯(lián)接或正常通常的錯誤中斷等問題等問題 2022-2-2差錯控制技術(shù)2-7差錯類型（續(xù)）差錯類型（續(xù)）v根據(jù)差錯的表現(xiàn)形式根據(jù)差錯的表現(xiàn)形式 ，可分為四類（）：，可分為四類（）：失真失真(Distortion) 定義：被傳送信息中的一個或多個比特發(fā)生了改定義：被傳送信息中的一個或多個比特發(fā)生了改變，或者被傳送的信息中插入了一些新的信息變，或者被傳送的信息中插入了一些新的信息(這種情況也稱為這種情況也稱為“插入插入(I

6、nsertion)”) 主要原因：主要原因：網(wǎng)絡(luò)中物理干擾網(wǎng)絡(luò)中物理干擾(如線路噪聲如線路噪聲)發(fā)送者和接收者之間的失步發(fā)送者和接收者之間的失步入侵者的故意攻擊入侵者的故意攻擊結(jié)點中的硬件故障和軟件差錯等結(jié)點中的硬件故障和軟件差錯等 解決方法：各種校驗方法來檢測解決方法：各種校驗方法來檢測 2022-2-2差錯控制技術(shù)2-8差錯類型（續(xù)）差錯類型（續(xù)）v根據(jù)差錯的表現(xiàn)形式根據(jù)差錯的表現(xiàn)形式 ，可分為四類，可分為四類（）（）丟失丟失(Deletion) 定義：網(wǎng)絡(luò)將被傳輸?shù)男畔G棄定義：網(wǎng)絡(luò)將被傳輸?shù)男畔G棄 主要原因：主要原因：噪聲脈沖對某個幀的破壞程度太大，以致接收方不知噪聲脈沖對某個幀的破

7、壞程度太大，以致接收方不知道這個幀已經(jīng)被傳輸；道這個幀已經(jīng)被傳輸；發(fā)送者和接收者之間的失步；發(fā)送者和接收者之間的失步；流量控制或擁塞控制措施不當(dāng)時因資源不夠而被中間流量控制或擁塞控制措施不當(dāng)時因資源不夠而被中間結(jié)點或接收者丟棄；結(jié)點或接收者丟棄；因接收者檢測到信息被損壞而主動將其丟棄等因接收者檢測到信息被損壞而主動將其丟棄等 解決方法：用序號、計時器和確認(rèn)共同檢測，通解決方法：用序號、計時器和確認(rèn)共同檢測，通過重傳的方法來糾正錯誤過重傳的方法來糾正錯誤 2022-2-2差錯控制技術(shù)2-9差錯類型（續(xù)）差錯類型（續(xù)）v根據(jù)差錯的表現(xiàn)形式根據(jù)差錯的表現(xiàn)形式 ，可分為四類，可分為四類（）（）重復(fù)重復(fù)

8、(Duplication) 定義：多次收到同樣的信息定義：多次收到同樣的信息 主要原因：主要原因：是差錯控制機(jī)制本身，如果發(fā)送方錯誤地認(rèn)為數(shù)據(jù)丟是差錯控制機(jī)制本身，如果發(fā)送方錯誤地認(rèn)為數(shù)據(jù)丟失了，因而重傳了它，就可能造成接收方收到重復(fù)的失了，因而重傳了它，就可能造成接收方收到重復(fù)的信息信息 路由選擇機(jī)制引起的重復(fù)幀，如使用基于擴(kuò)散的路由路由選擇機(jī)制引起的重復(fù)幀，如使用基于擴(kuò)散的路由選擇策略選擇策略(如洪泛法如洪泛法) 解決方法：用序號來檢測這種錯誤，用丟棄重復(fù)解決方法：用序號來檢測這種錯誤，用丟棄重復(fù)的數(shù)據(jù)來糾正錯誤。的數(shù)據(jù)來糾正錯誤。2022-2-2差錯控制技術(shù)2-10差錯類型（續(xù)）差錯類型

9、（續(xù)）v根據(jù)差錯的表現(xiàn)形式根據(jù)差錯的表現(xiàn)形式 ，可分為四類，可分為四類（）（）失序失序(Reordering) 定義：定義：數(shù)據(jù)到達(dá)接收方的順序與發(fā)送方發(fā)送的順數(shù)據(jù)到達(dá)接收方的順序與發(fā)送方發(fā)送的順序不一致序不一致 主要原因：主要原因：采用自適應(yīng)的路由選擇策略，分組在網(wǎng)絡(luò)中傳送時可采用自適應(yīng)的路由選擇策略，分組在網(wǎng)絡(luò)中傳送時可能有多條路由而引起的后發(fā)先到能有多條路由而引起的后發(fā)先到 重傳丟失的數(shù)據(jù)也可能導(dǎo)致數(shù)據(jù)不按序到達(dá)重傳丟失的數(shù)據(jù)也可能導(dǎo)致數(shù)據(jù)不按序到達(dá)解決方法：解決方法：把亂序的數(shù)據(jù)先存儲下來，使得以后能把它們存放在把亂序的數(shù)據(jù)先存儲下來，使得以后能把它們存放在正確的位置上；正確的位置上；

10、丟棄亂序的數(shù)據(jù)，然后按數(shù)據(jù)丟失來處理丟棄亂序的數(shù)據(jù)，然后按數(shù)據(jù)丟失來處理 。2022-2-2差錯控制技術(shù)2-11第第 講：內(nèi)容提綱講：內(nèi)容提綱2.4.1 差錯類型差錯類型2.4.2 差錯檢測技術(shù)差錯檢測技術(shù)2.4.3 差錯控制技術(shù)差錯控制技術(shù)2.4.4 差錯控制與層次的關(guān)系差錯控制與層次的關(guān)系2022-2-2差錯控制技術(shù)2-12差錯檢測技術(shù)：概述差錯檢測技術(shù)：概述v檢查收到的數(shù)據(jù)是否正確的方法和技術(shù)檢查收到的數(shù)據(jù)是否正確的方法和技術(shù)通常情況下，我們所說的差錯檢測是指檢測收到的通常情況下，我們所說的差錯檢測是指檢測收到的數(shù)據(jù)是否被損壞，而不包括對數(shù)據(jù)丟失、重復(fù)、亂數(shù)據(jù)是否被損壞，而不包括對數(shù)據(jù)丟

11、失、重復(fù)、亂序等差錯的檢測序等差錯的檢測在這樣的前提下，差錯檢測技術(shù)所采取的方法一般在這樣的前提下，差錯檢測技術(shù)所采取的方法一般是各種檢驗和技術(shù)，如奇偶檢驗，循環(huán)冗余檢驗等是各種檢驗和技術(shù)，如奇偶檢驗，循環(huán)冗余檢驗等, ,本節(jié)主要介紹這方面的技術(shù)本節(jié)主要介紹這方面的技術(shù)v差錯檢測是差錯控制的基礎(chǔ)差錯檢測是差錯控制的基礎(chǔ) 2022-2-2差錯控制技術(shù)2-13差錯檢測技術(shù)：原理差錯檢測技術(shù)：原理E, E：差錯檢驗碼：差錯檢驗碼對比對比接收器接收器數(shù)據(jù)數(shù)據(jù) EE = f(Data)數(shù)據(jù)數(shù)據(jù) EE = f(Data)發(fā)送器發(fā)送器數(shù)據(jù)數(shù)據(jù)f: 差錯檢驗函數(shù)差錯檢驗函數(shù)問題：問題：為什么總是將檢驗碼放在幀

12、的尾部？為什么總是將檢驗碼放在幀的尾部？2022-2-2差錯控制技術(shù)2-14差錯檢測技術(shù)差錯檢測技術(shù)一、奇偶檢驗一、奇偶檢驗(Parity Check) 2022-2-2差錯控制技術(shù)2-15奇偶檢驗奇偶檢驗v奇偶檢驗在數(shù)據(jù)的尾部附加上奇偶檢驗位，使奇偶檢驗在數(shù)據(jù)的尾部附加上奇偶檢驗位，使得碼字中比特得碼字中比特“1”的個數(shù)保持為奇數(shù)的個數(shù)保持為奇數(shù)(奇檢驗奇檢驗)或偶數(shù)或偶數(shù)(偶檢驗偶檢驗) v被廣泛用于諸如計算機(jī)的異步串行口通信中被廣泛用于諸如計算機(jī)的異步串行口通信中v三種類型：三種類型：垂直冗余檢驗垂直冗余檢驗(VRC：Vertical Redundancy Checking)縱向冗余檢驗

13、縱向冗余檢驗(LRC：Longitudinal Redundancy Checking)縱向垂直冗余檢驗縱向垂直冗余檢驗 2022-2-2差錯控制技術(shù)2-16奇偶檢驗：奇偶檢驗：垂直冗余檢驗v 原理：原理：將整個發(fā)送的信息分為長度為將整個發(fā)送的信息分為長度為p位的若干段，如位的若干段，如q段，段，每段后面按每段后面按“1”的個數(shù)為奇數(shù)或偶數(shù)的規(guī)律加上一位奇的個數(shù)為奇數(shù)或偶數(shù)的規(guī)律加上一位奇偶位，其有偶位，其有(p * q) 個信息位，每段由個信息位，每段由p位構(gòu)成，共位構(gòu)成，共q列列(段段)v 通常通常p值等于一個字符的長度，因此有時也將垂直冗余檢值等于一個字符的長度，因此有時也將垂直冗余檢驗

14、稱為驗稱為字符奇偶檢驗字符奇偶檢驗。v 可以用硬件或軟件方法來實現(xiàn)連續(xù)半加運算，且可以邊發(fā)可以用硬件或軟件方法來實現(xiàn)連續(xù)半加運算，且可以邊發(fā)送邊產(chǎn)生檢驗位，并插入發(fā)送。在接收時邊接收邊進(jìn)行檢送邊產(chǎn)生檢驗位，并插入發(fā)送。在接收時邊接收邊進(jìn)行檢驗并除去檢驗位驗并除去檢驗位v 能檢測出每列中的能檢測出每列中的所有奇數(shù)個位的錯所有奇數(shù)個位的錯，但檢測不出，但檢測不出偶數(shù)個偶數(shù)個位的錯位的錯。對于突發(fā)錯誤而言，奇數(shù)位錯與偶數(shù)位錯的概率。對于突發(fā)錯誤而言，奇數(shù)位錯與偶數(shù)位錯的概率差不多是相等的，因而對差錯的漏檢率接近于差不多是相等的，因而對差錯的漏檢率接近于50%50%。 2022-2-2差錯控制技術(shù)2-

15、17奇偶檢驗：奇偶檢驗：垂直冗余檢驗D = 1 0 0 0 1 0 0 0A = 1 0 0 0 0 0 1 0T = 1 0 1 0 1 0 0 1A = 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1垂直奇偶校驗縱向奇偶校驗2022-2-2差錯控制技術(shù)2-18奇偶檢驗：奇偶檢驗：縱向冗余檢驗v原理：原理：對各個信息段的相應(yīng)位水平進(jìn)行編碼，對各個信息段的相應(yīng)位水平進(jìn)行編碼，對應(yīng)每一行產(chǎn)生一個奇偶檢驗位。這種附加的對應(yīng)每一行產(chǎn)生一個奇偶檢驗位。這種附加的水平基礎(chǔ)上檢驗字符的技術(shù)，使用了和垂直冗水平基礎(chǔ)上檢驗字符的技術(shù)，使用了和垂直冗余檢驗同樣的奇偶性。余檢驗同樣的奇偶性。 v漏

16、檢率要比垂直冗余檢驗低。不但可以檢測出漏檢率要比垂直冗余檢驗低。不但可以檢測出各段同一位上的奇數(shù)位錯，而且可以檢測出突各段同一位上的奇數(shù)位錯，而且可以檢測出突發(fā)長度小于等于發(fā)長度小于等于p的所有突發(fā)錯誤（的所有突發(fā)錯誤（Why?Why?）因為可以安排發(fā)送順序使得因為可以安排發(fā)送順序使得在可見突發(fā)長度小于等于在可見突發(fā)長度小于等于p的突發(fā)錯誤必然分布在不同的突發(fā)錯誤必然分布在不同行中，每行一位，所以可以行中，每行一位，所以可以檢測出來檢測出來 2022-2-2差錯控制技術(shù)2-19奇偶檢驗：奇偶檢驗：縱向冗余檢驗D = 1 0 0 0 1 0 0 0A = 1 0 0 0 0 0 1 0T = 1

17、 0 1 0 1 0 0 1A = 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1垂直奇偶校驗縱向奇偶校驗2022-2-2差錯控制技術(shù)2-20奇偶檢驗：奇偶檢驗：縱向冗余檢驗v實現(xiàn)復(fù)雜：實現(xiàn)時不能在發(fā)送過程中邊產(chǎn)生奇實現(xiàn)復(fù)雜：實現(xiàn)時不能在發(fā)送過程中邊產(chǎn)生奇偶檢驗位，邊插入發(fā)送，而必須要等到要發(fā)送偶檢驗位，邊插入發(fā)送，而必須要等到要發(fā)送的完整信息塊到齊后，才能產(chǎn)生檢驗位，因而的完整信息塊到齊后，才能產(chǎn)生檢驗位，因而一定要使用記憶寄存器。一定要使用記憶寄存器。2022-2-2差錯控制技術(shù)2-21奇偶檢驗：奇偶檢驗：垂直縱向冗余檢驗v 同時進(jìn)行垂直冗余檢驗和縱向冗余檢驗同時進(jìn)行垂直冗

18、余檢驗和縱向冗余檢驗v 能檢測出所有能檢測出所有3位或位或3位以下的錯誤位以下的錯誤(因為此時至少在某因為此時至少在某一行或某一列上為一位錯一行或某一列上為一位錯)、奇數(shù)位錯奇數(shù)位錯、突發(fā)長度小于突發(fā)長度小于等于等于(p+1)的突發(fā)錯的突發(fā)錯以及很大以及很大一部分偶數(shù)位錯一部分偶數(shù)位錯。v 還可以還可以糾正部分差錯，糾正部分差錯，例如僅在某一行和某一列中有例如僅在某一行和某一列中有奇數(shù)位錯時，就可以確定錯誤的位置就在該行和該列奇數(shù)位錯時，就可以確定錯誤的位置就在該行和該列的交叉處，從而得以糾正。的交叉處，從而得以糾正。 v 此外，當(dāng)某一行出現(xiàn)偶數(shù)個錯時，雖然縱向冗余檢驗此外，當(dāng)某一行出現(xiàn)偶數(shù)個

19、錯時，雖然縱向冗余檢驗不能發(fā)現(xiàn)，但在其垂直冗余檢驗中還是可以被檢測出不能發(fā)現(xiàn)，但在其垂直冗余檢驗中還是可以被檢測出來。只有當(dāng)有錯的各行和各列中出錯位數(shù)均為偶數(shù)時，來。只有當(dāng)有錯的各行和各列中出錯位數(shù)均為偶數(shù)時，才不可能被發(fā)現(xiàn)。才不可能被發(fā)現(xiàn)。 2022-2-2差錯控制技術(shù)2-22奇偶檢驗：奇偶檢驗：垂直縱向冗余檢驗D = 1 0 0 0 1 0 0 0A = 1 0 0 0 0 0 1 0T = 1 0 1 0 1 0 0 1A = 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1垂直奇偶校驗縱向奇偶校驗2022-2-2差錯控制技術(shù)2-23奇偶檢驗：小結(jié)奇偶檢驗：小結(jié)v使用奇偶檢

20、驗并不是十分安全，因為噪聲脈沖使用奇偶檢驗并不是十分安全，因為噪聲脈沖的長度經(jīng)常足以破壞一個以上的比特，特別是的長度經(jīng)常足以破壞一個以上的比特，特別是在數(shù)據(jù)率較高的情況下。在數(shù)據(jù)率較高的情況下。 v低速率的串行口通信協(xié)議，如低速率的串行口通信協(xié)議，如RS232接口，常接口，常采用奇偶檢驗方法來檢測錯誤采用奇偶檢驗方法來檢測錯誤。v一般情況下，垂直冗余檢驗主要用于異步傳輸，一般情況下，垂直冗余檢驗主要用于異步傳輸，且一列對應(yīng)一個字符。且一列對應(yīng)一個字符。v而縱向冗余檢驗則常用于同步傳輸，通常是把而縱向冗余檢驗則常用于同步傳輸，通常是把一串字符作為一個塊傳送，字符之間沒有時間一串字符作為一個塊傳送

21、，字符之間沒有時間間隔，產(chǎn)生一個附加的字符跟在塊的后面。間隔，產(chǎn)生一個附加的字符跟在塊的后面。 2022-2-2差錯控制技術(shù)2-24差錯檢測技術(shù)差錯檢測技術(shù)二、二、循環(huán)冗余檢驗循環(huán)冗余檢驗(CRC) 2022-2-2差錯控制技術(shù)2-25CRC檢驗：原理檢驗：原理 1101010110Q 商 除數(shù)P110101 1010001101000002nM 被除數(shù) 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110R 余數(shù)q 數(shù)據(jù)：M=1010001101q 除數(shù)P（生成多項式）= X5+X

22、4+X2+1q 模 2 運算：加法不進(jìn)位，減法 和加法是一樣的，例如： 1111 + 1010 = 0101q 冗余碼稱為幀檢驗序列 FCSq 接收端運算：XnM(X) + R(X) / P(X) = Q(X)q 有錯：R(X) !=0q 問題：R(X) 等于0是否就不定沒有錯嗎？q 常見多項式：o CRC-16 = X16+X15+X2+1o CRC-CCITT = X16+X12+X5+1o CRC-32 = X32+X26+X23+ X22+X16+X12+ X11+X10+X8+ X7+X5+X4+ X2+X+12022-2-2差錯控制技術(shù)2-26CRC檢驗：檢錯率檢驗：檢錯率vCRC

23、檢驗的漏檢率是比較低的。檢驗的漏檢率是比較低的。CRC-CCITT檢驗可以檢測出所有的雙比特差錯，長度為檢驗可以檢測出所有的雙比特差錯，長度為17比特的數(shù)據(jù)中的比特的數(shù)據(jù)中的99.997%的突發(fā)錯誤，長度大的突發(fā)錯誤，長度大于于17比特的數(shù)據(jù)中的比特的數(shù)據(jù)中的99.998%的突發(fā)錯誤。的突發(fā)錯誤。v采用采用CRCCRC檢驗的著名協(xié)議：檢驗的著名協(xié)議：數(shù)據(jù)鏈路層協(xié)議數(shù)據(jù)鏈路層協(xié)議HDLCHDLC采用的就是采用的就是CRC-CCITTCRC-CCITT檢驗。檢驗。IBMIBM的的BisyncBisync協(xié)議中采用的是協(xié)議中采用的是CRC-16CRC-16檢驗檢驗以太網(wǎng)幀和光纖分布式數(shù)據(jù)接口標(biāo)準(zhǔn)以太

24、網(wǎng)幀和光纖分布式數(shù)據(jù)接口標(biāo)準(zhǔn)(FDDI)(FDDI)中則采中則采用的是用的是CRC-32CRC-32檢驗。檢驗。 2022-2-2差錯控制技術(shù)2-27CRC檢驗：實現(xiàn)檢驗：實現(xiàn)vCRC檢驗的編碼需要花費不少的時間，因此計檢驗的編碼需要花費不少的時間，因此計算檢驗和可能會降低協(xié)議的性能。算檢驗和可能會降低協(xié)議的性能。v為了提高協(xié)議的性能，通常采用為了提高協(xié)議的性能，通常采用硬件方法硬件方法(移移位寄存器位寄存器)或或查檢驗和表查檢驗和表(預(yù)先計算出檢驗和放預(yù)先計算出檢驗和放在表中，使用時查表即可在表中，使用時查表即可)的軟件方法來實現(xiàn)。的軟件方法來實現(xiàn)。 2022-2-2差錯控制技術(shù)2-28CR

25、C檢驗：源代碼檢驗：源代碼vAT&T Bell實驗室的實驗室的Don Mitchell所寫的一個計所寫的一個計算算CRC檢驗和，并生成檢驗和表的程序檢驗和，并生成檢驗和表的程序Crc_init.c: Crc_init.c: 創(chuàng)建檢驗和表創(chuàng)建檢驗和表(crc_table)(crc_table)Checksum(s, n)Checksum(s, n)查表生成檢驗和。輸入?yún)?shù)查表生成檢驗和。輸入?yún)?shù)s s為被為被檢驗的數(shù)據(jù)，檢驗的數(shù)據(jù)，n n為數(shù)據(jù)長度為數(shù)據(jù)長度( (單位為字節(jié)單位為字節(jié)) )。函數(shù)返。函數(shù)返回值為被檢驗的數(shù)據(jù)的檢驗和?；刂禐楸粰z驗的數(shù)據(jù)的檢驗和。 2022-2-2差錯控制技

26、術(shù)2-29crc_init.cmain(argc, argv) int argc; char *argv; unsigned long crc, poly; int n, i; sscanf(argv1, “%lo”,&poly); if (poly & 0 xffff0000) fprintf(stderr, “polynomial is too largen”); exit(1); printf(“/*n * CRC 0 %on * /n”,poly); printf(“static unsigned short crc_table256 = n”;2022-2-2差錯控制

27、技術(shù)2-30crc_init.c (Cont.)for (n =0; n256; n+) crc = n; if (n% 8 = =0) printf(“ “); for ( i = 0; i =1; crc = poly; else crc =1; printf(“0 x%x, “,crc); if ( n &8 = = 7) printf (“n”); printf(“);nn”); exit(0); 2022-2-2差錯控制技術(shù)2-31crc_init.c: examplesv$ crc_init 05401 crc_12.h 創(chuàng)建基于創(chuàng)建基于CRC-12的檢驗和表，并保存在文件

28、的檢驗和表，并保存在文件crc_12.h中中 v$ crc_init 0120001 crc_16.h 創(chuàng)建基于創(chuàng)建基于CRC-16的檢驗和表，并保存在文件的檢驗和表，并保存在文件crc_16.h中中 v$ crc_init 0102010 crc_ccitt.h 創(chuàng)建基于創(chuàng)建基于CRC-CCITT的檢驗和表，并保存在文件的檢驗和表，并保存在文件crc_ccitt.h 中中2022-2-2差錯控制技術(shù)2-32Checksum(s,n): 源碼源碼unsigned short cksum(s,n) register unsigned char *s; register int n; regist

29、er unsigned int crc; for (crc = 0; n 0; n-) crc = crc_table(crc *s+) & 0 xff (crc 8); return crc;2022-2-2差錯控制技術(shù)2-33差錯檢測技術(shù)差錯檢測技術(shù)三、三、UUCP檢驗和檢驗和 2022-2-2差錯控制技術(shù)2-34UUCP檢驗和檢驗和vUNIX操作系統(tǒng)中的操作系統(tǒng)中的uucp應(yīng)用程序中的計算檢驗應(yīng)用程序中的計算檢驗和方法，與和方法，與CRC檢驗比較類似檢驗比較類似v比較簡單，有點類似于散列方法，其漏檢率比比較簡單，有點類似于散列方法，其漏檢率比CRCCRC要高一些，而且計算同樣的檢

30、驗和，它所花要高一些，而且計算同樣的檢驗和，它所花的時間比查表計算的時間比查表計算CRCCRC檢驗和的方法要多一些。檢驗和的方法要多一些。 2022-2-2差錯控制技術(shù)2-35UUCP檢驗和：源碼檢驗和：源碼cksum(s, n)cksum(s, n) register char register char * *s;s; register n; register n; register short sum; register short sum; register unsigned short t; register unsigned short t; register short x; r

31、egister short x; sum = -1; x = 0; sum = -1; x = 0; do do if (sum 0) sum =1; sum+ if (sum 0) sum =1; sum+ else sum = 1; else sum = 1; t = sum; sum += (unsigned) t = sum; sum += (unsigned) * *s+ & 0377; x += sumn;s+ & 0377; x += sumn; if (unsigned short) sum = t) sum = x; if (unsigned short) s

32、um 0); while (-n 0); return (sum); return (sum); 2022-2-2差錯控制技術(shù)2-36差錯檢測技術(shù)差錯檢測技術(shù)四、四、算術(shù)檢驗和算術(shù)檢驗和(Arithmetic Checksum) 2022-2-2差錯控制技術(shù)2-37算術(shù)檢驗和算術(shù)檢驗和v盡管可以通過前面介紹的查表的方法或特殊硬盡管可以通過前面介紹的查表的方法或特殊硬件的方法計算檢驗和來縮短處理時間件的方法計算檢驗和來縮短處理時間，但：，但：v對于允許一定程度的漏檢率的應(yīng)用場合，對于允許一定程度的漏檢率的應(yīng)用場合，可以可以采用比采用比CRC檢驗要簡單且又能夠發(fā)現(xiàn)比較嚴(yán)重檢驗要簡單且又能夠發(fā)現(xiàn)比較

33、嚴(yán)重的傳輸錯誤的方法來進(jìn)行差錯檢測。的傳輸錯誤的方法來進(jìn)行差錯檢測。vJohn Fletcher John Fletcher 在在19821982提出了這樣一種差錯檢提出了這樣一種差錯檢測方法，稱為測方法，稱為算術(shù)檢驗和算術(shù)檢驗和只需用到加法和取模操作，只需用到加法和取模操作，且算法特別簡單且算法特別簡單 2022-2-2差錯控制技術(shù)2-38Arithmetic ChecksumvError detection at the higher layer is usually done by ordinary arithmetic operations.This is simpler in sof

34、tware but somewhat less effective than a CRC.vStandard technique is to view packet as sequence of k numbers of n bits each, say x1, x2,., xk.vChecksum is then the n bit number x1+x2+.+xk using ordinary arithmetic with no carry.2022-2-2差錯控制技術(shù)2-39Arithmetic Checksum (Cont.)vAlternatively, checksum mig

35、ht be 2n bits; first n bits is (sum) x1+x2+.+xk and second n bits is (sum of sum) x1+2x2+3x3+.+kxk.vExample: In TCP, n=16, checksum is 16 bits and ones complement of the sum.vIn ISBN, the data are radix 10 digits, checksum is radix 11 digit (with 10 represented as X) and is (sum of sum of all digits

36、)/11.2022-2-2差錯控制技術(shù)2-40算術(shù)檢驗和：源碼算術(shù)檢驗和：源碼vISO的類的類4運輸協(xié)議運輸協(xié)議(TP4) 中的實現(xiàn)源代碼：中的實現(xiàn)源代碼： unsigned short cksum(s, n) register unsigned char *s; register int n; register int c0=0, c1=0; do c0 = (c0 + *s+) % 255; c1 = (c0 + c1) %255; while (-n 0); return (unsigned short) (c1 11 + 1 =12，而且編號而且編號1=1, 2=2, 3=1+2, 4

37、=4,5=1+4, 6=2+4, 7=1+2+4, 8=8, 9=1+8, 10=2+8, 11=1+2+8, 于是有：于是有： (1) (1) + (3) + (5) + (7) + (9) + (11) (2) (2) + (3) + (6) + (7) + (10) + (11)(4) (4) + (5) + (6) + (7) (8) (8) + (9) + (10) + (11) v 注意：在每個檢驗位的形成表達(dá)式中，除自身的編號外，注意：在每個檢驗位的形成表達(dá)式中，除自身的編號外，其余都是信息位的編號，因此只要信息位是確定的，檢其余都是信息位的編號，因此只要信息位是確定的，檢驗位也

38、可以唯一地確定。驗位也可以唯一地確定。 2022-2-2差錯控制技術(shù)2-51Hamming Code (Cont.)v 10個個7位位ASCII字符使用海明編碼形成的字符使用海明編碼形成的10位碼字，其中位碼字，其中數(shù)據(jù)位在數(shù)據(jù)位在3、5、6、7、9、10和和11位，編號為位，編號為1、2、4、8的位是檢驗位。的位是檢驗位。字符：字符：H，ASCII編碼：編碼：1001000 ，海明碼：，海明碼：00110010000 字符：字符：a， ASCII編碼：編碼：1100001 ，海明碼：，海明碼：10111001001 字符：字符：m，ASCII編碼：編碼：1101101 ，海明碼：，海明碼：1

39、1101010101 字符：字符：i， ASCII編碼：編碼：1101001 ，海明碼：，海明碼：01101011001 字符：字符：n， ASCII編碼：編碼：1101110 ，海明碼：，海明碼：01101010110 字符：字符：g， ASCII編碼：編碼：1100111 ，海明碼：，海明碼：01111001111 字符：字符：c， ASCII編碼：編碼：1100011 ，海明碼：，海明碼：11111000011 字符：字符：o， ASCII編碼：編碼：1101111 ，海明碼：，海明碼：10101011111 字符：字符：d， ASCII編碼：編碼：1100100 ，海明碼：，海明碼：1

40、1111001100 字符：字符：e， ASCII編碼：編碼：1100101 ，海明碼：，海明碼：00111000101 2022-2-2差錯控制技術(shù)2-52HammingCode (Cont.)v 當(dāng)一碼字到達(dá)時，接收方將計數(shù)器清當(dāng)一碼字到達(dá)時，接收方將計數(shù)器清0。 v 然后接收方檢測每個檢驗位然后接收方檢測每個檢驗位D(這里的這里的D是檢驗位的編是檢驗位的編號號)，看是否具有正確的奇偶性。，看是否具有正確的奇偶性。 如果第如果第D位奇偶性不對，則計數(shù)值加位奇偶性不對，則計數(shù)值加D， 若所有檢驗位被檢查過后，計數(shù)器值仍為若所有檢驗位被檢查過后，計數(shù)器值仍為0，這個碼字就作為，這個碼字就作為有

41、效碼字接受。有效碼字接受。 假如計數(shù)器值不為假如計數(shù)器值不為0，則該值就是出錯位的編者編號。，則該值就是出錯位的編者編號。 例如，若檢測位例如，若檢測位1、2和和8錯誤，則第錯誤，則第11位就變反，因為它是唯位就變反，因為它是唯一被第一被第1、2和和8位檢測的位。位檢測的位。 v 海明碼的信息余量很大海明碼的信息余量很大( (前面的例子：前面的例子：7+4)7+4)，因而編碼，因而編碼效率低。大大增加了數(shù)據(jù)通信的開銷效率低。大大增加了數(shù)據(jù)通信的開銷2022-2-2差錯控制技術(shù)2-53檢錯重傳與糾錯檢錯重傳與糾錯v一般使用檢錯重傳，特別是在數(shù)據(jù)鏈路層以上一般使用檢錯重傳，特別是在數(shù)據(jù)鏈路層以上的

42、各層協(xié)議。的各層協(xié)議。v在有些協(xié)議中，將檢錯碼和糾錯碼結(jié)合起來一在有些協(xié)議中，將檢錯碼和糾錯碼結(jié)合起來一起使用，增強(qiáng)差錯控制的能力，如起使用，增強(qiáng)差錯控制的能力，如ATM AAL1協(xié)議中的差錯檢測機(jī)制協(xié)議中的差錯檢測機(jī)制。2022-2-2差錯控制技術(shù)2-54差錯檢測技術(shù)差錯檢測技術(shù)七、七、關(guān)于被檢驗的數(shù)據(jù)的討論關(guān)于被檢驗的數(shù)據(jù)的討論 2022-2-2差錯控制技術(shù)2-55被保護(hù)對象的選擇被保護(hù)對象的選擇v有些協(xié)議中，是對整個數(shù)據(jù)單元有些協(xié)議中，是對整個數(shù)據(jù)單元(幀、分組、幀、分組、報文，或統(tǒng)稱為報文，或統(tǒng)稱為PDU)進(jìn)行檢驗和保護(hù)，進(jìn)行檢驗和保護(hù)，v而另一些協(xié)議則只需要對數(shù)據(jù)單元的首部而另一些協(xié)

43、議則只需要對數(shù)據(jù)單元的首部(控控制部分制部分)或首部中的某個字段進(jìn)行檢驗和保護(hù)?；蚴撞恐械哪硞€字段進(jìn)行檢驗和保護(hù)。v選擇被保護(hù)對象的選擇被保護(hù)對象的主要依據(jù)是什么？主要依據(jù)是什么？協(xié)議提供的功能，協(xié)議提供的功能，下層協(xié)議提供的服務(wù)的特點下層協(xié)議提供的服務(wù)的特點以及性能上的要求等以及性能上的要求等 2022-2-2差錯控制技術(shù)2-56現(xiàn)有協(xié)議的例子現(xiàn)有協(xié)議的例子v HDLC，點對點數(shù)據(jù)傳輸協(xié)議點對點數(shù)據(jù)傳輸協(xié)議 ，整幀整幀(不包括首尾標(biāo)志字段不包括首尾標(biāo)志字段) v PPP，Internet中的點對點協(xié)議中的點對點協(xié)議，整幀整幀 v IP，網(wǎng)際互連網(wǎng)際互連，首部首部v TCP，面向連接的可靠的端

44、到端數(shù)據(jù)傳輸服務(wù)面向連接的可靠的端到端數(shù)據(jù)傳輸服務(wù)，整個整個TPDU (計算檢驗和時要加上一個偽首部計算檢驗和時要加上一個偽首部)v UDP，無連接的不可靠的端到端數(shù)據(jù)傳輸服務(wù)無連接的不可靠的端到端數(shù)據(jù)傳輸服務(wù)，整個整個TPDU (計算檢驗和時要加上一個偽首部計算檢驗和時要加上一個偽首部)，檢驗和可選檢驗和可選 v ATM協(xié)議協(xié)議 ，傳輸傳輸ATM信元信元 ，信元首部信元首部v ATM AAL1，支持實時的、面向連接的支持實時的、面向連接的CBR數(shù)據(jù)傳輸服務(wù)數(shù)據(jù)傳輸服務(wù)，首部中的序號計數(shù)器字段的首部中的序號計數(shù)器字段的CRC檢驗，整個首部的奇偶檢驗。檢驗，整個首部的奇偶檢驗?？蛇x的負(fù)載字段的可

45、選的負(fù)載字段的FEC。 2022-2-2差錯控制技術(shù)2-57現(xiàn)有協(xié)議的例子（現(xiàn)有協(xié)議的例子（Cont.）v ATM AAL2 ，傳輸實時、低速率可變長度的短分組，支持話傳輸實時、低速率可變長度的短分組，支持話音業(yè)務(wù)音業(yè)務(wù) ，首部首部 v ATM AAL3/4 ，支持可變比特率以及面向連接和無連接的服支持可變比特率以及面向連接和無連接的服務(wù)務(wù) ，整個整個SAR-PDU v ATM AAL5 ，傳輸高速數(shù)據(jù)傳輸高速數(shù)據(jù)(AAL3/4(AAL3/4的簡化版的簡化版) ) ，整個整個CS-PDU v 幀中繼幀中繼 ，高速數(shù)據(jù)傳輸高速數(shù)據(jù)傳輸 ，整幀整幀2022-2-2差錯控制技術(shù)2-58思考題思考題2

46、-10 請解釋上述協(xié)議采用的差錯檢測方法及選擇請解釋上述協(xié)議采用的差錯檢測方法及選擇的被操作對象的理由。的被操作對象的理由。2-11 是否在所有協(xié)議中，檢驗和生成函數(shù)的輸入是否在所有協(xié)議中，檢驗和生成函數(shù)的輸入只有被保護(hù)數(shù)據(jù)？請舉例說明，并作出解釋。只有被保護(hù)數(shù)據(jù)？請舉例說明，并作出解釋。2022-2-2差錯控制技術(shù)2-59差錯控制技術(shù)：內(nèi)容提綱差錯控制技術(shù)：內(nèi)容提綱2.4.1 差錯類型差錯類型2.4.2 差錯檢測技術(shù)差錯檢測技術(shù)2.4.3 差錯控制技術(shù)差錯控制技術(shù)2.4.4 差錯控制與層次的關(guān)系差錯控制與層次的關(guān)系2022-2-2差錯控制技術(shù)2-60差錯控制技術(shù)：概述差錯控制技術(shù)：概述v上一

47、節(jié)我們已詳細(xì)介紹了用于檢測信息被上一節(jié)我們已詳細(xì)介紹了用于檢測信息被“損損壞壞”的各種檢測技術(shù)的各種檢測技術(shù)v本節(jié)我們主要介紹本節(jié)我們主要介紹“丟失丟失”、“重復(fù)重復(fù)”、“失失序序”等錯誤的檢測技術(shù)以及各種差錯的恢復(fù)技等錯誤的檢測技術(shù)以及各種差錯的恢復(fù)技術(shù)。術(shù)。 v這些技術(shù)涉及的概念主要有：這些技術(shù)涉及的概念主要有：確認(rèn)確認(rèn) (Ack)計時器計時器 (Timer)重傳重傳 (Retransmit)序號序號 (Sequence Number)2022-2-2差錯控制技術(shù)2-61差錯控制技術(shù)差錯控制技術(shù)一、確認(rèn)一、確認(rèn)(Acknowledge) 2022-2-2差錯控制技術(shù)2-62確認(rèn)確認(rèn)v確認(rèn)確

48、認(rèn)(ack)是接收者顯式地通知發(fā)送者所發(fā)送的是接收者顯式地通知發(fā)送者所發(fā)送的特定數(shù)據(jù)的接收情況特定數(shù)據(jù)的接收情況v被確認(rèn)的對象主要有哪些？被確認(rèn)的對象主要有哪些？PDU字節(jié)字節(jié)v確認(rèn)的情況：確認(rèn)的情況：已正確到達(dá)，已正確到達(dá)，還沒有收到，還沒有收到，收到但有錯收到但有錯(相當(dāng)于沒有收到相當(dāng)于沒有收到) 2022-2-2差錯控制技術(shù)2-63確認(rèn)確認(rèn)(續(xù)續(xù))v確認(rèn)分為三種類型：確認(rèn)分為三種類型： 肯定確認(rèn)肯定確認(rèn)(Ack)指示數(shù)據(jù)已正確收到指示數(shù)據(jù)已正確收到否定確認(rèn)否定確認(rèn)(Nak)指示數(shù)據(jù)丟失指示數(shù)據(jù)丟失(沒收到或收到但有錯誤沒收到或收到但有錯誤) 選擇確認(rèn)選擇確認(rèn)(Select Ack)既指示

49、已正確接收的數(shù)據(jù)既指示已正確接收的數(shù)據(jù)PDU，又指示哪些數(shù)據(jù)，又指示哪些數(shù)據(jù)PDU還沒有正確收到還沒有正確收到 2022-2-2差錯控制技術(shù)2-64確認(rèn)確認(rèn)(續(xù)續(xù))v兩種發(fā)送方式：兩種發(fā)送方式：獨立確認(rèn)獨立確認(rèn)指用一個確認(rèn)指用一個確認(rèn)PDUPDU來攜帶確認(rèn)信息來攜帶確認(rèn)信息 獨立確認(rèn)隨時可以發(fā)送獨立確認(rèn)隨時可以發(fā)送另一種是另一種是應(yīng)答攜帶應(yīng)答攜帶(piggybacking) 將確認(rèn)信息放在數(shù)據(jù)將確認(rèn)信息放在數(shù)據(jù)PDU中發(fā)送中發(fā)送可以提高協(xié)議的效率，但要求接收方有數(shù)據(jù)發(fā)送可以提高協(xié)議的效率，但要求接收方有數(shù)據(jù)發(fā)送時才能發(fā)送確認(rèn)時才能發(fā)送確認(rèn)v通常在一種協(xié)議中，這兩種確認(rèn)形式均存在通常在一種協(xié)議中

50、，這兩種確認(rèn)形式均存在 2022-2-2差錯控制技術(shù)2-65確認(rèn)（續(xù)）確認(rèn)（續(xù)）v 如何標(biāo)識被確認(rèn)的對象？如何標(biāo)識被確認(rèn)的對象？用被確認(rèn)的數(shù)據(jù)用被確認(rèn)的數(shù)據(jù)PDU或字節(jié)或字節(jié)的序號來標(biāo)識的序號來標(biāo)識否定和肯定確認(rèn)由一個序號構(gòu)成否定和肯定確認(rèn)由一個序號構(gòu)成如果否定確認(rèn)或肯定確認(rèn)的語義是表示所給定的序號之前的如果否定確認(rèn)或肯定確認(rèn)的語義是表示所給定的序號之前的所有序號所有序號( (包括或不包括本序號包括或不包括本序號) )的數(shù)據(jù)的數(shù)據(jù)PDU都已被成功地接都已被成功地接收了，則該確認(rèn)又稱為收了，則該確認(rèn)又稱為累計確認(rèn)累計確認(rèn)。 選擇確認(rèn)信息中包含多個序號，其格式可以有以下幾種：選擇確認(rèn)信息中包含多個

51、序號，其格式可以有以下幾種： 表。表中含有一組序號，要么代表丟失的數(shù)據(jù)表。表中含有一組序號，要么代表丟失的數(shù)據(jù)PDU，或者代，或者代表正確接收的數(shù)據(jù)表正確接收的數(shù)據(jù)PDU。范圍。范圍用序號區(qū)間來表示，在區(qū)間內(nèi)的序號要么代表丟范圍。范圍用序號區(qū)間來表示，在區(qū)間內(nèi)的序號要么代表丟失的數(shù)據(jù)失的數(shù)據(jù)PDUPDU，或者代表正確接收的數(shù)據(jù)，或者代表正確接收的數(shù)據(jù)PDUPDU。 位圖。用一個比特組來表示確認(rèn)，其中每一個比特位代表一位圖。用一個比特組來表示確認(rèn)，其中每一個比特位代表一個序號，它被置位表示它所代表的數(shù)據(jù)個序號，它被置位表示它所代表的數(shù)據(jù)PDU是否已正確收到。是否已正確收到。此外，這種方法還需要一

52、個序號，指明該位圖的偏移量。此外，這種方法還需要一個序號，指明該位圖的偏移量。 2022-2-2差錯控制技術(shù)2-66(a) 肯 定 確 認(rèn)(b) 否 定 確 認(rèn)(c) 選 擇 確 認(rèn)firstnlastn,nfirst,nn,n(1)first,n-1 n,nfirst,n-1n,lastfirst,n i,j,.,(2)(3)(4)(5)(6)表 示 已 正 確 收 到 序 號 對 應(yīng) 的 幀表 示 尚 未 收 到 序 號 對 應(yīng) 的 幀first = 第 1個 發(fā) 送 的 序 號 last = 最 后 發(fā) 送 的 序 號 i,j=序 號 區(qū) 間2022-2-2差錯控制技術(shù)2-67確認(rèn)（續(xù)）

53、確認(rèn)（續(xù)）v產(chǎn)生一個確認(rèn)產(chǎn)生一個確認(rèn)PDU的觸發(fā)機(jī)制的觸發(fā)機(jī)制：在接收了在接收了n個數(shù)據(jù)個數(shù)據(jù)PDU之后，接收者產(chǎn)生一個確認(rèn)之后，接收者產(chǎn)生一個確認(rèn)PDU； 發(fā)送者產(chǎn)生一個信號，請求產(chǎn)生一個確認(rèn)發(fā)送者產(chǎn)生一個信號，請求產(chǎn)生一個確認(rèn)PDU。信。信號可以隨同一個數(shù)據(jù)號可以隨同一個數(shù)據(jù)PDU一起傳遞（一起傳遞（例：例：HDLC中中的什么字段？的什么字段？），也可以是一個專用的控制），也可以是一個專用的控制PDU。接收者直到數(shù)據(jù)接收者直到數(shù)據(jù)PDU不連續(xù)到達(dá)時，才產(chǎn)生一個確不連續(xù)到達(dá)時，才產(chǎn)生一個確認(rèn)認(rèn)PDU； 接收者周期性地產(chǎn)生確認(rèn)接收者周期性地產(chǎn)生確認(rèn)PDU，與數(shù)據(jù)，與數(shù)據(jù)PDU的到來的到來無關(guān)；

54、無關(guān)； 接收者重復(fù)收到同一個數(shù)據(jù)接收者重復(fù)收到同一個數(shù)據(jù)PDU，接收者發(fā)送確認(rèn)，接收者發(fā)送確認(rèn)PDU，防止確認(rèn)丟失；，防止確認(rèn)丟失； 接收者在發(fā)送的數(shù)據(jù)中攜帶確認(rèn)信息。接收者在發(fā)送的數(shù)據(jù)中攜帶確認(rèn)信息。 2022-2-2差錯控制技術(shù)2-68確認(rèn)：思考題確認(rèn)：思考題2-12 分析分析TCP協(xié)議采用的確認(rèn)機(jī)制（提示：參考協(xié)議采用的確認(rèn)機(jī)制（提示：參考相關(guān)相關(guān)RFC）或）或 分析分析ATM的信令協(xié)議采用的確認(rèn)的信令協(xié)議采用的確認(rèn)機(jī)制。機(jī)制。2-13 試分析高速傳輸協(xié)議與低速傳輸協(xié)議所采用試分析高速傳輸協(xié)議與低速傳輸協(xié)議所采用的確認(rèn)機(jī)制上的差別。要求：先從原理上說明，的確認(rèn)機(jī)制上的差別。要求：先從原理

55、上說明，然后舉例說明。然后舉例說明。2022-2-2差錯控制技術(shù)2-69差錯控制技術(shù)差錯控制技術(shù)二、計時器二、計時器(Timer) 2022-2-2差錯控制技術(shù)2-70計時器計時器v為什么需要計時器？為什么需要計時器？如果攜帶確認(rèn)信息的確認(rèn)如果攜帶確認(rèn)信息的確認(rèn)PDU或數(shù)據(jù)或數(shù)據(jù)PDU丟失，則丟失，則發(fā)送方無法知道發(fā)送的發(fā)送方無法知道發(fā)送的PDU的接收情況。的接收情況。 這將導(dǎo)致：這將導(dǎo)致：對于可靠通信協(xié)議而言，占用發(fā)送方緩存對于可靠通信協(xié)議而言，占用發(fā)送方緩存由于流量控制而不能發(fā)送新的由于流量控制而不能發(fā)送新的PDU發(fā)送方一直處于等待狀態(tài)，死鎖發(fā)送方一直處于等待狀態(tài)，死鎖計時器：計時器：檢測

56、確認(rèn)檢測確認(rèn)PDU或重傳請求信號的丟失或重傳請求信號的丟失2022-2-2差錯控制技術(shù)2-71計時器（續(xù)）計時器（續(xù)）v計時器的超時值如何設(shè)置？計時器的超時值如何設(shè)置？是一個非常復(fù)雜及難解決的問題是一個非常復(fù)雜及難解決的問題依賴于依賴于PDU的住返時間的住返時間（RTT）RTTRTT與網(wǎng)絡(luò)負(fù)載和路由選擇策略有很大的關(guān)系，通常與網(wǎng)絡(luò)負(fù)載和路由選擇策略有很大的關(guān)系，通常情況下是一個動態(tài)變化的量情況下是一個動態(tài)變化的量動態(tài)估計動態(tài)估計往返時間和重傳計時器的定時值的算法比較多往返時間和重傳計時器的定時值的算法比較多RFC793RFC793中定義的中定義的TCPTCP算法算法MillsMills算法算法

57、(Mills, 1983)(Mills, 1983)EdgeEdge算法算法(Edge, 1984)(Edge, 1984)KarnKarn和和PatridgePatridge的算法的算法(Karn and Patridge, 1987)(Karn and Patridge, 1987)Jacobson/KarelJacobson/Karel的算法的算法(Jacobson, 1988) (Jacobson, 1988) 2022-2-2差錯控制技術(shù)2-72計時器（續(xù)）計時器（續(xù)）v計時器的超時值如何設(shè)置？（續(xù)）計時器的超時值如何設(shè)置？（續(xù)）如果超時計時器的超時值設(shè)置不當(dāng)，如果超時計時器的超時值

58、設(shè)置不當(dāng)，會導(dǎo)致什么后果？會導(dǎo)致什么后果？連續(xù)大量的數(shù)據(jù)重傳連續(xù)大量的數(shù)據(jù)重傳嚴(yán)重情況下將加劇網(wǎng)絡(luò)的擁塞程度，出現(xiàn)更多數(shù)據(jù)嚴(yán)重情況下將加劇網(wǎng)絡(luò)的擁塞程度，出現(xiàn)更多數(shù)據(jù)丟失丟失 如果超時值設(shè)置太長，出現(xiàn)數(shù)據(jù)丟失而得不到即時如果超時值設(shè)置太長，出現(xiàn)數(shù)據(jù)丟失而得不到即時糾正，也會降低協(xié)議的性能糾正，也會降低協(xié)議的性能2022-2-2差錯控制技術(shù)2-73計時器（續(xù)）計時器（續(xù)）v為了差錯控制的目的，一個協(xié)議中往往存在多個為了差錯控制的目的，一個協(xié)議中往往存在多個計時器計時器OSIOSI類類4 4運輸協(xié)議：運輸協(xié)議：發(fā)起計時器發(fā)起計時器：CR(CR(建連請求建連請求) TPDU) TPDU重傳重傳重傳重

59、傳CCCC計時器計時器：CC (CC (連接證實連接證實)TPDU)TPDU重傳重傳重傳計時器重傳計時器：DT (DT (數(shù)據(jù)數(shù)據(jù))TPDU)TPDU重傳重傳加速重傳計時器加速重傳計時器：ED(ED(加速數(shù)據(jù)加速數(shù)據(jù)) TPDU) TPDU重傳重傳釋放計時器釋放計時器：DR(DR(斷連請求斷連請求) TPDU) TPDU重傳重傳放棄加速計時器放棄加速計時器：最后檢查未被確認(rèn)的：最后檢查未被確認(rèn)的ED TPDUED TPDU靜止計時器靜止計時器：運輸連接保持靜止?fàn)顟B(tài)的最大時間：運輸連接保持靜止?fàn)顟B(tài)的最大時間 窗口計時器窗口計時器：重傳：重傳AK(AK(確認(rèn)確認(rèn)) TPDU) TPDU的最大時間間

60、隔的最大時間間隔參照計時器參照計時器：源點參照或序號不得重復(fù)使用的時間：源點參照或序號不得重復(fù)使用的時間 2022-2-2差錯控制技術(shù)2-74計時器（續(xù)）計時器（續(xù)）v為了差錯控制的目的，一個協(xié)議中往往存在多個為了差錯控制的目的，一個協(xié)議中往往存在多個計時器（續(xù)）計時器（續(xù)）TCPTCP協(xié)議：協(xié)議：重傳計時器重傳計時器：控制丟失的或丟棄的報文段控制丟失的或丟棄的報文段 堅持計時器堅持計時器：一條連接一個堅持計時器。：一條連接一個堅持計時器。當(dāng)發(fā)送端當(dāng)發(fā)送端的的TCP收到一個窗口大小為零收到一個窗口大小為零(讓發(fā)送端停止發(fā)送讓發(fā)送端停止發(fā)送)的確認(rèn)時，就啟動堅持計時器。的確認(rèn)時，就啟動堅持計時器。 ?；钣嫊r器?；钣嫊r器：在某些實現(xiàn)中，用來防止在兩