可靠的数据传输实现指南（一）- 基本机制

发表于 | 分类于

写在前面：从上一篇开始，大概会有一系列网络相关的笔记，主要内容整理自《计算机网络：自顶向下方法》这本书，目前在看的是英文版，个人感觉比中文版看起来流畅。原本打算以《计算机网络（第五版）》为主要参考书的，这本与前者相反，是以自底向上的结构组织的，比较下来发现自己更适应前者的思维模式。在整理笔记的时候考虑到一些术语的翻译，也会参考后者，同时查漏补缺。目前看来两本书的涵盖点都挺全面的，相比之下，前者版本更新更快，内容更与时俱进。

在人们离不开网络的当今，我们通过网络交流、购物、协同工作，为了使这些活动能通过网络顺利地进行，我们需要解决网络传输的两大基本问题：

  • 如何提供可靠的数据传输
  • 如何避免网络拥塞以及在拥塞发生时如何恢复

在本篇笔记中，我们先来了解一下实现可靠的数据传输的相关机制。

什么是可靠的数据传输

当我们评价一个人“可靠”时，普遍认同的一点便是交待这个人做的事一定会有个靠谱的结果。那么当我们定义一个数据传输为“可靠”时，又包含了什么要求呢？
主要有三点：

  • 正确性：在传输中数据不会出现位差错，也就是 0 变成 1，1 变成 0
  • 完整性：在传输中不会发生数据丢失
  • 有序性：经传输得到的数据的顺序与其发送顺序一致

一个可靠数据传输协议的诞生

为了满足这三个条件，一个可靠的数据传输协议要用到哪些机制呢？为了更好地理解它们，让我们从零开始设计一个可靠的数据传输协议，就叫它 RDT (Reliable Data Transfer Protocol) 吧，在这个过程中，我们会逐步介绍各个机制及其作用。

RDT 1.0 - 适用于完全可靠的信道

我们都知道网络是一个分层架构的体系，上层的协议依赖于底层协议提供的服务。假如底层已经提供了可靠的信道，那么运行于其上的协议可以认为其数据的可靠性已经得到了保证，自己不需要再做额外的处理。

假设我们的 RDT 是一个运行在具备了可靠数据传输的通道之上的协议，那么它其实不用做什么，下图展示了 RDT 1.0 中发送方与接收方的有限状态机 (finite-state machine, FSM)。
RDT 1.0

「Note」 在上图（及下文的FSM图中），箭头旁边的虚线框中由虚线分隔的上半部分粗体字内容代表触发该状态改变的事件，下半部分代表事件发生后要执行的操作 (actions)。

RDT 1.0 中的发送方和接收方都只有一个状态：

  • 发送方一直处于等待上层的调用状态 - 当上层调用 rdt_send 这个事件发生时，它将上层数据封装成 packet，然后调用下层服务发送数据，然后回到等待上层调用状态，等待下一次被调用。
  • 接收方一直处于等待下层的调用状态 - 当下层调用 rdt_rcv 这个事件发生时，它将数据从底层传过来的 packet 解析出来将其交付给上层，然后回到等待下层调用状态，等待下一波被调用。

然而，如此完美可靠的信道在现实中是不可能存在的，毕竟理想很丰满，就让我们一点点削去理想的血肉，直面骨感的现实吧~

RDT 2.x - 适用于可能会出现位差错的信道

现在我们的信道有了一点小瑕疵，有可能在传输数据的过程中发生位差错，这也就意味着我们收到的数据可能是不正确的。那么问题来了：

  • 接收方如何知道数据是否正确呢？
  • 接收方发现数据出错时要怎么办呢？

校验和与应答机制 Checksum & Acknowledgement

想象一下打电话的场景，如果一方明确接收到对方的消息，为了让对方知道，一般都会实时给出“好的”之类响应，当传过来的消息不清晰时，接收方一般会追问：“我刚刚没听清，请再说一遍。”

用技术术语来描述，“好的”这类消息就被称为肯定应答 (positive acknowledgement, ACK)，“我没听清，请再说一遍”这类消息就被称为否定应答 (negative acknowledgement, NAK)，当接收方收到否定应答时，就会重传消息。在计算机网络中，基于这类重传机制的可靠数据传输协议被称为 ARQ (Automatic Repeat reQuest, 自动重传请求) 协议。

ARQ 协议通过如下几个功能点的组合来处理位差错：

  • 错误检测 (Error Detection) - 要处理位差错，首先要能发现位差错。校验和 (checksum) 是常用的技术。为了实现校验和，我们需要在 RDT 2.0 的 packet 里添加额外的字段
  • 接收方反馈 (Receiver Feedback) - 为了让发送方知道数据出现了差错，接收方要显式地给予反馈，比如上文提到的肯定应答和否定应答。理论上，应答 packet 只要 1 位大小就够了，比如 0 代表 NAK, 1 代表 ACK。
  • 重传 (Retransmission) - 发送方要重传出错的 packet。

下面是 RDT 2.0 的发送方和接收方的 FSM：
RDT 2.0

在上图所示 FSM 中，我们可以看到发送方在发出一个 packet 之后，就一直停在等待应答的状态，直到收到接收方的 ACK 应答才回到等待上层调用的状态，也就说在发送方确认接收方收到上一条消息之后才会发送新的消息，按这种模式运行的协议被称为 停等 (stop-and-wait) 协议。

