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

1、計(jì)算機(jī)網(wǎng)絡(luò) 第三章 數(shù)據(jù)鏈路層主要內(nèi)容z組幀z差錯(cuò)檢測(cè)z可靠交付y停-等協(xié)議y滑動(dòng)窗口協(xié)議z數(shù)據(jù)鏈路層協(xié)議舉例yHDLC協(xié)議yPPP協(xié)議1. 組幀z 使用字符填充的起止標(biāo)記法y使用特殊的字符表示幀的開始與結(jié)束。y使用字符填充（在特殊字符前加轉(zhuǎn)義字符）解決透明傳輸問(wèn)題。y該方法依賴于特定的字符編碼集，幀長(zhǎng)必須是8比特的整倍數(shù)，靈活性差，處理開銷大。z 使用比特填充的起止標(biāo)記法y使用一個(gè)特殊的比特模式（01111110）作為幀的起始與結(jié)束標(biāo)志。y使用比特填充（連續(xù)5個(gè)1后插入一個(gè)0）解決透明傳輸問(wèn)題。y該方法不依賴于特定的字符編碼集，靈活性強(qiáng)，處理簡(jiǎn)單。z 違法編碼法y使用物理層編碼中的無(wú)效編碼表

2、示幀的邊界。字符填充示例比特填充示例2. 差錯(cuò)檢測(cè)z出錯(cuò)的類型y單個(gè)錯(cuò)：由隨機(jī)的信道熱噪聲引起，一次只影響1位。y突發(fā)錯(cuò)：由瞬間的脈沖噪聲引起，一次影響許多位，用突發(fā)長(zhǎng)度表示突發(fā)錯(cuò)影響的最大數(shù)據(jù)位數(shù)。z差錯(cuò)編碼的類型y檢錯(cuò)碼：只能檢測(cè)出傳輸錯(cuò)誤，但無(wú)法自行糾正，通常與反饋重傳結(jié)合起來(lái)進(jìn)行差錯(cuò)恢復(fù)。y糾錯(cuò)碼：能夠檢測(cè)出傳輸錯(cuò)誤并糾正。如何檢測(cè)與糾正錯(cuò)誤？z 碼字（codeword）：由m比特的數(shù)據(jù)（消息）加上 r 比特的冗余（校驗(yàn)位）構(gòu)成。z 有效編碼集：由2m個(gè)有效碼字組成。z 檢錯(cuò)：當(dāng)收到的碼字為無(wú)效碼字時(shí)檢測(cè)出錯(cuò)誤。z 海明距離（Hamming Distance）：兩個(gè)碼字的對(duì)應(yīng)位上取值不

3、同的位數(shù)。z 糾錯(cuò)：將收到的無(wú)效碼字糾正到距其最近的有效碼字。z 檢錯(cuò)碼與糾錯(cuò)碼的能力都是有限的。編碼集的檢錯(cuò)與糾錯(cuò)能力z 編碼集的海明距離：編碼集中任意兩個(gè)有效碼字的海明距離的最小值。z 檢錯(cuò)能力：為檢測(cè)出 d 比特錯(cuò)誤，編碼集的海明距離至少應(yīng)為 d+1；奇偶校驗(yàn)是能夠檢測(cè)出1比特錯(cuò)誤的檢錯(cuò)碼。z 糾錯(cuò)能力：為糾正 d 比特錯(cuò)誤，編碼集的海明距離至少應(yīng)為 2d+1。z 結(jié)論：差錯(cuò)編碼的檢錯(cuò)/糾錯(cuò)能力與編碼集的海明距離有關(guān)。海明距離越大，檢錯(cuò)糾錯(cuò)能力就越強(qiáng)；但所需的冗余信息也越多，編碼效率就越低。 二維奇偶校驗(yàn)z 對(duì)一個(gè) kn 比特的信息矩陣的每一行和每一列計(jì)算奇偶校驗(yàn)位。 循環(huán)冗余碼（CRC

