第四章數據鏈路控制數據鏈路層定義和功能差錯控制流量控制常用的數據鏈路層協議

為什么要設計數據鏈路層？在原始的物理傳輸線路上傳輸數據信號是有差錯的，存在一定的誤碼率；設計數據鏈路層的目的就是如何在有差錯的線路上，進行無差錯傳輸。向網絡層提供高質量的服務。從網絡參考來看，物理層之上的各層都有改善數據傳輸質量的要求，數據鏈路層是重要的一層。4.1 定義和功能要解決的問題：如何在有差錯的線路上，進行無差錯傳輸。ISO關于數據鏈路層的定義：數據鏈路層的目的是為了提供功能上和規程上的方法，以便建立、維護和釋放網絡實體間的數據鏈路。數據鏈路：從數據發送點到數據接收點（點到點pointtopoint）所經過的傳輸途徑。

虛擬數據通路，實際數據通路分組和幀的關系二、數據鏈路層基本功能數據鏈路控制規程為使數據能迅速、正確、有效地從發送點到達接收點所采用的控制方式。數據鏈路層協議應提供的最基本功能：數據在數據鏈路上的正常傳輸（建立、維護和釋放）幀定界（幀同步）差錯控制流量控制尋址數據鏈路層協議的位置幀分組幀分組數據鏈路連接數據鏈路層為網絡層提供三種基本服務：無確認無連接服務

由上層完成差錯控制，適合于誤碼率低、實時性要求高的場合，如大部分有線局域網。有確認無連接服務進行簡單的差錯控制。適用于不可靠的信道，如無線網。面向連接確認服務在發送前需要建立連接，保證了幀的正確按序傳輸，適合于可靠性要求較高的場合。適合于大多數廣域網。應答方式正向應答:只對正確的信息應答。負向應答:只對錯誤的信息應答。雙向應答:既對正確的信息應答，也對錯誤的信息應答。問題1：在數據鏈路層，最常采用哪種應答方式？問題2：在數據傳輸過程中，數據會出現哪些情況？正向應答工作方式A0D0D1A1D0D0A0D1A1D1啟動計時器計時器超時啟動計時器計時器超時D0A0D1A1D1A1(1)正常的數據傳送 （2）數據幀丟失及出錯（3）應答幀丟失4.2成幀（Framing）將比特流分成離散的幀，并計算每個幀的校驗和。成幀方法：1）字符計數法在幀頭中用一個域來表示整個幀的字符個數缺點：若計數出錯，對本幀和后面的幀有影響。 因此很少采用。555343224521355成幀（2）2）帶字符填充的首尾字符定界法用DLESTX標示幀的開始用DLEETX標示幀的結束用DLEDLE標示傳送數據信息中的DLE例如：信息DLESTXADLEBDLEETX在網絡中傳送時表示為：DLESTXDLEDLESTXADLEDLEBDLEDLEETXDLEETX

缺點：局限于8位字符和ASCII字符傳送，也不被普遍采用。成幀（3）3）帶位填充的首尾標記定界法幀的起始和結束都用一個特殊的位串“01111110”，稱為標記(flag)“0”比特插入刪除技術，在傳送的數據信息中每遇到5個連續的1在其后加0例如：0110111111011111001在網絡中傳送時表示為：01111110011011111010111110001011111104）物理層編碼違例法只適用于物理層編碼有冗余的網絡，如曼徹斯特編碼注意：在很多數據鏈路協議中，使用字符計數法和一種其它方法的組合。4.3差錯控制差錯出現的特點：隨機，連續突發（burst）差錯產生的原因信道的電氣特性引起信號幅度、頻率、相位的畸變；信號反射；串擾；閃電、大功率電機的啟停等。

出錯情況幀（包括發送幀和響應幀）出錯幀（包括發送幀和響應幀）丟失差錯控制的目的保證幀正確，按序送交上層。在接收方能夠判斷接收的數據是否正確，若錯誤還可能要恢復錯誤。差錯控制的方法自動糾錯機制檢錯反饋重發機制差錯控制的方法糾錯碼和檢錯碼碼字codeword一個幀包括m個數據位，r個校驗位，稱為n

位碼字（n=m+r）。

糾錯碼error-correctingcode加入了足夠多的冗余位，使接收方不僅知道有差錯發生，并知道哪些位發生差錯。檢錯碼error-detectingcode加入了冗余位，使接收方知道有差錯發生，但不知道什么差錯，然后請求重發。

