3.4.1 Building a Reliable Data Transfer Protocol

我们将从简单到复杂，一步步完善我们的协议，直到它成为一个完美的可靠数据传输协议。

Reliable Data Transfer over a Perfectly Reliable Channel (rdt1.0)

我们首先考虑一个简单情形，即信道是可靠的。我们将这个版本的协议称为 rdt1.0。

rdt1.0 - A protocol for a completely reliable channel

先说明下图中的标记的意思：

圆圈表示状态
箭头表示状态转换的过程
水平线上表示发起状态转换的事件
水平线下表示状态转换事件中的行为

我们可以看到，无论对于发送端还是接收端，都只有一个状态。因为我们假设信道可靠，因此接收端不需要发送任何反馈给发送端。同时，我们也假设了发送和接收速度一致，因此接收端也不需要让发送端减慢发送速度。

在发送端，rdt 通过接口 rdt_send(data) 接受上层（应用层）的数据，然后创建包含数据的包(make_pkt(data))，然后发送打包好的数据包(udt_send(packet))。

在接收端，rdt 通过 rdt_rcv(packet) 从下层（网络层）接受数据包，取出数据(extract(packet))，然后通过 deliver_data(data) 将数据传给上层（应用层）。

Reliable Data Transfer over a Channel with Bit Errors (rdt 2.0)

一个更加实际的模型是假设一个不可靠的信道：在其中传输的数据包的某些 bit 可能出错。此外我们同样假设传输不乱序。

在这样的信道上，我们可以使用如下传输协议保证可靠通信：

对于每个数据包，接收方通知发送方接收成功，或者要求重发。

这样的协议叫做 ARQ (Automatic Repeat reQuest) 协议。我们需要以下行为来解决传输出错问题：

错误检测
我们需要某种机制让接收方发现 bit 错误。例如 UDP 的校验和。这需要额外占用数据包的一些 field
接收方反馈
接收方需要通知发送方接收成功(ACK)还是不成功(NAK)。
重传
接收方没有成功接收的数据，发送方需要重新传输

A protocol for a channel with bit errors

对于发送方，它具有两个状态，即：

等待上层调用
等待接收方回复（此时不能继续发送数据）

开始时，发送方处于 1 状态，当上层调用 rdt_send(data) 时，发送方创建数据包 sndpkt = make_pkt(data, checksum)，其中包括数据包的校验和。然后通过 udt_send(sndpkt) 发送给接收方，此后，发送方进入 2 状态。值得注意的是，此时不能再发起 rdt_send(data)。因此这种协议也成为称为 stop-and-wait 协议。

对于接收方，与 rdt1.0 一样，也仅有一个状态，即等待下层调用。当数据包到达时，接收方判断校验和，并且回复 ACK 或者 NAK。

rdt2.0 看起来似乎能够正常工作，但是有个缺陷：我们并没有处理 ACK 或者 NAK 数据包出错的情形。

考虑以下三种处理 ACK 或 NAK 出错的方式、

发送方 A 请求接收方 B 重发回复
这样不可行。因为如果 A 的这个请求本身也出错了，B 无法知道这是一个新消息还是重发请求。因此， B 也请求 A 重发。这样 B 的上一次消息就变成了该重发请求，即使后来收到 A 的重发请求，也无法收到想要的 ACK 了。
发送方将如何从错误中恢复写入校验和
这样可行。接收方可以在收到错误包之后，利用校验和中的信息恢复数据。
发送方直接重传数据
这样也不可行。这会导致接收方收到重复数据。接收方无法得知这是一个重发的数据还是新数据。

一个简单的解决方案是在数据包中加入一个新的信息，即序号 (sequence number)。这样接收方可以通过序号判断收到的消息是否是一次重传。对于简单的 stop-and-wait 协议，1 bit 的序号就足够。因为最多只有一个未确认的消息。我们将加入这个 fix 的协议称为 rdt 2.1。

rdt2.1 sender

rdt2.1 receiver

rdt2.1 与 rdt2.0 的主要区别是：

发送端在创建数据包时，加入了序号 0 或者 1：sndpkt = make_pkt(0, data, checksum)。而接收方在接收数据时，也明确自己需要收到 0 还是 1。

我们假设 0 号数据成功发送，此时发送方在”wait for ack/nak 0“，接收方转入”wait for 1“状态，但是回复给发送方的 ACK 在传输中出错，此时我们无法再发送新的数据，只能重试发送 0 号数据。接收方再次收到 0 号数据，由于此时是在等待 1 号数据包，于是它再次回复 ACK，并且不改变状态。发送方这次收到了回复，转换状态开始等待 1 号数据包。

我们可能会觉得接收方的状态转换比较复杂，事实上，如果我们在回复时带上最近 ACK 的序号，就不需要 NAK 这一个消息类型。当发送方发现 ACK 还是上一个消息的序号，则继续重发本次的消息。加入这个优化后，可以得到 rdt2.2 协议。

rdt2.2 sender (NAK-free)

rdt2.2 receiver (NAK-free)

Reliable Data Transfer over a Lossy Channel with Bit Errors (rdt3.0)

假设现在在传输过程中除了 bit 错误，还有可能丢失数据包。我们需要再考虑两个问题：如何发现丢包以及如何处理丢包。

我们可以利用超时重传来解决丢包问题。其机制是，如果超过一定时间发送者还未收到接收者对于某一个数据包的回复，则认为丢包并且重传。

问题是需要等待多久。理论上，发送者必须至少等待一个 RTT (round trip time)外加处理数据包的时间。但是，实际中最坏情况的 RTT 很难估计，并且也不希望等待太长时间。所以实际中都是谨慎指定一个时间。

相对于之前的 rdt2.2，rdt3.0 添加了对 timer 的操作。当 timeout 也会重传上一个数据。

rdt3.0 sender

rdt3.0 就是一个真正意义上的可靠数据传输协议了。

总结我们用到的一些机制：

机制	作用	注释
Checksum	检测 bit error
ACK/NAK	接收方通知发送方数据包是否正确收到	包含 ACK/NAK 数据包的 Sequence number
Sequence number	将发送端到接收端到每个数据包编号	接收端若发现 gap，则说明丢包；若发现重复，则说明收到重传的数据