數據鏈路層-上篇

概述

咱們首先來看看數據鏈路層在網絡體系結構中的地位。算法

如圖所示，主機H1向主機H2發送數據，中間要通過3個路由器和電話網、局域網、廣域網等多種網絡。緩存

從五層協議原理體系結構的角度來看，主機應具備體系結構中的各個層次。網絡

而路由器僅需具備體系結構中下面三層，各設備經過物理層下面的傳輸媒體進行互連。併發

當主機H1向H2發送數據時，主機H1將待發送的數據逐層封裝後，經過物理層將構成數據包的各比特轉換爲電信號，發送到傳輸媒體。性能

數據包進入路由器後，由下往上逐層解封到網絡層。路由器根據數據包的目的網絡地址和自身轉發表，肯定數據報的轉發端口。而後從網絡層向下逐層封裝數據包，並經過物理層將數據包發送到傳輸媒體。編碼

數據包最終到達主機H2時，還要由下往上逐層解封，最終解封出主機H1所發送的數據。spa

主機H1到H2的通訊，能夠當作是在4段不一樣的鏈路上的通訊組成的。計算機網絡

所謂鏈路（Link）就是從一個結點到相鄰結點的一段物理線路，而中間沒有任何其餘的交換節點。隊列

僅有鏈路還不夠，還須要一些通訊協議來控制這些數據的傳輸。資源

數據鏈路（Data Link）是指把視線通訊協議的硬件和軟件加到鏈路上，就構成了數據鏈路。

在數據鏈路層上傳輸的數據包，又稱爲幀。

也就是說，數據鏈路層是以幀爲單位傳輸和處理數據。

數據鏈路層的三個重要問題

數據鏈路層傳送的協議數據單元是幀

封裝成幀

• 封裝成幀 (framing) 就是在一段數據的先後分別添加首部和尾部，而後就構成了一個幀。
• 首部和尾部的一個重要做用就是進行幀定界。

差錯控制

發送方將封裝好的幀經過物理層發送到傳輸媒體，在傳輸過程當中可能會產生比特差錯：1 可能會變成 0， 而 0 也可能變成 1。

可是，接收方主機如何判斷幀在傳輸過程當中是否出現誤碼？

這能夠經過檢錯碼來發現。發送方在發送幀以前，基於待發送的數據和檢錯算法計算出檢錯碼。並將其封裝在幀尾。

可靠傳輸

接收方主機收到有誤碼的幀後，是不會接受該幀的，會將它丟棄。

若是數據鏈路層向其上層提供的是不可靠服務，那麼丟棄就丟棄了，不會再有更多措施。

若是數據鏈路層向其上層提供的是可靠服務，那就還須要其餘措施，來確保接收方主機還能夠從新收到被丟棄的這個幀的正確副本。

以上三個問題都是使用 點對點信道的數據鏈路層來舉例的

若是使用廣播信道的數據鏈路層除了包含上面三個問題外，還有一些問題要解決

如圖所示，主機A，B，C，D，E經過一根總線進行互連，主機A要給主機C發送數據，表明幀的信號會經過總線傳輸到總線上的其餘各主機，那麼主機B，D，E如何知道所收到的幀不是發送給它們的，主機C如何知道發送的幀是發送給本身的？

能夠用編址（地址）的來解決。將幀的目的地址添加在幀中一塊兒傳輸。

另外還有數據碰撞問題。

當總線上多臺主機同時使用總線來傳輸幀時，這是採用廣播信道的共享式局域網不可避免的。

隨着技術的發展，交換技術的成熟，

在 有線（局域網）領域 使用點對點鏈路和鏈路層交換機的交換式局域網取代了共享式局域網。

在無線局域網中仍然使用的是共享信道技術。

封裝成幀

封裝成幀是指數據鏈路層給上層交付的協議數據單元添加幀頭和幀尾使之成爲幀。

幀頭和幀尾中包含有重要的控制信息。

發送方的數據鏈路層將上層交付下來的協議數據單元封裝成幀後，還要經過物理層，將構成幀的各比特，轉換成電信號交給傳輸媒體，那麼接收方的數據鏈路層如何從物理層交付的比特流中提取出一個個的幀？

實際上，幀頭和幀尾的做用之一就是幀定界。

