【網絡原理】第四章 數據鏈路層（二）

二、數據鏈路層的重要功能

   （一）劃分幀的邊界（幀同步）

            ·方法一：字符計數法（面向字符）

               在幀頭用一個計數字段來表示整個幀中字符（包括自己）的個數。

               工作方式：接收方接收到的第一個字符放入計數器中，之后每接收一個字符，計數器的值減                                   一，當計數器減為0時，則幀結束，同時下一幀開始。

               優點：接收機制簡單。

               缺點：每一個幀的定界依賴于前一個幀，一旦一個幀定界出錯，后面的幀就無法定界

             ·方法二：帶字符填充的首位字符定界法（面向字符）

               用DLE STX標志幀的開始，用DLE ETX標志幀的結束

 為了防止誤把數據中的DLE當成開始結束標志，當數據中出現DLE時，把其加倍來填充。

 優點：每個幀單獨定界，一個幀出錯不會影響后面的幀

               缺點：信道浪費大，接收方不能用計數器的方式來判斷結束與否，處理復雜（發送方需要把有                          效數據掃描一遍，防止有dle出現在幀中）。

            ·方法三：帶位填充的首尾標記定界法（面向字符）

                用“01111110”來標識幀的開始和結束

          為了防止誤把數據中的“01111110”當成開始結束標志，數據中每出現5個1，都要在后面補              一個“0”

          例如：0111111001101111101011111000101111110

          優缺點同第二種方法

      ·方法四：物理層編碼違例法（面向字符）

      是適用于物理層編碼有冗余的網絡（如曼徹斯特編碼持續高電平或持續低電平是冗余編碼（二）差錯控制

      1、差錯出現的形式：隨機，連續若干位突發出現

      2、出現差錯的原因：受到了噪聲的干擾（電氣特性變化、信號反射、串擾、大功率電氣的起                                        停（比如熒光燈管開啟突然的大電流））

      3、出錯的形式：

      幀（包括發送幀和響應幀）出錯：接受方接收了，但是數據無效

      幀（包括發送幀和響應幀）丟失：接受方沒有收到

              4、差錯控制的目的：保證幀正確，按序（保證按照發送方發送的原始正確順序提交）提交給                                               上層。

              5、差錯控制方法：

                   在理論上，差錯控制分為自動糾錯和檢錯反饋加重發的機制。在實際網絡當中，用途最廣                    的是第二種，即先通過接收方檢錯，然后接收方通過正向應答的方式進行反饋，對于發送方                  來說，一旦計時器超時，則重發數據。

                 下面對檢錯或糾錯機制進行理論分析。

         如果一個幀如果要發送m位的數據，為了使這m位的數據中出錯的能夠被發現，則需要增加r位             的校驗位，校驗位是與數據沒有直接關系的冗余位，校驗位的增加會導致網絡信道的壓力增大。             我們通常把m+r的數據叫做碼字。

        如果在一個數據中加入了足夠多的校驗位，使得接收方不僅知道有差錯發生，并且知道哪些位               出現了差錯，這種編碼就是糾錯碼（error-correcting code）。但是如果加入了冗余位，使接               收方知道有差錯，但是不知道發生了什么差錯，只能請求重發的方式叫做檢錯碼（error-                       decting code）。

        顯然，為了達到相同的檢錯率，糾錯碼（奇偶校驗碼，每一位數據后都加一位校驗碼）比檢錯               碼（海明碼，每7位數據后加4位校驗碼）加的冗余位多，即占用信道的時間長。

                 在計算機網絡的數據鏈路層中，使用最多的方法被稱為循環冗余校驗法（CRC）。

       6、循環冗余校驗法（CRC，多項式編碼）

           例如：數據110001，表示成多項式為：x^5+x^4+1

           通信的雙方在發送數據之前，要約定一個生成多項式G（x）（在數據鏈路層協議制定時已規               定），其最高位和最低位必須為1,必須比傳輸信息對應的多項式短。

           其基本思想為：CRC加入的r位為檢錯碼（校驗和），加在幀尾，如果滿足約定：加了r位的                 冗余位后，整個多項式n位（m+r位），能夠被生成多項式G（x）整除

       CRC碼算法：

        設生成多項式G（x）為r階，在幀的末尾加r個0（左移r位），使幀為m+r位，相應多項式為                 x^Rm(x)

        按模2除法用對應的G（x）的位串去除對應于x^Rm(x)的位串。

        按模2除法從對應于x^Rm(x)的位串中減去余數（等于或者小于r位），結果就是要傳送的帶校               驗和的多項式T（x）。

                                     即： T（x）= x^Rm(x)+{ x^Rm(x) MOD2 G（x）}

       CRC為什么要把校驗和加在尾部呢？根據算法原理可知，CRC加在尾部可以邊計算邊發送，有              助于提高處理能力。

       CRC的檢錯率不是100%的，當錯誤位串恰好被生成多項式除盡時，則錯誤不能被檢測到。

      （三）流量控制

             1、數據是如何發送的？

                對于發送方而言，當上層要求數據鏈路層傳送數據時，數據鏈路層的發送方會把這個數據構                 成一個幀（數據鏈路層的協議數據單元）。需要注意，數據是下層被動接受的，且這些幀不是               直接送到上層的，而是儲存在緩存中然后發送，當確認幀發送成功時，緩存中的數據才可以刪               除。

               對于接收方而言，同樣有一個緩存，因為數據在提交給高層時必須保證數據的正確，所以需要               在緩存中計算校驗和來確保數據的正確。其次，需要按序提交，如果分段發送，則必須等所有               的幀到達合并完成后才可以向上層提交。當數據正確送到高層并確認收到時，在可以將緩存中               的數據刪除。

              如果采用正向應答加超時重發的機制來進行差錯的檢測與恢復，那么數據的應答發送的時機是              什么時候呢？是在數據提交給高層緩沖區清空之后才會產生應答。

               2、不同層解決的流量控制的問題不同

               H代表主機，R代表路由器。

               流量控制主要所解決的是由于收發方處理能力不匹配而導致接收方沒有足夠的能力處理數據的                問題。

               對于數據鏈路層，其主要解決的是一條物理鏈路直接相連的兩個點（點到點）的問題，網絡層                解決的是源節點到目的節點的問題，而傳輸層要解決的是源主機到目的主機之間（端到端）的                問題。雖然每個層次處理的問題不同，但是處理問題的方法卻是大同小異的。

              3、流量控制的基本方法

               （1）單工停等協議（理想狀況）

                假設理想狀況：通信基于單工信道傳輸，發送方和接收方是固定的，無休止的工作（發送方                   要發送的信息無限多，接收方的緩沖區無限大），且發送速率低于接收速率，通信線路不損                   壞沒有丟失信息幀。（無錯）

                  工作過程：

                      發送過程：取得數據、構成幀、發送幀

                      接收過程：等待、接收幀、送數據給高層

               （2）單工停等協議（無錯情況）

                增加約束條件：接收方不能無休止的接收（如：緩沖區數量有限，接收速率比發送速率低）

                解決辦法：接收方每收到一個幀，給發送方回送應答，發送方收到應答之前不能發送后續                                       幀。

            工作過程：

                       發送過程：取得數據、構成幀、發送幀，等待應答幀

                       接收過程：等待、接收幀、送數據給高層 ，發送應答幀

                （3）單工停等協議（有錯情況）

                 增加約束條件：信道有差錯，信息可能損壞或者丟失。

                 解決辦法：a、使用正向應答+超時重發機制來解決差錯問題

  B、數據序號采用循環序號機制（序號是為了保證數據的連續性，且數據序號會循        環使用）

  C、兩種應答方式：

            單幀應答：應答序號為某一個正確序號（簡化模型使用）

            成批應答：應答序號為下一個期望收到的序號（實際網絡環境使用，分                                析：實際計算機通訊的是雙工通訊，如果需要讓幀正確到達目                              的地，需要加入幀頭幀尾，這樣會造成信道浪費，所以需要讓                              數據幀攜帶應答信息，來避免應答幀單獨成幀浪費帶寬）

