计网数据链路层学习笔记

计网数据链路层学习笔记

Last updated on

12559 字 约 63 分钟

1.封装成帧

1.1.数据帧

通过对计算机网络体系结构的了解，我们可以知道，以OSI体系结构为例，当前主机将要传输给目标主机的数据将会自应用层向下逐级传递，其中对于中间的运输层、网络层等，都会在目标数据的基础上添加协议首部。其中对于数据链路层，添加的数据链路层协议首部，我们将其简称为帧头和帧尾。对于添加了帧头和帧尾之后的整组数据，我们称之为数据帧。

帧头
数据
帧尾
数据帧

帧头和帧尾的作用是什么？简要来说，就是存储数据相关的信息。比如说，数据从哪里发出，即主机源地址；发往哪里，即目标主机地址；数据在传输过程中有没有误码的出现；区分多段数据之间的边界，等等。

1.2.帧定界

我们在上面所说的，帧头和帧尾用于区分多端数据之间的边界，称作帧定界。

在这里，我们以PPP协议的帧格式为例

PPP帧

对于PPP帧，在帧头的首部和帧尾的尾部，分别具有1字节的帧定界标志。当目标主机接收到数据，即可通过帧定界标志将连续的数据拆分为正确的小段，处理去掉帧头和帧尾之后将IP数据报向上传递。

需要注意的是，并非每种协议的帧格式中都具有帧定界标志，例如对于以太网V2的MAC帧，它不具备帧定界标志，而是通过在数据前端添加前导码，并设置帧间间隔时间以达到相同的作用。

以太网MAC帧

此处我们列出四种常见的帧定界实现方法：

1.2.1.字符计数法(Character Count)

这种做法非常简单：在帧头部放一个字段，用于表明本帧一共包含多少个字符

比如说在头部放一个5，则接收方再往后数4个字符，将这几个字符视作一个帧。

缺点：当传输过程中只要发生一次该字段的翻转，将会导致后面的帧全部错位，极度脆弱且不稳定，目前几乎不再使用。

1.2.2.字符填充法(Character Stuffing)

  • 原理：定义一个特殊的控制字符(比如SOH表示帧开始，EOT表示帧结束)
  • 转义(填充)：若数据本身含有控制字符，则在其前端填充一个转义字符用于区分帧定界和数据
  • 缺点：依赖于具体字符集，对于非字符的纯二进制数据，较为低效

1.2.3.比特填充法(Bit Stuffing)

  • 标志流：定义一个特定的比特组合为起始和结束的标志，通常为01111110
  • 5 save 1规则(零比特填充)：
    • 发送方：在传输数据时，只要扫描到连续的5个1，不管后面紧跟的是0还是1，都强制在后面塞入一个0
    • 接收方：在接收时，只要看到连续的5个1，如果是0，就将这个0删掉，恢复原貌；如果是1，就知道帧结束了
  • 优势：实现了透明传输，即数据链路层对上层交付的传输数据没有任何限制。显然我们可以知道，无法实现透明传输的数据链路层协议的实用性将会大打折扣。

1.2.4.违例编码法(Physical Layer Coding Violations)

这个方法利用物理层编码的”漏洞”来做定界，是目前局域网(比如以太网)的常用手段

  • 原理：像曼彻斯特编码(Manchester Encoding)，每个比特周期中间必须有一次电平跳变(低到高为0，高到低为1)
  • 定界方式：利用一种”既不跳变，也不符合0和1规范”的错误电平信号，作为帧的边界标记(如IEEE 802.5 令牌环网)
  • 优势：零额外数据开销，高效直接

2.差错检测

2.1.为什么需要差错检测

在数据传输的过程中，会因为各种各样的因素，导致传输的比特流的某些位置发生了翻转，这些位置称为误码。

显然，我们不能直接接收可能产生误码的数据，需要使用某种方法来检测传输数据中是否存在错误，从而决定是直接丢弃该数据帧，还是触发自动重传机制，又或者进行前向纠错。

这种行为叫做差错检测，分为两种方式，一种是只找错误不纠正，另一种是找到错误并纠正，我们在这里先讲前一种。

2.2.检错

2.2.1.奇偶校验(Parity Check)

2.2.1.1.普通奇偶校验

现在在某些极为古老的串行通信中，我们可以见到这种检错方式：

假设原始发送数据有 nn 位，我们需要在其后端添加一个校验位，使其变成 n+1n + 1 位，添加的校验位是 0 或 1 根据我们约定使用的是奇校验还是偶校验决定：

  • 奇校验：添加完这一位之后，整组数据的 1 的个数须为奇数。如原始数据的 1 的个数为奇数，则添加0，否则添加1
  • 偶校验：同理，添加完这一位之后，整组数据的1的个数须为偶数。

想必大家都能够一眼看出这个校验方式的致命漏洞，如果有偶数个位数的比特发生误码，则接收方仍然会认为，奇偶性没有改变，数据正常，换句话说，它只有约为 50%50\% 的检错率，这在现代网络通信中简直是不可宽恕的。

2.2.1.2.二维奇偶校验

人们为了弥补一维奇偶校验的缺点，设计出了二维奇偶校验

设原始发送数据有 nn 位，则将其排列成近似于 n×n\sqrt{n} \times \sqrt{n} 的矩阵，对每一行每一列都分别安排一位校验位，根据使用的是奇校验还是偶校验计算校验位。

譬如说对于原始数据110101001，共有 99 位，排列成 3×33 \times 3 矩阵：

110101001\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{matrix}

假设采用奇校验，则计算校验位如下：

