《《計算機網(wǎng)絡原理與技術(shù)(第二版)》第3章數(shù)據(jù)鏈路層》由會員分享，可在線閱讀，更多相關(guān)《《計算機網(wǎng)絡原理與技術(shù)(第二版)》第3章數(shù)據(jù)鏈路層（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,計算機網(wǎng)絡,第三章 數(shù)據(jù)鏈路層,主要內(nèi)容,組幀,差錯檢測,可靠交付,停,-,等協(xié)議,滑動窗口協(xié)議,數(shù)據(jù)鏈路層協(xié)議舉例,HDLC,協(xié)議,PPP,協(xié)議,1.,組幀,使用字符填充的起止標記法,使用特殊的字符表示幀的開始與結(jié)束。,使用,字符填充,（在特殊字符前加轉(zhuǎn)義字符）解決透明傳輸問題。,該方法依賴于特定的字符編碼集，幀長必須是,8,比特的整倍數(shù)，靈活性差，處理開銷大。,使用比特填充的起止標記法,使用一個特殊的比特模式（,01111110,）作為幀的起始與結(jié)束標志。,使用,比特填充,（連續(xù),5,個,1,后插入一個

2、,0,）解決透明傳輸問題。,該方法不依賴于特定的字符編碼集，靈活性強，處理簡單。,違法編碼法,使用物理層編碼中的無效編碼表示幀的邊界。,字符填充示例,比特填充示例,2.,差錯檢測,出錯的類型,單個錯：,由隨機的信道熱噪聲引起，一次只影響,1,位。,突發(fā)錯,：,由瞬間的脈沖噪聲引起，一次影響許多位，用突發(fā)長度表示突發(fā)錯影響的最大數(shù)據(jù)位數(shù)。,差錯編碼的類型,檢錯碼：只能檢測出傳輸錯誤，但無法自行糾正，通常與反饋重傳結(jié)合起來進行差錯恢復。,糾錯碼：能夠檢測出傳輸錯誤并糾正。,如何檢測與糾正錯誤？,碼字（,codeword,）：由,m,比特的數(shù)據(jù)（消息）加上,r,比特的冗余（校驗位）構(gòu)成。,有效編碼集

3、：由,2,m,個有效碼字組成。,檢錯：當收到的碼字為無效碼字時檢測出錯誤。,海明距離（,Hamming Distance,）：兩個碼字的對應位上取值不同的位數(shù)。,糾錯：將收到的無效碼字糾正到距其最近的有效碼字。,檢錯碼與糾錯碼的能力都是有限的。,編碼集的檢錯與糾錯能力,編碼集的海明距離：編碼集中任意兩個有效碼字的海明距離的最小值。,檢錯能力：為檢測出,d,比特錯誤，編碼集的海明距離至少應為,d+1,；,奇偶校驗是能夠檢測出,1,比特錯誤的檢錯碼。,糾錯能力：為糾正,d,比特錯誤，編碼集的海明距離至少應為,2d+1,。,結(jié)論：差錯編碼的檢錯,/,糾錯能力與編碼集的海明距離有關(guān)。海明距離越大，檢錯

4、糾錯能力就越強；但所需的冗余信息也越多，編碼效率就越低。,二維奇偶,校驗,對一個,kn,比特的信息矩陣的每一行和每一列計算奇偶校驗位。,循環(huán)冗余碼（,CRC,）,CRC,是一種多項式編碼，它將位串看成是某個一元多項式的系數(shù)，如,1011001,看成是一元多項式,X,6,+X,4,+X,3,+1,的系數(shù)。,信息多項式,M(x),：,由,m,個信息比特為系數(shù)構(gòu)成的多項式。,冗余多項式,R(x),：,由,r,個冗余比特為系數(shù)構(gòu)成的多項式。,碼多項式,T(x),：,在,m,個信息比特后加上,r,個冗余比特構(gòu)成的碼字所對應的多項式，表達式為,T(x)=,x,r,M(x,)+R(x),。,生成多項式,G(

5、x),：,雙方預先確定用來計算,R(x),的一個多項式。,編碼方法,：用對應于,G(x),的位串去除對應于,x,r,M(x,),的位串，所得的余式即為,R(x),，,將其,附加到信息比特串的后面一起發(fā)送。,校驗方法,：用,對應于,G(x),的位串去除對應于,T(x),的位串，若余式為,0,則認為傳輸正確，否則認為傳輸錯誤。,CRC,碼檢錯能力強，實現(xiàn)簡單快捷，是應用最廣泛的檢錯碼。,CRC,的編碼及校驗,例,1,：,G(X)=X,4,+X+1,，,對,10110011,進行,CRC,編碼。,例,2,：仍取,G(X)=X,4,+X+1,，判斷收到的位串,100101111001,是否有錯？,常見

6、的,CRC,多項式,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.,可靠交付,差錯恢復的兩種辦法：,使用糾錯碼，由接收端自動糾正錯誤。,使用檢錯碼，采用自動重傳

