第三章 鏈路層

1、數(shù)據(jù)鏈路層 廣域網(wǎng)的鏈路層：本章 局域網(wǎng)的鏈路層：在局域網(wǎng)中 (物理物理)鏈路鏈路：一條無源的點到點的物理線路，中間沒有任何交換節(jié)點 基于物理層的協(xié)議，可以建立物理線路 （即把多個鏈路通過接口串聯(lián)起來），但要能在這條線路上傳送數(shù)據(jù)，還需要賦予物理鏈路一些基本的功能，可能的功能包括： 鏈路管理：鏈路管理： 數(shù)據(jù)鏈路的建立、維持和釋放 幀同步：幀同步： 在數(shù)據(jù)鏈路層的PDU是幀，幀同步的目的就是要在比特流中準(zhǔn)確區(qū)分一個幀的開始和結(jié)束。 流量控制：流量控制： 收發(fā)數(shù)據(jù)的雙方收發(fā)數(shù)據(jù)的速率匹配 差錯控制：差錯控制： 糾正或檢測數(shù)據(jù)幀中的差錯 區(qū)分?jǐn)?shù)據(jù)和控制信息：區(qū)分?jǐn)?shù)據(jù)和控制信息： 透明傳輸：透明傳輸

2、： 尋址：尋址： 物理鏈路在賦予了這些功能就可實現(xiàn)可靠的數(shù)據(jù)傳輸。為實現(xiàn)這些功能，需要一些必要的規(guī)程來控制數(shù)據(jù)的傳輸，這些規(guī)程就是數(shù)據(jù)鏈路的協(xié)議。 數(shù)據(jù)鏈路數(shù)據(jù)鏈路：物理鏈路加上必要的通信規(guī)程而形成的邏輯鏈路。 數(shù)據(jù)鏈路層協(xié)議數(shù)據(jù)鏈路層協(xié)議：為在不太可靠的物理鏈路上建立數(shù)據(jù)鏈路從而實現(xiàn)可靠的數(shù)據(jù)傳輸而規(guī)定的一些規(guī)程。 最簡單而又最基本的一個數(shù)據(jù)鏈路層協(xié)議是停止等待停止等待協(xié)議協(xié)議停止等待協(xié)議(stop-and-wait)兩機(jī)通過一條鏈路進(jìn)行通信的簡化模型主機(jī)AAP主機(jī)BBP鏈路鏈路層A鏈路層A緩沖區(qū) 一般，數(shù)據(jù)的傳輸受到兩個因素的影響 (A)信道可靠性 (B)發(fā)送和接收能力 理想情況下 (A)

3、信道無差錯,不丟失：無需檢錯重發(fā) (B)接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不會低于發(fā)送端發(fā)送數(shù)據(jù)的速率; 或者緩存無限大 : 無需流量控制 此時無需任何協(xié)議 而在一般情況下，上述情況難以保證。 以下先保留假設(shè)保留假設(shè)A，去掉假設(shè)，去掉假設(shè)B，此時只需要流量控制，即保證收方的緩沖區(qū)不會因為發(fā)方發(fā)送數(shù)據(jù)太快來不及向上層交付而導(dǎo)致溢出。 最簡單的停止-等待協(xié)議進(jìn)行流量控制 發(fā)送方： 1. 從主機(jī)取一個數(shù)據(jù)幀放到緩沖區(qū)后發(fā)送 2. 等待 3. 若收到接收方的確認(rèn)信息，轉(zhuǎn)到 1 接收方 1. 等待 2. 若收到發(fā)送方發(fā)來的數(shù)據(jù)幀，將其放入接收緩沖區(qū)并向上轉(zhuǎn)交 3. 向發(fā)送方發(fā)送一個確認(rèn)消息，表示緩沖區(qū)已空，

4、可以接收下一個數(shù)據(jù) 4. 轉(zhuǎn)到 1 這樣只需要一個數(shù)據(jù)幀的緩沖區(qū)就可以保證無溢出。停止等待協(xié)議data iACKdata i+1發(fā)出對剛收到的發(fā)出對剛收到的數(shù)據(jù)幀的應(yīng)答數(shù)據(jù)幀的應(yīng)答發(fā)出一幀發(fā)出一幀等待，直到收到等待，直到收到ACK才發(fā)送下一幀才發(fā)送下一幀發(fā)送方發(fā)送方接收方接收方 去掉假設(shè)去掉假設(shè)A、 B的一般情況，不僅要流量控制，還要進(jìn)行差錯控制（信道不可靠），幾種情況下的處理方式：實用的停止-等待協(xié)議: (設(shè)緩沖區(qū)可以裝下一個數(shù)據(jù)幀) 情況1 情況2 情況3 情況4情況1：正常情況2：數(shù)據(jù)幀錯（但已接收）：解決方案：重發(fā)情況3：數(shù)據(jù)丟失之?dāng)?shù)據(jù)幀丟失 ：導(dǎo)致死鎖解決方案：超時重發(fā)情況4：數(shù)據(jù)幀

