計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)第3章課件

1、第3章 數(shù)據(jù)鏈路層第1頁，共56頁。導(dǎo)入PPP協(xié)議是目前Internet上使用最為廣泛的點(diǎn)對(duì)點(diǎn)數(shù)據(jù)鏈路層協(xié)議。什么是數(shù)據(jù)鏈路層？其功能是什么？它包括哪些設(shè)計(jì)要點(diǎn)和關(guān)鍵技術(shù)？數(shù)據(jù)鏈路層協(xié)議包含哪些基本類型和具體實(shí)現(xiàn)方法？ 第2頁，共56頁。主要內(nèi)容3.1 數(shù)據(jù)鏈路層的基本概念3.2 差錯(cuò)控制編碼技術(shù)3.3 數(shù)據(jù)鏈路層協(xié)議3.4 數(shù)據(jù)鏈路層協(xié)議示例第3頁，共56頁。3.1 數(shù)據(jù)鏈路層的基本概念3.1.1 鏈路和數(shù)據(jù)鏈路3.1.2 數(shù)據(jù)鏈路層為網(wǎng)絡(luò)層提供的服務(wù)3.1.3 數(shù)據(jù)鏈路層設(shè)計(jì)要點(diǎn)數(shù)據(jù)鏈路層屬于計(jì)算機(jī)網(wǎng)絡(luò)的低層，數(shù)據(jù)鏈路層的主要功能是在不可靠的物理線路上實(shí)現(xiàn)數(shù)據(jù)的可靠傳輸，即數(shù)據(jù)鏈路層提供網(wǎng)

2、絡(luò)中相鄰節(jié)點(diǎn)之間的可靠的數(shù)據(jù)通信。數(shù)據(jù)鏈路層按使用信道類型的不同可以分為點(diǎn)對(duì)點(diǎn)信道的數(shù)據(jù)鏈路層和廣播信道的數(shù)據(jù)鏈路層兩種。本章主要介紹前者。 第4頁，共56頁。3.1.1 鏈路和數(shù)據(jù)鏈路鏈路，又叫物理鏈路，是一條無源的點(diǎn)到點(diǎn)的物理線路，中間沒有任何交換節(jié)點(diǎn)。 物理鏈路加上必要的通信協(xié)議(規(guī)程)，或者說把實(shí)現(xiàn)通信協(xié)議（規(guī)程）的硬件或軟件加在鏈路上，就構(gòu)成了數(shù)據(jù)鏈路，也稱邏輯鏈路。 第5頁，共56頁。3.1.2 數(shù)據(jù)鏈路層為網(wǎng)絡(luò)層提供的服務(wù)設(shè)立數(shù)據(jù)鏈路層的主要目的將原始的、不可靠的物理線路變?yōu)閷?duì)網(wǎng)絡(luò)層無差錯(cuò)的數(shù)據(jù)鏈路。為了實(shí)現(xiàn)這個(gè)目的，數(shù)據(jù)鏈路層必須實(shí)現(xiàn)鏈路管理、成幀與透明傳輸、流量控制、差錯(cuò)控制

3、等功能。數(shù)據(jù)鏈路層必須實(shí)現(xiàn)鏈路管理、成幀與透明傳輸、流量控制、差錯(cuò)控制等功能。 數(shù)據(jù)鏈路層為網(wǎng)絡(luò)層提供的服務(wù)中最主要的是將數(shù)據(jù)從源主機(jī)的網(wǎng)絡(luò)層傳輸?shù)侥康闹鳈C(jī)的網(wǎng)絡(luò)層。 第6頁，共56頁。數(shù)據(jù)鏈路層提供以下3種可能服務(wù) 1. 無確認(rèn)的無連接服務(wù)當(dāng)線路通信質(zhì)量高(錯(cuò)誤率很低)時(shí)，或在實(shí)時(shí)通信中，此類服務(wù)是很合適的。目前，絕大多數(shù)局域網(wǎng)中均采用此項(xiàng)服務(wù)。2. 有確認(rèn)的無連接服務(wù)數(shù)據(jù)鏈路層上提供確認(rèn)只是一種優(yōu)化，而永遠(yuǎn)不應(yīng)該是一種要求。此類服務(wù)用在不可靠的無線信道上是非常適合的。3. 有確認(rèn)的面向連接服務(wù)數(shù)據(jù)鏈路層的面向連接的服務(wù)為網(wǎng)絡(luò)層提供了可靠的數(shù)據(jù)傳輸服務(wù)。面向連接的服務(wù)的數(shù)據(jù)傳輸要經(jīng)過3個(gè)不同

