計算機網(wǎng)絡(luò)第三章1

1、第三章數(shù)據(jù)鏈路層主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)據(jù)鏈路層協(xié)議實例 一、數(shù)據(jù)鏈路層的定義和功能1、定義數(shù)據(jù)鏈路層主要討論的是在相鄰兩個節(jié)點之間如何進行可靠且有效的通信的問題。局域網(wǎng)廣域網(wǎng)主機 H1主機 H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng) 點到點 端到端 端到端節(jié)點鏈路link（物理鏈路）：是一條無源的點到點的物理路段，中間沒有任何其他的交換節(jié)點。路徑path：從源端到目的端的一條通路，可能經(jīng)由許多中間節(jié)點。數(shù)據(jù)鏈路：物理鏈路傳輸兩端的硬件相關(guān)的通信協(xié)議路徑鏈路網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層一、數(shù)據(jù)鏈路層的定義和功能2、功能（設(shè)計要點）數(shù)

2、據(jù)鏈路層的主要功能包括以下三個方面：為網(wǎng)絡(luò)層提供一個良好定義的服務(wù)接口；處理傳輸錯誤（差錯控制）；調(diào)節(jié)數(shù)據(jù)流，確保慢速的接收方不會被快速的發(fā)送方淹沒（流量控制）。網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層分 組凈荷域頭尾3、數(shù)據(jù)鏈路層的服務(wù)數(shù)據(jù)鏈路層的功能之一是向網(wǎng)絡(luò)層提供服務(wù)。最主要的服務(wù)是將數(shù)據(jù)從源主機的網(wǎng)絡(luò)層傳輸?shù)侥康闹鳈C的網(wǎng)絡(luò)層。IP 數(shù)據(jù)報1010 0110幀取出數(shù)據(jù)鏈路層網(wǎng)絡(luò)層鏈路結(jié)點 A結(jié)點 B物理層IP 數(shù)據(jù)報1010 0110幀裝入數(shù)據(jù)鏈路層傳送的是幀數(shù)據(jù)鏈路層的傳輸過程 把從網(wǎng)絡(luò)層獲取到的分組封裝到幀中，加一定的校驗信息，然后交給物理層用某種信號表示二進制數(shù)據(jù)位傳送到目的節(jié)點； 在目的節(jié)點，再

3、通過目的節(jié)點的物理層和數(shù)據(jù)鏈路層上傳到網(wǎng)絡(luò)層。數(shù)據(jù)鏈路層的作用 為網(wǎng)絡(luò)層提供一條可靠的數(shù)據(jù)鏈路。局域網(wǎng)廣域網(wǎng)主機 H1主機 H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機 H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層傳輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層傳輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從網(wǎng)絡(luò)層次上來看數(shù)據(jù)的流動局域網(wǎng)廣域網(wǎng)主機 H1主機 H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機 H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R

4、3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動虛擬數(shù)據(jù)通路實際數(shù)據(jù)通路數(shù)據(jù)鏈路層可以提供多種不同的服務(wù)，但一般情況下，通常會提供以下三種服務(wù)： 無確認的無連接服務(wù)源節(jié)點向目的節(jié)點發(fā)送獨立的幀，傳輸前不需要建立邏輯連接，傳輸后也不要求目的節(jié)點進行確認，即不保證幀的正確傳輸。這類服務(wù)適用于誤碼率非常低的傳輸環(huán)境及一些實時業(yè)務(wù)，如以太網(wǎng)有確認的無連接服務(wù)傳輸前不需要建立邏輯連接，但目的節(jié)點對于收到的每個幀都必須進行確認，它保證每個幀都能被正確接收。這類服務(wù)適用于誤碼率較高的傳輸環(huán)境，如無線系統(tǒng)。有確認的面向連接的服務(wù)傳輸前需要建立邏輯連接，每個幀被編上序號按序發(fā)送，目的節(jié)點對收到的幀進行檢錯、確認與排序，它保