5、正確，但應(yīng)答幀丟失，超時重發(fā)后，使得該數(shù)據(jù)幀在接收方收到兩次：重復(fù)幀 解決方案：使每個數(shù)據(jù)幀帶上不同的發(fā)送序號，每發(fā)送一個新的幀就把它的發(fā)送序號加1，這樣，若兩個數(shù)據(jù)幀序號相同，則為重復(fù)幀，可丟棄一個。對于每次只發(fā)送一個幀的停止等待協(xié)議，可以只用兩個不同的編號（一個比特）停等協(xié)議的算法流程停等協(xié)議的算法流程SGet 1st Data from Network LayerV(s) = 0N(s)= V(s)Save Date Frame to BufferSend Buffered Data Frame to Physical LayerStart TimerWait EventReceived

6、 ACKReceived NAKTime OutGet Next Data V(s) = 1-V(s)RV(r) = 0Wait Data FrameReceived Frame, and Test if Error occursCorrectErrorN(s) = V(r) ?Discard FramePass Data toNetwok Layer Send ACKSend NAKSend ACKV(r)= 1-V(r) 教材上的算法教材上的算法在發(fā)現(xiàn)出錯幀后,收方丟棄并不發(fā)NAK,而由發(fā)方的超時定時器控制自動重發(fā). 由于發(fā)送端對出錯的數(shù)據(jù)進(jìn)行重發(fā)是自動進(jìn)行的，所以這種差錯控制體制又簡稱為

7、：ARQ（自動請求重發(fā)(Automatic Repeat reQuest)）frame iACK iframe I+1ACKi+1frame i+2frame i+2ACK i+2frame i+3ACK i+3frame i+3ACK i+3發(fā)送方發(fā)送方接收方接收方超時超時超時超時幀丟失幀丟失 重發(fā)重發(fā)ACK丟失丟失 重發(fā)，重發(fā)，丟失重復(fù)幀丟失重復(fù)幀協(xié)議的效率評價： 定量分析（吞吐量分析：單位時間內(nèi)成功發(fā)送的數(shù)據(jù)量） 模型建立： 忽略處理時間tpr和確認(rèn)幀發(fā)送時間ta，則有， 在連續(xù)發(fā)送情況下，若不發(fā)生錯誤，成功傳送一幀需要的時間為， poutfTtttttf2若應(yīng)答幀不出錯，發(fā)送幀丟失和出

8、錯的概率為p，重發(fā)次數(shù)不限，則有正確傳送一幀需要的平均時間為， 11)1 (iTTiTavpttippttpouttt2prpaprpouttttttt 重傳時間 （數(shù)據(jù)幀發(fā)送完畢后若經(jīng)過這樣長的時間沒有收到確認(rèn)幀就重傳這一幀）故鏈路最大吞吐量為，Tavtpt11max設(shè)發(fā)端幀到達(dá)率為，則應(yīng)有， maxTtp1定義歸一化吞吐量， = 11)1 (maxPttpttTfff這里， 為歸一化時間,顯然， 1 fTttARQ評價：簡單易行 通信信道的利用率不高改進(jìn)：連續(xù)ARQ, 選擇重傳ARQ連續(xù)ARQ協(xié)議 基本原理 在發(fā)送完一個數(shù)據(jù)幀后，不是象ARQ中那樣等待應(yīng)答幀后再發(fā)，而是可以連續(xù)發(fā)送若干個數(shù)

9、據(jù)幀（見下頁圖） 但接收端口只按順序接收數(shù)據(jù)幀，一旦中間有一個幀出錯，則在其后發(fā)送的幀要全部重發(fā)。 問題：等待時間和重傳時間的權(quán)衡，在未收到應(yīng)答時，一次連續(xù)發(fā)送多少數(shù)據(jù)幀為好： 開窗口的寬度：滑動窗口協(xié)議 （特殊：ARQ=1,等待多，重傳少) 一般情況下，窗口寬度與信道的關(guān)系： 如果信道的延遲大，則等待時間長，多開窗為宜 如果信道的噪聲大，則易出錯，易導(dǎo)致重傳，少開窗為宜連續(xù)ARQ協(xié)議的工作原理 連續(xù)ARQ又稱為 GO-BACK-N ARQ，意思是當(dāng)出現(xiàn)差錯必須重傳時，要向回走N個幀，然后再開始重傳。數(shù)據(jù)幀出錯數(shù)據(jù)幀丟失設(shè)誤幀率為p，則有，1)1(iTifavtipPttpptf1)1(1 這

10、里fTtt連續(xù)ARQ吞吐量分析故最大吞吐量為，)1(111maxptptfav歸一化吞吐量：pptf) 1(11可見，當(dāng)?shù)扔?時，停止等待ARQ與連續(xù)ARQ性能相同。結(jié)論：對于遠(yuǎn)程傳輸， ，連續(xù)ARQ具有明顯的優(yōu)越性。也就是說信道的延遲大，連續(xù)ARQ比ARQ效率要高。 fTtt滑動窗口概念滑動窗口概念 前提：在連續(xù)前提：在連續(xù)ARQ協(xié)議中，必須對可以連續(xù)發(fā)出的最多幀數(shù)協(xié)議中，必須對可以連續(xù)發(fā)出的最多幀數(shù)（已已發(fā)出但未確認(rèn)的幀）作限制發(fā)出但未確認(rèn)的幀）作限制 原則：循環(huán)重復(fù)使用有限的幀序號原則：循環(huán)重復(fù)使用有限的幀序號 流量控制：流量控制： 發(fā)送窗口：其大小發(fā)送窗口：其大小WT表示在收到對方確認(rèn)

