【計算機網絡】王道考研筆記整理（3）數據鏈路層

第三章 · 數據鏈路層

3.1 數據鏈路層的功能

3.2 組幀

?3.2.1 字符計數法

3.2.2 字節填充法

?3.2.3 零比特填充法

3.2.4 違規編碼法

3.3 差錯控制

3.3.1 奇偶校驗碼

3.3.2 CRC 校驗碼

?3.3.3 海明校驗碼

3.4 可靠傳輸與流量控制

3.4.1 滑動窗口機制

?3.4.2 停止 - 等待協議

3.4.3 后退 N 幀協議

3.4.4 選擇重傳協議

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

3.5 介質訪問控制

3.5.1 信道劃分

?3.5.2 隨機訪問

3.6 局域網和 IEEE802

3.6.1 局域網的基本概念和體系結構

?3.6.2 以太網和 IEEE802.3

3.6.3 VLAN 的基本概念與基本原理

3.6.4 IEEE802.11 無線局域網

第三章 · 數據鏈路層

3.1 數據鏈路層的功能

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

? ? ? ? 以下是數據鏈路層的常見功能，也是本章節之后會涉及到的所有內容。

3.2 組幀

? ? ? ? 本節我們主要討論不同的組幀編碼方式。

?3.2.1 字符計數法

? ? ? ? 字符計數法的原理是在每個幀開頭，用一個定長計數字段表示幀長。注意，這里的幀長是計數字段長度加上幀的數據部分長度的和。

? ? ? ? 這種方法的缺點在于任何一個計數字段錯誤，后面所有的幀都會無法定界。?

3.2.2 字節填充法

? ? ? ? 字節填充法的原理是在每個幀的開頭和結尾分別添加一段控制字符。

? ? ? ? 但問題在于可能會將數據部分中某一段當作控制字符，因此，使用這種編碼需要在數據部分出現控制字符時，在前面加上一段轉義字符。這樣，機器識別的時候，當識別到轉義字符時，就會認為后一段是數據部分，并忽略轉義字符的內容。從而避免將數據的一部分當作控制字符。

?3.2.3 零比特填充法

? ? ? ? 這種編碼方式和字節填充法類似，也是在每一幀的開頭結尾添加一段特殊比特串。

? ? ? ? 但問題也一樣，可能在數據部分出現和特殊比特串一樣的數據段。由于特殊比特串中間有 6 個連續的 1，因此，采用的解決方法是對于數據部分，從左往右掃，每當出現 5 個連續的 1 時，就會在后面插入一個 0。這樣就永遠不可能出現 6 個連續的 1，而接收方在接收數據時也可以用類似的方法將數據部分復原，實現透明傳輸。

? ? ? ? 注意：HDLC 和 PPP 組幀協議使用的就是零比特填充法。?

3.2.4 違規編碼法

? ? ? ? 這種編碼方式需要物理層配合使用，比如說在物理層傳輸比特串時使用的是曼徹斯特編碼，上跳 0 下跳 1，時間周期中間一定會變化，那么就可以在幀的開頭結尾加上一個時鐘周期的編碼。這段編碼的中間不發生變化，也就是違規的曼徹斯特編碼。

? ? ? ? 當遇到違規的曼徹斯特編碼時，就可以很方便地確定幀的界。

3.3 差錯控制

? ? ? ? 差錯控制主要目的是發現并解決一個幀內部的“位錯誤”。常用的有兩種解決方案：一種是接收方在發現比特錯誤后，丟棄幀，由發送方重傳幀；另一種是由接收方發現和糾正比特錯誤。

? ? ? ? 第一種解決方案使用的編碼方式被稱為檢錯編碼，本節主要討論奇偶校驗碼和 CRC 校驗碼。

? ? ? ? 第二種解決方案使用的編碼方式被稱為糾錯編碼，本節主要討論海明校驗碼。

3.3.1 奇偶校驗碼

? ? ? ? 奇偶校驗碼的原理如下圖所示：

? ? ? ? 工業上常見的是偶校驗法，因為偶校驗的硬件實現比較簡單，只需要將所有信息位做異或運算得到的就是偶校驗位。但問題在于，無法檢驗出偶數位錯誤，并且沒有糾錯能力。

3.3.2 CRC 校驗碼

?????????CRC 校驗碼全稱為循環冗余校驗碼，具體原理如下圖所示：

【例題】如何求 CRC 碼？

? ? ? ? ?注意這里的余數產生使用的是模 2 除法，而不是我們常用的十進制除法！！！

