【文章內(nèi)容簡介】 ,則需要d 個位差錯才能將其中一個碼字轉(zhuǎn)換成另一個 . H=3 二、差錯檢測與校正 （ CRC循環(huán)冗余碼） ? 糾錯碼的編碼效率較低，差錯控制經(jīng)常采用檢錯碼＋ ARQ。循環(huán)冗余碼 CRC（ Cyclic Redundancy Code ）是計算機網(wǎng)絡中使用最為廣泛的檢錯碼，又稱為多項式碼。 三、關于數(shù)據(jù) 幀 ? 數(shù)據(jù)鏈路層所傳送的不再是原始的比特流，而應具備相應的語法和語義，以達到可靠傳輸?shù)墓δ堋? ? 數(shù)據(jù)鏈路層將從網(wǎng)絡層接收的分組（ Packet)組成幀后傳送給物理層，通過物理層傳送到對方的數(shù)據(jù)鏈路層。 ? 幀：數(shù)據(jù)鏈路層規(guī)定最小的數(shù)據(jù)傳送邏輯單位 ? 數(shù)據(jù)鏈路層協(xié)議要規(guī)定幀的類型與格式類型包括控制信息幀與數(shù)據(jù)信息幀等，格式則規(guī)定幀所包含的域）。 幀的基本組成 ? 幀定界（開始與結(jié)束） ? 地址字段（用于尋址） ? 幀類型（或長度 /控制）字段 ? 數(shù)據(jù) ? 幀校驗字段（差錯控制） 幀的開始 地址 幀類型或長度 數(shù)據(jù) 幀校驗 幀的結(jié)束 上圖只是幀的一般組成，不同的數(shù)據(jù)鏈路層協(xié)議所規(guī)定的幀格式可能會與其存在微小的區(qū)別。 幀的同步 同步就是標識幀的開始與結(jié)束 常用的幀同步方法： ? 字符計數(shù)法 ? 帶字符填充的首尾界符法 ? 帶位填充的首尾標志法 ? 違例編碼法 字符計數(shù)法 5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6 5 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6 計數(shù) 計數(shù) 計數(shù) 第 1幀 5個字符 第 2幀 5個字符 第 3幀 8個字符 發(fā)送 : 接收 : 第 1 幀正確 ! 第 2 幀不正確 ! 問題 : 出錯之后 ,接收方 與發(fā)送方不同步 ! 無法確定下一幀 的開始位置 .請求 重傳也沒有用處 , 因為目的機器不知 道應該回跳多少 字符開始重傳 . 7出錯 ! 1 1個字符計數(shù) ?? 在幀頭中使用一個字段來標明幀內(nèi)的字符數(shù)， 通常該字段稱為幀長字段。 首尾界符法 ? 每一幀以 ASCII字符序列 DLE STX開始，以 DLE ETX結(jié)束。 ? DLE為 Data Link Escape 的縮寫， STX意味著 Start of Text， ETX代表 End of Text。 ? 其缺點是成幀完全依賴于 8位字符 STX,A,B,GOOD,BYE,ETX A,B,GOOD,BYE 數(shù)據(jù) 組幀 字符填充 ? 在首尾界符法中，由于數(shù)據(jù)中可能會出現(xiàn) DLE STX或DLE ETX，從而干擾幀的正常定界 ? 字符填充法可用于解決上述問題。即發(fā)送端在數(shù)據(jù)中所遇到的 DLE前再插入一個附加的 DLE，而接收端則忽略兩個連續(xù) DLE的前一個。 DLE,STX,A,DLE,B,DLE,ETX DLE,STX,A,DLE,DLE,B,DLE,ETX 網(wǎng)絡層發(fā)出的數(shù)據(jù) 經(jīng)數(shù)據(jù)鏈路層填充后的數(shù)據(jù) 字節(jié)填充圖例 (a) A frame delimited by flag bytes (b) Four examples of byte sequences before and after stuffing. 首尾標記法 ? 每一幀使用一個特殊的位模式“ 01111110”作為開始和結(jié)束標記。 ? 該位模式又稱為 flag ? 位模式允許數(shù)據(jù)幀包含任意個數(shù)的比特，也允許每個字符采用任意比特的編碼。 … Data … 01111110 01111110 位填充 ? 在首尾標記法中，由于數(shù)據(jù)中可能會出現(xiàn)與標記相同的位串，從而干擾幀的正常定界 ? 位填充法可用于解決上述問題。即發(fā)送端在數(shù)據(jù)中若遇到 5個連續(xù)的“ 1”時，則在其后自動插隊入一個“ 0”。該技術簡稱“逢五 1插 0”；接收端則忽略 5個連續(xù)的“ 1”后面的“ 0”，簡稱“逢五 1刪 0” 。 (a) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 (b) 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 (c) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 填充的位 比特填充圖例 (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in receiver’s memory after destuffing. 違例編碼法 ? 采用不可能出現(xiàn)在信息位中的比特編碼作為幀的起始邊界。 ? 在物理層采用特定的比特編碼方法時使用 ? 曼徹斯特編碼中電平的跳變表示 1（低 高）和 0（高 低） ? 高高和低低電平是違例編碼 四、 數(shù)據(jù)鏈路層協(xié)議 — 數(shù)據(jù)鏈路通信的簡單模型 AP1緩存AP2緩存幀 幀數(shù)據(jù)鏈路發(fā)送方接收方主機A主機B完全理想化的數(shù)據(jù)傳輸 完全理想化的數(shù)據(jù)傳輸基于以下兩個假定 ? 假定 1：鏈路 是 理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。 ? 假定 2： 不管發(fā)送方以多快的速率發(fā)送數(shù)據(jù)，接收方總來得及收下，并及時上交主機。 (接收端向主機交付的數(shù)據(jù)速率永遠不會低于發(fā)送端發(fā)送數(shù)據(jù)的速率 ) 停等協(xié)議 ? 停止等待 (stopandwait)協(xié)議是最簡單但也是最基本的數(shù)據(jù)鏈路層協(xié)議。 ? 具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議 ? 仍保留假定 1，但去掉假定 2 ? 鏈路是理想的傳輸信道，即所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失 ? 由接收方控制發(fā)送方的數(shù)據(jù)流 (計算機網(wǎng)絡中流量控制的一個基本方法 )。 停等協(xié)議算法 ? 在發(fā)送結(jié)點： （ 1）從主機取一個數(shù)據(jù)幀； （ 2）將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存； （ 3）將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去； （ 4）等待； （ 5）若收到由接收結(jié)點發(fā)過來的信息 (此信息的格式與內(nèi)容可由雙方事先商定好 )，則從主機取一個新的數(shù)據(jù)幀，然后轉(zhuǎn)到（ 2）。 ? 在接收結(jié)點： （ 1）等待； （ 2）若收到由發(fā)送結(jié)點發(fā)過來的數(shù)據(jù)幀，則將其放入數(shù)據(jù)鏈路層的接收緩存； （ 3）將接收緩存中的數(shù)據(jù)幀上交主機； （ 4）向發(fā)送結(jié)點發(fā)一信息，表示數(shù)據(jù)幀已經(jīng)上交給主機； （ 5）轉(zhuǎn)到 (1)。 停等協(xié)議 ? 兩種數(shù)據(jù)傳輸比較 從 主 機 取 數(shù) 據(jù) 上 交 主 機 DATA1 DATA4 DATA3 DATA2 結(jié)點 A 結(jié)點 B ? 理想信道 從 主 機 取 數(shù) 據(jù) 上 交 主 機 DATA1 DATA2 結(jié)點 A 結(jié)點 B ACK ACK ? 具有簡單流量控制的數(shù)據(jù)鏈路層協(xié)議 從 主 機 取 數(shù) 據(jù) 上 交 主 機 DATA1 DATAn DATA2 結(jié)點 A 結(jié)點 B DATAn+3 DATAn+2 DATAn+1 NAKn+1 ACK ? 流水線協(xié)議 實用的停止等待協(xié)議 ? 前提：去掉兩個假定，即傳輸數(shù)據(jù)的信道不能保證使所傳的數(shù)據(jù)不產(chǎn)生差錯，而且還需對數(shù)據(jù)的發(fā)送端進行流量控制。 ? 流量控制方法：等待發(fā)送 ? 差錯控制：發(fā)送方數(shù)據(jù)幀中加入校驗碼（ CRC），由接收方檢查；若正確，返回 ACK，若出錯，返回 NAK；發(fā)送方根據(jù)收到的返回幀，決定發(fā)送新幀和重發(fā)。 ? 幀丟失處理：超時定時器；以序號標識數(shù)據(jù)幀 ? 優(yōu)點：簡單 ? 缺點：信道利用率低，信道還遠遠沒有被數(shù)據(jù)比特填滿 數(shù)據(jù)幀在鏈路上傳輸?shù)?幾種情況 A B 時 間 送 主 機 送 主 機 Tout 丟失 A B 重傳 送 主 機 放 棄 (a) 正常情況 (b) 數(shù)據(jù)幀出錯 (C) 數(shù)據(jù)幀丟失 (d) 確認幀丟失 A B 出錯 重 傳 送 主 機 重傳 丟失 A B Tout 送 主 機 實用停止等待協(xié)議的算法 ? 在發(fā)送結(jié)點： (1)從主機取一個數(shù)據(jù)幀，送交發(fā)送緩存。 (2)v(S)←0 。 (發(fā)送狀態(tài)變量 v(S)初始化 ) (3)N(S)←v(S) 。 (將發(fā)送狀態(tài)變量值寫入數(shù)據(jù)幀中的發(fā)送序號 N(S)) (4)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。 (這個數(shù)據(jù)幀的副本仍保留在發(fā)送緩存中 ) (5)設置超時計時器。 (選擇適當?shù)某瑫r重傳時間 tout) (6)等待。 (等待以下 (7)和 (8)這兩個事件中最先出現(xiàn)的一個 ) (7)收到確認幀 ACKn， (這里隱含地表示已經(jīng)通過了 CRC的硬件差錯檢測 ) 若 n=1v(S)，則： (已發(fā)送的數(shù)據(jù)幀被接收方確認 ) 從主機取一個新的數(shù)據(jù)