11、的信息之前，可表示在收到對方確認(rèn)的信息之前，可以連續(xù)發(fā)出的最多數(shù)據(jù)幀數(shù)（只有序號在窗口內(nèi)的幀才可以以連續(xù)發(fā)出的最多數(shù)據(jù)幀數(shù)（只有序號在窗口內(nèi)的幀才可以發(fā)送）發(fā)送） 接收窗口：其大小接收窗口：其大小WR可以連續(xù)接收的最多數(shù)據(jù)幀數(shù)（只有可以連續(xù)接收的最多數(shù)據(jù)幀數(shù)（只有序號在窗口內(nèi)的幀才可以接收，否則丟棄）序號在窗口內(nèi)的幀才可以接收，否則丟棄） 接收窗口驅(qū)動發(fā)送窗口的轉(zhuǎn)動接收窗口驅(qū)動發(fā)送窗口的轉(zhuǎn)動發(fā)送窗口的最值：發(fā)送窗口的最值：n個比特編號，接收窗口大小為個比特編號，接收窗口大小為1時，時， 發(fā)送窗口發(fā)送窗口WT最大最大2n - 1 WT = 5WR = 1發(fā)出幀發(fā)出幀0, 100001111422

12、223333444555566667777HHHHHHTT發(fā)出幀發(fā)出幀2，接收到接收到ACK0滑動窗口示例滑動窗口示例接收到幀接收到幀0，發(fā)出發(fā)出ACK0初始狀態(tài)初始狀態(tài)0011223344556677T初始狀態(tài)初始狀態(tài)TTT接收到幀接收到幀1發(fā)出發(fā)出ACK1WT = 5WR = 10011223344556677H發(fā)出幀發(fā)出幀3, 4滑動窗口示例滑動窗口示例HHHHH01234567012345670123456701234567幀幀1的定時器超時，的定時器超時，重發(fā)幀重發(fā)幀1接收到接收到ACK1接收到幀接收到幀3,還沒有收到幀還沒有收到幀2接收到重傳接收到重傳的幀的幀1接收到幀接收到幀2T

