第四章 數(shù)據(jù)鏈路控制

1、鏈路管理鏈路管理（1）理想情況下：）理想情況下：發(fā)收(2) 實(shí)際應(yīng)用情況下：實(shí)際應(yīng)用情況下： 需要考慮主機(jī)的流控問題和差錯的處理需要考慮主機(jī)的流控問題和差錯的處理發(fā)收ACK正確正確發(fā)收NAK錯誤錯誤重發(fā)重發(fā)發(fā)收重發(fā)重發(fā)超時超時重發(fā)重發(fā)正確正確發(fā)收重發(fā)重發(fā)正確正確ACK超時超時重發(fā)重發(fā)正確正確重復(fù)幀重復(fù)幀(1)(2)(3)(4) Buffer / WindowACK0123456701WT = 50123456701WR = 1 Buffer / WindowACK0123456012WT = 50123456012WR = 1 數(shù)據(jù)比特數(shù)數(shù)據(jù)比特數(shù) + 冗余比特數(shù) 00110010011001

2、 x4+x3+x2+1則：冗余碼則：冗余碼R(x)為：為：10011 1 0 0 0 0 01 1 1 0 1111011 0 11 0 1 0 01 1 1 0 11 0 0 1例如：對于例如：對于(7,3)碼，若數(shù)據(jù)碼字為碼，若數(shù)據(jù)碼字為110，G(x)是是x4+x3+x2+1 求其冗余校驗(yàn)碼。求其冗余校驗(yàn)碼。碼字中碼字中“1”1”的個數(shù)。的個數(shù)。 如：如：“100011”100011”，其權(quán)值為：，其權(quán)值為：3 3(2) (2) 兩碼字間的漢明距離：兩碼字相對應(yīng)位不同的個數(shù)。兩碼字間的漢明距離：兩碼字相對應(yīng)位不同的個數(shù)。 例如：例如：(3) (3) 校驗(yàn)碼的漢明距離（漢明距）：在給定編碼

3、方法情校驗(yàn)碼的漢明距離（漢明距）：在給定編碼方法情況下，所有合法碼字間的最小漢明距離。況下，所有合法碼字間的最小漢明距離。 例如：例如：(7,3)(7,3)碼共有碼共有8 8個合法編碼：個合法編碼： 000 001 010 011 100 101 110 111000 001 010 011 100 101 110 111 則：最小的距離是：？則：最小的距離是：？100011101010 要發(fā)現(xiàn)要發(fā)現(xiàn)d位錯誤，其編碼的漢明距離至少為：位錯誤，其編碼的漢明距離至少為：d+1 要糾正要糾正d位錯誤，其編碼的漢明距離至少為：位錯誤，其編碼的漢明距離至少為：2d+1ABAA”若dAB=3，則有：ABA

4、A”若dAB=5，則有：若發(fā)生若發(fā)生1位錯，位錯，dAB=2，顯然錯！，顯然錯！若發(fā)生若發(fā)生2位錯，位錯，dA”B=1，顯然錯！，顯然錯！ 采用采用“就近恢復(fù)就近恢復(fù)”原則原則若發(fā)生若發(fā)生3位錯，位錯，A B，不知錯！，不知錯！ 將碼字的每一位從左向右編號，最左邊為第一位；將碼字的每一位從左向右編號，最左邊為第一位； 凡是編號為凡是編號為2的乘冪的位均是校驗(yàn)位，其余為數(shù)據(jù)位；的乘冪的位均是校驗(yàn)位，其余為數(shù)據(jù)位； 將任一數(shù)據(jù)位的編號按將任一數(shù)據(jù)位的編號按2的最大乘冪展開成和式，和式的最大乘冪展開成和式，和式中每一項(xiàng)所對應(yīng)的位均是該數(shù)據(jù)位的校驗(yàn)位。中每一項(xiàng)所對應(yīng)的位均是該數(shù)據(jù)位的校驗(yàn)位。 每個校驗(yàn)

5、位連同所負(fù)責(zé)的數(shù)據(jù)位一起構(gòu)成偶校驗(yàn)。每個校驗(yàn)位連同所負(fù)責(zé)的數(shù)據(jù)位一起構(gòu)成偶校驗(yàn)。 例如：求例如：求ASCII字符字符“a”的的Hamming編碼？編碼？解題參考：解題參考： “a”的的ASCII為：為：1100001，所以有：，所以有：12 3 4 5 6 7 8 9 10 11A B 1 C 1 0 0 D 0 0 1 A A A A A 有有A=1 B B B B B B=0 C C C C=1 D D D D=1因此，因此，“a”的漢明編碼為：的漢明編碼為： 10111001001在收端設(shè)一個差錯計數(shù)器并置在收端設(shè)一個差錯計數(shù)器并置“0”，收到漢明碼后，收到漢明碼后，逐個檢查各校驗(yàn)位及其

