1、第三章 數(shù)據(jù)鏈路層,第三章 數(shù)據(jù)鏈路層,1 數(shù)據(jù)鏈路是什么？物理層實(shí)現(xiàn)了bit流透明傳輸，按bit流進(jìn)行數(shù)據(jù)傳輸存在什么問題？ 2 如何保證數(shù)據(jù)在鏈路上的可靠傳輸？ 3 我們以后自己設(shè)計一個數(shù)據(jù)鏈路層，有沒有值得借鑒的案例呢?,鏈路層: 工作環(huán)境,鏈路層: 工作環(huán)境,兩個 物理上連接的 設(shè)備: 主機(jī)-路由器, 路由器-路由器, 主機(jī)-主機(jī) 數(shù)據(jù)單元: frame（幀）,鏈路層: 實(shí)現(xiàn),通過 “adapter（網(wǎng)卡或適配器）” 實(shí)現(xiàn) e.g., PCMCIA 卡, 以太網(wǎng)卡 一般適配器都含有: RAM, DSP 芯片, 主機(jī)的總線接口, 和鏈路接口,network link physical,M

2、,frame,phys. link,data link protocol,adapter card,鏈路層的服務(wù),幀同步 幀的可靠傳輸 什么樣的傳輸是可靠傳輸？ 差錯控制 流量控制 鏈路訪問機(jī)制（廣播式鏈路）,差錯控制基本概念,什么是差錯控制？ 在通信過程中，發(fā)現(xiàn)、檢測差錯并進(jìn)行糾正 為何要進(jìn)行差錯控制？ 不存在理想的信道傳輸總會出錯 產(chǎn)生差錯的原因： 信號衰減和熱噪聲 信道的電氣特性引起信號幅度、頻率、相位的畸變； 信號反射，串?dāng)_； 沖擊噪聲，閃電、大功率電機(jī)的啟停等。,問題1：,幀如何定界（同步）？,幀同步,形成幀的四種方法 字符計數(shù)法 幀不定長，幀頭中用一個字符來表示幀內(nèi)的字符數(shù) 缺點(diǎn)：

3、計數(shù)字段一旦出錯，將無法再同步,幀同步,形成幀的四種方法 帶填充字符的首尾界符法 以特定的字符序列為控制字段（起始字符 DLE STX，結(jié)束字符DLE ETX） 缺點(diǎn)：依賴于字符集（8位字符和ASCII字符），不通用，也無法擴(kuò)展,幀同步,形成幀的四種方法 帶位填充的首尾標(biāo)記定界法 幀的起始和結(jié)束都用一個特殊的位串“01111110”，稱為標(biāo)記（flag） “0”比特插入刪除技術(shù) (參動畫),幀同步,形成幀的四種方法 物理層編碼違例法 IEEE802協(xié)議中：高-低電平對表示“1”，低-高電平對表示“0”。高-高/低-低不表示數(shù)據(jù)，可以用來做定界符。 只適用于在物理媒體的編碼策略中采用了冗余技術(shù)的

4、網(wǎng)絡(luò)；優(yōu)點(diǎn)：無需填充。 注意 在很多數(shù)據(jù)鏈路協(xié)議中，使用字符計數(shù)法和一種其它方法的組合。,第三章 數(shù)據(jù)鏈路層,1 數(shù)據(jù)鏈路是什么？物理層實(shí)現(xiàn)了數(shù)據(jù)鏈路之間的bit流傳輸，按bit流進(jìn)行數(shù)據(jù)傳輸存在什么問題？ 2 如何保證幀在數(shù)據(jù)鏈路上的可靠傳輸？,我們?nèi)绾沃缼欠癯鲥e？ 若出錯了怎么辦?,如何使幀的發(fā)送速率和接收速率匹配？,問題2,差錯控制和流量控制,差錯控制 差錯控制編碼 檢錯碼和糾錯碼 差錯控制技術(shù) 差錯控制的基本方法：接收方進(jìn)行差錯檢測，并向發(fā)送方應(yīng)答，告知是否正確接收。 流量控制 自動請求重傳Automatic Repeat Request （ARQ） 停等 ARQ Go-back-