海明定理海明距離兩個編碼的海明距離：兩個編碼不相同位的個數。編碼方案的海明距離：編碼方案中任兩個編碼海明距離的最小值。例：0000000000與0000011111的海明距離為5海明定理為檢測d位錯，編碼方案的海明距離應至少為d+1；當發生d位錯時，不會由一種合法編碼變為另一種合法編碼。為糾正d位錯，編碼方案的海明距離應至少為2d+1；當發生d位錯時，出錯編碼仍然最接近于原始的正確編碼。差錯碼舉例奇偶校驗碼在數據后填加一個奇偶位（paritybit）例：使用偶校驗（“1”的個數為偶數） 10110101 ——> 101101011 10110001 ——> 101100010若接收方收到的字節奇偶結果不正確，就可以知道傳輸中發生了錯誤。增加奇偶校驗位后海明距離由1變為2，因此可以檢查出一位二進制位的差錯循環冗余碼(CRC)循環冗余碼（CRC碼，多項式編碼）110001，表示成多項式x5+x4+1生成多項式G(x)發方、收方事前約定；生成多項式的高位和低位必須為1生成多項式必須比傳輸信息對應的多項式短。CRC校驗基本思想：CRC碼（即校驗和）加在幀尾，使帶CRC碼的幀的多項式能被G(x)除盡；接收方接收時，用G(x)去除它，若有余數，則傳輸出錯。設G(x)為r階，在幀的末尾加r個0，使幀為

m+r位，相應多項式為xrM(x)；按模2除法用對應于G(x)的位串去除對應于xrM(x)的位串；按模2減法從對應于xrM(x)的位串中減去余數（等于或小于r位），結果就是要傳送的帶校驗和的多項式T(x)。CRC碼計算算法CRC的檢錯能力發送：T(x)；接收：T(x)+E(x)；余數((T(x)+E(x))/G(x))=0+余數(E(x)/G(x))若余數(E(x)/G(x))=0，則差錯不能發現；否則，可以發現。四個多項式已成為國際標準CRC-12 =x12+x11+x3+x2+x+1CRC-16 =x16+x15+x2+1CRC-CCITT =x16+x12+x5+1CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1硬件實現CRC校驗。循環冗余校驗法CRC碼計算算法檢驗和(checksum)算法檢驗字段初值置0；數據拆分成與檢驗字段等長的分片，不足部分補0；將所有分片逐位取反，并連續累加，丟棄最高進位；計算結果置入檢驗字段；接收段執行相同的過程，并將計算結果和傳輸過來的檢驗和進行比較以決定數據是否出現差錯；適用于高層協議，如IP、TCP、UDP等；檢驗和算法舉例待傳輸數據為：10010100,01110110,1100計算過程~(10010100)+~(01110110)=1111010011110100+~(11000000)=00110011帶檢驗和的傳輸數據是10010100,01110110,1100001100114.4 流量控制假設單工傳輸發送方無休止工作（要發送的信息無限多）；接收方無休止工作（緩沖區無限大）；發送數據的速率低于接收數據的速率；通信線路（信道）不損壞或丟失信息幀（無錯）。工作過程發送程序取數據，構成幀，發送幀；接收程序等待，接收幀，送數據給高層。單工停等協議（理想情況）增加約束條件：接收方不能無休止接收。例如：緩沖區數量有限，接收速率比發送速率低等。解決辦法：

接收方每收到一個幀，給發送方回送應答。工作過程發送程序取數據，成幀，發送幀，等待響應幀；接收程序等待，接收幀，數據送高層，發送應答幀。單工停等協議（無錯情況）（a）簡單停等協議；（b）帶流量控制停等協議增加約束條件：信道（線路）有差錯，信息幀可能損壞或丟失。解決方法常使用正向應答+重發機制來解決差錯控制。數據序號采用循環序號機制。應答幀的兩種方式：單幀應答：應答序號為某一個正確幀的序號成批應答：應答序號為下一個期望接收的序號通常采用附載應答方式：將數據幀攜帶應答信息的通信方式稱為附載應答。可以把應答幀的序號加在信息幀中一并發送，以提高效率。單工停等協議（有錯情況）數據幀在鏈路上傳輸的可能情況從網絡層取數，成幀發送幀幀到否應答到否超時否重復否正確否接收幀，送網絡層發應答發送幀應答幀YNYNYNNY定時器丟棄丟棄NY有噪聲信道的單工停等協議示意圖停等協議效率連續ARQ協議工作原理連續停等協議是指不需要收到應答幀就可連續不斷的發下面的幀出錯后處理全部重發流水線協議當一幀出錯時，需重發出錯幀之后的所有幀；接收方的緩沖區數量只需要一個。選擇重發流水線協議當一幀出錯時，只重發出錯幀；接收方的緩沖區數量足夠多。連續ARQ協議的工作原理滑動窗口協議滑動窗口協議是對連續停等協議的改進，它能夠控制已發送但未確認的數據幀的個數（滑動窗口的大小）。發送窗口窗口尺寸：允許連續發送未應答的幀的個數數據允許發送的條件：上界－下界<窗口尺寸窗口滑動的條件窗口上限移動：發送數據幀；窗口下限移動：收到應答幀滑動窗口協議（接收窗口）接收窗口窗口尺寸：允許連續接收未處理的幀的個數數據允許接收的條件：數據序號落在接收窗口中窗口滑動的條件發送應答幀后上下界同時移動窗口大小與序號關系出錯全部重傳WT>WR

