數(shù)據(jù)鏈路層課件

計(jì)算機(jī)網(wǎng)絡(luò)

ComputerNetwork2023年1月2日計(jì)算機(jī)網(wǎng)絡(luò)

ComputerNetwork2022年12課程目錄第1章 概述第2章 物理層與數(shù)據(jù)通信基礎(chǔ)第3章 數(shù)據(jù)鏈路層第4章 局域網(wǎng)第5章 網(wǎng)絡(luò)層第6章 網(wǎng)絡(luò)互聯(lián)技術(shù)第7章 傳輸層第8章 應(yīng)用層第9章 網(wǎng)絡(luò)管理與信息安全第10章 網(wǎng)絡(luò)新技術(shù)專題2計(jì)算機(jī)網(wǎng)絡(luò)課程目錄第1章 概述2計(jì)算機(jī)網(wǎng)絡(luò)本章提綱3.1 數(shù)據(jù)鏈路層的功能3.2 差錯(cuò)檢測(cè)和校正3.3 數(shù)據(jù)鏈路層協(xié)議3.4 協(xié)議描述與驗(yàn)證3.5 數(shù)據(jù)鏈路層協(xié)議舉例第3章 數(shù)據(jù)鏈路層3計(jì)算機(jī)網(wǎng)絡(luò)本章提綱3.1 數(shù)據(jù)鏈路層的功能第3章 數(shù)據(jù)鏈路層3計(jì)算3.1 數(shù)據(jù)鏈路層的功能

3.1.1幀同步3.1.2差錯(cuò)控制3.1.3流量控制3.1.4鏈路管理4計(jì)算機(jī)網(wǎng)絡(luò)3.1 數(shù)據(jù)鏈路層的功能3.1.1幀同步4計(jì)算機(jī)網(wǎng)絡(luò)3.1.1幀同步

幀同步：能從比特流中區(qū)分出幀的起始與終止。1、字節(jié)計(jì)數(shù)法以一個(gè)特殊字符表征一幀的起始，并以一個(gè)專門(mén)字段來(lái)標(biāo)明幀內(nèi)的字節(jié)數(shù)。2、使用字符填充的首尾定界符法用一些特定的字符來(lái)定界一幀的起始與終止。

數(shù)據(jù)的透明性3、使用比特填充的首尾定界符法以一組特定的比特模式(如01111110)來(lái)標(biāo)志一幀的起始與終止。數(shù)據(jù)的透明性4、違法編碼法借用違法編碼序列來(lái)定界幀的起始與終止。

5計(jì)算機(jī)網(wǎng)絡(luò)3.1.1幀同步幀同步：能從比特流中區(qū)分出幀的起始與終止3.1.2差錯(cuò)控制通信系統(tǒng)必須具備發(fā)現(xiàn)(即檢測(cè))差錯(cuò)的能力，并采取措施糾正它，使差錯(cuò)控制在所能允許的盡可能小的范圍內(nèi)，這就是差錯(cuò)控制過(guò)程，也是數(shù)據(jù)鏈路層的主要功能之一。反饋重發(fā)計(jì)時(shí)器幀序號(hào)6計(jì)算機(jī)網(wǎng)絡(luò)3.1.2差錯(cuò)控制通信系統(tǒng)必須具備發(fā)現(xiàn)(即檢測(cè))差錯(cuò)的能3.1.3流量控制流量控制并不是數(shù)據(jù)鏈路層特有的功能，許多高層協(xié)議中也提供流量控制功能，只不過(guò)流量控制的對(duì)象不同而已。流量控制實(shí)際上是對(duì)發(fā)送方數(shù)據(jù)流量的控制，使其發(fā)送速率不超過(guò)接收方的接收速率。7計(jì)算機(jī)網(wǎng)絡(luò)3.1.3流量控制流量控制并不是數(shù)據(jù)鏈路層特有的功能，3.1.4鏈路管理

鏈路管理功能主要是用于面向連接的服務(wù)。數(shù)據(jù)鏈路層連接的建立、維持和釋放就稱做鏈路管理。8計(jì)算機(jī)網(wǎng)絡(luò)3.1.4鏈路管理鏈路管理功能主要是用于面向連接的服務(wù)。3.2 差錯(cuò)檢測(cè)和校正

3.2.1傳輸差錯(cuò)的特性3.2.2奇偶校驗(yàn)3.2.3循環(huán)冗余校驗(yàn)3.2.4海明碼9計(jì)算機(jī)網(wǎng)絡(luò)3.2 差錯(cuò)檢測(cè)和校正3.2.1傳輸差錯(cuò)的特性9計(jì)算機(jī)3.2.1傳輸差錯(cuò)的特性傳輸中的差錯(cuò)都是由于噪聲引起的。噪聲有兩大類：一類是信道所固有的、持續(xù)存在的隨機(jī)熱噪聲；另一類是由于外界特定的短暫原因所造成的沖擊噪聲。誤碼率編碼效率差錯(cuò)控制的方式：自動(dòng)請(qǐng)求重發(fā)（AutomaticReQuestforRepeat，ARQ）前向糾錯(cuò)(ForwardErrorCorrection，F(xiàn)EC)10計(jì)算機(jī)網(wǎng)絡(luò)3.2.1傳輸差錯(cuò)的特性傳輸中的差錯(cuò)都是由于噪聲引起的。噪3.2.2奇偶校驗(yàn)(1/2)奇偶校驗(yàn)的特點(diǎn)：奇偶校驗(yàn)碼是一種通過(guò)增加冗余位使得碼字中“1”的個(gè)數(shù)恒為奇數(shù)或偶數(shù)的編碼方法,它是一種檢錯(cuò)碼。偶校驗(yàn):ri=I1i⊕I2i⊕…⊕Ipi奇校驗(yàn):ri=I1i⊕I2i⊕…⊕Ipi⊕1奇偶校驗(yàn)的分類：垂直奇偶校驗(yàn)

編碼效率R=p/(p+1)

11計(jì)算機(jī)網(wǎng)絡(luò)3.2.2奇偶校驗(yàn)(1/2)奇偶校驗(yàn)的特點(diǎn)：11計(jì)算機(jī)網(wǎng)絡(luò)3.2.2奇偶校驗(yàn)(2/2)水平奇偶校驗(yàn)編碼效率R=q/(q+1)