4、的階段：建立連接、數(shù)據(jù)傳輸和釋放連接。 第7頁，共56頁。3.1.3 數(shù)據(jù)鏈路層設(shè)計(jì)要點(diǎn)組幀與幀同步透明傳輸流量控制差錯(cuò)控制尋址 第8頁，共56頁。組幀與幀同步在數(shù)據(jù)鏈路層，數(shù)據(jù)傳送的基本單位是幀 。組幀主要是便于進(jìn)行錯(cuò)誤檢測(cè)和糾正，在某些情況下可提高傳輸效率。 幀同步是指接收端應(yīng)當(dāng)能從收到的比特流中準(zhǔn)確地區(qū)分出一幀的開始和結(jié)束的位置。網(wǎng)絡(luò)傳輸中很難保證計(jì)時(shí)的正確和一致（很難保證收發(fā)雙方的時(shí)鐘能精確一致），所以采用依靠時(shí)間或時(shí)間間隔關(guān)系來標(biāo)識(shí)一幀的開始和結(jié)束位置的方法顯然是不可行的。 第9頁，共56頁。常用的有4種幀同步方法 字節(jié)計(jì)數(shù)法 字符填充首尾定界法 比特填充首尾定界法 物理層違例編碼法

5、 第10頁，共56頁。透明傳輸透明傳輸就是不管所傳數(shù)據(jù)是什么樣的比特組合（字符型數(shù)據(jù)或二進(jìn)制數(shù)據(jù)），都應(yīng)當(dāng)能夠在鏈路上安全可靠地傳輸。 非透明傳輸舉例 字節(jié)填充法解決透明傳輸問題的示例比特填充法解決透明傳輸?shù)膯栴}示例第11頁，共56頁。流量控制流量控制實(shí)際上是對(duì)發(fā)送方數(shù)據(jù)流量的控制，使其發(fā)送速率不至于超過接收端的處理能力。 當(dāng)接收端來不及接收時(shí)，就必須及時(shí)控制發(fā)送端發(fā)送數(shù)據(jù)的速率，以使收發(fā)雙方達(dá)到匹配。 流量控制常用的方法有兩種。基于反饋的流量控制（Feedback-Based Flow Control） 基于速率的流量控制（Rate-Based Flow Control） 流量控制并不是數(shù)據(jù)

6、鏈路層特有的功能，許多高層協(xié)議也提供流量控制功能，只不過流量控制的對(duì)象不同而已。對(duì)于數(shù)據(jù)鏈路層來說，控制的是相鄰兩節(jié)點(diǎn)之間數(shù)據(jù)鏈路上的流量，而對(duì)于運(yùn)輸層來說，控制的則是從源主機(jī)到目的主機(jī)之間端對(duì)端的流量。第12頁，共56頁。差錯(cuò)控制前向糾錯(cuò)（Forward Error Correction, FEC）即接收方收到有差錯(cuò)的數(shù)據(jù)幀時(shí)能自動(dòng)將差錯(cuò)改正過來。這種方法的開銷較大，不適合于計(jì)算機(jī)網(wǎng)絡(luò)通信。 自動(dòng)請(qǐng)求重發(fā)(Automatic Repeat reQuest, ARQ) 即接收方如果檢測(cè)出收到的幀中有差錯(cuò)，就讓發(fā)送方重復(fù)發(fā)送這一幀，直到接收方正確收到這一幀為止。這種方法在計(jì)算機(jī)網(wǎng)絡(luò)通信中是最常用

7、的。 傳輸差錯(cuò)可分為兩大類：一類是比特差錯(cuò)；而另一類就是出現(xiàn)了幀丟失、幀重復(fù)或幀失序。 要解決這兩類傳輸差錯(cuò)問題，從而實(shí)現(xiàn)數(shù)據(jù)鏈路層的可靠傳輸，必須在差錯(cuò)檢測(cè)技術(shù)的基礎(chǔ)上，增加定時(shí)器、幀編號(hào)、確認(rèn)和重傳機(jī)制。目前因特網(wǎng)上廣泛使用的數(shù)據(jù)鏈路層協(xié)議已不再使用確認(rèn)和重傳機(jī)制了，即不提供向上的可靠傳輸服務(wù)了。 第13頁，共56頁。尋址 必須保證每一幀都能送到正確的目的站，接收方也應(yīng)知道發(fā)送方是哪個(gè)站。第14頁，共56頁。3.2 差錯(cuò)控制編碼技術(shù)3.2.1 奇偶校驗(yàn)碼3.2.2 循環(huán)冗余校驗(yàn)碼3.2.3 海明碼糾錯(cuò)碼（Error-Correcting Code）和檢錯(cuò)碼（Error-Detecting