6、負(fù)責(zé)的數(shù)據(jù)位的偶校驗(yàn)特性，逐個檢查各校驗(yàn)位及其負(fù)責(zé)的數(shù)據(jù)位的偶校驗(yàn)特性，若被破壞，則將該校驗(yàn)位的序號累加到計數(shù)器。待若被破壞，則將該校驗(yàn)位的序號累加到計數(shù)器。待所有校驗(yàn)位檢查完后，若計數(shù)器的值為所有校驗(yàn)位檢查完后，若計數(shù)器的值為0，則傳輸正，則傳輸正確，否則，計數(shù)器的值即為出錯的位。確，否則，計數(shù)器的值即為出錯的位。12 3 4 5 6 7 8 9 10 11A B 1 C 1 0 0 D 0 0 1 A A A A A 有有A=1 B B B B B B=0 C C C C=1 D D D D=1連續(xù)連續(xù)ARQ停等停等ARQAutomation RepeatreQuest-ARQ發(fā)發(fā)收收0A

7、CK01正確正確錯誤錯誤NAK111ACK11正確正確超時重發(fā)超時重發(fā)超時重發(fā)超時重發(fā)正確正確重復(fù)幀處理重復(fù)幀處理1230123123456WT = 70123123456WR = 1丟棄丟棄等待等待1號幀號幀交上交上層處層處理理(1) 接收的數(shù)據(jù)幀通過差錯檢測發(fā)現(xiàn)幀錯誤接收的數(shù)據(jù)幀通過差錯檢測發(fā)現(xiàn)幀錯誤一般地，當(dāng)差錯檢測發(fā)現(xiàn)第一般地，當(dāng)差錯檢測發(fā)現(xiàn)第I幀錯誤，則接收方給出否認(rèn)幀幀錯誤，則接收方給出否認(rèn)幀信息，發(fā)送方退回第信息，發(fā)送方退回第I幀，重發(fā)第幀，重發(fā)第I幀及幀及I幀的后續(xù)幀。幀的后續(xù)幀。( 2) 當(dāng)傳輸?shù)臄?shù)據(jù)幀丟失當(dāng)傳輸?shù)臄?shù)據(jù)幀丟失0123412345WT = 70123412345

8、WR = 1丟棄丟棄等待等待1號幀號幀交上層交上層處理處理超時間隔超時間隔超時重發(fā)超時重發(fā)( 3) 當(dāng)接收方發(fā)出的確認(rèn)幀丟失當(dāng)接收方發(fā)出的確認(rèn)幀丟失0123412345WT = 70123412345WR = 1丟棄重復(fù)幀丟棄重復(fù)幀交上層交上層處理處理超時間隔超時間隔超時重發(fā)超時重發(fā)0123145670WT 10123145670WR 1暫存暫存緩存緩存等待等待1號幀號幀一起交上一起交上層處理層處理ACK3(1) 接收的數(shù)據(jù)幀通過差錯檢測發(fā)現(xiàn)幀錯誤接收的數(shù)據(jù)幀通過差錯檢測發(fā)現(xiàn)幀錯誤( 2) 當(dāng)傳輸?shù)臄?shù)據(jù)幀丟失當(dāng)傳輸?shù)臄?shù)據(jù)幀丟失0123415670WT 10123415670WR 1暫存暫存等待

9、等待1號幀號幀超時間隔超時間隔超時超時重發(fā)重發(fā)一起交上一起交上層處理層處理( 3) 當(dāng)接收方發(fā)出的確認(rèn)幀丟失當(dāng)接收方發(fā)出的確認(rèn)幀丟失0123415670WT = 70123415670WR = 1丟棄重丟棄重復(fù)幀復(fù)幀超時間隔超時間隔超時超時重發(fā)重發(fā) 1、面向字符與面向比特流的通信、面向字符與面向比特流的通信（1）面向字符的同步通信方式（如：）面向字符的同步通信方式（如：IBM的的BSC規(guī)程）規(guī)程） 所謂面向字符就是說在鏈路上所傳送的數(shù)據(jù)必須所謂面向字符就是說在鏈路上所傳送的數(shù)據(jù)必須是由規(guī)定字符集（例如是由規(guī)定字符集（例如ASCII碼）中的字符所組成。在碼）中的字符所組成。在鏈路上傳送的控制信息

