1、計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)第第 3 章章 點(diǎn)對點(diǎn)信道的數(shù)據(jù)鏈路層點(diǎn)對點(diǎn)信道的數(shù)據(jù)鏈路層課程要求課程要求n1.理解數(shù)據(jù)鏈路層的基本原理理解數(shù)據(jù)鏈路層的基本原理n2.掌握錯誤檢測和糾正的方法掌握錯誤檢測和糾正的方法n3.掌握停止等待工作原理掌握停止等待工作原理n4.掌握掌握ARQ協(xié)議工作原理協(xié)議工作原理n5.理解理解HDLC協(xié)議和協(xié)議和PPP協(xié)議協(xié)議第第 3 章章 數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層*3.1 數(shù)據(jù)鏈路層的基本概念數(shù)據(jù)鏈路層的基本概念*3.2 停止等待協(xié)議停止等待協(xié)議3.2.1 完全理想化的數(shù)據(jù)傳輸完全理想化的數(shù)據(jù)傳輸3.2.2 具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議3.2

2、.3 實(shí)用的停止等待協(xié)議實(shí)用的停止等待協(xié)議3.2.4 循環(huán)冗余檢驗(yàn)的原理循環(huán)冗余檢驗(yàn)的原理3.2.5 停止等待協(xié)議的算法停止等待協(xié)議的算法3.2.6 停止等待協(xié)議的定量分析停止等待協(xié)議的定量分析第第 3 章章 數(shù)據(jù)鏈路層（續(xù)）數(shù)據(jù)鏈路層（續(xù)）*3.3 連續(xù)連續(xù) ARQ 協(xié)議協(xié)議3.3.1 連續(xù)連續(xù) ARQ 協(xié)議的工作原理協(xié)議的工作原理3.3.2 連續(xù)連續(xù) ARQ 協(xié)議的吞吐量協(xié)議的吞吐量3.3.3 滑動窗口的概念滑動窗口的概念3.3.4 信道利用率與最佳幀長信道利用率與最佳幀長3.4 選擇重傳選擇重傳 ARQ 協(xié)議協(xié)議第第 3 章章 數(shù)據(jù)鏈路層（續(xù)）數(shù)據(jù)鏈路層（續(xù)）*3.5 面向比特的鏈路層協(xié)

3、議面向比特的鏈路層協(xié)議 HDLC3.5.1 HDLC 協(xié)議概述協(xié)議概述3.5.2 HDLC 的幀結(jié)構(gòu)的幀結(jié)構(gòu)*3.6 因特網(wǎng)的點(diǎn)對點(diǎn)協(xié)議因特網(wǎng)的點(diǎn)對點(diǎn)協(xié)議 PPP 3.6.1 PPP 協(xié)議的工作原理協(xié)議的工作原理 3.6.2 PPP 協(xié)議的幀格式協(xié)議的幀格式 3.6.3 PPP 協(xié)議的工作狀態(tài)協(xié)議的工作狀態(tài)3.1 數(shù)據(jù)鏈路層的基本概念數(shù)據(jù)鏈路層的基本概念 n鏈路鏈路(link)是一條無源的點(diǎn)到點(diǎn)的物理線是一條無源的點(diǎn)到點(diǎn)的物理線路段，中間沒有任何其他的交換結(jié)點(diǎn)。路段，中間沒有任何其他的交換結(jié)點(diǎn)。n一條鏈路只是一條通路的一個組成部分。一條鏈路只是一條通路的一個組成部分。n數(shù)據(jù)鏈路數(shù)據(jù)鏈路(dat

4、a link) 除了物理線路外，還必除了物理線路外，還必須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實(shí)須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實(shí)現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路。了數(shù)據(jù)鏈路。n現(xiàn)在最常用的方法是使用適配器（即網(wǎng)卡）來實(shí)現(xiàn)現(xiàn)在最常用的方法是使用適配器（即網(wǎng)卡）來實(shí)現(xiàn)這些協(xié)議的硬件和軟件。這些協(xié)議的硬件和軟件。n一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層的功能。的功能。 數(shù)據(jù)鏈路層像個數(shù)字管道數(shù)據(jù)鏈路層像個數(shù)字管道 n常常在兩個對等的數(shù)據(jù)鏈路層之間畫出常常在兩個對等的數(shù)據(jù)鏈路層之間畫出一

5、個數(shù)字管道，而在這條數(shù)字管道上傳一個數(shù)字管道，而在這條數(shù)字管道上傳輸?shù)臄?shù)據(jù)單位是輸?shù)臄?shù)據(jù)單位是幀幀。n早期的數(shù)據(jù)通信協(xié)議曾叫作早期的數(shù)據(jù)通信協(xié)議曾叫作通信規(guī)程通信規(guī)程(procedure)。因此在數(shù)據(jù)鏈路層，規(guī)程。因此在數(shù)據(jù)鏈路層，規(guī)程和協(xié)議是同義語。和協(xié)議是同義語。 結(jié)點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)幀幀幀幀數(shù)據(jù)鏈路層的主要功能數(shù)據(jù)鏈路層的主要功能(1) 鏈路管理鏈路管理(2) 幀定界幀定界 (3) 流量控制流量控制(4) 差錯控制差錯控制 (5) 將數(shù)據(jù)和控制信息區(qū)分開將數(shù)據(jù)和控制信息區(qū)分開 (6) 透明傳輸透明傳輸 (7) 尋址尋址 數(shù)據(jù)鏈路層的主要功能（續(xù)）數(shù)據(jù)鏈路層的主要功能（續(xù)）(1)鏈路管理鏈路管

6、理 當(dāng)網(wǎng)絡(luò)中的兩個結(jié)點(diǎn)要進(jìn)行通信時，通信當(dāng)網(wǎng)絡(luò)中的兩個結(jié)點(diǎn)要進(jìn)行通信時，通信的雙方必須先要交換一些必要的信息，必的雙方必須先要交換一些必要的信息，必須先建立一條數(shù)據(jù)鏈路。同樣地，在傳輸須先建立一條數(shù)據(jù)鏈路。同樣地，在傳輸數(shù)據(jù)時要維持?jǐn)?shù)據(jù)鏈路，而在通信完畢時數(shù)據(jù)時要維持?jǐn)?shù)據(jù)鏈路，而在通信完畢時要釋放數(shù)據(jù)鏈路。要釋放數(shù)據(jù)鏈路。 數(shù)據(jù)鏈路的數(shù)據(jù)鏈路的建立、維持和釋放建立、維持和釋放就叫做鏈路就叫做鏈路管理。管理。 數(shù)據(jù)鏈路層的主要功能（續(xù)）數(shù)據(jù)鏈路層的主要功能（續(xù)）(2) 幀定界幀定界 n 在數(shù)據(jù)鏈路層，數(shù)據(jù)的傳送單位是在數(shù)據(jù)鏈路層，數(shù)據(jù)的傳送單位是幀幀。數(shù)據(jù)一幀一幀地傳送，就可以在出現(xiàn)差數(shù)據(jù)一幀一

7、幀地傳送，就可以在出現(xiàn)差錯時，將有差錯的幀再重傳一次，而避錯時，將有差錯的幀再重傳一次，而避免了將全部數(shù)據(jù)都進(jìn)行重傳。免了將全部數(shù)據(jù)都進(jìn)行重傳。n幀定界幀定界是指收方應(yīng)當(dāng)能從收到的比特流是指收方應(yīng)當(dāng)能從收到的比特流中準(zhǔn)確地區(qū)分出一幀的開始和結(jié)束在什中準(zhǔn)確地區(qū)分出一幀的開始和結(jié)束在什么地方。幀定界也可稱為么地方。幀定界也可稱為幀同步幀同步。 數(shù)據(jù)鏈路層的主要功能（續(xù)）數(shù)據(jù)鏈路層的主要功能（續(xù)）(3) 流量控制流量控制n發(fā)方發(fā)送數(shù)據(jù)的速率必須使收方來得及發(fā)方發(fā)送數(shù)據(jù)的速率必須使收方來得及接收。當(dāng)收方來不及接收時就必須及時接收。當(dāng)收方來不及接收時就必須及時控制發(fā)方發(fā)送數(shù)據(jù)的速率。這種功能稱控制發(fā)方發(fā)