13、TTTTTT滑動窗口協(xié)議已成功發(fā)出已成功發(fā)出的數(shù)據(jù)幀的數(shù)據(jù)幀將發(fā)出的數(shù)據(jù)幀將發(fā)出的數(shù)據(jù)幀窗口后沿窗口后沿窗口前沿窗口前沿幀序號幀序號發(fā)送方發(fā)送方緩沖區(qū)緩沖區(qū)已正確接收已正確接收的數(shù)據(jù)幀的數(shù)據(jù)幀將收到的數(shù)據(jù)幀將收到的數(shù)據(jù)幀幀序號幀序號接收方接收方緩沖區(qū)緩沖區(qū)窗口后沿窗口后沿窗口前沿窗口前沿滑動窗口示例信道利用率和最佳幀長（1）信道利用率 CDU這里， 為有效數(shù)據(jù)率， 是信道容量。（2）幀長對信道利用率的影響 過長，誤幀率高，信道利用率下降； 過短，幀開銷大，信道利用率下降。DC（3）最佳幀長計算令幀長為 ，幀頭長為 ，用戶數(shù)據(jù)長度為 ，則最大數(shù)據(jù)率為，flhldl)1(1 )1 (maxptlp

14、lDfdd將 代入上式，得，CllCltdhff)1(1)()1(pllClpDdhd故有，)1(1)()1 (plllPCDUdhd)1(11ppllldhd令 ， 解出 ，即可求出最佳幀長。0dlUdl選擇重傳ARQ協(xié)議 在連續(xù)ARQ中，一旦中間有一個幀出錯，則在其后接收到的幀全部丟失，要發(fā)送端全部重發(fā)，為此的改進(jìn)： 在選擇重傳ARQ中，接收端把后面接收到的數(shù)據(jù)幀暫存在接收端的緩存中，等待前面那個出錯的數(shù)據(jù)幀重傳后，再接收確認(rèn)緩存中的數(shù)據(jù)，減少了重傳的數(shù)據(jù)幀。 上述的ARQ系列主要針對流量控制以便充分利用信道，同時保證數(shù)據(jù)傳輸?shù)恼_。 那么如何能實現(xiàn)ARQ協(xié)議功能（如何在數(shù)據(jù)單元加上相應(yīng)的

15、控制信息） 此外，還有一些其他的鏈路層控制任務(wù)：建立、保持和釋放連接等高級數(shù)據(jù)鏈路控制(HDLC)早期規(guī)定在鏈路上所傳送的數(shù)據(jù)必須由一些規(guī)定的字符集組成（如ASCII碼），控制信息也只能用其中的幾個來描述，這被稱為面向字符的協(xié)議，缺點： 只對數(shù)據(jù)部分進(jìn)行差錯控制，可靠性差 依賴于字符集，不易擴(kuò)展70年代后，出現(xiàn)面向比特的協(xié)議 IBM SNA的 SDLC（同步數(shù)據(jù)鏈路控制 ） ANSI 的ADDCP（先進(jìn)的數(shù)據(jù)通信控制規(guī)程） ISO 的HDLC （高級數(shù)據(jù)鏈路控制） CCITT的LAP（鏈路接入規(guī)程） X.25采用LAPB（鏈路接入規(guī)程 - 平衡型 ）鏈路配置 概念： 主站：發(fā)送命令幀、負(fù)責(zé)控制

16、鏈路 從站（次站）：接收命令幀，向主站發(fā)送響應(yīng)幀，并配合主站 復(fù)合站（組合站）：同時具有主站和從站功能。 兩種基本配置：(見下頁圖示) 非平衡配置 點 - 點工作 多點工作 平衡配置 點 - 點工作命令命令(B)響應(yīng)響應(yīng)(B)主站主站A從站從站B非平衡配置：點非平衡配置：點-點點命令命令(B/C/D)響應(yīng)響應(yīng)(B)響應(yīng)響應(yīng)(C)響應(yīng)響應(yīng)(D)主站主站A從站從站B從站從站C從站從站D非平衡配置：點非平衡配置：點-多點多點命令命令(A)響應(yīng)響應(yīng)(B)響應(yīng)響應(yīng)(A)復(fù)合站復(fù)合站A復(fù)合站復(fù)合站B平衡配置平衡配置命令命令(B)數(shù)據(jù)傳送方式 對于非平衡配置： 正常響應(yīng)方式(NRM)： 數(shù)據(jù)傳輸由主站發(fā)起，

17、從站只能響應(yīng)主站的輪詢 異步響應(yīng)方式(ARM)： 從站可以主動發(fā)送數(shù)據(jù)，但鏈路管理由主站負(fù)責(zé) 對于平衡配置： 異步平衡方式(ABM)： 任一復(fù)合站都可以發(fā)起數(shù)據(jù)傳輸數(shù)據(jù)傳輸模式 非平衡式： 正常響應(yīng)模式（NRM）主 從CCRR 異步響應(yīng)模式（ARM）RCCR平衡式 異步平衡模式（ABM）CRCRHDLC的幀結(jié)構(gòu)幀是數(shù)據(jù)鏈路層協(xié)議的數(shù)據(jù)單元*信息字段的頭尾各加上24bit的控制信息， 就構(gòu)成了完整的一幀F(xiàn)InfoCAFFCS8 位位16 0888校驗區(qū)間透明傳輸區(qū)間HDLC幀結(jié)構(gòu)F (flaq) ：固定格式- 01111110 - 帶來的問題是什么？ 作用 - 幀同步；A (address) ：