110→1101→1001→0↓↓↓101\begin{matrix} 1 & 1 & 0 & \rightarrow & 1 \\ 1 & 0 & 1 & \rightarrow & 1 \\ 0 & 0 & 1 & \rightarrow & 0 \\ \downarrow & \downarrow & \downarrow \\ 1 & 0 & 1 \end{matrix}

则此时我们的检错率大大提高，甚至对于只有 11 位的误码，可以实现纠错，通过行列定位。

至于为什么要选择排成近似于 n×n\sqrt{n} \times \sqrt{n} 矩阵呢？原因在于对冗余率的控制。

假设我们使用 R×CR \times C 的矩阵，则需要安排的校验位的数量为 R+CR + C，为使冗余率下降，即令 R+CR + C 最小，根据基本不等式有 R+C≥RC=nR + C \ge \sqrt{RC} = n，当且仅当 R=C=nR = C = \sqrt{n} 时有最小冗余率。

但它仍然存在较大缺点，例如对于数据矩阵中的一个边长为偶数的环同时出现错误，则此时行列校验位均不会查出问题，误判数据正常。

在此之外，它的空间开销仍然较大，随着 nn 的增大，额外空间开销近似以 O(n)O(\sqrt{n}) 的速率增长。

此外，它并不适配数据链路层的硬件环境，为实现二维奇偶校验，需在网卡芯片开辟昂贵的静态内存，用于存储矩阵，并还要对其进行扫描，引发巨大转发延迟。

最后，它的定位非常尴尬，论检错率，它远不如我们稍后将要提到的CRC循环冗余检验；论纠错能力，则被LDPC码、海明码等一众高手吊锤。

因此最终奇偶校验只能留在历史和极其古老的设备上使用，应用场景狭窄。

2.2.2.循环冗余校验(Cyclic Redundancy Check, CRC)

2.2.2.1.定义与流程概述

由于奇偶校验的众多缺点，我们需要使用其他方法进行差错检验，而下面将要介绍的方法则在差错检测的非纠错处理中使用最为广泛。

  • 核心思想：利用二进制的异或运算生成校验码，缀在数据后端，接收方使用相同的异或方式处理，若余数为0，则无纰漏，否则数据发生差错。

首先，我们选定一个生成多项式函数 G(x)G(x)，令其每一项的系数都为 00 或 11，设最高次项的次数为 RR

随后，对于待处理的原始数据，我们在其后端补上 RR 个 00，作为待进行异或模 22 运算的数字。

接着，进行模 22 除法，将最终得到的余数用 00 补齐到 RR 位，替换掉刚才在原始数据后面补的 RR 位 00，得到最终发送数据。

接收方收到发送数据之后，使用同样的生成多项式函数的01串对其进行异或模 22 运算。

若得到余数为 00，则数据正常；反之出现误码。

2.2.2.2.流程演示

下面进行演示：

假设我们使用 G(x)=x3+x2+1G(x) = x^{3} + x^{2} + 1

则对应的01串为1101

设原始发送数据为101101001

依据 R=3R = 3，在后面补上 33 个 00 ，得到101101001000

随后进行”除法”


       ------------
1101 / 101101001000

看”被除数”的最高项为1，因此商取1

          1
       ------------
1101 / 101101001000
       1101
       ----

下面对其进行依位异或运算

          1
       ------------
1101 / 101101001000
       1101
       ----
       0110

前缀0省略掉

          1
       ------------
1101 / 101101001000
       1101
       ----
        110

把下一位的0挪下来

          1
       ------------
1101 / 101101001000
       1101
       ----
        1100

余数1100的最高项为1，商取1

          11
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101

同样，异或运算

          11
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
        0001

前缀0省略，上面的1挪下来

          11
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           11

最高项为0，商取0，上面再挪一位下来

          110
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           110

最高项仍为0，商取0，上面再挪一位下来

          1100
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100

最高项为1，商取1

          11001
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101

异或

          11001
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101
           ----
           0001

去掉前缀0，上面的1挪下来

          11001
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101
           ----
              11

最高项为0，同理

          110010
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101
           ----
              110

还是0

          1100100
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101
           ----
              1100

可以了，进行异或

          11001001
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101
           ----
              1100
              1101
              ----
                 1

挪位下来

          11001001
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101
           ----
              1100
              1101
              ----
                 10

不够，没得挪了

          110010000
       ------------
1101 / 101101001000
       1101
       ----
        1100
        1101
        ----
           1100
           1101
           ----
              1100
              1101
              ----
                 10

则”余数”为10，前面补足一位0到 R=3R = 3，得到010

将其缀到原始数据的后面，得到101101001010，即为可发送数据，处理完成。

随后接收方接收到数据之后，也使用相同的生成多项式处理一遍，得到余数是 00 之后就把后面的 R=3R = 3 (在这个示例中)位去掉，得到原始数据。

2.2.2.3.小结

对于生成函数，我们有常用的规范，例如CRC-16, CRC-32，通过这些生成函数，可以将检错率提升至接近 100%100\%

CRC检错率极高，且冗余率极低，对于这样的异或运算，在数据链路层的硬件环境下极为友好，计算极快。

3.可靠传输

3.1.可靠传输的基本概念

我们在上面提到，为了应对数据在传输过程中可能出现的误码，我们采用各种检错或纠错方式对数据进行处理。

对于纠错，显然不存在后续处理问题，在纠错完成之后，直接将数据继续向上传递即可。