8、送數(shù)據(jù)的速率。這種功能稱作流量控制作流量控制(flow control)。 數(shù)據(jù)鏈路層的主要功能（續(xù)）數(shù)據(jù)鏈路層的主要功能（續(xù)）(4) 差錯控制差錯控制n 在計(jì)算機(jī)通信中，一般都要求有極低的比特差錯率。在計(jì)算機(jī)通信中，一般都要求有極低的比特差錯率。廣泛地采用了編碼技術(shù)。編碼技術(shù)有兩大類廣泛地采用了編碼技術(shù)。編碼技術(shù)有兩大類:n前向糾錯：前向糾錯：即收方收到有差錯的數(shù)據(jù)幀時，能夠自動即收方收到有差錯的數(shù)據(jù)幀時，能夠自動將差錯改正過來。這種方法的開銷較大，不大適合于將差錯改正過來。這種方法的開銷較大，不大適合于計(jì)算機(jī)通信。計(jì)算機(jī)通信。n差錯檢測差錯檢測，即收方可以檢測出收到的幀有差錯。當(dāng)檢，即收方

9、可以檢測出收到的幀有差錯。當(dāng)檢測出有差錯的幀時就立即將它丟棄。測出有差錯的幀時就立即將它丟棄。n兩種選擇：一種方法不進(jìn)行任何處理兩種選擇：一種方法不進(jìn)行任何處理(要處理也是由高要處理也是由高層進(jìn)行層進(jìn)行)；另；另種方法則是由數(shù)據(jù)鏈路層負(fù)責(zé)重傳丟棄種方法則是由數(shù)據(jù)鏈路層負(fù)責(zé)重傳丟棄的幀。這兩種方法都是很常用的。的幀。這兩種方法都是很常用的。數(shù)據(jù)鏈路層的主要功能（續(xù)）數(shù)據(jù)鏈路層的主要功能（續(xù)）(5) 將數(shù)據(jù)和控制信息區(qū)分開將數(shù)據(jù)和控制信息區(qū)分開 n在許多情況下，數(shù)據(jù)和控制信息處于同在許多情況下，數(shù)據(jù)和控制信息處于同一幀中。因此，一定要有相應(yīng)的措施使一幀中。因此，一定要有相應(yīng)的措施使收方能夠?qū)⑺鼈儏^(qū)

10、分開來。收方能夠?qū)⑺鼈儏^(qū)分開來。數(shù)據(jù)鏈路層的主要功能（續(xù)）數(shù)據(jù)鏈路層的主要功能（續(xù)）(6) 透明傳輸透明傳輸 n所謂透明傳輸就是不管所傳數(shù)據(jù)是什么樣的比所謂透明傳輸就是不管所傳數(shù)據(jù)是什么樣的比特組合，都應(yīng)當(dāng)能夠在鏈路上傳送。特組合，都應(yīng)當(dāng)能夠在鏈路上傳送。 當(dāng)所傳數(shù)據(jù)中的比特組合恰巧出現(xiàn)了與某一個當(dāng)所傳數(shù)據(jù)中的比特組合恰巧出現(xiàn)了與某一個控制信息完全一樣時，必須有可靠的措施，使控制信息完全一樣時，必須有可靠的措施，使收方不會將這種比特組合的數(shù)據(jù)誤認(rèn)為是某種收方不會將這種比特組合的數(shù)據(jù)誤認(rèn)為是某種控制信息。只要能做到這點(diǎn)，數(shù)據(jù)鏈路層的傳控制信息。只要能做到這點(diǎn)，數(shù)據(jù)鏈路層的傳輸就被稱為是輸就被稱為

11、是透明透明的。的。數(shù)據(jù)鏈路層的主要功能（續(xù)）數(shù)據(jù)鏈路層的主要功能（續(xù)）(7) 尋址尋址 必須保證每必須保證每幀都能送到正確的目的站。幀都能送到正確的目的站。收方也應(yīng)知道發(fā)方是哪個站。收方也應(yīng)知道發(fā)方是哪個站。3.2 停止停止等待等待協(xié)議協(xié)議n3.2.1 完全理想化的數(shù)據(jù)傳輸完全理想化的數(shù)據(jù)傳輸n先研究一下數(shù)據(jù)鏈路層的模型。先研究一下數(shù)據(jù)鏈路層的模型。數(shù)據(jù)鏈路層的簡單模型數(shù)據(jù)鏈路層的簡單模型局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈

