第3章-數據鏈路層

1、計算機網絡計算機網絡第第3 3章章 數據鏈路層數據鏈路層 n數據鏈路層的服務與功能n成幀方法n差錯控制與流量控制n差錯檢測和糾正n基本數據鏈路層協(xié)議-滑動窗口機制n數據鏈路層協(xié)議實例數據鏈路層的服務與功能（數據鏈路層的服務與功能（1 1） 使用物理層提供的服務在通信信道上發(fā)送和接收比特。完成功能包括：n向網絡層提供一個定義良好的服務接口n處理傳輸錯誤n調節(jié)數據流，確保慢速的接收方不會被快速的發(fā)送方淹沒 路由器的數據鏈路層示意數據鏈路層的服務與功能（數據鏈路層的服務與功能（2 2） n無確認無連接當錯誤率很低,恢復留給高層,對實時通信很適合.絕大多數局域網采用，以太網n有確認無連接每一幀都要獨立

2、確認，超時重發(fā),使用于不可靠信道,如無線系統(tǒng)，WiFin有確認有連接建立連接（初始化變量和計數器）、傳輸一個或多個幀、釋放連接。為網絡層進程提供了可靠的位流.3種可能的服務數據鏈路層的服務與功能（數據鏈路層的服務與功能（3 3） 成幀方法成幀方法 n字節(jié)計數法n字節(jié)填充的標志字節(jié)法n比特填充的標志比特法 n物理層編碼違例法 成幀方法成幀方法- -字節(jié)計數法字節(jié)計數法 以特殊字符表征幀的起始和結束，并以一個專門字段來標明幀內的字節(jié)數。 典型實例是DEC公司的數字數據通信報協(xié)議DDCMP（Digital Data Communications Message Protocol）。成幀方法成幀方法-

3、標志字節(jié)填充法（標志字節(jié)填充法（1 1） 用特殊的字符作為幀頭和幀尾，起始字符 DLE STX，結束字符DLE ETX，接收方一旦丟失了幀信息，只要查找DLE STX就可重新確定幀邊界。字符填充局限于8位字符和ASCII字符傳送。 透明傳輸策略：當數據中含有DLE時，在DLE前面加上DLE幀尾SYN SYN DLE STX A DLE DLE B DLE DLE C DLE ETX幀首同步字符數據傳輸幀填充字符字符填充成幀方法成幀方法- -標志字節(jié)填充法（標志字節(jié)填充法（2 2） 成幀方法成幀方法 -PPP協(xié)議采用字節(jié)填充方案成幀方法成幀方法-標志位填充法標志位填充法 幀 的 起 始 和 結

4、束 都 用 一 個 特 殊 的 位 串“01111110”，稱為標記（flag）。在面向二進制位的同步串型通信中常使用帶位填充的首尾標志格式，如HDLC 。 透明傳輸策略：“0”插入法 幀首幀首數據數據幀尾幀尾011111100111111001111101101111100填充位填充位 “0”比特插入刪除技術比特插入刪除技術成幀方法成幀方法- -物理層編碼違例法n借用一些違法編碼序列來定界幀的起始與終止，局域網IEEE 802標準中就采用了這種方法。違法編碼法不需要任何填充技術，便能實現數據的透明性。 數據0：低高電平對數據1：高低電平對曼徹斯特編碼差錯控制和流量控制（1）n確保可靠傳輸 反

5、饋確認 超時重傳 幀編號（區(qū)分原始幀和重傳幀）n流量控制 基于反饋的流量控制 基于速率的流量控制（限制發(fā)送方傳輸數據的速率）流量控制流量控制 流量控制（Flow Control）規(guī)定了對幀進行發(fā)送和跟蹤的方法，以及該站點如何進行錯誤控制。決定幀在什么時候可以或不可以被發(fā)送，什么時候這些幀可以被第二次發(fā)送。流量控制協(xié)議確保所有的相關幀能夠精確和有序地到達目的地。 典型情況下，流量控制是發(fā)送方、接收方某些連續(xù)層次的多個實體交互作用的結果，例如OSI模型中數據鏈路層和網絡層的交互關系。流量控制也存在于較高層協(xié)議如TCP，實際上流量控制存在于不同的模型以及不同的層之間。差錯控制方法差錯控制方法 從差錯

6、控制的角度，對于傳輸的信號，利用檢糾錯基本原理進行編碼來降低差錯的發(fā)生，利用差錯控制編碼方法進行差錯控制的常用方式主要有如下幾種： n 自動請求重發(fā)（ARQ）方式n 前向糾錯（FEC）方式n 混合糾錯（HEC）方式自動請求重發(fā)（自動請求重發(fā)（ARQARQ）方式）方式 發(fā)送端發(fā)送出可以發(fā)現錯誤的碼字，接收端譯碼若檢測到錯誤，則主動向發(fā)送端發(fā)出請求，要求重發(fā)以便糾錯。這種系統(tǒng)要求有反饋信道且發(fā)送端和接收端都有緩存器。前向糾錯（FEC）方式 發(fā)送端發(fā)出的碼字是具有一定糾錯能力的碼字。在接收端譯碼后不僅可以發(fā)現錯碼，而且能夠判斷錯碼所在的位置并自動糾正。這種方法不需反饋信道，實時性好，傳輸效率較高，但