水平垂直奇偶校驗(yàn)編碼效率R=pq/(p+1)(q+1)12計(jì)算機(jī)網(wǎng)絡(luò)3.2.2奇偶校驗(yàn)(2/2)水平奇偶校驗(yàn)12計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(1/3)它是一種檢錯(cuò)碼。思想：任何一個(gè)由二進(jìn)制數(shù)位串組成的代碼都可以和一個(gè)只含0和1兩個(gè)系數(shù)的多項(xiàng)式建立一一對(duì)應(yīng)的關(guān)系。k位信息位對(duì)應(yīng)于一個(gè)k-1次多項(xiàng)式K(x)，r位冗余位對(duì)應(yīng)于一個(gè)r-1次多項(xiàng)式R(x)，生成的n=k+r位碼字則對(duì)應(yīng)于一個(gè)n-1次多項(xiàng)式T(x)。生成方法：發(fā)送方和接收方依據(jù)一事先約定的r次生成多項(xiàng)式G(x)（最高項(xiàng)xr和最低項(xiàng)的系數(shù)為1），用G(x)去除xrK(x)得到的余式就是R(x)，即得冗余位。13計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(1/3)它是一種檢錯(cuò)碼。13計(jì)算機(jī)3.2.3循環(huán)冗余校驗(yàn)(2/3)示例設(shè)信息位為1010001，即K(x)=x6+x4+1，取G(x)=x4+x2+x+1（對(duì)應(yīng)的代碼為10111），則x4K(x)=x10+x8+x4（對(duì)應(yīng)的代碼為10100010000），則所以冗余位為1101，

R(x)=x3+x2+1。T(X)=x4K(x)+R(x)=x10+x8+x4+

x3+x2+1

對(duì)應(yīng)的發(fā)送代碼為：1010001110114計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(2/3)示例設(shè)信息位為101003.2.3循環(huán)冗余校驗(yàn)(3/3)檢測(cè)方法：用發(fā)送端發(fā)送時(shí)采用的生成多項(xiàng)式G(x)來(lái)除接收到的碼字多項(xiàng)式，若余式不為0，則傳輸有差錯(cuò)；否則，認(rèn)為傳輸無(wú)差錯(cuò)。15計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(3/3)檢測(cè)方法：用發(fā)送端發(fā)送時(shí)采3.2.4海明碼(1/3)也是一種可以糾正一位差錯(cuò)的編碼。對(duì)于奇偶校驗(yàn)碼，若信息位為an-1an-2…a1，加上一位偶校驗(yàn)位a0，在接收端校驗(yàn)時(shí)，可按關(guān)系式

S=

an-1

⊕

an-2

⊕

…⊕a0來(lái)計(jì)算，若S=0，則無(wú)錯(cuò)；若S=1，則有錯(cuò)。上式稱為監(jiān)督關(guān)系式，S稱為校正因子。思想：增加冗余位，也相應(yīng)地增加監(jiān)督關(guān)系式和校正因子，就能表示更多的差錯(cuò)情況，包括具體定出是哪一位出錯(cuò)。理論依據(jù)：當(dāng)信息位為k位，增加r個(gè)冗余位，構(gòu)成n=k+r位碼字。若希望用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來(lái)區(qū)分無(wú)錯(cuò)和在碼字中n個(gè)不同的位置的一位錯(cuò)，則要求：2r≥k+r+1。16計(jì)算機(jī)網(wǎng)絡(luò)3.2.4海明碼(1/3)也是一種可以糾正一位差錯(cuò)的編碼。3.2.4海明碼(2/3)生成過(guò)程：（假設(shè)k=4，則r取3，信息位a6a5a4a3，冗余位a2a1a0）（1）構(gòu)造監(jiān)督關(guān)系式表（2）寫(xiě)出監(jiān)督關(guān)系式由上表可知，a2、a4、a5

或a6的一位錯(cuò)都應(yīng)使S2=1，所以

S2=a2⊕

a4

⊕

a5

⊕a6

同理

S1=a1⊕

a3

⊕

a5⊕a6

S0=a0⊕

a3⊕

a4⊕a6S2S1S0000001010100011101110111錯(cuò)碼位置無(wú)錯(cuò)a0錯(cuò)a1錯(cuò)a2錯(cuò)a3錯(cuò)a4錯(cuò)a5錯(cuò)a6錯(cuò)17計(jì)算機(jī)網(wǎng)絡(luò)3.2.4海明碼(2/3)生成過(guò)程：（假設(shè)k=4，則r取33.2.4海明碼(3/3)（3）求出冗余位關(guān)系式令S0、S1

和S2為0，即可求出a0、a1和a2：

a2=

a4⊕

a5⊕a6

a1=

a3⊕

a5⊕a6

a0=

a3⊕

a4⊕a6

示例（P69表3.2）糾錯(cuò)（P68）特點(diǎn)：（1）編碼效率為k/k+r（上例4/7）；（2）較容易實(shí)現(xiàn)，但只能糾正1位錯(cuò)。18計(jì)算機(jī)網(wǎng)絡(luò)3.2.4海明碼(3/3)（3）求出冗余位關(guān)系式18計(jì)算機(jī)3.3 數(shù)據(jù)鏈路層協(xié)議

3.3.1基本鏈路控制協(xié)議3.3.2滑動(dòng)窗口協(xié)議19計(jì)算機(jī)網(wǎng)絡(luò)3.3 數(shù)據(jù)鏈路層協(xié)議3.3.1基本鏈路控制協(xié)議193.3.1基本鏈路控制協(xié)議(1/8)

ARQ（AutomaticRepeatQuest，自動(dòng)重發(fā)請(qǐng)求，也稱“循環(huán)自動(dòng)請(qǐng)求”）協(xié)議是數(shù)據(jù)鏈路層最基本的協(xié)議。它是指在接收站接收到一個(gè)包含出錯(cuò)數(shù)據(jù)的信息（幀）時(shí)，自動(dòng)發(fā)出一個(gè)重傳錯(cuò)幀的請(qǐng)求。

ARQ的作用原則是對(duì)出錯(cuò)的數(shù)據(jù)幀自動(dòng)重發(fā)，它有三種形式：停等ARQ協(xié)議連續(xù)ARQ協(xié)議選擇重傳ARQ協(xié)議

20計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(1/8)ARQ（Automa3.3.1基本鏈路控制協(xié)議(2/8)

1、理想情況下的主機(jī)通信：完全理想化的數(shù)據(jù)傳輸要基于以下兩個(gè)假定：假定1—鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。假定2—不管發(fā)送方以多快的速率發(fā)送數(shù)據(jù)，接收方總是來(lái)得及收下，并及時(shí)上交主機(jī)。數(shù)據(jù)鏈路層不需要協(xié)議就可以保證數(shù)據(jù)傳輸?shù)恼_。21計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(2/8)1、理想情況下的主機(jī)3.3.1基本鏈路控制協(xié)議(3/8)

