1. 數據鏈路層的功能

• 1. 數據鏈路層使用物理層提供的**“比特傳輸”**服務
• 2. 數據鏈路層為網絡層提供服務，將網絡層的 IP數據報（分組） 封裝成幀，傳輸給下一個相鄰結點

物理鏈路：**傳輸介質（0層）+ 物理層（1層）**實現了相鄰結點之間的“物理鏈路”

邏輯鏈路：數據鏈路層需要基于“物理鏈路”，實現相鄰結點之間邏輯上無差錯的“數據鏈路（邏輯鏈路）”

2. 組幀

2.1 字符填充法

再次強調：首部計數字段所記錄的幀長 = 計數字段長度 + 幀的數據部分長度

2.2 字節填充法

總結：

• 發送方發送：只要遇到特殊字符，如：SOH、EOT、ESC等，就在這個特殊字符前面加上一個ESC（轉義字符）
• 接收方接收：只要遇到ESC（轉義字符），就丟掉這個ESC，然后跳過一個字符，去接著看跳過字符后面的內容

2.3 零比特填充法

總結：

• 發送：每當遇到連續5個1，就填充一個0
• 接收：每當遇到連續5個1，就刪掉后面的0

2.4 違規編碼

2.5 總結

3. 差錯控制

3.1 檢錯編碼

3.1.1 奇偶校驗

• 奇校驗碼：有效信息位和校驗位（整個校驗碼）中“1”的個數為奇數
• 偶校驗位：有效信息位和校驗位（整個校驗碼）中“1”的個數為偶數

異或運算，符號：$\oplus$。運算規則：

• 1. 相同為0，相異為1
• 2. 無進制加法，進制指二進制，即：0 $\oplus$ 0 = 0、0 $\oplus$ 1 = 1、1 $\oplus$ 0 = 1、1 $\oplus$ 1 = 0。中間符號就可以理解為+，只不過是無進制的，在組成原理里用異或運算實現CPU加法器

個人覺得用第二種理解能更快得出異或結果

• 奇偶校驗常用偶校驗，因為偶校驗的硬件實現更簡單：各信息進行異或（模2加）運算，得到的結果即為偶校驗位：

再次強調，奇偶校驗只能檢測奇數位錯誤，不能檢測偶數位錯誤

3.1.2 循環冗余校驗碼（CRC）

例：

說明：

強調：CRC不是百分百檢錯，但其檢錯率很高，其也有1位的糾錯能力，但實際應用中只用它的檢錯。

3.1.3 總結

3.2 糾錯編碼（海明校驗碼）

• 偶校驗：能發現奇數位錯誤，但無法確定是哪一位出錯。即1個校驗位只能攜帶2種狀態信息
• 基于偶校驗，海明碼的設計思路：將信息位分組進行偶校驗 -> 設計多個校驗位 -> 多個校驗位標注出錯位置。即多個校驗位能攜帶多種狀態信息

求解步驟：

例：給定信息位 —— 1010

• 1. 確定海明碼的位數：2^k >= n + k + 1 -> n = 4 -> k = 3
     
• 2. 確定校驗位的分布：校驗位 P_i 放在海明位號為 2^i-1 的位置上，信息位按順序放到其余位置

• 3. 求校驗位的值：
     ①先分組形成校驗關系，即每個數據位用多個校驗位進行校驗，滿足條件：被校驗數據位的海明位號等于校驗該數據位的各校驗位海明位號之和
     
     ②異或取值：三個分組各自分別進行偶校驗

填表如下：

• 4. 檢錯糾錯
     
     同理：S₃S₂S₁ = 110，表示第6位出錯，S₃S₂S₁ = 111，表示第7位出錯

上述為從大到小的格式，當然也有從小到大的格式：

補充：

推論：

• 1. S₃S₂S₁ = 000 且全體偶校驗成功 -> 無錯誤
• 2. S₃S₂S₁ != 000 且全體偶校驗失敗 -> 有1位錯，糾正即可。但實際上這個推論只能說明是有奇數個位錯誤，如D₁D₂D₄同時出錯時，也滿足這個條件，但實際生活中這是個小概率事件，因為有線鏈路的出錯率本來就低
• 3. S₃S₂S₁ != 000 且全體偶校驗成功 -> 有偶數個位錯，需重傳
• 4. S₃S₂S₁ = 000 且全體偶校驗失敗 -> 海明校驗碼失效，需重傳，對應D₁D₂D₃同時出錯

3.3 總結

4. 流量控制 & 可靠傳輸

數據鏈路層的流量控制與可靠傳輸都是基于滑動窗口機制實現的

滑動窗口機制：

4.1 停止 - 等待協議（S-W）

4.2 后退N幀協議（GBN）

4.3 選擇重傳協議（SR）

特殊的，當發送窗口的大小大于1，接收窗口的大小等于1，且發送窗口的大小+接收窗口的大小 <= 2ⁿ，此時又變為了GBN協議

4.4 總結

強調：

• 1. 三種協議都有超時重傳機制、確認幀以及幀的正確編號限制，這是滑動窗口保證可靠傳輸與流量控制的奧妙所在
• 2. 都要滿足W_T + W_R <= 2ⁿ。其中SR還規定W_T <= W_R，一般取W_T = W_R
• 3. GBN采用累積確認的方式，若中間出錯，僅需重傳最后一次收到的確認幀位置之后的所有幀（不包含確認幀位置幀的重傳）
• 4. S-W和SR則采用逐幀確認的方式，哪個幀有問題就重傳哪個幀，不同的是，SR檢測收到的幀有差錯，需傳否認幀NAK給發送方，而S-W只需丟棄該幀，等待發送方超時重傳即可，可以看出SR的時間效率高于S-W

5. 三種協議的信道利用率分析

5.1 S-W

5.2 GBN & SR

5.3 總結