1、第4章 數(shù)據(jù)鏈路層4.1 數(shù)據(jù)鏈路層概述4.1.1 數(shù)據(jù)鏈路層的功能數(shù)據(jù)鏈路層的功能是為網(wǎng)絡(luò)層提供服務(wù)。最主要的服務(wù)是將數(shù)據(jù)從源計算機的網(wǎng)絡(luò)層傳輸?shù)侥繕擞嬎銠C的網(wǎng)絡(luò)層。1. 鏈路管理鏈路管理的主要功能是數(shù)據(jù)鏈路的建立、維持和釋放。2. 幀定界和同步幀定界是指在每個字段之間進行標識和分界。幀同步是指雙方應(yīng)能從收到的比特流中準確的區(qū)分出一幀的開始和結(jié)束。3. 流量控制（滑動窗口機制）流量控制提供保持發(fā)送和接收同步的方法和過程。發(fā)送方發(fā)送數(shù)據(jù)的速率不能大于接收方的接收能力。4. 差錯校驗與恢復包括對差錯的檢驗、對正確信息的接收以及對出差錯的信息請求再次傳送等。5. 區(qū)分數(shù)據(jù)和控制信息由于數(shù)據(jù)和控制信

2、息都是在同一信道中傳送的，而在許多情況下，數(shù)據(jù)和控制信息處于同一幀中，因此要有相應(yīng)的措施使收方能夠?qū)⑺鼈儏^(qū)分開來。6. 透明傳輸透明傳輸是指不管所傳輸?shù)臄?shù)據(jù)是什么樣的比特組合，都應(yīng)當能夠在鏈路上傳輸，7. 尋址在多點連接的情況下，必須保證每一幀都能送到正確的目的站。4.1.2 成幀數(shù)據(jù)鏈路層從網(wǎng)絡(luò)層獲取到分組，然后將這些分組封裝到幀中以便傳輸。每一幀包含一個幀頭、一個凈荷域，以及一個幀尾。幀管理構(gòu)成了數(shù)據(jù)鏈路層工作的核心。1. 字符計數(shù)法字符計數(shù)法利用頭部中的一個域來制定該幀中的字符數(shù)。2. 含字節(jié)填充的分界符法（發(fā)送方和接收方要用相同的編碼原則）含字節(jié)填充的分界符法讓每一幀都用一些特殊的字符

3、作為開始和結(jié)束。這些特殊的字符叫做標志字節(jié)（FLAG）。兩個連續(xù)的標志字節(jié)代表了當前幀的結(jié)束和下一幀的開始。這種方法不適宜傳輸數(shù)據(jù)中包含二進制數(shù)的幀，因為在包含二進制數(shù)的幀中很可能出現(xiàn)與FLAG相同的bit序列。一種方法是在二進制數(shù)中偶然出現(xiàn)的FLAG前再插入一個ESC轉(zhuǎn)義字節(jié)，這種方法稱為字節(jié)填充法。3. 含位填充的分界標志法含位填充的分界標志法允許數(shù)據(jù)幀包含任意長度的位，也允許每個字符有任意長度的位。每一幀的開始和結(jié)束都有一個特殊的位模式：01111110。當幀中出現(xiàn)一個與幀標志相同的位串01111110，則在連續(xù)5個1后自動插入一個0，即變成01111101，接收方將自動刪除第5個1后的

4、0。標志序列只可能出現(xiàn)在幀邊界上，不可能出現(xiàn)在數(shù)據(jù)中。4. 物理層編碼標志法（局域網(wǎng)中用的比較多；曼徹斯特編碼/差分曼徹斯特編碼）物理層編碼標志法適用于物理介質(zhì)上編碼方法中包含冗余信息的網(wǎng)絡(luò)。高-高電平對和低-低電平對沒有使用，如在二進制編碼中出現(xiàn)則稱為編碼違例，但這兩種違例編碼正好可用作幀界符。4.2 數(shù)據(jù)鏈路層管理機制流量控制和差錯控制是保證數(shù)據(jù)鏈路層實現(xiàn)可靠數(shù)據(jù)傳輸?shù)淖钪饕臄?shù)據(jù)鏈路層管理機制。數(shù)據(jù)鏈路層實現(xiàn)流量控制的一個重要方法是滑動窗口機制。差錯控制的基本方式是確認重發(fā)狀態(tài)。4.2.1 滑動窗口機制發(fā)送窗口用來對發(fā)放進行流量控制，其大小WT表明在收到對方ACK（確認字符）之前的發(fā)送方

