數(shù)據(jù)鏈路層
1.DLL層設(shè)計問題
1.1 DLL層·功能
數(shù)據(jù)鏈路層使用物理層提供的服務(wù)在通信信道上發(fā)送和接收比特。
（1） 向網(wǎng)絡(luò)層提供一個定義良好的接口
（2） 處理傳輸錯誤
（3） 調(diào)節(jié)數(shù)據(jù)流，確保慢速的接收方不會被快速的發(fā)送方淹沒
提供的服務(wù)
（1） 無確認的無連接服務(wù) （局域網(wǎng)）
（2） 有確認的無連接服務(wù) （無線通信）
（3） 有確認的有連接服務(wù) （電話）
無線通信，信道使用率很低但數(shù)據(jù)傳輸?shù)恼`碼率相對較高，確認是必要的
1.2 成幀
成幀：將原始的位流分散到離散的幀中。
成幀的方法有：
（1）字符計數(shù)法
（2）帶字節(jié)/字符填充的標志字節(jié)法
（3）比特填充的比特標志法
（4）物理層編碼違例法
（1）字符計數(shù)法
字節(jié)計數(shù)法：利用幀頭部的一個字段來標識該幀中的字符數(shù)
缺點：簡單，無法恢復，已經(jīng)很少使用
（2）帶字節(jié)/字符填充的標志字節(jié)法
該方法考慮了錯誤之后重新開始同步的問題，用一些特殊字節(jié)（FLAG）作為幀開始和結(jié)束標志，用轉(zhuǎn)義字符（ESC）來區(qū)分二進制數(shù)據(jù)中存在的特殊字節(jié)。
（3）比特填充的比特標志法
- 以特殊的位模式01111110作為幀標志，即一個幀的開始（同時標志前一個幀的結(jié)束）
- 當幀內(nèi)容中出現(xiàn)一個與幀標志相同的位串01111110，則在5個1后插入一個0，即變成01111101，接收方將自動刪除第5 個1后的0。這稱為位填充法，也稱為透明傳輸。
（4）物理層編碼違例法
采用冗余編碼技術(shù)，如曼切斯特編碼，即兩個脈沖寬來表示一個二進制位
數(shù)據(jù)0：低-高電平對
數(shù)據(jù)1：高-低電平對
高-高電平對和低-低電平對沒有使用，可用作幀邊界
2. 糾錯和檢錯
- 幀的校驗
- ? ? 超時與重發(fā)（計時器）
- ? 幀的序號（解決重復幀的問題）
- 流控? 基于反饋的流控? 基于速率的流控（發(fā)送端確定，在DLL 中幾乎不采用）
2.1幀的校驗
差錯的種類：
- 單個錯誤，錯誤分散在各塊中
- 突發(fā)錯誤，錯誤集中在某塊中
差錯的處理：
- 糾錯碼（需要太多的冗余位，糾錯開銷太大，主要用于無線網(wǎng)絡(luò)）
- 檢錯碼 (不能恢復，可重傳)
計算機網(wǎng)絡(luò)中主要采用：
- 檢錯碼：循環(huán)冗余碼(CRC)
- 糾錯碼：海明碼
2.1.1 海明碼
海明距離的意義：如果海明距離為d，則一個碼字需要發(fā)生d個1位錯誤才能變成另外一個碼字
海明距離與檢錯和糾錯的關(guān)系：
- 海明距離為d+1的編碼能檢測出d位差錯。
因為在距離為d+1的檢驗碼中，只改變d位的值，不可能產(chǎn)生另一個合法碼。如奇偶校驗碼，海明距離為2，能查出單個錯。
- 海明距離為2d+1的編碼，能糾正d位差錯。
因為此時，如果一個碼字有d位發(fā)生差錯，它仍然距離原來的碼字距離最近，可以直接恢復為該碼。（奇偶校驗碼，海明距離為2，可以檢出單個錯）
糾正單比特錯的冗余位下界,m為數(shù)據(jù)位數(shù)，r為校驗位數(shù)
(m+r+1)≤2^r
- 每一個碼字從左到右編號，最左邊為第1位
- 校驗位和數(shù)據(jù)位
凡編號為2的乘冪的位是校驗位，如1、2、4、8、16、……。
其余是數(shù)據(jù)位，如3、5、6、7、9、……。 - 每一個校驗位設(shè)置根據(jù)：包括自己在內(nèi)的一些位的集合的奇偶值（奇校驗或偶校驗)。
2.1.1.1 如何決定每個數(shù)據(jù)位的校驗碼
將某一位數(shù)據(jù)位的編號展開成2的乘冪的和，那末每一項所對應(yīng)的位即為該數(shù)據(jù)位的校驗位(收方使用)。
如： 11 = 1 + 2 + 8
29 = 1 + 4 + 8 + 16
校驗位1的檢驗集合為所有奇數(shù)位。
校驗位2的檢驗集合：2、3、6、7、10、11、…
校驗位4的檢驗集合：4、5、6、7、……
校驗位8的檢驗集合：8、9、10、11、……
海明碼糾錯過程(只糾錯1位)
首先將差錯計數(shù)器置“0”。
當海明碼數(shù)據(jù)到達接收端后，接收端逐個檢查各個校驗位的奇偶性。
如發(fā)現(xiàn)某一校驗位和它所檢測的集合的奇偶性不正確，就將該檢驗位的編號加到差錯計數(shù)器中。
待所有校驗位核對完畢：
若差錯計數(shù)器仍為“0”值，則說明該碼字接收無誤。
非“0”值，差錯計數(shù)器的值為出錯位的編號，將該位求反就可得到正確結(jié)果。
例子：
計算"1001000"的偶校驗時的海明碼字？
經(jīng)計算需要的檢驗字個數(shù)的最小值 r應(yīng)滿足 ( 所以r最小值為4,再根據(jù)校驗位的對應(yīng)規(guī)則可得下表：
海明碼糾錯實例
Data: 1011010
Even: 1011010 0 （偶校驗）
Odd: 1011010 1 （奇校驗）
2.1.2 循環(huán)冗余檢錯碼CRC
- 可以檢測到所有長度小于等于r的突發(fā)錯誤
- 廣泛用于各種網(wǎng)絡(luò)，幾乎所有的局域網(wǎng)
使用CRC編碼時發(fā)送方和接收方必須預先商定一個生成多項式G(x),假設(shè)有一個m為的幀M(x)，使用G(x)生成的幀的步驟如下：
假設(shè)G(x)的階為r， 那么M(x)在末尾添加r個0，得到 m+r位的位模式 。
利用模2出發(fā)，用G(x)去除 ,得到對應(yīng)的余數(shù)（總是小于等于r位）。
利用 減去(模2減法)第2步中得到的余數(shù)，得到的位模式就是即將被傳輸?shù)膸ｒ灪偷膸?br>
Sender
在數(shù)據(jù)幀的低端加上r個零，對應(yīng)多項式為XrM(x)
采用模2除法，用G(x)去除XrM(x)，得余數(shù)
采用模2減法，用XrM(x)減去余數(shù)，得到帶CRC校驗和的幀
Receiver
用收到的幀去除以G（x）
為零：無錯誤產(chǎn)生。非零：發(fā)生了錯誤，重傳
3.基本DLL層協(xié)議
3.1 協(xié)議1 烏托邦式單工協(xié)議（理想的）
在一定條件下運作:
- 數(shù)據(jù)單向傳送
- 收發(fā)雙方的網(wǎng)絡(luò)層都處于就緒狀態(tài)（隨時待命）
- 處理時間忽略不計（瞬間完成）
- 可用的緩存空間無窮大（無限空間）
- 假設(shè)DLL之間的信道永遠不會損壞或者丟失幀（完美通道）
- “烏托邦”
缺點：
- 不現(xiàn)實，沒有任何流量控制
- 處理過程接近無確認的無連接服務(wù)，卻沒有差錯檢測
3.2 協(xié)議2 無錯信道上的單工停-等式協(xié)議
- 添加了確認幀
用于防止慢的接收方被數(shù)據(jù)淹沒
收方回發(fā)一個啞幀，發(fā)送方收到啞幀，表明收方允許接收數(shù)據(jù)，
此時再次發(fā)送下一幀數(shù)據(jù)
采用一個半雙工的物理信道
缺點：
-
新舊幀無區(qū)別對待（詳情看協(xié)議3）
協(xié)議2實現(xiàn)
3.3 協(xié)議3 有錯信道上的單工停-等式協(xié)議(重傳+確認)【ARQ/PAR】
對協(xié)議2的改進：
確認幀
只在接收無差錯時才發(fā)確認幀，出錯時不發(fā)確認幀。
重發(fā)
網(wǎng)絡(luò)中采用檢錯碼，無法糾正錯誤，由重發(fā)原來幀的方式來恢復正確的幀。
計時器
控制何時重發(fā)，防止無限期等待（死鎖）。
幀序號
防止重發(fā)時接收端收到重復的幀，序號還用于接收時排序。
保證送給網(wǎng)絡(luò)層的都是按序無重復的分組
幀格式：
****
3.3&3.4的夾縫 下一類協(xié)議：滑動窗口協(xié)議
與前三個協(xié)議不同，這是一個雙向傳遞的協(xié)議。之后的三個協(xié)議都屬于滑動窗口協(xié)議。
-
捎帶確認：
當發(fā)送方的數(shù)據(jù)幀到來，抑制自己并開始等待，直到網(wǎng)絡(luò)層傳給他下一個要發(fā)的數(shù)據(jù)包，將確認信息搭載在下一個外發(fā)的數(shù)據(jù)幀（s.ack）上。
如無法“捎帶”，當一個控制捎帶確認的計時器超時后，單獨發(fā)確認幀。
捎帶確認的作用：更好的利用了信道的可用帶寬。幀頭的確認信息只占用很少的幾位，而單獨的幀需要一個幀頭、確認信息和校驗和
滑動窗口協(xié)議
如果發(fā)送端可以連續(xù)發(fā)送一批數(shù)據(jù)幀，必須考慮接收端是否來得及接納與處理這么多的幀，這里就提出了網(wǎng)絡(luò)流量控制問題
N回退協(xié)議和選擇重傳協(xié)議：
由于傳輸過程中存在延遲，即數(shù)據(jù)在傳播過程中需要時間，那么如果使用上面所提及的協(xié)議，傳輸過程中有大量的時間存在阻塞狀態(tài)，所以為了充分利用帶寬，我們讓發(fā)送方一次發(fā)送w個幀。所以就存在如何處理在傳輸過程中出現(xiàn)的幀錯誤的問題
3.4 協(xié)議4， 1位滑動窗口協(xié)議
協(xié)議四的基本工作原理：
窗口設(shè)置
- 滑動窗口最大值： MAX_SEQ = 1
- 通信雙方初始值： seq =0, ack=1（期待接收seq=0）
窗口滑動機制
- A首先發(fā)送數(shù)據(jù)幀（ seq=0, ack=1, A0）
- B收到A0，發(fā)送捎帶確認幀（seq=0, ack=0, B0）
- A收到對A0的確認，滑動窗口，發(fā)送幀（seq=1, ack=0, A1）
特點
- 序列號seq和確認值ack“0”“1”交替
- 滑動窗口長度W=1，收到確認才移動窗口
- 保證按順序?qū)⒔邮盏降?strong>正確幀只一次上交網(wǎng)絡(luò)層
- 發(fā)送數(shù)據(jù)幀01,10交替，確認幀00,11交替
出錯情況：
連續(xù)發(fā)送W個數(shù)據(jù)幀，其中有一幀出錯，但其后續(xù)幀被成功發(fā)送
改進：針對出錯情況接收方的接收策略選擇
丟棄錯幀及后續(xù)幁，其后續(xù)幀因不是期望接收幀也被丟棄
丟棄錯幀，緩存后續(xù)正確接收幀
對應(yīng)的發(fā)送方的重傳策略選擇
緩存在發(fā)送窗口中的出錯幀以及其后續(xù)幀全部重發(fā)——協(xié)議5
只重發(fā)出錯幀——協(xié)議6
3.5 協(xié)議5 回退N協(xié)議
接收方的接收策略：丟棄錯幀，其后續(xù)幀因不是期望接收幀也被丟棄（接收窗口為1）。
發(fā)送方的重傳策略：緩存在發(fā)送窗口中的出錯幀以及其后續(xù)幀全部重發(fā)
3.5.1 基本概念：
- 定義序列號seq的取值范圍和滑動窗口長度W
- 發(fā)送方連續(xù)發(fā)送至發(fā)送窗口滿
- 接收窗口為1，對出錯幀不確認（引發(fā)超時）
- 發(fā)送方超時重傳，從未被確認幀開始
w值：
W<=2BD+1(個幀)
BD:帶寬-延遲乘積，bit乘積出來之后換算成幀的個數(shù)
3.5.2 回退N協(xié)議：
該圖的發(fā)送方和接收方的窗口大小都是7，那么也就是說發(fā)送方一次最多只能發(fā)送7個幀，剛開始發(fā)送方只能發(fā)送序號為0~6的數(shù)據(jù)幀，圖中發(fā)送方收到序列號為第0和第1號幀的確認幀，那么整個窗口向前滑動，發(fā)送方可以發(fā)送序列號為7和8 的數(shù)據(jù)幀，但是不幸的是2號數(shù)據(jù)幀并沒有收到確認幀，所以整個窗口并不會向前滑動，此時只能等待2號數(shù)據(jù)幀的計時器超時，那么超時后發(fā)送方將會從2號數(shù)據(jù)幀開始發(fā)送，重復這個過程。
實現(xiàn)
出錯情況
3.6 協(xié)議6 選擇重傳協(xié)議
原因：如果錯誤很少發(fā)生，那么協(xié)議5可以很好的工作。一旦線路質(zhì)量很差，那么重傳幀需要浪費大量帶寬。而選擇重傳節(jié)約了帶寬，允許接收方緩存丟失幀之后的所有幀
接收方的接收策略：丟棄錯幀，緩存后續(xù)正確接收幀
發(fā)送方的重傳策略：只重發(fā)出錯幀。
基本概念：
- 接收窗口存儲差錯幀后繼的所有正確幀
- 發(fā)送方只重傳差錯幀
- 接收方接收重傳幀，按正確順序?qū)⒎纸M提交網(wǎng)絡(luò)層
選擇重傳策略：
接收方丟掉壞幀，但接受并緩存壞幀后面的所有好幀。
- 選擇重傳策略常與否定重傳策略一起使用
否定重傳策略：
當接收方收到錯誤，他就發(fā)送一個否定確認（NAK）信息，而不需要等到相應(yīng)的計數(shù)器超時，提高協(xié)議性能。
3.6.1 差錯控制策略比較
回退n幀
發(fā)送方需要較大的緩沖區(qū)，以便重傳
重傳幀數(shù)多，適于信道出錯率較少的情況選擇重傳
接收方需要較大的緩沖區(qū)，以便按正確順序?qū)⒎纸M提交網(wǎng)絡(luò)層
重傳幀數(shù)少，適于信道質(zhì)量不好的情況
滑動窗口長度w的選擇
協(xié)議5（回退n幀）W = MAX_SEQ
協(xié)議6（選擇重傳）W= (MAX_SEQ + 1) / 2
發(fā)送方和接收方的窗口大小 W=((MAX_SEQ+1))/2,原因是防止窗口重疊，在確認幀丟失的情況下而導致的數(shù)據(jù)錯誤
接收方在某個幀出錯后繼續(xù)接受和緩存后續(xù)發(fā)送的數(shù)據(jù)包，直到整個窗口的填滿后，把幀進行排序后才傳遞給網(wǎng)絡(luò)層。
4. DLL層協(xié)議實例
4.1 高級數(shù)據(jù)鏈路控制（HDLC），面向位的數(shù)據(jù)鏈路協(xié)議
特性：
面向比特、 同步傳輸（ bit-synchronous）工作原理：數(shù)據(jù)幀的可靠傳輸
面向連接（建立/釋放邏輯連接）
流控制（滑動窗口seq/ack ）
差錯控制（ go back n / select repeat）
4.2 點到點協(xié)議PPP
面向字符的數(shù)據(jù)鏈路協(xié)議
PPP 是一種在鏈路上傳輸分組的常用方法
- 采用字節(jié)填充的幀界法 (0x7E)
- “無序號幀” (無確認無連接) 用于承載IP分組
- 采用校驗和檢錯
3個主要特性：
- 成幀：毫無歧義地區(qū)分出一幀的結(jié)束和下一幀的開始
- 鏈路控制協(xié)議（LCP）
- 網(wǎng)絡(luò)控制協(xié)議（NCP）
PPP兩種認證協(xié)議： PAP and CHAP
PAP是一種簡單的明文驗證方式
簡單的C發(fā)送賬號密碼到S，S再返回值給C
這種驗證方式的安全性較差，第三方可以很容易獲取被傳送的用戶名和口令CHAP是一種加密的驗證方式，能夠避免建立連接時傳送用戶的真實密碼
1.S發(fā)送隨機數(shù)序列給C，C將賬號密碼與序列運算后發(fā)送給S，S返回值給C
2.NAS 向遠程用戶發(fā)送一個挑戰(zhàn)口令（challenge ），其中包括會話ID和一個任意生成的挑戰(zhàn)字串（arbitrary challengestring ）。遠程客戶必須使用MD5 單向哈希算法返回用戶名和加密的挑戰(zhàn)口令
3.因為服務(wù)器端存有客戶的明文口令，所以服務(wù)器可以重復客戶端進行
的操作，并將結(jié)果與用戶返回的口令進行對照
4.在整個連接過程中，CHAP 將不定時的向客戶端重復發(fā)送挑戰(zhàn)口令，從而避免第3 方冒充遠程客戶（remote client impersonation ）進行攻擊。
PPP的幀格式
PPP成幀是面向字節(jié)填充的:
具體細節(jié)可以參考上面的字節(jié)填充法， 因為PPP重用了HDLC的技術(shù)，所以PPP使用標志字（0x7E 01111110）來標記幀的起始，使用0x7D來作為轉(zhuǎn)義字符，具體操作如下：
- 使用0x7E來標記幀的開始
- 如果在Payload中存在0x7E則在該字節(jié)前，填充 0x7D（轉(zhuǎn)義），把 0x7E 和 0x20 進行異或運算，對出現(xiàn)的0x7D 同樣處理 0x7E --> 0x7D 0x5E 0x7D --> 0x7D 0x5D
- 若信息字段中出現(xiàn)ASCII碼的控制字符（即數(shù)值小于0x20的字符），則在該字符前面要加入一個0x7D字節(jié)，同時將該字符的編碼和0x20進行異或處理
接收方接收到幀后進行下面處理：
在幀中遇到0x7D 就把0x7D刪除，在把緊跟在0x7D 后的字節(jié)和0x20進行異或運算，就得到對應(yīng)的數(shù)據(jù)
- 地址域：固定為11111111 ，可省略
控制域：缺省為00000011，即無序號幀（即毋需確認），可省略
協(xié)議域：不同的協(xié)議不同的代碼
載荷域：可變長，缺省1500字節(jié)
校驗和：缺省為2字節(jié)，也可定義為4字節(jié)
LCP （ Link Control Protocol）提供了建立、配置、維護和終止點對點鏈接的方法
PPP的工作過程
- 發(fā)送端PPP首先發(fā)送LCP幀，以配置和測試數(shù)據(jù)鏈路
- 在LCP建立好數(shù)據(jù)鏈路并協(xié)調(diào)好所選設(shè)備之后，發(fā)送端PPP發(fā)送NCP幀，以選擇和配置一個或多個網(wǎng)絡(luò)協(xié)議
- 當所選的網(wǎng)絡(luò)層協(xié)議配置好后，便可將各網(wǎng)絡(luò)層協(xié)議的分組發(fā)送到數(shù)據(jù)鏈路上
- 配置好的鏈路將一直保持通信狀態(tài)，直到LCP幀或NCP幀明確提示關(guān)閉鏈路，或有其它的外部事件發(fā)生（如用戶干預等）
