單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,計(jì)算機(jī)網(wǎng)絡(luò),第三章 數(shù)據(jù)鏈路層,主要內(nèi)容,組幀,差錯(cuò)檢測(cè),可靠交付,停,-,等協(xié)議,滑動(dòng)窗口協(xié)議,數(shù)據(jù)鏈路層協(xié)議舉例,HDLC,協(xié)議,PPP,協(xié)議,1.,組幀,使用字符填充的起止標(biāo)記法,使用特殊的字符表示幀的開始與結(jié)束。,使用,字符填充,（在特殊字符前加轉(zhuǎn)義字符）解決透明傳輸問(wèn)題。,該方法依賴于特定的字符編碼集，幀長(zhǎng)必須是,8,比特的整倍數(shù)，靈活性差，處理開銷大。,使用比特填充的起止標(biāo)記法,使用一個(gè)特殊的比特模式（,01111110,）作為幀的起始與結(jié)束標(biāo)志。,使用,比特填充,（連續(xù),5,個(gè),1,后插入一個(gè),0,）解決透明傳輸問(wèn)題。,該方法不依賴于特定的字符編碼集，靈活性強(qiáng)，處理簡(jiǎn)單。,違法編碼法,使用物理層編碼中的無(wú)效編碼表示幀的邊界。,字符填充示例,比特填充示例,2.,差錯(cuò)檢測(cè),出錯(cuò)的類型,單個(gè)錯(cuò)：,由隨機(jī)的信道熱噪聲引起，一次只影響,1,位。,突發(fā)錯(cuò),：,由瞬間的脈沖噪聲引起，一次影響許多位，用突發(fā)長(zhǎng)度表示突發(fā)錯(cuò)影響的最大數(shù)據(jù)位數(shù)。,差錯(cuò)編碼的類型,檢錯(cuò)碼：只能檢測(cè)出傳輸錯(cuò)誤，但無(wú)法自行糾正，通常與反饋重傳結(jié)合起來(lái)進(jìn)行差錯(cuò)恢復(fù)。,糾錯(cuò)碼：能夠檢測(cè)出傳輸錯(cuò)誤并糾正。,如何檢測(cè)與糾正錯(cuò)誤？,碼字（,codeword,）：由,m,比特的數(shù)據(jù)（消息）加上,r,比特的冗余（校驗(yàn)位）構(gòu)成。,有效編碼集：由,2,m,個(gè)有效碼字組成。,檢錯(cuò)：當(dāng)收到的碼字為無(wú)效碼字時(shí)檢測(cè)出錯(cuò)誤。,海明距離（,Hamming Distance,）：兩個(gè)碼字的對(duì)應(yīng)位上取值不同的位數(shù)。,糾錯(cuò)：將收到的無(wú)效碼字糾正到距其最近的有效碼字。,檢錯(cuò)碼與糾錯(cuò)碼的能力都是有限的。,編碼集的檢錯(cuò)與糾錯(cuò)能力,編碼集的海明距離：編碼集中任意兩個(gè)有效碼字的海明距離的最小值。,檢錯(cuò)能力：為檢測(cè)出,d,比特錯(cuò)誤，編碼集的海明距離至少應(yīng)為,d+1,；,奇偶校驗(yàn)是能夠檢測(cè)出,1,比特錯(cuò)誤的檢錯(cuò)碼。,糾錯(cuò)能力：為糾正,d,比特錯(cuò)誤，編碼集的海明距離至少應(yīng)為,2d+1,。,結(jié)論：差錯(cuò)編碼的檢錯(cuò),/,糾錯(cuò)能力與編碼集的海明距離有關(guān)。海明距離越大，檢錯(cuò)糾錯(cuò)能力就越強(qiáng)；但所需的冗余信息也越多，編碼效率就越低。,二維奇偶,校驗(yàn),對(duì)一個(gè),kn,比特的信息矩陣的每一行和每一列計(jì)算奇偶校驗(yàn)位。,循環(huán)冗余碼（,CRC,）,CRC,是一種多項(xiàng)式編碼，它將位串看成是某個(gè)一元多項(xiàng)式的系數(shù)，如,1011001,看成是一元多項(xiàng)式,X,6,+X,4,+X,3,+1,的系數(shù)。,信息多項(xiàng)式,M(x),：,由,m,個(gè)信息比特為系數(shù)構(gòu)成的多項(xiàng)式。,冗余多項(xiàng)式,R(x),：,由,r,個(gè)冗余比特為系數(shù)構(gòu)成的多項(xiàng)式。,碼多項(xiàng)式,T(x),：,在,m,個(gè)信息比特后加上,r,個(gè)冗余比特構(gòu)成的碼字所對(duì)應(yīng)的多項(xiàng)式，表達(dá)式為,T(x)=,x,r,M(x,)+R(x),。,生成多項(xiàng)式,G(x),：,雙方預(yù)先確定用來(lái)計(jì)算,R(x),的一個(gè)多項(xiàng)式。,編碼方法,：用對(duì)應(yīng)于,G(x),的位串去除對(duì)應(yīng)于,x,r,M(x,),的位串，所得的余式即為,R(x),，,將其,附加到信息比特串的后面一起發(fā)送。,校驗(yàn)方法,：用,對(duì)應(yīng)于,G(x),的位串去除對(duì)應(yīng)于,T(x),的位串，若余式為,0,則認(rèn)為傳輸正確，否則認(rèn)為傳輸錯(cuò)誤。,CRC,碼檢錯(cuò)能力強(qiáng)，實(shí)現(xiàn)簡(jiǎn)單快捷，是應(yīng)用最廣泛的檢錯(cuò)碼。,CRC,的編碼及校驗(yàn),例,1,：,G(X)=X,4,+X+1,，,對(duì),10110011,進(jìn)行,CRC,編碼。,例,2,：仍取,G(X)=X,4,+X+1,，判斷收到的位串,100101111001,是否有錯(cuò)？,常見的,CRC,多項(xiàng)式,CRC,C(x,),CRC-8,X,8,+X,2,+X,1,+1,CRC-10,X,10,+X,9,+X,5,+X,4,+X,1,+1,CRC-12,X,12,+X,11,+X,3,+X,2,+1,CRC-16,X,16,+X,15,+X,2,+1,CRC-CCITT,X,16,+X,12,+X,5,+1,CRC-32,X,32,+X,26,+X,23,+X,22,+X,16,+X,12,+X,11,+X,10,+X,8,+X,7,+X,5,+X,4,+X,2,+X,1,+1,3.,可靠交付,差錯(cuò)恢復(fù)的兩種辦法：,使用糾錯(cuò)碼，由接收端自動(dòng)糾正錯(cuò)誤。,使用檢錯(cuò)碼，采用自動(dòng)重傳請(qǐng)求（,ARQ,）保證可靠交付。這是數(shù)據(jù)鏈路層（及傳輸層）上最常使用的可靠交付方式。,兩種,ARQ,算法：,停,-,等,滑動(dòng)窗口,3.1,停,-,等算法,基本思想：發(fā)送方發(fā)完一幀后即停下來(lái)等待確認(rèn)；如果收到一個(gè)確認(rèn)，接著發(fā)送下一個(gè)幀；如果定時(shí)器超時(shí)，重發(fā)剛才的幀。,停,-,等算法的四種情形,。,停,-,等算法的超時(shí)值對(duì)性能影響很大，必須仔細(xì)選擇。,為區(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)前期望接收的幀序號(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ù),停,-,等算法在傳輸延遲較長(zhǎng)的信道上傳輸效率很低。,假如將鏈路看成是一根管道，數(shù)據(jù)是管道中流動(dòng)的水，那么停,-,等算法無(wú)法使數(shù)據(jù)充滿管道，因而信道利用率很低。,管道的容量通常用延遲,-,帶寬乘積表示，它表示發(fā)送端在收到第一個(gè)幀的確認(rèn)前最多可以發(fā)送的數(shù)據(jù)量。,滑動(dòng)窗口機(jī)制允許發(fā)送端連續(xù)發(fā)送多個(gè)幀來(lái)盡可能多地填充管道，從而提高信道的利用率。,3.2,滑動(dòng)窗口,滑動(dòng)窗口是計(jì)算機(jī)網(wǎng)絡(luò)中最著名的算法，它可以應(yīng)用在數(shù)據(jù)鏈路層及傳輸層，用來(lái)完成三個(gè)不同的任務(wù)：,在不可靠的鏈路（網(wǎng)絡(luò)）上可靠地傳輸數(shù)據(jù),保持?jǐn)?shù)據(jù)的傳輸順序,支持流量控制,在數(shù)據(jù)鏈路層上，以上三個(gè)功能組合在一個(gè)滑動(dòng)窗口協(xié)議中。,發(fā)送窗口,發(fā)送窗口：發(fā)送端允許發(fā)送的幀序號(hào)表。,發(fā)送窗口大?。喊l(fā)送端最大允許的未確認(rèn)幀數(shù)目。,發(fā)送窗口下沿：最早發(fā)送但尚未被確認(rèn)的幀序號(hào)。,發(fā)送窗口上沿：（發(fā)送窗口下沿發(fā)送窗口大小,1,）,mod 2,n,。,當(dāng)收到對(duì)發(fā)送窗口下沿幀的確認(rèn)時(shí)，發(fā)送窗口整體向前滑動(dòng)一個(gè)序號(hào)，將已被確認(rèn)的幀移出發(fā)送窗口，并加入一個(gè)新的序號(hào)。（,圖,）,發(fā)送窗口中的幀都保留在緩沖區(qū)中以備重傳，當(dāng)某個(gè)幀被移出發(fā)送窗口時(shí)，同時(shí)從緩沖區(qū)中刪除。,當(dāng)發(fā)送窗口滿時(shí)，停止從網(wǎng)絡(luò)層接收數(shù)據(jù)，直到有一個(gè)緩沖區(qū)空出來(lái)為止。,發(fā)送窗口和接收窗口圖示,接收,窗口,接收窗口：接收端允許接收的幀序號(hào)表。,接收窗口大小：接收端允許接收的最大幀數(shù)。,接收窗口下沿：接收端按順序期待接收的幀序號(hào)。,當(dāng)接收端收到窗口下沿幀且校驗(yàn)正確時(shí)，將幀交給網(wǎng)絡(luò)層，向發(fā)送方發(fā)回一個(gè)確認(rèn)，然后窗口整體向前滑動(dòng)一個(gè)序號(hào)。（,圖,）,接收窗口的大小可以設(shè)為任意值，通常的設(shè)置有兩種：,接收窗口大小,=1,：意味著接收方只能按順序接收；,接收窗口大小,=,發(fā)送窗口大小：意味著接收方可以不按順序接收，但接收方交給上層實(shí)體的數(shù)據(jù)總是有序的。,捎帶確認(rèn),捎帶確認(rèn)（,piggybacking,）：將確認(rèn)序號(hào)攜帶在數(shù)據(jù)幀中傳輸，提高線路的效率。,推遲確認(rèn)：當(dāng)需要發(fā)送確認(rèn)但沒有要發(fā)送的數(shù)據(jù)時(shí)，可以讓確認(rèn)信息推遲一小段時(shí)間再發(fā)送；這一小段時(shí)間后若數(shù)據(jù)仍未準(zhǔn)備好，接收端必須立即發(fā)送一個(gè)單獨(dú)的確認(rèn)幀。,接收端對(duì)正確收到的若干個(gè)幀同時(shí)進(jìn)行確認(rèn)，通常用對(duì)某一個(gè)幀的確認(rèn)來(lái)表示對(duì)該幀之前的所有幀進(jìn)行確認(rèn)。,Go Back n,Go back n,當(dāng)接收端收到一個(gè)出錯(cuò)幀或亂序幀時(shí)，丟棄所有的后繼幀，并且不為這些幀發(fā)送確認(rèn)；發(fā)送端超時(shí)后，重傳所有未被確認(rèn)的幀。,該策略對(duì)應(yīng)接收窗口為,1,的情況，即只能按順序接收幀。,若信道的誤碼率較高，這種方法會(huì)浪費(fèi)很多帶寬，但對(duì)接收端內(nèi)存的需求不大。,Go Back N,示,意圖,選擇重傳,選擇重傳,當(dāng)接收端收到一個(gè)出錯(cuò)幀或亂序幀時(shí)，后續(xù)到達(dá)的幀只要校驗(yàn)正確且落在接收窗口內(nèi)，都放入接收緩沖區(qū)中；發(fā)送端超時(shí)后只重傳最早發(fā)送但未被確認(rèn)的幀。,該策略對(duì)應(yīng)接收窗口大于,1,的情況。,選擇重傳通常使用一個(gè)否定的確認(rèn)（,NAK,）,對(duì)校驗(yàn)出錯(cuò)或疑為丟失的幀進(jìn)行確認(rèn)，以便發(fā)送端盡快重傳該幀。,當(dāng)接收窗口很大時(shí)，這種方法要求接收端有較大的內(nèi)存，但它不浪費(fèi)帶寬。,選擇重傳示意圖,有限序號(hào)與窗口限制,使用,Go Back N,協(xié)議，發(fā)送窗口的大小不能超過(guò),2,n,-1,。,使用選擇重傳協(xié)議，若發(fā)送窗口與接收窗口大小相同，則發(fā)送窗口的大小不能超過(guò),2,n-1,。,4.,數(shù)據(jù)鏈路協(xié)議舉例,高級(jí)數(shù)據(jù)鏈路控制（,HDLC,）,點(diǎn)到點(diǎn)協(xié)議（,PPP,）,4.1 HDLC,幀,結(jié)構(gòu),：,標(biāo)志：,01111110,，標(biāo)識(shí)一幀的開始與結(jié)束，以及作為幀間填充。,地址,：,在點(diǎn)到多點(diǎn)線路中用于指明通信的終端地址，在點(diǎn)到點(diǎn)線路中用于區(qū)分命令和響應(yīng)。,控制,：,用于構(gòu)成各種命令和響應(yīng)，對(duì)鏈路進(jìn)行監(jiān)控。,信息,：,可以是任意的二進(jìn)制比特串。,校驗(yàn),：,CRC,碼，對(duì)兩個(gè)標(biāo)志之間的幀內(nèi)容進(jìn)行校驗(yàn)。,幀,類型,信息幀：,以控制字段的第一比特為“,0”,標(biāo)志。,用于傳送數(shù)據(jù)，數(shù)據(jù)放在信息字段中。,采用滑動(dòng)窗口協(xié)議，,N(S),為發(fā)送序號(hào)，,N(R),為捎帶確認(rèn)。,幀,類型（續(xù)）,監(jiān)視幀：,以控制字段的第一、二比特為“,10”,標(biāo)志。,用于差錯(cuò)控制和流量控制，沒有信息字段。,S,1,S,2,：,決定監(jiān)控幀的類型,類型,0,：接收準(zhǔn)備好,類型,1,：否定確認(rèn),類型,2,：接收未準(zhǔn)備好,類型,3,：選擇拒絕,幀,類型（續(xù)）,無(wú)編號(hào)幀：,以控制字段的第一、二比特為“,11”,標(biāo)志。,提供鏈路的建立、拆除及其它控制功能。,不包含,N(S),或,N(R),字段。,M,1,M,5,：,修正位，構(gòu)成各種鏈路命令和響應(yīng),HDLC,的訪問(wèn)規(guī)程,鏈路層的,操作分為三個(gè)階段：,建立鏈路：一方發(fā)送一個(gè)置模式命令，另一方發(fā)送,UA,幀進(jìn)行響應(yīng)，并初始化鏈路變量。,傳輸信息：,雙方使用滑動(dòng)窗口協(xié)議進(jìn)行數(shù)據(jù)傳輸控制；,對(duì)收到的信息幀使用捎帶確認(rèn)或監(jiān)視幀進(jìn)行響應(yīng)；,對(duì)檢測(cè)到錯(cuò)誤的幀使用否定確認(rèn)或選擇拒絕要求重發(fā)；,未準(zhǔn)備好接收下一幀時(shí)，用接收未準(zhǔn)備好暫停對(duì)方的發(fā)送。,斷開鏈路：一方發(fā)送一個(gè)斷連命令，另一方用一個(gè),UA,幀進(jìn)行響應(yīng)。,4.2 PPP,協(xié)議,PPP,是因特網(wǎng)中廣泛使用的點(diǎn)到點(diǎn)數(shù)據(jù)鏈路協(xié)議。,PPP,由以下三部分組成：,一種在串行通信線路上的組幀方式；,用于建立、配置、測(cè)試和拆除數(shù)據(jù)鏈路的鏈路控制協(xié)議,LCP,；,一組網(wǎng)絡(luò)控制協(xié)議（,NCP,），,用以支持不同的網(wǎng)絡(luò)層協(xié)議。,PPP,的組幀,PPP,采用與,HDLC,類似的幀結(jié)構(gòu)，不同之處是：,PPP,采用字符填充而不是比特填充。,地址字段總是,oxFF,，控制字段總是,0 x03,。,增加的協(xié)議字段說(shuō)明信息字段中攜帶的數(shù)據(jù)屬于哪個(gè)上層協(xié)議。,CRC,字段的長(zhǎng)度可以協(xié)商。,PPP,鏈路的,配置、維護(hù)和終止,