? ? ? ? 最終得到校驗位是 001，因此，CRC 碼為 101001001。

? ? ? ? ?除了計算 CRC 碼，我們還需要知道如果接收方收到的編碼除以除數得到的結果不是 0，那么我們是可以根據不同的余數情況判斷收到的編碼中哪一位出現了問題。只不過，對于不同的除數，得到的余數和編碼中位數的對應關系是不同的！比如下圖就是除數為 1101 時，不同余數對應出錯的編碼位：

?3.3.3 海明校驗碼

? ? ? ? 這部分在計算機組成原理中已有，這里不再贅述。

3.4 可靠傳輸與流量控制

? ? ? ? 可靠傳輸與流量控制的具體功能在第一節中已經提過了，這兩者都與滑動窗口機制緊密相關。本節，我們從滑動窗口開始說起，并討論與之息息相關的三種協議。

3.4.1 滑動窗口機制

? ? ? ? 如下圖所示，發送窗孔表示發送方當前允許發送的幀，接收窗口表示接收方當前允許接收的幀。

????????若此時，發送方發送 A,B,C,D 這四個幀，由于 A,B 落在接收窗口范圍內，因此會被接收，而 C,D 因為落在接收窗口范圍外，則會直接丟棄。接著，接收方可以通過“確認機制”控制發送方窗口向右滑動，從而實現“流量控制”。

????????之后，我們將提到的一些協議在下圖中的四個方面都有所不同，也是我們討論的中心。

?3.4.2 停止 - 等待協議

?????????上圖是停止 - 等待協議中的一些機制。這里主要對幀編號這一點做一定的解釋：無論是停止 - 等待協議還是之后將提及的后退 N 幀協議和選擇重傳協議，我們判斷需要 n?bit 來給幀編號，都使用的是條件 Wt + Wr <= 2^n。這里可以求得 n = 1。

????????假如此時，接收方沒有收到數據幀，那么發送方會因為長時間沒有收到確認幀而選擇重新發送數據幀 Data0。等到接收方收到數據幀 Data0，并且發送方收到確認幀之后，接收窗口和發送窗口才會右移。

????????假如此時，接收方發出的確認幀丟失，那么發送方也會因為長時間沒有收到確認幀而選擇重新發送數據幀 Data0。但是，此時接收方已經移動到幀序號為 1 處，當收到數據幀 Data0 時，容易判斷收到的是重復幀，所以直接丟棄，并發送重復幀的 ACK?給發送方。等到發送方收到確認幀之后，發送窗口才會右移。

? ? ? ? 通過上面的例子可以看出，如果沒有編號，那么接收方將無法判斷“重復幀”。由于接收窗口和發送窗口的距離相差不超過 1，因此使用 1 bit 表示幀序號足矣。

3.4.3 后退 N 幀協議

? ? ? ? 上圖是后退 N 幀協議的一些機制。這里發送窗口的數量并不固定，因此，需要用多少 bit 來給幀編號，是要利用條件計算才能得到的。

? ? ? ? ?正常情況下，GBN 使用特殊規則“累計確認”來依次接收和發送幀數據。假如此時，再一次發送，本來應該發送 3，0，1 但是 0 號幀出現了問題。那么接收方將會返回最后一個接收到的正確的幀，也就是 3 號幀的 ACK。接著，發送方本要繼續發送 2，3，0 號幀，但因為收到的 ACK 只到 3 號幀，所以會“后退”到 0 號幀，發送 0，1，2 號幀。

? ? ? ? 注意：這里的“后退”并不是指滑動窗口后退，只不過是需要重傳部分幀，因此看起來比原本應該傳的幀有所后退罷了。?

3.4.4 選擇重傳協議

? ? ? ? ?上圖是選擇重傳的一些機制，具體的實現原理和停止 - 等待協議和后退 N 幀協議類似，在此不再贅述。

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

? ? ? ? 停止 - 等待協議的信道利用率比較容易分析：

? ? ? ? 只要代入公式計算即可。這里確認幀的傳輸時延一般較短，有時甚至可以忽略。

? ? ? ? 后退 N 幀協議和選擇重傳協議的信道利用率計算公式一致：

? ? ? ? ?但要注意信道利用率的最大值為 1，因此，如果通過公式計算得到的結果超過 1，應該取 1。

? ? ? ? 【注意】這里要額外講一些術語：

????????如果題目里出現滑動窗口協議，那么指的是后退 N 幀協議或選擇重傳協議。

? ? ? ? 如果題目里出現 ARQ 協議，那么三種協議都有可能。