12、路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從層次上來看數(shù)據(jù)的流動數(shù)據(jù)鏈路層的簡單模型數(shù)據(jù)鏈路層的簡單模型( ( 續(xù)）續(xù)）局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機(jī)主機(jī) H1 向向 H2 發(fā)送數(shù)據(jù)發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動僅從數(shù)據(jù)鏈路層觀察幀的流動3.2 停止等待協(xié)議停止等待協(xié)議3.2.1 完全理想化的數(shù)據(jù)傳輸完全理想化的數(shù)據(jù)傳輸數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層主機(jī) A緩存主機(jī) B數(shù)據(jù)鏈路數(shù)據(jù)鏈路AP2AP1緩存發(fā)送方發(fā)送方接收方接

13、收方幀幀高層高層幀幀簡化模型：簡化模型：把數(shù)據(jù)鏈路層以上用一個主機(jī)來代替，把數(shù)據(jù)鏈路層以上用一個主機(jī)來代替，而物理層和數(shù)據(jù)鏈路層等效成一條簡單的數(shù)據(jù)鏈路而物理層和數(shù)據(jù)鏈路層等效成一條簡單的數(shù)據(jù)鏈路完全理想化的數(shù)據(jù)傳輸完全理想化的數(shù)據(jù)傳輸所基于的兩個假定所基于的兩個假定 n假定假定 1：鏈路是理想的傳輸信道，所傳：鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。送的任何數(shù)據(jù)既不會出差錯也不會丟失。n假定假定 2：不管發(fā)方以多快的速率發(fā)送數(shù)：不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時上交據(jù)，收方總是來得及收下，并及時上交主機(jī)。主機(jī)。n這個假定就相當(dāng)于認(rèn)為：接收端向主機(jī)交

14、這個假定就相當(dāng)于認(rèn)為：接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不會低于發(fā)送端發(fā)送數(shù)付數(shù)據(jù)的速率永遠(yuǎn)不會低于發(fā)送端發(fā)送數(shù)據(jù)的速率。據(jù)的速率。 3.2.2 具有最簡單流量控制的具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議數(shù)據(jù)鏈路層協(xié)議n現(xiàn)在去掉上述的第二個假定。但是，仍現(xiàn)在去掉上述的第二個假定。但是，仍然保留第一個假定，即主機(jī)然保留第一個假定，即主機(jī) A 向主機(jī)向主機(jī) B傳輸數(shù)據(jù)的信道仍然是無差錯的理想信傳輸數(shù)據(jù)的信道仍然是無差錯的理想信道。然而現(xiàn)在不能保證接收端向主機(jī)交道。然而現(xiàn)在不能保證接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不低于發(fā)送端發(fā)送數(shù)付數(shù)據(jù)的速率永遠(yuǎn)不低于發(fā)送端發(fā)送數(shù)據(jù)的速率。據(jù)的速率。n由收方控制發(fā)方的數(shù)據(jù)流由

15、收方控制發(fā)方的數(shù)據(jù)流，乃是計(jì)算機(jī)，乃是計(jì)算機(jī)網(wǎng)絡(luò)中流量控制的一個基本方法。網(wǎng)絡(luò)中流量控制的一個基本方法。 具有最簡單流量控制的具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議算法數(shù)據(jù)鏈路層協(xié)議算法在發(fā)送結(jié)點(diǎn)：在發(fā)送結(jié)點(diǎn)： (1) 從主機(jī)取一個數(shù)據(jù)幀。從主機(jī)取一個數(shù)據(jù)幀。 (2) 將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。 (3) 將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。 (4) 等待。等待。 (5) 若收到由接收結(jié)點(diǎn)發(fā)過來的信息若收到由接收結(jié)點(diǎn)發(fā)過來的信息(此信息此信息 的格式與內(nèi)容可由雙方事先商定好的格式與內(nèi)容可由雙方事先商定好)，則，則 從主機(jī)取一個新的數(shù)據(jù)

16、幀，然后轉(zhuǎn)到從主機(jī)取一個新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)。具有最簡單流量控制的具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議算法（續(xù)）數(shù)據(jù)鏈路層協(xié)議算法（續(xù)）在接收結(jié)點(diǎn)：在接收結(jié)點(diǎn)： (1) 等待。等待。 (2) 若收到由發(fā)送結(jié)點(diǎn)發(fā)過來的數(shù)據(jù)幀，若收到由發(fā)送結(jié)點(diǎn)發(fā)過來的數(shù)據(jù)幀， 則將其放入數(shù)據(jù)鏈路層的接收緩存。則將其放入數(shù)據(jù)鏈路層的接收緩存。 (3) 將接收緩存中的數(shù)據(jù)幀上交主機(jī)。將接收緩存中的數(shù)據(jù)幀上交主機(jī)。 (4) 向發(fā)送結(jié)點(diǎn)發(fā)一信息，表示數(shù)據(jù)幀已向發(fā)送結(jié)點(diǎn)發(fā)一信息，表示數(shù)據(jù)幀已 經(jīng)上交給主機(jī)。經(jīng)上交給主機(jī)。 (5) 轉(zhuǎn)到轉(zhuǎn)到(1)。兩種情況的對比（傳輸均無差錯）兩種情況的對比（傳輸均無差錯）ABDATAD

17、ATADATADATA送主機(jī) B送主機(jī) B送主機(jī) B送主機(jī) BABDATA送主機(jī) BDATA送主機(jī) B時間不需要流量控制不需要流量控制需要流量控制需要流量控制3.2.3 實(shí)用的停止等待協(xié)議實(shí)用的停止等待協(xié)議時間ABDATA0送主機(jī)ACKDATA1送主機(jī)ACK(a) 正常情況ABDATA0DATA0送主機(jī)ACK(c) 數(shù)據(jù)幀丟失重傳tout丟失 ！ABDATA0送主機(jī)ACKDATA0丟棄ACK(d) 確認(rèn)幀丟失重傳tout丟失 ！ABDATA0NAKDATA0送主機(jī)ACK(b) 數(shù)據(jù)幀出錯重傳出錯四種情況四種情況超時計(jì)時器的作用超時計(jì)時器的作用n結(jié)點(diǎn)結(jié)點(diǎn)A發(fā)送完一個數(shù)據(jù)幀時，就啟動一個發(fā)送完一個

18、數(shù)據(jù)幀時，就啟動一個超時計(jì)時器超時計(jì)時器(timeout timer)。n計(jì)時器又稱為計(jì)時器又稱為定時器定時器。n若到了超時計(jì)時器所設(shè)置的重傳時間若到了超時計(jì)時器所設(shè)置的重傳時間 tout而仍收不到結(jié)點(diǎn)而仍收不到結(jié)點(diǎn) B 的任何確認(rèn)幀，則結(jié)的任何確認(rèn)幀，則結(jié)點(diǎn)點(diǎn) A 就重傳前面所發(fā)送的這一數(shù)據(jù)幀。就重傳前面所發(fā)送的這一數(shù)據(jù)幀。n一般可將重傳時間選為略大于一般可將重傳時間選為略大于“從發(fā)完從發(fā)完數(shù)據(jù)幀到收到確認(rèn)幀所需的平均時間數(shù)據(jù)幀到收到確認(rèn)幀所需的平均時間”。 解決重復(fù)幀的問題解決重復(fù)幀的問題 n使每一個數(shù)據(jù)幀帶上不同的使每一個數(shù)據(jù)幀帶上不同的發(fā)送序號發(fā)送序號。每發(fā)送一個新的數(shù)據(jù)幀就把它的發(fā)送

19、序每發(fā)送一個新的數(shù)據(jù)幀就把它的發(fā)送序號加號加 1。 n若結(jié)點(diǎn)若結(jié)點(diǎn) B 收到發(fā)送序號相同的數(shù)據(jù)幀，收到發(fā)送序號相同的數(shù)據(jù)幀，就表明出現(xiàn)了重復(fù)幀。這時應(yīng)丟棄重復(fù)就表明出現(xiàn)了重復(fù)幀。這時應(yīng)丟棄重復(fù)幀，因?yàn)橐呀?jīng)收到過同樣的數(shù)據(jù)幀并且?guī)?，因?yàn)橐呀?jīng)收到過同樣的數(shù)據(jù)幀并且也交給了主機(jī)也交給了主機(jī) B。n但此時結(jié)點(diǎn)但此時結(jié)點(diǎn) B 還必須向還必須向 A 發(fā)送確認(rèn)幀發(fā)送確認(rèn)幀 ACK，因?yàn)?，因?yàn)?B 已經(jīng)知道已經(jīng)知道 A 還沒有收到上還沒有收到上一次發(fā)過去的確認(rèn)幀一次發(fā)過去的確認(rèn)幀 ACK。 幀的編號問題幀的編號問題 n任何一個編號系統(tǒng)的序號所占用的比特?cái)?shù)一定任何一個編號系統(tǒng)的序號所占用的比特?cái)?shù)一定是有限的。因

20、此，經(jīng)過一段時間后，發(fā)送序號是有限的。因此，經(jīng)過一段時間后，發(fā)送序號就會重復(fù)。就會重復(fù)。 n序號占用的比特?cái)?shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷序號占用的比特?cái)?shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷就越小。就越小。 n對于停止等待協(xié)議，由于每發(fā)送一個數(shù)據(jù)幀就對于停止等待協(xié)議，由于每發(fā)送一個數(shù)據(jù)幀就停止等待，因此用一個比特來編號就夠了。停止等待，因此用一個比特來編號就夠了。n一個比特可表示一個比特可表示 0 和和 1 兩種不同的序號。兩種不同的序號。 幀的發(fā)送序號幀的發(fā)送序號 n數(shù)據(jù)幀中的發(fā)送序號數(shù)據(jù)幀中的發(fā)送序號 N(S) 以以 0 和和 1 交交替的方式出現(xiàn)在數(shù)據(jù)幀中。替的方式出現(xiàn)在數(shù)據(jù)幀中。n每發(fā)一個新的數(shù)據(jù)幀，發(fā)

21、送序號就和上每發(fā)一個新的數(shù)據(jù)幀，發(fā)送序號就和上次發(fā)送的不一樣。用這樣的方法就可以次發(fā)送的不一樣。用這樣的方法就可以使收方能夠區(qū)分開新的數(shù)據(jù)幀和重傳的使收方能夠區(qū)分開新的數(shù)據(jù)幀和重傳的數(shù)據(jù)幀了。數(shù)據(jù)幀了。 可靠傳輸可靠傳輸 n雖然物理層在傳輸比特時會出現(xiàn)差錯，雖然物理層在傳輸比特時會出現(xiàn)差錯，但由于數(shù)據(jù)鏈路層的停止等待協(xié)議采用但由于數(shù)據(jù)鏈路層的停止等待協(xié)議采用了有效的檢錯重傳機(jī)制，數(shù)據(jù)鏈路層對了有效的檢錯重傳機(jī)制，數(shù)據(jù)鏈路層對上面的網(wǎng)絡(luò)層就可以提供上面的網(wǎng)絡(luò)層就可以提供可靠傳輸可靠傳輸?shù)姆姆?wù)。務(wù)。 3.2.4 循環(huán)冗余檢驗(yàn)的原理循環(huán)冗余檢驗(yàn)的原理 n在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了在數(shù)據(jù)鏈