8、Code）是實(shí)現(xiàn)差錯(cuò)檢測(cè)和糾正的兩種不同的差錯(cuò)控制編碼技術(shù)。糾錯(cuò)碼（Error-Correcting Code）和檢錯(cuò)碼各有優(yōu)缺點(diǎn)。比較常見的檢錯(cuò)碼主要有奇偶校驗(yàn)碼和循環(huán)冗余校驗(yàn)碼，常見的糾錯(cuò)碼主要有海明碼、正反碼等。第15頁，共56頁。3.2.1 奇偶校驗(yàn)碼奇偶校驗(yàn)碼是通過增加冗余位來使得碼字中“1”的個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）的編碼方法。 奇偶校驗(yàn)碼可分為垂直、水平、水平垂直奇偶校驗(yàn)等幾種方式 垂直偶校驗(yàn) 水平偶校驗(yàn) 水平垂直偶校驗(yàn) 第16頁，共56頁。3.2.2 循環(huán)冗余校驗(yàn)碼（Cyclic Redundancy Check, CRC） CRC又叫多項(xiàng)式編碼（polynomia

9、l code）基本思想是：將比特串看成是系數(shù)為0或1的多項(xiàng)式。一個(gè)k比特構(gòu)成的幀看作是一個(gè)k-1次多項(xiàng)式系數(shù)列表，該多項(xiàng)式共有k項(xiàng)，從xk-1到x0，這個(gè)多項(xiàng)式的最高階為k-1。如比特串110011共有6位，對(duì)應(yīng)一個(gè)共有6項(xiàng)的多項(xiàng)式，其系數(shù)分別為1、1、0、0、1和1，即x5+x4+x+1（1*x5+ 1*x4+ 0*x3+ 0*x2+ 1*x1+ 1*x0）。多項(xiàng)式的算術(shù)運(yùn)算采用模2運(yùn)算法則。按照它的運(yùn)算法則，加法不進(jìn)位，減法不借位，加法和減法兩者都與異或運(yùn)算相同，因而計(jì)算結(jié)果相同。CRC具有較強(qiáng)的檢錯(cuò)能力，可以檢測(cè)出所有的奇數(shù)位錯(cuò)、雙比特錯(cuò)、小于等于校驗(yàn)和長(zhǎng)度的突發(fā)錯(cuò)。 第17頁，共56頁

10、。CRC進(jìn)行編碼和校驗(yàn)的原理 (1) 發(fā)送方和接收方事先約定一個(gè)生成多項(xiàng)式G(x)，生成多項(xiàng)式的最高位和最低位必須是1。(2) 發(fā)送端根據(jù)生成多項(xiàng)式G(x)去計(jì)算要附加在信息幀尾部的冗余位（校驗(yàn)和，Checksum）。計(jì)算校驗(yàn)和的算法如下。 假設(shè)信息幀的比特?cái)?shù)為k位，對(duì)應(yīng)的多項(xiàng)式為K(x)，G(x)為r階。在信息幀的低位端加上r個(gè)0，此時(shí)信息幀的比特?cái)?shù)變?yōu)閗+r位，對(duì)應(yīng)的多項(xiàng)式為xrK(x)。 按模2除法，用對(duì)應(yīng)于G(x)的比特串去除對(duì)應(yīng)于xrK(x)的比特串，從而得到一個(gè)小于等于r位的余數(shù)。這個(gè)余數(shù)便可作為校驗(yàn)和。(3) 將校驗(yàn)和附加在k位信息幀尾部，組成一個(gè)新的幀，由發(fā)送端發(fā)送給接收端。假

11、設(shè)這個(gè)新的幀對(duì)應(yīng)的多項(xiàng)式為T(x)，其顯然能被G(x)除盡。因?yàn)檫@個(gè)新的幀的多項(xiàng)式T(x)所對(duì)應(yīng)的比特串可以看作是由多項(xiàng)式xrK(x)對(duì)應(yīng)的比特串減去余數(shù)而得到的。(4) 當(dāng)接收方收到帶有校驗(yàn)和的幀時(shí)，用G(x)去除它，如果余數(shù)不為0，則說明傳輸過程中出現(xiàn)了錯(cuò)誤；如果余數(shù)為0，則認(rèn)為傳輸無差錯(cuò)。第18頁，共56頁。發(fā)送端生成帶校驗(yàn)和的CRC幀的過程舉例信息幀1101011011生成多項(xiàng)式x4+ x+1第19頁，共56頁。3.2.3 海明碼海明碼是由R.Hamming在1950年首次提出的，是一種可以糾正一比特錯(cuò)的編碼。簡(jiǎn)單的奇偶校驗(yàn)中的一個(gè)重要的結(jié)論 信息位為k=n-1位an-1an-2a1，

