第3章數據鏈路層

1、2022年6月30日2/42計算機網絡計算機網絡n第1章概述n第2章物理層與數據通信基礎n第第3章章數據鏈路層數據鏈路層n第4章局域網n第5章網絡層n第6章網絡互聯技術n第7章傳輸層n第8章應用層n第9章網絡管理與信息安全n第10章網絡新技術專題3/42計算機網絡計算機網絡n3.1 數據鏈路層的功能 n3.2 差錯檢測和校正 n3.3 數據鏈路層協議 n3.4 協議描述與驗證 n3.5 數據鏈路層協議舉例 4/42計算機網絡計算機網絡 n3.1.1 幀同步 n3.1.2 差錯控制 n3.1.3 流量控制 n3.1.4 鏈路管理 5/42計算機網絡計算機網絡 n幀同步：能從比特流中區(qū)分出幀的起始

2、與終止。1、字節(jié)計數法 n以一個特殊字符表征一幀的起始，并以一個專門字段來標明幀內的字節(jié)數。2、使用字符填充的首尾定界符法 n用一些特定的字符來定界一幀的起始與終止。 n數據的透明性3、使用比特填充的首尾定界符法 n以一組特定的比特模式(如01111110)來標志一幀的起始與終止。n數據的透明性4、違法編碼法 n借用違法編碼序列來定界幀的起始與終止。 6/42計算機網絡計算機網絡n通信系統(tǒng)必須具備發(fā)現(即檢測)差錯的能力，并采取措施糾正它，使差錯控制在所能允許的盡可能小的范圍內，這就是差錯控制過程，也是數據鏈路層的主要功能之一 。n反饋重發(fā)n計時器n幀序號7/42計算機網絡計算機網絡n流量控制

3、并不是數據鏈路層特有的功能，許多高層協議中也提供流量控制功能，只不過流量控制的對象不同而已。n流量控制實際上是對發(fā)送方數據流量的控制，使其發(fā)送速率不超過接收方的接收速率。 8/42計算機網絡計算機網絡 n鏈路管理功能主要是用于面向連接的服務。n數據鏈路層連接的建立、維持和釋放就稱做鏈路管理。 9/42計算機網絡計算機網絡 n3.2.1 傳輸差錯的特性 n3.2.2 奇偶校驗 n3.2.3 循環(huán)冗余校驗 n3.2.4 海明碼 10/42計算機網絡計算機網絡n傳輸中的差錯都是由于噪聲引起的。噪聲有兩大類：一類是信道所固有的、持續(xù)存在的隨機熱噪聲；另一類是由于外界特定的短暫原因所造成的沖擊噪聲。n誤

4、碼率n編碼效率n差錯控制的方式 ：n自動請求重發(fā)（Automatic ReQuest for Repeat，ARQ） n前向糾錯(Forward Error Correction，FEC) 接收的總碼元數發(fā)生差錯的碼元數ePrkknkR11/42計算機網絡計算機網絡n奇偶校驗的特點：n奇偶校驗碼是一種通過增加冗余位使得碼字中“1”的個數恒為奇數或偶數的編碼方法,它是一種檢錯碼。n偶校驗:ri=I1iI2iIpin奇校驗: ri=I1iI2iIpi1n奇偶校驗的分類：n垂直奇偶校驗 n編碼效率 R=p/(p+1) R=p/(p+1) 12/42計算機網絡計算機網絡n水平奇偶校驗 n編碼效率 R=

5、q/(q+1) R=q/(q+1) n水平垂直奇偶校驗n編碼效率 R= R=pqpq/(p+1)(q+1)/(p+1)(q+1)13/42計算機網絡計算機網絡n它是一種檢錯碼。n思想思想：任何一個由二進制數位串組成的代碼都可以和一個只含0和1兩個系數的多項式建立一一對應的關系。nk位信息位對應于一個k-1次多項式K(x)，r位冗余位對應于一個r-1次多項式R(x)，生成的n=k+r位碼字則對應于一個n-1次多項式T(x)。n生成方法生成方法：發(fā)送方和接收方依據一事先約定的r次生成多項式G(x) （最高項xr和最低項的系數為1），用G(x)去除xrK(x)得到的余式就是R(x)，即得冗余位。14