7、糾錯編碼方法和設備較復雜?；旌霞m錯（HEC）方式 實際應用中，可以結合使用ARQ方式和FEC方式。即在傳輸錯碼較少且接收端能糾正時，自動糾正錯誤；在錯碼較多、超出糾正能力但尚能檢測時，采用自動請求重發(fā)方式，請求發(fā)送端重傳，直到正確接收為止。該方式大大提高了通信的可靠性。差錯檢測和糾正n前向糾錯（FEC）利用糾錯碼n反饋重傳 利用檢錯碼n糾錯碼的冗余量檢錯碼的冗余量 對信道質量較好的有線鏈路一般都用檢錯碼 對信道質量較差的無線鏈路采用糾錯碼糾錯碼出現在物理層、鏈路層和高層多個層次檢錯碼更是經常應用于鏈路層、網絡層和傳輸層檢錯糾錯的基本原理檢錯糾錯的基本原理 檢糾錯的基本思想就是，在被傳送的信息中

8、附加一些冗余信息，使信息傳輸碼元和冗余傳輸碼元兩者之間建立某種校驗監(jiān)督關系，當傳輸過程產生錯誤時，在接收端可利用監(jiān)督關系進行檢測并予以糾正。這種檢糾錯的能力是用信息量的冗余度來換取的。n碼距和檢糾錯能力的關系n編碼效率 碼距和檢糾錯能力的關系n碼重：指碼字中非零碼元的數目，即“1”的個數。碼字（C表示）由許多碼元組成，碼字中碼元的個數稱為碼長（n表示）。n碼距：也稱海明距離（Hamming distance），是一個碼組中任意兩碼字之間對應位上碼元取值不同的數目。用d表示，即10)(),(npjpipjiccccd意義任意兩個碼字的海明距離為d,則需要d個一位錯誤才能將一個碼字變成另一個碼字。

9、一種編碼方案的檢錯和糾錯能力與海明距的關系 n為了檢測d個錯誤，需用距離為d+1的編碼方案，因為d個1位錯誤不可能將一個有效碼字變成另一個有效碼字。接收到無效碼字，就知道發(fā)生了傳輸錯誤。n為了糾正d個錯誤，需要一個距離為2d+1的編碼方案，即使發(fā)生了d位錯誤，還是原來的碼字離它最近。從而可以唯一的確定原來的碼字。n若碼組中用于糾t個錯，同時檢e個錯，則距離de+t+1，其中et 糾錯碼4種不同的糾錯編碼n海明碼n二進制卷積碼n里德所羅門碼n低密度奇偶效驗碼糾錯碼-海明碼n設計一種編碼方案 每個碼字有m個報文位和r個校驗位，n=m+r,可以糾正所有的單個錯。 共有2n種符號表示。 其中合法報文（

10、2m個） 任意一個合法報文，發(fā)生單個錯（n位中的任一位都有可能），可能造成n個與合法報文的距離是1的非法碼字 因此編碼方案中，n必須滿足 （n+1）2m=2nn海明的方法（1950）：糾正單個差錯.n碼字中（1,2,4,8)為校驗位;剩下的位是數據.每個校驗位迫使某一組位的奇偶值為偶數或奇數.n當一個碼字到來時,接收方將重新計算所收到的每個校驗位,看是否有正確的奇偶性。 若有錯，將有錯的位置相加，就是錯誤位置.若檢驗出第1位和第4位校驗位有誤，則表示第5位出錯7位ASCII碼編成11位 滿足27+ n* 27=2n校驗位生成方法a1=a3+a5+a7+a9+a11a2=a3+a6+a7+a10

11、+a11a4=a5+a6+a7a8=a9+a10+a11若檢驗出第1位和第4位校驗位有誤，則表示第5位出錯第1個校驗位分別對3,5,7,9,11位做校驗3=1+25=1+4 6=2+47=1+2+49=1+810=2+811=1+2+8糾錯碼-卷積碼（convolution code）卷積碼（n,k,m)不屬于塊碼，主要用來糾隨機錯誤 碼元與前后碼元有一定的約束關系，編碼復雜度可用編碼約束長度m*n來表示。 n個碼元不僅與當前段的k個信息有關，而且與前面的（m1）段信息有關（m為編碼的約束長度）。 已經成為GSM移動電話系統(tǒng)的一部分，在衛(wèi)星通信和802.11中都得到應用。 例 NASA卷積碼