5、證向網(wǎng)絡(luò)層遞交正確有序的數(shù)據(jù)流。數(shù)據(jù)鏈路層使用的信道主要有以下兩種類型：點對點信道。這種信道使用一對一的點對點通信方式。廣播信道。這種信道使用一對多的廣播通信方式，因此過程比較復(fù)雜。廣播信道上連接的主機很多，因此必須使用專用的共享信道協(xié)議來協(xié)調(diào)這些主機的數(shù)據(jù)發(fā)送。介質(zhì)訪問控制子層（MAC）：它是數(shù)據(jù)鏈路層上特有的一個子層，用于解決共享信道的分配問題 主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)據(jù)鏈路層協(xié)議實例 二、數(shù)據(jù)的可靠傳輸數(shù)據(jù)鏈路層的主要目的：保證相鄰兩個節(jié)點的可靠性傳輸。將傳輸?shù)男畔⒔M合成幀差錯控制 流量控制將傳輸?shù)男畔⒔M合成幀成幀封裝成幀(fra

6、ming)就是在一段數(shù)據(jù)的前后分別添加首部和尾部，然后就構(gòu)成了一個幀。確定幀的界限-首部和尾部的重要作用之一就是進行幀定界。 幀結(jié)束幀首部IP 數(shù)據(jù)報幀的數(shù)據(jù)部分幀尾部 MTU數(shù)據(jù)鏈路層的幀長開始發(fā)送幀開始成幀 (framing) 字符計數(shù)法帶字節(jié)填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 字符計數(shù)法：每一個幀的第一個字段攜帶幀的長度信息。 5123456789801234568第一幀第二幀第三幀缺點：幀頭出錯不光影響本數(shù)據(jù)幀，還影響后續(xù)的幀。a 無差錯512347678980123456第一幀第二幀第三幀b 有一個差錯成幀 (framing) 字符計數(shù)法帶字節(jié)

7、填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 帶字節(jié)填充的分界符法 分界符法：使用特殊的字節(jié)（標(biāo)志字節(jié)flagbyte）來表示幀的開始與結(jié)束，當(dāng)失去同步后，只需要搜索特定的標(biāo)志字節(jié)就可以了。-具有再同步能力當(dāng)標(biāo)志字節(jié)的位模式FLAG出現(xiàn)在數(shù)據(jù)中怎么辦？成幀 (framing) 帶字節(jié)填充的分界符法：為避免在幀的其它部分出現(xiàn)與標(biāo)志字節(jié)相同的位模式，采用了字節(jié)填充的方法，即在與標(biāo)志字節(jié)相同的字符前插入轉(zhuǎn)義字符ESC，如圖。（PPP協(xié)議） 成幀 (framing) 帶字節(jié)填充的分界符法 缺點：依賴于特定的字符編碼集（如ASCII字符中，F(xiàn)LAG用7E H表示，ESC用1

8、B H表示，只能是8位字符模式），靈活性差（實際中，并不是所有字符碼都采用8位字符表示，UNICODE使用的是16位字符）成幀 (framing) 字符計數(shù)法帶字節(jié)填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 帶位填充的分界標(biāo)志法： 使用一個特殊的比特模式（如：01111110）作為幀的起始與結(jié)束標(biāo)志（Flag）。 -具有再同步能力當(dāng)標(biāo)志符的位模式FLAG出現(xiàn)在數(shù)據(jù)中怎么辦？成幀 (framing) 為避免在幀的其它部分出現(xiàn)與此標(biāo)志相同的比特模式，采用了比特填充的方法，即在5個連續(xù)的1后插入一個0，如圖。（HDLC協(xié)議） 原始數(shù)據(jù)傳輸線路上的數(shù)據(jù)刪除填充位之后接收

9、存儲的數(shù)據(jù)成幀 (framing) 字符計數(shù)法帶字節(jié)填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 物理層編碼違例法：這種方法只適用于那些在物理層編碼中使用冗余技術(shù)的網(wǎng)絡(luò)。例如：以太網(wǎng)的物理層采用曼徹斯特編碼，它將比特“1”表示成高-低電平對，將比特“0”表示成低-高電平對，而高-高電平對和低-低電平對在編碼中沒有使用，這樣可以用這兩種無效的編碼標(biāo)識幀的邊界。注意：在很多數(shù)據(jù)鏈路協(xié)議中，使用字符計數(shù)法和一種其它方法的組合。二、數(shù)據(jù)的可靠傳輸數(shù)據(jù)鏈路層的主要目的：保證相鄰兩個節(jié)點的可靠性傳輸。將傳輸?shù)男畔⒔M合成幀差錯控制 流量控制差錯控制傳輸過程出錯情況：幀（包括發(fā)送