，WR=1WT≤2n-1

選擇性重傳WT

=WR

WR≤2n-14.5 常用的數據鏈路層協議面向字符的鏈路層協議ISO的IS1745，基本型傳輸控制規程及其擴充部分（BM和XBM）IBM的二進制同步通信規程（BSC）DEC的數字數據通信報文協議（DDCMP）PPP—Point-to-PointProtocol，Internet的協議。4.5 常用的數據鏈路層協議面向比特的鏈路層協議IBM的SNA使用的數據鏈路協議SDLC（SynchronousDataLinkControlprotocol）；ANSI修改SDLC，提出ADCCP（AdvancedDataCommunicationControlProcedure）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作為X.25網絡接口標準的一部分，后來改為LAPB。高級數據鏈路控制規程HDLCHDLC的組成幀結構（語法）規程元素（語法）規程類型（語義）使用HDLC的語法可以定義多種具有不同操作特點的鏈路層協議。HDLC的描述數據站：主站，次站，組合站鏈路構型：平衡型和非平衡型操作模式：正規響應模式，異步響應模式，異步平衡模式HDLC的幀結構定界符01111110空閑的點到點線路上連續傳定界符，說明物理連接已經建立，能夠建立數據鏈路。地址字段（Address）多終端線路，用來區分終端；點到點線路，有時用來區分命令和響應。若地址是接收該幀站的地址，則該幀是命令幀；若地址是發送該幀站的地址，則該幀是響應幀。HDLC的幀結構（續）控制字段（Control）8b：用作序號、確認和其它目的數據字段（Data）任意信息，任意長度（長度由上層控制）校驗和（Checksum）CRC校驗生成多項式：CRC-CCITT=x16+x12+x5+1HDLC幀的類型幀類型信息幀（Information）完成信息傳送。監控幀（Supervisory）差錯控制和流量控制。無序號幀（Unnumbered）鏈路控制管理。控制字段幀的類型及相應的信息用控制域的字段表示；信息幀序號（Seq）：滑動窗口技術，3位序號，發送窗口大小為7捎帶確認（Next）：下一個希望接收到的幀探詢/結束P/F位（Poll/Final）HDLC中的監控幀監控幀類型“0”表示確認幀RR（RECEIVEREADY），接收準備確認。類型“1”表示否定性確認幀REJ（REJECT），對應于出錯全部重傳類型“2”表示接收未準備好RNR（RECEIVENOTREADY）類型“3”表示選擇拒絕SREJ（SELECTIVEREJECT），對應選擇性重傳HDLC和ADCCP允許選擇拒絕，SDLC和LAPB不允許。HDLC中的無序號幀無序號幀可以用來傳控制信息，也可在不可靠無連接服務中傳數據。Type和Modifier聯合表示不同類型的無序號幀；命令DISC（DISConnect）SNRM（SetNormalResponseMode）SARM（SetAsynchronousResponseMode）SABM（SetAsynchronousBalancedMode）HDLC和LAPB使用。FRMR（FRaMeReject）無序號確認UA（UnnumberedAcknowledgement）對控制幀進行確認，用于確認模式建立和接受拆除命令。UI（UnnumberedInformation）HDLC的功能組合三種站，兩種構型，三種操作模式，以及規程元素中定義的各種幀的各種組合產生多種鏈路層協議。HDLC定義了選擇構成鏈路層協議的良序結構：選擇站構型——>基本操作模式——>基本幀種類——>12種任選功能——>得到協議X.25協議（自學）X.25協議分組級，PLP幀級，X.25LAP（LinkAccessProcedure），X.25LAPB（Balanced）物理級，X.21“X.25協議規程使用HDLC規程的原理和術語”X.25LAP：HDLC非平衡規程幀的基本清單+任選功能2、8、12，也可組成主站—次站式平衡規程。X.25LAPB：HDLC組合站平衡規程幀的基本清單+任選功能2、8、11、12。因此，X.25LAP、LAPB是HDLC的子集。X.25的幀格式與HDLC完全相同X.25鏈路級的命令和響應X.25的鏈路層協議LA