5、N ARQ 滑動窗口協(xié)議,差錯控制編碼原理,EDC= 錯誤檢測校正（Error Detection and Correction (冗余數(shù)據(jù))）位 D = 由檢驗(yàn)位保護(hù)的數(shù)據(jù), 可包括首部字段 錯誤檢測不可能達(dá)到 100% 可靠! 協(xié)議算法可能會忽略了某些錯誤, 但比例極小 較大的 EDC 字段可以產(chǎn)生較好的檢錯和糾錯效果,差錯控制編碼,奇偶檢驗(yàn)（檢錯碼） 海明糾錯碼（糾錯碼） 循環(huán)冗余碼(CRC)（檢錯碼）,奇偶檢驗(yàn),原理： 在原始數(shù)據(jù)字節(jié)的最高位（或最低位）增加一個奇偶校驗(yàn)位，使結(jié)果中1的個數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。 例如：1100010增加偶校驗(yàn)位后為11100010 注意：

6、只能檢測出奇數(shù)個位錯，偶數(shù)個位錯則不能檢出。,海明糾錯碼,海明糾錯碼 海明糾錯碼的格式 碼字的編號從左到右，最左邊是第一位，其中2的冪數(shù)位是檢驗(yàn)位，其余是k個數(shù)據(jù)位(信息元)。 海明糾錯碼格式如下： 20 21 22 23 24 p1 p2 * p3 * * * p4* * * * * * * p5 *-信息元 P-校驗(yàn)位,海明糾錯碼,海明碼的編碼與譯碼的方法 用矩陣乘法求檢驗(yàn)位，并且找出錯誤位。 設(shè)編碼長度為 n = 2r 1，其中r為校驗(yàn)碼的位數(shù)。數(shù)據(jù)位長度 k = n r。 校驗(yàn)位插入到編碼序列的2j-1 (j=1,2,.,r)的位置上；由r(樣本)建立一個(2r -1)行 * r列的矩

7、陣。,海明糾錯碼,將編碼字寫成串形式的一維向量,其中，l1 =l2 =lr =1或0(l=0為偶校驗(yàn)，l=1為奇校驗(yàn))； bij = 1 或 0,海明糾錯碼,例: 按下列步驟將數(shù)據(jù)(信息)1100進(jìn)行編碼，設(shè)校驗(yàn)位為r=3。 解: (1)編碼長度 n = 2r 1 = 7 數(shù)據(jù)位 k = n r = 4 校驗(yàn)位 r = 3,海明糾錯碼,(2)編碼過程,由矩陣乘法得，p1 = 0 ,p2 = 1, p3 = 1 解得海明碼為 0111100,循環(huán)冗余碼(CRC),循環(huán)冗余碼（CRC） 基本思想 收發(fā)雙方約定一個生成多項(xiàng)式G(x)（其最高階和最低階系數(shù)必須為1），發(fā)送方在幀的末尾加上校驗(yàn)序列，使帶

8、校驗(yàn)序列的幀的多項(xiàng)式能被G(x)整除；接收方收到后，用G(x)除多項(xiàng)式，若有余數(shù)，則傳輸有錯。 多項(xiàng)式碼 將位串看成系數(shù)為0或1的多項(xiàng)式 如：110001，表示成多項(xiàng)式 x5+x4+1,循環(huán)冗余碼(CRC),循環(huán)冗余碼（CRC） CRC的計算算法,循環(huán)冗余碼(CRC),循環(huán)冗余碼（CRC） 常用的CRC生成多項(xiàng)式 CRC-12=x12+x11+x3+x2+x+1 CRC-16=x16+x15+x2+1 CRC-CCITT=x16+x12+x5+1 檢錯能力：CRC-16和CRC-CCITT可以捕捉突發(fā)錯長度小于16的全部錯誤、長度為17的突發(fā)錯的99.998、長度為18以上的突發(fā)錯的99.99

9、7。,差錯編碼比較,結(jié)論： 1.CRC檢錯能力強(qiáng)。 2.是線性碼，有良好的結(jié)構(gòu)，易于硬件實(shí)現(xiàn)。,差錯控制和流量控制,差錯控制 差錯控制編碼 檢錯碼和糾錯碼 差錯控制技術(shù) 差錯控制的基本方法：接收方進(jìn)行差錯檢測，并向發(fā)送方應(yīng)答，告知是否正確接收。 流量控制 自動請求重傳Automatic Repeat Request （ARQ） 停等 ARQ Go-back-N ARQ 滑動窗口協(xié)議,停止等待協(xié)議的原理,原理 發(fā)送方發(fā)送完一幀數(shù)據(jù)后，必須等待接收方的確認(rèn)幀返回，確認(rèn)數(shù)據(jù)被正確接收后才能繼續(xù)發(fā)送下一幀。,停止等待協(xié)議的原理,過程,從 主 機(jī) 取 數(shù) 據(jù),上 交 主 機(jī),DATA1,DATA2,結(jié)點(diǎn)

