第4-2講 差錯控制技術(shù).ppt

1、-1,差錯控制技術(shù),第 4-2 講,網(wǎng)絡(luò)通用技術(shù),-2,內(nèi)容提綱,1 概述 2 差錯類型 3 差錯檢測技術(shù) 4 差錯控制技術(shù) 5 差錯控制與網(wǎng)絡(luò)層次的關(guān)系,-3,差錯控制：概述,網(wǎng)絡(luò)通信的目的是通過網(wǎng)絡(luò)在應(yīng)用進程間傳輸信息，任何數(shù)據(jù)丟失或損壞都將對通信雙方產(chǎn)生重要的影響。 差錯控制是指在網(wǎng)絡(luò)通信過程中發(fā)現(xiàn)（檢測）差錯，并采取措施糾正，把差錯限制在所允許的盡可能小的范圍內(nèi)的技術(shù)和方法。 差錯控制的目的是為了提高數(shù)據(jù)傳輸?shù)目煽啃?，但是任何一種差錯控制方法均不可能糾正所有可能出現(xiàn)的差錯。,-4,差錯類型（續(xù)）,根據(jù)差錯的表現(xiàn)形式 ，可分為四類（）： 失真(Distortion) 定義：被傳送信息中的

2、一個或多個比特發(fā)生了改變，或者被傳送的信息中插入了一些新的信息，后一種情況也稱為“插入(Insertion)” 主要原因： 網(wǎng)絡(luò)中物理干擾（如線路噪聲） 發(fā)送者和接收者之間的失步 入侵者的故意攻擊 結(jié)點中的硬件故障和軟件差錯等 解決方法：各種校驗方法來檢測,-5,差錯類型（續(xù)）,根據(jù)差錯的表現(xiàn)形式 ，可分為四類（） 丟失(Deletion) 定義：網(wǎng)絡(luò)將被傳輸?shù)男畔G棄 主要原因： 噪聲脈沖對某個幀的破壞程度太大，以致接收方不知道這個幀已經(jīng)被傳輸； 發(fā)送者和接收者之間的失步； 流量控制或擁塞控制措施不當(dāng)時因資源不夠而被中間結(jié)點或接收者丟棄； 因接收者檢測到信息被損壞而主動將其丟棄等 解決方法：

3、用序號、計時器和確認共同檢測，通過重傳的方法來糾正錯誤,-6,差錯類型（續(xù)）,根據(jù)差錯的表現(xiàn)形式 ，可分為四類（） 重復(fù)(Duplication) 定義：多次收到同樣的信息 主要原因： 是差錯控制機制本身，如果發(fā)送方錯誤地認為數(shù)據(jù)丟失了，因而重傳了它，就可能造成接收方收到重復(fù)的信息 路由選擇機制引起的重復(fù)幀，如使用基于擴散的路由選擇策略(如洪泛法) 解決方法：用序號來檢測這種錯誤，用丟棄重復(fù)的數(shù)據(jù)來糾正錯誤。,-7,差錯類型（續(xù)）,根據(jù)差錯的表現(xiàn)形式 ，可分為四類（） 失序(Reordering) 定義：數(shù)據(jù)到達接收方的順序與發(fā)送方發(fā)送的順序不一致 主要原因： 采用自適應(yīng)的路由選擇策略，分組在

4、網(wǎng)絡(luò)中傳送時可能有多條路由而引起的后發(fā)先到 中間結(jié)點緩存或轉(zhuǎn)發(fā)出錯 重傳丟失的數(shù)據(jù)也可能導(dǎo)致數(shù)據(jù)不按序到達 解決方法： 把亂序的數(shù)據(jù)先存儲下來，使得以后能把它們存放在正確的位置上； 丟棄亂序的數(shù)據(jù)，然后按數(shù)據(jù)丟失來處理 。,-8,差錯檢測技術(shù)：概述,檢查收到的數(shù)據(jù)是否正確 通常情況下，我們所說的差錯檢測是指檢測收到的數(shù)據(jù)是否被損壞，而不包括對數(shù)據(jù)丟失、重復(fù)、亂序等差錯的檢測 在這樣的前提下，差錯檢測技術(shù)所采取的方法一般是各種檢驗和技術(shù)，如奇偶檢驗，循環(huán)冗余檢驗等,本節(jié)主要介紹這方面的技術(shù) 差錯檢測是差錯控制的基礎(chǔ),-9,差錯檢測技術(shù)：原理,E, E：差錯檢驗碼,對比,接收器,數(shù)據(jù),E,E =