但比不是每一種數據鏈路層協議的幀都包含有幀定界標誌，例以下面例子：

前導碼

• 前同步碼：做用是使接收方的時鐘同步
• 幀開始定界符：代表其後面緊跟着的就是MAC幀

另外以太網還規定了幀間間隔爲96比特時間，所以，MAC幀不須要幀結束定界符。

接下來咱們介紹透明傳輸的問題，透明傳輸是指數據鏈路層對上層交付的傳輸數據沒有任何限制，就好像數據鏈路層不存在同樣。

幀界定標誌也就是個特定數據值，若是在上層交付的協議數據單元中， 剛好也包含這個特定數值，接收方就不能正確接收。

因此數據鏈路層應該對上層交付的數據有限制，其內容不能包含幀定界符的值。

解決透明傳輸問題

解決方法：面向字節的物理鏈路使用字節填充 (byte stuffing) 或字符填充 (character stuffing)，面向比特的物理鏈路使用比特填充的方法實現透明傳輸。

發送端的數據鏈路層在數據中出現控制字符「SOH」或「EOT」的前面插入一個轉義字符「ESC」(其十六進制編碼是1B)。

接收端的數據鏈路層在將數據送往網絡層以前刪除插入的轉義字符。

若是轉義字符也出如今數據當中，那麼應在轉義字符前面插入一個轉義字符 ESC。當接收端收到連續的兩個轉義字符時，就刪除其中前面的一個。

爲了提升幀傳輸的效率，應當使幀的數據部分的長度儘量大些。

考慮到差錯控制等多種因素，每一種數據鏈路層協議都規定了幀的數據部分的長度上限，即最大傳送單元MTU（Maximum Transfer Unit）。

差錯檢測

介紹

咱們知道，實際的通訊鏈路都不是理想的，比特在傳輸過程當中可能出現差錯：1可能會變成0，而0可能會變成1。這稱爲比特差錯。

在一段時間內，傳輸錯的比特佔所傳輸比特總數比率稱爲誤碼率BER（Bit Error Rate）

使用差錯檢測碼來檢測數據在傳輸過程當中是否產生了比特差錯，是數據鏈路層所要解決的重要問題之一。

奇偶校驗

在待發送的數據後面添加1位奇偶校驗位，使整個數據（包括所添加的校驗位在內）中"1"的個數爲奇數（奇校驗）或偶數（偶校驗）。

經過下面例子能夠看出：

若是有奇數個位發生誤碼，則奇偶性發生變化，能夠檢測出誤碼。

若是有偶數個位發生誤碼，則奇偶性不發生變化，不能檢測出誤碼（漏檢）。

因爲奇偶校驗的漏檢率比較高，所以計算機網絡的數據鏈路層通常不會採用這種檢測方法。

循環冗餘校驗CRC(Cyclic Redundancy Check)

這是一種具備很強檢錯能力的檢錯方法，漏檢率極低。

• 收發雙方約定好一個生成多項式G(x)；
• 發送方基於待發送的數據和生成多項式計算出差錯檢測碼（冗餘碼），將其添加至待傳輸數據後面一塊兒傳輸；
• 接收方經過生成多項式來計算收到的數據是否產生了誤碼；

總結

• 檢錯碼只能檢測出幀在傳輸過程當中出現了差錯，但並不能定位錯誤，所以沒法糾正錯誤。
• 要想糾正傳輸中的差錯，可使用冗餘信息更多的糾錯碼進行前向糾錯。但糾錯碼的開銷比較大，在計算機網絡中較少使用。
• 循環冗餘校驗CRC有很好的檢錯能力（漏檢率很是低），雖然計算比較複雜，但很是易於用硬件實現，所以被普遍應用於數據鏈路層。
• 在計算機網絡中一般採用咱們將要討論的檢錯重傳方式來糾正傳輸中的差錯，或者僅僅是丟棄檢測到差錯的幀，這取決於數據鏈路層向其上層提供的是可靠傳輸服務仍是不可靠傳輸服務。

循環冗餘校驗 CRC 是一種檢錯方法，而幀校驗序列 FCS 是添加在數據後面的冗餘碼。

可靠傳輸

基本概念

當檢測出幀中出現了比特差錯，那麼，接下來該如何處理呢？這取決於數據鏈路層向其上層提供的服務類型。