12、加上一個(gè)偶校驗(yàn)位a0，構(gòu)成一個(gè)n位的碼字an-1an-2a1a0。在接收端校驗(yàn)時(shí)，可按關(guān)系式：S0=an-1+an-2+a1+a0（模2運(yùn)算）來計(jì)算，若S0=0，則認(rèn)為無錯(cuò)；若S0=1，則肯定有錯(cuò)。上面關(guān)系式稱為監(jiān)督關(guān)系式，S0稱為校正因子。 第20頁，共56頁。海明碼原理推導(dǎo)對(duì)上面結(jié)論的分析在上面偶校驗(yàn)情況下，只有一個(gè)監(jiān)督關(guān)系式，一個(gè)校正因子，其取值只有0或1兩種可能，分別代表了無錯(cuò)和有錯(cuò)兩種情況，但卻不能指出差錯(cuò)所在的位置。不難設(shè)想，如果增加冗余位，讓每個(gè)冗余位分別與信息中的某些位構(gòu)成一個(gè)偶校驗(yàn)關(guān)系，則就會(huì)相應(yīng)地增加監(jiān)督關(guān)系式和校正因子，就能區(qū)分更多的情況。 不難推出，信息位為k位，增加r

13、位冗余位，構(gòu)成n=k+r位碼字。若希望用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分無錯(cuò)和在碼字中的n個(gè)不同位置的1位錯(cuò)，則要求：2rn+1或2rk+r+1第21頁，共56頁。k=4時(shí)，海明碼產(chǎn)生基本原理示例 構(gòu)造S2S1S0取值與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系 也可以規(guī)定成另外的對(duì)應(yīng)關(guān)系，這并不影響討論的一般性 根據(jù)上表推出監(jiān)督關(guān)系式 令校正因子都等于零，代入已知信息位，計(jì)算出冗余位第22頁，共56頁。K=4時(shí)由信息位算得的冗余位 基于上面構(gòu)造的海明碼，可得到各種信息位與冗余位的對(duì)應(yīng)關(guān)系 第23頁，共56頁。海明碼糾正突發(fā)性錯(cuò)誤 海明碼只能糾正1位錯(cuò)，為了糾正在傳輸過程中出現(xiàn)的突發(fā)性錯(cuò)誤，可以采用如下的技巧或

14、方法。將k個(gè)連續(xù)的碼字排成一個(gè)矩陣，每行一個(gè)碼字，傳輸數(shù)據(jù)時(shí)每次發(fā)送一列，從左邊的列開始，如圖所示。第24頁，共56頁。海明碼生成方案海明碼是一種可以糾正一位差錯(cuò)的編碼。它是利用在信息位為k位，增加r個(gè)冗余位，構(gòu)成一個(gè)n=k+r位的碼字，然后用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分無錯(cuò)和在碼字中的n個(gè)不同位置的1位錯(cuò)。它必須滿足 2rn+1或2rk+r+1海明碼的生成方案主要有兩種，二者的主要區(qū)別是對(duì)冗余位在生成后的碼字中的位置處理方式不一樣。前面已經(jīng)介紹了第一種方案，它是將r個(gè)冗余位順序放在k個(gè)信息位的后面，另一種方案叫順序生成法，是將r個(gè)冗余位分別放在k+r位的碼字中位置（按位從右往左數(shù)）

15、為20到2r-1的那些位上，其余的用信息位來填充。第25頁，共56頁。海明碼的生成與接收過程(1) 假設(shè)信息位為k位，將k的值代入公式（2rk+r+1）計(jì)算出冗余位的個(gè)數(shù)r的取值范圍，從中選擇一個(gè)（通常會(huì)取最小的那一個(gè)），以方案一或順序生成法對(duì)r個(gè)冗余位進(jìn)行處理，構(gòu)造一個(gè)n=k+r的碼字。(2) 約定r個(gè)校正因子組成的二進(jìn)制序列Sr-1S1S0的取值與錯(cuò)碼的位置對(duì)應(yīng)關(guān)系（通常將其表示成表格的形式）。(3) 確定監(jiān)督關(guān)系式。(4) 令監(jiān)督關(guān)系式中所有的校正因子均為0，同時(shí)將信息位的值代入相應(yīng)的監(jiān)督關(guān)系式，從而計(jì)算出各冗余位的值。(5) 將信息位與冗余位組成的碼字發(fā)送給接收端。(6) 接收端將其收