而对于检错，在检查出错误之后，会面临如何处理的选择，具体来说，根据接收方的数据链路层选择的是不可靠传输还是可靠传输，做出相应的处理。

  • 不可靠传输：仅丢弃有误码的帧，其他什么也不做
  • 可靠传输：尝试实现发送方发送什么，接收方接收到什么

需要注意的是，可靠传输并不止在数据链路层实现。

3.1.1.是否选择可靠传输

对于是否选择可靠传输，我们大概区分为下面两种情况：

  • 有线网络：在有线网络中，通常情况下传输数据的误码率极低，不要求使用可靠传输，即使出现了误码，也交由上层处理
  • 无线网络：区别于有线网络，在传输过程中更容易受到干扰发生误码，因此一般来说强制要求使用可靠传输

但是在实际应用中，一般根据应用本身的需求去选择是否采用可靠传输。

3.1.2.传输差错的分类

在前面，我们只提到在传输过程中可能发生的错误有比特差错，但在实际情况中，还存在着其他种类的传输差错。

我们知道，在现代网络通信中常常使用分组交换传输，因此接下来我们暂且使用”组”来代表原有数据帧的概念。

  • 分组丢失：假设发送方向接收方发送了数据组A，在中途发送至中转节点，由于该中转节点本身的存储容量不足，根据该中转节点自身的规则，将数据组A丢弃，接收方无法接收到数据组A。这种情况就叫做分组丢失
  • 分组失序：假设发送方向接收方依次发送了三组数据A, B, C，但由于各种原因，三组数据并没有按照正确的顺序发送至接收方，比如接收到B, C, A，这种情况就叫做分组失序
  • 分组重复：假设发送方向接收方发送了数据组A，在中途由于网络阻塞等原因，导致停滞在传输过程中过久，发送方触发超时重传，重新发送新的数据组A，接收方接收到数据组A，而一段时间后，最开始的数据组A恢复传输，接收方接收到第二个数据组A，这种情况就叫做分组重复

3.2.可靠传输的实现机制

对于可靠传输具体如何实现，我们这里列出三种机制：停止-等待协议、回退N帧协议、选择重传协议

3.2.1.停止-等待协议(Stop-Wait Protocol, SW)

3.2.1.1.确认与否认
确认与否认

在网络状况正常时，数据传输流程大致如上图。

  • 首先，发送方向接收方传输数据，中途一切正常
  • 接收方接收到数据后，向发送方发送一个确认分组(ACK)
  • 发送方接收到ACK之后，开始发送下一个数据分组
  • 此时这个数据分组在传输过程中产生误码，接收方检查到错误
  • 在这里，有两种处理机制：
    • 接收方静默处理，等待一段时间，发送方未接收到ACK，进行超时重传。这段时间称为超时重传时间，在数据链路层中，一般简单设为略大于传输延时，在其他层级中则有较为复杂的设定机制，此处按下不表
    • 接收方向发送方发送一个否认分组(NAK)，发送方接收到NAK后，对该组数据进行重传
  • 接收方接收到正常数据，重复上述过程
3.2.1.2.超时重传
超时重传

实际上，对于这种数据组在传输过程中丢失的情况，处理方式和我们上面所说的接收方检查到误码且不返回NAK的情况相同，超过所设定的时间之后，自动进行超时重传

3.2.1.3.确认丢失
确认丢失

实际上，我们很容易可以想到，数据分组在传输过程中遇到的问题，ACK也同样会遇到

比如在上图，接收方接收到正常数据组后，向发送方发送了ACK，然而在发送过程中，遭遇丢失

发送方经过一段时间没有接收到接收方反馈，触发超时重传，向接收方再次发送该组数据

而接收方重复接收到该组数据，也即遭遇我们上面所说的分组重复错误，应当如何分辨，这是发送方发送的新的数据，还是针对上一组数据的重传呢？

对于这个问题，我们考虑区分不同组别的数据，也即对其进行编号

提到编号，想必大多数人会想到使用 1,2,3,…1, 2, 3, \dots 这样的方式进行编号，但如果直接将这样的编号整合到数据中，不仅难以设置对应编号区间长度，还会造成过多不必要的冗余。

在这样的情况中，我们可以发现，只需要辨别该组数据是否与上一组发送的数据相同即可

  • 如果相同，就说明发送方并没有接收到ACK或者NAK，接收方可以再次尝试发送
  • 如果不同，就说明已经是下一组数据了，接收方照常接收

在这里，我们采用一个比特位用于记录编号，对于发送方将要发送的一连串数据组，该比特位设为010101...这样的格式用于标记与前一组数据不同

3.2.1.4.确认迟到
确认迟到

对于ACK，除了可能在半途丢失之外，还可能因为种种因素迟到，导致触发发送方超时重传

想象一下下面的流程：

  • 接收方接收到正常数据，向发送方发送ACK
  • ACK在传输过程中因某种因素迟到
  • 发送方在超过超时重传时间后仍未收到接收方反馈，触发超时重传，向接收方发送DATA0(假设我们从0开始表示编号)
  • 此时ACK终于到达发送方，发送方接收到ACK，开始发送DATA1
  • 接收方接收到发送方超时重传的DATA0，再次返回一个ACK
  • 然后发送方又收到一个ACK，懵逼了，还要发送一个DATA1吗？

为了解决这个问题，我们使用与上面确认丢失类似的方法：对ACK也进行编号

如此一来，发送方接收到第二个ACK0，就可以直接把它忽略

3.2.1.5.信道利用率
信道利用率示意图

接下来我们尝试计算停止-等待协议的信道利用率

设数据分组的发送时延为 TDT_{D} ，发送之后等待接收方回应的平均等待时间为 RTTRTT，ACK的发送时延为 TAT_{A}，信道利用率为 UU