10、幀和響應(yīng)幀）出錯；校驗和確認幀（包括發(fā)送幀和響應(yīng)幀）丟失；超時和重發(fā)幀（包括發(fā)送幀和響應(yīng)幀）重復(fù)；加序號 幀出錯信號在任何信道上傳輸都存在著傳輸差錯，這些差錯由多種物理現(xiàn)象引起，解決差錯問題的方法有兩種：一種是在要發(fā)送的數(shù)據(jù)中加入一定的冗余位，使接收方能知道數(shù)據(jù)是否出錯，但不知道是哪里出錯，這種編碼方法叫差錯檢測碼，或簡稱檢錯碼。另一種是在要發(fā)送的數(shù)據(jù)中加入足夠多的冗余位，使接收方能糾正出錯的位，這種編碼方法叫差錯校正碼，或簡稱糾錯碼。使用糾錯碼傳數(shù)據(jù)，效率低，適用于不可能重傳的場合；大多數(shù)情況采用檢錯碼加重傳。檢錯碼奇偶校驗碼多項式編碼，又叫循環(huán)冗余校驗碼CRC（Cyclic Redunda

11、ncy Check）奇偶校驗碼在每個字符的數(shù)據(jù)位傳輸之前，先檢測并計算奇偶校驗位，然后附加在其后；接收機重新計算收到字符的奇偶校驗位，確定該字符是否出現(xiàn)傳輸差錯；注：只能發(fā)現(xiàn)奇數(shù)個錯誤，如果有偶數(shù)比特出錯，奇偶校驗位無效；檢錯碼奇偶校驗碼多項式編碼，又叫循環(huán)冗余校驗碼CRC（Cyclic Redundancy Check）多項式編碼（循環(huán)冗余校驗碼CRC）基本原理：它先將要發(fā)送的信息數(shù)據(jù)與一個通信雙方共同約定的數(shù)據(jù)進行除法運算，并根據(jù)余數(shù)得出一個校驗碼，然后將這個校驗碼附加在信息數(shù)據(jù)幀之后發(fā)送出去。 接收端接收數(shù)據(jù)后，將包括校驗碼在內(nèi)的數(shù)據(jù)幀再與約定的數(shù)據(jù)進行除法運算，若余數(shù)為“0”，就表示接

12、收的數(shù)據(jù)正確，若余數(shù)不為“0”，則表明數(shù)據(jù)在傳輸?shù)倪^程中出錯。 定義：它將位串看成是某個一元多項式的系數(shù)。如果一個m位的幀，可以看作是一個m1次多項式的系數(shù)列表，該多項式用M(x)表示,共有m項，從Xm1到X0。 如1011001看成是一元多項式X6 + X4 + X3 + 1的系數(shù)；生成多項式G(x)：雙方預(yù)先確定的一個多項式,共有r項；冗余多項式R(x)： xrM(x)/G(X)的余數(shù)；碼多項式T(x)：T(x) 等于 xrM(x) 減去 余數(shù)R(x)；具體實現(xiàn)步驟：1、若G(x)為r階。原始數(shù)據(jù)為m位，其多項式為M(x)，則在原始數(shù)據(jù)后面添加r個0，實際傳輸數(shù)據(jù)為m+r位，相應(yīng)多項式為x

13、rM(x)。2、按模2除法用對應(yīng)于G(x)的位串去除對應(yīng)于xrM(x)的位串。3、按模2減法從對應(yīng)于xrM(x)的位串中減去余數(shù)（等于或小于r位），結(jié)果就是要傳送的帶校驗和的多項式T(x)。檢錯方法：用對應(yīng)于G(x)的位串去除對應(yīng)于T(x)的位串，若余式為0則認為傳輸正確，否則認為傳輸錯誤例1 取G（X）X4+X+1，假設(shè)欲發(fā)送的一段信息101100110，問在線路上傳輸?shù)拇a字是？ 10101100010011 1011001100000 10011 10101 10011 11010 10011 10010 10011 1000解：由G（X）X4+X+1得 生成的碼字為：10011，r為4