22、路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗(yàn)循環(huán)冗余檢驗(yàn) CRC 的檢錯技術(shù)。的檢錯技術(shù)。n假設(shè)待傳送的數(shù)據(jù)假設(shè)待傳送的數(shù)據(jù) M = 1010001101（共（共k bit）。我們在）。我們在M的后面再添加供差錯的后面再添加供差錯檢測用的檢測用的 n bit 冗余碼冗余碼一起發(fā)送。一起發(fā)送。 冗余碼的計(jì)算冗余碼的計(jì)算 n用二進(jìn)制的模用二進(jìn)制的模 2 運(yùn)算進(jìn)行運(yùn)算進(jìn)行 2n 乘乘 M 的運(yùn)算，的運(yùn)算，這相當(dāng)于在這相當(dāng)于在 M 后面添加后面添加 n 個個 0。n得到的得到的 (k + n) bit 的數(shù)除以事先選定好的數(shù)除以事先選定好的長度為的長度為 (n + 1) bit 的數(shù)的數(shù) P，得出商是，得出

23、商是 Q 而余數(shù)是而余數(shù)是 R，余數(shù)，余數(shù) R 比除數(shù)比除數(shù) P 至少要至少要少少1 個比特。個比特。 冗余碼的計(jì)算舉例冗余碼的計(jì)算舉例 n設(shè)設(shè) n = 5, P = 110101，模，模 2 運(yùn)算的結(jié)果運(yùn)算的結(jié)果是：商是：商 Q = 1101010110， 余數(shù)余數(shù)R = 01110。n將余數(shù)將余數(shù) R 作為冗余碼添加在數(shù)據(jù)作為冗余碼添加在數(shù)據(jù) M 的后的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或，或 2nM + R。 1101010110 Q 商 除數(shù) P 110101 101000110100000 2nM 被除數(shù) 110101 111011

24、 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余數(shù)循環(huán)冗余檢驗(yàn)的原理說明循環(huán)冗余檢驗(yàn)的原理說明 幀檢驗(yàn)序列幀檢驗(yàn)序列 FCS n在數(shù)據(jù)后面添加上的冗余碼稱為在數(shù)據(jù)后面添加上的冗余碼稱為幀檢驗(yàn)幀檢驗(yàn)序列序列 FCS (Frame Check Sequence)。n循環(huán)冗余檢驗(yàn)循環(huán)冗余檢驗(yàn) CRC 和幀檢驗(yàn)序列和幀檢驗(yàn)序列 FCS并不等同。并不等同。nCRC 是一種常用的是一種常用的檢錯方法檢錯方法，而，而 FCS 是添是添加在數(shù)據(jù)后面的加在數(shù)據(jù)后面的冗余碼冗余碼。nFCS 可以用可以用 CRC 這種

25、方法得出，但這種方法得出，但 CRC 并非用來獲得并非用來獲得 FCS 的惟一方法。的惟一方法。 檢測出差錯檢測出差錯 n只要得出的余數(shù)只要得出的余數(shù) R 不為不為 0，就表示檢測，就表示檢測到了到了差錯差錯。n但這種檢測方法并不能確定究竟是哪一但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現(xiàn)了差錯。個或哪幾個比特出現(xiàn)了差錯。n一旦檢測出差錯，就一旦檢測出差錯，就丟棄丟棄這個出現(xiàn)差錯這個出現(xiàn)差錯的幀。的幀。n只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)多的除數(shù) P，那么出現(xiàn)檢測不到的差錯，那么出現(xiàn)檢測不到的差錯的概率就很小很小。的概率就很小很小。 應(yīng)當(dāng)注意應(yīng)

26、當(dāng)注意 n僅用循環(huán)冗余檢驗(yàn)僅用循環(huán)冗余檢驗(yàn) CRC 差錯檢測技術(shù)只能做差錯檢測技術(shù)只能做到無差錯到無差錯接受接受(accept)。n“無差錯接受無差錯接受”是指：是指：“凡是接受的幀（即凡是接受的幀（即不不包括丟棄的幀包括丟棄的幀），我們都能以非常接近于），我們都能以非常接近于 1 的的概率認(rèn)為這些幀在傳輸過程中沒有產(chǎn)生差錯概率認(rèn)為這些幀在傳輸過程中沒有產(chǎn)生差錯”。n也就是說：也就是說：“凡是接受的幀都沒有傳輸差錯凡是接受的幀都沒有傳輸差錯”（有差錯的幀就丟棄而不接受）。（有差錯的幀就丟棄而不接受）。n要做到要做到“可靠傳輸可靠傳輸”（即發(fā)送什么就收到什么）（即發(fā)送什么就收到什么）就必須再加上

27、就必須再加上確認(rèn)確認(rèn)和和重傳重傳機(jī)制。機(jī)制。 3.2.5 停止等待協(xié)議的算法停止等待協(xié)議的算法n這里這里不使用否認(rèn)幀不使用否認(rèn)幀（實(shí)用的數(shù)據(jù)鏈路層協(xié)議大（實(shí)用的數(shù)據(jù)鏈路層協(xié)議大都是這樣的），而且確認(rèn)幀帶有序號都是這樣的），而且確認(rèn)幀帶有序號 n。n按照習(xí)慣的表示法，按照習(xí)慣的表示法，ACKn 表示表示“第第 n 1 號號幀已經(jīng)收到，現(xiàn)在幀已經(jīng)收到，現(xiàn)在期望接收期望接收第第 n 號幀號幀”。nACK1 表示表示“0 號幀已收到，現(xiàn)在期望接收的下一號幀已收到，現(xiàn)在期望接收的下一幀是幀是 1 號幀號幀”；nACK0 表示表示“1 號幀已收到，現(xiàn)在期望接收的下一號幀已收到，現(xiàn)在期望接收的下一幀是幀是

28、0 號幀號幀”。 在發(fā)送結(jié)點(diǎn)在發(fā)送結(jié)點(diǎn) (1) 從主機(jī)取一個數(shù)據(jù)幀，送交發(fā)送緩存。從主機(jī)取一個數(shù)據(jù)幀，送交發(fā)送緩存。(2) V(S)0。 發(fā)送狀態(tài)變量發(fā)送狀態(tài)變量V(S)初始化初始化(3) N(S)V(S)。將發(fā)送狀態(tài)變量將發(fā)送狀態(tài)變量V(S)寫入數(shù)據(jù)幀中的發(fā)送序號寫入數(shù)據(jù)幀中的發(fā)送序號(4) 將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。 保留副本保留副本(5) 設(shè)置超時計(jì)時器。設(shè)置超時計(jì)時器。 選擇適當(dāng)?shù)某瑫r重傳時間選擇適當(dāng)?shù)某瑫r重傳時間(6) 等待。等待。 等待以下等待以下(7)和和(8)這兩個事件中最先出現(xiàn)的一個這兩個事件中最先出現(xiàn)的一個(7) 收到確認(rèn)幀收到確認(rèn)幀 AC

29、Kn， 隱含地表示通過了隱含地表示通過了CRC硬件差錯檢測硬件差錯檢測 若若 n = 1 V(s)，則：，則： 已發(fā)送的數(shù)據(jù)幀被接收方確認(rèn)已發(fā)送的數(shù)據(jù)幀被接收方確認(rèn) 從主機(jī)取一個新的數(shù)據(jù)幀，放入發(fā)送緩存；從主機(jī)取一個新的數(shù)據(jù)幀，放入發(fā)送緩存； V(S)1 V(S)， 更新發(fā)送狀態(tài)變量，使用下一序號更新發(fā)送狀態(tài)變量，使用下一序號 轉(zhuǎn)到轉(zhuǎn)到 (3)。 否則，丟棄這個確認(rèn)幀，轉(zhuǎn)到否則，丟棄這個確認(rèn)幀，轉(zhuǎn)到(6)。 表明沒有被接收方確認(rèn)表明沒有被接收方確認(rèn)(8) 若超時計(jì)時器時間到，則轉(zhuǎn)到若超時計(jì)時器時間到，則轉(zhuǎn)到(4) 。 重發(fā)重發(fā)在接收結(jié)點(diǎn)在接收結(jié)點(diǎn) (1) V(R)0。接收狀態(tài)變量的初始化接收狀