5、f(Data),數(shù)據(jù),E,E = f(Data),發(fā)送器,數(shù)據(jù),f: 差錯檢驗函數(shù),問題：為什么將檢驗碼放在幀的尾部？,-10,奇偶檢驗,奇偶檢驗在數(shù)據(jù)的尾部附加上奇偶檢驗位，使得碼字中比特“1”的個數(shù)保持為奇數(shù)(奇檢驗)或偶數(shù)(偶檢驗) 被廣泛用于諸如計算機的異步串行口通信中 三種類型： 垂直冗余檢驗(Vertical Redundancy Checking，VRC) 水平（縱向）冗余檢驗(Longitudinal Redundancy Checking，LRC) 垂直水平冗余檢驗,-11,奇偶檢驗：垂直冗余檢驗,原理：將整個發(fā)送的信息分為長度為p位的若干段，如q段，每段后面按“1”的個數(shù)為

6、奇數(shù)或偶數(shù)的規(guī)律加上一位奇偶位，其有(pq) 個信息位，每段由p位構(gòu)成，共q段。 通常p值等于一個字符的長度，因此有時也將垂直冗余檢驗稱為字符奇偶檢驗。 可以用硬件或軟件方法來實現(xiàn)連續(xù)半加（不考慮進位）運算，且可以邊發(fā)送邊產(chǎn)生檢驗位，并插入檢驗位發(fā)送。在接收時邊接收邊進行檢驗并除去檢驗位 能檢測出每行中的所有奇數(shù)個位的錯，但檢測不出偶數(shù)個位的錯。對于突發(fā)錯誤而言，奇數(shù)位錯與偶數(shù)位錯的概率差不多是相等的，因而對差錯的漏檢率接近于50%。,-12,奇偶檢驗：水平冗余檢驗,原理：對各個信息段的相應(yīng)位水平進行編碼，對應(yīng)每一列產(chǎn)生一個奇偶檢驗位。這種水平基礎(chǔ)上檢驗字符的技術(shù)，使用了和垂直冗余檢驗同樣的奇

7、偶性。 漏檢率要比垂直冗余檢驗低。不但可以檢測出各段同一位上的奇數(shù)位錯，而且可以檢測出突發(fā)長度小于等于p的所有突發(fā)錯誤（Why?）,突發(fā)長度小于等于p的突發(fā)錯誤必然分布在不同列中，每列一位，所以可以檢測出來,-13,奇偶檢驗：垂直水平冗余檢驗,同時進行垂直冗余檢驗和縱向冗余檢驗 能檢測出所有3位或3位以下的錯誤(因為此時至少在某一行或某一列上為一位錯)、奇數(shù)位錯、突發(fā)長度小于等于(p+1)的突發(fā)錯。 還可以糾正部分差錯，例如僅在某一行和某一列中有1位錯時，就可以確定錯誤的位置就在該行和該列的交叉處，從而得以糾正。 此外，能檢測很大一部分偶數(shù)位錯。當(dāng)某一行出現(xiàn)偶數(shù)個錯時，雖然垂直冗余檢驗不能發(fā)現(xiàn)