16、到的碼字，利用監(jiān)督關(guān)系式進(jìn)行校驗(yàn)。如果Sr-1S1S0 =0，則表示沒有錯(cuò)誤。如果Sr-1S1S0不為0，則根據(jù)約定的Sr-1S1S0的取值與錯(cuò)碼的位置對(duì)應(yīng)關(guān)系確定出錯(cuò)碼的位置，對(duì)錯(cuò)碼位進(jìn)行取反，得到正確的碼字。第26頁，共56頁。3.3 數(shù)據(jù)鏈路層協(xié)議為了便于說明，采用一個(gè)簡(jiǎn)化的通信模型，把數(shù)據(jù)鏈路層以上的各層抽象為一個(gè)主機(jī)，而把物理層和傳輸媒體抽象成一條簡(jiǎn)單的鏈路。假設(shè)全雙工通信，則收發(fā)兩端要同時(shí)設(shè)有發(fā)送和接收緩沖區(qū)。 第27頁，共56頁。理想傳輸條件下的數(shù)據(jù)傳輸 所謂的理想傳輸條件是指滿足以下兩個(gè)假定的理想化狀態(tài)。(1) 鏈路是理想的傳輸信道，不會(huì)產(chǎn)生差錯(cuò)，數(shù)據(jù)幀傳輸過程中不會(huì)出錯(cuò)也不會(huì)

17、丟失。(2) 不管發(fā)送端以多快的速度發(fā)送數(shù)據(jù)幀，接收端總是來得及接收，并及時(shí)上交主機(jī)。在這樣的理想傳輸條件下，不需要采取任何措施就能實(shí)現(xiàn)可靠傳輸，即不需要任何數(shù)據(jù)鏈路層協(xié)議就可保證可靠傳輸。然而實(shí)際的網(wǎng)絡(luò)都不具備以上兩個(gè)理想條件 第28頁，共56頁。3.3 數(shù)據(jù)鏈路層協(xié)議3.3.1 簡(jiǎn)單的停止等待協(xié)議3.3.2 實(shí)用的停止等待協(xié)議3.3.3 連續(xù)ARQ協(xié)議3.3.4 選擇重傳ARQ協(xié)議3.3.5 滑動(dòng)窗口(Sliding Window)協(xié)議第29頁，共56頁。3.3.1 簡(jiǎn)單的停止等待協(xié)議簡(jiǎn)單的停止等待協(xié)議的工作原理假定鏈路是理想的傳輸信道，不會(huì)產(chǎn)生差錯(cuò)，數(shù)據(jù)幀傳輸過程中不會(huì)出錯(cuò)也不會(huì)丟失。在

18、發(fā)送端，每發(fā)送完一個(gè)數(shù)據(jù)幀就暫停發(fā)送，等待著接收端的確認(rèn)。如果收到了來自接收端的確認(rèn)幀，就繼續(xù)發(fā)送下一幀。在接收端每收到一個(gè)無差錯(cuò)的幀，就將其交給上層，并向發(fā)送端發(fā)送一個(gè)確認(rèn)幀。第30頁，共56頁。簡(jiǎn)單的停止等待協(xié)議算法 第31頁，共56頁。3.3.2 實(shí)用的停止等待協(xié)議實(shí)用的停止等待協(xié)議就是在理想傳輸條件的兩個(gè)假定都不成立的情況下，保證數(shù)據(jù)可靠傳輸?shù)囊环N協(xié)議。 在簡(jiǎn)單的停止等待協(xié)議中 通過引入“確認(rèn)”解決了流量控制問題，這種方法對(duì)于實(shí)用的停止等待協(xié)議同樣適用 。實(shí)用的停止等待協(xié)議還要處理數(shù)據(jù)幀在傳輸過程中出現(xiàn)的差錯(cuò)，主要包括數(shù)據(jù)幀出錯(cuò)、數(shù)據(jù)幀丟失、確認(rèn)幀丟失等幾種情況。 第32頁，共56頁。

19、數(shù)據(jù)幀出錯(cuò)時(shí)的兩種解決方法 為了進(jìn)行重傳，在發(fā)送端必須暫時(shí)保存已發(fā)送過的數(shù)據(jù)幀的副本，直到收到對(duì)已發(fā)送幀的確認(rèn)幀為止。當(dāng)通信質(zhì)量太差時(shí)，可能要進(jìn)行多次重傳，但當(dāng)重傳達(dá)到一定的次數(shù)后，應(yīng)立即停止，并向高層報(bào)告。超時(shí)定時(shí)器設(shè)置的超時(shí)時(shí)間應(yīng)仔細(xì)選擇確定。 第33頁，共56頁。兩種不同的幀丟失的解決方法 超時(shí)重傳與確認(rèn)幀丟失的使用可能會(huì)引入了新的問題-重復(fù)幀為解決重復(fù)幀的問題，引入了給數(shù)據(jù)幀編號(hào)的方法任何一個(gè)編號(hào)系統(tǒng)的序號(hào)所占用的比特?cái)?shù)一定是有限的，經(jīng)過一段時(shí)間后序號(hào)就會(huì)重復(fù)。 序號(hào)占用的比特?cái)?shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷就越小 第34頁，共56頁。實(shí)用的停止等待協(xié)議算法算法描述中，幾個(gè)參數(shù)的意義如下 V