10、 A,結(jié)點(diǎn) B,ACK,ACK,思考,問題1：發(fā)送幀出錯或丟失怎么辦？ 設(shè)置計時器，利用超時中斷防止因幀丟失所造成的死鎖。 問題2：應(yīng)答幀出錯或丟失怎么辦？ 設(shè)置幀序號，利用序號檢查是新幀還是重復(fù)幀。 問題3：幀序號字段需占用多少位？ 根據(jù)停等協(xié)議的定義，表示幀發(fā)送序號的字段只需占用一位，因?yàn)橹恍铏z查前后兩幀的順序是否相同，而不注重各幀的順序號本身的值是多少。,幀序號討論,例：發(fā)送幀本身序號為 0 1 2 3 4 5 6 7 停等協(xié)議幀序號為 0 1 0 1 0 1 0 1 同理，幀確認(rèn)序號也只需占用一位。 為便于判斷序號的正確性，通常定義幀確認(rèn)序號(ACK)為期望發(fā)送方下次發(fā)送的幀序號(SE

11、Q)，表達(dá)式為： ACK=SEQ+1(mod 2),單工停等協(xié)議,過程 發(fā)送方將當(dāng)前信息幀作為待確認(rèn)幀保存在緩沖區(qū) 發(fā)送數(shù)據(jù)的同時起動計時器 接收方收到數(shù)據(jù)后返回一個確認(rèn)幀 若接收方收到的數(shù)據(jù)有錯，則丟棄 發(fā)送方若在規(guī)定時間內(nèi)沒有收到確認(rèn)幀，則計時器清零，重發(fā)緩沖區(qū)內(nèi)的信息幀,單工停止等待協(xié)議,過程(參考動畫演示:停止等待協(xié)議),單工停等協(xié)議,雙工停等協(xié)議,問題1：如何區(qū)分發(fā)送幀(數(shù)據(jù)幀)和應(yīng)答幀？ 在幀的控制信息中增加一個幀類型的字段。 問題2：如果某站收到對方的數(shù)據(jù)后，在給對方發(fā)送應(yīng)答幀的同時，又有數(shù)據(jù)幀要發(fā)往對方，能不能只發(fā)送一幀？ 采用“背回”(Piggybacking)技術(shù)。可以在數(shù)

12、據(jù)幀中增加一個接受順序號字段(ACK字段)以存放應(yīng)答信息，于是對方在收到數(shù)據(jù)幀的同時也得到了應(yīng)答。,背回技術(shù)的討論,背回應(yīng)答的優(yōu)點(diǎn)： 減少了幀的發(fā)送數(shù)目(因?yàn)闇p少了單獨(dú)應(yīng)答幀)； 能有效地利用通道，且接收站的“幀正確到達(dá)”中斷次數(shù)和接收站的輸入緩沖區(qū)均可以減少。 但是背回應(yīng)答增加了協(xié)議的復(fù)雜性。,背回技術(shù)的討論,問題3：高層并非始終有信息發(fā)送，應(yīng)答幀何時發(fā)送？ 解決辦法：設(shè)置ACK計時器,連續(xù)ARQ協(xié)議,連續(xù)ARQ又稱為Go-Back-N ARQ 當(dāng)出現(xiàn)差錯必須重傳時，要向回走N個幀，然后開始重傳。 原理 發(fā)送端連續(xù)發(fā)送至發(fā)送緩沖區(qū)窗口滿 接收緩沖區(qū)窗口大小為1幀，對丟棄幀不確認(rèn) 發(fā)送方設(shè)置超

13、時，若超時回退若干幀到未被確認(rèn)幀開始重傳 接收方從出錯幀起丟棄所有后繼幀,連續(xù)ARQ協(xié)議,特點(diǎn) 發(fā)送方需要較大的緩沖區(qū)，以便重傳 減少了等待時間，提高了吞吐量 發(fā)送幀和接受幀都要進(jìn)行編號 適于信道出錯率較少的情況 問題 信道誤碼率高時，對損壞幀和非損壞幀的重傳非常多，反而降低效率,連續(xù)ARQ協(xié)議,注意的問題 接收端按序接收。例如：2號幀出錯但收到正確的3號幀仍然丟棄3號幀從2號幀開始重傳 ACK1表示確認(rèn)0號幀DATA0，期望下次收到1號幀，依次類推 思考 實(shí)際的連續(xù)ARQ利用一個計時器實(shí)現(xiàn)N個獨(dú)立超時計數(shù)器的功能，思考這如何實(shí)現(xiàn)？,滑動窗口協(xié)議,采用窗口的原因 應(yīng)對以發(fā)送出去但尚未被確認(rèn)的幀