12、第一個被用于1977年旅行者航天飛行任務中的編碼卷積碼的糾錯能力不僅與約束長度有關，還與采用的譯碼方式有關。卷積碼的性能至少不比分組碼差糾錯碼-里德所羅門碼（Reed-Solomon code）線性塊碼，與海明碼不同，對m位符號進行操作，而不是針對單個位處理。類比方案描述：兩個數據點代表一條線，選自同一條線上的額外兩個點充當校驗位，當有一個點出現錯誤，仍然可以通過擬合線恢復這個點。得到廣泛應用，強大的糾錯能力。用在DSL、線纜上的數據通信、衛(wèi)星通信、CD、DVD。加入2t個冗余符號后，可以糾正傳輸符號中的任意t個錯誤。通常和其他編碼結合一起用，如卷積碼。糾錯碼-低密度奇偶校驗碼（LDPC）Ro

13、bert Gallagher 1962年博士論文中提出每個輸出位由一小部分輸入位形成，編碼可以用一個1的密度很低的矩陣表示。接收碼字通過一個近似算法解碼獲得，該算法通過迭代不斷改進接收到的數據域合法碼字的最佳匹配。適用于大塊數據，糾錯能力強。被新的協(xié)議所采納，成為數字視頻廣播、萬兆以太網、電力線網以及新版802.11標準的一部分。檢錯碼檢錯碼n糾錯碼廣泛應用于無線鏈路,而有線鏈路,通常使用檢錯碼.n例如:錯誤率為10-6,1000 位數據塊,需要10位糾錯碼,能糾正1位錯,而用檢錯碼只需1個奇偶位,1M數據位需要的糾錯和檢錯的開銷?三種檢錯碼線性塊碼n奇偶n校驗和n循環(huán)冗余校驗（CRC） 檢錯

14、碼檢錯碼-奇偶校驗奇偶監(jiān)督碼是一種最基本的、最常用的、最簡單的檢錯碼。它可分為奇監(jiān)督碼和偶監(jiān)督碼兩種，基本編碼原理相同。奇偶監(jiān)督碼中，監(jiān)督位僅有1位，設監(jiān)督位為c0，奇偶監(jiān)督碼的編碼規(guī)則是加入c0后，碼字中“1”的個數滿足奇數或偶數，用下式表示： 1200nnccc偶監(jiān)督碼：1201nnccc奇監(jiān)督碼：檢錯碼檢錯碼-二維奇偶監(jiān)督碼 二維奇偶監(jiān)督碼又稱方陣碼，是在奇偶校驗碼的基礎上產生的。它把奇偶監(jiān)督碼的若干碼字排列呈矩陣，每個碼字一行，增加一位監(jiān)督位，再按列的方向增加垂直監(jiān)督位，構成水平垂直奇偶監(jiān)督碼。nInternet校驗和 1.待校驗的相鄰字節(jié)成對組成16比特整數并計算其和的二進制反碼(二

15、進制反碼求和).二進制反碼求和:從低位到高位逐列進行和計算,如果最高位(16位)進位,則得到的結果加1,一直循環(huán)到最高位沒有進位為止.最后把得到的結果取反.2.檢查校驗和,將所有字節(jié),包括校驗和,進行相加并求二進制反碼.如果結果為全1(即二進制反碼算術中的0),檢查通過.簡單的求和，無法檢測出0數據的增加和刪除，保護很弱檢錯碼檢錯碼-校驗和nFletcher校驗和 Fletcher 1982年提出，將數據和位置的乘積添加到總和中，能對數據位置的變化提供更強大的檢測作用。檢錯碼檢錯碼-循環(huán)冗余校驗碼（循環(huán)冗余校驗碼（CRCCRC） 循環(huán)碼又稱為多項式碼，是一種線性分組碼。它是在嚴格的代數學理論基

