數據鏈路層

1.DLL層設計問題

1.1 DLL層·功能

數據鏈路層使用物理層提供的服務在通信信道上發送和接收比特。

(1) 向網絡層提供一個定義良好的接口

(2) 處理傳輸錯誤

(3) 調節數據流，確保慢速的接收方不會被快速的發送方淹沒

提供的服務

(1) 無確認的無連接服務 (局域網)

(2) 有確認的無連接服務 (無線通信)

(3) 有確認的有連接服務 (電話)

無線通信，信道使用率很低但數據傳輸的誤碼率相對較高，確認是必要的

1.2 成幀

成幀：將原始的位流分散到離散的幀中。

成幀的方法有：

(1)字符計數法

(2)帶字節/字符填充的標志字節法

(3)比特填充的比特標志法

(4)物理層編碼違例法

(1)字符計數法

字節計數法：利用幀頭部的一個字段來標識該幀中的字符數

缺點：簡單，無法恢復，已經很少使用

字符計數法

(2)帶字節/字符填充的標志字節法

該方法考慮了錯誤之后重新開始同步的問題，用一些特殊字節(FLAG)作為幀開始和結束標志，用轉義字符(ESC)來區分二進制數據中存在的特殊字節。

Paste_Image.png

(3)比特填充的比特標志法

以特殊的位模式01111110作為幀標志，即一個幀的開始(同時標志前一個幀的結束)

當幀內容中出現一個與幀標志相同的位串01111110，則在5個1后插入一個0，即變成01111101，接收方將自動刪除第5 個1后的0。這稱為位填充法，也稱為透明傳輸。

Paste_Image.png

(4)物理層編碼違例法

采用冗余編碼技術，如曼切斯特編碼，即兩個脈沖寬來表示一個二進制位

數據0：低-高電平對

數據1：高-低電平對

高-高電平對和低-低電平對沒有使用，可用作幀邊界

2. 糾錯和檢錯

幀的校驗

? ? 超時與重發(計時器)

? 幀的序號(解決重復幀的問題)

流控? 基于反饋的流控? 基于速率的流控(發送端確定，在DLL 中幾乎不采用)

2.1幀的校驗

差錯的種類：

單個錯誤，錯誤分散在各塊中

突發錯誤，錯誤集中在某塊中

差錯的處理：

糾錯碼(需要太多的冗余位，糾錯開銷太大，主要用于無線網絡)

檢錯碼 (不能恢復，可重傳)

計算機網絡中主要采用：

檢錯碼：循環冗余碼(CRC)

糾錯碼：海明碼

2.1.1 海明碼

海明距離的意義：如果海明距離為d，則一個碼字需要發生d個1位錯誤才能變成另外一個碼字

海明距離與檢錯和糾錯的關系：

海明距離為d+1的編碼能檢測出d位差錯。

因為在距離為d+1的檢驗碼中，只改變d位的值，不可能產生另一個合法碼。如奇偶校驗碼，海明距離為2，能查出單個錯。

海明距離為2d+1的編碼，能糾正d位差錯。

因為此時，如果一個碼字有d位發生差錯，它仍然距離原來的碼字距離最近，可以直接恢復為該碼。(奇偶校驗碼，海明距離為2，可以檢出單個錯)

糾正單比特錯的冗余位下界,m為數據位數，r為校驗位數

(m+r+1)≤2^r

每一個碼字從左到右編號，最左邊為第1位

校驗位和數據位

凡編號為2的乘冪的位是校驗位，如1、2、4、8、16、……。

其余是數據位，如3、5、6、7、9、……。

每一個校驗位設置根據：包括自己在內的一些位的集合的奇偶值(奇校驗或偶校驗)。

2.1.1.1 如何決定每個數據位的校驗碼

將某一位數據位的編號展開成2的乘冪的和，那末每一項所對應的位即為該數據位的校驗位(收方使用)。

如： 11 = 1 + 2 + 8

29 = 1 + 4 + 8 + 16

校驗位1的檢驗集合為所有奇數位。

校驗位2的檢驗集合：2、3、6、7、10、11、…

校驗位4的檢驗集合：4、5、6、7、……

校驗位8的檢驗集合：8、9、10、11、……

海明碼糾錯過程(只糾錯1位)