4、）z CRC是一種多項(xiàng)式編碼，它將位串看成是某個(gè)一元多項(xiàng)式的系數(shù)，如1011001看成是一元多項(xiàng)式X6 + X4 + X3 + 1的系數(shù)。z 信息多項(xiàng)式M(x)：由 m 個(gè)信息比特為系數(shù)構(gòu)成的多項(xiàng)式。z 冗余多項(xiàng)式R(x)：由 r 個(gè)冗余比特為系數(shù)構(gòu)成的多項(xiàng)式。z 碼多項(xiàng)式T(x)：在 m 個(gè)信息比特后加上 r 個(gè)冗余比特構(gòu)成的碼字所對(duì)應(yīng)的多項(xiàng)式，表達(dá)式為 T(x) = xrM(x) + R(x)。z 生成多項(xiàng)式G(x)：雙方預(yù)先確定用來(lái)計(jì)算R(x)的一個(gè)多項(xiàng)式。z 編碼方法：用對(duì)應(yīng)于 G(x) 的位串去除對(duì)應(yīng)于 xrM(x) 的位串，所得的余式即為 R(x)，將其附加到信息比特串的后面一起發(fā)

5、送。z 校驗(yàn)方法：用對(duì)應(yīng)于 G(x) 的位串去除對(duì)應(yīng)于 T(x) 的位串，若余式為0則認(rèn)為傳輸正確，否則認(rèn)為傳輸錯(cuò)誤。z CRC碼檢錯(cuò)能力強(qiáng)，實(shí)現(xiàn)簡(jiǎn)單快捷，是應(yīng)用最廣泛的檢錯(cuò)碼。CRC的編碼及校驗(yàn)z 例1：G(X) = X4 + X + 1，對(duì)10110011進(jìn)行CRC編碼。z 例2：仍取G(X) = X4 + X + 1，判斷收到的位串100101111001是否有錯(cuò)？ 常見的CRC多項(xiàng)式CRCC(x)CRC-8X8 + X2 + X1 + 1CRC-10X10 + X9 + X5 + X4 + X1 + 1CRC-12X12 + X11 + X3 + X2 + 1 CRC-16X16 +

6、X15 + X2 + 1 CRC-CCITTX16 + X12 + X5 + 1 CRC-32X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1 3. 可靠交付z差錯(cuò)恢復(fù)的兩種辦法：y使用糾錯(cuò)碼，由接收端自動(dòng)糾正錯(cuò)誤。y使用檢錯(cuò)碼，采用自動(dòng)重傳請(qǐng)求（ARQ）保證可靠交付。這是數(shù)據(jù)鏈路層（及傳輸層）上最常使用的可靠交付方式。z兩種ARQ算法：y停-等y滑動(dòng)窗口 3.1 停-等算法z 基本思想：發(fā)送方發(fā)完一幀后即停下來(lái)等待確認(rèn)；如果收到一個(gè)確認(rèn)，接著發(fā)送下一個(gè)幀；如果定時(shí)器超時(shí)，重發(fā)剛才的幀

7、。z 停-等算法的四種情形。z 停-等算法的超時(shí)值對(duì)性能影響很大，必須仔細(xì)選擇。z 為區(qū)分新幀和重發(fā)幀，停-等算法使用一比特的幀序號(hào)。停-等算法的四種情形停-等算法的過(guò)-發(fā)送方 1）幀序號(hào)初始化為0 2）從緩沖區(qū)中取出一個(gè)幀，加上當(dāng)前幀序號(hào)發(fā)送。 3）等待確認(rèn) i）收到確認(rèn)幀，且?guī)蛱?hào)與當(dāng)前維護(hù)的幀序號(hào)不同，將 幀序號(hào)加1，從緩沖區(qū)中取出一個(gè)新的幀，加上當(dāng)前 幀序號(hào)發(fā)送。 ii）收到確認(rèn)幀，且?guī)蛱?hào)與當(dāng)前維護(hù)的幀序號(hào)相同，重 發(fā)當(dāng)前序號(hào)的幀。 iii）收到錯(cuò)誤的確認(rèn)幀，重發(fā)當(dāng)前序號(hào)的幀。 iv）定時(shí)器超時(shí)，重發(fā)當(dāng)前序號(hào)的幀。停-等算法的過(guò)程-接收方 1）幀序號(hào)初始化為0（表示當(dāng)前期望接收的幀序

8、號(hào)） 2）等待接收 3）幀到達(dá) i）幀校驗(yàn)正確，且序號(hào)為當(dāng)前期望接收的幀序號(hào)，將幀 放入接收緩沖區(qū)，幀序號(hào)加1，放入確認(rèn)幀中發(fā)送。 ii）幀校驗(yàn)正確，但序號(hào)與當(dāng)前期望接收的幀序號(hào)不同， 丟棄幀，重發(fā)確認(rèn)幀。 iii）幀校驗(yàn)錯(cuò)誤，丟棄幀，重發(fā)確認(rèn)幀。信道利用率與流水線技術(shù)z停-等算法在傳輸延遲較長(zhǎng)的信道上傳輸效率很低。z假如將鏈路看成是一根管道，數(shù)據(jù)是管道中流動(dòng)的水，那么停-等算法無(wú)法使數(shù)據(jù)充滿管道，因而信道利用率很低。z管道的容量通常用延遲-帶寬乘積表示，它表示發(fā)送端在收到第一個(gè)幀的確認(rèn)前最多可以發(fā)送的數(shù)據(jù)量。z滑動(dòng)窗口機(jī)制允許發(fā)送端連續(xù)發(fā)送多個(gè)幀來(lái)盡可能多地填充管道，從而提高信道的利用率。3