30、態(tài)變量的初始化(2) 等待。等待。(3) 收到一個數(shù)據(jù)幀；收到一個數(shù)據(jù)幀； 隱含地通過了隱含地通過了CRC硬件差錯檢測硬件差錯檢測 若若 N(S) = V(R)，則執(zhí)行，則執(zhí)行(4)； 收到正確序號的幀收到正確序號的幀 否則丟棄此數(shù)據(jù)幀，然后轉(zhuǎn)到否則丟棄此數(shù)據(jù)幀，然后轉(zhuǎn)到(6)。 丟棄重復(fù)幀丟棄重復(fù)幀(4) 將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交上層軟件將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交上層軟件 （也就是數(shù)據(jù)鏈路層模型中的主機(jī)）。（也就是數(shù)據(jù)鏈路層模型中的主機(jī)）。(5) V(R)1 V(R)。更新接收狀態(tài)變量，準(zhǔn)備接收下更新接收狀態(tài)變量，準(zhǔn)備接收下一個一個(6) nV(R)； 發(fā)送確認(rèn)幀發(fā)送確認(rèn)幀 ACK

31、n，轉(zhuǎn)到，轉(zhuǎn)到(2)。 期望接收期望接收n號幀，在號幀，在它之前的都收到了它之前的都收到了停止等待協(xié)議的要點(diǎn)停止等待協(xié)議的要點(diǎn)n只有收到序號正確的確認(rèn)幀只有收到序號正確的確認(rèn)幀 ACKn 后，才更新后，才更新發(fā)送狀態(tài)變量發(fā)送狀態(tài)變量 V(S)一次，并發(fā)送新的數(shù)據(jù)幀。一次，并發(fā)送新的數(shù)據(jù)幀。n接收端接收到數(shù)據(jù)幀時，就要將發(fā)送序號接收端接收到數(shù)據(jù)幀時，就要將發(fā)送序號 N(S) 與本地的接收狀態(tài)變量與本地的接收狀態(tài)變量 V(R) 相比較。相比較。n若二者相等就表明是若二者相等就表明是新的數(shù)據(jù)幀新的數(shù)據(jù)幀，就收下，并發(fā)送，就收下，并發(fā)送確認(rèn)。確認(rèn)。n否則為否則為重復(fù)幀重復(fù)幀，就必須丟棄。但這時，就必須

32、丟棄。但這時仍須向發(fā)送端仍須向發(fā)送端發(fā)送確認(rèn)幀發(fā)送確認(rèn)幀 ACKn，而接收狀態(tài)變量，而接收狀態(tài)變量 V(R) 和確認(rèn)序和確認(rèn)序號號 n 都不變。都不變。 停止等待協(xié)議的要點(diǎn)（續(xù)）停止等待協(xié)議的要點(diǎn)（續(xù)）n連續(xù)出現(xiàn)相同發(fā)送序號的數(shù)據(jù)幀，表明連續(xù)出現(xiàn)相同發(fā)送序號的數(shù)據(jù)幀，表明發(fā)送端進(jìn)行了發(fā)送端進(jìn)行了超時重傳超時重傳。連續(xù)出現(xiàn)相同。連續(xù)出現(xiàn)相同序號的確認(rèn)幀，表明接收端收到了序號的確認(rèn)幀，表明接收端收到了重復(fù)重復(fù)幀幀。 n發(fā)送端在發(fā)送完數(shù)據(jù)幀時，必須在其發(fā)發(fā)送端在發(fā)送完數(shù)據(jù)幀時，必須在其發(fā)送緩存中暫時保留這個數(shù)據(jù)幀的送緩存中暫時保留這個數(shù)據(jù)幀的副本副本。這樣才能在出差錯時進(jìn)行重傳。只有確這樣才能在出差

33、錯時進(jìn)行重傳。只有確認(rèn)對方已經(jīng)收到這個數(shù)據(jù)幀時，才可以認(rèn)對方已經(jīng)收到這個數(shù)據(jù)幀時，才可以清除這個副本。清除這個副本。 停止等待協(xié)議的要點(diǎn)（續(xù)）停止等待協(xié)議的要點(diǎn)（續(xù)）n實(shí)用的實(shí)用的 CRC 檢驗(yàn)器都是用檢驗(yàn)器都是用硬件硬件完成的。完成的。nCRC 檢驗(yàn)器能夠自動丟棄檢測到的出錯檢驗(yàn)器能夠自動丟棄檢測到的出錯幀。因此所謂的幀。因此所謂的“丟棄出錯幀丟棄出錯幀”，對上，對上層軟件或用戶來說都是層軟件或用戶來說都是感覺不到感覺不到的。的。n發(fā)送端對出錯的數(shù)據(jù)幀進(jìn)行重傳是自動發(fā)送端對出錯的數(shù)據(jù)幀進(jìn)行重傳是自動進(jìn)行的，因而這種差錯控制體制常簡稱進(jìn)行的，因而這種差錯控制體制常簡稱為為ARQ (Automa

34、tic Repeat reQuest)，直譯是直譯是自動重傳請求自動重傳請求，但意思是，但意思是自動請自動請求重傳求重傳。 3.2.6 停止等待協(xié)議的定量分析停止等待協(xié)議的定量分析n設(shè)設(shè) tf 是一個數(shù)據(jù)幀的是一個數(shù)據(jù)幀的發(fā)送時間發(fā)送時間，且數(shù)據(jù)幀的長度是固，且數(shù)據(jù)幀的長度是固定不變的。顯然，數(shù)據(jù)幀的發(fā)送時間定不變的。顯然，數(shù)據(jù)幀的發(fā)送時間 tf 是數(shù)據(jù)幀的長是數(shù)據(jù)幀的長度度 lf (bit)與數(shù)據(jù)的發(fā)送速率與數(shù)據(jù)的發(fā)送速率 C (bit/s)之比，即之比，即 tf = lf /C = lf /C (s) （3-1） n發(fā)送時間發(fā)送時間 tf 也就是數(shù)據(jù)幀的也就是數(shù)據(jù)幀的發(fā)送時延發(fā)送時延。n數(shù)

35、據(jù)幀沿鏈路傳到結(jié)點(diǎn)數(shù)據(jù)幀沿鏈路傳到結(jié)點(diǎn)B還要經(jīng)歷一個還要經(jīng)歷一個傳播時延傳播時延 tp。n結(jié)點(diǎn)結(jié)點(diǎn) B 收到數(shù)據(jù)幀要花費(fèi)時間進(jìn)行處理，此時間稱為收到數(shù)據(jù)幀要花費(fèi)時間進(jìn)行處理，此時間稱為處理時間處理時間 tpr，發(fā)送確認(rèn)幀，發(fā)送確認(rèn)幀 ACK 的發(fā)送時間為的發(fā)送時間為 ta。 停止等待協(xié)議中數(shù)據(jù)幀和確認(rèn)幀停止等待協(xié)議中數(shù)據(jù)幀和確認(rèn)幀的發(fā)送時間關(guān)系的發(fā)送時間關(guān)系 ABDATADATAACK傳播時延 tp處理時間 tpr確認(rèn)幀發(fā)送時間 ta傳播時延 tp處理時間 tprtT時間兩個成功發(fā)送的數(shù)據(jù)幀之間的最小時間間隔數(shù)據(jù)幀的發(fā)送時間tf設(shè)置的重傳時間tout重傳時間重傳時間 n重傳時間的作用是：數(shù)據(jù)幀

36、發(fā)送完畢后若經(jīng)過了這樣重傳時間的作用是：數(shù)據(jù)幀發(fā)送完畢后若經(jīng)過了這樣長的時間還沒有收到確認(rèn)幀，就重傳這個數(shù)據(jù)幀。長的時間還沒有收到確認(rèn)幀，就重傳這個數(shù)據(jù)幀。 n為方便起見，我們設(shè)重傳時間為為方便起見，我們設(shè)重傳時間為 tout = tp + tpr+ ta + tp + tpr (3-2) n設(shè)上式右端的處理時間設(shè)上式右端的處理時間 tpr 和確認(rèn)幀的發(fā)送時間和確認(rèn)幀的發(fā)送時間 ta 都遠(yuǎn)都遠(yuǎn)小于傳播時延小于傳播時延 tp，因此可將重傳時間取為，因此可將重傳時間取為兩倍的傳播兩倍的傳播時延時延，即，即 tout = 2tp (3-3)簡單的數(shù)學(xué)分析簡單的數(shù)學(xué)分析 n兩個發(fā)送成功的數(shù)據(jù)幀之間的最