20、(S)是發(fā)送端的狀態(tài)變量，用來對(duì)發(fā)送端將要發(fā)送的數(shù)據(jù)幀進(jìn)行編號(hào)；V(R)是接收端的狀態(tài)變量，用來表示接收端所期望接收到的數(shù)據(jù)幀的序號(hào)；N(S)是數(shù)據(jù)幀的幀編號(hào)。另外，對(duì)于數(shù)據(jù)幀出錯(cuò)的處理，是使用超時(shí)重傳的方法，而沒有采用向發(fā)送端發(fā)送否定確認(rèn)幀的方法。 第35頁，共56頁。在發(fā)送端(1) 從主機(jī)取一個(gè)數(shù)據(jù)幀。(2) V(S)取0（發(fā)送狀態(tài)變量V(S)初始化）。(3) 令N(S)等于V(S)（將發(fā)送狀態(tài)變量的數(shù)值寫入數(shù)據(jù)幀中的發(fā)送序號(hào)N(S)，將數(shù)據(jù)幀送交發(fā)送緩沖區(qū)）。(4) 將發(fā)送緩沖區(qū)中的數(shù)據(jù)幀發(fā)送出去（發(fā)送緩沖區(qū)中保留此數(shù)據(jù)幀的副本）。(5) 設(shè)置超時(shí)定時(shí)器（選擇適當(dāng)?shù)某瑫r(shí)時(shí)間）。(6) 等

21、待（等待以下步驟中的兩個(gè)事件中最先出現(xiàn)的一個(gè)）。(7) 收到確認(rèn)幀ACKn，若n=1-V(S)，則（接收方已經(jīng)正確接收了發(fā)送端發(fā)出的數(shù)據(jù)幀，并給出了確認(rèn)）從主機(jī)取一個(gè)新的數(shù)據(jù)幀；令V(S)等于“1-V(S)”（更新發(fā)送狀態(tài)變量，使用下一個(gè)序號(hào)）；轉(zhuǎn)到執(zhí)行步驟(3)。否則，丟棄這個(gè)確認(rèn)幀，轉(zhuǎn)到執(zhí)行步驟(6)。(8) 若超時(shí)定時(shí)器的時(shí)間到，則轉(zhuǎn)到執(zhí)行步驟(4)（重發(fā)數(shù)據(jù)幀）。第36頁，共56頁。在接收端(1) V(R)取0（接收狀態(tài)變量初始化，其數(shù)值等于欲接收的數(shù)據(jù)幀的序號(hào)）。(2) 等待。(3) 當(dāng)收到一個(gè)數(shù)據(jù)幀，檢查數(shù)據(jù)幀是否出錯(cuò)（通常使用CRC進(jìn)行檢測(cè)）。若檢查結(jié)果正確無誤，則轉(zhuǎn)到執(zhí)行步驟(

22、4)；否則，丟棄此數(shù)據(jù)幀，轉(zhuǎn)到步驟(2)；(4) 若N(S)=V(R)（收到了所期望的數(shù)據(jù)幀），將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交主機(jī)，轉(zhuǎn)到執(zhí)行步驟(5)。否則，丟棄此數(shù)據(jù)幀，然后轉(zhuǎn)到執(zhí)行步驟(6)；（丟棄的幀為重復(fù)的幀）。(5) 使V(R)等于1-V(R)（更新接收狀態(tài)變量，準(zhǔn)備接收下一個(gè)數(shù)據(jù)幀）。(6) 令n= V(R)，發(fā)送確認(rèn)幀ACKn，并轉(zhuǎn)到步驟(2)。（期望接收n號(hào)幀，在它之前的幀收到了）第37頁，共56頁。實(shí)用的停止等待協(xié)議算法要點(diǎn)(1) 發(fā)送端每發(fā)送一個(gè)數(shù)據(jù)幀，都要將發(fā)送狀態(tài)變量V(S)的值（0或1）寫到數(shù)據(jù)幀的發(fā)送序號(hào)N(S)上。只有收到已發(fā)送幀的確認(rèn)幀后，才能更新發(fā)送狀態(tài)變量V