首先將差錯計數器置“0”。

當海明碼數據到達接收端后，接收端逐個檢查各個校驗位的奇偶性。

如發現某一校驗位和它所檢測的集合的奇偶性不正確，就將該檢驗位的編號加到差錯計數器中。

待所有校驗位核對完畢：

若差錯計數器仍為“0”值，則說明該碼字接收無誤。

非“0”值，差錯計數器的值為出錯位的編號，將該位求反就可得到正確結果。

例子：

計算"1001000"的偶校驗時的海明碼字？

經計算需要的檢驗字個數的最小值 r應滿足 ( 所以r最小值為4,再根據校驗位的對應規則可得下表：

Paste_Image.png

海明碼糾錯實例

Paste_Image.png

Data: 1011010

Even: 1011010 0 (偶校驗)

Odd: 1011010 1 (奇校驗)

2.1.2 循環冗余檢錯碼CRC

可以檢測到所有長度小于等于r的突發錯誤

廣泛用于各種網絡，幾乎所有的局域網

使用CRC編碼時發送方和接收方必須預先商定一個生成多項式G(x),假設有一個m為的幀M(x)，使用G(x)生成的幀的步驟如下：

假設G(x)的階為r， 那么M(x)在末尾添加r個0，得到 m+r位的位模式 。

利用模2出發，用G(x)去除 ,得到對應的余數(總是小于等于r位)。

利用 減去(模2減法)第2步中得到的余數，得到的位模式就是即將被傳輸的帶校驗和的幀

Sender

在數據幀的低端加上r個零，對應多項式為XrM(x)

采用模2除法，用G(x)去除XrM(x)，得余數

采用模2減法，用XrM(x)減去余數，得到帶CRC校驗和的幀

Receiver

用收到的幀去除以G(x)

為零：無錯誤產生。非零：發生了錯誤，重傳

3.基本DLL層協議

3.1 協議1 烏托邦式單工協議(理想的)

在一定條件下運作:

數據單向傳送

收發雙方的網絡層都處于就緒狀態(隨時待命)

處理時間忽略不計(瞬間完成)

可用的緩存空間無窮大(無限空間)

假設DLL之間的信道永遠不會損壞或者丟失幀(完美通道)

“烏托邦”

缺點：

不現實，沒有任何流量控制

處理過程接近無確認的無連接服務，卻沒有差錯檢測

協議1實現

3.2 協議2 無錯信道上的單工停-等式協議

添加了確認幀

用于防止慢的接收方被數據淹沒

收方回發一個啞幀，發送方收到啞幀，表明收方允許接收數據，

此時再次發送下一幀數據

采用一個半雙工的物理信道

缺點：

新舊幀無區別對待(詳情看協議3)

協議2實現

3.3 協議3 有錯信道上的單工停-等式協議(重傳+確認)【ARQ/PAR】

對協議2的改進：

Paste_Image.png

確認幀

只在接收無差錯時才發確認幀，出錯時不發確認幀。

重發

網絡中采用檢錯碼，無法糾正錯誤，由重發原來幀的方式來恢復正確的幀。

計時器

控制何時重發，防止無限期等待(死鎖)。

幀序號

防止重發時接收端收到重復的幀，序號還用于接收時排序。

保證送給網絡層的都是按序無重復的分組

幀格式：

****

協議3

Paste_Image.png

Paste_Image.png

3.3&3.4的夾縫 下一類協議：滑動窗口協議

與前三個協議不同，這是一個雙向傳遞的協議。之后的三個協議都屬于滑動窗口協議。

捎帶確認：

當發送方的數據幀到來，抑制自己并開始等待，直到網絡層傳給他下一個要發的數據包，將確認信息搭載在下一個外發的數據幀(s.ack)上。

如無法“捎帶”，當一個控制捎帶確認的計時器超時后，單獨發確認幀。

捎帶確認的作用：更好的利用了信道的可用帶寬。幀頭的確認信息只占用很少的幾位，而單獨的幀需要一個幀頭、確認信息和校驗和

滑動窗口本質

Paste_Image.png

滑動窗口協議

如果發送端可以連續發送一批數據幀，必須考慮接收端是否來得及接納與處理這么多的幀，這里就提出了網絡流量控制問題

N回退協議和選擇重傳協議：

由于傳輸過程中存在延遲，即數據在傳播過程中需要時間，那么如果使用上面所提及的協議，傳輸過程中有大量的時間存在阻塞狀態，所以為了充分利用帶寬，我們讓發送方一次發送w個幀。所以就存在如何處理在傳輸過程中出現的幀錯誤的問題

3.4 協議4， 1位滑動窗口協議

協議四的基本工作原理：

窗口設置

滑動窗口最大值： MAX_SEQ = 1

通信雙方初始值： seq =0, ack=1(期待接收seq=0)

窗口滑動機制

A首先發送數據幀( seq=0, ack=1, A0)

B收到A0，發送捎帶確認幀(seq=0, ack=0, B0)

A收到對A0的確認，滑動窗口，發送幀(seq=1, ack=0, A1)

特點

序列號seq和確認值ack“0”“1”交替

滑動窗口長度W=1，收到確認才移動窗口

保證按順序將接收到的正確幀只一次上交網絡層

發送數據幀01,10交替，確認幀00,11交替

協議4-實現

出錯情況：

連續發送W個數據幀，其中有一幀出錯，但其后續幀被成功發送

Paste_Image.png

Paste_Image.png

改進：針對出錯情況接收方的接收策略選擇

丟棄錯幀及后續幁，其后續幀因不是期望接收幀也被丟棄

丟棄錯幀，緩存后續正確接收幀

對應的發送方的重傳策略選擇

緩存在發送窗口中的出錯幀以及其后續幀全部重發——協議5

只重發出錯幀——協議6

3.5 協議5 回退N協議

連續發送W幀的原因

接收方的接收策略：丟棄錯幀，其后續幀因不是期望接收幀也被丟棄(接收窗口為1)。

發送方的重傳策略：緩存在發送窗口中的出錯幀以及其后續幀全部重發

3.5.1 基本概念：

定義序列號seq的取值范圍和滑動窗口長度W

發送方連續發送至發送窗口滿

接收窗口為1，對出錯幀不確認(引發超時)

發送方超時重傳，從未被確認幀開始

w值：

W<=2BD+1(個幀)

BD:帶寬-延遲乘積，bit乘積出來之后換算成幀的個數

Paste_Image.png

3.5.2 回退N協議：

Paste_Image.png

Paste_Image.png

該圖的發送方和接收方的窗口大小都是7，那么也就是說發送方一次最多只能發送7個幀，剛開始發送方只能發送序號為0~6的數據幀，圖中發送方收到序列號為第0和第1號幀的確認幀，那么整個窗口向前滑動，發送方可以發送序列號為7和8 的數據幀，但是不幸的是2號數據幀并沒有收到確認幀，所以整個窗口并不會向前滑動，此時只能等待2號數據幀的計時器超時，那么超時后發送方將會從2號數據幀開始發送，重復這個過程。

實現

回退N協議實現.png

回退N協議實現.png

回退N協議的累計確認

出錯情況

出錯情況

3.6 協議6 選擇重傳協議

原因：如果錯誤很少發生，那么協議5可以很好的工作。一旦線路質量很差，那么重傳幀需要浪費大量帶寬。而選擇重傳節約了帶寬，允許接收方緩存丟失幀之后的所有幀

接收方的接收策略：丟棄錯幀，緩存后續正確接收幀

發送方的重傳策略：只重發出錯幀。

基本概念：

接收窗口存儲差錯幀后繼的所有正確幀

發送方只重傳差錯幀

接收方接收重傳幀，按正確順序將分組提交網絡層

選擇重傳策略：

接收方丟掉壞幀，但接受并緩存壞幀后面的所有好幀。

選擇重傳策略常與否定重傳策略一起使用

否定重傳策略：

當接收方收到錯誤，他就發送一個否定確認(NAK)信息，而不需要等到相應的計數器超時，提高協議性能。

3.6.1 差錯控制策略比較

回退n幀

發送方需要較大的緩沖區，以便重傳

重傳幀數多，適于信道出錯率較少的情況

選擇重傳

接收方需要較大的緩沖區，以便按正確順序將分組提交網絡層

重傳幀數少，適于信道質量不好的情況

滑動窗口長度w的選擇

協議5(回退n幀)W = MAX_SEQ

協議6(選擇重傳)W= (MAX_SEQ + 1) / 2

發送方和接收方的窗口大小 W=((MAX_SEQ+1))/2,原因是防止窗口重疊，在確認幀丟失的情況下而導致的數據錯誤

窗口重疊1

重口重疊2.png

窗口重疊3

窗口重疊4

窗口重疊5

接收方在某個幀出錯后繼續接受和緩存后續發送的數據包，直到整個窗口的填滿后，把幀進行排序后才傳遞給網絡層。

4. DLL層協議實例

4.1 高級數據鏈路控制(HDLC)，面向位的數據鏈路協議

特性：

面向比特、 同步傳輸( bit-synchronous)

工作原理：數據幀的可靠傳輸

面向連接(建立/釋放邏輯連接)

流控制(滑動窗口seq/ack )

差錯控制( go back n / select repeat)

4.2 點到點協議PPP

面向字符的數據鏈路協議

PPP 是一種在鏈路上傳輸分組的常用方法

采用字節填充的幀界法 (0x7E)

“無序號幀” (無確認無連接) 用于承載IP分組

采用校驗和檢錯

3個主要特性：

成幀：毫無歧義地區分出一幀的結束和下一幀的開始

鏈路控制協議(LCP)

網絡控制協議(NCP)

PPP兩種認證協議： PAP and CHAP

PAP是一種簡單的明文驗證方式

簡單的C發送賬號密碼到S，S再返回值給C

這種驗證方式的安全性較差，第三方可以很容易獲取被傳送的用戶名和口令

CHAP是一種加密的驗證方式，能夠避免建立連接時傳送用戶的真實密碼

1.S發送隨機數序列給C，C將賬號密碼與序列運算后發送給S，S返回值給C

2.NAS 向遠程用戶發送一個挑戰口令(challenge )，其中包括會話ID和一個任意生成的挑戰字串(arbitrary challengestring )。遠程客戶必須使用MD5 單向哈希算法返回用戶名和加密的挑戰口令

3.因為服務器端存有客戶的明文口令，所以服務器可以重復客戶端進行

的操作，并將結果與用戶返回的口令進行對照

4.在整個連接過程中，CHAP 將不定時的向客戶端重復發送挑戰口令，從而避免第3 方冒充遠程客戶(remote client impersonation )進行攻擊。

PPP的幀格式

PPP的幀格式.png

PPP成幀是面向字節填充的:

具體細節可以參考上面的字節填充法， 因為PPP重用了HDLC的技術，所以PPP使用標志字(0x7E 01111110)來標記幀的起始，使用0x7D來作為轉義字符，具體操作如下：

使用0x7E來標記幀的開始

如果在Payload中存在0x7E則在該字節前，填充 0x7D(轉義)，把 0x7E 和 0x20 進行異或運算，對出現的0x7D 同樣處理 0x7E --> 0x7D 0x5E 0x7D --> 0x7D 0x5D

若信息字段中出現ASCII碼的控制字符(即數值小于0x20的字符)，則在該字符前面要加入一個0x7D字節，同時將該字符的編碼和0x20進行異或處理

接收方接收到幀后進行下面處理：

在幀中遇到0x7D 就把0x7D刪除，在把緊跟在0x7D 后的字節和0x20進行異或運算，就得到對應的數據

地址域：固定為11111111 ，可省略

控制域：缺省為00000011，即無序號幀(即毋需確認)，可省略

協議域：不同的協議不同的代碼

載荷域：可變長，缺省1500字節

校驗和：缺省為2字節，也可定義為4字節

LCP ( Link Control Protocol)提供了建立、配置、維護和終止點對點鏈接的方法

PPP的工作過程

發送端PPP首先發送LCP幀，以配置和測試數據鏈路

在LCP建立好數據鏈路并協調好所選設備之后，發送端PPP發送NCP幀，以選擇和配置一個或多個網絡協議

當所選的網絡層協議配置好后，便可將各網絡層協議的分組發送到數據鏈路上

配置好的鏈路將一直保持通信狀態，直到LCP幀或NCP幀明確提示關閉鏈路，或有其它的外部事件發生(如用戶干預等)

總結

以上是生活随笔為你收集整理的回退n帧协议c语言代码,[计算机网络]Ch.3 数据链路层的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。