1、1計算機與信息學院計算機與信息學院課前思考課前思考 為什么建立數據鏈路連接？為什么建立數據鏈路連接？ 數據鏈路連接與物理連接的聯系和區別？數據鏈路連接與物理連接的聯系和區別？ 數據鏈路層主要功能有哪些？數據鏈路層主要功能有哪些？ 數據鏈路層上常用的差錯控制碼有哪些？數據鏈路層上常用的差錯控制碼有哪些？ 數據鏈路層上常用的流量控制策略有哪些？數據鏈路層上常用的流量控制策略有哪些？ 常用的數據鏈路層協議有哪些？常用的數據鏈路層協議有哪些？第四章第四章 數據鏈路層數據鏈路層2計算機與信息學院計算機與信息學院本章內容本章內容4.1 概述概述4.2 差錯控制差錯控制4.3 流量控制流量控制 4.4 數據

2、鏈路層協議舉例數據鏈路層協議舉例3計算機與信息學院計算機與信息學院4.1 概述概述 數據鏈路層主要功能數據鏈路層主要功能 在相鄰節點之間保證數據幀的在相鄰節點之間保證數據幀的“透明透明”傳輸。傳輸。 數據幀數據幀 數據幀數據幀是數據鏈路層的最小數據傳輸單元，即是數據鏈路層的最小數據傳輸單元，即DPDU。 數據幀數據幀的一般格式：的一般格式：幀同步幀同步目的地址目的地址源地址源地址控制控制數據數據幀校驗幀校驗數據鏈路層協議涉及的主要內容數據鏈路層協議涉及的主要內容l 數據鏈路的建立與拆除數據鏈路的建立與拆除l 幀同步幀同步l 差錯控制差錯控制l 流量控制流量控制4計算機與信息學院計算機與信息學院

3、4.2 差錯控制差錯控制4.2.1 傳輸差錯的特征傳輸差錯的特征 熱噪聲熱噪聲: 傳輸介質內的分子熱運動。沖擊噪沖擊噪聲聲：外界干擾。熱噪熱噪聲聲: 干擾幅度小，持續性，對模擬通信影響大。 沖擊噪沖擊噪聲聲：干擾幅度大，突發性，對數字通信影響大。 特征特征 如數據率為9600bps，一次閃電持續時間約為10ms，則連續破壞96位。 差錯產生的主要原因差錯產生的主要原因 計算機網絡中，差錯控制主要針對沖擊噪聲。計算機網絡中，差錯控制主要針對沖擊噪聲。5計算機與信息學院計算機與信息學院4.2 差錯控制差錯控制4.2.2 差錯控制方法差錯控制方法 通過特殊的編碼（差錯控制碼），使接收端能夠發現甚至自

4、動糾正錯誤。差錯控制編碼差錯控制編碼l檢錯碼：檢錯碼：能夠發現差錯，但無法自動糾正差錯，通過發送方重傳來 獲得正確的數據。l糾錯碼：糾錯碼：不但能過發現差錯，而且知道哪些位出錯，從而能夠自動 糾正差錯。4.2.3 編碼的檢錯和糾錯能力、編碼效率編碼的檢錯和糾錯能力、編碼效率 定義定義l碼字：碼字：碼字由信息位串和校驗位串（冗余位串）組成。設信息位 為m位，校驗位為r位，則碼字長度為n=m+r。6計算機與信息學院計算機與信息學院4.2 差錯控制差錯控制l兩個碼字的距離兩個碼字的距離 兩個等長碼字的不同位數稱為這兩個碼字的距離，簡稱碼距。兩個等長碼字的不同位數稱為這兩個碼字的距離，簡稱碼距。 如：

5、如：10001001 10110001 則這兩個碼字的距離為則這兩個碼字的距離為3。l海明距離海明距離 給定某種編碼規則，就能夠造出包含全部合法碼字的碼字給定某種編碼規則，就能夠造出包含全部合法碼字的碼字表（編碼系統）；該碼字表中必存在著兩個碼字，使得這兩個表（編碼系統）；該碼字表中必存在著兩個碼字，使得這兩個碼字的距離最小；該最小距離稱為該碼字表（編碼系統）的碼字的距離最小；該最小距離稱為該碼字表（編碼系統）的海海明距離明距離。海明距離海明距離決定了編碼系統的檢錯和糾錯能力決定了編碼系統的檢錯和糾錯能力 編碼的檢錯和糾錯能力編碼的檢錯和糾錯能力l若要檢測若要檢測d位出錯，則海明距離至少為位出