14、原始信息101100110對應(yīng)的多項式 M(x)=X8+X6+X5+X2+X, XrM(x)=X4 (X8+X6+X5+X2+X)= X12+X10+X9+X6+X5,則XrM(x)對應(yīng)的碼字為：1011001100000 用對應(yīng)的G（X）的碼字去除對應(yīng)的XrM(x)的位串得余數(shù)為1000.把XrM(x)位串與余數(shù)相加就是實際要傳送的碼字，為： 1011001101000例2.已知：接收碼字:1100111001多項式: T(X)=X9+X8+X5+X4+X3+1 生成多項式:G(X)=X4+X3+1(r=4)求：碼字的正確性。若正確，則指出冗余碼和信息碼。解： 1）用接收碼字除以生成碼，余數(shù)

15、為0，所以碼字正確。 2)因r=4，所以冗余碼是：1001，信息碼是:110011 生成多項式G(x)的選擇四個多項式已成為國際標(biāo)準(zhǔn)CRC-12 = x12 + x11 + x3 + x2 + x + 1CRC-16 = x16 + x15 + x2 + 1CRC-CCITT = x16 + x12 + x5 + 1CRC-32= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1應(yīng)當(dāng)注意 僅用循環(huán)冗余檢驗 CRC 差錯檢測技術(shù)只能做到無差錯接受(accept)。 “無差錯接受”是指：凡是

16、接受的幀（即不包括丟棄的幀），我們都能以非常接近于 1 的概率認為這些幀在傳輸過程中沒有產(chǎn)生差錯。 也就是說：“凡是接收端數(shù)據(jù)鏈路層接受的幀都沒有傳輸差錯”（有差錯的幀就丟棄而不接受）。要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認和重傳機制。 什么樣的錯誤可以被檢測到？ 在接收方收到帶校驗和的幀后，用G(x)來除它。如果E（x）表示一個錯誤多項式，則在接收方要計算: T（x） E（x）/ G（x）因為T（x）/ G（x）=0，所以就是要計算E（x）/ G（x）的值。如果錯誤多項式E（x）恰好包含G（x）作為它的一個因子，則這樣的錯誤將無法檢測出來；否則其他錯誤都可以檢測得到。 差

17、錯控制傳輸過程出錯情況：幀（包括發(fā)送幀和響應(yīng)幀）出錯；校驗和確認幀（包括發(fā)送幀和響應(yīng)幀）丟失；超時和重發(fā)幀（包括發(fā)送幀和響應(yīng)幀）重復(fù)；加序號 ACK（ Acknowledgement ）NAK（Negative Acknowledgement）幀丟失通過發(fā)送方的計時器解決超時、重傳超時（TimeOut）：發(fā)送方一旦發(fā)送一個幀，就啟動一個計時器，如果在規(guī)定的時間內(nèi)，收不到回應(yīng)，則在計時器溢出時，在重發(fā)此幀。注： 超時時間的設(shè)置 差錯控制傳輸過程出錯情況：幀（包括發(fā)送幀和響應(yīng)幀）出錯；校驗和確認幀（包括發(fā)送幀和響應(yīng)幀）丟失；超時和重發(fā)幀（包括發(fā)送幀和響應(yīng)幀）重復(fù)；加序號 幀重復(fù)如果接收方發(fā)送的確認

18、幀丟失，導(dǎo)致發(fā)送方多次發(fā)送同一幀，接收方多次收到同一幀，造成了幀重復(fù)；要區(qū)別是否是同一幀，在每一幀中加入一個幀的編號二、數(shù)據(jù)的可靠傳輸數(shù)據(jù)鏈路層的主要目的：保證相鄰兩個節(jié)點的可靠性傳輸。將傳輸?shù)男畔⒔M合成幀差錯控制（校驗、重傳）流量控制流量控制當(dāng)發(fā)送端的發(fā)送速度大于接收端的接收速度，或發(fā)送端所在的網(wǎng)絡(luò)傳輸速率大于接收端所在的網(wǎng)絡(luò)傳輸速率時，就需要流量控制。常見的方法有兩種： 基于反饋的流控制窗口機制 基于速率的流控制幀的數(shù)據(jù)結(jié)構(gòu)（一般意義上）：確認號ack幀的數(shù)據(jù)部分（分組）info幀序號seq幀類型kind幀頭主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)