8、，但在其縱向冗余檢驗中還是可以被檢測出來；反之亦然。只有當(dāng)有錯的各行和各列中出錯位數(shù)均為偶數(shù)時，才不可能被發(fā)現(xiàn)。,-14,CRC檢驗：原理,CRC是數(shù)據(jù)通信中進行錯誤檢查和糾正的一種重要方法，易于編碼和解碼，對隨機和突發(fā)錯碼均能以較低冗余度實施檢查。 方法：發(fā)端產(chǎn)生一個循環(huán)冗余檢驗碼，附在信息位后面發(fā)到收端，收端按照與發(fā)端同樣的算法進行檢驗，若有錯，需要重發(fā)。 線性碼：由k位信息碼和r位檢驗碼構(gòu)成，每位檢驗碼都是前面某些信息碼元的模2和（即按照線性關(guān)系相加），碼長n=k+r。 線性碼特點：封閉性（任意兩個碼字相加仍可得到一個碼字）和循環(huán)型（一個碼字作任意循環(huán)移位得到的仍是碼字）。,-15,CR

9、C檢驗：示例,1101010110Q 商 除數(shù)P110101 101000110100000XrM 被除數(shù) 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110R 余數(shù),數(shù)據(jù)：M=1010001101 除數(shù)P（生成多項式）= X5+X4+X2+X0 XrM(X)=P(X)Q(X)+R(X) 模 2 運算：加法不進位，減法和加法一樣， 例如：1111 + 1010 = 0101 冗余碼（R(X)）稱為幀檢驗序列 FCS T(X)=XrM(X) + R(X)稱為循環(huán)碼 接收端運算：XrM

10、(X) + R(X) / P(X) = Q(X)， 有錯：余數(shù)R(X) !=0； 無錯：余數(shù)R(X) =0，去掉尾部r位便得到信息碼 問題：R(X) 等于0就肯定沒有錯嗎？ 常見多項式： CRC-CCITT = X16+X12+X5+1； CRC-16 = X16+X15+X2+1 CRC-12 = X12+X11+X3+X2+X+1 CRC-32 = X32+X26+X23+ X22+X16+X12+ X11+X10+X8+ X7+X5+X4+ X2+X+1,（信息多項式）,-16,算術(shù)檢驗和（因特網(wǎng)檢驗和）,盡管可以通過前面介紹的查表方法或特殊硬件方法計算檢驗和來縮短處理時間，但： 對于允

11、許一定程度漏檢率的應(yīng)用場合，可以采用比CRC檢驗簡單且又能夠發(fā)現(xiàn)比較嚴重的傳輸錯誤的方法來進行差錯檢測。 John Fletcher 在1982提出了這樣一種差錯檢測方法，稱為算術(shù)檢驗和 只需用到加法和取模操作 算法特別簡單 一些因特網(wǎng)協(xié)議（TCP、UDP和IP）使用這種方法，強調(diào)易實現(xiàn)性和簡單性,-17,Arithmetic Checksum,Error detection at the higher layer is usually done by ordinary arithmetic operations.This is simpler in software but somewhat

12、 less effective than CRC. Standard technique is to view packet as sequence of k numbers of n bits each, say x1, x2,., xk. Checksum is then the n bit number x1+x2+.+xk using ordinary arithmetic with no carry.,-18,Arithmetic Checksum (Cont.),Alternatively, checksum might be 2n bits; first n bits is (s

13、um) x1+x2+.+xk and second n bits is (sum of sum) x1+2x2+3x3+.+kxk. Example: n=16, checksum is 16 bits. Checksum=x1+x2+.+xk，接收端計算x1+x2+.+xk+Checksum=0，則沒有錯誤。,-19,UDP協(xié)議的差錯檢測,兩個數(shù)進行二進制反碼求和的運算規(guī)則是從低位到高位逐列進行計算。0和0相加是0，0和1相加是1，1和1相加是0但要產(chǎn)生一個進位1，加到下一列。最高位相加后產(chǎn)生的進位則進到最低位，也就是循環(huán)進位。,-20,UDP協(xié)議的差錯檢測,-21,TCP協(xié)議的差錯檢測,檢

