计算机网络——可靠数据传输原理

前言

  传统的计算机网络一共分为 $5$ 层，自顶向下分别是：应用层、运输层、网络层、链路层、物理层。其中：

• 应用层主要负责落实到网络应用，在发送方负责将网络应用的请求打包成报文，在接收方负责将下层的报文递交给应用程序。
• 运输层在 PDU 中加入端口号。在发送方主要负责收集各个网络应用的报文，并交付给下层；在接收方负责根据端口号落实到特定的网络应用程序。运输层不知道也不在意数据在主机之前是如何传输的。
• 网络层负责将运输层的 PDU 进一步修饰（加入 IP，与运输层加入的端口号形成“套接字”），并将该 PDU 发送到网络中。网络层对 PDU 的传输路径有一定的了解，但是它不知道也不在意自己收到的 PDU 中包含了哪些网络应用的请求报文。

  数据在网络中的传输是不可靠的，为了让应用层享受到可靠的数据，运输层主动承担起提供可靠数据服务的责任。

停等协议可靠数据传输

  在停等（StopWait）协议中，发送方只有确认接收方确实收到了分组 $x$ 之后，才会开始发送分组 $x+1$。你也可以将其理解为分组串行发送的模式。这类可靠数据传输由 RDT 协议描述。

Rdt 1.0——可靠信道的可靠传输

  Rdt 1.0 的基本假设是网络层信道完全可靠，即不会产生错误，不会丢包。实际上这种情况并不会发生，因为网络层肯定是不可靠的，但是它仍具有研究的价值。

此时的发送方：

• 等待上层调用……
• 上层调用rdt_send(data)，那么发送方的运输层将数据打包成packet，然后通过udt_send(packet)将分组发送到网络层。

接收方：

• 等待来自下层的调用……
• 下层调用rdt_rcv(packet)，那么来自网络层的包被拆包成data，然后发送到应用层。

Rdt 2.0

  假设信道会产生错误，但是依然不会丢包。为了能够检错，在将data打包为packet的时候引入一个校验和字段。发送方会根据收到的数据是否正确，发送 ACK 或者 NAK。

Rdt 2.1

  Rdt 2.0 的 FSM 存在问题，因为 ACK 和 NAK 分组也可能受损，不能假定他们就是正确的。
  然而接收方并不知道自己发送的 ACK/NAK 在信道中会不会出错，比如当自己发送 ACK 时，接收方不知道发送方接下来是重新发送包 $x$（自己的 ACK 出错了），还是顺序地发送 $x+1$（ACK 未出错）。因此，引入分组编号是必须的。

注意上面的两张图，每张都只需要看一半就可以了。对比 Rdt 2.0 的执行过程，Rdt 2.1 更新了两个地方：

• 发送方：对接收方发来的 ACK/NAK 进行检查，有误则重发且等待，否则状态迁移。
• 接收方：对发送方发来的 seqnum（分组编号）进行检查，如果不是自己想要的就发送 NAK，否则发送 ACK 且状态迁移。

Rdt 2.2

  在 Rdt 2.1 引入分组编号之后，NAK 就显得多余了。因为 ACK/NAK 的本质是决定发送方接下来重发 $x$ 还是继续发 $x+1$，而实现这两种模式，发送方可以分别发送 ACK x-1 和 ACK x，即不需要 NAK 的参与。发送方只需要检查ACK所带的序号值，即可决定发 $x$ 还是发 $x+1$。

Rdt 3.0

  Rdt 3.0 在 Rdt 2.x 的基础上进一步假设信道会丢包。丢包是在网络层发生的，位于运输层的 TCP 并不知道这一点，所以只能设置一个计时器，超时即认为丢包。

接收方的 FSM 图可以自行画出。相比于 Rdt 2.2，Rdt 3.0 引入了计时器，并作如下增加与改动：

• 在收到上层调用，向网络层发送分组时，同时启动定时器。
• 在分组确认接收时，关闭定时器。
• 在收到错误的 ACK 序号，或者 ACK 校验和错误时，不像 Rdt 2.2 那样立刻重发当前的包，Rdt 3.0 选择什么也不做，等待 Timer 超时的时候重发。

流水线可靠数据传输

  停等数据传输存在一定问题，因为它的特点是“发送方只有确认接收方确实收到了分组 $x$ 之后，才会开始发送分组 $x+1$”。就像一批人上高速回家，但是高速的入口一次只允许经过一辆车，后面的车辆到达入口时需要停下来，等到这辆车走完高速，才能上高速；这种情况下，长长的高速公路上同一时刻只有一辆车，大大地浪费了交通资源，也大大地浪费了大家的时间。为什么不让他们一起上路呢？
  基于这个事实，流水线可靠数据传输（并行的可靠数据传输）的想法就油然而生，发送方一次可以同时发送多个分组，而不需要等到前面的分组被确认再发送后面的分组。但是这又产生了新的问题：