6、/42計算機網絡計算機網絡n示例示例 設信息位為1010001，即K(x)= x6+x4+1，取G(x)= x4+x2+x+1（對應的代碼為10111），則x4 K(x)= x10+x8+x4（對應的代碼為10100010000），則n所以冗余位為1101， R(x)= x3+x2+1。 T(X)= x4 K(x)+ R(x)= x10+x8+x4 + x3+x2+1 對應的發(fā)送代碼為：1010001110115/42計算機網絡計算機網絡n檢測方法檢測方法：用發(fā)送端發(fā)送時采用的生成多項式G(x)來除接收到的碼字多項式，若余式不為0，則傳輸有差錯；否則，認為傳輸無差錯。16/42計算機網絡計算機

7、網絡n也是一種可以糾正一位差錯的編碼。n對于奇偶校驗碼，若信息位為an-1an-2a1，加上一位偶校 驗 位 a0， 在 接 收 端 校 驗 時 ， 可 按 關 系 式 S = an-1 an-2 a0來計算，若S=0，則無錯；若S=1，則有錯。上式稱為監(jiān)督關系式監(jiān)督關系式，S稱為校正因子校正因子。n思想：思想：增加冗余位，也相應地增加監(jiān)督關系式和校正因子，就能表示更多的差錯情況，包括具體定出是哪一位出錯。n理論依據：理論依據：當信息位為k位，增加r個冗余位，構成n=k+r位碼字。若希望用r個監(jiān)督關系式產生的r個校正因子來區(qū)分無錯和在碼字中n個不同的位置的一位錯，則要求：2rk+r+1。17/

8、42計算機網絡計算機網絡n生成過程：（生成過程：（假設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錯18/42計算機網絡計算機網絡（3）求出冗余位關系式令S0 、S1 和S2為0，即可求出a0 、a1和a2： a2 = a4 a5 a6 a1 = a3

9、 a5 a6 a0 = a3 a4 a6 n示例示例（P69 表3.2）n糾錯糾錯（P68 ）n特點：（1）編碼效率為k/k+r （上例4/7 ）；（2）較容易實現，但只能糾正1位錯。19/42計算機網絡計算機網絡 n3.3.1 基本鏈路控制協議 n3.3.2 滑動窗口協議 20/42計算機網絡計算機網絡 nARQ（Automatic Repeat Quest，自動重發(fā)請求，也稱“循環(huán)自動請求”）協議是數據鏈路層最基本的協議。它是指在接收站接收到一個包含出錯數據的信息（幀）時，自動發(fā)出一個重傳錯幀的請求。n ARQ的作用原則是對出錯的數據幀自動重發(fā)，它有三種形式：n停等ARQ協議n連續(xù)ARQ協

10、議n選擇重傳ARQ協議 21/42計算機網絡計算機網絡 1、理想情況下的主機通信：n完全理想化的數據傳輸要基于以下兩個假定：n假定1鏈路是理想的傳輸信道，所傳送的任何數據既不會出差錯也不會丟失。n假定2不管發(fā)送方以多快的速率發(fā)送數據，接收方總是來得及收下，并及時上交主機。n數據鏈路層不需要協議就可以保證數據傳輸的正確。22/42計算機網絡計算機網絡 2、停等ARQ協議：n工作原理n發(fā)送方發(fā)送一個數據幀后，必須停下來等待接收方的確認幀后才可以發(fā)送下一個數據幀；在接收方接收錯誤時，接收方則發(fā)一否認幀，要求發(fā)送方重發(fā)該幀；為防止發(fā)送的數據丟失，發(fā)送方內部設置一個定時器，當超過定時時間，而發(fā)送方仍未收

