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

課前思考

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

在相鄰節(jié)點(diǎn)之間保證數(shù)據(jù)幀的“透明”傳輸?！巴该鳌钡暮x是指無差錯、無丟失、無重復(fù)、無順序錯誤。

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

熱噪聲:傳輸介質(zhì)內(nèi)的分子熱運(yùn)動沖擊噪聲：外界干擾熱噪聲:干擾幅度小，持續(xù)性，對模擬通信影響大。

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

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

信息位為m位，校驗(yàn)位為r位 a5=a1+a2+a3

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

再令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)根據(jù)式（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以此類推。得到下表出錯位與校驗(yàn)因子出錯位 s1s2s3101110無 0 0 01110111000100011234567如果7個碼位均不出錯，則海明距離只能糾正一位出錯，而實(shí)際通信過程中經(jīng)常發(fā)生的是突發(fā)性錯誤（一連串位出錯）。要糾正這樣的突發(fā)性出錯，則必須加大海明距離；但加大海明距離勢必會增加校驗(yàn)位長度，從而降低了編碼效率。同時也會使編碼系統(tǒng)過于復(fù)雜。只要將發(fā)送方式稍做改變，就能利用糾正一位出錯的海明碼來糾正突發(fā)錯。設(shè)每次傳輸?shù)臄?shù)據(jù)塊有k個碼字組成，將這k個碼字排列成一個矩陣，每行一個碼字若要糾正突發(fā)錯，則按列發(fā)送，數(shù)據(jù)塊到達(dá)接受端，再重新組成矩陣。如果突發(fā)長度≦K,則每個碼字最多出現(xiàn)一位錯誤，而前述的海明碼正好能夠糾正這樣的一位錯。應(yīng)用：ATM網(wǎng)對信元的自動糾錯。4.1.4循環(huán)冗余碼(檢錯碼)

循環(huán)冗余碼簡稱為CRC碼(CyclicRedunancyCode)是目前計算機(jī)網(wǎng)絡(luò)中使用最廣泛的一種檢錯碼CRC碼又稱多項式碼，每個碼字對應(yīng)于一個多項式。 設(shè)碼字為a1a2a3….an，則對應(yīng)的多項式為： A(x)=a1xn-1+a2xn-2+a3xn-3+.…+an 如110001→x5+x4+1編碼原理（發(fā)送端）設(shè)信息位串為a1a2a3….am，則信息編碼多項式為M(x)=a1xm-1+a2xm-2+a3xm-3+.…+am選擇一個r次多項式G(x)作為生成多項式，按下面步驟生成校驗(yàn)串：在信息位串后補(bǔ)r個0，對應(yīng)的多項式為xrM(x).用模2不借位除法，計算余數(shù)R(x)R(x)=MOD(xrM(x)/G(x))要發(fā)送的碼字多項式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→商除數(shù)G(X)余數(shù)被除數(shù)校驗(yàn)位串編碼電路G（x）=x4+x2+x+1的編碼電路x0x1x2x3＋＋＋輸入輸出開關(guān)譯碼原理（接收端）接受方收到一個碼字后用同一生成多項式G(x)除該碼字多項式T′(x)若MOD(T′(x))/G(x))=0則正確若MOD(T′(x))/G(x))≠0則出錯，要求重發(fā)譯碼電路（

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

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

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

次站次站次站

主站A非平衡方式

命令（A）

AB響應(yīng)（A）

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

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