課前思考

為什么建立數據鏈路連接？數據鏈路連接與物理連接的聯系和區別？數據鏈路層主要功能有哪些？數據鏈路層上常用的差錯控制編碼有哪些？數據鏈路層上常用的流量控制策略有哪些？常用的數據鏈路層協議有哪些？第四章數據鏈路層本章內容4.1概述4.2差錯控制4.3流量控制4.4數據鏈路層協議舉例4.1概述數據鏈路層主要功能

在相鄰節點之間保證數據幀的“透明”傳輸。“透明”的含義是指無差錯、無丟失、無重復、無順序錯誤。

數據幀數據幀是數據鏈路層的最小數據傳輸單元，即DPDU。數據幀的一般格式：幀同步目的地址源地址控制數據幀校驗數據鏈路層協議涉及的主要內容數據鏈路的建立與拆除幀同步差錯控制流量控制4.2差錯控制4.2.1傳輸差錯的特征

熱噪聲:傳輸介質內的分子熱運動沖擊噪聲：外界干擾熱噪聲:干擾幅度小，持續性，對模擬通信影響大。

沖擊噪聲：干擾幅度大，突發性，對數字通信影響大。特征如數據率為9600bps，一次閃電持續時間為10ms，則連續破壞96位。差錯產生的主要原因

計算機網絡通信中，差錯控制主要針對沖擊噪聲。差錯控制差錯控制方法通過特殊的編碼（差錯控制碼），使接收端能夠發現甚至自動糾正錯誤。常用的差錯控制編碼有兩類檢錯碼能夠發現差錯，但無法自動糾正差錯，通過發送方重傳來獲得正確的數據。糾錯碼不但能過發現差錯，而且能夠知道哪里出錯，從而自動糾正差錯4.1.2編碼效率、檢錯和糾錯能力碼字碼字有信息位和校驗位（冗余位）組成。設信息位為m位，校驗位為r位，則碼字長度為n=m+r兩個碼字的距離兩個碼字的不同位數稱為這兩個碼字的距離。例：10001001和10110001的距離為3。海明距離給定某種編碼算法，就能夠造出包含全部合法碼字的碼字表（編碼系統）。該碼字表中必存在著兩個碼字之間的距離最小，這個最小距離稱為該碼字表（編碼系統）的海明距離。海明距離決定了編碼系統的檢錯和糾錯能力若檢測d位出錯，則海明距離至少為d+1.若糾正d位出錯，則海明距離至少為2d+1.例：設有一編碼系統的碼字表有4個碼字組成：0000000000000001111111111000001111111111海明距離為5，則可檢測出4位出錯，糾正兩位出錯。如果收到一個碼字：0000000111，判斷出錯。如果出錯位不超過兩位，則可以斷定其正確碼字為0000011111如果出錯為超過兩位（如3位），則無法斷定其正確碼字是0000011111，還是0000000000。編碼效率R=m/n=m/(m+r).

信息位為m位，校驗位為r位 a5=a1+a2+a3

a6=a2+a3+a4 a7=a1+a3+a40000000010011010001011100001000101101011011001110110100000101110110001101001011101000011100011101010110011111111顯然，編碼表的海明距離為3，能夠自動糾正一位出錯的編碼注：+異或，由式（4-1）構造的編碼表如下：(4-1)1950年海明發明海明碼。設海明碼的信息位有4位，記為a1a2a3a4；校驗位為3位，記為a5a6a7。編碼系統中任何一個合法的碼字必須滿足線性獨立的方程：4.1.3海明碼(糾錯碼)設發送方發出一個碼字a1a2a3a4a5a6a7，接受方收到的碼字為b1b2b3b4b5b6b7。令br=ar+err=1,2,……..7(4-2)若第r位出錯，則er=1，否則er=0.其中s1s2s3稱為校驗因子。接受方將根據校驗因子來判斷哪位出錯。

再令s1=b1+b2+b3+b5s2=b2+b3+b4+b6