11、到確認幀時，發(fā)送方重發(fā)該幀；為防止確認幀丟失而造成發(fā)送方重發(fā)同一數據幀，發(fā)送方給每一個數據幀帶上一個序列號。23/42計算機網絡計算機網絡 n停等ARQ協議的缺點：n停等ARQ協議雖然保證了傳輸的安全可靠，但在傳輸過程中信道的吞吐量太低。24/42計算機網絡計算機網絡 3、連續(xù)ARQ協議：n工作原理n連續(xù)ARQ是連續(xù)發(fā)送若干數據幀，如果發(fā)送方接收到接收端發(fā)回的確認幀，則繼續(xù)發(fā)送；發(fā)送方在每發(fā)完一個數據幀后，就啟動內部超時定時器，在設置的超時時間內未收到確認幀，則重發(fā)相應的數據幀。n連續(xù)ARQ協議的工作示意圖：25/42計算機網絡計算機網絡 n連續(xù)ARQ協議的缺點：n連續(xù)ARQ協議一方面因連續(xù)發(fā)

12、送數據幀而提高了效率，但另一方面，在重傳時又必須把原來已正確傳送過的數據幀進行重傳（但僅因這些數據幀之前有一個數據幀出了錯），這樣又使傳送速率降低。由此可見，若傳輸信道的傳輸質量很差而誤碼率較大時，連續(xù)ARQ協議不一定優(yōu)于停等ARQ協議。26/42計算機網絡計算機網絡 4、選擇重傳ARQ協議：n工作原理n當接收方發(fā)現某幀出錯后，其后繼續(xù)送來的正確幀雖然不能立即遞交給接收方的高層，但接收方仍可收下來，存放在一個緩沖區(qū)中，同時要求發(fā)送方重新傳送出錯的那一幀。一旦收到重新傳來的幀后，就可以與原來已存于緩沖區(qū)中的其余幀一并按正確的順序遞交高層。 n選擇重傳ARQ協議的缺點：n選擇重發(fā)減少了浪費，但要求

13、接收方有足夠大的緩沖區(qū)空間，這在許多情況下是不夠經濟的。正因如此，選擇重傳ARQ協議在目前就遠沒有連續(xù)重傳ARQ協議使用得那么廣泛。今后存儲器芯片的價格會更加便宜，選擇重傳ARQ協議還是有可能受到更多的重視。27/42計算機網絡計算機網絡 n選擇重傳ARQ協議的工作示意圖：n以上三種重傳方法各有利弊，停等ARQ協議最簡單，但信道利用率最低；選擇重傳ARQ協議信道利用率最高，但它要求接收端的緩沖容量相當大；連續(xù)ARQ協議介于兩者之間。在應用中應根據實際情況選擇。28/42計算機網絡計算機網絡1、XON/XOFFn在流量控制方面，可以從不同側面采取不同的控制方案。最簡單的方法就是增加接收端的緩沖存

14、儲空間，使得接收端可以緩存更多的數據。但這只是一種被動、消極的方法。因為，一方面系統(tǒng)不允許開設過大的緩沖空間；另一方面對于速率則顯著失效，而且在傳送大量數據的場合下，即使緩存空間再大也會出現不夠的現象。n目前普遍采取一種稱之為“XON/XOFF”的發(fā)送控制字符的方案，通過控制字符來確定發(fā)送方是否繼續(xù)發(fā)送數據，相比之下更主動、更積極、更有效。 29/42計算機網絡計算機網絡nXON/XOFF 的通信原理：nXON/XOFF是一種異步通信協議，接收設備或計算機使用特殊字符來控制發(fā)送設備或計算機傳送的數據流。當接收計算機不能繼續(xù)接收數據時，發(fā)送一個XOFF控制字符告訴發(fā)送方停止傳送；當傳輸可以恢復時

15、，該計算機發(fā)送一個XON字符來通知發(fā)送方。 30/42計算機網絡計算機網絡2、滑動窗口協議n滑動窗口協議屬異步雙工傳輸模式。n協議基本內容：n發(fā)送的信息幀都有一個序號，從0到某個最大值，02n1，一般用n個二進制位表示；發(fā)送端始終保持一個已發(fā)送但尚未確認的幀的序號表，稱為發(fā)送窗口。發(fā)送窗口的上界表示要發(fā)送的下一個幀的序號，下界表示未得到確認的幀的最小編號。發(fā)送窗口大小=上界-下界，大小可變。發(fā)送端每發(fā)送一個幀，序號取上界值，上界加1；每接收到一個正確響應幀，下界加1。n接收端有一個接收窗口，大小固定，但不一定與發(fā)送窗口相同。接收窗口的上界表示允許接收的序號最大的幀，下界表示希望接收的幀。接收窗