16、礎上建立起來的，檢糾錯能力非常強，且廣泛應用在計算機網絡和數據通信中。循環(huán)碼除了具有線性分組碼的一般性質外，還有一個顯著的特點就是循環(huán)性，即循環(huán)碼中任一碼字循環(huán)左移（右移）一位或多位所形成的碼字仍舊是循環(huán)碼中的碼字。 循環(huán)碼的編碼 n第一步 若生成多項式G(x)的階是r, 將信息位左移r位，得xrM(x)；n第二步，作模2除法，求余數r(x)；余數由下式獲得： n第三步，根據T(x)=xrM(x)+r(x)，求出碼字。 )()()()(xrxQxGxMxrCRC的檢錯能力分析n接收方:T(x)+E(x)當E(x)/G(x)為0時,錯誤無法檢出(1)1位錯能夠檢出.E(x)=xi(2)兩個獨立的

17、一位錯,E(x)=xi+xj=xj(x i-j+1) 除非i-j很大,要不然E(x)/G(x)!=0.如對于任何k1, rws=1n設窗口序列號分別是0、1、2.MAX-SEQ(2n-1)sws應小于N =2n ,最大未確認幀數是2n-1累計確認（cumulative acknowledgement） 若取sws=N,會導致某些情況下協(xié)議失敗如當發(fā)送0-7號幀,成功，返回ACK=0 又發(fā)送0-7號幀，成功？全部丟失？無法區(qū)分Protocol Using Go-Back-N (3)A sliding window protocol using go-back-n. . .Protocol Usi

18、ng Go-Back-N (4). . .Protocol Using Go-Back-N (5). . .Protocol Using Go-Back-N (6). . .Protocol Using Go-Back-N (7)A sliding window protocol using go-back-n. . .Protocol Using Go-Back-N (8)A sliding window protocol using go-back-n. . .*累計確認的處理*重傳Protocol Using Go-Back-N (9)用于流量控制，diable_network_laye

19、r()阻止網絡層給予太多的工作Protocol Using Go-Back-N (10)Simulation of multiple timers in software. (a) The queuedtimeouts (b) The situation after the first timeout has expired.多個計時器的軟件實現選擇重傳協(xié)議Pipelining and error recovery. Effect of an error when(b) receivers window size is large.選擇重傳協(xié)議非順序接收帶來的問題(a)Initial situ

20、ation with a window of size7(b)After 7 frames sent and received but not acknowledged.(c)Initial situation with a window size of 4.(d)After 4 frames sent and received but not acknowledged. swssws1, 1, rwsrws11舉例說明選擇性重傳在發(fā)送窗口和接收窗口都取7時，在某些情況失效 設 2n = 8，設sws=7, rws = 7； 發(fā)方發(fā)幀 0 - 6，收方全部收到； 接收窗口前移（7 - 5）；

21、現在發(fā)生意外，確認幀全部丟失； 由于超時，發(fā)方重傳幀0； 收方作為新幀接收，并對幀6確認（因為0-6都收 到） 發(fā)送方發(fā)出新幀 7-5， 收方已收過幀 0，丟棄新幀 0，協(xié)議出錯。選擇性拒絕ARQ中，顯然接收窗口不應該大于發(fā)送窗口，當接收窗口尺寸取最大時，rws=sws，明顯地， rws=sws 2n /2=2n-1，只有滿足這個條件才能不發(fā)生混幀的問題。（前后兩個接收窗口不能重疊）Protocol Using Selective Repeat (1)A sliding window protocol using selective repeat. . .Protocol Using Sele

22、ctive Repeat (2)A sliding window protocol using selective repeat. . .發(fā)送過程，可以發(fā)送數據、攜帶ack、或nakProtocol Using Selective Repeat (3)A sliding window protocol using selective repeat. . .Protocol Using Selective Repeat (4). . .Protocol Using Selective Repeat (5). . .Protocol Using Selective Repeat (6). . .P

23、rotocol Using Selective Repeat (7). . .將接收到的數據幀遞交給網絡層，接收窗口滑動Protocol Using Selective Repeat (8). . .檢測到幀錯誤，發(fā)送nak重傳Protocol Using Selective Repeat (9)數據鏈路協(xié)議實例數據鏈路協(xié)議實例 HDLC的幀格式，由標志、地址、控制、信息和幀檢驗序列（FCS）等段構成。 高級數據鏈路控制（HDLC- High-level Data Link Control）是由國際標準化組織ISO于1976年提出制定的面向位的有序鏈路級協(xié)議。 HDLC HDLC幀的類型幀的類

24、型 1 1、信息幀（、信息幀（InformationInformation）；）； 2 2、監(jiān)控幀（、監(jiān)控幀（SupervisorySupervisory）；）； 3 3、無編號幀（、無編號幀（U U幀）幀）數據鏈路協(xié)議實例數據鏈路協(xié)議實例 Internet兩種常見情況下通過廣域網中的SONET光纖鏈路發(fā)送數據包Internet邊緣的電話網絡本地回路上的ADSL鏈路數據鏈路協(xié)議都采用點到點協(xié)議（PPP）RFC1661，1662數據鏈路協(xié)議實例（數據鏈路協(xié)議實例（1)1) Packet over SONET. (a) A protocol stack. (b) Frame relationships數據鏈路協(xié)議實例（數據鏈路協(xié)議實例（2)2) PPP功能處理錯誤、檢測鏈路配置、支持多種協(xié)議、允許身份認證三個主要部分 成幀方法成幀方法 明確地定界一個幀的結束 和下一個幀的開始，也允許進行錯誤檢測。 鏈路控制協(xié)議（鏈路控制協(xié)議（LCPLC