【网络原理】第四章 数据链路层（二）

二、数据链路层的重要功能

   （一）划分帧的边界（帧同步）

            ·方法一：字符计数法（面向字符）

               在帧头用一个计数字段来表示整个帧中字符（包括自己）的个数。

               工作方式：接收方接收到的第一个字符放入计数器中，之后每接收一个字符，计数器的值减                                   一，当计数器减为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、接收窗口

                  窗口尺寸：允许连续接收未处理帧的个数（缓冲区大小）

                  数据允许接受的条件：数据序号落在接收窗口中。

                  接收窗口的上下界：对于接收窗口上界和下界的距离是固定不变的，就是接收窗口的尺寸

上期思考题答案：正向应答。如果使用负向应答，发送方通过设定一个特定时间，如果特定时间到了而没有收到接收方的应答，发送方认为数据正确到达。这个协议存在缺陷。一，如果数据丢失或者应答帧丢失，都会导致发送方错误的认为数据已经到达。二，如果每次节点都要判定数据是否到达，则发送的时延增长，整个发送效率变低。如果使用双向应答，则要在每一个应答帧前加入一个表示来指明数据是正确应答还是错误应答，信道利用率会降低，同时由于多加入了一位数据，会增加整体系统处理的复杂性。