则显然在这一个循环中，发送方实际发送信息的时间只有 TDT_{D}，故有

U=TDTD+RTT+TAU = \frac{T_{D}}{T_{D} + RTT + T_{A}}

由于 TAT_{A} 一般远小于 RTTRTT，故在计算中可忽略

U=TDTD+RTTU = \frac{T_{D}}{T_{D} + RTT}
3.2.1.6.停止-等待协议小结

根据以上所述，我们可以整理出SW的优点与缺点

  • 优点：
    • 非常简单，发送方与接收方的缓冲区只要有能装下一个帧的容量就可以
    • 天生自带流量控制，在发送方发送数据极为庞大的情况下，可以控制流量，使接收方掌控传输节奏
    • 在极端恶劣环境下表现良好，可以保持发一个，等一个的节奏，相当稳定
  • 缺点：
    • 对**定时器(Timer)**的精度要求极高，如果设置超时重传时间太短，可能导致过度重传，而实际上只是网络轻微堵塞，重传过多可能直接导致网络瘫痪；如果设置时间太长，则会导致在已经发送失败的情况下，发送方仍在等待，浪费空闲时间
    • 在信道较长的情况下，信道利用率表现极差，对于高带宽延迟积，如跨国通道，信道极长且较宽，但在SW中，仍然是一次只能发送一个分组，如同一条高速公路一次只让一辆车通过，浪费传输资源

那么什么时候适合应用SW呢？在硬件资源匮乏，信道环境恶劣，对传输速率无要求的情况下，SW表现良好

反之，在现代互联网、高带宽，以及追求高并发的现代Web应用中，SW极度不适合

3.2.2.回退N帧协议(Go-Back-N, GBN)

3.2.2.1.流水线传输

为了解决停止-等待协议信道利用率极低的问题，人们引入了回退N帧协议

而在介绍回退N帧协议之前，先需要介绍流水线传输

流水线传输

回忆一下，停止-等待协议的最大痛点是什么？又或者说，导致它信道利用率低的主要原因是什么？就是在同一时间内，只发送一组数据，且在接收到ACK或计时器超时之前，会持续等待。

所以要改善这个缺点，我们不妨在一次性连续地发送多组数据，即为流水线传输，而回退N帧协议就是基于它实现的。

3.2.2.2.核心机制：滑动窗口(Slibing Window)

同样地，我们对原始数据进行处理，添加序号用于标识不同组的数据。但不同于停止-等待协议中的是，它对应的比特位可能不止一位。

我们假设使用 nn 位比特来表示序号，则表示范围为 0∼2n−10 \sim 2^{n} - 1

此时，我们维护一个发送窗口，在发送窗口覆盖范围内的数据分组可以连续发送。设发送窗口的长度为 WTW_{T}，则显然需有 1≤WT≤2n−11 \le W_{T} \le 2^{n} - 1

发送窗口

如图所示，我们设 n=3,WT=5n = 3, W_{T} = 5

在初始情况下，我们的滑动窗口覆盖了序号为 0∼40 \sim 4 范围的数据，分别连续地将其依次发送。

同样地，在接收方，也有一个接收窗口，不过在回退N帧协议中，设接收窗口长度为 WRW_{R} ，则 WRW_{R} 始终为 11 ，即它和停止-等待协议一样，都是同一时间只接收一组数据。

接收窗口

发送方发送的数据分组依次到达接收方

  • 首先，接收方接收到编号为0的分组，确认无误码后，接收窗口向右移动一位，同时向发送方发送ACK0
  • 接收方接收到编号为1的分组，同样确认无误，接收窗口再次向右移动一位，向发送方发送ACK1
  • 后面依次重复相同操作

接下来我们来看发送方对于ACK的反应

  • 发送方接收到ACK0，说明编号为0的数据组已经发送成功，将数据组0从缓存中去除，发送窗口整体向右移动一位
  • 此时发送方的发送窗口的覆盖编号范围为 1∼51 \sim 5，检查到编号为 55 的数据组尚未发送，于是将其发送
  • 发送方接收到ACK1，同样地，将数据组1从缓存中去除，发送窗口整体向右移动一位
  • 重复以上操作
发送方视角的序列号空间：
+--------------------+-----------------------+-----------------------+---------------------+
|   已发送且已确认   |    已发送但未确认     |   允许发送但尚未发送  |    暂不允许发送     |
+--------------------+-----------------------+-----------------------+---------------------+
                     ^                       ^
                     |                       |
               发送窗口左边界           当前发送指针              发送窗口右边界
               (base / send_left)      (next_seq_num)          (send_right)
                     |<------------  发送窗口大小 W_T ----------->|
3.2.2.3.累计确认

然而，相较于停止-等待协议，回退N帧协议还有一个显著的优势，就是累计确认

同样是上面的流程，此时我们仍然是收到一个数据组，就返回一个对应的ACK

但是我们可以这样做，比如接收方在前面收到数据组时，并不立即返回对应的ACK，而是在收到数据组4之后，仅返回一个ACK4

当发送方接收到ACK4之后，就可以知道，在第4组数据之前的所有数据都已经成功接收了，所以可以直接一次性将发送窗口挪动多个位置

使用累计确认的好处就是，可以节约通信资源，也缓解了接收方的处理压力

退一步说，就算仍然是对于每个数据组都返回对应的ACK，由于拥有这种处理机制，假如说返回了ACK1, ACK2, ACK3, ACK4，假设中途的ACK2丢失了，发送方也不会因此重传，因为它成功接收到了ACK4，就知道数据组4之前的都已经发送成功了，可以放心更新发送窗口。