23、 (S)（1變?yōu)?，或0變?yōu)?），并發(fā)送新的數(shù)據(jù)幀。(2) 接收端每接收到一個(gè)無差錯(cuò)的數(shù)據(jù)幀，就要將發(fā)送端在數(shù)據(jù)幀上設(shè)置的發(fā)送序號(hào)N(S)與本地的接收狀態(tài)變量V(R)進(jìn)行比較。若二者相等就表明是所期望的數(shù)據(jù)幀，就收下，并發(fā)送確認(rèn)。否則為重復(fù)幀，必須丟棄，但這時(shí)仍需要向發(fā)送端發(fā)送確認(rèn)幀ACKn，而接收狀態(tài)變量V(R)和確認(rèn)序號(hào)n都不變，即重發(fā)上次的確認(rèn)幀。(3) 發(fā)送端在發(fā)送完數(shù)據(jù)幀時(shí)，必須在其發(fā)送緩沖區(qū)中保留已發(fā)送數(shù)據(jù)幀的副本，以便在出現(xiàn)差錯(cuò)時(shí)進(jìn)行重發(fā)。只有在收到接收端發(fā)來的確認(rèn)幀，表示已經(jīng)正確接收數(shù)據(jù)幀時(shí)，才能清除這個(gè)副本。第38頁，共56頁。3.3.3 連續(xù)ARQ協(xié)議連續(xù)ARQ協(xié)議的工作要

24、點(diǎn)發(fā)送端每發(fā)送完一個(gè)數(shù)據(jù)幀后，不是停下來等待接收端的確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個(gè)數(shù)據(jù)幀。如果在此過程中收到了接收端發(fā)來的確認(rèn)幀，那么還可以繼續(xù)發(fā)送數(shù)據(jù)幀。由于減少了等待時(shí)間，整個(gè)通信的吞吐量就提高了。第39頁，共56頁。連續(xù)ARQ協(xié)議的工作原理示例注意：接收端只能按順序接收數(shù)據(jù)幀。 連續(xù)ARQ又稱為Go-back-N ARQ，意思是當(dāng)出現(xiàn)差錯(cuò)必須重傳時(shí)，要向回走N個(gè)幀，然后再開始重傳。 連續(xù)ARQ要求發(fā)送端的發(fā)送緩沖區(qū)必須能緩存多個(gè)數(shù)據(jù)幀，而接收端的緩沖區(qū)只需要能容納一個(gè)數(shù)據(jù)幀就足夠了。 數(shù)據(jù)幀丟失與數(shù)據(jù)幀出錯(cuò)時(shí)的情況是基本相同的。 數(shù)據(jù)幀的確認(rèn)幀丟失了，則情況較為復(fù)雜 。連續(xù)ARQ協(xié)議的

25、工作原理：數(shù)據(jù)幀出錯(cuò) 第40頁，共56頁。3.3.4 選擇重傳ARQ協(xié)議為了進(jìn)一步提高信道的利用率和傳輸效率，可以設(shè)法只重傳出錯(cuò)的數(shù)據(jù)幀或者是超時(shí)的數(shù)據(jù)幀。此時(shí)必須加大接收端的緩沖區(qū)使其能容納多個(gè)數(shù)據(jù)幀，以便接收端先緩存那些正確的數(shù)據(jù)幀（發(fā)送序號(hào)可能是不連續(xù)的），等到所缺序號(hào)的數(shù)據(jù)幀收到之后再一并送交主機(jī)。第41頁，共56頁。選擇重傳ARQ協(xié)議的工作原理示例選擇重傳ARQ協(xié)議可避免重傳那些本來已經(jīng)正確到達(dá)接收端的數(shù)據(jù)幀，但是必須付出的代價(jià)：在接收端需要設(shè)置具有相當(dāng)容量的緩存空間 數(shù)據(jù)幀的確認(rèn)幀丟失的情況較為復(fù)雜 選擇重傳ARQ協(xié)議示意圖：數(shù)據(jù)幀出錯(cuò) 第42頁，共56頁。3.3.5 滑動(dòng)窗口(S

26、liding Window)協(xié)議在使用連續(xù)ARQ協(xié)議時(shí)，如果發(fā)送端一直沒有收到對(duì)方的確認(rèn)，那么實(shí)際上發(fā)送端并不能無限制的發(fā)送數(shù)據(jù)幀，其原因如下。(1) 當(dāng)未被確認(rèn)的數(shù)據(jù)幀的數(shù)目太多時(shí)，只要有一幀出錯(cuò)或丟失，就會(huì)有很多的數(shù)據(jù)幀需要重傳，這必然浪費(fèi)很多時(shí)間，增大了開銷。(2) 為了對(duì)所發(fā)送的大量數(shù)據(jù)幀進(jìn)行編號(hào)，每個(gè)數(shù)據(jù)幀的發(fā)送序號(hào)也要占用較多的比特，這樣又增加了一些不必要的開銷。在連續(xù)ARQ協(xié)議中必須將已發(fā)送出去、但未被確認(rèn)的數(shù)據(jù)幀的數(shù)目加以限制，這就是滑動(dòng)窗口協(xié)議所要討論的內(nèi)容。第43頁，共56頁。發(fā)送窗口與接收窗口加入適當(dāng)?shù)目刂茩C(jī)制，循環(huán)使用已收到確認(rèn)的那些幀的序號(hào)，在發(fā)送端和接收端分別設(shè)定“