5、最多可以發(fā)送多個數(shù)據(jù)幀，落在窗口內(nèi)的數(shù)據(jù)幀是可以連續(xù)發(fā)送的。接受窗口控制那些數(shù)據(jù)幀可以接收，只有到達的數(shù)據(jù)幀的序號落在接受窗口之內(nèi)時才可以被接收，否則將被丟棄掉。捎帶確認是在雙向數(shù)據(jù)傳輸?shù)那闆r下，將確認信息放在自己的數(shù)據(jù)幀的首部字段中捎帶出去。當發(fā)送方收到接收方的確認后，發(fā)送窗口才能向前滑動，滑動長度取決于接收方確認的序號。4.2.2 自動重發(fā)請求相關(guān)概念：重發(fā)：網(wǎng)絡(luò)中采用檢錯碼，無法糾正錯誤，由重發(fā)原來幀的方法來恢復正確的幀。計時器：控制何時重發(fā)。幀序號：防止重發(fā)時接收端收到的重復的幀，序號還用于接收時排序。效率的計算方法：有效數(shù)據(jù)/全部數(shù)據(jù) or 有效時間/全部時間1. 空閑重發(fā)請求（停止

6、等待協(xié)議）（發(fā)送窗口WT=1，接收窗口WR=1）幀編號采取一位二進制。停止等待協(xié)議的信道利用率：信道利用率=（發(fā)送延時+傳播延時）/（發(fā)送延時+傳播延時+反饋信息傳播延時+反饋信息發(fā)送延時）發(fā)送延時=數(shù)據(jù)塊長度/信道帶寬傳播延時=信道長度/電磁波在信道上的傳播速率設(shè)信道容量為B，幀長度為L，信道長度為S，傳播速率為V，反饋信息數(shù)據(jù)長度為M。信道利用率=（L/B+S/V）/（L/B+2*S/V+M/B）實現(xiàn)過程：(1) 發(fā)送方每次僅將當前信息幀作為待確認幀保留在緩沖存儲器中；(2) 當發(fā)送方開始發(fā)送信息幀時，隨機啟動計時器；(3) 當接收方收到無差錯信息幀后，即向發(fā)送方返回一個確認幀；(4) 當

7、接收方檢測到一個含有差錯的信息幀時，便舍棄該幀；(5) 若發(fā)送方在規(guī)定時間內(nèi)收到確認幀，即將計時器清零，繼而開始下一幀的發(fā)送；(6) 若發(fā)送方在規(guī)定時間內(nèi)未收到確認幀（即計時器超時），則應(yīng)重發(fā)存于緩存器中的待確認信息幀。停止等待協(xié)議的算法和程序見附件。優(yōu)點：所需的緩沖存儲空間最小，多用于簡單終端的環(huán)境。2. 連續(xù)重發(fā)請求（退回N算法）（發(fā)送窗口WT=7，接收窗口WR=1）實現(xiàn)過程（不發(fā)生傳輸差錯情況下）：(1) 發(fā)送方連續(xù)發(fā)送信息幀而不必等待確認幀的返回；(2) 發(fā)送方在重發(fā)表中保存所發(fā)送的每一個幀的備份；(3) 重發(fā)表按先進先出（FIFO）隊列規(guī)則操作；(4) 接收方對每一個正確收到的信息幀

8、返回一個確認幀；(5) 每一個確認幀包含一個唯一的序號，隨相應(yīng)的確認幀返回；(6) 接收方保存一個接受次序表，它包含最后正確收到的信息幀的序號；(7) 當發(fā)送方收到相應(yīng)的信息幀的確認后，從重發(fā)表中刪除該信息幀的備份；(8) 當發(fā)送方檢測出失序的確認幀（即第N號信息幀和第N+2號信息幀的確認幀返回，而N+1號的確認幀未返回）后，便重發(fā)未被確認的信息幀。優(yōu)點：鏈路傳輸效率大大提高。缺點：需要更大的緩沖存儲空間。出現(xiàn)差錯情況下的退回N策略：退回N的算法和程序見附件。3. 選擇重發(fā)請求（發(fā)送窗口WT=4，接收窗口WR=4）選擇重發(fā)協(xié)議在退回機制的基礎(chǔ)上做了如下改進：接受窗口WR>1，這樣就可以接

