第4-2講 差錯控制技術.ppt

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

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

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

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

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

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

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

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

9、C檢驗：示例,1101010110Q 商 除數P110101 101000110100000XrM 被除數 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110R 余數,數據：M=1010001101 除數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)， 有錯：余數R(X) !=0； 無錯：余數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,算術檢驗和（因特網檢驗和）,盡管可以通過前面介紹的查表方法或特殊硬件方法計算檢驗和來縮短處理時間，但： 對于允

11、許一定程度漏檢率的應用場合，可以采用比CRC檢驗簡單且又能夠發(fā)現(xiàn)比較嚴重的傳輸錯誤的方法來進行差錯檢測。 John Fletcher 在1982提出了這樣一種差錯檢測方法，稱為算術檢驗和 只需用到加法和取模操作 算法特別簡單 一些因特網協(xié)議（TCP、UDP和IP）使用這種方法，強調易實現(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é)議的差錯檢測,兩個數進行二進制反碼求和的運算規(guī)則是從低位到高位逐列進行計算。0和0相加是0，0和1相加是1，1和1相加是0但要產生一個進位1，加到下一列。最高位相加后產生的進位則進到最低位，也就是循環(huán)進位。,-20,UDP協(xié)議的差錯檢測,-21,TCP協(xié)議的差錯檢測,檢

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

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

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

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

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

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

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

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

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

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

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

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