9、.2 滑動(dòng)窗口z滑動(dòng)窗口是計(jì)算機(jī)網(wǎng)絡(luò)中最著名的算法，它可以應(yīng)用在數(shù)據(jù)鏈路層及傳輸層，用來(lái)完成三個(gè)不同的任務(wù)：y在不可靠的鏈路（網(wǎng)絡(luò)）上可靠地傳輸數(shù)據(jù)y保持?jǐn)?shù)據(jù)的傳輸順序y支持流量控制z在數(shù)據(jù)鏈路層上，以上三個(gè)功能組合在一個(gè)滑動(dòng)窗口協(xié)議中。發(fā)送窗口z 發(fā)送窗口：發(fā)送端允許發(fā)送的幀序號(hào)表。z 發(fā)送窗口大?。喊l(fā)送端最大允許的未確認(rèn)幀數(shù)目。z 發(fā)送窗口下沿：最早發(fā)送但尚未被確認(rèn)的幀序號(hào)。z 發(fā)送窗口上沿：（發(fā)送窗口下沿發(fā)送窗口大小1）mod 2n。 z 當(dāng)收到對(duì)發(fā)送窗口下沿幀的確認(rèn)時(shí)，發(fā)送窗口整體向前滑動(dòng)一個(gè)序號(hào)，將已被確認(rèn)的幀移出發(fā)送窗口，并加入一個(gè)新的序號(hào)。（圖）z 發(fā)送窗口中的幀都保留在緩沖區(qū)中

10、以備重傳，當(dāng)某個(gè)幀被移出發(fā)送窗口時(shí)，同時(shí)從緩沖區(qū)中刪除。z 當(dāng)發(fā)送窗口滿時(shí)，停止從網(wǎng)絡(luò)層接收數(shù)據(jù)，直到有一個(gè)緩沖區(qū)空出來(lái)為止。發(fā)送窗口和接收窗口圖示接收窗口z 接收窗口：接收端允許接收的幀序號(hào)表。z 接收窗口大小：接收端允許接收的最大幀數(shù)。z 接收窗口下沿：接收端按順序期待接收的幀序號(hào)。z 當(dāng)接收端收到窗口下沿幀且校驗(yàn)正確時(shí)，將幀交給網(wǎng)絡(luò)層，向發(fā)送方發(fā)回一個(gè)確認(rèn)，然后窗口整體向前滑動(dòng)一個(gè)序號(hào)。（圖）z 接收窗口的大小可以設(shè)為任意值，通常的設(shè)置有兩種：y接收窗口大小 = 1：意味著接收方只能按順序接收；y接收窗口大小 = 發(fā)送窗口大?。阂馕吨邮辗娇梢圆话错樞蚪邮?，但接收方交給上層實(shí)體的數(shù)據(jù)總是

11、有序的。捎帶確認(rèn)z 捎帶確認(rèn)（piggybacking）：將確認(rèn)序號(hào)攜帶在數(shù)據(jù)幀中傳輸，提高線路的效率。z 推遲確認(rèn)：當(dāng)需要發(fā)送確認(rèn)但沒(méi)有要發(fā)送的數(shù)據(jù)時(shí)，可以讓確認(rèn)信息推遲一小段時(shí)間再發(fā)送；這一小段時(shí)間后若數(shù)據(jù)仍未準(zhǔn)備好，接收端必須立即發(fā)送一個(gè)單獨(dú)的確認(rèn)幀。z 接收端對(duì)正確收到的若干個(gè)幀同時(shí)進(jìn)行確認(rèn)，通常用對(duì)某一個(gè)幀的確認(rèn)來(lái)表示對(duì)該幀之前的所有幀進(jìn)行確認(rèn)。Go Back nzGo back ny當(dāng)接收端收到一個(gè)出錯(cuò)幀或亂序幀時(shí)，丟棄所有的后繼幀，并且不為這些幀發(fā)送確認(rèn)；發(fā)送端超時(shí)后，重傳所有未被確認(rèn)的幀。y該策略對(duì)應(yīng)接收窗口為1的情況，即只能按順序接收幀。y若信道的誤碼率較高，這種方法會(huì)浪費(fèi)很