10、也鏈路上傳送的控制信息也必須由同一字符集中的若干必須由同一字符集中的若干指定的控制字符構(gòu)成指定的控制字符構(gòu)成。這種面向字符的鏈路控制規(guī)程。這種面向字符的鏈路控制規(guī)程在計算機(jī)網(wǎng)絡(luò)的發(fā)展過程中曾起了重要的作用，但它在計算機(jī)網(wǎng)絡(luò)的發(fā)展過程中曾起了重要的作用，但它存在通信線路的存在通信線路的利用率低、可靠性較差、不易擴(kuò)展利用率低、可靠性較差、不易擴(kuò)展等等缺點(diǎn)，所以具有更大的靈活性和更高的效率的面向比缺點(diǎn)，所以具有更大的靈活性和更高的效率的面向比特型協(xié)議逐漸成為數(shù)據(jù)鏈路層的主要協(xié)議。特型協(xié)議逐漸成為數(shù)據(jù)鏈路層的主要協(xié)議。IBM的的BSC規(guī)程：規(guī)程：特殊格式字符定義：特殊格式字符定義： SYN：同步字符：

11、同步字符(Synchronous character)，每幀可加，每幀可加1 個個(單同步單同步)或或2個個(雙同步雙同步)同步字符。同步字符。 SOH：標(biāo)題開始：標(biāo)題開始(Start of Header)。 標(biāo)題：標(biāo)題：Header，包含源地址、目的地址、路由指示。，包含源地址、目的地址、路由指示。 STX：正文開始：正文開始(Start of Text)。 數(shù)據(jù)塊：正文數(shù)據(jù)塊：正文(Text)，由多個字符組成。，由多個字符組成。 ETB:塊傳輸結(jié)束塊傳輸結(jié)束(end of transmission block)， 標(biāo)識標(biāo)識數(shù)據(jù)塊結(jié)束。數(shù)據(jù)塊結(jié)束。 ETX：全文結(jié)束：全文結(jié)束(end of

12、text)，(全文分為若干塊傳輸全文分為若干塊傳輸)。 塊校驗(yàn)：對從塊校驗(yàn)：對從SOH開始，直到開始，直到ETB/ETX字段的檢驗(yàn)碼。字段的檢驗(yàn)碼。（2）、面向比特流的同步通信（如：）、面向比特流的同步通信（如：SDLC規(guī)程）規(guī)程） 高級數(shù)據(jù)鏈路控制高級數(shù)據(jù)鏈路控制HDLC（High-level Data Link Control）就是一種面向比特）就是一種面向比特流的流的協(xié)議。其特點(diǎn)是以位協(xié)議。其特點(diǎn)是以位的位置來定位各個字段，而不用控制字符。各字段內(nèi)的位置來定位各個字段，而不用控制字符。各字段內(nèi)均由位的各種組合組成。它的最早版本是均由位的各種組合組成。它的最早版本是IBM公司研公司研制的制

13、的SDLC協(xié)議，用作協(xié)議，用作IBM SNA網(wǎng)的數(shù)據(jù)鏈路層協(xié)議。網(wǎng)的數(shù)據(jù)鏈路層協(xié)議。后來幾個國際標(biāo)準(zhǔn)化組織做了少量修改，發(fā)展為多個后來幾個國際標(biāo)準(zhǔn)化組織做了少量修改，發(fā)展為多個版本的面向比特版本的面向比特流的流的協(xié)議。如協(xié)議。如ANSI的版本是的版本是ADDCP協(xié)議，協(xié)議，ISO的版本就是的版本就是HDLC協(xié)議，協(xié)議，CCITT的版本是的版本是LAP協(xié)議，并作為建議書協(xié)議，并作為建議書X.25的一部分。的一部分。面向比特流的控制規(guī)程（面向比特流的控制規(guī)程（HDLC）FlagFlagAddressControlCheckSumInformation0111111001111110CRC校驗(yàn)校驗(yàn)流