? ? ? ? 如果題目里出現連續 ARQ 協議，那么指的是后退 N 幀協議或選擇重傳協議。

3.5 介質訪問控制

? ? ? ? 在多個節點共享同一個“總線型”廣播信道時，可能發生信號沖突。為了減少甚至避免沖突，就需要對介質訪問加以控制。本節將講解不同的介質訪問控制技術。

3.5.1 信道劃分

? ? ? ? 信道劃分的方式有很多，比如時分復用、頻分復用等等。具體的實現思想就是通過將信道按照某一個標準進行劃分，從而使得不同的信號不會相互干擾。

1. 時分復用（TDM）

? ? ? ? 將時間分為等長的 TDM 幀，每個 TDM 幀又劃分為等長的時隙，將 m 個時隙分配給 m 個用戶使用。

? ? ? ? 但 TDM 的缺點也十分明顯，每對節點最多只能分配到 1/m 個帶寬。如果某對節點不發送數據，會導致分配的時隙閑置，信道利用率低。

2. 統計時分復用（STDM）

? ? ? ? 在 TDM 的基礎上，動態按序分配時隙。如果需要時某個節點可以在一段時間內獲得所有的信道帶寬資源。如果某節點暫不發送數據，可以不分配“時隙”，信道利用率更高。

3. 頻分復用（FDM）

????????頻分復用劃分的是信道的總頻帶范圍，也就是總帶寬。通過將信道的總頻帶劃分為多個子頻帶，每一個子頻帶作為一個子信道，每對用戶通過一個子信道進行通信。

? ? ? ? 這種方式的優點在于，充分利用了信道帶寬，但缺點是只能使用模擬信號進行傳輸。

4. 波分復用

? ? ? ? 波分復用其實就是光的頻分復用。光的頻率和波長呈負相關，將各節點發出的不同波長的光信號“復合”后傳輸到光纖上，就成了波分復用。

5. 碼分復用

?????????碼分復用的內容比較復雜，具體可以參看下圖：

? ? ? ? 我們可以用例子幫助理解：下圖展示的就是對于 A,B,C 三個節點之間傳輸信息的碼分序列設置。

? ? ? ? 而如何將疊加的信號從節點收到的信息中分離出來呢？就使用規格化內積的方式：

?3.5.2 隨機訪問

1. ALOHA 協議

? ? ? ? 這里我們將通過流程圖的形式幫助理解隨機訪問的過程。ALOHA 協議分為純 ALOHA 協議和時隙 ALOHA 協議。

? ? ? ? 上圖展示的是純 ALOHA 協議的流程，特點是一旦準備好數據幀就立刻發送。

? ? ? ? 例如，在上圖中 A,B,C,D 的數據幀準備好就立刻發送，假如出現發送是被或者沖突的情況，就會隨機等一段時間后重發。

? ? ? ? 上圖展示的是時隙 ALOHA 協議的流程，特點是我們設置的時隙大小就是傳輸一個幀的最長時間，并且只有在每個幀的開始才會傳輸數據幀。

? ? ? ? ?時隙的好處在于避免了用戶發送數據的隨意性，降低了沖突的概率，增加了信道利用率。

2. CSMA 協議

? ? ? ? CSMA 協議即載波監聽多路訪問協議，在發送數據前，會監聽信道是否空閑，只有信道空閑時才會發送數據。

? ? ? ? CSMA 協議有很多不同的變種。首先，我們來看 1-堅持 CSMA 協議。它的優點是信道利用率高，一旦信道空閑就會給下一個節點使用。它的缺點是當多個節點準備好數據時，一旦信道空閑，所有節點會同時發送數據，出現沖突的概率大。

?????????在此基礎上，衍生出了?非堅持 CSMA 協議。此時當信道并不空閑時，各個準備好的節點會隨機推遲一段時間再監聽信道，這樣使出現沖突的概率降低了。但缺點是信道剛剛恢復空閑時，可能不會被立即利用，導致信道利用率降低。

? ? ? ? 還有一種 CSMA 協議是?p-堅持 CSMA 協議。它的特點在于當信道空閑時，有一定概率會立刻將數據幀發送到信道上，也有一定概率會推遲一段時間再嘗試發送。它屬于是 1-堅持 CSMA 協議和非堅持 CSMA 協議的中和。

3. CSMA/CD 協議

? ? ? ? CSMA/CD 協議用于早期的有線以太網（總線型）。

? ? ? ? ?上圖中展示了 CSMA/CD 協議中的核心內容，下面我們通過流程圖理解一下這個協議的步驟：