37、小時間間隔是兩個發(fā)送成功的數(shù)據(jù)幀之間的最小時間間隔是 tT = tf + tout = tf + 2tp (3-4) n設(shè)數(shù)據(jù)幀出現(xiàn)差錯設(shè)數(shù)據(jù)幀出現(xiàn)差錯(包括幀丟失包括幀丟失)的概率為的概率為 p，但假設(shè)確認(rèn)幀不會出現(xiàn)差錯。但假設(shè)確認(rèn)幀不會出現(xiàn)差錯。n設(shè)設(shè)正確正確傳送一個數(shù)據(jù)幀所需的傳送一個數(shù)據(jù)幀所需的平均時間平均時間 tav tav = tT ( 1 + 一個幀的平均重傳次數(shù)一個幀的平均重傳次數(shù)) 簡單的數(shù)學(xué)分析（續(xù)）簡單的數(shù)學(xué)分析（續(xù)） 一幀的平均重傳次數(shù)一幀的平均重傳次數(shù) = 1 P重傳次數(shù)為重傳次數(shù)為 1 + 2 P重傳次數(shù)為重傳次數(shù)為 2 + 3 P重傳次數(shù)為重傳次數(shù)為 3 + =

38、1 P第第 1 次發(fā)送出錯次發(fā)送出錯 P第第 2 次發(fā)送成功次發(fā)送成功 + 2 P第第 1, 2 次發(fā)送出錯次發(fā)送出錯 P第第 3 次發(fā)送成功次發(fā)送成功 + 3 P第第 1, 2, 3 次發(fā)送出錯次發(fā)送出錯 P第第 4 次發(fā)送成功次發(fā)送成功 + = p(1 p) + 2p2(1 p) + 3p3(1 p) + 這里這里 PX 是出現(xiàn)事件是出現(xiàn)事件 X 的概率。的概率。 簡單的數(shù)學(xué)分析（續(xù)）簡單的數(shù)學(xué)分析（續(xù)） 得出正確傳送一個數(shù)據(jù)幀所需的平均時間：得出正確傳送一個數(shù)據(jù)幀所需的平均時間：當(dāng)傳輸差錯率增大時，當(dāng)傳輸差錯率增大時，tav 也隨之增大。當(dāng)無差錯時，也隨之增大。當(dāng)無差錯時，p = 0,

39、tav = tT。 )1 ( /)1 (1pttippttiTTiTav(3-5)簡單的數(shù)學(xué)分析（續(xù)）簡單的數(shù)學(xué)分析（續(xù)） 每秒成功發(fā)送的最大幀數(shù)就是鏈路的最大吞吐量每秒成功發(fā)送的最大幀數(shù)就是鏈路的最大吞吐量 max。顯然，。顯然， max = 1/tav = (1 p) / tT (3-6)在發(fā)送端，設(shè)數(shù)據(jù)幀的實(shí)際到達(dá)率為在發(fā)送端，設(shè)數(shù)據(jù)幀的實(shí)際到達(dá)率為 ，則，則 不應(yīng)超過最大吞吐量不應(yīng)超過最大吞吐量 max，即，即 (1 p) / tT (3-7)用時間用時間 tf 進(jìn)行歸一化，得出歸一化的吞吐量進(jìn)行歸一化，得出歸一化的吞吐量 為為 tf (1 p) / 1 (3-8)其中參數(shù)其中參數(shù) 是

40、是 tT 的歸一化時間：的歸一化時間： tT / tf 1 (3-9)當(dāng)重傳時間遠(yuǎn)小于發(fā)送時間時，當(dāng)重傳時間遠(yuǎn)小于發(fā)送時間時， 1，此時的歸一化吞吐量，此時的歸一化吞吐量 1 p (3-10) 停止等待協(xié)議停止等待協(xié)議 ARQ 的優(yōu)缺點(diǎn)的優(yōu)缺點(diǎn) n優(yōu)點(diǎn)：優(yōu)點(diǎn)：比較簡單比較簡單 。n缺點(diǎn)：通信信道的利用率不高，也就是說，缺點(diǎn)：通信信道的利用率不高，也就是說，信道還遠(yuǎn)遠(yuǎn)沒有被數(shù)據(jù)比特填滿。信道還遠(yuǎn)遠(yuǎn)沒有被數(shù)據(jù)比特填滿。n為了克服這一缺點(diǎn)，就產(chǎn)生了另外兩種協(xié)議，為了克服這一缺點(diǎn)，就產(chǎn)生了另外兩種協(xié)議，即連續(xù)即連續(xù) ARQ 和選擇重傳和選擇重傳 ARQ。這將在后面。這將在后面進(jìn)一步討論。進(jìn)一步討論。

41、3.3連續(xù)連續(xù) ARQ 協(xié)議協(xié)議3.3.1 連續(xù)連續(xù) ARQ 協(xié)議的工作原理協(xié)議的工作原理 n在發(fā)送完一個數(shù)據(jù)幀后，不是停下來等待確在發(fā)送完一個數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個數(shù)據(jù)幀。認(rèn)幀，而是可以連續(xù)再發(fā)送若干個數(shù)據(jù)幀。n如果這時收到了接收端發(fā)來的確認(rèn)幀，那么如果這時收到了接收端發(fā)來的確認(rèn)幀，那么還可以接著發(fā)送數(shù)據(jù)幀。還可以接著發(fā)送數(shù)據(jù)幀。n由于減少了等待時間，整個通信的吞吐量就由于減少了等待時間，整個通信的吞吐量就提高了。提高了。 連續(xù)連續(xù) ARQ 協(xié)議的工作原理協(xié)議的工作原理 DATA0DATA1DATA2DATA3DATA4DATA5重傳 DATA2重傳 DAT

42、A3ACK1ACK2ACK1 確認(rèn) DATA0ACK2 確認(rèn) DATA1DATA2 出錯，丟棄DATA3 不按序，丟棄，重傳 ACK2DATA4 不按序，丟棄，重傳 ACK2DATA5 不按序，丟棄，重傳 ACK2ACK3ACK3 確認(rèn) DATA2ACK4 確認(rèn) DATA3ACK4重傳 DATA5重傳 DATA4超超時時重重傳傳時時間間ABtout送交主機(jī)送交主機(jī)?ACK2ACK2ACK2需要注意：需要注意： (1) 接收端接收端只按序接收只按序接收數(shù)據(jù)幀。雖然在有差錯的數(shù)據(jù)幀。雖然在有差錯的 2號幀之號幀之后接著又收到了正確的后接著又收到了正確的 3 個數(shù)據(jù)幀，但接收端都必須個數(shù)據(jù)幀，但接收

43、端都必須將這些幀丟棄，因?yàn)樵谶@些幀前面有一個將這些幀丟棄，因?yàn)樵谶@些幀前面有一個 2 號幀還沒號幀還沒有收到。雖然丟棄了這些不按序的無差錯幀，但應(yīng)重有收到。雖然丟棄了這些不按序的無差錯幀，但應(yīng)重復(fù)發(fā)送已發(fā)送過的最后一個確認(rèn)幀（防止確認(rèn)幀丟復(fù)發(fā)送已發(fā)送過的最后一個確認(rèn)幀（防止確認(rèn)幀丟失）。失）。(2) ACK1 表示確認(rèn)表示確認(rèn) 0 號幀號幀 DATA0，并期望下次收到，并期望下次收到 1 號幀；號幀；ACK2 表示確認(rèn)表示確認(rèn) 1 號幀號幀 DATA1，并期望下次收，并期望下次收到到 2 號幀。依此類推。號幀。依此類推。 需要注意：需要注意： (3) 結(jié)點(diǎn)結(jié)點(diǎn) A 在每發(fā)送完一個數(shù)據(jù)幀時都要設(shè)