3.2.2.4.异常处理

以上所述皆为在无异常情况下的处理，接下来我们来看看，当检测到差错时，回退N帧协议是如何处理的。

设想当接收方接收到数据组1，发现误码，则它不会接受该数据组，将其丢弃。

随后，数据组2, 3, 4依次到达，但由于与当前接收窗口所覆盖的位置对应的数据编号不符合，同样将其丢弃，丢弃的同时，向发送方重复发送ACK0，总计发送4个ACK0

发送方接收到4个ACK0，与之前已经接收过的ACK0重复，知道之前发送的数据分组出现了差错，因此可以不用等到超时再进行重传

至于接受几个重复值之后开始重传，取决于具体实现

在这个例子中，即使数据组2, 3, 4正常到达接收方，但由于数据组1出现了差错，导致后面的分组也不被接受，回退到数据组1开始重新发送，这就是回退N帧的由来

3.2.2.5.发送窗口大小的选取

对于 WT=1W_{T} = 1 的情况，我们可以很容易看出，这就是停止-等待协议的实现

为什么 WTW_{T} 要小于等于 2n−12^{n} - 1 呢？

  • 试想当 WT=2nW_{T} = 2^{n} 时，此时接收方成功接收了这前 2n2^{n} 个数据组，往回发送一个对应的ACK
  • 但是该ACK在传输过程中丢失，发送方计时器超时后，触发超时重传，又发送这 2n2^{n} 个数据组
  • 接收方又接收到这 2n2^{n} 个数据分组，由于这 2n2^{n} 个数据分组与后 2n2^{n} 个数据分组的序号都为 0,1,2,…,2n−10, 1, 2, \dots, 2^{n} - 1，发送方误以为这是新一组数据，导致后面数据全部错位

而对于 2n∤WT2^{n} \nmid W_{T} 的情况，比如选取 n=2,WT=5n = 2, W_{T} = 5，同样会出现问题

  • 比如当发送方发送0, 1, 2, 3, 0，接收方在接收数据的时候，后面的那个0发生了误码
  • 接收方将这组数据丢弃，返回一个ACK3
  • 但由于神秘的网络波动，这个ACK3丢失了
  • 发送方计时器超时，触发超时重传，又发送了0, 1, 2, 3, 0
  • 接收方接收到开头的那个0，乐乐呵呵接收了，但实际上完全错位了！

因此，对于某一组发送的数据，其编号不应当有重复的情况，也不应当完全覆盖所有序号范围，否则将会造成无法预料的错误

3.2.2.6.GBN小结

对于回退N帧协议，我们大概可以总结一下它的优点与缺点。

优点：

  • 和SW一样，硬件开销低，接收方只需要长度为1的 WRW_{R} 用来接收数据
  • 支持累计确认，前面已经讲过了
  • 显著提升了信道利用率

缺点：

  • 回退重传开销极大，对于环境不好的信道，触发多次重传回退，会导致性能大幅下降，甚至和SW相差不多了

因此在现在，我们也只能在某些特定的广播通信和简陋的嵌入式环境见到GBN的单独使用，在现代网络中应用面较为狭窄。

3.2.3.选择重传协议(Selective Repeat, SR)

3.2.3.1.SR介绍

为了解决在回退N帧协议中，前面的一个数据组发生错误，导致后面的数据组需要全部重传的的问题，人们引入了选择重传协议

相较于GBN，SR的主要改动就是，将接收窗口 WRW_{R} 增大，同一时间可以接受接收窗口中的任意一组数据，随着正确数据分组的接收，接收窗口不断向后移动，直到遇到未成功接收的数据分组。

其中，由于后面的数据分组的确认接收不能再保证前面的数据分组都已成功接收，SR不能够再使用累计确认，而是逐个确认每个数据分组是否接收成功。

在这里，我们来模拟一遍SR的工作流程

SR发送窗口

这是发送窗口，在这里，我们选取编号位比特数为 n=3n = 3， WT=4W_{T} = 4

SR接收窗口
  • 首先，发送方向接收方依次发送数据分组0, 1, 2, 3
  • 在传输过程中，数据分组2丢失，接收方接收到数据分组0, 1, 3
  • 接收方逐个确认数据分组0, 1, 3，向发送方发送ACK0, ACK1, ACK3
接收方接收到0, 1, 3号数据分组
  • 与此同时，接收方由于成功接收数据分组0, 1，将接收窗口向后移动两位
  • 此时数据分组3也已经成功接收，但由于它并不是按序成功接收的数据分组，所以此时接收窗口不能再移动
  • 接收窗口此时新纳入了数据分组4, 5的位置，可以接收这两个数据分组
发送方接收到ACK0, 1, 3
  • 对于发送方，每按序收到一个确认分组，发送窗口向后移动一个位置
  • 故此时发送窗口覆盖范围为 2∼52 \sim 5，因为还未收到ACK2
  • 发送方发送数据分组4, 5
接收方接收到数据分组4, 5
  • 接收方接收到数据分组4, 5，返回ACK4, ACK5，但由于数据分组2未能成功接收，接收窗口还不能向后移动，故保持不变
  • 发送方的数据分组2的计时器超时，触发超时重传，重新发送2号数据分组
发送方接收到ACK4, 5
  • 发送方接收到ACK4, ACK5，将其标记为已接收，但由于并非按序接收，故不能向后移动发送窗口
接收方接收到数据分组2
  • 此时接收方接收到数据分组2，接收窗口向后移动四个位置，同时向发送方发送ACK2