27、發(fā)送窗口”和“接收窗口”。 發(fā)送窗口用來對(duì)發(fā)送端進(jìn)行流量控制，而發(fā)送窗口的大小Ws代表在還沒有收到對(duì)方確認(rèn)的條件下發(fā)送端最多可以發(fā)送多少個(gè)數(shù)據(jù)幀。 接收窗口是為了控制哪些數(shù)據(jù)幀可以接收而哪些幀不可以接收。在接收端，只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。 只有在接收窗口旋轉(zhuǎn)（滑動(dòng)）時(shí)，發(fā)送窗口才有可能旋轉(zhuǎn)（滑動(dòng)）。但發(fā)送端如果沒有收到已發(fā)送的那些幀的任何確認(rèn)，同樣也不會(huì)旋轉(zhuǎn)（滑動(dòng)）。接收窗口保持不動(dòng)時(shí)，發(fā)送窗口無論如何也不會(huì)旋轉(zhuǎn)（滑動(dòng)），正因?yàn)槭瞻l(fā)兩端的窗口按照以上規(guī)律不斷旋轉(zhuǎn)（滑動(dòng)），因此這種協(xié)議被稱為滑動(dòng)窗口協(xié)議。 第44頁，共56頁?；瑒?dòng)窗口協(xié)議示例-3比特編號(hào)注

28、：可以用水平窗口和圓形窗口兩種方法來表示發(fā)送與接收窗口。發(fā)送端接收端第45頁，共56頁。發(fā)送窗口的最大值討論3個(gè)比特可編出8個(gè)不同的序號(hào)發(fā)送窗口的最大值似乎應(yīng)當(dāng)是8。其實(shí)不然，設(shè)置發(fā)送窗口為8將使協(xié)議在某些情況下無法工作。如圖(b)所示，發(fā)送窗口Ws=8將導(dǎo)致協(xié)議失敗 第46頁，共56頁。發(fā)送窗口應(yīng)滿足的約束關(guān)系如圖所示，采用3個(gè)比特供數(shù)據(jù)幀的序號(hào)使用，WS=6，WR=3。 根據(jù)當(dāng)前接收窗口的情況，只能推測(cè)發(fā)送端發(fā)送窗口的可能位置為 。接收端在收到一個(gè)數(shù)據(jù)幀時(shí)，必須在下列3種情況中做出正確無誤的選擇。(1) 是所期望接收的數(shù)據(jù)幀。(2) 是重復(fù)幀（已對(duì)此幀發(fā)過確認(rèn)幀，且已交付給主機(jī)）。 (3) 是序號(hào)錯(cuò)誤的超前幀。第47頁，共56頁。發(fā)送窗口應(yīng)滿足的約束關(guān)系（續(xù)）對(duì)于圖中的位置，應(yīng)要求在WS+WR的范圍內(nèi)無重復(fù)序號(hào)對(duì)于位置，要求在WS的范圍內(nèi)無重復(fù)序號(hào)對(duì)于位置，除了要求在WS的范圍內(nèi)無重復(fù)序號(hào)外,還要求發(fā)送端重發(fā)的那些數(shù)據(jù)幀的序號(hào)不能與WR的范圍內(nèi)的序號(hào)重復(fù)綜合以上3種要求可知，當(dāng)用n個(gè)比特進(jìn)行編號(hào)時(shí)，發(fā)送窗口的大小WS和接收窗口的大小WR必須滿足WS+WR2n (3-1)對(duì)于停止等待協(xié)議，WS=1，WR=1，根據(jù)公式(3-1)可知n1 對(duì)于連續(xù)ARQ協(xié)議，WR=1，根據(jù)公式(3-1)可得出WS2n-1，所以發(fā)送窗口的取值范圍為11，WR1，WS+WR2n。