14、驗和字段檢驗的范圍包括首部和數(shù)據(jù)這兩部分。和UDP用戶數(shù)據(jù)報一樣，在計算檢驗和時，要在TCP報文段的前面加上12字節(jié)的偽首部。偽首部的格式與UDP用戶數(shù)據(jù)報的偽首部一樣。但應(yīng)將偽首部第6個字段中的17改為6（TCP的協(xié)議號是6），將第5字段中的UDP長度改為TCP長度。TCP必須進行檢驗(UDP可選)。,-22,前向糾錯技術(shù),前向糾錯：在每個要發(fā)送的數(shù)據(jù)塊附加足夠的冗余信息(糾錯碼)，使接收方能夠推導(dǎo)出發(fā)送方實際發(fā)送的應(yīng)該是什么樣的比特串。 前面介紹的縱向垂直冗余檢驗就具有糾錯功能。 漢明碼(Hamming Code) 一般情況下，使用差錯檢測技術(shù)檢測出傳輸錯誤后，通常使用重傳（請求重傳和超時

15、重傳）的方法來糾正。 為什么需要前向糾錯(Forward Error Correction, FEC) ？,-23,前向糾錯技術(shù),在有些場合下，不適合或不能使用重傳的方法，例如： 很長的傳輸時延： 例如，空間探測器與地面控制中心之間的通信，可能沒有足夠的時間來重傳 沒有反向信道： 在單向廣播系統(tǒng)中，根本不能發(fā)送重傳請求。 高的比特差錯率： 重傳幀以及請求重傳幀出錯的概率都非常高，使得重傳難以實現(xiàn) 某些實時性應(yīng)用 發(fā)端的信息無法存儲,-24,被保護對象的選擇,有些協(xié)議中，是對整個數(shù)據(jù)單元（幀、分組、報文，或統(tǒng)稱為PDU）進行檢驗和保護， 而另一些協(xié)議則只需要對數(shù)據(jù)單元的首部(控制部分)或首部中的

16、某些字段進行檢驗和保護。 選擇被保護對象的主要依據(jù)是： 協(xié)議提供的功能 下層協(xié)議提供的服務(wù)的特點 性能上的要求等,-25,思考題,1 請說明上述協(xié)議采用的差錯檢測方法及選擇的被保護對象的理由。 2 是否在所有協(xié)議中，檢驗和生成函數(shù)的輸入只有被保護數(shù)據(jù)？請舉例說明，并作出解釋。,-26,差錯控制技術(shù),一、確認(Acknowledge),-27,確認,確認(ack)是接收者顯式地通知發(fā)送者所發(fā)送的特定數(shù)據(jù)的接收情況 被確認的對象主要有 PDU 字節(jié) 確認的情況： 已正確到達， 還沒有收到， 收到但有錯（相當(dāng)于沒有收到）,-28,確認(續(xù)),確認分為三種類型： 肯定確認(Ack) 指示數(shù)據(jù)已正確收到

17、 否定確認(Nak) 指示數(shù)據(jù)丟失（沒收到或收到但有錯誤） 選擇確認(Select Ack) 既指示已正確接收的數(shù)據(jù)，又指示哪些數(shù)據(jù)還沒有正確收到,-29,確認(續(xù)),兩種發(fā)送方式： 獨立確認 指用一個確認PDU來攜帶確認信息 獨立確認隨時可以發(fā)送 另一種是捎帶確認(piggybacking) 將確認信息放在數(shù)據(jù)PDU中發(fā)送 可以提高協(xié)議的效率，但要求接收方有數(shù)據(jù)發(fā)送時才能發(fā)送確認 通常在一種協(xié)議中，這兩種確認形式均存在。,-30,確認（續(xù)）,如何標(biāo)識被確認的對象？ 用被確認的PDU或字節(jié)的序號來標(biāo)識 否定和肯定確認通常包含一個序號 如果確認的語義表示給定序號之前的所有序號(包括或不包括本序號

18、)的數(shù)據(jù)都已被成功接收，則該確認又稱為累計確認。 選擇確認信息中包含多個序號，其格式可以有以下幾種： 表。表中含有一組序號，代表丟失的數(shù)據(jù)或代表正確接收的數(shù)據(jù)。 范圍。范圍用序號區(qū)間來表示，在區(qū)間內(nèi)的序號代表丟失的數(shù)據(jù)或者代表正確接收的數(shù)據(jù)。 位圖。用一個比特組來表示確認，其中每一個比特位代表一個序號，它被置位表示它所代表的數(shù)據(jù)已正確收到。此外，這種方法還需要一個序號，指明該位圖的偏移量。,-31,確認：思考題,3 討論TCP協(xié)議采用的確認機制（考慮收到正確數(shù)據(jù)、錯誤數(shù)據(jù)、數(shù)據(jù)丟失、重復(fù)、失序等情況）并分析確認機制的效率。 4 試分析高速傳輸協(xié)議與低速傳輸協(xié)議所采用的確認機制上的差別（如幀中繼