发送方接收到ACK2
  • 发送方接收到ACK2，发送窗口向后移动四个位置
  • 重复以上操作，发送方继续发送数据
3.2.3.2.窗口长度的选取

在SR中，发送窗口的长度应满足 1<WT≤2n−11 < W_{T} \le 2^{n - 1}，接收窗口的长度应满足 1<WR≤WT1 < W_{R} \le W_{T}

首先对于发送窗口，我们容易知道，长度应当小于 2n2^{n}，这在上面的GBN的介绍中曾经提到过，但是为什么要小于等于 2n−12^{n - 1} 呢？我们来模拟一下

还是令 n=3n = 3，此时我们将 WTW_{T} 设为 55

  • 发送方发送数据分组0, 1, 2, 3, 4
  • 接收方接收数据分组0, 1, 2, 3, 4，返回ACK0, ACK1, ACK2, ACK3, ACK4，并将接收窗口向后移动五个位置，此时覆盖编号为5, 6, 7, 0, 1
  • 在传输中途，ACK0丢失，发送方接收到ACK1, ACK2, ACK3, ACK4，由于不是按序接收，无法向后移动窗口
  • 经过一段时间，计时器超时，发送方将数据分组0超时重传
  • 接收方接收到数据分组0，将其误认为当前接收窗口5, 6, 7, 0, 1中的0号数据分组，照常接收
  • 就这样，数据分组发生错位

接下来，我们来分析为什么接收窗口的长度不能超过发送窗口的长度，即 WR≤WTW_{R} \le W_{T}

此时设 WT=2,WR=4W_{T} = 2, W_{R} = 4，不考虑序号空间大小

  • 发送方发送数据分组0, 1
  • 由于网络问题，数据分组1比数据分组0先到达，但接收到数据分组1之后，接收窗口仍然不能移动，只返回ACK1
  • 此时数据分组0到达，接受方返回ACK0
  • 发送方接收到ACK1，但无法移动发送窗口
  • 只有当发送方接收到ACK0，发送窗口才能移动，也就是说，对于那些超出的部分，比如数据分组2, 3，仅有在接收到ACK0之后才有权限发送，接收方维护了多余的内存资源，却无法达到更好的效果
3.2.3.3.SR小结

优点：

  • 精准重传：哪个包丢了就重传哪个，节省了网络带宽
  • 信道吞吐量高：允许乱序到达，信道保持较高利用率

缺点：

  • 乱序缓存开销：当最前面的数据没到，后面的也只能在缓存中干着急
  • 排序与交付延迟：接收方接收到乱序数据之后，需要在缓存中使用链表或者红黑树排序，等到前面的包到达，才一口气向上推
  • 定时器滥用：SR不得不为每个发出去且未被确认的包维护一个定时器，负载极高

4.点对点PPP协议(Point to Point Protocol)

4.1.介绍

在主机连接到因特网的过程中，一般需要先连接到互联网服务提供者ISP控制的一批IP地址，而PPP协议就是管理主机与这些IP地址连接过程的协议。

PPP协议是目前使用最为广泛的数据链路层协议，但需要注意的是，在从前的拨号上网(ADSL)的以太网连接的过程中，底层的协议也是PPP，严格来讲是PPPoE，即运行在以太网上的PPP

另外，PPP协议也广泛应用于广域网(WAN)的连接

需要注意的是，PPP协议不提供流量控制

4.2.核心构成

PPP协议由以下三部分构成：

  • 成帧方法：即如何将从上层传下来的IP数据报封装成帧
  • LCP(Link Control Protocol, 链路控制协议)：负责链路的建立、配置和测试，两台设备在通过PPP协议连接之前，需要先通过LCP进行协调
  • NCP(Network Control Protocol, 网络控制协议)：负责配置网络层协议，实际上，PPP协议中有一整套NCPs，每个NCP对应支持一套网络层协议，如支持IP协议、IPX协议等

4.3.PPP帧格式

PPP协议将IP数据报封装为PPP帧，PPP帧的格式如下所示：

PPP帧格式
字段Flag(标志)Address(地址)Control(控制)Protocol(协议)Information(数据)FCS(校验)Flag(标志)
长度1字节1字节1字节2字节0 - 1500字节2或4字节1字节
值0x7E0xFF0x03动态变化IP报文CRC结果0x7E
  • Flag(标志位)：固定为0x7E(二进制01111110)，为帧的边界，用于标识帧开始或结束
  • Address, Control：在PPP设计时，为了兼容老旧的HDLC(高级数据链路控制)协议的硬件，沿用了HDLC的帧格式
    • 在HDLC中，Address是用于区分多点链路的站点的，但PPP为点对点，于是规定Address永远为0xFF(广播地址，表示所有人都能听)，Control为0x03(表示无编号信息帧)
    • 即代表这两个字段无实际意义，在后来的LCP协商中，引入了一个叫做ACFC(Address-and-Control-Field-Compression, 地址和控制字段压缩) 的优化选项，如果双方协商时开启这个功能，则在实际传输过程中，会直接不发送这两个字节的内容
  • Protocol(协议)：用于标识数据报的种类，例如0x0021表示为IP数据报，0xC021表示为LCP报文
  • FCS(帧检验序列)：使用我们上面提到的CRC循环冗余校验生成

4.4.透明传输问题

对于数据报中也含有0x7E的情况，PPP协议分为以下两种处理方式：

  • 异步链路：字节填充法，即使用转义字符
  • 同步链路：零比特填充法，即对于数据报中每连续5个1，后面塞入一个0

这里的两种方法我们都已经在帧定界提到过，此处不再赘述