19、據(jù)鏈路層協(xié)議實例 三、基本的數(shù)據(jù)鏈路層協(xié)議通信模型的基本假設(shè)：1、假設(shè)一臺主機上，物理層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層都是獨立的進程；2、A、B兩臺主機要求可靠的、面向連接的服務(wù)。3、在接收方的數(shù)據(jù)鏈路層，正在運行wait_for_event(&event),即等待某個事件發(fā)生數(shù)據(jù)鏈路層主機 A緩存主機 B數(shù)據(jù)鏈路AP2AP1緩存發(fā)送方接收方幀高層幀 數(shù)據(jù)鏈路層通過過程調(diào)用wait_for_event(&event),來等待事情的發(fā)生。 當(dāng)一個數(shù)據(jù)幀到達接收方時（可看作有一個事件發(fā)生 event），硬件會計算校驗和。 如果校驗和不正確，令eventchecksum_err； 如果校驗和正確，令event

20、frame_arrival幀的數(shù)據(jù)結(jié)構(gòu)（一般意義上）：確認號ack幀的數(shù)據(jù)部分（分組）info幀序號seq幀類型kind幀頭基本的數(shù)據(jù)鏈路層協(xié)議協(xié)議1：一種無限制的單工協(xié)議協(xié)議2：一種單工的停-等協(xié)議協(xié)議3：有噪音信道的單工協(xié)議協(xié)議1：一種無限制的單工協(xié)議理想環(huán)境下的理想的協(xié)議，假定1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。不需要校驗、確認，不要重傳假定2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時上交主機。接收端處理速度無限高，緩沖區(qū)無限大，不需要流控發(fā)送端：接收端：基本的數(shù)據(jù)鏈路層協(xié)議協(xié)議1：一種無限制的單工協(xié)議協(xié)議2：一種單工的停-等協(xié)議協(xié)議3：

21、有噪音信道的單工協(xié)議協(xié)議2：一個單工的停等協(xié)議增加約束條件：接收方不可能具有足夠高的CPU處理能力來及時處理所有的接收幀，也不可能具有足夠大的緩沖區(qū)。協(xié)議2：一個單工的停等協(xié)議 假定1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。不需要校驗，不要重傳假定2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時上交主機。接收端處理速度無限高，緩沖區(qū)無限大，不需要流控 解決方法：發(fā)送方每發(fā)出一個幀后，等待接收方發(fā)回的一個確認，接到確認后，再繼續(xù)發(fā)送停等協(xié)議發(fā)送端：接收端：基本的數(shù)據(jù)鏈路層協(xié)議協(xié)議1：一種無限制的單工協(xié)議協(xié)議2：一種單工的停-等協(xié)議協(xié)議3：有噪音信道的單工協(xié)

22、議協(xié)議3：有噪音信道的單工協(xié)議理想環(huán)境下的理想的協(xié)議，假定1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。不需要校驗，不要重傳假定2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時上交主機。接收端處理速度無限高，緩沖區(qū)無限大，不需要流控數(shù)據(jù)幀可能被損壞，也可能丟失 需要校驗和重傳需要流控 時間ABDATA0送主機ACKDATA1送主機ACK(a) 正常情況ABDATA0DATA0送主機ACK(c) 數(shù)據(jù)幀丟失重傳tout丟失 ！ABDATA0送主機ACKDATA0丟棄ACK(d) 確認幀丟失（數(shù)據(jù)幀重復(fù)）重傳tout丟失 ！噪聲信道傳輸過程中出錯的三種情況協(xié)議3

23、的要點發(fā)送方要記錄下一個準(zhǔn)備發(fā)送的順序號接收方要記錄下一個期望接收的順序號發(fā)送過程和接收過程是嚴(yán)格交替的PAR（Positive Acknowledgement with Retransmission）支持重傳的肯定確認協(xié)議 或者ARQ（Automatic Repeat reQuest）自動重復(fù)請求協(xié)議 在協(xié)議3中，發(fā)送方應(yīng)重發(fā)當(dāng)前幀還是發(fā)下一幀，可以根據(jù)超時和是否收到確認來判定，即它僅僅與前一幀和后一幀有關(guān)，所以，在協(xié)議中，只需要一位（0或1）就可以表示順序號發(fā)送端：等待應(yīng)答接收端：注意協(xié)議3重發(fā)機制的缺陷效率較低： 如接收方收到的幀出錯或者整個數(shù)據(jù)幀丟失，則不發(fā)送確認幀，發(fā)送方在超時后重發(fā)

