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

課前思考

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

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

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

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

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

計(jì)算機(jī)網(wǎng)絡(luò)通信中，差錯(cuò)控制主要針對(duì)沖擊噪聲。差錯(cuò)控制差錯(cuò)控制方法通過(guò)特殊的編碼（差錯(cuò)控制碼），使接收端能夠發(fā)現(xiàn)甚至自動(dòng)糾正錯(cuò)誤。常用的差錯(cuò)控制編碼有兩類檢錯(cuò)碼能夠發(fā)現(xiàn)差錯(cuò)，但無(wú)法自動(dòng)糾正差錯(cuò)，通過(guò)發(fā)送方重傳來(lái)獲得正確的數(shù)據(jù)。糾錯(cuò)碼不但能過(guò)發(fā)現(xiàn)差錯(cuò)，而且能夠知道哪里出錯(cuò)，從而自動(dòng)糾正差錯(cuò)4.1.2編碼效率、檢錯(cuò)和糾錯(cuò)能力碼字碼字有信息位和校驗(yàn)位（冗余位）組成。設(shè)信息位為m位，校驗(yàn)位為r位，則碼字長(zhǎng)度為n=m+r兩個(gè)碼字的距離兩個(gè)碼字的不同位數(shù)稱為這兩個(gè)碼字的距離。例：10001001和10110001的距離為3。海明距離給定某種編碼算法，就能夠造出包含全部合法碼字的碼字表（編碼系統(tǒng)）。該碼字表中必存在著兩個(gè)碼字之間的距離最小，這個(gè)最小距離稱為該碼字表（編碼系統(tǒng)）的海明距離。海明距離決定了編碼系統(tǒng)的檢錯(cuò)和糾錯(cuò)能力若檢測(cè)d位出錯(cuò)，則海明距離至少為d+1.若糾正d位出錯(cuò)，則海明距離至少為2d+1.例：設(shè)有一編碼系統(tǒng)的碼字表有4個(gè)碼字組成：0000000000000001111111111000001111111111海明距離為5，則可檢測(cè)出4位出錯(cuò)，糾正兩位出錯(cuò)。如果收到一個(gè)碼字：0000000111，判斷出錯(cuò)。如果出錯(cuò)位不超過(guò)兩位，則可以斷定其正確碼字為0000011111如果出錯(cuò)為超過(guò)兩位（如3位），則無(wú)法斷定其正確碼字是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，能夠自動(dòng)糾正一位出錯(cuò)的編碼注：+異或，由式（4-1）構(gòu)造的編碼表如下：(4-1)1950年海明發(fā)明海明碼。設(shè)海明碼的信息位有4位，記為a1a2a3a4；校驗(yàn)位為3位，記為a5a6a7。編碼系統(tǒng)中任何一個(gè)合法的碼字必須滿足線性獨(dú)立的方程：4.1.3海明碼(糾錯(cuò)碼)設(shè)發(fā)送方發(fā)出一個(gè)碼字a1a2a3a4a5a6a7，接受方收到的碼字為b1b2b3b4b5b6b7。令br=ar+err=1,2,……..7(4-2)若第r位出錯(cuò)，則er=1，否則er=0.其中s1s2s3稱為校驗(yàn)因子。接受方將根據(jù)校驗(yàn)因子來(lái)判斷哪位出錯(cuò)。

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

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

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

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

WT+WR≤2m保證了上一輪幀序號(hào)和下一輪序號(hào)在WT+WR范圍內(nèi)不會(huì)出現(xiàn)重復(fù)，否則接收端無(wú)法判斷落入窗口的幀是上輪重發(fā)的還是新的幀。WT+WR>2m錯(cuò)誤分析設(shè)m=3,WT=7,WR=2,顯然，WR+WT﹥2m.發(fā)送窗口首先連續(xù)發(fā)送7幀（0-6號(hào)幀）假設(shè)這7幀全部正確到達(dá)，接收端發(fā)出確認(rèn)信息，并將接收窗口向前滑動(dòng)7個(gè)窗口，即當(dāng)前窗口為7號(hào)和0號(hào)接收端發(fā)出的確認(rèn)信息全部丟失，發(fā)送端由于收不到確認(rèn)信息而誤認(rèn)為接收端沒(méi)有發(fā)送幀，由于超時(shí)計(jì)時(shí)器重新啟動(dòng)0-6號(hào)幀。重發(fā)的0號(hào)幀又落入接收窗口而被重復(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)志著一個(gè)幀的開(kāi)始和結(jié)束。具有幀之間的同步作用。在連續(xù)發(fā)送多幀時(shí)，可用一個(gè)標(biāo)志字段，既表示幀的開(kāi)始，又表示幀的結(jié)束。插“0”技術(shù)為了避免其它字段中出現(xiàn)“01111110”，產(chǎn)生誤解，HDLC采用插“0”技術(shù)發(fā)送方：除標(biāo)志位外，連續(xù)發(fā)現(xiàn)5個(gè)“1”后自動(dòng)插“0”。接收方：連續(xù)發(fā)現(xiàn)5個(gè)“1”后其后為“0”，則自動(dòng)去掉該“0”。為“1”則出錯(cuò)其后為“1”，則檢查下一位為“0”則為標(biāo)志位“0”的插入與刪除數(shù)據(jù)中某一段比特組合恰好出現(xiàn)標(biāo)志字段01001111110001010會(huì)被誤認(rèn)為是標(biāo)志字段發(fā)送端在5個(gè)連1之后填入0比特再發(fā)送出去填入0比特010011111010001010在接收端將5個(gè)連1之后的0比特刪除，恢復(fù)原樣在此位置刪除填入的0比特010011111010001010地址全“1”為廣播地址，全“0”為無(wú)效地址。在非平衡方式中，總是填入次站地址在平衡方式中，總是填入應(yīng)答站地址，用來(lái)區(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）平衡方式控制：該字段表示幀類型，幀編號(hào)及其他控制信息。 。

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