若是提供的是不可靠傳輸服務：僅僅丟棄有誤碼的幀，其餘什麼也不作。

若是提供的是可靠傳輸服務：想辦法實現發送端發送什麼，接收端就接收什麼。

通常狀況下，有線鏈路的誤碼率比較低，爲了減小開銷，並不要求數據鏈路層向上提供可靠傳輸服務，即便出現了誤碼，可靠傳輸的問題也由其上層處理。

然而，無線鏈路易受干擾，誤碼率比較高，所以要求數據鏈路層必須向上層提供可靠傳輸服務。

須要說明的是比特差錯只是傳輸差錯中的一種。

從整個計算機網絡體系結構來看，傳輸差錯還包括分組丟失、分組失序以及分組重複。

• 分組丟失：路由器輸入隊列快滿了，主動丟棄收到的分組。
• 分組失序：數據並未按照發送順序依次到達接收端。
• 分組重複：因爲某些緣由，有些分組在網絡中滯留了，沒有及時到達接收端，這可能會形成發送端對該分組的重發，重發的分組到達接收端，但一段時間後，滯留在網絡的分組也到達了接收端，這就形成分組重複的傳輸差錯。

分組丟失、分組失序以及分組重複這些傳輸差錯，通常不會出如今數據鏈路層，而會出如今其上層。

可靠傳輸服務並不只侷限於數據鏈路層，其餘各層都可選擇實現可靠傳輸。

三種可靠協議

• 中止-等待協議SW
• 回退N幀協議GBN
• 選擇重傳協議SR

這三種可靠傳輸實現機制的基本原理並不只限於數據鏈路層，能夠應用到計算機網絡體系結構的各層協議中。

中止-等待協議SW

確認與否定

以下圖所示，收發雙方基於互聯網通訊，而不是侷限於一條點對點的數據鏈路。

發送方給接收方發送數據分組，接收方收到後對其進行差錯檢測，如沒有誤碼，則接受該數據分組，並給發送方發送確認分組，簡稱爲ACK。

發送方收到對所發送數據分組的確認分組後，才能發送下一個數據分組。

假設這個數據分組在傳輸過程當中出現了誤碼，接收方收到後對其進行差錯檢測，發現了誤碼，則丟棄該分組。並給發送方發送否定分組，簡稱NAK。

發送方收到對所發送數據分組的否定分組後，就知道了本身以前發送的數據分組出現了差錯而被接收方拒絕，因而馬上重傳該數據分組。

所以發送方每發送完一個數據分組後，並不能馬上將該數據分組從緩存中刪除，只有在收到針對該數據分組的確認分組後，才能夠將其從緩存中刪除。隨後發送下一個數據分組。

超時重傳

發送方給接收方發送數據分組，然而該數據分組在傳輸過程當中丟失了。

須要說明的是，對於數據鏈路層點對點信道而言，不太容易出現這種狀況。

但對於多個網絡經過多個路由器互連的複雜互聯網環境而言，是會常常出現的。

接收方收不到數據分組，就不會發送ACK或者NAK。若是不採起其它措施，發送方就會一直處於等待接收方ACK或者NAK的狀態。

爲解決該問題，能夠在發送方發送完一個數據分組後，啓動一個超時計時器。若到了超時計時器所設置的重傳時間而發送方仍沒有收到接收方的ACK或NAK，則重傳原來的數據分組，這就叫作超時重傳。

通常可將重傳時間設置爲略大於"從發送方到接收方的平均往返時間"。

• 在數據鏈路層點對點的往返時間比較肯定，重傳時間比較好設定。
• 然而在運輸層，因爲端到端往返時間很是不固定，設置合適的重傳時間並不容易。

確認丟失

到目前爲止，貌似基於中止等待、使用確認或否定分組，再加上超時重傳的手段，就能夠實現可靠傳輸了。

但請你們思考一下，是否還會出現目前手段不足以應對實現可靠傳輸的狀況呢？

既然發送方發送的數據分組可能丟失，那麼接收方放的確認或否定分組也可能丟失。

當接收方發送ACK或NAK丟失時候，必然會形成發送方對以前所發送數據分組的超時重傳。

那麼接收方如何判斷該數據分組是不是一個重複分組呢？