44、置該幀的在每發(fā)送完一個數(shù)據(jù)幀時都要設(shè)置該幀的超時超時計(jì)時器計(jì)時器。如果在所設(shè)置的超時時間內(nèi)收到確認(rèn)幀，就。如果在所設(shè)置的超時時間內(nèi)收到確認(rèn)幀，就立即將超時計(jì)時器清零。但若在所設(shè)置的超時時間到立即將超時計(jì)時器清零。但若在所設(shè)置的超時時間到了而未收到確認(rèn)幀，就要重傳相應(yīng)的數(shù)據(jù)幀（仍需重了而未收到確認(rèn)幀，就要重傳相應(yīng)的數(shù)據(jù)幀（仍需重新設(shè)置超時計(jì)時器）。新設(shè)置超時計(jì)時器）。 在等不到在等不到 2 號幀的確認(rèn)而重傳號幀的確認(rèn)而重傳 2 號數(shù)據(jù)幀時，雖號數(shù)據(jù)幀時，雖然結(jié)點(diǎn)然結(jié)點(diǎn) A 已經(jīng)發(fā)完了已經(jīng)發(fā)完了 5 號幀，但仍必須向回走，將號幀，但仍必須向回走，將 2號幀及其以后的各幀全部進(jìn)行重傳。連續(xù)號幀及其以

45、后的各幀全部進(jìn)行重傳。連續(xù) ARQ 又稱又稱為為Go-back-N ARQ，意思是當(dāng)出現(xiàn)差錯必須重傳時，意思是當(dāng)出現(xiàn)差錯必須重傳時，要向回走要向回走 N 個幀，然后再開始重傳。個幀，然后再開始重傳。 需要注意：需要注意： (4) 以上講述的僅僅是連續(xù)以上講述的僅僅是連續(xù) ARQ 協(xié)議的工作原理。協(xié)議協(xié)議的工作原理。協(xié)議在具體實(shí)現(xiàn)時還有許多的細(xì)節(jié)。例如，用一個計(jì)時器在具體實(shí)現(xiàn)時還有許多的細(xì)節(jié)。例如，用一個計(jì)時器就可實(shí)現(xiàn)相當(dāng)于就可實(shí)現(xiàn)相當(dāng)于 N 個獨(dú)立的超時計(jì)時器的功能。個獨(dú)立的超時計(jì)時器的功能。 3.3.2 連續(xù)連續(xù) ARQ 協(xié)議的吞吐量協(xié)議的吞吐量 n可以很方便地導(dǎo)出連續(xù)可以很方便地導(dǎo)出連續(xù)

46、ARQ 協(xié)議的吞協(xié)議的吞吐量公式。吐量公式。3.3.3 滑動窗口的概念滑動窗口的概念n發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口 。n發(fā)送窗口用來對發(fā)送端進(jìn)行流量控制。發(fā)送窗口用來對發(fā)送端進(jìn)行流量控制。n發(fā)送窗口的大小發(fā)送窗口的大小 WT 代表在還沒有收到對方確認(rèn)信代表在還沒有收到對方確認(rèn)信息的情況下發(fā)送端最多可以發(fā)送多少個數(shù)據(jù)幀。息的情況下發(fā)送端最多可以發(fā)送多少個數(shù)據(jù)幀。 01234567012發(fā)送窗口WT不允許發(fā)送這些幀允許發(fā)送 5 個幀(a)01234567012不允許發(fā)送這些幀還允許發(fā)送 4 個幀WT已發(fā)送(b)01234567012不允許發(fā)送這些

47、幀WT已發(fā)送(c)01234567012不允許發(fā)送這些幀還允許發(fā)送 3 個幀WT已發(fā)送 已發(fā)送并已收到確認(rèn)(d)接收端設(shè)置接收窗口接收端設(shè)置接收窗口 n在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號落入接在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。 n若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將其丟棄。其丟棄。 n在連續(xù)在連續(xù) ARQ 協(xié)議中，接收窗口的大小協(xié)議中，接收窗口的大小 WR = 1。n只有當(dāng)收到的幀的序號與接收窗口一致時才能接收該幀。只有當(dāng)收到的幀的序號與接收窗口一致時才能接收該幀。否則，就丟棄

48、它。否則，就丟棄它。n每收到一個序號正確的幀，接收窗口就向前（即向右方）每收到一個序號正確的幀，接收窗口就向前（即向右方）滑動一個幀的位置。同時發(fā)送對該幀的確認(rèn)?；瑒右粋€幀的位置。同時發(fā)送對該幀的確認(rèn)。 不允許接收這些幀01234567012WR準(zhǔn)備接收 0 號幀(a)不允許接收這些幀01234567012WR準(zhǔn)備接收 1 號幀已收到(b)不允許接收這些幀01234567012WR準(zhǔn)備接收 4 號幀已收到(c)滑動窗口的重要特性滑動窗口的重要特性n只有在接收窗口向前滑動時（與此同時只有在接收窗口向前滑動時（與此同時也發(fā)送了確認(rèn)），發(fā)送窗口才有可能向也發(fā)送了確認(rèn)），發(fā)送窗口才有可能向前滑動。前滑

49、動。n收發(fā)兩端的窗口按照以上規(guī)律不斷地向收發(fā)兩端的窗口按照以上規(guī)律不斷地向前滑動，因此這種協(xié)議又稱為滑動窗口前滑動，因此這種協(xié)議又稱為滑動窗口協(xié)議。協(xié)議。n當(dāng)發(fā)送窗口和接收窗口的大小都等于當(dāng)發(fā)送窗口和接收窗口的大小都等于 1時，就是停止等待協(xié)議。時，就是停止等待協(xié)議。 發(fā)送窗口的最大值發(fā)送窗口的最大值 n當(dāng)用當(dāng)用 n 個比特進(jìn)行編號時，若接收窗口個比特進(jìn)行編號時，若接收窗口的大小為的大小為 1，則只有在發(fā)送窗口的大小，則只有在發(fā)送窗口的大小 WT 2n 1時，連續(xù)時，連續(xù) ARQ 協(xié)議才能正協(xié)議才能正確運(yùn)行。確運(yùn)行。n例如，當(dāng)采用例如，當(dāng)采用 3 bit 編碼時，發(fā)送窗口的編碼時，發(fā)送窗口的最

50、大值是最大值是 7 而不是而不是 8。 3.3.4 信道利用率信道利用率n由于每個數(shù)據(jù)幀都必須包括一定的控制由于每個數(shù)據(jù)幀都必須包括一定的控制信息信息(如幀的序號、地址、同步信息以及如幀的序號、地址、同步信息以及其他的一些控制信息其他的一些控制信息)，所以即使連續(xù)不，所以即使連續(xù)不停地發(fā)送數(shù)據(jù)幀，信道利用率停地發(fā)送數(shù)據(jù)幀，信道利用率(即扣除全即扣除全部的控制信息后的數(shù)據(jù)率與信道容量之部的控制信息后的數(shù)據(jù)率與信道容量之比比)也不可能達(dá)到也不可能達(dá)到 100 %。 n當(dāng)出現(xiàn)差錯時當(dāng)出現(xiàn)差錯時(這是不可避免的這是不可避免的)，數(shù)據(jù)幀，數(shù)據(jù)幀的不斷重傳將進(jìn)一步使信道利用率降低。的不斷重傳將進(jìn)一步使信道

51、利用率降低。 最佳幀長最佳幀長 n若數(shù)據(jù)幀的幀長取得很短，那么控制信若數(shù)據(jù)幀的幀長取得很短，那么控制信息在每一幀中所占的比例就增大，因而息在每一幀中所占的比例就增大，因而額外開銷增大，這就導(dǎo)致信道利用率的額外開銷增大，這就導(dǎo)致信道利用率的下降。下降。n若幀長取得太長，則數(shù)據(jù)幀在傳輸過程若幀長取得太長，則數(shù)據(jù)幀在傳輸過程中出錯的概率就增大，于是重傳次數(shù)將中出錯的概率就增大，于是重傳次數(shù)將增大，這也會使信道利用率下降。增大，這也會使信道利用率下降。n由此可見，存在一個由此可見，存在一個最佳幀長最佳幀長，在此幀，在此幀長下信道的利用率最高。長下信道的利用率最高。 3.4 選擇重傳選擇重傳 ARQ 協(xié)