4.5.PPP工作状态

对于PPP协议在网络连接中的工作状态，可以描述为下图：

PPP工作状态
  • 首先，处于静止状态，当检测到载波时，尝试建立物理层连接
  • 建立物理层连接后，LCP开始发挥作用，双方主机协商配置
    • 协商重点参数有以下内容：
      • MRU(Maximum Receive Unit)：最大接收单元，默认1500字节
      • Authentication Protocol(认证协议)：协商这趟协议是用PAP还是CHAP
      • Magic Number(魔术字)：一个随机的4字节数，用于检测环路
    • 若协商成功，则进入鉴别阶段
    • 若协商失败，回退至静止阶段
  • 鉴别阶段，根据上一轮的建立阶段所确定的鉴别协议进行鉴别
    • 若无需鉴别或者鉴别成功，进入网络阶段
    • 若鉴别失败，进入终止阶段
  • 在网络阶段，尝试进行NCP配置
    • 若配置成功，则可以开始正常进行通信
    • 若配置失败，则进入终止阶段
  • 当出现故障或者发出通信终止请求，进入终止阶段
  • 终止阶段中，当载波停止时，重新回到静止阶段

5.媒体接入控制(MAC, Medium Access Control)

5.1.基本概念

想象对于一个总线型的网络，有多个主机接入到总线上。在某一时刻，有两个或者更多的主机尝试向外发送信息，当两个主机发送的信息在信道中碰撞时，就会造成发送失败。

为了解决这个问题，我们引入了媒体接入控制的概念，我们大概可以将它的实际应用方法概括为下图：

媒体接入控制概览

5.2.静态划分信道

5.2.1.多路复用(Multiplexing)

5.2.1.1.多路复用的基本概念

在广播信道中，为了让多个主机共享同一条物理信道，需要使用多路复用技术，将一条高带宽的物理信道，在逻辑上划分为多个低带宽的子信道并分配给不同的用户

5.2.1.2.频分复用(FDM, Frequency Division Multiplexing)
  • 原理：将总频带宽度划分为若干个更窄的子频带(子信道)，每个用户占据其中的一个子频带。同时为了防止互相干扰，子频带之间还需要留有隔离频带
  • 特点：所有用户在相同时间占用不同的频率资源
  • 应用：传统的广播电台、有线电视
5.2.1.3.时分复用(TDM, Time Division Multiplexing)
  • 原理：将时间划分为等长的TDM帧，每个TDM帧又划分为若干个等长的时隙(Time Slot)，每个用户周期性地占用每个TDM帧中的某一个固定序号的时隙
  • 特点：所有用户在不同时间占用相同频率的资源
  • 改进：由于传统TDM不管该时隙有没有人发送数据，都留出这一个位置，造成资源浪费，因此实际应用中多采用**STDM(异步时分复用)**来动态分配时隙
5.2.1.4.波分复用(WDM, Wavelength Division Multiplexing)
  • 原理：实际上就是光的频分复用，由于光的频率极高，工程上习惯用波长来表示，在一根光纤上传递多个不同波长的光载波信号
  • 实现：发送端用光复用器(Mux)，把多路光信号混在一起传进光纤，接收端用**光分用器(Demux)**将不同波长的光信号分离
5.2.1.5.码分复用(CDM, Code Division Multicomplexing)

码分复用CDM是另一种共享信道的方法，实际上，由于该技术主要用于多址接入，人们更常用的名词是码分多址

5.2.2.多址(Multiple Access)

5.2.2.1.多址的基本概念

如果说复用是一种划分频带资源以满足多主机通信的方式，那么多址，或者说多点接入，就是将信道动态分配给用户的方法

在这里，我们大概介绍时分多址和频分多址的概念，随后重点讲解码分多址

5.2.2.2.TDMA(Time Division Multiple Access, 时分多址)与FDMA(Frequency Division Multiple Access, 频分多址)
  • TDMA(时分多址)：对应时分复用，将时间划分为多个切片，每个主机轮流占据某个时间切片下信道的使用权。即使信息没有发送完毕，时间到了也只能将使用权给下一个人
  • FDMA(频分多址)：对应频分复用，为电台广播的常用控制方法，将频率划分为多个小段，如100MHz，101MHz
5.2.2.3.CDMA(Code Division Multiple Access, 码分多址)
5.2.2.3.1.核心思想与基本定义

CDMA允许所有用户在相同时间使用相同频率进行通信，它通过数学上的向量正交来区分不同的用户信号

  • 码片(Chip)：CDMA将每一个比特时间划分为 mm 个短的间隔，通常 m=64m = 64 或 128128，为了简化举例，此处设 m=8m = 8。这 mm 个二进制位被称为一个码片
  • 码片序列(Chip Sequence)：每个站点被指派一个唯一的 mm 位码片序列 为了进行数学计算，我们作如下符号规定：
    • 二进制的1写作向量里的 +1+1
    • 二进制的0写作向量里的 −1-1
  • 信号发送规则
    • 站点如果想要发送比特1：则发送它自己的 mm 位码片序列(原向量)
    • 站点如果想要发送比特0：则发送它自己码片序列的二进制反码(即原向量取负向量值)
    • 站点如果不发送数据：则发送全0向量(静默)
5.2.2.3.2.原理分析

设指派给站点 SS 的码片向量为 S\mathbf{S}，指派给站点 TT 的码片向量为 T\mathbf{T}

则任意两个不同站点的码片序列，其规格化内积必为 00