18、表示誰的地址？- 因幀類型與應(yīng)用而異；C (control) ：表示幀的類型、幀的編號、命令與控制信息；I (information) ：網(wǎng)絡(luò)層數(shù)據(jù)，編碼可以是任意的，長度可變， max 256B;CRC(checksum) ：校驗A,C,I字段的數(shù)據(jù)； G(X)= X16+X12+X5+1 ( CRC-16 )FACFCRCI8bit8n8N168I各字段說明標(biāo)志字段F：頭尾各8位“01111110”標(biāo)記幀的首尾邊界以實現(xiàn)幀同步零比特填充(連續(xù)五個1后填0)以實現(xiàn)透明傳輸(透明傳輸區(qū)間) 地址字段A：非平衡方式，填入從站地址平衡方式，填入響應(yīng)站地址 控制字段C：標(biāo)記幀類型，并附加控制信息信息

19、幀：若控制字段的第1比特為0，傳送的是數(shù)據(jù)信息監(jiān)督幀：若控制字段的第1-2比特為10，傳送的是確認(rèn)等控制信息無編號幀：若控制字段的第1-2比特為11，建立和釋放鏈路的信息等 幀檢驗序列FCS：采用CRC-CCITT16， G(x) = x16 + x12 + x5 + 1地址字端（A） 響應(yīng)站地址； 全1為廣播地址； 全0為無效地址。 地址端擴(kuò)充：0 0 1 C幀類型及控制字段的意義：FACFCRCI8bit8n8N168b7b6b5b4b3b2b1b0I幀S幀U幀01 01 1N(S)SMP/FP/FP/FN(R)N(R)MI幀類型：I幀 ：信息幀； N(S) - 發(fā)送幀的順序號； N(R)

20、 -接收幀的順序號； P/F= Poll / Final ， P=1 - 詢問，F(xiàn)=1 - 響應(yīng)； P與F成對出現(xiàn)；S幀 ：監(jiān)控幀； S = 2bit，監(jiān)控功能位； S = 00，RR (receive ready) S = 10, RNR (receive not ready) S = 01, REJ (reject) S = 11, SREJ (select reject)U幀 ：無編號幀； 用于實現(xiàn)數(shù)據(jù)鏈路控制功能； 監(jiān)督幀的類型監(jiān)督幀的類型 S = 00 RR（Receive Ready）, 準(zhǔn)備接收下一幀，準(zhǔn)備接收下一幀， 確認(rèn)確認(rèn)N(R)-1及以前的各幀及以前的各幀 10 RNR（

21、Receive Not Ready）, 暫停暫停接收下一幀，接收下一幀， 確認(rèn)確認(rèn)N(R)-1及以前的各幀及以前的各幀 01 REJ（Reject）, 否認(rèn)自否認(rèn)自N(R)開始的幀開始的幀 確認(rèn)確認(rèn)N(R)-1及以前的各幀及以前的各幀 11 SREJ (Selective Reject), 只否認(rèn)只否認(rèn)N(R)幀幀 確認(rèn)確認(rèn)N(R)-1及以前的各幀及以前的各幀連續(xù)連續(xù)ARQ選擇重傳選擇重傳ARQP/F位的意義（詢問位的意義（詢問/終止）終止）= 0 無意義無意義= 1 非平衡配置非平衡配置 正常響應(yīng)方式正常響應(yīng)方式 主站主站 S/I 幀幀 P=1 （命令）（命令） S/I 幀幀 （響應(yīng)）（響應(yīng)

22、）I中中F=1，表示最后一個數(shù)據(jù)幀，表示最后一個數(shù)據(jù)幀S中中F=1，表示此時沒有數(shù)據(jù)要發(fā)送，表示此時沒有數(shù)據(jù)要發(fā)送從站從站NRM異步響應(yīng)方式異步響應(yīng)方式ARM平衡配置平衡配置 異步平衡方式異步平衡方式 ABM P=1 （詢問）（詢問）F=1 （回答本站狀態(tài)）（回答本站狀態(tài)）命令方命令方響應(yīng)方響應(yīng)方3）P/F 在非平衡方式中：輪詢/最終BCAAB,CB RR.0.PB I.0 0B I 1 0B I 2 0B I 3 0 FB RR 4C RR 0 PC RR 0 F在平衡式中：問/答B(yǎng) I 2 0B I 3 1B RR2 FB I 0 0 PB I 1 0A I 0 0A I 1 0A I 2 2無編號幀，定義了無編號幀，定義了15種，起