9、收和保存正確達到的失序幀；出現(xiàn)傳輸差錯時只重發(fā)出錯的幀，后續(xù)的正確到達的幀不再重發(fā)。這樣可以提高利用率。優(yōu)點：避免重復傳送那些本已得到正確傳輸?shù)膸Ｈ秉c：在接收端要設(shè)置具有相當容量的緩存空間。選擇重發(fā)協(xié)議的算法和程序見附件。4.3 差錯控制能校驗差錯的編碼稱為檢錯碼，可以糾錯的編碼稱為糾錯碼。差錯控制用的最廣泛的方式還是反饋重發(fā)糾錯。發(fā)送端計算檢錯碼并隨信息一起發(fā)送，接收端按照同樣的方式計算，若發(fā)現(xiàn)錯誤后反饋給發(fā)送端，發(fā)送端重發(fā)信息。4.3.1 奇偶校驗發(fā)送方根據(jù)發(fā)送的字符“0”和“1”的個數(shù)確定一個校驗位“0”和“1”，接收方檢查此位是否還保持數(shù)據(jù)位的正確關(guān)系，以判斷是否重發(fā)。奇偶校驗碼是一

10、種通過增加冗余位使得碼字中“”的個數(shù)為奇數(shù)或偶數(shù)的編碼方法，是一種檢錯碼。1. 水平奇偶校驗水平奇偶校驗又稱為橫向奇偶校驗,它是對各個信息段的相應(yīng)位橫向進行編碼,產(chǎn)生一個奇偶校驗冗余位。若每個信息段就是一個字符的話,這里的q就是發(fā)送的信息塊中的字符數(shù)。水平奇偶校驗的編碼效率為R=q/(q+1)。2. 垂直奇偶校驗垂直奇偶校驗又稱為縱向奇偶校驗,它是將要發(fā)送的整個信息塊分為定長p位的若干段(比如說q段),每段后面按"1"的個數(shù)為奇數(shù)或偶數(shù)的規(guī)律加上一位奇偶位。垂直奇偶校驗方法的編碼效率為R=p/(p+1)。水平或垂直奇偶校驗只能檢驗出奇數(shù)個錯誤而不能檢驗出偶數(shù)個錯誤。3. 水

11、平垂直奇偶校驗水平垂直奇偶校驗的編碼效率為R=pq/(p+1)(q+1)。水平垂直奇偶校驗?zāi)軝z出以下類型的錯誤：(1) 可檢出某行、某列所有的奇數(shù)個錯誤(2) 能發(fā)現(xiàn)大部分偶數(shù)個錯誤(3) 能發(fā)現(xiàn)長度不大于N+1（N為行數(shù)，即碼字長度）的突發(fā)性錯誤(4) 通過水平垂直奇偶校驗碼不僅可以檢測出一位錯誤，還可以糾正一位錯誤海明碼，見附件。4.3.2 循環(huán)冗余檢驗(CRC,多用于局域網(wǎng)和廣域網(wǎng))在數(shù)據(jù)后面附加上用于差錯檢驗的冗余碼，在數(shù)據(jù)鏈路層的幀結(jié)構(gòu)中成為幀校驗序列。冗余的位數(shù)常有12、16和32位，一般要附加的用于校驗的冗余碼的位數(shù)越多，檢錯能力就越強，但傳輸?shù)念~外開銷也就越大。工作原理：舉例：

12、注：冗余碼的位數(shù)是G(x)的最高次數(shù)項的次數(shù)，即G(x)的位數(shù)減1CRC-16 G（x）= x16+x15+x2+1CRC-CCITT G（x）= x16+x12+x5+1CRC-32 G（x）= x32+x26+x23+x22+x16+x12+x11+ x10+x8+x7+x5+x4 + x2+x+1 4.3.3 校驗和校驗和是針對一個數(shù)據(jù)塊（包）進行處理的。在網(wǎng)絡(luò)通信系統(tǒng)中，隨著每一個數(shù)據(jù)塊（包）一起發(fā)送一個校驗和，目的是為接收方的計算機進行差錯檢驗。校驗和的計算機方法有很多種，但發(fā)送方和接收方必須采用相同的方法。4.4 數(shù)據(jù)鏈路層協(xié)議4.4.1 HDLC幀格式和操作方式1. HDLC幀的