• 这一群分组中，如果有一个分组丢失了，怎么办？
• 发送方按顺序发送分组，但是接收方那边是乱序到达的，怎么办？

对于这两个问题，不同的流水线协议有不同的答案。

GBN（Go-Back-N）协议

  GBN 协议中，接收方在某一时刻只能接收一个分组。即接收方的状态：

1. 等待收到分组x。
2. 收到正确无误的分组x，则++x，发送ACK x，且回到状态1。
3. 收到错误序号的分组，或者错误内容的分组，丢弃该分组，发送ACK x-1，且回到状态1。

  发送方不能无限制地发送分组，下一个可用分组和最近收到确认的分组之间，至多相隔 $N$。如下图，base之前的都已被确认，窗口为[base,base + N)。

• 上层调用（应用层有数据过来），如果nextseqnum < base + N，说明仍有可用空间，将其放入nextseqnum，nexseqnum自增，并且向网络层发送这个包。这个包过来之前，可能窗口里没有发送还未确认的包；如果是这样的话，发送完这个包之后，还要开启计时器。
• 计时器 timeout，首先重新启动计时器，然后将[base,nextseqnum)之间的包再重新发送给网络层。可见，GBN 中对所有发送还未确认的分组设立统一的计时器。
• 收到来自接收方的 ACK，若 ACK 校验和错误，则啥也不做。
• 收到来自接收方的ACK x，校验和正确，可以更新base = x + 1。此时再看看base == nextseqnum是否成立，若是，说明所有发送的包都已确认，也就没有设置定时器的必要了，因此关闭定时器；否则重新启动定时器。

  有一个问题就是，收到来自接收方的ACK x，且校验和正确，会不会导致base的回退？实际上是不会的。我们知道，接收方发送的 ACK 序号是随时间递增的；即 $t_1,t_2$ 时刻分别放松 $x_1,x_2$ 的 ACK，那么有 $x_1\le x_2$。在 $t_2$ 时刻，收到接收方 $x_2$ 的 ACK，说明之前必定存在某一个时刻（之前必然有对base的一次更新）$t_1$，使得 $\mathrm{base}=x_1+1$。显然 $\mathrm{base}\le x_2+1$，也就是说base只会增加或保持不变，而不会回退。
  因此 GBN 对于上面两个问题的回答是：

• 一个分组丢失，那么后面的分组号都不是我想要的，即使到了我也会直接丢掉。
• 失序到达——我这边只按序接受，不符合我想要的分组号的分组，都会被我丢掉。

SR（Selective Repeat）协议

  SR 协议，又称为选择重传协议，其接收方存在一定的缓存区。此时，如果一个分组丢失，后面的分组也不会被接收方丢掉，而是被缓存起来；失序到达也是同样的道理。SR 协议同样拥有base，标明base之前的分组都已正确接收，并提交到应用层；但是它不具有nextseqnum，因为 SR 所期待的不是某一个特定的分组号，而是一群分组号（在自己窗口内的分组号都是 SR 所期望的）。在这种情况下，发送方的行为：

• 上层调用和 GBN 几乎一样，只是最后开启的计时器是针对这次收到的这一个分组，而不是窗口内的所有分组。
• 计时器 timeout，由于 SR 是对窗口内的每个分组单独设置定时器，谁超时了重发谁就好了。
• 收到来自接收方的 ACK，若 ACK 校验和错误，啥也不做。
• 收到来自接收方的ACK x，校验和正确。若x在窗口（[base,base + N)）内，则标记窗口内的x为已确认。如果x == base，可以向右推动窗口，直到新的base对于的分组状态是未确认。

此时的接收方行为是：

• 收到的分组号x是窗口内的，接收它，发送ACK x，如果x == base（注意接收方、发送方的窗口是不同的），那么可以向右推动窗口，直到新的base对应的分组是处于未收到的状态。同时记得向上层提交分组。
• 收到的分组号x不是窗口内的。可能原因是之前发送过对x的确认，然后接收方的窗口向右推进使得x不再处于窗口内了，但是发送方没有收到ACK x，所以重发了一个。再确认一次，发送ACK x就好了。

TCP 协议

  TCP 协议相比于前两种协议，有以下特点：

• 按字节编号。前两种协议中，发送方的base,nextseqnum,acknum这些都是按分组来编号，而 TCP 中它们都是按字节来编号的。
• 增加快速重传机制。虽然上文中没有提及，但是 GBN 和 SR 在收到校验和正确的ACK x，且x不在窗口内时，其策略是什么也不做，坐等超时重发。TCP 在收到三个重复的ACK x时，会在超时到来之前直接重传x字节开始的数据。

TCP 对于乱序到达的报文没有规定怎么处理。实现者可以像 GBN 一样，给接收方只设置一个缓冲区，从而丢弃乱序到达的报文；也可以像 SR 一样，设置多个缓冲区（窗口大小），从而缓存失序到达的报文。