7、請求（,ARQ,）保證可靠交付。這是數(shù)據(jù)鏈路層（及傳輸層）上最常使用的可靠交付方式。,兩種,ARQ,算法：,停,-,等,滑動窗口,3.1,停,-,等算法,基本思想：發(fā)送方發(fā)完一幀后即停下來等待確認；如果收到一個確認，接著發(fā)送下一個幀；如果定時器超時，重發(fā)剛才的幀。,停,-,等算法的四種情形,。,停,-,等算法的超時值對性能影響很大，必須仔細選擇。,為區(qū)分新幀和重發(fā)幀，停,-,等算法使用一比特的幀序號。,停,-,等算法的四種情形,停,-,等算法的過,-,發(fā)送方,1,）幀序號初始化為,0,2,）從緩沖區(qū)中取出一個幀，加上當前幀序號發(fā)送。,3,）等待確認,i,）收到確認幀，且?guī)蛱柵c當前維護的幀序號

8、不同，將,幀序號加,1,，從緩沖區(qū)中取出一個新的幀，加上當前,幀序號發(fā)送。,ii,）收到確認幀，且?guī)蛱柵c當前維護的幀序號相同，重,發(fā)當前序號的幀。,iii,）收到錯誤的確認幀，重發(fā)當前序號的幀。,iv,）定時器超時，重發(fā)當前序號的幀。,停,-,等算法的過程,-,接收方,1,）幀序號初始化為,0,（表示當前期望接收的幀序號）,2,）等待接收,3,）幀到達,i,）,幀,校驗正確，且序號為當前期望接收的幀序號，將幀,放入接收緩沖區(qū)，幀序號加,1,，放入確認幀中發(fā)送。,ii,）幀校驗正確，但序號與當前期望接收的幀序號不同，,丟棄幀，重發(fā)確認幀。,iii,）幀校驗錯誤，丟棄幀，重發(fā)確認幀。,信道利用率

9、與流水線技術(shù),停,-,等算法在傳輸延遲較長的信道上傳輸效率很低。,假如將鏈路看成是一根管道，數(shù)據(jù)是管道中流動的水，那么停,-,等算法無法使數(shù)據(jù)充滿管道，因而信道利用率很低。,管道的容量通常用延遲,-,帶寬乘積表示，它表示發(fā)送端在收到第一個幀的確認前最多可以發(fā)送的數(shù)據(jù)量。,滑動窗口機制允許發(fā)送端連續(xù)發(fā)送多個幀來盡可能多地填充管道，從而提高信道的利用率。,3.2,滑動窗口,滑動窗口是計算機網(wǎng)絡中最著名的算法，它可以應用在數(shù)據(jù)鏈路層及傳輸層，用來完成三個不同的任務：,在不可靠的鏈路（網(wǎng)絡）上可靠地傳輸數(shù)據(jù),保持數(shù)據(jù)的傳輸順序,支持流量控制,在數(shù)據(jù)鏈路層上，以上三個功能組合在一個滑動窗口協(xié)議中。,發(fā)送

10、窗口,發(fā)送窗口：發(fā)送端允許發(fā)送的幀序號表。,發(fā)送窗口大小：發(fā)送端最大允許的未確認幀數(shù)目。,發(fā)送窗口下沿：最早發(fā)送但尚未被確認的幀序號。,發(fā)送窗口上沿：（發(fā)送窗口下沿發(fā)送窗口大小,1,）,mod 2,n,。,當收到對發(fā)送窗口下沿幀的確認時，發(fā)送窗口整體向前滑動一個序號，將已被確認的幀移出發(fā)送窗口，并加入一個新的序號。（,圖,）,發(fā)送窗口中的幀都保留在緩沖區(qū)中以備重傳，當某個幀被移出發(fā)送窗口時，同時從緩沖區(qū)中刪除。,當發(fā)送窗口滿時，停止從網(wǎng)絡層接收數(shù)據(jù)，直到有一個緩沖區(qū)空出來為止。,發(fā)送窗口和接收窗口圖示,接收,窗口,接收窗口：接收端允許接收的幀序號表。,接收窗口大?。航邮斩嗽试S接收的最大幀數(shù)。,

11、接收窗口下沿：接收端按順序期待接收的幀序號。,當接收端收到窗口下沿幀且校驗正確時，將幀交給網(wǎng)絡層，向發(fā)送方發(fā)回一個確認，然后窗口整體向前滑動一個序號。（,圖,）,接收窗口的大小可以設(shè)為任意值，通常的設(shè)置有兩種：,接收窗口大小,=1,：意味著接收方只能按順序接收；,接收窗口大小,=,發(fā)送窗口大?。阂馕吨邮辗娇梢圆话错樞蚪邮眨邮辗浇唤o上層實體的數(shù)據(jù)總是有序的。,捎帶確認,捎帶確認（,piggybacking,）：將確認序號攜帶在數(shù)據(jù)幀中傳輸，提高線路的效率。,推遲確認：當需要發(fā)送確認但沒有要發(fā)送的數(shù)據(jù)時，可以讓確認信息推遲一小段時間再發(fā)送；這一小段時間后若數(shù)據(jù)仍未準備好，接收端必須立即發(fā)送一