14、的數(shù)目加以限制。 要重復(fù)循環(huán)使用幀的序號，避免無止境的幀序號的增大。 發(fā)送窗口 在發(fā)送端。用來對發(fā)送方進(jìn)行流量控制。 發(fā)送窗口的大?。耗軌虼娣诺拇_認(rèn)幀的最大數(shù)目。 接收窗口 在接收端。用來指示接收方允許接收的幀的序號。,滑動窗口協(xié)議,滑動窗口實(shí)例：發(fā)送窗口=2；接收窗口=1 初態(tài)：發(fā)送端無數(shù)據(jù)發(fā)出，接受端0號窗口打開準(zhǔn)備接收數(shù)據(jù) 發(fā)送端發(fā)出0號幀，0號窗口被占用；此時接收端尚未收到數(shù)據(jù) 發(fā)送端發(fā)出1號幀，1號窗口被占用；此時接收端尚未收到數(shù)據(jù)。發(fā)送方停止發(fā)送數(shù)據(jù)。 接收端0號幀收到，關(guān)閉其0號窗口，打開1號窗口等待接受 發(fā)送方收到接收端發(fā)來的確認(rèn)后，關(guān)閉0號窗口 發(fā)送方發(fā)送2號幀，占用2號窗

15、口，然后暫停發(fā)送 依次類推循環(huán)，達(dá)到了限止發(fā)送幀的數(shù)目，又避免了幀序號重復(fù)時的歧義。,滑動窗口協(xié)議,滑動窗口實(shí)例：發(fā)送窗口=2；接收窗口=1,滑動窗口協(xié)議,各種協(xié)議規(guī)定的緩沖窗口大小 停止等待：發(fā)送窗口=1，接收窗口=1 Go Back n：發(fā)送窗口1，接收窗口=1 滑動窗口：發(fā)送窗口1，接收窗口1,滑動窗口結(jié)論,令發(fā)送窗口為WT，接收窗口為WR 。發(fā)送序號用n個比特表示。 結(jié)論1：若WR1，則WT2n1 例如n=3，（WT）max7 結(jié)論2：WR2n/2，WT= WR=2n/2 例如n=3 ，則WT= WR=4,鏈路層的服務(wù),幀同步 幀的可靠傳輸 什么樣的傳輸是可靠傳輸？ 差錯控制 流量控制

16、 鏈路訪問機(jī)制（廣播式鏈路）？,鏈路和協(xié)議,有三種類型的 “鏈路”: 點(diǎn)對點(diǎn) ( e.g. PPP, SLIP) 廣播式 (共享線路或介質(zhì); e.g, 以太網(wǎng), 無線網(wǎng), etc.) 交換式 (e.g., 交換式以太網(wǎng), ATM etc),點(diǎn)對點(diǎn)的數(shù)據(jù)鏈路協(xié)議（DLC）,一方發(fā),一方收,一條鏈路:比廣播信道簡單的多 無需介質(zhì)訪問控制 不必進(jìn)行MAC尋址 e.g., 撥號鏈路, ISDN 線路等 常見的點(diǎn)對點(diǎn)DLC協(xié)議: SLIP (Serial Line Internet Protocol) PPP (point-to-point 協(xié)議) SDLC: Synchronous Data Link

17、 Control (SNA的面向比特的數(shù)據(jù)鏈路規(guī)程) HDLC: High level data link control (ISO高級數(shù)據(jù)鏈路控制),多點(diǎn)訪問協(xié)議,一條共享的通信信道 兩個或多個結(jié)點(diǎn)可同時發(fā)送信號: 相互干擾 在某一時刻只有一個結(jié)點(diǎn)可以成功地發(fā)送信號 多點(diǎn)訪問協(xié)議: 分布式的算法來決定如何共享信道, i.e., 決定工作站何時可以發(fā)送 注意：有關(guān)共享通道的通信（協(xié)商）也必須在該通道自身上解決! 我們希望多點(diǎn)訪問協(xié)議能夠解決什么問題: 同步還是異步 了解其他站點(diǎn)的信息 健壯性 (e.g.如何對待信道錯誤) 性能,點(diǎn)到點(diǎn)數(shù)據(jù)鏈路層協(xié)議案例,案例1：高級數(shù)據(jù)鏈路控制規(guī)程,HDLC