2、停等ARQ協(xié)議：工作原理發(fā)送方發(fā)送一個(gè)數(shù)據(jù)幀后，必須停下來(lái)等待接收方的確認(rèn)幀后才可以發(fā)送下一個(gè)數(shù)據(jù)幀；在接收方接收錯(cuò)誤時(shí)，接收方則發(fā)一否認(rèn)幀，要求發(fā)送方重發(fā)該幀；為防止發(fā)送的數(shù)據(jù)丟失，發(fā)送方內(nèi)部設(shè)置一個(gè)定時(shí)器，當(dāng)超過(guò)定時(shí)時(shí)間，而發(fā)送方仍未收到確認(rèn)幀時(shí)，發(fā)送方重發(fā)該幀；為防止確認(rèn)幀丟失而造成發(fā)送方重發(fā)同一數(shù)據(jù)幀，發(fā)送方給每一個(gè)數(shù)據(jù)幀帶上一個(gè)序列號(hào)。22計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(3/8)2、停等ARQ協(xié)議：3.3.1基本鏈路控制協(xié)議(4/8)

停等ARQ協(xié)議的缺點(diǎn)：停等ARQ協(xié)議雖然保證了傳輸?shù)陌踩煽?，但在傳輸過(guò)程中信道的吞吐量太低。23計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(4/8)停等ARQ協(xié)議的缺點(diǎn)3.3.1基本鏈路控制協(xié)議(5/8)

3、連續(xù)ARQ協(xié)議：工作原理連續(xù)ARQ是連續(xù)發(fā)送若干數(shù)據(jù)幀，如果發(fā)送方接收到接收端發(fā)回的確認(rèn)幀，則繼續(xù)發(fā)送；發(fā)送方在每發(fā)完一個(gè)數(shù)據(jù)幀后，就啟動(dòng)內(nèi)部超時(shí)定時(shí)器，在設(shè)置的超時(shí)時(shí)間內(nèi)未收到確認(rèn)幀，則重發(fā)相應(yīng)的數(shù)據(jù)幀。連續(xù)ARQ協(xié)議的工作示意圖：24計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(5/8)3、連續(xù)ARQ協(xié)議：3.3.1基本鏈路控制協(xié)議(6/8)

連續(xù)ARQ協(xié)議的缺點(diǎn)：連續(xù)ARQ協(xié)議一方面因連續(xù)發(fā)送數(shù)據(jù)幀而提高了效率，但另一方面，在重傳時(shí)又必須把原來(lái)已正確傳送過(guò)的數(shù)據(jù)幀進(jìn)行重傳（但僅因這些數(shù)據(jù)幀之前有一個(gè)數(shù)據(jù)幀出了錯(cuò)），這樣又使傳送速率降低。由此可見(jiàn)，若傳輸信道的傳輸質(zhì)量很差而誤碼率較大時(shí)，連續(xù)ARQ協(xié)議不一定優(yōu)于停等ARQ協(xié)議。25計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(6/8)連續(xù)ARQ協(xié)議的缺點(diǎn)3.3.1基本鏈路控制協(xié)議(7/8)

4、選擇重傳ARQ協(xié)議：工作原理當(dāng)接收方發(fā)現(xiàn)某幀出錯(cuò)后，其后繼續(xù)送來(lái)的正確幀雖然不能立即遞交給接收方的高層，但接收方仍可收下來(lái)，存放在一個(gè)緩沖區(qū)中，同時(shí)要求發(fā)送方重新傳送出錯(cuò)的那一幀。一旦收到重新傳來(lái)的幀后，就可以與原來(lái)已存于緩沖區(qū)中的其余幀一并按正確的順序遞交高層。

選擇重傳ARQ協(xié)議的缺點(diǎn)：選擇重發(fā)減少了浪費(fèi)，但要求接收方有足夠大的緩沖區(qū)空間，這在許多情況下是不夠經(jīng)濟(jì)的。正因如此，選擇重傳ARQ協(xié)議在目前就遠(yuǎn)沒(méi)有連續(xù)重傳ARQ協(xié)議使用得那么廣泛。今后存儲(chǔ)器芯片的價(jià)格會(huì)更加便宜，選擇重傳ARQ協(xié)議還是有可能受到更多的重視。26計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(7/8)4、選擇重傳ARQ協(xié)3.3.1基本鏈路控制協(xié)議(8/8)

選擇重傳ARQ協(xié)議的工作示意圖：以上三種重傳方法各有利弊，停等ARQ協(xié)議最簡(jiǎn)單，但信道利用率最低；選擇重傳ARQ協(xié)議信道利用率最高，但它要求接收端的緩沖容量相當(dāng)大；連續(xù)ARQ協(xié)議介于兩者之間。在應(yīng)用中應(yīng)根據(jù)實(shí)際情況選擇。27計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(8/8)選擇重傳ARQ協(xié)議的1、XON/XOFF在流量控制方面，可以從不同側(cè)面采取不同的控制方案。最簡(jiǎn)單的方法就是增加接收端的緩沖存儲(chǔ)空間，使得接收端可以緩存更多的數(shù)據(jù)。但這只是一種被動(dòng)、消極的方法。因?yàn)?，一方面系統(tǒng)不允許開(kāi)設(shè)過(guò)大的緩沖空間；另一方面對(duì)于速率則顯著失效，而且在傳送大量數(shù)據(jù)的場(chǎng)合下，即使緩存空間再大也會(huì)出現(xiàn)不夠的現(xiàn)象。目前普遍采取一種稱之為“XON/XOFF”的發(fā)送控制字符的方案，通過(guò)控制字符來(lái)確定發(fā)送方是否繼續(xù)發(fā)送數(shù)據(jù)，相比之下更主動(dòng)、更積極、更有效。3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(1/4)

28計(jì)算機(jī)網(wǎng)絡(luò)1、XON/XOFF3.3.2XON/XOFF方案和滑動(dòng)窗XON/XOFF的通信原理：XON/XOFF是一種異步通信協(xié)議，接收設(shè)備或計(jì)算機(jī)使用特殊字符來(lái)控制發(fā)送設(shè)備或計(jì)算機(jī)傳送的數(shù)據(jù)流。當(dāng)接收計(jì)算機(jī)不能繼續(xù)接收數(shù)據(jù)時(shí)，發(fā)送一個(gè)XOFF控制字符告訴發(fā)送方停止傳送；當(dāng)傳輸可以恢復(fù)時(shí)，該計(jì)算機(jī)發(fā)送一個(gè)XON字符來(lái)通知發(fā)送方。3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(2/4)

29計(jì)算機(jī)網(wǎng)絡(luò)XON/XOFF的通信原理：3.3.2XON/XOFF方2、滑動(dòng)窗口協(xié)議滑動(dòng)窗口協(xié)議屬異步雙工傳輸模式。協(xié)議基本內(nèi)容：發(fā)送的信息幀都有一個(gè)序號(hào)，從0到某個(gè)最大值，0～2n－1，一般用n個(gè)二進(jìn)制位表示；發(fā)送端始終保持一個(gè)已發(fā)送但尚未確認(rèn)的幀的序號(hào)表，稱為發(fā)送窗口。發(fā)送窗口的上界表示要發(fā)送的下一個(gè)幀的序號(hào)，下界表示未得到確認(rèn)的幀的最小編號(hào)。發(fā)送窗口大小=上界-下界，大小可變。發(fā)送端每發(fā)送一個(gè)幀，序號(hào)取上界值，上界加1；每接收到一個(gè)正確響應(yīng)幀，下界加1。接收端有一個(gè)接收窗口，大小固定，但不一定與發(fā)送窗口相同。接收窗口的上界表示允許接收的序號(hào)最大的幀，下界表示希望接收的幀。接收窗口容納允許接收的信息幀，落在窗口外的幀均被丟棄。序號(hào)等于下界的幀被正確接收，并產(chǎn)生一個(gè)響應(yīng)幀，上界、下界都加1。接收窗口大小不變。