s3=b1+b3+b4+b7(4-3)將（4-1），（4-2）代入（4-3）得： s1=e1+e2+e3+e5

s2=e2+e3+e4+e6s3=e1+e3+e4+e7(4-4)根據式（4-4）判斷，s1=0s2=0s3=0(4-4)s1=e1+e2+e3+e5

s2=e2+e3+e4+e6s3=e1+e3+e4+e7若第一位出錯，則s1=1s2=0s3=1以此類推。得到下表出錯位與校驗因子出錯位 s1s2s3101110無 0 0 01110111000100011234567如果7個碼位均不出錯，則海明距離只能糾正一位出錯，而實際通信過程中經常發生的是突發性錯誤（一連串位出錯）。要糾正這樣的突發性出錯，則必須加大海明距離；但加大海明距離勢必會增加校驗位長度，從而降低了編碼效率。同時也會使編碼系統過于復雜。只要將發送方式稍做改變，就能利用糾正一位出錯的海明碼來糾正突發錯。設每次傳輸的數據塊有k個碼字組成，將這k個碼字排列成一個矩陣，每行一個碼字若要糾正突發錯，則按列發送，數據塊到達接受端，再重新組成矩陣。如果突發長度≦K,則每個碼字最多出現一位錯誤，而前述的海明碼正好能夠糾正這樣的一位錯。應用：ATM網對信元的自動糾錯。4.1.4循環冗余碼(檢錯碼)

循環冗余碼簡稱為CRC碼(CyclicRedunancyCode)是目前計算機網絡中使用最廣泛的一種檢錯碼CRC碼又稱多項式碼，每個碼字對應于一個多項式。 設碼字為a1a2a3….an，則對應的多項式為： A(x)=a1xn-1+a2xn-2+a3xn-3+.…+an 如110001→x5+x4+1編碼原理（發送端）設信息位串為a1a2a3….am，則信息編碼多項式為M(x)=a1xm-1+a2xm-2+a3xm-3+.…+am選擇一個r次多項式G(x)作為生成多項式，按下面步驟生成校驗串：在信息位串后補r個0，對應的多項式為xrM(x).用模2不借位除法，計算余數R(x)R(x)=MOD(xrM(x)/G(x))要發送的碼字多項式T(x)=xrM(x)+R(x)例：信息位串為1010001，若G(x)=x4+x2+x+1，求CRC碼。解：M（x）=x6+x4+1r=4 xrM(x)=x10+x8+x4

→10100010000計算R(x)=MOD(xrM(x)/G(x))=x10+x8+x4+x3+x2+1101111010001000010111T(x)=xrM(x)+R(x)信息位串110101011110011111101010111110101011111010101111101R(x)=x3+x2+1

10100011101→商除數G(X)余數被除數校驗位串編碼電路G（x）=x4+x2+x+1的編碼電路x0x1x2x3＋＋＋輸入輸出開關譯碼原理（接收端）接受方收到一個碼字后用同一生成多項式G(x)除該碼字多項式T′(x)若MOD(T′(x))/G(x))=0則正確若MOD(T′(x))/G(x))≠0則出錯，要求重發譯碼電路（