18、面向比特的數(shù)據(jù)鏈路層協(xié)議(規(guī)程） 使用HDLC的語法可以定義多種具有不同操作特點(diǎn)的鏈路層協(xié)議。,案例1：HDLC,鏈路基本配置原理圖,案例1：HDLC,HDLC鏈路基本配置類型 非平衡配置：點(diǎn)對點(diǎn)工作；多點(diǎn)工作 由一個主站控制整個鏈路的工作。主站發(fā)出的幀叫做命令。受控各站叫做次站或從站。從站發(fā)出的叫做響應(yīng)。多點(diǎn)工作時主站與每個從站都有分開的邏輯鏈路。 平衡配置：點(diǎn)對點(diǎn)工作 鏈路上都是復(fù)合站，平等發(fā)送數(shù)據(jù)，不需要對方的允許。,案例1：HDLC,HDLC涉及三種類型的站： 主站（Primary Station） 主要功能是發(fā)送命令（包括數(shù)據(jù)），接收響應(yīng)，負(fù)責(zé)整個鏈路的控制（如系統(tǒng)的初始、流控、差錯

19、恢復(fù)等）； 從站（Secondary Station） 主要功能是接收命令，發(fā)送響應(yīng)，配合主站完成鏈路的控制； 復(fù)合站（Combined Station） 同時具有主、從站功能，既發(fā)送又接收命令和響應(yīng)，并負(fù)責(zé)整個鏈路的控制。,案例1：HDLC,幀的一般結(jié)構(gòu),案例1：HDLC,標(biāo)志字段 以0111 1110作為起止的幀邊界標(biāo)記 零比特填充法 原因 避免數(shù)據(jù)信息字段與標(biāo)志字段F相同，引起幀邊界錯誤，達(dá)到透明傳輸。 采用方法 發(fā)送端： 利用硬件掃描數(shù)據(jù)信息字段，遇到5個1即添加一個0 接受端： 硬件掃描到連續(xù)5個1，因?yàn)榘l(fā)送端掃描填充過0，緊接的必然是0，去掉這個0,案例1：HDLC,地址字段 非平

20、衡方式寫入從站地址，平衡方式寫入確認(rèn)站地址 全1地址為廣播方式，全0為無效地址，有效地址254個 地址字段可擴(kuò)展,案例1：HDLC,HDLC的三種幀類型 信息幀（Information Frame） 監(jiān)督幀（Supervisory Frame） 無編號幀（Unnumbered Frame）,案例1：HDLC,三種HDLC幀的控制字段,案例1：HDLC,三種HDLC幀的控制字段 序號（Seq） 當(dāng)前發(fā)送的信息幀的序號。使用滑動窗口技術(shù)，3位序號，發(fā)送窗口大小為4。 捎帶確認(rèn)（Next） 捎帶下一個準(zhǔn)備接受的幀序號，而不是最后一個已收到的幀序號。 探詢/結(jié)束 P/F位（Poll/Final） 命令

21、幀置“P”，響應(yīng)幀置“F”。有些協(xié)議，P/F位用來強(qiáng)迫對方機(jī)器立刻發(fā)監(jiān)督幀； 多終端系統(tǒng)中，計算機(jī)置“P”，允許終端發(fā)送數(shù)據(jù)；終端發(fā)向計算機(jī)的幀中，最后一個幀置為“F”，其它置為“P”。,案例1：HDLC,三種HDLC幀的控制字段 監(jiān)督幀的類型（Type）,案例1：HDLC程,三種HDLC幀的控制字段 無編號幀 可以用來傳控制信息，也可在不可靠無連接服務(wù)中傳數(shù)據(jù)； 利用3、4、6、7、8共5個bit來表示不同的功能。,案例1：HDLC,半雙工“點(diǎn)-點(diǎn)”數(shù)據(jù)傳送 全雙工鏈路，單向傳輸 全雙工鏈路，雙向同時傳輸,案例1：HDLC,半雙工“點(diǎn)-點(diǎn)”數(shù)據(jù)傳送 幾點(diǎn)說明： 類型(TYPE)：對于信息使用I幀，對于S幀則使用RR、REJ、RNR或SREJ。 P/F指明探詢或最后幀是否建立。,案例1：HDLC,案例1：HDLC,案例1：HDLC,全雙工鏈路，單向傳輸,主站,從站,I,0,0,I,1,0,I,2,0,I,3,0,P,RR,1,F,I,1,0,I,2,0,I,3,0,P,I,4,0,RR,4,F,I,5,0,I,6,0,X 干擾,案例1：HDLC,注意： 主站在發(fā)送了探詢之后仍能繼續(xù)發(fā)送數(shù)據(jù)。另外，在發(fā)送信息幀7以后，