3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(3/4)

30計(jì)算機(jī)網(wǎng)絡(luò)2、滑動(dòng)窗口協(xié)議3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(4/4)

主要的滑動(dòng)窗口協(xié)議：1比特滑動(dòng)窗口協(xié)議（停等協(xié)議）退后n幀協(xié)議選擇重傳協(xié)議滑動(dòng)窗口協(xié)議的工作原理示意圖：31計(jì)算機(jī)網(wǎng)絡(luò)3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(4/4)主3.4 協(xié)議描述與驗(yàn)證

3.4.1有限狀態(tài)機(jī)模型3.4.2Petri網(wǎng)模型32計(jì)算機(jī)網(wǎng)絡(luò)3.4 協(xié)議描述與驗(yàn)證3.4.1有限狀態(tài)機(jī)模型323.4.1有限狀態(tài)機(jī)模型

有限狀態(tài)機(jī)（FiniteStateMachine，F(xiàn)SM）是一種用來(lái)描述系統(tǒng)的常用方法。在這個(gè)模型中，系統(tǒng)被描述成有限的狀態(tài)，在一定的前提條件下會(huì)發(fā)生一系列的輸入事件，這些事件使得系統(tǒng)采取相應(yīng)的動(dòng)作，并從一個(gè)狀態(tài)轉(zhuǎn)換成另一個(gè)狀態(tài)，稱為狀態(tài)的變遷或轉(zhuǎn)換（Transition）。33計(jì)算機(jī)網(wǎng)絡(luò)3.4.1有限狀態(tài)機(jī)模型有限狀態(tài)機(jī)（FiniteSt3.4.2Petri網(wǎng)模型

Petri網(wǎng)是由德國(guó)學(xué)者C.A.Petri首先提出的一種描述方法,它本質(zhì)上也是一種有限狀態(tài)機(jī)模型。Petri網(wǎng)的描述中有四種基本元素：位置(Place)—位置是一圓圈，表示可能進(jìn)入的狀態(tài)標(biāo)記(Token)—位置中的小圓黑點(diǎn)，某個(gè)位置中有標(biāo)記就表示已處于該狀態(tài)變遷(Transition)—用一根直線段來(lái)表示,指明了該變遷發(fā)生的條件帶箭頭的弧線(Arc)—用弧線來(lái)表示,指明變遷產(chǎn)生的條件和變遷產(chǎn)生的結(jié)果34計(jì)算機(jī)網(wǎng)絡(luò)3.4.2Petri網(wǎng)模型Petri網(wǎng)是由德國(guó)學(xué)者C.3.5 數(shù)據(jù)鏈路層協(xié)議舉例

3.5.1數(shù)據(jù)鏈路層協(xié)議的分類3.5.2HDLC3.5.3SLIP和PPP35計(jì)算機(jī)網(wǎng)絡(luò)3.5 數(shù)據(jù)鏈路層協(xié)議舉例3.5.1數(shù)據(jù)鏈路層協(xié)議的3.5.1數(shù)據(jù)鏈路層協(xié)議的分類鏈路控制協(xié)議的分類：異步協(xié)議—以字符為獨(dú)立的信息傳輸單位，在每個(gè)字符的起始處開(kāi)始對(duì)字符內(nèi)的比特實(shí)現(xiàn)同步，但字符與字符之間的間隔時(shí)間是不固定的(即字符之間是異步的)同步協(xié)議—以許多字符或許多比特組織成的數(shù)據(jù)塊----幀為傳輸單位，在幀的起始處同步，使幀內(nèi)維持固定的時(shí)鐘。同步協(xié)議的分類：面向字符的同步協(xié)議

面向比特的同步協(xié)議面向字節(jié)計(jì)數(shù)的同步協(xié)議36計(jì)算機(jī)網(wǎng)絡(luò)3.5.1數(shù)據(jù)鏈路層協(xié)議的分類鏈路控制協(xié)議的分類：36計(jì)3.5.2HDLC(1/2)

1、HDLC的操作方式：所謂操作方式，通俗地講就是某站點(diǎn)是以主站點(diǎn)方式操作還是以從站方式操作，或者是二者兼?zhèn)洹?/p>

HDLC操作方式的類型：正常響應(yīng)方式NRM(NormaResponsesMode)—這是一非平衡數(shù)據(jù)鏈路方式，有時(shí)也稱非平衡正常響應(yīng)方式，傳輸過(guò)程由主站啟動(dòng)。異步響應(yīng)方式ARM(AsynchronousResponsesMode)—這也是一種非平衡數(shù)據(jù)鏈路操作方式，與NRM不同的是，ARM下的傳輸過(guò)程由從站啟動(dòng)。

異步平衡方式ABM(AsynchronousBalancedMode)—這是一種允許任何節(jié)點(diǎn)來(lái)啟動(dòng)傳輸?shù)牟僮鞣绞?。為了提高鏈路傳輸效率，?jié)點(diǎn)之間在兩個(gè)方向上都需要有較高的信息傳輸量。37計(jì)算機(jī)網(wǎng)絡(luò)3.5.2HDLC(1/2)1、HDLC的操作方式：3.5.2HDLC(2/2)

2、HDLC的幀格式：3、HDLC的幀類型：信息幀(I幀)—信息幀用于傳送有效信息或數(shù)據(jù)，通常簡(jiǎn)稱I幀。監(jiān)控幀(S幀)—監(jiān)控幀用于差錯(cuò)控制和流量控制，通常簡(jiǎn)稱S幀。無(wú)編號(hào)幀(U幀)—無(wú)編號(hào)幀因其控制字段中不包含編號(hào)N(S)和N(R)而得名，簡(jiǎn)稱U幀。U幀用于提供對(duì)鏈路的建立、拆除以及多種控制功能。

38計(jì)算機(jī)網(wǎng)絡(luò)3.5.2HDLC(2/2)2、HDLC的幀格式：3.5.3SLIP和PPP(1/4)

用戶接入Internet的常用方法：使用撥號(hào)電話線接入Internet使用專線接入

SLIP：串行線路SLIP（SerialLineInternetProtocol，SLIP）用于運(yùn)行TCP/IP協(xié)議的面向字符的點(diǎn)對(duì)點(diǎn)串行連接，早在1984年就已經(jīng)開(kāi)始使用。

