【網(wǎng)絡(luò)原理】第四章 數(shù)據(jù)鏈路層（二）

二、數(shù)據(jù)鏈路層的重要功能

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

            ·方法一：字符計數(shù)法（面向字符）

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

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

               優(yōu)點：接收機制簡單。

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

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

               用DLE STX標(biāo)志幀的開始，用DLE ETX標(biāo)志幀的結(jié)束

 為了防止誤把數(shù)據(jù)中的DLE當(dāng)成開始結(jié)束標(biāo)志，當(dāng)數(shù)據(jù)中出現(xiàn)DLE時，把其加倍來填充。

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

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

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

                用“01111110”來標(biāo)識幀的開始和結(jié)束

          為了防止誤把數(shù)據(jù)中的“01111110”當(dāng)成開始結(jié)束標(biāo)志，數(shù)據(jù)中每出現(xiàn)5個1，都要在后面補              一個“0”

          例如：0111111001101111101011111000101111110

          優(yōu)缺點同第二種方法

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

      是適用于物理層編碼有冗余的網(wǎng)絡(luò)（如曼徹斯特編碼持續(xù)高電平或持續(xù)低電平是冗余編碼（二）差錯控制

      1、差錯出現(xiàn)的形式：隨機，連續(xù)若干位突發(fā)出現(xiàn)

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

      3、出錯的形式：

      幀（包括發(fā)送幀和響應(yīng)幀）出錯：接受方接收了，但是數(shù)據(jù)無效

      幀（包括發(fā)送幀和響應(yīng)幀）丟失：接受方?jīng)]有收到

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

              5、差錯控制方法：

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

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

         如果一個幀如果要發(fā)送m位的數(shù)據(jù)，為了使這m位的數(shù)據(jù)中出錯的能夠被發(fā)現(xiàn)，則需要增加r位             的校驗位，校驗位是與數(shù)據(jù)沒有直接關(guān)系的冗余位，校驗位的增加會導(dǎo)致網(wǎng)絡(luò)信道的壓力增大。             我們通常把m+r的數(shù)據(jù)叫做碼字。

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

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

                 在計算機網(wǎng)絡(luò)的數(shù)據(jù)鏈路層中，使用最多的方法被稱為循環(huán)冗余校驗法（CRC）。

       6、循環(huán)冗余校驗法（CRC，多項式編碼）

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

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

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

       CRC碼算法：

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

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

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

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

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

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

      （三）流量控制

             1、數(shù)據(jù)是如何發(fā)送的？

                對于發(fā)送方而言，當(dāng)上層要求數(shù)據(jù)鏈路層傳送數(shù)據(jù)時，數(shù)據(jù)鏈路層的發(fā)送方會把這個數(shù)據(jù)構(gòu)                 成一個幀（數(shù)據(jù)鏈路層的協(xié)議數(shù)據(jù)單元）。需要注意，數(shù)據(jù)是下層被動接受的，且這些幀不是               直接送到上層的，而是儲存在緩存中然后發(fā)送，當(dāng)確認(rèn)幀發(fā)送成功時，緩存中的數(shù)據(jù)才可以刪               除。

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

              如果采用正向應(yīng)答加超時重發(fā)的機制來進行差錯的檢測與恢復(fù)，那么數(shù)據(jù)的應(yīng)答發(fā)送的時機是              什么時候呢？是在數(shù)據(jù)提交給高層緩沖區(qū)清空之后才會產(chǎn)生應(yīng)答。

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

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

               流量控制主要所解決的是由于收發(fā)方處理能力不匹配而導(dǎo)致接收方?jīng)]有足夠的能力處理數(shù)據(jù)的                問題。

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

              3、流量控制的基本方法

               （1）單工停等協(xié)議（理想狀況）

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

                  工作過程：

                      發(fā)送過程：取得數(shù)據(jù)、構(gòu)成幀、發(fā)送幀

                      接收過程：等待、接收幀、送數(shù)據(jù)給高層

               （2）單工停等協(xié)議（無錯情況）

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

                解決辦法：接收方每收到一個幀，給發(fā)送方回送應(yīng)答，發(fā)送方收到應(yīng)答之前不能發(fā)送后續(xù)                                       幀。

            工作過程：

                       發(fā)送過程：取得數(shù)據(jù)、構(gòu)成幀、發(fā)送幀，等待應(yīng)答幀

                       接收過程：等待、接收幀、送數(shù)據(jù)給高層 ，發(fā)送應(yīng)答幀

                （3）單工停等協(xié)議（有錯情況）

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

                 解決辦法：a、使用正向應(yīng)答+超時重發(fā)機制來解決差錯問題

  B、數(shù)據(jù)序號采用循環(huán)序號機制（序號是為了保證數(shù)據(jù)的連續(xù)性，且數(shù)據(jù)序號會循        環(huán)使用）

  C、兩種應(yīng)答方式：

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

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

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

（4）連續(xù)停等協(xié)議（流水線協(xié)議）

                      工作原理：不需要收到應(yīng)答幀就可以連續(xù)不斷地發(fā)送下面的后續(xù)幀

                       出錯后處理：

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

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

                                       （需要足夠大的緩沖區(qū)）

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

                (5)滑動窗口協(xié)議

                  滑動窗口協(xié)議是對連續(xù)停等協(xié)議的改進，他能夠控制已發(fā)送但未確認(rèn)的數(shù)據(jù)幀的個數(shù)（即滑                  動窗口的大小）

                  A、發(fā)送窗口

                    窗口尺寸：規(guī)定了允許連續(xù)發(fā)送未應(yīng)答幀的個數(shù)(其尺寸與緩沖區(qū)的數(shù)量一致)

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

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

                   數(shù)據(jù)允許發(fā)送的條件：上界-下界<窗口的尺寸

                   窗口上界移動的條件：發(fā)送數(shù)據(jù)幀

                   窗口下界移動的條件：收到應(yīng)答幀

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

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

               B、接收窗口

                  窗口尺寸：允許連續(xù)接收未處理幀的個數(shù)（緩沖區(qū)大?。?/span>

                  數(shù)據(jù)允許接受的條件：數(shù)據(jù)序號落在接收窗口中。

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

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