爲避免分組重複這種傳輸錯誤，必須給每一個分組帶上序號。

對於中止-等待協議，因爲每發送一個數據分組就中止等待，只要保證每發送一個新的數據分組，其發送序號與上次發送的數據分組的序號不一樣便可。

所以，使用一個比特來編號就夠了。

確認遲到

既然發送分組須要編號，那麼確認分組是否也須要編號呢？

咱們來看這種狀況，發送方發送0號數據分組，接收方正確接收後，給發送方發送確認分組。因爲某些緣由，該分組遲到了。

這必然會致使發送方進行超時重傳，在重傳0號數據分組的傳輸過程當中，發送方接收到遲到了確認分組。因而發送1號數據分組。

接收方收到數據分組後，發現是一個重複的數據分組，則丟棄。並針對該數據分組發送確認分組，以避免再次超時重傳。

咱們能夠清楚地看到，這是對0號數據的重複確認。

可是發送方又如何知道呢？若是不採起其它措施的話，發送方會誤認爲這是對1號數據分組的確認分組。

若是對確認分組也進行編號，就能夠解決這種誤判。

對於數據鏈路層的點對點信道，往返時間比較固定，不會出現確認遲到的狀況，能夠不用給確認分組編號。

像中止-等待協議這樣經過確認和重傳機制實現的可靠傳輸協議，常稱爲自動請求重傳協議ARQ( Automatic Repeat re Quest)，意思是重傳的請求是自動進行，由於不須要接收方顯式地請求，發送方重傳某個發送的分組。

回退N幀協議GBN

爲何使用回退N幀協議？

由於中止-等待協議的信道利用率很低，若出現超時重傳，則信號利用率更低。

在相同的時間內，使用中止-等待協議的發送方只能發送一個數據分組，而採用流水線傳輸的發送方，能夠發送多個數據分組。

回退N幀協議在流水線傳輸的基礎上，利用發送窗口來限制發送方可連續發送數據分組的個數。

無差錯狀況流程

發送方將序號落在發送窗口內的0~4號數據分組，依次連續發送出去。

他們通過互聯網傳輸正確到達接收方，沒有亂序和誤碼，接收方按序接收它們，每接收一個，接收窗口就向前滑動一個位置，並給發送方發送針對所接收分組的確認分組，再經過互聯網的傳輸正確到達了發送方。

發送方每接收一個、發送窗口就向前滑動一個位置，這樣就有新的序號落入發送窗口，發送方能夠將收到確認的數據分組從緩存中刪除了，而接收方能夠擇機將已接收的數據分組交付上層處理。

使用回退N幀協議的接收方，能夠採用累積確認的方式。也就是說，接收方不必定要對收到的數據分組逐個發送確認，而是能夠在收到幾個數據分組後，對按序到達的最後一個數據分組發送確認，ACKn表示序號爲n及之前的數據分組都已正確接收。

假設發送方發送0-4號數據分組，正確到達接收方後進行發送確認分組，好比當確認到1號數據分組時，給發送方發送了一個累計確認ACK1，隨後進行後續接受完2-4號數據分組後，又發送了一個ACK4。

即便ACK1在發送給發送方時丟失了，當ACK4到達發送方時，也能夠知道序號爲4及之前的數據已經被接收方正確接收了。發送方就能夠將收到確認分組的數據從緩存中刪除。

累計確認的優缺點：

優勢:

• 即便確認分組丟失，發送方也可能沒必要重傳
• 減少接收方的開銷
• 減少對網絡資源的佔用

缺點：

• 不能向發送方及時反映出接收方已經正確接收的數據分組信息

有差錯狀況

例如，在傳輸數據分組時，5號數據分組出現誤碼，接收方經過數據分組中的檢錯碼發現了錯誤。

因而丟棄該分組，然後續到達的這剩下四個分組與接收窗口的序號不匹配。

接收方一樣也不能接收它們，將它們丟棄，並對以前按序接收的最後一個數據分組進行確認，發送ACK4，每丟棄一個數據分組，就發送一個ACK4。

當收到重複的ACK4時，就知道以前所發送的數據分組出現了差錯，因而能夠不等超時計時器超時就馬上開始重傳，具體收到幾個重複確認就馬上重傳，根據具體實現決定。