序号 Sequence Number

RDT 2.0 看起来没问题，事实上，我们忽视了非常致命的一点 —— ACK 和 NAK 消息也可能在传输过程中出错，这种情况要怎么办呢？首先，我们要给 ACK 和 NAK 消息也加上校验和以便检测其是否出错，然后呢？
我们可能采取的方式有如下几种：

  1. 当 A 收到的 ACK 或 NAK 出错时，它可以回复一条“你说啥，请再说一遍。”给 B，正常情况下 B 收到之后重传应答。问题就出在这条“你说啥”可能也出错了，B 没听懂，又给 A 发了一条“你说啥”，然后这条消息也出错了，…。显然，这个方案不可取。
  2. 增加校验和的长度，使得能直接从校验和中恢复消息。这种情况能解决 packet 出错的问题，但是不适用于会丢包的信道。
  3. 若发送方收到出错的 ACK 或 NAK，则重传一遍刚刚传送的数据。这个方案会带来一个新的问题——重复分组 (duplicate packet)。因为 ACK 或 NAK 的出错，发送方可能会多次发送同一个 packet，接收方如何得知当前收到的 packet 是新的还是重传的呢？

为了能区分重复分组，我们可以为每个 packet 添加一个序号 (sequence number)字段。接收方通过读取 packet 的序号就能知道这是否是一个重传的 packet。对于 RDT 2.0 这种 stop-and-wait 协议，1位序号就够了。

下图展示了添加了序号字段的 RDT 2.1 发送方与接收方的 FSM：
RDT 2.1 Sender
RDT 2.1 Receiver
在 RDT 2.1 中，除了引入了序号之外，我们去掉了 NAK，而选择了返回最后一个正确接收的 packet 的 ACK（ACK 包含了该 packet 的序号）来通知发送方数据传输发生了错误，当发送方收到一个 ACK 中的 packet 序号与当前等待应答的 packet 序号不匹配时，就会判定数据传输出错从而触发重传机制。

RDT 3.0 - 适用于会有位差错的丢包信道

在现实环境中，信道不仅可能出现位差错，还可能出现丢包的情况，那么，新的问题来了：

  • 如何检测丢包？
  • 丢包之后怎么办？ - 这个问题应用我们在 RDT 2.x 中已经提到的校验和、肯定/否定应答、序号、重传等机制来解决。

第二个问题有了答案，那如何检测丢包呢？
我们将这个任务交给发送方，当发送方发现一个 packet 发出之后，等待足够久的时间后都没有收到应答，则确认 packet 已丢失。

足够久 是多久呢？至少要大于发送方与接收方之间的一个往返延迟(round-trip delay)，可能包含中间路由器的缓冲时延 + 接收方处理一个 packet 的时间。
不过，最坏情况下的延迟并不好估计，而且有可能很长，然而理想情况下协议应该尽快从丢包中回复，如果每次都等待最坏情况下的延迟时间并不是明智的决定。实际应用中，这个值的任务交给发送方来选择。

等待一段时间后没有收到应答的可能情况会有如下几种：

  • 发送的 packet 丢失
  • 接收方回复的 ACK 丢失
  • packet 或 ACK 并没有丢失，只是延迟太久

然而，作为发送方并不关心丢包的原因，只要一招就能搞定一切 —— 重传。

计时器 Timer

要实现基于时间的重传机制，我们需要一个倒计数定时器 (countdown timer)。
发送方在发送 packet 的同时启动一个定时器，当倒计时结束时还没有收到应答的话，计时器会中断发送方通知其采取适当的动作。

下图展示了引入了计时器的 RDT 3.0 的发送方的 FSM，RDT 3.0 发送方的 FSM 与 RDT 2.1 的相同：
RDT 3.0 Sender

经过逐步地完善，RDT 3.0 终于可以被称之为一个可靠的数据传输协议了。我们注意到在 RDT 3.0 中 packet 的序号始终在 0 和 1 之间交替，因此 RDT 3.0 又被称为交替位协议(Alternating-bit Protocol)。实际上，交替位协议是数据链路层的一个协议。

小结

最后，让我们总结一下在本文中提到的实现可靠数据传输用到的机制：

  • 校验和 Checksum - 用于差错检测
  • 应答机制 Acknowledgement (ACK/NAK) - 接收方通过应答机制通知发送方数据是否正确完整地被接收。应答中将包含了对应的 packet 的序号以便发送方在必要时重传。
  • 序号 Sequence Number - 通过检测序号是否连续或者是否为期待的序号值可判断是否发生丢包；也用于检测重复分组。
  • 计时器 Timer - 考虑到 ACK 也可能丢失，计时器用于判断是否丢包。

RDT 3.0 综合以上四类机制实现了可靠的数据传输，然而作为一个停等协议，它的性能实在是不尽人意。尤其在现在的高速网络中，我们需要效率更高的可靠数据传输协议。
为了达到这一目标，我们还需要引入一个非常重要的机制：

  • 管道化 Pipelining

考虑到篇幅问题，下一篇见~

参考资料

  • Computer Networking: A Top-Down Approach, 7th Edition
  • 计算机网络，第五版