19、和X.25）。,-32,差錯控制技術(shù),二、計時器(Timer),-33,計時器,為什么需要計時器？ 如果攜帶確認信息的確認PDU或數(shù)據(jù)PDU丟失，則發(fā)送方無法知道發(fā)送的PDU的接收情況。 這將導(dǎo)致： 對于可靠通信協(xié)議而言，占用發(fā)送方緩存 由于流量控制而不能發(fā)送新的PDU 發(fā)送方一直處于等待狀態(tài)，死鎖 計時器：檢測確認PDU或重傳請求信號的丟失,-34,計時器（續(xù)）,計時器的超時值如何設(shè)置？ 是一個非常復(fù)雜和難解決的問題，依賴于住返時間（RTT） RTT與網(wǎng)絡(luò)負載和路由選擇策略有很大的關(guān)系，通常情況下是一個動態(tài)變化的量 動態(tài)估計往返時間和重傳計時器定時值的算法 Mills算法(Mills, 19

20、83) Edge算法(Edge, 1984) Karn和Patridge的算法(Karn and Patridge, 1987) Jacobson/Karel的算法(Jacobson, 1988) 如果超時計時器的超時值設(shè)置不當(dāng)，會導(dǎo)致 過短，導(dǎo)致連續(xù)大量的數(shù)據(jù)重傳，嚴重情況下將加劇網(wǎng)絡(luò)擁塞，甚至出現(xiàn)擁塞崩潰 如果超時值設(shè)置太長，出現(xiàn)數(shù)據(jù)丟失而得不到及時糾正，則會降低協(xié)議的性能,-35,計時器（續(xù)）,為了差錯控制的目的，一個協(xié)議中往往存在多個計時器（續(xù)） TCP協(xié)議： 重傳計時器：控制丟失的或丟棄的報文段 凍結(jié)計時器：一條連接一個凍結(jié)計時器。當(dāng)發(fā)送端的TCP收到一個窗口大小為零(讓發(fā)送端停止發(fā)

21、送)的確認時，就啟動凍結(jié)計時器。 保活計時器：在某些實現(xiàn)中，用來防止在兩個TCP端點之間的連接長期處于空閑 時間等待計時器：在連接終止期間使用。當(dāng)TCP關(guān)閉一個連接時，它并不認為這個連接馬上就真正關(guān)閉。在時間等待期間中，連接還處于一種中間過渡狀態(tài)。,-36,計時器：思考題,5 請以TCP為例，詳細討論在設(shè)置計時器的超時值時應(yīng)考慮哪些問題。,-37,差錯控制技術(shù),三、重傳(Retransmit),-38,重傳,指發(fā)送者重傳由確認所指出的數(shù)據(jù)PDU或重傳計時器超時未收到確認的數(shù)據(jù)PDU。 基于滑動窗口的重傳方法： 回退n幀(Go-back-N) 接收方直接丟棄所有不按序到達的數(shù)據(jù)PDU。 發(fā)送方從

