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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、檢率要比垂直冗余檢驗(yàn)低。不但可以檢測(cè)出漏檢率要比垂直冗余檢驗(yàn)低。不但可以檢測(cè)出各段同一位上的奇數(shù)位錯(cuò)，而且可以檢測(cè)出突各段同一位上的奇數(shù)位錯(cuò)，而且可以檢測(cè)出突發(fā)長(zhǎng)度小于等于發(fā)長(zhǎng)度小于等于p的所有突發(fā)錯(cuò)誤（的所有突發(fā)錯(cuò)誤（Why?Why?）因?yàn)榭梢园才虐l(fā)送順序使得因?yàn)榭梢园才虐l(fā)送順序使得在可見突發(fā)長(zhǎng)度小于等于在可見突發(fā)長(zhǎng)度小于等于p的突發(fā)錯(cuò)誤必然分布在不同的突發(fā)錯(cuò)誤必然分布在不同行中，每行一位，所以可以行中，每行一位，所以可以檢測(cè)出來(lái)檢測(cè)出來(lái) 2022-2-2差錯(cuò)控制技術(shù)2-19奇偶檢驗(yàn)：奇偶檢驗(yàn)：縱向冗余檢驗(yàn)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垂直奇偶校驗(yàn)縱向奇偶校驗(yàn)2022-2-2差錯(cuò)控制技術(shù)2-20奇偶檢驗(yàn)：奇偶檢驗(yàn)：縱向冗余檢驗(yàn)v實(shí)現(xiàn)復(fù)雜：實(shí)現(xiàn)時(shí)不能在發(fā)送過(guò)程中邊產(chǎn)生奇實(shí)現(xiàn)復(fù)雜：實(shí)現(xiàn)時(shí)不能在發(fā)送過(guò)程中邊產(chǎn)生奇偶檢驗(yàn)位，邊插入發(fā)送，而必須要等到要發(fā)送偶檢驗(yàn)位，邊插入發(fā)送，而必須要等到要發(fā)送的完整信息塊到齊后，才能產(chǎn)生檢驗(yàn)位，因而的完整信息塊到齊后，才能產(chǎn)生檢驗(yàn)位，因而一定要使用記憶寄存器。一定要使用記憶寄存器。2022-2-2差錯(cuò)控制技術(shù)2-21奇偶檢驗(yàn)：奇偶檢驗(yàn)：垂直縱向冗余檢驗(yàn)v 同時(shí)進(jìn)行垂直冗余檢驗(yàn)和縱向冗余檢驗(yàn)同時(shí)進(jìn)行垂直冗

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

19、錯(cuò)時(shí)，雖然縱向冗余檢驗(yàn)不能發(fā)現(xiàn)，但在其垂直冗余檢驗(yàn)中還是可以被檢測(cè)出不能發(fā)現(xiàn)，但在其垂直冗余檢驗(yàn)中還是可以被檢測(cè)出來(lái)。只有當(dāng)有錯(cuò)的各行和各列中出錯(cuò)位數(shù)均為偶數(shù)時(shí)，來(lái)。只有當(dāng)有錯(cuò)的各行和各列中出錯(cuò)位數(shù)均為偶數(shù)時(shí)，才不可能被發(fā)現(xiàn)。才不可能被發(fā)現(xiàn)。 2022-2-2差錯(cuò)控制技術(shù)2-22奇偶檢驗(yàn)：奇偶檢驗(yàn)：垂直縱向冗余檢驗(yàn)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垂直奇偶校驗(yàn)縱向奇偶校驗(yàn)2022-2-2差錯(cuò)控制技術(shù)2-23奇偶檢驗(yàn)：小結(jié)奇偶檢驗(yàn)：小結(jié)v使用奇偶檢

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

21、，字符之間沒(méi)有時(shí)間間隔，產(chǎn)生一個(gè)附加的字符跟在塊的后面。間隔，產(chǎn)生一個(gè)附加的字符跟在塊的后面。 2022-2-2差錯(cuò)控制技術(shù)2-24差錯(cuò)檢測(cè)技術(shù)差錯(cuò)檢測(cè)技術(shù)二、二、循環(huán)冗余檢驗(yàn)循環(huán)冗余檢驗(yàn)(CRC) 2022-2-2差錯(cuò)控制技術(shù)2-25CRC檢驗(yàn)：原理檢驗(yàn)：原理 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（生成多項(xiàng)式）= X5+X