若是收到這4個重複的確認並不會觸發發送方馬上重傳，一段時間後。超時計時器超時，也會將發送窗口內已發送過的這些數據分組所有重傳。

在本例中，儘管序號六、七、0、1的數據分組正確到達接收方方，但因爲5號數據分組誤碼不被接受，它們也會受牽連而不被接受，發送方還要重傳這些數據分組，這就是所謂的GO-back_N（回退N幀）。

可見，當通訊線路信號很差時，回退N幀協議的信道利用率並不比中止-等待協議高。

總結

• 回退N幀協議在流水線傳輸的基礎上利用發送窗口來限制發送方連續發送數據分組的數量，是一種連續ARQ協議。
• 在協議的工做過程當中發送窗口和接收窗口不斷向前滑動，所以這類協議又稱爲滑動窗口協議。

選擇重傳協議SR

回退N幀協議的接收窗口尺寸WR只能等於1，所以接收方只能按序接收正確到達的數據分組。

一個數據分組的誤碼就會致使其後續多個數據分組不能被接收方按序接收而丟棄（儘管它們無亂序和誤碼）。這必然會形成發送方對這些數據分組的超時重傳，顯然這是對通訊資源的極大浪費。

爲了進一步提升性能，可設法只重傳出現誤碼的數據分組。所以，接收窗口的尺寸WR不該再等於1而應該大於1，以便接收方先收下失序到達但無誤碼而且序號落在接收窗內的那些數據分組，等到所缺分組收齊後再進一併送交給上層。這就是選擇重傳協議。

須要注意的是： 選擇重傳協議爲了使發送方僅重傳出現差錯的分組，接收方 不能再使用累計確認，而須要對每一個正確接收到的數據分組進行 逐一確認

假設採用3個比特給分組編序號，所以序號的取值範圍是0-7，當序號到達7時再從0開始。

接收方的WR通常可與發送窗口的尺寸WT取值相同

發送方將數據分組按序發送出去，通過互聯網傳輸後陸續到達接收方，但其中2號數據分組丟失了。

只要序號落入接收窗口內且無誤碼的數據分組，接收方都會接收。

接收方接收0號和1號數據分組，併發送0號和1號確認分組，接收窗口向前滑動兩個位置，這樣就有4和5這兩個新的序號落入接收窗口。

接收方接收3號分組，併發送3號確認分組，但接收窗口不能向前滑動，由於3號數據分組是未按序到達的數據分組。

這些確認分組通過互聯網的傳輸陸續到達發送方。發送方每按序收到一個確認分組，發送窗口就向前滑動一個位置。

發送方接收0號和1號確認分組，發送窗口向前滑動兩個位置。這樣就有4和5這兩個新的序號落入發送窗口。

發送方將序號落入發送窗口的4號和5號數據發送出去。這時發送方就能夠刪除0號和1號數據緩存。

接收方可擇機將已接收到的0和1交付給上層處理。

發送方接收3號確認分組，但發送窗口不能向前滑動，由於這是一個未按序到達的確認分組，發送方還未收到它以前的2號確認分組。不過須要記錄3號數據分組已收到確認，這樣該數據分組就不會超時重發。

隨後接收方接收4號和5號數據分組，併發送4號和5號確認分組，但接收窗口不能向前滑動，由於它們是未按序到達的數據分組。接收方還沒收到它們以前的2號數據分組。

隨後發送方會針對2號數據進行超時重發，此時發送方也接收到了4號和5號的確認分組，但發送窗口不能向前滑動，由於由於這是一個未按序到達的確認分組，發送方還未收到它以前的2號確認分組。不過須要記錄4號和5號數據分組已收到確認，這樣該數據分組就不會超時重發。

隨後接收方接收到2號數據分組，接受窗口就能夠向前滑動4個位置，這樣六、七、0、1這四個新的序號落入接收窗口。

2號確認分組通過互聯網的傳輸到達發送方，發送方接收該確認分組，發送方窗口能夠向前滑動4個位置。這樣六、七、0、1這四個新的序號落入發送窗口。

這樣就能夠繼續發送接下來的數據了，而且從緩存中刪除以前的數據分組。

總結

若是發送窗口和接收窗口的尺寸超過了取值範圍，就會使接收方沒法分辨新、舊數據分組，進而出現分組重複這種傳輸差錯。