16、口容納允許接收的信息幀，落在窗口外的幀均被丟棄。序號等于下界的幀被正確接收，并產生一個響應幀，上界、下界都加1。接收窗口大小不變。 31/42計算機網絡計算機網絡 n主要的滑動窗口協議 ：n1比特滑動窗口協議（停等協議） n退后n幀協議 n選擇重傳協議 n滑動窗口協議的工作原理示意圖32/42計算機網絡計算機網絡 n3.4.1 有限狀態(tài)機模型 n3.4.2 Petri網模型 33/42計算機網絡計算機網絡 n有限狀態(tài)機（Finite State Machine，FSM）是一種用來描述系統(tǒng)的常用方法。在這個模型中，系統(tǒng)被描述成有限的狀態(tài)，在一定的前提條件下會發(fā)生一系列的輸入事件，這些事件使得系統(tǒng)

17、采取相應的動作，并從一個狀態(tài)轉換成另一個狀態(tài)，稱為狀態(tài)的變遷或轉換（Transition）。34/42計算機網絡計算機網絡 nPetri網是由德國學者C.A.Petri首先提出的一種描述方法,它本質上也是一種有限狀態(tài)機模型。 nPetri網的描述中有四種基本元素 ：n位置(Place)位置是一圓圈，表示可能進入的狀態(tài) n標記(Token)位置中的小圓黑點，某個位置中有標記就表示已處于該狀態(tài) n變遷(Transition)用一根直線段來表示,指明了該變遷發(fā)生的條件 n帶箭頭的弧線(Arc)用弧線來表示,指明變遷產生的條件和變遷產生的結果 35/42計算機網絡計算機網絡 n3.5.1 數據鏈路層協

18、議的分類 n3.5.2 HDLC n3.5.3 SLIP和PPP 36/42計算機網絡計算機網絡n鏈路控制協議的分類：n異步協議以字符為獨立的信息傳輸單位，在每個字符的起始處開始對字符內的比特實現同步，但字符與字符之間的間隔時間是不固定的(即字符之間是異步的) n同步協議以許多字符或許多比特組織成的數據塊-幀為傳輸單位，在幀的起始處同步，使幀內維持固定的時鐘。 n同步協議的分類： n面向字符的同步協議 n面向比特的同步協議n面向字節(jié)計數的同步協議37/42計算機網絡計算機網絡 1、HDLC的操作方式：n所謂操作方式，通俗地講就是某站點是以主站點方式操作還是以從站方式操作，或者是二者兼?zhèn)洹?nH

19、DLC操作方式的類型：n正常響應方式NRM(Norma Responses Mode) 這是一非平衡數據鏈路方式，有時也稱非平衡正常響應方式，傳輸過程由主站啟動。 n異步響應方式ARM(Asynchronous Responses Mode) 這也是一種非平衡數據鏈路操作方式，與NRM不同的是，ARM下的傳輸過程由從站啟動。 n異步平衡方式ABM(Asynchronous Balanced Mode) 這是一種允許任何節(jié)點來啟動傳輸的操作方式。為了提高鏈路傳輸效率，節(jié)點之間在兩個方向上都需要有較高的信息傳輸量。 38/42計算機網絡計算機網絡 2、HDLC的幀格式的幀格式 ：3、HDLC的幀類型的幀類型 ：n信息幀(I幀)信息幀用于傳送有效信息或數據，通常簡稱I幀。 n監(jiān)控幀(S幀)監(jiān)控幀用于差錯控制和流量控制，通常簡稱S幀。 n無編號幀(U幀)無編號幀因其控制字段中不包含編號N(S)和N(R)而得名，簡稱U幀。U幀用于提供對鏈路的建立、拆除以及多種控制功能。 39/42計算機網絡計算機網絡 n用戶接入Internet的常用方法：n使用撥號電話線接入Internet n使用專線接入 nSLIP：n串行線路SLIP（Serial Line Internet Protocol，SLIP）用于運行TCP/IP協議的面向字符的點對