22、第一個否定確認或超時時所指序號的數(shù)據(jù)PDU開始，重傳所有后續(xù)數(shù)據(jù)PDU。 選擇重傳(selective repeat) 發(fā)送方只重傳否定確認、選擇確認和計時器超時指出的那些數(shù)據(jù)PDU,-39,重傳（續(xù)）,實際協(xié)議中的重傳機制比較復(fù)雜，主要是計時器的超時間隔很難確定。 TCP的重傳機制 重傳機制是TCP中最重要和最復(fù)雜的問題之一。TCP每發(fā)送一個報文段，就設(shè)置一次計時器。只要計時器設(shè)置的重傳時間到而還沒有收到確認，就要重傳這一報文段。 TCP的下層往往是一個互連網(wǎng)環(huán)境。發(fā)送的報文段可能只經(jīng)過一個高速率的局域網(wǎng)，也可能經(jīng)過多個低速率的廣域網(wǎng)，并且數(shù)據(jù)報所選擇的路由也可能會發(fā)生變化 需要一種動態(tài)自適

23、應(yīng)算法,-40,差錯控制技術(shù),四、序號(Sequence Number),-41,序號,為什么需要序號？ 為了檢測數(shù)據(jù)PDU的重復(fù)、失序和丟失，需要對數(shù)據(jù)PDU進行無二義性的編號，該編號稱為數(shù)據(jù)PDU的序號 編號通常是按照請求服務(wù)者傳遞SDU的次序進行的。這些SDU被放入PDU中進行傳輸。 序號有三種不同的產(chǎn)生方式： SDU序號：對每個SDU都編上序號，從SDU序號得到PDU的序號。如果該SDU被攜帶在多個數(shù)據(jù)PDU中時，還應(yīng)附加一個SDU數(shù)據(jù)塊號 PDU序號：對PDU連續(xù)編號，不管它們攜帶的SDU數(shù)據(jù)量。 字節(jié)序號：一個SDU的每個字節(jié)都編號，PDU的序號來自于它所攜帶的SDU的第1個字節(jié)的

24、序號或最后1個字節(jié)的序號。,-42,序號（續(xù)）,一個重要的問題：如何防止序號重復(fù)？ 使用非常大的序號空間。這個序號空間大到使得在數(shù)據(jù)單元從這一端傳送到另一端的最大可能的遲延時間L內(nèi)，所有從源點發(fā)送出去的新的數(shù)據(jù)單元都具有不同的序號。在開始一個新的連接時，可以使數(shù)據(jù)單元的起始序號為上次連接中最后使用過的序號加1。 每次連接開始數(shù)據(jù)單元都使用同樣的起始序號，但必須使新的連接推遲開始，如至少在上次的連接釋放后推遲時間L。 賦給每個連接一個標(biāo)號，或者稱為連接序號。對于一個給定連接中的每一個數(shù)據(jù)單元都附上連接序號。當(dāng)新建一個連接時，就換上一個新的序號(如socket)。,-43,序號（續(xù)）,序號空間的大

25、小與信道特點、確認方法、流量控制方法和PDU數(shù)據(jù)字段長度有關(guān) 如果信道的質(zhì)量比較好，則序號空間要求比較大，從而可以連續(xù)發(fā)送多個數(shù)據(jù)單元，提高協(xié)議效率 采用周期性確認，序號空間就不一定要很大 在停止等待協(xié)議中，只需要0和1兩個序號即可 一般來說，序號空間的大小與數(shù)據(jù)字段長度成反比 序號是確認和重傳的基礎(chǔ)，此外序號還可用于流量控制。,-44,差錯控制技術(shù)：思考題,6 簡要說明確認、計時器、重傳、序號之間的關(guān)系。,-45,差錯控制與協(xié)議層次的關(guān)系,從通信和信息處理角度看，物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層和運輸層屬面向通信部分，因而網(wǎng)絡(luò)中的絕大部分差錯控制功能要在這幾層中實現(xiàn)。 處于不同層次的協(xié)議所采用的差錯控制機制是有