6、錯，則海明距離至少為d+1。l若要糾正若要糾正d位出錯，則海明距離至少為位出錯，則海明距離至少為2d+1。7計算機與信息學院計算機與信息學院 例：設有一編碼系統的碼字表有例：設有一編碼系統的碼字表有4 4個碼字組成：個碼字組成： 0000000000 0000011111 1111100000 1111111111 因為海明距離為因為海明距離為5，可檢測出，可檢測出4位出錯，自動糾正位出錯，自動糾正2位出錯。位出錯。 如果出錯位不超過如果出錯位不超過4位，則收到的碼子必定是非法的碼子位，則收到的碼子必定是非法的碼子,即不屬即不屬于碼子表于碼子表; 如果出錯位為如果出錯位為5位，則出錯的碼子可能

7、是合法的碼子。位，則出錯的碼子可能是合法的碼子。例：例： 發送的碼子為發送的碼子為1111100000，而收到的碼子，而收到的碼子1111111111。 設收到的碼字為設收到的碼字為0000000111，如果出錯位不超過兩位，則可以，如果出錯位不超過兩位，則可以斷定其正確碼字為斷定其正確碼字為0000011111; 如果出錯位可能超過兩位（如如果出錯位可能超過兩位（如3位），則無法斷定其正確碼字是位），則無法斷定其正確碼字是 0000011111，還是，還是0000000000。 編碼效率編碼效率 R=m/n=m/(m+r) 其中，m為信息位串長度， r為校驗位串（冗余位串）長度。4.2 差錯

8、控制差錯控制8計算機與信息學院計算機與信息學院a5= a1 +a2+ a3a6= a2 +a3+ a4a7= a1 +a3+ a4 0000000 0100110 1000101 1100001 0001011 0101101 1001110 1101000 0010111 0110001 1010010 1110100 0011100 0111010 1011001 1111111顯然，編碼表的海明距離為3，能夠自動糾正一位出錯。其中，+：異或， 由式（4-1）構造的編碼表如下：(4-1) 設信息位有4位，記為a1a2a3a4；校驗位為3位，記為a5a6a7。 編碼系統中任何一個合法的碼字滿

9、足如下線性獨立的方程： 4.2 差錯控制差錯控制4.2.4 海明碼海明碼(糾錯碼糾錯碼) 構造海明碼構造海明碼9計算機與信息學院計算機與信息學院設發送方發出的碼字為： a1a2a3a4 a5a6a7 接受方收到的碼字為：b1b2b3b4 b5b6b7 令：br= ar+er r=1,2,.7 (4-2)若第r位出錯，則er=1；否則er=0。s1 s2 s3稱為校驗因子；接受方將根據校驗因子來判斷哪位出錯。 再令：s1= b1 +b2+b3+ b5 s2= b2 +b3+ b4+b6 s3= b1 +b3+b4+ b7(4-3)將（4-1）,（4-2）代入（4-3）得： s1= e1 +e2+

10、 e3+ e5 s2= e2 +e3+ e4+ e6s3= e1 +e3+ e4+ e7(4-4) 糾錯原理糾錯原理10計算機與信息學院計算機與信息學院4.2 差錯控制差錯控制根據式（4-4）:s1= e1 +e2+ e3 + e5 s2= e2 +e3+ e4 + e6s3= e1 +e3+ e4+ e7得到下表:出錯位 s1 s2 s3 1 0 11 1 0無無 0 001 1 10 1 11 0 00 1 00 0 1123456711計算機與信息學院計算機與信息學院4.2 差錯控制差錯控制l上述上述海明海明碼碼只能糾正一位出錯，而實際通信中經常發生的是突只能糾正一位出錯，而實際通信中經