SLIP通常專門(mén)用于串行連接，有時(shí)候也用于撥號(hào)，使用的線路速率一般介于1200bit/s和19.2Kbit/s之間。主要用與低速的交互性業(yè)務(wù)。SLIP允許主機(jī)和路由器混合連接通信（主機(jī)-主機(jī)、主機(jī)-路由器、路由器-路由器都是SLIP網(wǎng)絡(luò)通用的配置），因而非常有用。39計(jì)算機(jī)網(wǎng)絡(luò)3.5.3SLIP和PPP(1/4)用戶接入Inte3.5.3SLIP和PPP(2/4)

SLIP協(xié)議的缺點(diǎn)：SLIP沒(méi)有差錯(cuò)檢測(cè)的功能。通信的每一方必須事先知道對(duì)方的IP地址，這對(duì)撥號(hào)入網(wǎng)的用戶是很不方便的。SLIP僅支持IP，而不支持其他的協(xié)議。SLIP并未成為Internet的標(biāo)準(zhǔn)協(xié)議。因此目前存在著多種互不兼容的版本，影響了不同網(wǎng)絡(luò)的互聯(lián)。

40計(jì)算機(jī)網(wǎng)絡(luò)3.5.3SLIP和PPP(2/4)SLIP協(xié)議的缺3.5.3SLIP和PPP(3/4)

PPP協(xié)議的三部分：一個(gè)將IP數(shù)據(jù)報(bào)封裝到串行鏈路的方法。PPP既支持異步鏈路（無(wú)奇偶校驗(yàn)的8比特?cái)?shù)據(jù)），也支持面向比特的同步鏈路。一個(gè)用來(lái)建立、配置和測(cè)試數(shù)據(jù)鏈路連接的鏈路控制協(xié)議LCP（LinkControlProtocol），通信的雙方可協(xié)商一些選項(xiàng)。一套網(wǎng)絡(luò)控制協(xié)議NCP（NetworkControlProtocol），支持不同的網(wǎng)絡(luò)層協(xié)議，如IP、OSI的網(wǎng)絡(luò)層、DECnet及AppleTalk。41計(jì)算機(jī)網(wǎng)絡(luò)3.5.3SLIP和PPP(3/4)PPP協(xié)議的三部3.5.3SLIP和PPP(4/4)

PPP協(xié)議的幀格式：PPP協(xié)議的特點(diǎn)：PPP協(xié)議是面向字符型的，所以它不能采用HDLC所使用的零比特插入法，而是使用一種特殊的字符填充。PPP不使用序號(hào)和確認(rèn)，因此，PPP不提供可靠傳輸?shù)姆?wù)。

42計(jì)算機(jī)網(wǎng)絡(luò)3.5.3SLIP和PPP(4/4)PPP協(xié)議的幀格計(jì)算機(jī)網(wǎng)絡(luò)

ComputerNetwork2023年1月2日計(jì)算機(jī)網(wǎng)絡(luò)

ComputerNetwork2022年12課程目錄第1章 概述第2章 物理層與數(shù)據(jù)通信基礎(chǔ)第3章 數(shù)據(jù)鏈路層第4章 局域網(wǎng)第5章 網(wǎng)絡(luò)層第6章 網(wǎng)絡(luò)互聯(lián)技術(shù)第7章 傳輸層第8章 應(yīng)用層第9章 網(wǎng)絡(luò)管理與信息安全第10章 網(wǎng)絡(luò)新技術(shù)專題44計(jì)算機(jī)網(wǎng)絡(luò)課程目錄第1章 概述2計(jì)算機(jī)網(wǎng)絡(luò)本章提綱3.1 數(shù)據(jù)鏈路層的功能3.2 差錯(cuò)檢測(cè)和校正3.3 數(shù)據(jù)鏈路層協(xié)議3.4 協(xié)議描述與驗(yàn)證3.5 數(shù)據(jù)鏈路層協(xié)議舉例第3章 數(shù)據(jù)鏈路層45計(jì)算機(jī)網(wǎng)絡(luò)本章提綱3.1 數(shù)據(jù)鏈路層的功能第3章 數(shù)據(jù)鏈路層3計(jì)算3.1 數(shù)據(jù)鏈路層的功能

3.1.1幀同步3.1.2差錯(cuò)控制3.1.3流量控制3.1.4鏈路管理46計(jì)算機(jī)網(wǎng)絡(luò)3.1 數(shù)據(jù)鏈路層的功能3.1.1幀同步4計(jì)算機(jī)網(wǎng)絡(luò)3.1.1幀同步

幀同步：能從比特流中區(qū)分出幀的起始與終止。1、字節(jié)計(jì)數(shù)法以一個(gè)特殊字符表征一幀的起始，并以一個(gè)專門(mén)字段來(lái)標(biāo)明幀內(nèi)的字節(jié)數(shù)。2、使用字符填充的首尾定界符法用一些特定的字符來(lái)定界一幀的起始與終止。

數(shù)據(jù)的透明性3、使用比特填充的首尾定界符法以一組特定的比特模式(如01111110)來(lái)標(biāo)志一幀的起始與終止。數(shù)據(jù)的透明性4、違法編碼法借用違法編碼序列來(lái)定界幀的起始與終止。

47計(jì)算機(jī)網(wǎng)絡(luò)3.1.1幀同步幀同步：能從比特流中區(qū)分出幀的起始與終止3.1.2差錯(cuò)控制通信系統(tǒng)必須具備發(fā)現(xiàn)(即檢測(cè))差錯(cuò)的能力，并采取措施糾正它，使差錯(cuò)控制在所能允許的盡可能小的范圍內(nèi)，這就是差錯(cuò)控制過(guò)程，也是數(shù)據(jù)鏈路層的主要功能之一。反饋重發(fā)計(jì)時(shí)器幀序號(hào)48計(jì)算機(jī)網(wǎng)絡(luò)3.1.2差錯(cuò)控制通信系統(tǒng)必須具備發(fā)現(xiàn)(即檢測(cè))差錯(cuò)的能3.1.3流量控制流量控制并不是數(shù)據(jù)鏈路層特有的功能，許多高層協(xié)議中也提供流量控制功能，只不過(guò)流量控制的對(duì)象不同而已。流量控制實(shí)際上是對(duì)發(fā)送方數(shù)據(jù)流量的控制，使其發(fā)送速率不超過(guò)接收方的接收速率。49計(jì)算機(jī)網(wǎng)絡(luò)3.1.3流量控制流量控制并不是數(shù)據(jù)鏈路層特有的功能，3.1.4鏈路管理

鏈路管理功能主要是用于面向連接的服務(wù)。數(shù)據(jù)鏈路層連接的建立、維持和釋放就稱做鏈路管理。50計(jì)算機(jī)網(wǎng)絡(luò)3.1.4鏈路管理鏈路管理功能主要是用于面向連接的服務(wù)。3.2 差錯(cuò)檢測(cè)和校正