G（x）=x4+x2+x+1）x0x1x2x3出錯檢測信號＋＋＋＋CRC碼檢錯能力思考：1.若MOD(T′(x))/G(x))=0，是否一定正確2.若MOD(T′(x))/G(x))≠0，是否一定出錯CRC碼不能100%的發現錯誤，當余數為“0”時可能發生錯誤。CRC檢錯率取決于生成多項式G(x)生成多項式性質若G(x)中含有x+1因子，則能檢測出所有的奇數位錯。若G(x)中不含有x因子，或者說，G(x)含有常數項1，那么能檢測出所有突發長度≦r的突發錯。若G(x)中不含有x因子，且對任何0<e≤n-1的e,除不盡xe+1,則能檢測出所有的雙位錯。若G(x)中不含有x因子，則對于突發長度為r+1的突發錯誤的漏校率為2-(r-1).若G(x)中不含有x因子,則對突發長度大于r+1的突發錯誤的漏校率為2-r.三個標準CRC生成多項式：CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+14.1.5其它差錯控制編碼奇偶校驗碼定比碼指定每個碼字中均含有相同數目的“1”編碼效率R=log2Cnm/n(n為碼字的長度，m為“1”的數目。)編碼效率較低。檢錯能力除了碼字中“1”變為“0”和“0”變為“1”成對出現外，其余所有差錯都能被檢測出來，正反碼4.2流量控制4.2.1?！葏f議AB發送方接收方發送方發送一幀后，等待對方的應答。接收端收到一幀后，檢查校驗位串。若出錯，返回“否認”信息；若無錯，返回“確認”信息。發送端收到“確認”后，立即發送下一幀；收到“否認”則重發該幀。發送端發送一幀后，立即啟動超時計時器。若超時中斷，重發該幀。接收端應保存最近收到的幀序號，若下一個到達幀的序號與該序號相同，則丟棄并返回“確認”信息。?！葏f議缺點信道利用率低優點簡單信道最大利用率B為信道速率，L為幀長，R為信號在信道中的單程傳播延時，U為信道的最大利用率。U=L/B

L/B+2R如考慮由于差錯造成的重發，以及幀頭、校驗和冗余信息，信道實際利用率達不到最大利用率，實際利用率見P90接收方發送方L/B2R數據幀ACK幀時間4.2.2滑動窗口協議基本思想為提高信道利用率，允許發送方連續發送若干幀后再等待對方應答。基本概念窗口：可容納數據幀的緩沖區。發送窗口：發送方用來保存已發送但尚未經確認的數據幀。接收窗口：接收方用來保存已正確接受但尚未提交給主機(網絡層)數據幀。窗口尺寸：窗口中可以保存的幀數目稱為窗口尺寸。幀序號為了保證接收方能按正確次序向主機遞交數據幀而設立的臨時幀序號。一般在幀控制字段中用若干位來表示幀序號。如果用3位來表示，則幀序號為0—7。當一次通信超過8幀時，則順序重復使用這8個幀序號。窗口號：對應幀序號?；瑒哟翱趨f議的基本規則只有幀序號落入當前窗口的幀才有資格發送，發送方收到對方確認信息后，將發送窗口向前滑動（順序改變當前窗號）。只有幀序號落入當前窗口的幀才接收，否則丟棄，接收方接收窗口中的幀遞交給主機后，接收窗口向前滑動（順序改變當前窗號）。WT=2,接收窗口尺寸WR=1.順序接收管道協議（回退n）接收窗口尺寸為1的滑動窗口協議，也稱回退n協議。設發送窗口尺寸WT=n,接收窗口尺寸WR=1.發送方可連續發送n幀而無需對方應答，但需要將已發出但尚未收到確認的幀保存在發送窗口中，以備由于出錯或丟失而重發。接收方將正確的且幀序號落入當前接收窗口的幀存入接收窗口，同時按序將接收窗口的幀送交給主機（網絡層）。出錯或幀序號未落入當前窗口的幀全部予以丟棄。當某幀丟失或出錯時，則其后到達的幀均丟棄，并返回否認信息，請求對方從出錯幀開始重發。發送方設置一個超時計時器，當連續發送n幀后，立即啟動超時計時器。當超時計時器滿且未收到應答，則重發這n幀。回退n選擇重傳協議順序接收管道協議優點：僅需一個接收緩沖區缺點：當信道誤碼率較高時，會產生大量重發幀另一種更好的方法：選擇重傳協議若某一幀出錯，后面正確到達的幀雖然不能立即送網絡層，但接收方可將其保存在接收窗口，僅要求發送方重傳那個發錯幀。其工作原理如P94小結停—等協議、順序接收管道協議、選擇重傳協議都可以看成是滑動窗口協議，其差別僅在窗口的尺寸不同。如下表所示協議發送窗口接收窗口?！?1回退n>11選擇重傳>1>1窗口尺寸受到的限制幀序號的位數為m，則WT≥WRWT+WR≤2m分析：若WR>WT會有WR-WT個窗口永遠用不上。