12、多帶寬，但對(duì)接收端內(nèi)存的需求不大。Go Back N 示意圖選擇重傳z選擇重傳y當(dāng)接收端收到一個(gè)出錯(cuò)幀或亂序幀時(shí)，后續(xù)到達(dá)的幀只要校驗(yàn)正確且落在接收窗口內(nèi)，都放入接收緩沖區(qū)中；發(fā)送端超時(shí)后只重傳最早發(fā)送但未被確認(rèn)的幀。y該策略對(duì)應(yīng)接收窗口大于1的情況。y選擇重傳通常使用一個(gè)否定的確認(rèn)（NAK）對(duì)校驗(yàn)出錯(cuò)或疑為丟失的幀進(jìn)行確認(rèn)，以便發(fā)送端盡快重傳該幀。y當(dāng)接收窗口很大時(shí)，這種方法要求接收端有較大的內(nèi)存，但它不浪費(fèi)帶寬。選擇重傳示意圖有限序號(hào)與窗口限制z 使用Go Back N協(xié)議，發(fā)送窗口的大小不能超過(guò) 2n-1。z 使用選擇重傳協(xié)議，若發(fā)送窗口與接收窗口大小相同，則發(fā)送窗口的大小不能超過(guò)2n-

13、1。4. 數(shù)據(jù)鏈路協(xié)議舉例z高級(jí)數(shù)據(jù)鏈路控制（HDLC）z點(diǎn)到點(diǎn)協(xié)議（PPP）4.1 HDLCz 幀結(jié)構(gòu)：y標(biāo)志：01111110，標(biāo)識(shí)一幀的開始與結(jié)束，以及作為幀間填充。y地址：在點(diǎn)到多點(diǎn)線路中用于指明通信的終端地址，在點(diǎn)到點(diǎn)線路中用于區(qū)分命令和響應(yīng)。y控制：用于構(gòu)成各種命令和響應(yīng)，對(duì)鏈路進(jìn)行監(jiān)控。y信息：可以是任意的二進(jìn)制比特串。y校驗(yàn)：CRC碼，對(duì)兩個(gè)標(biāo)志之間的幀內(nèi)容進(jìn)行校驗(yàn)。幀類型z 信息幀：y以控制字段的第一比特為“0”標(biāo)志。y用于傳送數(shù)據(jù)，數(shù)據(jù)放在信息字段中。y采用滑動(dòng)窗口協(xié)議，N(S)為發(fā)送序號(hào)，N(R)為捎帶確認(rèn)。幀類型（續(xù)）z 監(jiān)視幀：y以控制字段的第一、二比特為“10”標(biāo)志

14、。y用于差錯(cuò)控制和流量控制，沒(méi)有信息字段。yS1S2：決定監(jiān)控幀的類型 類型0：接收準(zhǔn)備好 類型1：否定確認(rèn) 類型2：接收未準(zhǔn)備好 類型3：選擇拒絕幀類型（續(xù)）z 無(wú)編號(hào)幀：y以控制字段的第一、二比特為“11”標(biāo)志。y提供鏈路的建立、拆除及其它控制功能。y不包含 N(S) 或 N(R) 字段。y M1M5：修正位，構(gòu)成各種鏈路命令和響應(yīng)HDLC的訪問(wèn)規(guī)程z鏈路層的操作分為三個(gè)階段：y建立鏈路：一方發(fā)送一個(gè)置模式命令，另一方發(fā)送UA幀進(jìn)行響應(yīng)，并初始化鏈路變量。y傳輸信息：x雙方使用滑動(dòng)窗口協(xié)議進(jìn)行數(shù)據(jù)傳輸控制；x對(duì)收到的信息幀使用捎帶確認(rèn)或監(jiān)視幀進(jìn)行響應(yīng)；x對(duì)檢測(cè)到錯(cuò)誤的幀使用否定確認(rèn)或選擇拒絕要求重發(fā)；x未準(zhǔn)備好接收下一幀時(shí)，用接收未準(zhǔn)備好暫停對(duì)方的發(fā)送。y斷開鏈路：一方發(fā)送一個(gè)斷連命令，另一方用一個(gè)UA幀進(jìn)行響應(yīng)。4.2 PPP協(xié)議zPPP是因特網(wǎng)中廣泛使用的點(diǎn)到點(diǎn)