? ? ? ? 流程圖中的過程其實比較容易理解，但有一個概念比較新穎，叫爭用期。這里我們著重解釋一下什么是爭用期。

? ? ? ? 考慮廣播信道中相距最遠的兩個節點，爭用期 = 2 * 最大單向傳播時延（最遠兩個節點間數據傳輸的時間）。CSMA/CD 協議沒有 ACK 機制，如果發送過程中沒有檢測到沖突，就判定發送成功。爭用期的概念是為了讓發送方可以認為，如果在爭用期內沒有檢測到沖突，那么就不可能出現沖突。?

? ? ? ? 或者也可以根據以下步驟，也就是一個簡單的行程問題理解爭用期的概念：

? ? ? ? ?除此之外，我們還要解釋最短幀長的概念。最短幀長 = 2 * 最大單向傳播時延 * 信道帶寬。如果收到的幀長小于最短幀長，則視為無效幀。

? ? ? ? 如果發送的幀小于最短幀長，有可能實際上發生了沖突，但因為沖突信息傳回來的時間過長，導致認為發送成功。

? ? ? ? 有最短幀長，就有最長幀長。這是為了避免有的節點長時間占用信道。一般而言，以太網規定最短幀長為 64 B，最長幀長為 1518 B。

? ? ? ? 剛才我們的流程圖展示的是發送方的任務，現在我們來看接收方的任務，這比較簡單。

?4. CSMA/CA 協議

? ? ? ? 如果說 CSMA/CD 協議的核心在于沖突檢測，那么 CSMA/CA 協議的核心在于沖突避免。CSMA/CA 在發送時不用檢測沖突，發送前想辦法避免沖突。這種協議更適用于無線網絡技術。

? ? ? ? 在介紹該協議之前，我們要先了解什么是 AP。AP 又稱接入點，也就是平時連接的無線 WIFI 熱點。之前我們提過，家用路由器 = 路由器 + 交換機 + AP。所有的移動站點都需要和固定站點的 AP 進行通信。

【提問】為什么移動通信不使用 CSMA/CD 協議呢？

【回答】一方面是因為硬件上很難實現“邊聽邊發，沖突檢測”——因為接收信號的強度往往遠小于發送信號的強度，且在無線介質上信號強度的動態變化范圍很大。

? ? ? ? 另一方面存在“隱蔽站”問題——在無線通信中，并非所有站點都能夠聽見對方。發送節點處沒有沖突不代表在接收節點處不存在沖突。

? ? ? ? 不考慮隱蔽站的情況下，協議要點如下：

? ? ? ? 在協議要點中出現的間隔 DIFS 含義解釋如下：

? ? ? ? ?為了方便理解上面的協議要點，我們使用時間圖幫助理解：

3.6 局域網和 IEEE802

? ? ? ?本節主要討論局域網和 IEEE802 之間的關系。在此之前，我們首先需要了解什么是 IEEE802 委員會。?

3.6.1 局域網的基本概念和體系結構

?????????局域網是一種覆蓋較小的地理范圍，具有較低的時延和誤碼率，在各節點之間以幀為單位進行傳輸，支持單播、廣播、多播的網絡概念。

? ? ? ? 單播指的是一對一發送幀，如 A->B

? ? ? ? 廣播指的是一對全部發送幀，如 A->BCDE...

? ? ? ? 多播指的是一對多發送幀，如 A->BCD

?????????局域網分為有線局域網（LAN）和無線局域網（WLAN）。我們需要關注的是不同網絡的拓撲結構，傳輸介值和介值訪問控制方式。這些內容均可以通過下圖查看。

? ? ? ? 另外，我們還要了解實現局域網的一些硬件架構：一臺計算機和局域網之間的信息傳輸主要通過網絡適配器這個裝置完成。具體的內容可以通過下圖查看。

?3.6.2 以太網和 IEEE802.3

? ? ? ? IEEE802.3 將五層參考模型中的數據鏈路層劃分為介質訪問控制子層和邏輯鏈路控制子層。其中，以太網技術的研究范疇包括物理層和介質訪問控制子層。

? ? ? ? 上圖展示的是 IEEE802.3 推出的以太網物理層標準。重點要關注的是支持全雙工還是半雙工。同軸電纜只能半雙工。雙絞線在速率 < 2.5Gbps 時既可以支持半雙工，也可以支持全雙工；在速率 >= 2.5Gbps 時只能支持全雙工。光纖只支持全雙工。另外，在做題時，默認交換機連接的終端都可以全雙工，集線器連接的終端都只能半雙工。