3.2.1傳輸差錯(cuò)的特性3.2.2奇偶校驗(yàn)3.2.3循環(huán)冗余校驗(yàn)3.2.4海明碼51計(jì)算機(jī)網(wǎng)絡(luò)3.2 差錯(cuò)檢測(cè)和校正3.2.1傳輸差錯(cuò)的特性9計(jì)算機(jī)3.2.1傳輸差錯(cuò)的特性傳輸中的差錯(cuò)都是由于噪聲引起的。噪聲有兩大類：一類是信道所固有的、持續(xù)存在的隨機(jī)熱噪聲；另一類是由于外界特定的短暫原因所造成的沖擊噪聲。誤碼率編碼效率差錯(cuò)控制的方式：自動(dòng)請(qǐng)求重發(fā)（AutomaticReQuestforRepeat，ARQ）前向糾錯(cuò)(ForwardErrorCorrection，F(xiàn)EC)52計(jì)算機(jī)網(wǎng)絡(luò)3.2.1傳輸差錯(cuò)的特性傳輸中的差錯(cuò)都是由于噪聲引起的。噪3.2.2奇偶校驗(yàn)(1/2)奇偶校驗(yàn)的特點(diǎn)：奇偶校驗(yàn)碼是一種通過(guò)增加冗余位使得碼字中“1”的個(gè)數(shù)恒為奇數(shù)或偶數(shù)的編碼方法,它是一種檢錯(cuò)碼。偶校驗(yàn):ri=I1i⊕I2i⊕…⊕Ipi奇校驗(yàn):ri=I1i⊕I2i⊕…⊕Ipi⊕1奇偶校驗(yàn)的分類：垂直奇偶校驗(yàn)

編碼效率R=p/(p+1)

53計(jì)算機(jī)網(wǎng)絡(luò)3.2.2奇偶校驗(yàn)(1/2)奇偶校驗(yàn)的特點(diǎn)：11計(jì)算機(jī)網(wǎng)絡(luò)3.2.2奇偶校驗(yàn)(2/2)水平奇偶校驗(yàn)編碼效率R=q/(q+1)

水平垂直奇偶校驗(yàn)編碼效率R=pq/(p+1)(q+1)54計(jì)算機(jī)網(wǎng)絡(luò)3.2.2奇偶校驗(yàn)(2/2)水平奇偶校驗(yàn)12計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(1/3)它是一種檢錯(cuò)碼。思想：任何一個(gè)由二進(jìn)制數(shù)位串組成的代碼都可以和一個(gè)只含0和1兩個(gè)系數(shù)的多項(xiàng)式建立一一對(duì)應(yīng)的關(guān)系。k位信息位對(duì)應(yīng)于一個(gè)k-1次多項(xiàng)式K(x)，r位冗余位對(duì)應(yīng)于一個(gè)r-1次多項(xiàng)式R(x)，生成的n=k+r位碼字則對(duì)應(yīng)于一個(gè)n-1次多項(xiàng)式T(x)。生成方法：發(fā)送方和接收方依據(jù)一事先約定的r次生成多項(xiàng)式G(x)（最高項(xiàng)xr和最低項(xiàng)的系數(shù)為1），用G(x)去除xrK(x)得到的余式就是R(x)，即得冗余位。55計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(1/3)它是一種檢錯(cuò)碼。13計(jì)算機(jī)3.2.3循環(huán)冗余校驗(yàn)(2/3)示例設(shè)信息位為1010001，即K(x)=x6+x4+1，取G(x)=x4+x2+x+1（對(duì)應(yīng)的代碼為10111），則x4K(x)=x10+x8+x4（對(duì)應(yīng)的代碼為10100010000），則所以冗余位為1101，

R(x)=x3+x2+1。T(X)=x4K(x)+R(x)=x10+x8+x4+

x3+x2+1

對(duì)應(yīng)的發(fā)送代碼為：1010001110156計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(2/3)示例設(shè)信息位為101003.2.3循環(huán)冗余校驗(yàn)(3/3)檢測(cè)方法：用發(fā)送端發(fā)送時(shí)采用的生成多項(xiàng)式G(x)來(lái)除接收到的碼字多項(xiàng)式，若余式不為0，則傳輸有差錯(cuò)；否則，認(rèn)為傳輸無(wú)差錯(cuò)。57計(jì)算機(jī)網(wǎng)絡(luò)3.2.3循環(huán)冗余校驗(yàn)(3/3)檢測(cè)方法：用發(fā)送端發(fā)送時(shí)采3.2.4海明碼(1/3)也是一種可以糾正一位差錯(cuò)的編碼。對(duì)于奇偶校驗(yàn)碼，若信息位為an-1an-2…a1，加上一位偶校驗(yàn)位a0，在接收端校驗(yàn)時(shí)，可按關(guān)系式

S=

an-1

⊕

an-2

⊕

…⊕a0來(lái)計(jì)算，若S=0，則無(wú)錯(cuò)；若S=1，則有錯(cuò)。上式稱為監(jiān)督關(guān)系式，S稱為校正因子。思想：增加冗余位，也相應(yīng)地增加監(jiān)督關(guān)系式和校正因子，就能表示更多的差錯(cuò)情況，包括具體定出是哪一位出錯(cuò)。理論依據(jù)：當(dāng)信息位為k位，增加r個(gè)冗余位，構(gòu)成n=k+r位碼字。若希望用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來(lái)區(qū)分無(wú)錯(cuò)和在碼字中n個(gè)不同的位置的一位錯(cuò)，則要求：2r≥k+r+1。58計(jì)算機(jī)網(wǎng)絡(luò)3.2.4海明碼(1/3)也是一種可以糾正一位差錯(cuò)的編碼。3.2.4海明碼(2/3)生成過(guò)程：（假設(shè)k=4，則r取3，信息位a6a5a4a3，冗余位a2a1a0）（1）構(gòu)造監(jiān)督關(guān)系式表（2）寫(xiě)出監(jiān)督關(guān)系式由上表可知，a2、a4、a5

或a6的一位錯(cuò)都應(yīng)使S2=1，所以

S2=a2⊕

a4

⊕

a5

⊕a6

同理

S1=a1⊕

a3

⊕

a5⊕a6

S0=a0⊕

a3⊕

a4⊕a6S2S1S0000001010100011101110111錯(cuò)碼位置無(wú)錯(cuò)a0錯(cuò)a1錯(cuò)a2錯(cuò)a3錯(cuò)a4錯(cuò)a5錯(cuò)a6錯(cuò)59計(jì)算機(jī)網(wǎng)絡(luò)3.2.4海明碼(2/3)生成過(guò)程：（假設(shè)k=4，則r取33.2.4海明碼(3/3)（3）求出冗余位關(guān)系式令S0、S1

和S2為0，即可求出a0、a1和a2：

a2=

a4⊕

a5⊕a6

a1=