11、常發生的是突發性錯誤（一連串位出錯）。發性錯誤（一連串位出錯）。l要糾正突發性出錯，則必須加大海明距離；但加大海明距離勢要糾正突發性出錯，則必須加大海明距離；但加大海明距離勢必會增加校驗位串長度，從而降低了編碼效率必會增加校驗位串長度，從而降低了編碼效率，同時也會使編同時也會使編碼系統過于復雜。碼系統過于復雜。l只要將發送方式稍做改變，就能利用糾正一位出錯的海明碼來只要將發送方式稍做改變，就能利用糾正一位出錯的海明碼來糾正多位突發錯：糾正多位突發錯： 討論討論 將k個碼字排列成一個矩陣，每行一個碼字。按列發送，一次傳輸k個碼字。 數據到達接收端后，再重新組成矩陣。如果突發長度K,則每個碼字最多

12、出現一位錯誤，而前述的海明碼恰好能夠糾正這樣的一位錯。 12計算機與信息學院計算機與信息學院4.2 差錯控制差錯控制 循環冗余碼循環冗余碼（CRC碼碼） 是目前計算機網絡中使用最廣泛的一種檢錯碼。是目前計算機網絡中使用最廣泛的一種檢錯碼。CRC碼又稱多項式碼，每個碼字對應于一個多項式。碼又稱多項式碼，每個碼字對應于一個多項式。 設碼字為a1a2a3.an，則對應的多項式為：A(x)=a1xn-1+ a2xn-2+ a3xn-3+. +an 如： 110001 x5+x4+1 4.2.5 循環冗余碼循環冗余碼( (檢錯碼檢錯碼) ) l設信息位串為a1a2a3.am ，則對應的多項式為： M(x

13、)=a1xm-1+ a2xm-2+ a3xm-3+. +aml選擇一個r次多項式G(x)作為生成多項式，按下面步驟生成校驗串：在信息位串后補r個0，對應的多項式為xrM(x)用模2不借位除法，計算余數R(x)： R(x)= MOD(xrM(x)/G(x)要發送的碼字多項式：T(x)=xrM(x)+ R(x) 編碼原理（發送端）編碼原理（發送端） 13計算機與信息學院計算機與信息學院4.2 差錯控制差錯控制例：信息位串為例：信息位串為1010001，若若G(x)= x4+x2+x+1，求，求CRC碼。碼。 解：M（x）= x6+x4+ 1 r=4 xrM(x)= x10+x8+ x4101000

14、10000 計算 ：R(x)= MOD(xrM(x)/G(x)14計算機與信息學院計算機與信息學院= x10+x8+ x4+x3+x2+ 110111 10100010000 10111T(x) = xrM(x)+ R(x)信息位串信息位串 11010 10111 1001111 11010 10111 11010 10111 11010 10111 1101R(x)= x3+x2+ 1 1010001 1101商商除數除數G(XG(X) )余數余數被除數被除數校驗位串校驗位串 4.2 差錯控制差錯控制15計算機與信息學院計算機與信息學院4.2 差錯控制差錯控制G (x) = x4+x2+x+

15、1的編碼電路R01000101輸入10111000101輸出 編碼電路編碼電路R1R2R3 譯碼原理譯碼原理( (接受端）接受端） 接受方收到一個碼字后，用同一生成多項式接受方收到一個碼字后，用同一生成多項式G(x)G(x)除該碼字多項式除該碼字多項式T T (x)(x)， 若若MOD(TMOD(T(x)/G(x)(x)/G(x)0,0,則正確則正確 若若MOD(TMOD(T (x)/G(x)(x)/G(x)0,0,則出錯則出錯思考：思考： 若若MOD(T(x)/ /G(x)0, 是否一定正確是否一定正確? 若若MOD(T(x)/ /G(x) 0，是否一定出錯，是否一定出錯?16計算機與信息學

16、院計算機與信息學院4.2 差錯控制差錯控制l若若G(x)含有含有x+1因子，則能檢測出所有的奇數位錯。因子，則能檢測出所有的奇數位錯。l若若G(x)含有常數項含有常數項1，那么能檢測出所有突發長度，那么能檢測出所有突發長度r的突發錯。的突發錯。l若若G(x)含有常數項含有常數項1，且對任何，且對任何01， 接收窗口尺寸接收窗口尺寸WR=1。發送方連續發送發送方連續發送n幀而無需對方應答，但需要將已發出但尚幀而無需對方應答，但需要將已發出但尚未得到確認的幀保存在發送窗口中，以備重發。未得到確認的幀保存在發送窗口中，以備重發。接收方將正確的且幀序號落入當前接收窗口的幀存入接收窗接收方將正確的且幀序

17、號落入當前接收窗口的幀存入接收窗口，同時按序將接收窗口的幀送交給主機（網絡層）。出錯口，同時按序將接收窗口的幀送交給主機（網絡層）。出錯或幀序號未落入當前窗口的幀予以丟棄。或幀序號未落入當前窗口的幀予以丟棄。當某幀丟失或出錯時，則其后到達的幀均丟棄，并返回否認當某幀丟失或出錯時，則其后到達的幀均丟棄，并返回否認信息，請求對方從出錯幀開始重發。信息，請求對方從出錯幀開始重發。發送方設置一個超時計時器，當連續發送發送方設置一個超時計時器，當連續發送n幀后，立即啟動幀后，立即啟動超時計時器；若超時且未收到應答，則重發這超時計時器；若超時且未收到應答，則重發這n幀。幀。 順序接收管道協議順序接收管道協

18、議 （回退（回退n協議）協議）l 協議描述協議描述23計算機與信息學院計算機與信息學院4.3 流量控制流量控制l 優點：僅需一個接收緩沖區。優點：僅需一個接收緩沖區。l 缺點：當信道誤碼率較高時，會產生大量重發幀。缺點：當信道誤碼率較高時，會產生大量重發幀。 選擇重傳協議選擇重傳協議l 發送窗口尺寸發送窗口尺寸WT= n 1， 接收窗口尺寸接收窗口尺寸WR=m 1 。l若某一幀出錯，后面正確到達的幀雖然不能立即送網絡層，但可若某一幀出錯，后面正確到達的幀雖然不能立即送網絡層，但可將其保存在接收窗口；因此，僅需重傳出錯幀。將其保存在接收窗口；因此，僅需重傳出錯幀。l 優點：僅需重傳出錯幀，不會產

19、生大量重發幀。優點：僅需重傳出錯幀，不會產生大量重發幀。l 缺點：需要多個接收緩沖區。缺點：需要多個接收緩沖區。24計算機與信息學院計算機與信息學院4.3 流量控制流量控制協議協議 發送窗口發送窗口 接收窗口接收窗口 停等 1 1 回退n 1 1 選擇重傳 1 1停停等等 、順序接收管道、選擇重傳協議都可以看成是滑動窗口協、順序接收管道、選擇重傳協議都可以看成是滑動窗口協 議，其差別僅在窗口的尺寸不同，如下表所示議，其差別僅在窗口的尺寸不同，如下表所示 ： 設幀序號的位數為設幀序號的位數為m，則：，則： WTWR WT+ WR2m若若WR WT ，則有，則有 WR-WT個窗口永遠用不上。個窗口

20、永遠用不上。 WT+ WR2m保證了上一輪幀序號和下一輪序號在保證了上一輪幀序號和下一輪序號在WT+ WR范圍內不會范圍內不會出現重復；否則，接收端無法判斷落入窗口的幀是屬于哪一輪的。出現重復；否則，接收端無法判斷落入窗口的幀是屬于哪一輪的。 25計算機與信息學院計算機與信息學院4.3 流量控制流量控制例：設例：設m=3, , WT =7, , WR=2，顯然，顯然，WR+WT2m。發送窗口首先連續發送發送窗口首先連續發送7幀（幀（0-6號幀）。號幀）。假設這假設這7幀全部正確到達，接收端收到后返回幀全部正確到達，接收端收到后返回“確認確認”，并將接，并將接收窗口向前滑動收窗口向前滑動7個窗口

21、，即當前窗口為個窗口，即當前窗口為7號和號和0號。號。假設假設“確認確認”丟失，由于發送端超時收不到丟失，由于發送端超時收不到“確認確認” 而誤認為所而誤認為所發送的幀全部丟失，于是重發發送的幀全部丟失，于是重發0-6號幀。號幀。重發的重發的0號幀又落入接收窗口而被重復接收，并被誤認為下一輪號幀又落入接收窗口而被重復接收，并被誤認為下一輪幀的幀的0號幀而遞交給主機。號幀而遞交給主機。26計算機與信息學院計算機與信息學院4.4 數據鏈路層協議舉例數據鏈路層協議舉例4.4.1 HDLC協議協議 HDLC (High Level Data Control) 是一種是一種典型的數據鏈路層協議，典型的數

22、據鏈路層協議，該協議該協議“面向比特面向比特”，即以，即以“比特比特”作為數據幀的基本數據單位。作為數據幀的基本數據單位。 HDLC幀格式幀格式l 標志標志標志標志地址地址 控制控制 數據數據幀檢驗幀檢驗標志標志 字節數： 1 1 1 任意 2 1幀同步標志，固定為幀同步標志，固定為“01111110”，標志著一個幀的開始與結束。，標志著一個幀的開始與結束。連續發送多幀時，可用一個標志字段，既表示幀的開始，又表示幀連續發送多幀時，可用一個標志字段，既表示幀的開始，又表示幀的結束。的結束。為了避免其它字段中出現為了避免其它字段中出現“01111110”，HDLC采用采用插插“0”技術：技術：27

23、計算機與信息學院計算機與信息學院4.4 數據鏈路層協議舉例數據鏈路層協議舉例其后為“0”，則自動去掉該“0”。為“1”則出錯。其后為“1”，則檢查下一位：為“0”則為標志位。 發送方：除標志位外，連續發送5個“1”后自動插“0”。接收方：連續收到5個“1”后， 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0例：例：某一非標志字段中恰好出現“0111111001111110”，被誤認為是標志字段：0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0發送端連續發送 5 個“1”后，填入1個“

24、0”：接收端將 5 個連 1 之后的“0”刪除：28計算機與信息學院計算機與信息學院4.4 數據鏈路層協議舉例數據鏈路層協議舉例l 地址地址全全“1”為廣播地址，全為廣播地址，全“0”為無效地址。為無效地址。在多點通信中，表示目的地址。在多點通信中，表示目的地址。在點到點通信中，地址沒有太大意義，一般用來區分發起方和響應方。在點到點通信中，地址沒有太大意義，一般用來區分發起方和響應方。 l 控制控制 該字段表示幀類型，幀編號及其他控制信息。該字段表示幀類型，幀編號及其他控制信息。 信息幀：信息幀：用于傳輸數據監督幀：監督幀：應答幀不帶編號和數據，相當于控制幀，包括：SNRMSNRM（置正常響應

25、模式）UAUA（無編號幀確認）FRMRFRMR（幀拒絕）DISCDISC（拆除連接）RESETRESET(復位)等。幀類型幀類型無編號幀：無編號幀：29計算機與信息學院計算機與信息學院4.4 數據鏈路層協議舉例數據鏈路層協議舉例0 0 N(S) N(S)P/FP/FN(R) N(R) 1 1 1 1M MP/FP/FM M1 10 0S SP/FP/FN(R)N(R) 1 2 3 4 5 6 7 8信息幀以“0”打頭 監督幀以“10”打頭 無編號幀以“11”打頭 N(S):N(S):表示信息幀的幀序號（0-7）。N(R):N(R):接收端期望接收的下一幀的序號。P/F P/F ：輪詢/結束位，

26、用于多點輪詢訪問方式。控制字段格式控制字段格式S S：00:00:確認以前各幀，準備接受序號從N(R)開始的后繼幀。10:10:確認以前各幀，但暫停接收后繼幀，用來進行流量控制。01:01:否認N(R)起的各幀，請求重發序號從N(R)開始的各幀。11:11:僅否認 N(R)幀，請求重發序號為N(R)的單幀。M M：共5位，表示32種控制功能。30計算機與信息學院計算機與信息學院4.4 數據鏈路層協議舉例數據鏈路層協議舉例要傳輸的數據，即高層的報文分組，可以是任意二進制位的組合。l 數據數據l 幀校驗幀校驗 16位CRCCRC碼，G(X)= CRC-CCITT = xG(X)= CRC-CCITT = x1616+x+x1212+x+x5 5+1+1。 HDLC工作原理工作原理l 建立數據鏈路連接建立數據鏈路連接SNRM網絡層網絡層網絡層網絡層HDLCHDLC物理層物理層物理層物理層UASNRMUASNRM，UA位流位流31計算機與信息學院計算機與信息學院4.4 數據鏈路層協議舉例數據鏈路層協議舉例通過層間接口通過層間接口(服務服務)，請求建立物理連接。，請求建立物理連接。請求建立鏈路