12、個單獨的確認幀。,接收端對正確收到的若干個幀同時進行確認，通常用對某一個幀的確認來表示對該幀之前的所有幀進行確認。,Go Back n,Go back n,當接收端收到一個出錯幀或亂序幀時，丟棄所有的后繼幀，并且不為這些幀發(fā)送確認；發(fā)送端超時后，重傳所有未被確認的幀。,該策略對應接收窗口為,1,的情況，即只能按順序接收幀。,若信道的誤碼率較高，這種方法會浪費很多帶寬，但對接收端內(nèi)存的需求不大。,Go Back N,示,意圖,選擇重傳,選擇重傳,當接收端收到一個出錯幀或亂序幀時，后續(xù)到達的幀只要校驗正確且落在接收窗口內(nèi)，都放入接收緩沖區(qū)中；發(fā)送端超時后只重傳最早發(fā)送但未被確認的幀。,該策略對應接

13、收窗口大于,1,的情況。,選擇重傳通常使用一個否定的確認（,NAK,）,對校驗出錯或疑為丟失的幀進行確認，以便發(fā)送端盡快重傳該幀。,當接收窗口很大時，這種方法要求接收端有較大的內(nèi)存，但它不浪費帶寬。,選擇重傳示意圖,有限序號與窗口限制,使用,Go Back N,協(xié)議，發(fā)送窗口的大小不能超過,2,n,-1,。,使用選擇重傳協(xié)議，若發(fā)送窗口與接收窗口大小相同，則發(fā)送窗口的大小不能超過,2,n-1,。,4.,數(shù)據(jù)鏈路協(xié)議舉例,高級數(shù)據(jù)鏈路控制（,HDLC,）,點到點協(xié)議（,PPP,）,4.1 HDLC,幀,結(jié)構(gòu),：,標志：,01111110,，標識一幀的開始與結(jié)束，以及作為幀間填充。,地址,：,在點

14、到多點線路中用于指明通信的終端地址，在點到點線路中用于區(qū)分命令和響應。,控制,：,用于構(gòu)成各種命令和響應，對鏈路進行監(jiān)控。,信息,：,可以是任意的二進制比特串。,校驗,：,CRC,碼，對兩個標志之間的幀內(nèi)容進行校驗。,幀,類型,信息幀：,以控制字段的第一比特為“,0”,標志。,用于傳送數(shù)據(jù)，數(shù)據(jù)放在信息字段中。,采用滑動窗口協(xié)議，,N(S),為發(fā)送序號，,N(R),為捎帶確認。,幀,類型（續(xù)）,監(jiān)視幀：,以控制字段的第一、二比特為“,10”,標志。,用于差錯控制和流量控制，沒有信息字段。,S,1,S,2,：,決定監(jiān)控幀的類型,類型,0,：接收準備好,類型,1,：否定確認,類型,2,：接收未準備

15、好,類型,3,：選擇拒絕,幀,類型（續(xù)）,無編號幀：,以控制字段的第一、二比特為“,11”,標志。,提供鏈路的建立、拆除及其它控制功能。,不包含,N(S),或,N(R),字段。,M,1,M,5,：,修正位，構(gòu)成各種鏈路命令和響應,HDLC,的訪問規(guī)程,鏈路層的,操作分為三個階段：,建立鏈路：一方發(fā)送一個置模式命令，另一方發(fā)送,UA,幀進行響應，并初始化鏈路變量。,傳輸信息：,雙方使用滑動窗口協(xié)議進行數(shù)據(jù)傳輸控制；,對收到的信息幀使用捎帶確認或監(jiān)視幀進行響應；,對檢測到錯誤的幀使用否定確認或選擇拒絕要求重發(fā)；,未準備好接收下一幀時，用接收未準備好暫停對方的發(fā)送。,斷開鏈路：一方發(fā)送一個斷連命令，另一方用一個,UA,幀進行響應。,4.2 PPP,協(xié)議,PPP,是因特網(wǎng)中廣泛使用的點到點數(shù)據(jù)鏈路協(xié)議。,PPP,由以下三部分組成：,一種在串行通信線路上的組幀方式；,用于建立、配置、測試和拆除數(shù)據(jù)鏈路的鏈路控制協(xié)議,LCP,；,一組網(wǎng)絡控制協(xié)議（,NCP,），,用以支持不同的網(wǎng)絡層協(xié)議。,PPP,的組幀,PPP,采用與,HDLC,類似的幀結(jié)構(gòu)，不同之處是：,PPP,采用字符填充而不是比特填充。,地址字段總是,oxFF,，控制字段總是,0 x03,。,增加的協(xié)議字段說明信息字段中攜帶的數(shù)據(jù)屬于哪個上層協(xié)議。,CRC,字段的長度可以協(xié)商。,PPP,鏈路的,配置、維護和終止,