a3⊕

a5⊕a6

a0=

a3⊕

a4⊕a6

示例（P69表3.2）糾錯(cuò)（P68）特點(diǎn)：（1）編碼效率為k/k+r（上例4/7）；（2）較容易實(shí)現(xiàn)，但只能糾正1位錯(cuò)。60計(jì)算機(jī)網(wǎng)絡(luò)3.2.4海明碼(3/3)（3）求出冗余位關(guān)系式18計(jì)算機(jī)3.3 數(shù)據(jù)鏈路層協(xié)議

3.3.1基本鏈路控制協(xié)議3.3.2滑動(dòng)窗口協(xié)議61計(jì)算機(jī)網(wǎng)絡(luò)3.3 數(shù)據(jù)鏈路層協(xié)議3.3.1基本鏈路控制協(xié)議193.3.1基本鏈路控制協(xié)議(1/8)

ARQ（AutomaticRepeatQuest，自動(dòng)重發(fā)請(qǐng)求，也稱“循環(huán)自動(dòng)請(qǐng)求”）協(xié)議是數(shù)據(jù)鏈路層最基本的協(xié)議。它是指在接收站接收到一個(gè)包含出錯(cuò)數(shù)據(jù)的信息（幀）時(shí)，自動(dòng)發(fā)出一個(gè)重傳錯(cuò)幀的請(qǐng)求。

ARQ的作用原則是對(duì)出錯(cuò)的數(shù)據(jù)幀自動(dòng)重發(fā)，它有三種形式：停等ARQ協(xié)議連續(xù)ARQ協(xié)議選擇重傳ARQ協(xié)議

62計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(1/8)ARQ（Automa3.3.1基本鏈路控制協(xié)議(2/8)

1、理想情況下的主機(jī)通信：完全理想化的數(shù)據(jù)傳輸要基于以下兩個(gè)假定：假定1—鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。假定2—不管發(fā)送方以多快的速率發(fā)送數(shù)據(jù)，接收方總是來(lái)得及收下，并及時(shí)上交主機(jī)。數(shù)據(jù)鏈路層不需要協(xié)議就可以保證數(shù)據(jù)傳輸?shù)恼_。63計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(2/8)1、理想情況下的主機(jī)3.3.1基本鏈路控制協(xié)議(3/8)

2、停等ARQ協(xié)議：工作原理發(fā)送方發(fā)送一個(gè)數(shù)據(jù)幀后，必須停下來(lái)等待接收方的確認(rèn)幀后才可以發(fā)送下一個(gè)數(shù)據(jù)幀；在接收方接收錯(cuò)誤時(shí)，接收方則發(fā)一否認(rèn)幀，要求發(fā)送方重發(fā)該幀；為防止發(fā)送的數(shù)據(jù)丟失，發(fā)送方內(nèi)部設(shè)置一個(gè)定時(shí)器，當(dāng)超過(guò)定時(shí)時(shí)間，而發(fā)送方仍未收到確認(rèn)幀時(shí)，發(fā)送方重發(fā)該幀；為防止確認(rèn)幀丟失而造成發(fā)送方重發(fā)同一數(shù)據(jù)幀，發(fā)送方給每一個(gè)數(shù)據(jù)幀帶上一個(gè)序列號(hào)。64計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(3/8)2、停等ARQ協(xié)議：3.3.1基本鏈路控制協(xié)議(4/8)

停等ARQ協(xié)議的缺點(diǎn)：停等ARQ協(xié)議雖然保證了傳輸?shù)陌踩煽?，但在傳輸過(guò)程中信道的吞吐量太低。65計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(4/8)停等ARQ協(xié)議的缺點(diǎn)3.3.1基本鏈路控制協(xié)議(5/8)

3、連續(xù)ARQ協(xié)議：工作原理連續(xù)ARQ是連續(xù)發(fā)送若干數(shù)據(jù)幀，如果發(fā)送方接收到接收端發(fā)回的確認(rèn)幀，則繼續(xù)發(fā)送；發(fā)送方在每發(fā)完一個(gè)數(shù)據(jù)幀后，就啟動(dòng)內(nèi)部超時(shí)定時(shí)器，在設(shè)置的超時(shí)時(shí)間內(nèi)未收到確認(rèn)幀，則重發(fā)相應(yīng)的數(shù)據(jù)幀。連續(xù)ARQ協(xié)議的工作示意圖：66計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(5/8)3、連續(xù)ARQ協(xié)議：3.3.1基本鏈路控制協(xié)議(6/8)

連續(xù)ARQ協(xié)議的缺點(diǎn)：連續(xù)ARQ協(xié)議一方面因連續(xù)發(fā)送數(shù)據(jù)幀而提高了效率，但另一方面，在重傳時(shí)又必須把原來(lái)已正確傳送過(guò)的數(shù)據(jù)幀進(jìn)行重傳（但僅因這些數(shù)據(jù)幀之前有一個(gè)數(shù)據(jù)幀出了錯(cuò)），這樣又使傳送速率降低。由此可見(jiàn)，若傳輸信道的傳輸質(zhì)量很差而誤碼率較大時(shí)，連續(xù)ARQ協(xié)議不一定優(yōu)于停等ARQ協(xié)議。67計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(6/8)連續(xù)ARQ協(xié)議的缺點(diǎn)3.3.1基本鏈路控制協(xié)議(7/8)

4、選擇重傳ARQ協(xié)議：工作原理當(dāng)接收方發(fā)現(xiàn)某幀出錯(cuò)后，其后繼續(xù)送來(lái)的正確幀雖然不能立即遞交給接收方的高層，但接收方仍可收下來(lái)，存放在一個(gè)緩沖區(qū)中，同時(shí)要求發(fā)送方重新傳送出錯(cuò)的那一幀。一旦收到重新傳來(lái)的幀后，就可以與原來(lái)已存于緩沖區(qū)中的其余幀一并按正確的順序遞交高層。

選擇重傳ARQ協(xié)議的缺點(diǎn)：選擇重發(fā)減少了浪費(fèi)，但要求接收方有足夠大的緩沖區(qū)空間，這在許多情況下是不夠經(jīng)濟(jì)的。正因如此，選擇重傳ARQ協(xié)議在目前就遠(yuǎn)沒(méi)有連續(xù)重傳ARQ協(xié)議使用得那么廣泛。今后存儲(chǔ)器芯片的價(jià)格會(huì)更加便宜，選擇重傳ARQ協(xié)議還是有可能受到更多的重視。68計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(7/8)4、選擇重傳ARQ協(xié)3.3.1基本鏈路控制協(xié)議(8/8)