24、，直至正確（效率低）； 前面的協(xié)議都假定數(shù)據(jù)幀沿著一個方向傳輸，但事實上大多數(shù)的通信都是雙向的。 雙向傳輸解決方案兩條線路（四根信道）： 兩根數(shù)據(jù) 兩根應(yīng)答 信道利用率低一條線路（兩根信道）：一根A到B，一根B到A問題是如何區(qū)分數(shù)據(jù)和應(yīng)答？用不同的幀類型用捎帶（piggybacking）確認滑動窗口協(xié)議收發(fā)使用兩條信道 發(fā)送方可以連續(xù)發(fā)送多幀，接收方接受到一組幀后就從另一個信道發(fā)一個確認，為提高信道使用效率，可使用捎帶確認；幀是有序號的 在滑動窗口協(xié)議中，每一個要發(fā)送的幀都包含一個序號，范圍是從0到某個最大值，最大值通常是2n-1，n為幀序號的長度。 即使過早的超時而導(dǎo)致的重發(fā)，也可以根據(jù)幀的

25、序號來避免幀的重復(fù)滑動窗口協(xié)議的要點： 任何時刻發(fā)送進程都要維護一組幀序號，對應(yīng)于一組已經(jīng)發(fā)送但尚未被確認的幀，這些幀稱為落在發(fā)送窗口內(nèi)； 類似地，接收進程也要維護一組幀序號，對應(yīng)于一組允許接收的幀，這些幀稱為落在接收窗口內(nèi)。發(fā)送窗口發(fā)送窗口中的序號代表已發(fā)送但尚未確認的幀，其中窗口下沿代表最早發(fā)送但至今尚未確認的幀。當(dāng)發(fā)送窗口尚未達到最大值時，可以從網(wǎng)絡(luò)層接收一個新的分組，然后將窗口上沿加1，并將新的上沿序號分配給新的幀；當(dāng)收到對窗口下沿幀的確認時，窗口下沿加1。由于每一個幀都有可能傳輸出錯，所以發(fā)送窗口中的幀都必須保留在緩沖區(qū)里以備重傳，直至收到確認為止。當(dāng)發(fā)送窗口達到最大值時，停止從網(wǎng)絡(luò)

26、層接收數(shù)據(jù)，直到有一個緩沖區(qū)空出來為止。 接收窗口接收窗口中的序號代表允許接收的幀，任何落在窗口外的幀都被丟棄，落在窗口內(nèi)的幀存放到緩沖區(qū)里。當(dāng)收到窗口下沿幀時，將其交給網(wǎng)絡(luò)層，并產(chǎn)生一個確認，然后窗口整體向前移動一個位置。和發(fā)送窗口不同，接收窗口的大小是不變的，總是保持初始時的大小。接收窗口大小為1，意味著數(shù)據(jù)鏈路層只能順序接收數(shù)據(jù)，當(dāng)接收窗口大于1時不是這樣，但無論如何，數(shù)據(jù)鏈路層必須按順序?qū)?shù)據(jù)遞交給網(wǎng)絡(luò)層。 發(fā)送窗口和接收窗口圖示要發(fā)送的下一個幀的序號未得到確認的幀的最小編號允許接收的序號最大的幀希望接收的幀三個窗口協(xié)議（協(xié)議46）1位滑動窗口協(xié)議回退n幀的滑動窗口協(xié)議選擇性重傳的滑動

27、窗口協(xié)議1位滑動窗口協(xié)議(協(xié)議4) 發(fā)送窗口 WT1，接收窗口WR1該協(xié)議使用停-等方式，所以只需要1比特長的幀序號。幀頭中至少包括seq和ack兩個域，ack用于對正確收到的幀的序號進行確認。由于支持雙向傳輸，所以每個協(xié)議實體需要同時完成發(fā)送和接收兩個功能。 1位滑動窗口協(xié)議(協(xié)議4)接收方發(fā)送方比較兩種情況正常情況：發(fā)送方和接收方交替發(fā)送異常情況：當(dāng)發(fā)送方和接收方同時向?qū)Ψ桨l(fā)送，會造成不必要的重發(fā)，但協(xié)議也能夠正常運行1位滑動窗口協(xié)議(協(xié)議4)的缺點信道利用率低協(xié)議4：發(fā)送端的等待時間至少是發(fā)送端到接收端信號傳播時間的兩倍例：衛(wèi)星信道傳輸速率50kbps，往返傳輸延遲500ms，若傳100