14、控、差控流控、差控特點(diǎn)：特點(diǎn)：（1）Information域可以傳輸任意位數(shù)據(jù)。域可以傳輸任意位數(shù)據(jù)。 （2）同步控制域不是特定字符。）同步控制域不是特定字符。 （3）適合于計算機(jī)網(wǎng)絡(luò)通信。）適合于計算機(jī)網(wǎng)絡(luò)通信。2、高級數(shù)據(jù)鏈路控制、高級數(shù)據(jù)鏈路控制(HDLC)的操作方式的操作方式(1) 正常響應(yīng)方式正常響應(yīng)方式NRM（Norma Responses Model） (2) 異步響應(yīng)方式異步響應(yīng)方式ARM Asynchronous Responses Mode） (3) 異步平衡方式異步平衡方式ABM（Asynchronous Balanced Mode） 主站主站從站從站命令幀響應(yīng)幀主站主站

15、從站從站命令幀響應(yīng)幀主站主站從站從站命令/響應(yīng)幀命令/響應(yīng)幀3、HDLC的幀格式的幀格式 FlagFlagAddressControlCheckSumInformation8bit8bit8/16bit8/16bit16/32bit可變（1）Flag域：域： 固定位組合值：固定位組合值：01111110，作為幀的開始和結(jié)束標(biāo)志。，作為幀的開始和結(jié)束標(biāo)志。 零比特填充方法零比特填充方法： 發(fā)送方：每連續(xù)發(fā)送方：每連續(xù)5個個“1”插入一個插入一個“0”； 接收方：每連續(xù)接收方：每連續(xù)5個個“1”去掉一個去掉一個“0”。（2）Address域：域：全全“1”和全和全“0”地址均為保留地址地址均為保留

16、地址/無站地址。無站地址。地址擴(kuò)展：地址擴(kuò)展：0111表明后一個字節(jié)仍然表明后一個字節(jié)仍然是地址域的值是地址域的值表明后一個字節(jié)不是表明后一個字節(jié)不是地址域的值地址域的值1ByteEthernet的的MAC地址：地址：6ByteTCP/IP協(xié)議的協(xié)議的IP地址：地址：4Byte保證每個站點(diǎn)有唯一地址保證每個站點(diǎn)有唯一地址（3）Frame Check Sum (FCS)域域FlagFlagAddressControlCheckSumInformation8bit8bit8/16bit8/16bit16/32bit可變FCS校驗(yàn)區(qū)域采用CRC-16差錯編碼 CRC-32（4）Information

17、域域由由Control域決定：信息幀域決定：信息幀(I幀幀)和無編號幀和無編號幀(U幀幀)（5）Control域域控制域位12345678I幀0N(S)P/FN(R)S幀10S1S2P/FN(R)U幀11M1M2P/FM3M4M5S位編碼表位編碼表S位位幀幀 名名功功 能能用途用途00RR(Receive Ready)準(zhǔn)備接收準(zhǔn)備接收N(R)幀幀確認(rèn)確認(rèn)N (R) -1及前續(xù)幀及前續(xù)幀退后退后N幀幀ARQ01RNR(Receive Not Ready) 暫停接收暫停接收N(R)幀幀確認(rèn)確認(rèn)N (R) -1及前續(xù)幀及前續(xù)幀10REJ(Reject)否認(rèn)否認(rèn)N (R)及后續(xù)幀及后續(xù)幀確認(rèn)確認(rèn)N (

18、R) -1及前續(xù)幀及前續(xù)幀11SREJ(Selective Reject)否認(rèn)否認(rèn)N(R)幀幀確認(rèn)確認(rèn)N (R) -1及前續(xù)幀及前續(xù)幀選擇選擇重發(fā)重發(fā)ARQ 8765 4321（位） 12 3 4 . . . 分組頭 數(shù)據(jù) 圖 4-12 X.25 分組的一般格式 數(shù)據(jù)（可變長、可為空） 與分組類型有關(guān)的信息（可為空） 分組類型標(biāo)識 邏輯信道號 通用格式標(biāo)識 邏輯信道組號 4、其它鏈路控制協(xié)議、其它鏈路控制協(xié)議(1) X.25分組交換網(wǎng)絡(luò)分組交換網(wǎng)絡(luò): （LAPB）FlagFlagAddressControlCheckSumInformation8bit8bit8/16bit8/16bit16/32bit可變（2）N_ISDN（Integrated Services Digital Network ）： （LAPD）基于基于D通道的鏈路控制，即：通道的鏈路控制，即：2B+DB = 64Kbps D = 16Kbps 圖 4-14 B-ISDN 與 ATM 及光纖網(wǎng)絡(luò)的關(guān)系 B-ISDN 用戶 用戶 用戶 光纖傳輸網(wǎng) A TM 網(wǎng) 基本速率基本速率主速率主速率（3）Frame Relay（LAPF） 幀中繼幀中繼(FR) FlagFlagAdd