22、4+X2+1q 模 2 運(yùn)算：加法不進(jìn)位，減法 和加法是一樣的，例如： 1111 + 1010 = 0101q 冗余碼稱為幀檢驗(yàn)序列 FCSq 接收端運(yùn)算：XnM(X) + R(X) / P(X) = Q(X)q 有錯(cuò)：R(X) !=0q 問(wèn)題：R(X) 等于0是否就不定沒(méi)有錯(cuò)嗎？q 常見多項(xiàng)式：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差錯(cuò)控制技術(shù)2-26CRC檢驗(yàn)：檢錯(cuò)率檢驗(yàn)：檢錯(cuò)率vCRC

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

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

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

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差錯(cuò)控制

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差錯(cuò)控制技術(shù)2-31crc_init.c: examplesv$ crc_init 05401 crc_12.h 創(chuàng)建基于創(chuàng)建基于CRC-12的檢驗(yàn)和表，并保存在文件

28、的檢驗(yàn)和表，并保存在文件crc_12.h中中 v$ crc_init 0120001 crc_16.h 創(chuàng)建基于創(chuàng)建基于CRC-16的檢驗(yàn)和表，并保存在文件的檢驗(yàn)和表，并保存在文件crc_16.h中中 v$ crc_init 0102010 crc_ccitt.h 創(chuàng)建基于創(chuàng)建基于CRC-CCITT的檢驗(yàn)和表，并保存在文件的檢驗(yàn)和表，并保存在文件crc_ccitt.h 中中2022-2-2差錯(cuò)控制技術(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差錯(cuò)控制技術(shù)2-33差錯(cuò)檢測(cè)技術(shù)差錯(cuò)檢測(cè)技術(shù)三、三、UUCP檢驗(yàn)和檢驗(yàn)和 2022-2-2差錯(cuò)控制技術(shù)2-34UUCP檢驗(yàn)和檢驗(yàn)和vUNIX操作系統(tǒng)中的操作系統(tǒng)中的uucp應(yīng)用程序中的計(jì)算檢驗(yàn)應(yīng)用程序中的計(jì)算檢驗(yàn)和方法，與和方法，與CRC檢驗(yàn)比較類似檢驗(yàn)比較類似v比較簡(jiǎn)單，有點(diǎn)類似于散列方法，其漏檢率比比較簡(jiǎn)單，有點(diǎn)類似于散列方法，其漏檢率比CRCCRC要高一些，而且計(jì)算同樣的檢

30、驗(yàn)和，它所花要高一些，而且計(jì)算同樣的檢驗(yàn)和，它所花的時(shí)間比查表計(jì)算的時(shí)間比查表計(jì)算CRCCRC檢驗(yàn)和的方法要多一些。檢驗(yàn)和的方法要多一些。 2022-2-2差錯(cuò)控制技術(shù)2-35UUCP檢驗(yàn)和：源碼檢驗(yàn)和：源碼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差錯(cuò)控制技術(shù)2-36差錯(cuò)檢測(cè)技術(shù)差錯(cuò)檢測(cè)技術(shù)四、四、算術(shù)檢驗(yàn)和算術(shù)檢驗(yàn)和(Arithmetic Checksum) 2022-2-2差錯(cuò)控制技術(shù)2-37算術(shù)檢驗(yàn)和算術(shù)檢驗(yàn)和v盡管可以通過(guò)前面介紹的查表的方法或特殊硬盡管可以通過(guò)前面介紹的查表的方法或特殊硬件的方法計(jì)算檢驗(yàn)和來(lái)縮短處理時(shí)間件的方法計(jì)算檢驗(yàn)和來(lái)縮短處理時(shí)間，但：，但：v對(duì)于允許一定程度的漏檢率的應(yīng)用場(chǎng)合，對(duì)于允許一定程度的漏檢率的應(yīng)用場(chǎng)合，可以可以采用比采用比CRC檢驗(yàn)要簡(jiǎn)單且又能夠發(fā)現(xiàn)比較嚴(yán)重檢驗(yàn)要簡(jiǎn)單且又能夠發(fā)現(xiàn)比較

33、嚴(yán)重的傳輸錯(cuò)誤的方法來(lái)進(jìn)行差錯(cuò)檢測(cè)。的傳輸錯(cuò)誤的方法來(lái)進(jìn)行差錯(cuò)檢測(cè)。vJohn Fletcher John Fletcher 在在19821982提出了這樣一種差錯(cuò)檢提出了這樣一種差錯(cuò)檢測(cè)方法，稱為測(cè)方法，稱為算術(shù)檢驗(yàn)和算術(shù)檢驗(yàn)和只需用到加法和取模操作，只需用到加法和取模操作，且算法特別簡(jiǎn)單且算法特別簡(jiǎn)單 2022-2-2差錯(cuò)控制技術(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差錯(cuò)控制技術(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差錯(cuò)控制技術(shù)2-40算術(shù)檢驗(yàn)和：源碼算術(shù)檢驗(yàn)和：源碼vISO的類的類4運(yùn)輸協(xié)議運(yùn)輸協(xié)議(TP4) 中的實(shí)現(xiàn)源代碼：中的實(shí)現(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，而且編號(hào)而且編號(hào)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 注意：在每個(gè)檢驗(yàn)位的形成表達(dá)式中，除自身的編號(hào)外，注意：在每個(gè)檢驗(yàn)位的形成表達(dá)式中，除自身的編號(hào)外，其余都是信息位的編號(hào)，因此只要信息位是確定的，檢其余都是信息位的編號(hào)，因此只要信息位是確定的，檢驗(yàn)位也

38、可以唯一地確定。驗(yàn)位也可以唯一地確定。 2022-2-2差錯(cuò)控制技術(shù)2-51Hamming Code (Cont.)v 10個(gè)個(gè)7位位ASCII字符使用海明編碼形成的字符使用海明編碼形成的10位碼字，其中位碼字，其中數(shù)據(jù)位在數(shù)據(jù)位在3、5、6、7、9、10和和11位，編號(hào)為位，編號(hào)為1、2、4、8的位是檢驗(yàn)位。的位是檢驗(yàn)位。字符：字符：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差錯(cuò)控制技術(shù)2-52HammingCode (Cont.)v 當(dāng)一碼字到達(dá)時(shí)，接收方將計(jì)數(shù)器清當(dāng)一碼字到達(dá)時(shí)，接收方將計(jì)數(shù)器清0。 v 然后接收方檢測(cè)每個(gè)檢驗(yàn)位然后接收方檢測(cè)每個(gè)檢驗(yàn)位D(這里的這里的D是檢驗(yàn)位的編是檢驗(yàn)位的編號(hào)號(hào))，看是否具有正確的奇偶性。，看是否具有正確的奇偶性。 如果第如果第D位奇偶性不對(duì)，則計(jì)數(shù)值加位奇偶性不對(duì)，則計(jì)數(shù)值加D， 若所有檢驗(yàn)位被檢查過(guò)后，計(jì)數(shù)器值仍為若所有檢驗(yàn)位被檢查過(guò)后，計(jì)數(shù)器值仍為0，這個(gè)碼字就作為，這個(gè)碼字就作為有

41、效碼字接受。有效碼字接受。 假如計(jì)數(shù)器值不為假如計(jì)數(shù)器值不為0，則該值就是出錯(cuò)位的編者編號(hào)。，則該值就是出錯(cuò)位的編者編號(hào)。 例如，若檢測(cè)位例如，若檢測(cè)位1、2和和8錯(cuò)誤，則第錯(cuò)誤，則第11位就變反，因?yàn)樗俏ㄎ痪妥兎?，因?yàn)樗俏ㄒ槐坏谝槐坏?、2和和8位檢測(cè)的位。位檢測(cè)的位。 v 海明碼的信息余量很大海明碼的信息余量很大( (前面的例子：前面的例子：7+4)7+4)，因而編碼，因而編碼效率低。大大增加了數(shù)據(jù)通信的開銷效率低。大大增加了數(shù)據(jù)通信的開銷2022-2-2差錯(cuò)控制技術(shù)2-53檢錯(cuò)重傳與糾錯(cuò)檢錯(cuò)重傳與糾錯(cuò)v一般使用檢錯(cuò)重傳，特別是在數(shù)據(jù)鏈路層以上一般使用檢錯(cuò)重傳，特別是在數(shù)據(jù)鏈路層以上的

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

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

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

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

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

47、節(jié)我們已詳細(xì)介紹了用于檢測(cè)信息被上一節(jié)我們已詳細(xì)介紹了用于檢測(cè)信息被“損損壞壞”的各種檢測(cè)技術(shù)的各種檢測(cè)技術(shù)v本節(jié)我們主要介紹本節(jié)我們主要介紹“丟失丟失”、“重復(fù)重復(fù)”、“失失序序”等錯(cuò)誤的檢測(cè)技術(shù)以及各種差錯(cuò)的恢復(fù)技等錯(cuò)誤的檢測(cè)技術(shù)以及各種差錯(cuò)的恢復(fù)技術(shù)。術(shù)。 v這些技術(shù)涉及的概念主要有：這些技術(shù)涉及的概念主要有：確認(rèn)確認(rèn) (Ack)計(jì)時(shí)器計(jì)時(shí)器 (Timer)重傳重傳 (Retransmit)序號(hào)序號(hào) (Sequence Number)2022-2-2差錯(cuò)控制技術(shù)2-61差錯(cuò)控制技術(shù)差錯(cuò)控制技術(shù)一、確認(rèn)一、確認(rèn)(Acknowledge) 2022-2-2差錯(cuò)控制技術(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)的對(duì)象主要有哪些？被確認(rèn)的對(duì)象主要有哪些？PDU字節(jié)字節(jié)v確認(rèn)的情況：確認(rèn)的情況：已正確到達(dá)，已正確到達(dá)，還沒(méi)有收到，還沒(méi)有收到，收到但有錯(cuò)收到但有錯(cuò)(相當(dāng)于沒(méi)有收到相當(dāng)于沒(méi)有收到) 2022-2-2差錯(cuò)控制技術(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ù)丟失(沒(méi)收到或收到但有錯(cuò)誤沒(méi)收到或收到但有錯(cuò)誤) 選擇確認(rèn)選擇確認(rèn)(Select Ack)既指示

49、已正確接收的數(shù)據(jù)既指示已正確接收的數(shù)據(jù)PDU，又指示哪些數(shù)據(jù)，又指示哪些數(shù)據(jù)PDU還沒(méi)有正確收到還沒(méi)有正確收到 2022-2-2差錯(cuò)控制技術(shù)2-64確認(rèn)確認(rèn)(續(xù)續(xù))v兩種發(fā)送方式：兩種發(fā)送方式：獨(dú)立確認(rèn)獨(dú)立確認(rèn)指用一個(gè)確認(rèn)指用一個(gè)確認(rèn)PDUPDU來(lái)攜帶確認(rèn)信息來(lái)攜帶確認(rèn)信息 獨(dú)立確認(rèn)隨時(shí)可以發(fā)送獨(dú)立確認(rèn)隨時(shí)可以發(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ā)送時(shí)才能發(fā)送確認(rèn)時(shí)才能發(fā)送確認(rèn)v通常在一種協(xié)議中，這兩種確認(rèn)形式均存在通常在一種協(xié)議中

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

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

52、個(gè)序號(hào)，指明該位圖的偏移量。此外，這種方法還需要一個(gè)序號(hào)，指明該位圖的偏移量。 2022-2-2差錯(cuò)控制技術(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)表 示 已 正 確 收 到 序 號(hào) 對(duì) 應(yīng) 的 幀表 示 尚 未 收 到 序 號(hào) 對(duì) 應(yīng) 的 幀first = 第 1個(gè) 發(fā) 送 的 序 號(hào) last = 最 后 發(fā) 送 的 序 號(hào) i,j=序 號(hào) 區(qū) 間2022-2-2差錯(cuò)控制技術(shù)2-67確認(rèn)（續(xù)）

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

54、無(wú)關(guān)； 接收者重復(fù)收到同一個(gè)數(shù)據(jù)接收者重復(fù)收到同一個(gè)數(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差錯(cuò)控制技術(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ī)制上的差別。要求：先從原理上說(shuō)明，的確認(rèn)機(jī)制上的差別。要求：先從原理

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

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

58、設(shè)置不當(dāng)，會(huì)導(dǎo)致什么后果？會(huì)導(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í)值設(shè)置太長(zhǎng)，出現(xiàn)數(shù)據(jù)丟失而得不到即時(shí)如果超時(shí)值設(shè)置太長(zhǎng)，出現(xiàn)數(shù)據(jù)丟失而得不到即時(shí)糾正，也會(huì)降低協(xié)議的性能糾正，也會(huì)降低協(xié)議的性能2022-2-2差錯(cuò)控制技術(shù)2-73計(jì)時(shí)器（續(xù)）計(jì)時(shí)器（續(xù)）v為了差錯(cuò)控制的目的，一個(gè)協(xié)議中往往存在多個(gè)為了差錯(cuò)控制的目的，一個(gè)協(xié)議中往往存在多個(gè)計(jì)時(shí)器計(jì)時(shí)器OSIOSI類類4 4運(yùn)輸協(xié)議：運(yùn)輸協(xié)議：發(fā)起計(jì)時(shí)器發(fā)起計(jì)時(shí)器：CR(CR(建連請(qǐng)求建連請(qǐng)求) TPDU) TPDU重傳重傳重傳重

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

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