52、議協(xié)議 n可加大接收窗口，先收下發(fā)送序號不連續(xù)但仍可加大接收窗口，先收下發(fā)送序號不連續(xù)但仍處在接收窗口中的那些數(shù)據(jù)幀。等到所缺序號處在接收窗口中的那些數(shù)據(jù)幀。等到所缺序號的數(shù)據(jù)幀收到后再一并送交主機(jī)。的數(shù)據(jù)幀收到后再一并送交主機(jī)。 n選擇重傳選擇重傳 ARQ 協(xié)議可避免重復(fù)傳送那些本來協(xié)議可避免重復(fù)傳送那些本來已經(jīng)正確到達(dá)接收端的數(shù)據(jù)幀。已經(jīng)正確到達(dá)接收端的數(shù)據(jù)幀。n但我們付出的代價是在接收端要設(shè)置具有相當(dāng)?shù)覀兏冻龅拇鷥r是在接收端要設(shè)置具有相當(dāng)容量的緩存空間。容量的緩存空間。n對于選擇重傳對于選擇重傳 ARQ 協(xié)議，若用協(xié)議，若用 n 比特進(jìn)行編比特進(jìn)行編號，則接收窗口的最大值受下式的約束號

53、，則接收窗口的最大值受下式的約束WR 2n/2 (3-18) 3.5 面向比特的鏈路控制規(guī)程面向比特的鏈路控制規(guī)程 HDLC3.5.1 HDLC 協(xié)議概述協(xié)議概述n1974年，年，IBM 公司推出了面向比特的規(guī)程公司推出了面向比特的規(guī)程SDLC (Synchronous Data Link Control)。n后來后來 ISO 把把 SDLC 修改后稱為修改后稱為 HDLC (High-level Data Link Control)，譯為高級數(shù)據(jù)鏈路，譯為高級數(shù)據(jù)鏈路控制，作為國際標(biāo)準(zhǔn)控制，作為國際標(biāo)準(zhǔn)ISO 3309。nCCITT 則將則將 HDLC 再修改后稱為鏈路接入規(guī)再修改后稱為鏈路

54、接入規(guī)程程 LAP (Link Access Procedure)。不久，。不久，HDLC 的新版本又把的新版本又把 LAP 修改為修改為 LAPB，“B”表示平衡型表示平衡型(Balanced)，所以，所以 LAPB 叫做鏈叫做鏈路接入規(guī)程路接入規(guī)程(平衡型平衡型)。 3.5.2 HDLC 的幀結(jié)構(gòu)的幀結(jié)構(gòu)n標(biāo)志字段 F (Flag) 為 6 個連續(xù) 1 加上兩邊各一個 0 共 8 bit。在接收端只要找到標(biāo)志字段就可確定一個幀的位置。 比特888可變168信息 Info標(biāo)志 F標(biāo)志 F地址 A控制 C幀檢驗(yàn)序列 FCS透明傳輸區(qū)間FCS 檢驗(yàn)區(qū)間零比特填充法零比特填充法 nHDLC 采用零

55、比特填充法使一幀中兩個采用零比特填充法使一幀中兩個 F 字段之間不會出現(xiàn)字段之間不會出現(xiàn) 6 個連續(xù)個連續(xù) 1。n在發(fā)送端，當(dāng)一串比特流數(shù)據(jù)中有在發(fā)送端，當(dāng)一串比特流數(shù)據(jù)中有 5 個個連續(xù)連續(xù) 1 時，就立即填入一個時，就立即填入一個 0。n在接收幀時，先找到在接收幀時，先找到 F 字段以確定幀的字段以確定幀的邊界。接著再對比特流進(jìn)行掃描。每當(dāng)邊界。接著再對比特流進(jìn)行掃描。每當(dāng)發(fā)現(xiàn)發(fā)現(xiàn) 5 個連續(xù)個連續(xù) 1 時，就將其后的一個時，就將其后的一個 0 刪除，以還原成原來的比特流。刪除，以還原成原來的比特流。 零比特的填充與刪除零比特的填充與刪除 數(shù)據(jù)中某一段比特組合恰好數(shù)據(jù)中某一段比特組合恰好出

56、現(xiàn)和出現(xiàn)和 F 字段一樣的情況字段一樣的情況0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0會被誤認(rèn)為是會被誤認(rèn)為是 F 字段字段發(fā)送端在發(fā)送端在 5 個連個連 1 之后之后填入填入 0 比特再發(fā)送出去比特再發(fā)送出去填入填入 0 比特比特0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0在接收端將在接收端將 5 個連個連 1 之后之后的的 0 比特刪除，恢復(fù)原樣比特刪除，恢復(fù)原樣在此位置刪除填入的在此位置刪除填入的 0 比特比特0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0透明傳輸透明傳輸 n采用零比特填充法就可傳送任意組采用零比特

57、填充法就可傳送任意組合的比特流，或者說，就可實(shí)現(xiàn)數(shù)合的比特流，或者說，就可實(shí)現(xiàn)數(shù)據(jù)鏈路層的據(jù)鏈路層的透明傳輸透明傳輸。n當(dāng)連續(xù)傳輸兩個幀時，前一個幀的結(jié)束當(dāng)連續(xù)傳輸兩個幀時，前一個幀的結(jié)束標(biāo)志字段標(biāo)志字段 F 可以兼作后一幀的起始標(biāo)志可以兼作后一幀的起始標(biāo)志字段。字段。n當(dāng)暫時沒有信息傳送時，可以連續(xù)發(fā)送當(dāng)暫時沒有信息傳送時，可以連續(xù)發(fā)送標(biāo)志字段，使收端可以一直和發(fā)端保持標(biāo)志字段，使收端可以一直和發(fā)端保持同步。同步。 其他字段其他字段 n地址字段地址字段 A 是是 8 bit。 n幀檢驗(yàn)序列幀檢驗(yàn)序列 FCS 字段共字段共 16 bit。所檢驗(yàn)。所檢驗(yàn)的范圍是從地址字段的第一個比特起，的范圍是

58、從地址字段的第一個比特起，到信息字段的最末一個比特為止。到信息字段的最末一個比特為止。 n控制字段控制字段 C 共共 8 bit，是最復(fù)雜的字段。，是最復(fù)雜的字段。HDLC 的許多重要功能都靠控制字段來的許多重要功能都靠控制字段來實(shí)現(xiàn)。實(shí)現(xiàn)。 3.6 因特網(wǎng)的點(diǎn)對點(diǎn)協(xié)議因特網(wǎng)的點(diǎn)對點(diǎn)協(xié)議 PPP3.6.1 PPP 協(xié)議的工作原理協(xié)議的工作原理n現(xiàn)在全世界使用得最多的數(shù)據(jù)鏈路層協(xié)現(xiàn)在全世界使用得最多的數(shù)據(jù)鏈路層協(xié)議是議是點(diǎn)對點(diǎn)協(xié)議點(diǎn)對點(diǎn)協(xié)議 PPP (Point-to-Point Protocol)。n用戶使用撥號電話線接入因特網(wǎng)時，一用戶使用撥號電話線接入因特網(wǎng)時，一般都是使用般都是使用 PPP 協(xié)議。協(xié)議。 用戶撥號入網(wǎng)的示意圖用戶撥號入網(wǎng)的示意圖 路由器調(diào)制解調(diào)器調(diào)制解調(diào)器因特網(wǎng)服務(wù)提供者(ISP)用戶家庭撥號電話線 使用 TCP/IP 的 PPP 連接使用 TCP/IP 的 客戶進(jìn)程路由選擇 進(jìn)程至因特網(wǎng)PC 機(jī)PPP 協(xié)議協(xié)議 n1992 年制訂了年制訂了 PPP 協(xié)議。經(jīng)過協(xié)議。經(jīng)過 1993 年和年和 1994 年的修訂，現(xiàn)在的年