WT+WR≤2m保證了上一輪幀序號和下一輪序號在WT+WR范圍內不會出現重復，否則接收端無法判斷落入窗口的幀是上輪重發的還是新的幀。WT+WR>2m錯誤分析設m=3,WT=7,WR=2,顯然，WR+WT﹥2m.發送窗口首先連續發送7幀（0-6號幀）假設這7幀全部正確到達，接收端發出確認信息，并將接收窗口向前滑動7個窗口，即當前窗口為7號和0號接收端發出的確認信息全部丟失，發送端由于收不到確認信息而誤認為接收端沒有發送幀，由于超時計時器重新啟動0-6號幀。重發的0號幀又落入接收窗口而被重復接收，并被誤認為下一輪幀遞交給主機。4.3數據鏈路層協議舉例4.3.1HDLC協議HDLC(HighLevelDataControl)協議是一種面向比特的鏈路層協議。所謂“面向比特”是指以二進制位作為數據幀的基本數據單位。HDLC是ISO在IBM的SDLC(SynchronousDataLinkControl)的基礎上制定的。該協議已成為鏈路層協議的典型代表。HDLC幀格式標志地址 控制數據幀檢驗標志字節數111任意 21標志固定為0111110，標志著一個幀的開始和結束。具有幀之間的同步作用。在連續發送多幀時，可用一個標志字段，既表示幀的開始，又表示幀的結束。插“0”技術為了避免其它字段中出現“01111110”，產生誤解，HDLC采用插“0”技術發送方：除標志位外，連續發現5個“1”后自動插“0”。接收方：連續發現5個“1”后其后為“0”，則自動去掉該“0”。為“1”則出錯其后為“1”，則檢查下一位為“0”則為標志位“0”的插入與刪除數據中某一段比特組合恰好出現標志字段01001111110001010會被誤認為是標志字段發送端在5個連1之后填入0比特再發送出去填入0比特010011111010001010在接收端將5個連1之后的0比特刪除，恢復原樣在此位置刪除填入的0比特010011111010001010地址全“1”為廣播地址，全“0”為無效地址。在非平衡方式中，總是填入次站地址在平衡方式中，總是填入應答站地址，用來區分命令和響應。BCD響應（B）響應（C）響應（D）命令（B）或（C）或（D）

次站次站次站

主站A非平衡方式

命令（A）

AB響應（A）

復合站命令（B）復合站響應（B）平衡方式控制：該字段表示幀類型，幀編號及其他控制信息。 。

信息幀：含有要傳輸的數據監督幀：應答幀不帶編號和數據，相當于控制幀SNRM（置正常響應模式）UA（無編號幀確認）FRMR（幀拒絕）DISC（拆除連線）RESET(復位)等。幀類型無編號幀：控制字段的格式0N(S)P/FN(R)11MP/FM10SP/FN(R)12345678信息幀“0”打頭監督幀“10”打頭無編號幀“11”打頭N(S):表示信息幀的幀序號0-7，以便標識信息幀的發送順序。N(R):接收端期望接收的下一幀的序號。P/F：輪詢/結束位，用于多點輪詢訪問方式。HDLC幀格式00:確認以前各幀，準備接受后繼幀。10:確認以前各幀，但暫停接收后繼幀，用來進行流量控制。01:否認N(R)起的各幀，請求重發從N(R)開始的各幀。11:僅否認N(R)幀，請求重發N(R)那一幀。SM：共5位，表示25=32種控制功能。數據：要傳輸的數據，可以是任意二進制位的組合，即高層的報文分組。幀校驗：16位CRC碼，G(X)=CRC-CCITT=x16+x12+x5+1HDLC工作原理分三個階段:建立數據鏈路連接傳輸數據幀當數據鏈路建立完畢，發送/接收方按照某種流量控制策略發送和接收數據幀，