13、格式注：8比特=1字節(jié)標志8比特：標識符“01111110”，發(fā)送方“0比特插入”，接收方“0比特刪除”。地址8比特：非平衡配置時總是寫入從站地址，平衡配置時總是寫入應(yīng)答站的地址。當?shù)刂啡珵椤?”時表示廣播地址，全為“0”時無效。控制8比特：定義不同類型的幀，進行鏈路的建立與拆除、信息的傳輸以及流量和差錯的控制等。信息不定長，信息字段攜帶用戶數(shù)據(jù)。幀校驗序列16比特：采用CRC，生成多項式是CRCCCITT，校驗范圍包括地址字段到信息字段的全部比特。2. 三種類型的幀(1) 信息幀I控制字段的第0比特為“0”，便表示該幀為信息幀。信息幀包含信息字段，用于傳輸數(shù)據(jù)。N(S)是發(fā)送序號，表示當前發(fā)

14、送的數(shù)據(jù)幀的序號。N(R)是接收序號，表示該站期待接收的下一幀的序號。 P/F是探詢（Poll）和終止（Final）位。P=1表示主站詢問，F(xiàn)=1表示響應(yīng)終止。(2) 監(jiān)督幀S若控制字段的第1、2比特為1、0，則對應(yīng)的幀為監(jiān)督幀。監(jiān)督幀共有四種，取決于第3位、第4位比特的值。RR（Receive Ready）幀，SS=00， 接收準備就緒。RNR（Receive Not Ready）幀，SS=10，接收未準備好，暫停接收。REJ（Reject）幀，SS=01，拒絕。否認N(R) 起的所有幀。 SREJ（Select Reject）幀，SS=11，選擇拒絕。只否認N(R)幀。以上四種監(jiān)督幀，前三

15、種用于連續(xù)ARQ協(xié)議中，而最后一種只用于選擇重發(fā)ARQ協(xié)議中。所有的監(jiān)督幀都不包含要傳送的數(shù)據(jù)信息。(3) 無編號幀U若控制字段的第1、2比特都是1時，這個幀就是無編號幀。無編號幀本身不帶編號，而是用5位來表示不同功能的無編號幀。可以定義出32種附加命令和附加響應(yīng)功能，目前已定義了15種無編號幀。無編號幀主要起控制作用，在需要時隨時發(fā)出。3. HDLC的操作方式三種類型的通信站：主站、次站和復合站。(1) 主站：在鏈路中用于控制目的的站成為主站。功能：發(fā)送命令幀、數(shù)據(jù)信息幀和響應(yīng)幀；系統(tǒng)初始化、流量控制以及差錯控制。(2) 次站在鏈路中受主站控制的站。功能：接收主站發(fā)來的命令幀，向主站發(fā)送響應(yīng)

16、幀，并配合主站控制鏈路。(3) 復合站既具備主站功能又具備次站的功能。兩種基本配置：非平衡配置和平衡配置。(1) 非平衡配置：由一個主站和一個或多個次站構(gòu)成。主站控制次站實現(xiàn)鏈路管理。信道可以是點對點鏈路，也可以是多點共享的鏈路。可支持全雙工或半雙工通信。(2) 平衡配置：由兩個復合站點對點地互連而成。兩個站點地位均等，負有同等的鏈路控制責任。信道可支持全雙工或半雙工通信。三種操作方式：正常響應(yīng)模式（NRM）、異常響應(yīng)模式（ARM）和異步平衡模式（ABM）。(1) 正常響應(yīng)模式（用于非平衡配置）：主站具有選擇、輪詢次站的能力，并可向次站發(fā)送命令或數(shù)據(jù)；次站只有在主站輪詢時才能作出響應(yīng)。(2) 異常響應(yīng)模式（用于非平衡配置）：主站具有初始化鏈路，差錯校正、鏈路的建立和釋放等功能；次站可以主動傳輸數(shù)據(jù)。(3) 異步平衡模式（用于平衡配置）：任一組合站均可控制鏈路，主動傳送數(shù)據(jù)。4.4.2 PPP協(xié)議1. PPP協(xié)議組成一個將IP數(shù)據(jù)報封到串行鏈路的方法異步鏈路或同步鏈路。一個用來建立、配置和測試數(shù)據(jù)鏈路的鏈路控制協(xié)議（LCP）。一套網(wǎng)絡(luò)控制協(xié)議NCP，支持不同的網(wǎng)絡(luò)層協(xié)議。2. PPP幀格式PPP幀格式和HDLC幀格式相似，二者主要的區(qū)別是：PPP是面向字符的，而HDLC是面向位的。PPP協(xié)議不是面向比特的，因而所有的PPP幀長度