選擇重傳ARQ協(xié)議的工作示意圖：以上三種重傳方法各有利弊，停等ARQ協(xié)議最簡(jiǎn)單，但信道利用率最低；選擇重傳ARQ協(xié)議信道利用率最高，但它要求接收端的緩沖容量相當(dāng)大；連續(xù)ARQ協(xié)議介于兩者之間。在應(yīng)用中應(yīng)根據(jù)實(shí)際情況選擇。69計(jì)算機(jī)網(wǎng)絡(luò)3.3.1基本鏈路控制協(xié)議(8/8)選擇重傳ARQ協(xié)議的1、XON/XOFF在流量控制方面，可以從不同側(cè)面采取不同的控制方案。最簡(jiǎn)單的方法就是增加接收端的緩沖存儲(chǔ)空間，使得接收端可以緩存更多的數(shù)據(jù)。但這只是一種被動(dòng)、消極的方法。因?yàn)?，一方面系統(tǒng)不允許開(kāi)設(shè)過(guò)大的緩沖空間；另一方面對(duì)于速率則顯著失效，而且在傳送大量數(shù)據(jù)的場(chǎng)合下，即使緩存空間再大也會(huì)出現(xiàn)不夠的現(xiàn)象。目前普遍采取一種稱之為“XON/XOFF”的發(fā)送控制字符的方案，通過(guò)控制字符來(lái)確定發(fā)送方是否繼續(xù)發(fā)送數(shù)據(jù)，相比之下更主動(dòng)、更積極、更有效。3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(1/4)

70計(jì)算機(jī)網(wǎng)絡(luò)1、XON/XOFF3.3.2XON/XOFF方案和滑動(dòng)窗XON/XOFF的通信原理：XON/XOFF是一種異步通信協(xié)議，接收設(shè)備或計(jì)算機(jī)使用特殊字符來(lái)控制發(fā)送設(shè)備或計(jì)算機(jī)傳送的數(shù)據(jù)流。當(dāng)接收計(jì)算機(jī)不能繼續(xù)接收數(shù)據(jù)時(shí)，發(fā)送一個(gè)XOFF控制字符告訴發(fā)送方停止傳送；當(dāng)傳輸可以恢復(fù)時(shí)，該計(jì)算機(jī)發(fā)送一個(gè)XON字符來(lái)通知發(fā)送方。3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(2/4)

71計(jì)算機(jī)網(wǎng)絡(luò)XON/XOFF的通信原理：3.3.2XON/XOFF方2、滑動(dòng)窗口協(xié)議滑動(dòng)窗口協(xié)議屬異步雙工傳輸模式。協(xié)議基本內(nèi)容：發(fā)送的信息幀都有一個(gè)序號(hào)，從0到某個(gè)最大值，0～2n－1，一般用n個(gè)二進(jìn)制位表示；發(fā)送端始終保持一個(gè)已發(fā)送但尚未確認(rèn)的幀的序號(hào)表，稱為發(fā)送窗口。發(fā)送窗口的上界表示要發(fā)送的下一個(gè)幀的序號(hào)，下界表示未得到確認(rèn)的幀的最小編號(hào)。發(fā)送窗口大小=上界-下界，大小可變。發(fā)送端每發(fā)送一個(gè)幀，序號(hào)取上界值，上界加1；每接收到一個(gè)正確響應(yīng)幀，下界加1。接收端有一個(gè)接收窗口，大小固定，但不一定與發(fā)送窗口相同。接收窗口的上界表示允許接收的序號(hào)最大的幀，下界表示希望接收的幀。接收窗口容納允許接收的信息幀，落在窗口外的幀均被丟棄。序號(hào)等于下界的幀被正確接收，并產(chǎn)生一個(gè)響應(yīng)幀，上界、下界都加1。接收窗口大小不變。

3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(3/4)

72計(jì)算機(jī)網(wǎng)絡(luò)2、滑動(dòng)窗口協(xié)議3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(4/4)

主要的滑動(dòng)窗口協(xié)議：1比特滑動(dòng)窗口協(xié)議（停等協(xié)議）退后n幀協(xié)議選擇重傳協(xié)議滑動(dòng)窗口協(xié)議的工作原理示意圖：73計(jì)算機(jī)網(wǎng)絡(luò)3.3.2XON/XOFF方案和滑動(dòng)窗口協(xié)議(4/4)主3.4 協(xié)議描述與驗(yàn)證

3.4.1有限狀態(tài)機(jī)模型3.4.2Petri網(wǎng)模型74計(jì)算機(jī)網(wǎng)絡(luò)3.4 協(xié)議描述與驗(yàn)證3.4.1有限狀態(tài)機(jī)模型323.4.1有限狀態(tài)機(jī)模型

有限狀態(tài)機(jī)（FiniteStateMachine，F(xiàn)SM）是一種用來(lái)描述系統(tǒng)的常用方法。在這個(gè)模型中，系統(tǒng)被描述成有限的狀態(tài)，在一定的前提條件下會(huì)發(fā)生一系列的輸入事件，這些事件使得系統(tǒng)采取相應(yīng)的動(dòng)作，并從一個(gè)狀態(tài)轉(zhuǎn)換成另一個(gè)狀態(tài)，稱為狀態(tài)的變遷或轉(zhuǎn)換（Transition）。75計(jì)算機(jī)網(wǎng)絡(luò)3.4.1有限狀態(tài)機(jī)模型有限狀態(tài)機(jī)（FiniteSt3.4.2Petri網(wǎng)模型

Petri網(wǎng)是由德國(guó)學(xué)者C.A.Petri首先提出的一種描述方法,它本質(zhì)上也是一種有限狀態(tài)機(jī)模型。Petri網(wǎng)的描述中有四種基本元素：位置(Place)—位置是一圓圈，表示可能進(jìn)入的狀態(tài)標(biāo)記(Token)—位置中的小圓黑點(diǎn)，某個(gè)位置中有標(biāo)記就表示已處于該狀態(tài)變遷(Transition)—用一根直線段來(lái)表示,指明了該變遷發(fā)生的條件帶箭頭的弧線(Arc)—用弧線來(lái)表示,指明變遷產(chǎn)生的條件和變遷產(chǎn)生的結(jié)果76計(jì)算機(jī)網(wǎng)絡(luò)3.4.2Petri網(wǎng)模型Petri網(wǎng)是由德國(guó)學(xué)者C.3.5 數(shù)據(jù)鏈路層協(xié)議舉例

3.5.1數(shù)據(jù)鏈路層協(xié)議的分類3.5.2HDLC3.5.3SLIP和PPP77計(jì)算機(jī)網(wǎng)絡(luò)3.5 數(shù)據(jù)鏈路層協(xié)議舉例3.5.1數(shù)據(jù)鏈路層協(xié)議的3.5.1數(shù)據(jù)鏈路層協(xié)議的分類鏈路控制協(xié)議的分類：異步協(xié)議—以字符為獨(dú)立的信息傳輸單位，在每個(gè)字符的起始處開(kāi)始對(duì)字符內(nèi)的比特實(shí)現(xiàn)同步，但字符與字符之間的間隔時(shí)間是不固定的(即字符之間是異步的)