S⋅T=1m∑i=1mSiTi=0\mathbf{S} \cdot \mathbf{T} = \frac{1}{m} \sum^{m}_{i = 1} S_{i} T_{i} = 0

同理，任何一个向量与其反码向量 T‾\overline{\mathbf{T}} 的规格化内积也为 00

S⋅T‾=0\mathbf{S} \cdot \overline{\mathbf{T}} = 0

而任何一个站点的码片向量，与它自身的规格化内积必然为 11

S⋅S=1m∑i=1mSi2=1m∑i=1m(±1)2=1\mathbf{S} \cdot \mathbf{S} = \frac{1}{m} \sum^{m}_{i = 1} S^{2}_{i} = \frac{1}{m} \sum^{m}_{i = 1} (\pm 1)^{2} = 1

它与自身反码的规格化内积必然为 −1-1

S⋅S‾=−1\mathbf{S} \cdot \overline{\mathbf{S}} = -1
5.2.2.3.3.应用解密

当多个站点同时在空中发射信号时，在物理介质中，这些电磁波信号会线性叠加

假设A站发1，B站发0，C站不发送信号

则叠加总信号为

X=A+B‾\mathbf{X} = \mathbf{A} + \overline{\mathbf{B}}

对于每个站点，接收端将这个总信号向量与站点自己的码向量作内积，就得出来对应的结果：

对于A

(A+B‾)⋅A=A⋅A+A⋅B‾=1+0=1(\mathbf{A} + \overline{\mathbf{B}}) \cdot \mathbf{A} = \mathbf{A} \cdot \mathbf{A} + \mathbf{A} \cdot \overline{\mathbf{B}} = 1 + 0 = 1

则A发送的为比特1

对于B

(A+B‾)⋅B=B⋅A+B⋅B‾=0+(−1)=−1(\mathbf{A} + \overline{\mathbf{B}}) \cdot \mathbf{B} = \mathbf{B} \cdot \mathbf{A} + \mathbf{B} \cdot \overline{\mathbf{B}} = 0 + (-1) = -1

则B发送的为比特0

对于C

(A+B‾)⋅C=C⋅A+C⋅B‾=0+0=0(\mathbf{A} + \overline{\mathbf{B}}) \cdot \mathbf{C} = \mathbf{C} \cdot \mathbf{A} + \mathbf{C} \cdot \overline{\mathbf{B}} = 0 + 0 = 0

则C未发送数据

5.2.3.小结

对于静态划分信道，其在用户数量固定、流量稳定、对延迟极其敏感的传统电信网中，仍然是不可动摇的基石

但在流量突发性强的现代计算机网络中，动态接入使用相对广泛

5.3.动态受控接入:轮询MAC

  • 轮询(Polling)：我们维护一个主节点，然后由它逐个询问从节点是否需要发送数据，缺点是容易因为主节点故障导致网络瘫痪
  • 令牌传递(Token Passing)：多个主机采用环形连接，相互之间传递一个叫做令牌的特殊数据分组，拿到令牌的主机才能发送数据

缺点为开销极大，还需要维护令牌丢失、节点故障、环断开等情况，逻辑极其复杂繁琐

5.4.动态随机接入:争用型MAC

相较而言，这个就是在现代网络中应用较为广泛的媒体接入控制方式了

5.4.1.CSMA/CD(载波监听多路访问/冲突检测)

其过程可以总结为：先听后发，边发边听，冲突停止，随机延迟重发

  • 先听后发(CS)：发数据前，先查询总线上有没有主机正在通信，如果有，就先暂时等待

  • 边发边听(CD)：为了处理信号传输的延迟(争用期/碰撞窗口)，在信号发射的同时，接收头监测电压，若发现电压异常，就说明数据发送发生碰撞

  • 冲突停止：若发现冲突，则停止发送，并补发人为干扰信号，通知全网

  • 随机延迟重发：对于延迟重发时间，采用**退避算法(截断二进制指数退避算法)**进行计算：

    退避时间=2τ×r退避时间 = 2 \tau \times r

    其中 τ\tau 为单向传输时延，rr 是集合 {0,1,…,2k−1}\{0, 1, \dots, 2^{k} - 1 \} 中的随机整数(k=min(冲突次数,10)k = \text{min}(冲突次数, 10))

    撞击次数越多，随机范围翻倍扩大，如果连撞16次，就向上层报错

此方法在有线以太网中应用广泛，但对于无线Wi-Fi，我们需要使用接下来的这种方法

5.4.2.CSMA/CA(载波监听多路访问/冲突避免)

在无线网络(Wi-Fi)中，无线网卡在发射信号时，由于自身发射信号功率过大，无法同时监听外界微弱的冲突信号

也就是说，它没办法做到边发边听(CD)，从而也就无法实现冲突检测

再加上无线存在隐蔽站问题，即A和C都能连接B，但是由于A和C互相不可见，当它们同时向B发送信号就会出现冲突

所以CSMA/CA将重点放在了避免冲突上：

  • 不再边发边听：既然无法检测冲突，就尝试一口气将整个数据帧发完
  • IFS(帧间间隔)：发完之后或者想要再次发送之前，必须强制等待一段时间，给高优先级的数据(如ACK)让路
  • 虚拟载波监听(RTS/CTS)：为了解决隐蔽站问题，A在发送数据之前，先发送一个很短的RTS(请求发送)，B在接收到RTS之后，广播一个CTS(允许发送)，这时当C接受到CTS，就知道此时其他主机正在向目标传输数据，就暂作等待
  • ACK：接收方收到数据之后，必须返回一个ACK确认，若发送方未接收到ACK，就认为传输发生碰撞，退避重发