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

計算機網絡

ComputerNetwork2023年1月2日計算機網絡

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

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

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

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

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

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

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

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

11計算機網絡3.2.2奇偶校驗(1/2)奇偶校驗的特點：11計算機網絡3.2.2奇偶校驗(2/2)水平奇偶校驗編碼效率R=q/(q+1)

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

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

x3+x2+1

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

S=

an-1

⊕

an-2

⊕

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

或a6的一位錯都應使S2=1，所以

S2=a2⊕

a4

⊕

a5

⊕a6

同理

S1=a1⊕

a3

⊕

a5⊕a6

S0=a0⊕

a3⊕

a4⊕a6S2S1S0000001010100011101110111錯碼位置無錯a0錯a1錯a2錯a3錯a4錯a5錯a6錯17計算機網絡3.2.4海明碼(2/3)生成過程：（假設k=4，則r取33.2.4海明碼(3/3)（3）求出冗余位關系式令S0、S1

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

a2=

a4⊕

a5⊕a6

a1=

a3⊕

a5⊕a6

a0=

a3⊕

a4⊕a6

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

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

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

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

20計算機網絡3.3.1基本鏈路控制協(xié)議(1/8)ARQ（Automa3.3.1基本鏈路控制協(xié)議(2/8)

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

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

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

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

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

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

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

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

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

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

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

30計算機網絡2、滑動窗口協(xié)議3.3.2XON/XOFF方案和滑動窗口協(xié)3.3.2XON/XOFF方案和滑動窗口協(xié)議(4/4)

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

3.4.1有限狀態(tài)機模型3.4.2Petri網模型32計算機網絡3.4 協(xié)議描述與驗證3.4.1有限狀態(tài)機模型323.4.1有限狀態(tài)機模型

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

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

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

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

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

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

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

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

38計算機網絡3.5.2HDLC(2/2)2、HDLC的幀格式：3.5.3SLIP和PPP(1/4)

用戶接入Internet的常用方法：使用撥號電話線接入Internet使用專線接入

SLIP：串行線路SLIP（SerialLineInternetProtocol，SLIP）用于運行TCP/IP協(xié)議的面向字符的點對點串行連接，早在1984年就已經開始使用。

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

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

40計算機網絡3.5.3SLIP和PPP(2/4)SLIP協(xié)議的缺3.5.3SLIP和PPP(3/4)

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

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

42計算機網絡3.5.3SLIP和PPP(4/4)PPP協(xié)議的幀格計算機網絡

ComputerNetwork2023年1月2日計算機網絡

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

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

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

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

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

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

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

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

53計算機網絡3.2.2奇偶校驗(1/2)奇偶校驗的特點：11計算機網絡3.2.2奇偶校驗(2/2)水平奇偶校驗編碼效率R=q/(q+1)

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

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

x3+x2+1

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

S=

an-1

⊕

an-2

⊕

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

或a6的一位錯都應使S2=1，所以

S2=a2⊕

a4

⊕

a5

⊕a6

同理

S1=a1⊕

a3

⊕

a5⊕a6

S0=a0⊕

a3⊕

a4⊕a6S2S1S0000001010100011101110111錯碼位置無錯a0錯a1錯a2錯a3錯a4錯a5錯a6錯59計算機網絡3.2.4海明碼(2/3)生成過程：（假設k=4，則r取33.2.4海明碼(3/3)（3）求出冗余位關系式令S0、S1

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

a2=

a4⊕

a5⊕a6

a1=

a3⊕

a5⊕a6

a0=

a3⊕

a4⊕a6

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

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

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

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

62計算機網絡3.3.1基本鏈路控制協(xié)議(1/8)ARQ（Automa3.3.1基本鏈路控制協(xié)議(2/8)

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

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

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

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

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

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

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

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

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

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

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

72計算機網絡2、滑動窗口協(xié)議3.3.2XON/XOFF方案和滑動窗口協(xié)3.3.2XON/XOFF方案和滑動窗口協(xié)議(4/4)

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

3.4.1有限狀態(tài)機模型3.4.2Petri網模型74計算機網絡3.4 協(xié)議描述與驗證3.4.1有限狀態(tài)機模型323.4.1有限狀態(tài)機模型

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

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

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