計網學習筆記二 Link Layer Service

在上一週的計網學習了network和Internet的總論。在這一週開始的未來幾講將集中在鏈路層link layer，並且會有相應的計網lab完成。在這一講中，我們主要關注鏈路層提供的服務。

課程資料地址：https://cs.nju.edu.cn/lwz/networks/CH2-Direct Link Networks-1.pdf

鏈路層簡介

來學習鏈路層之前，我們先來學一些術語：

• layer-2：即data link layer，一種簡化的稱呼。
• node：節點，包括hosts和routers。
• links：鏈路，連線相鄰節點的通訊通道（communication channel）。link的種類有point-to-point，multiple access和wireless link(WIFI)。
• frame：鏈路層幀，layer-2的封包稱呼，為datagram的封裝（datagram即網路層資料包）。

網路層負責的是任意兩臺主機之間的通訊服務，鏈路層則是負責端到端的通訊服務。

鏈路層實現位置

鏈路層由harware，software和firmware聯合實現，具體裝置在host和router(switch)裡面。鏈路層的實現主體部分是在network adaptor中（網路介面卡，有時稱為網路介面卡，即網路卡），network adaptor的例子有NIC、Ethernet Card、 802.11 Card等。

首先我們來看實現鏈路層硬體部分的網路介面卡。位於網路介面卡核心的是鏈路層控制器（一個晶片，實現了framing，link access， error detection等服務）。

在傳送端，控制器取得了上層網路層發下來的資料包後，根據協定對其封裝，設定差錯檢測位元，並將幀傳進鏈路。

在接收端，控制器接收整個幀，對其進行差錯檢測，抽取出網路層資料包（向上傳是軟體負責）。

上圖即鏈路層的實現位置：網路介面卡硬體和執行在CPU上的軟體。

鏈路層的軟體元件實現了高速鏈路層功能，如組裝鏈路層的定址資訊和負責啟用控制器硬體。鏈路層軟體在接收端負責的工作有響應控制器中斷，處理差錯條件以及將adaptor抽出的資料包向網路層傳遞。

所以，鏈路層可是協定棧中硬體與軟體交接的地方！

鏈路層提供的服務

概括

服務	功能	備註
framing	將網路層資料包封裝成鏈路層幀，由鏈路層協定決定幀的格式結構	不同種通訊（有線和無線）加的頭部資訊都不一樣
link access	通過MAC協定來規定幀在鏈路上的傳輸規則，尤其協調多節點的傳輸	協調多址接入的媒介（coordinate）；使用MAC來確定區域性地址；Half-duplex and full-duplex 即半雙工和全雙工，收發同時進行
reliable delivery	保證無差錯經鏈路層移動每個網路層資料包	易於產生高差錯率的鏈路會實現服務，如無線傳輸，反之光纖這樣的可靠傳輸就很少實現這個服務；還有流控機制
error detection && correction	差錯檢測服務給幀提供差錯檢測欄位，讓接收方可以檢測幀中的位元差錯；差錯糾正則可以準確定位差錯位置並進行糾正。	用來處理因噪聲和訊號衰減所造成的錯誤；傳送訊號用以重傳或者把幀丟棄；這個服務實現不是必須的，但因為容易實現所以大多數都實現了

Framing 成幀

framing比較好理解，就是傳送端將網路層傳下來的資料包進行封裝，加上一些資訊例如像差錯檢測位元，流控（flow control）欄位等；接收端就接收完整個幀後，根據封裝資訊進行差錯檢測，流控設定等操作，再抽出資料包傳到網路層。

Link access 鏈路接入

鏈路接入有兩種方式：point-to-point對等鏈路接入 和 broadcast廣播鏈路接入。

點到點鏈路接入是一種專用接入（只有單個傳送方和單個接收方），它廣泛用於長距離纜線連線，以及大部分的乙太網技術。

而廣播鏈路接入能夠讓多個傳送方和接收方共用相同的單一的廣播通道，如傳統的乙太網和WLAN。這種接入方式會產生一個多路存取問題（Multiple access problem）：

因為所有的節點都能傳輸幀，所以多個節點同時傳輸幀時，通道上的所有節點同時收到多個幀。此時就會在接收處發生幀的碰撞（即collisions）。這就導致碰撞的幀都丟失了，而且在碰撞時間間隔內通道也被浪費了。

這就需要協調多個節點對一個共用廣播通道的存取。解決這個問題我們提出了MAC協定。它可以劃分為三種型別：

• Channel partitioning：通道劃分協定。物理媒介角度上切片，均勻頻率。
• Taking turns：輪流協定。時間角度上切，頻率不均勻。
• Random access：隨機接入協定。前面兩種可能造成通道的浪費，這類協定允許衝突存在，併為衝突提供解決機制。

我們在這講先不詳細介紹，不然很難一下子消化。留到後面MAC的時候再寫寫。

Reliable delivery 可靠交付

對於這個服務的實現我們採用流控機制（flow control）。它可以確保我們的接收方不會被傳送的幀給淹沒，即預防接收方的buffer產生溢位。實現這個機制我們主要有兩種協定：

1.Stop and Wait

這可以說是最早的鏈路層協定。它的實現很簡單，對大的封包傳輸的效率很不錯（因為返回ACK資訊的耗時和傳輸封包的耗時相比不值一提），但ACK（「確定收到」資訊）返回耗時對小包來說是耗不起的。它的過程就是你來我往一下一下，如下：

2.Sliding Window

我們直譯是滑動視窗。相比於stop&wait協定的一次一包，滑動視窗協定每次傳輸都是一次發一批。

在這個協定中，有幾個要點：

• 幀上有一個k位的欄位，k的範圍是0-8，用來做幀的序號2^k（0-255）；
• 接收方有一個buffer，即window，它的大小為win個幀，win <= 2^k；
• 傳送端可以在沒收到ACK的時候最多傳送win個幀。
• ACK後面的數位表示：傳送端你可以發n號幀了；

我們來看看滑動視窗是怎麼操作的：

然後滑動視窗對資料丟失的處理又細分為兩種協定：

• GO-BACK-N：回退N協定。絕大多數硬體採用了這種實現（因為它的演演算法非常符合硬體，移位元運算）
• Selective Reject：選擇重傳協定。少用，接收方需保有較大的足夠的buffer。

我們可以來看這兩篇文章：

[What is a Sliding Window Protocol in Computer Network ](https://www.tutorialspoint.com/what-is-a-sliding-window-protocol-in-computer-network sliding window is also known as windowing.,Layer (OSI model) or Transmission Control Protocol (TCP).)

資料鏈路層-Data Link Layer：拆分位元流的成幀方法/滑動視窗協定/回退N協定/選擇重傳協定

Error detection and correction 差錯檢測和糾正

我們在鏈路層中實現的差錯檢測為位元級差錯檢測。一般在framing過程中我們把EDC欄位加到資料包的末尾，它的檢測邏輯如下：

可以說EDC越大，它給予的檢測效果就越可靠。我們有兩種主要的方法：

Parity Checking

奇偶檢驗。這差不多是最簡單的檢測方法，如果採用的是單個奇偶校驗位，位的值取決於資料中1的數目是否為奇數/偶素。而二維奇偶檢測的魯棒性比一維的更高，它將資料劃分為行列分佈，並且按照行列來設定校驗位，這可以讓接收方根據行列位置進行對差錯bit的修正。

Cyclic Redundancy Check

即CRC，迴圈冗餘檢測編碼。詳細操作如下：

這一講就先寫這麼多，不然回看的時候沒法消化……（第一講寫得太爛了）