在實際情況下，雖然單工停等協議確實能夠流量控制的問題，但是其效率、吞吐率很低。我們能不能想一個辦法把信道本身當作一個緩沖區呢？于是人們發明了連續停等協議（流水線協議）

（4）連續停等協議（流水線協議）

                      工作原理：不需要收到應答幀就可以連續不斷地發送下面的后續幀

                       出錯后處理：

                        處理策略1： 出錯以后，他將重發這個幀后續的所有幀，接收方只需一個緩沖區（全部                                            重發流水線協議）（浪費信道帶寬）

       處理策略2： 出錯以后，他只重發出錯幀，接收方緩沖區需要把之前接收幀緩存起來，                                          等待期望幀的發送，這要求接收方的緩沖區足夠多（選擇重發流水線協議）

                                       （需要足夠大的緩沖區）

                      在實際過程中，流水線協議無法滿足緩沖區動態分配的問題，有可能造成資源分配不足或                      浪費或者出現死鎖的情況。所以出現了目前計算機體系中使用最多的協議——滑動窗口協                        議。

                (5)滑動窗口協議

                  滑動窗口協議是對連續停等協議的改進，他能夠控制已發送但未確認的數據幀的個數（即滑                  動窗口的大小）

                  A、發送窗口

                    窗口尺寸：規定了允許連續發送未應答幀的個數(其尺寸與緩沖區的數量一致)

                   上界（前沿）：下一個發送的序號，即要發送的下一個幀其幀的編號

                   下界（后沿）：下一個應答的序號，即其期望得到的應答幀的序號

                   數據允許發送的條件：上界-下界<窗口的尺寸

                   窗口上界移動的條件：發送數據幀

                   窗口下界移動的條件：收到應答幀

                  其工作原理：假設窗口尺寸為4，在初始時下一個發送序號和下一個期望得到應答的序號都                   是0，現在發送數據。其數據編號取上界的編號，即發送了一個序號為0的幀，則其期望得到                   的序號由0變為了1，即這個窗口的上界滑動了一個單位，這樣不能連續發送，其限制為上界-                下界<窗口的尺寸，這樣就可以控制在未收到應答時允許連續發送數據的個數。這時如果收到                了一個（或多個）應答，則下界會滑動一個（或多個）位置，重新滿足條件，可以繼續發送數                據幀。通過這種方式，可以控制發送的幀小于或等于緩沖區的空間，最大程度上加大效率。

         思考：當收到一個幀，但是這個幀與我們期望的序號不一致，首先要判斷這個幀時重發幀還是后續     幀，重發幀直接丟棄，而后續幀要存在緩沖區中，如果使用循環序號，大小不能區分。即使期望幀的      后續幀到達，因為緩沖區的個數有限，后續幀也不一定會保存，我們要存哪些幀呢？接收窗口會為我      們解決。

               B、接收窗口

                  窗口尺寸：允許連續接收未處理幀的個數（緩沖區大小）

                  數據允許接受的條件：數據序號落在接收窗口中。

                  接收窗口的上下界：對于接收窗口上界和下界的距離是固定不變的，就是接收窗口的尺寸

上期思考題答案：正向應答。如果使用負向應答，發送方通過設定一個特定時間，如果特定時間到了而沒有收到接收方的應答，發送方認為數據正確到達。這個協議存在缺陷。一，如果數據丟失或者應答幀丟失，都會導致發送方錯誤的認為數據已經到達。二，如果每次節點都要判定數據是否到達，則發送的時延增長，整個發送效率變低。如果使用雙向應答，則要在每一個應答幀前加入一個表示來指明數據是正確應答還是錯誤應答，信道利用率會降低，同時由于多加入了一位數據，會增加整體系統處理的復雜性。