28、0bit的幀，使用協(xié)議4，則傳輸一個幀所需時間為： 發(fā)送時間 + 信息信道延遲 + 確認信道延遲（確認幀很短，忽略發(fā)送時間）= 1000bit / 50kbps + 250ms + 250ms = 520ms 所以 ，信道利用率 = 20 / 520 4%如果我們在等待確認的時候多發(fā)送一些幀（連續(xù)發(fā)送多幀后再等待確認），就可以提高線路的效率。事實上就是允許發(fā)送窗口包含多個未被確認的幀，這種技術(shù)稱為管道化（pipelining）。當(dāng)信號傳播延遲遠大于幀的傳輸時間時，適合采用這個技術(shù)。 比如，如果位于幀流中的某個幀丟失或損壞了，會發(fā)生什么情況在發(fā)送進程發(fā)現(xiàn)出錯前，大量的后繼幀會到達接收方；當(dāng)一個壞

29、幀到達接收方時，顯然會被接收方丟棄，那么后面到來的幀如何處理？ 當(dāng)管道化技術(shù)建立在不可靠的信道上時會有一些問題有兩種基本的方法來處理以上問題：一種方法稱為 go back n（回退n幀） 接收進程從出錯幀起丟棄所有的后繼幀，并且不通知發(fā)送進程。該策略對應(yīng)接收窗口為1的情況，即只能按順序接收幀，當(dāng)發(fā)送進程超時后，必須按順序重傳所有未被確認的幀，如圖3-16(a)。 有一個差錯時，回退n幀 （WT7 WR1）三個窗口協(xié)議（協(xié)議46）1位滑動窗口協(xié)議 發(fā)送窗口WT1，接收窗口WR1回退n幀的滑動窗口協(xié)議 發(fā)送窗口WT1，接收窗口WR1選擇性重傳的滑動窗口協(xié)議回退n幀的滑動窗口協(xié)議程序（協(xié)議5）接收方

30、發(fā)送方回退n幀的滑動窗口協(xié)議，如果編號由n 位組成，則 發(fā)送窗口WT2n1 接收窗口WR1缺陷：沒有考慮到當(dāng)某個方向上沒有數(shù)據(jù)要發(fā)送時，要對收到的幀進行單獨確認。在收到期待的幀后應(yīng)該啟動一個ACK超時計時器，當(dāng)發(fā)生超時事件時，判斷哪個計時器超時，若是ACK計時器超時，應(yīng)該單獨發(fā)送一個確認幀。而當(dāng)發(fā)送了一個數(shù)據(jù)包時，應(yīng)將被捎帶確認的幀的ACK計時器終止。一旦數(shù)據(jù)幀丟失，在發(fā)送端意識到丟失（TimeOut）時，已經(jīng)有大量的數(shù)據(jù)幀到達接收端，被丟棄。這樣如果錯誤率高的話，這種方法會浪費很多帶寬，但對內(nèi)存需求不大。 圖三個窗口協(xié)議（協(xié)議46）1位滑動窗口協(xié)議回退n幀的滑動窗口協(xié)議選擇性重傳的滑動窗口協(xié)

31、議另一種方法稱為選擇重傳（對應(yīng)接收窗口大于1的情況）只要是落入接收窗口且校驗正確的幀，都要接收下來放到緩沖區(qū)里，這樣當(dāng)發(fā)送進程意識到某個幀出錯時，只是重傳此幀而不是所有的后繼幀，如圖3-16(b)。選擇重傳通常使用NAK對校驗出錯或疑為丟失的幀進行確認，以便發(fā)送進程盡快重傳該幀。如果第二次重傳成功，接收方的數(shù)據(jù)鏈路層中會有許多按順序排列的正確幀，這些幀可以一起交給網(wǎng)絡(luò)層，并只對最高序號的幀進行確認。當(dāng)窗口很大時，這種方法需要大量的數(shù)據(jù)鏈路層內(nèi)存，但它不浪費帶寬。 主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)據(jù)鏈路層協(xié)議實例 數(shù)據(jù)鏈路協(xié)議舉例高級數(shù)據(jù)鏈路控制 HDLC -High-Level Data Link Control因特網(wǎng)中的數(shù)據(jù)鏈路層 PPP-Point-to-Point Protocol高級數(shù)據(jù)鏈路控制HDLC最早在IBM大型機領(lǐng)域中使