我们现在一步步地研究一系列协议，它们一个比一个更为复杂，最后得到一个完美、可靠的数据传输协议。

1. 经完全可靠信道的可靠数据传输：rdt1.0

首先，我们考虑最简单的情况，即底层信道是完全可靠的。我们称该协议为 rdt1.0, 该协议本身是简单的。下图显示了 rdt1.0 发送方和接收方的有限状态机(Finite-State Machine, FSM) 的定义。

注意到下列问题是重要的，发送方和接收方有各自的 FSM。上图中发送方和接收方的 FSM 每个都只有一个状态。FSM 描述图中的箭头指示了协议从一个状态变迁到另一个状态。(因为上图中的每个 FSM 都只有一个状态，因此变迁必定是从一个状态返回到自身；我们很快将看到更复杂的状态图)

引起变迁的事件显示在表示变迁的横线上方，事件发生时所采取的动作显示在横线下方。如果对一个事件没有动作，或没有就事件发生而采取了一个动作，我们将在横线上方或下方使用符号 ，以分别明确地表示缺少动作或事件。FSM 的初始状态用虚线表示。尽管上图中的 FSM 只有一个状态，但马上我们就将看到多状态的 FSM。因此，标识每个 FSM 的初始状态是非常重要的。

rdt 的发送端只通过 **rdt_send(data)** 事件接受来自较高层的数据，产生一个包含该数据的分组 (经由 **make_pkt (data)** 动作)，并将分组发送到信道中。实际上，rdt_send(data) 事件是由较高层应用的过程调用产生的 (例如，rdt_send())。

在接收端，rdt 通过 **rdt_rcv(packet)** 事件从底层信道接收一个分组，从分组中取岀数据 (经由 **extract(packet, data)** 动作)，并将数据上传给较高层(通过**deliver_data( data)** 动作)。 实际上，rdt_rcv( packet) 事件是由较低层协议的过程调用产生的(例如，rdt_rcv() ) 。

在这个简单的协议中，一个单元数据与一个分组没差别。而且，所有分组是从发送方流向接收方；有了完全可靠的信道，接收端就不需要提供任何反馈信息给发送方，因为不必担心出现差错！注意到我们也已经假定了接收方接收数据的速率能够与发送方发送数据的速率一样快。因此，接收方没有必要请求发送方慢一点！

2. 经具有比特差错信道的可靠数据传输: rdt2.0

底层信道更为实际的模型是分组中的比特可能受损的模型。在分组的传输、传播或缓存的过程中，这种比特差错通常会岀现在网络的物理部件中。我们眼下还将继续假定所有发送的分组(虽然有些比特可能受损)将按其发送的顺序被接收。

在研发一种经这种信道进行可靠通信的协议之前，首先考虑一下人们会怎样处理这类情形。考虑一下你自己是怎样通过电话口述一条长报文的。在通常情况下，报文接收者在听到、理解并记下每句话后可能会说 “0K”。如果报文接收者听到一句含糊不清的话时, 他可能要求你重复那句容易误解的话。这种口述报文协议使用了肯定确认 (positive ac­knowledgment ) (“OK”) 与否定确认 (negative acknowledgmenl) (“请重复一遍)。

这些控制报文使得接收方可以让发送方知道哪些内容被正确接收，哪些内容接收有误并因此需要重复。在计算机网络环境中，基于这样重传机制的可靠数据传输协议称为自动重传请求 (Automatic Repeat reQuest, ARQ) 协议。

重要的是，ARQ 协议中还需要另外三种协议功能来处理存在比特差错的情况：

差错检测功能

首先，需要一种机制以使接收方检测到何时出现了比特差错。前一节讲到，UDP 使用因特网检验和字段正是为了这个目的。在第 5 章中，我们将更详细地学习差错检测和纠错技术。这些技术使接收方可以检测并可能纠正分组中的比特差错。

此刻，我们只需知道这些技术要求有额外的比特 (除了待发送的初始数据比特之外的比特) 从发送方发送到接收方；这些比特将被汇集在 rdt2.0 数据分组的分组检验和字段中。

接收方反馈

因为发送方和接收方通常在不同端系统上执行，可能相隔数千英里, 发送方要了解接收方情况 (此时为分组是否被正确接收) 的唯一途径就是让接收方提供明确的反馈信息给发送方。

在口述报文情况下回答的 “肯定确认” (ACK) 和 “否定确认” (NAK) 就是这种反馈的例子。类似地，我们的 rdt2.0 协议将从接收方向发送方回送 ACK 与 NAK 分组。理论上，这些分组只需要一个比特长；如用 0 表示 NAK，用 1 表示 ACK。

重传功能

接收方收到有差错的分组时，发送方将重传该分组文。

下图说明了表示 rdt2.0 的 FSM，该数据传输协议采用了差错检测、肯定确认与否定确认。

• 发送端
  
  rdt2.0 的发送端有两个状态。在最左边的状态中，发送端协议正等待来自上层传下来的数据。当 rdt_send(data) 事件岀现时，发送方将产生一个包含待发送数据的分组 (sndpkt)，带有检验和 (就像UDP报文段使用的方法)，然后经由 udt_send(sndpkt) 操作发送该分组。
  在最右边的状态中，发送方协议等待来自接收方的 ACK 或 NAK 分组。如果收到一个 ACK 分组 (图 3.10 中符号 rdt_rcv(rcvpkt) && isACK(rcvpkt) 对应该事件)，则发送方知道最近发送的分组已被正确接收，因此协议返回到等待来自上层的数据的状态。如果收到一个NAK分组，该协议重传上一个分组并等待接收 方为响应重传分组而回送的 ACK 和 NAK。
  注意到下列事实很重要：当发送方处于等待 ACK 或 NAK 的状态时，它不能从上层获得更多的数据；这就是说，rdt_send() 事件不可能岀现；仅当接收到 ACK 并离开该状态时才能发生这样的事件。因此，发送方将不会发送 一块新数据，除非发送方确信接收方已正确接收当前分组。由于这种行为，rdt2.0 这样的协议被称为停等 (stop-and-wait) 协议。
• 接收端
  
  rdt2.0 接收方的 FSM 仍然只有单一状态。当分组到达时，接收方要么回答一个 ACK，要么回答一个 NAK，这取决于收到的分组是否受损。在上图中，符号rdt_rcv( rcvpkt) && corrupt( rcvpkt) 对应于收到一个分组并发现有错的事件。

rdt2.0 协议看起来似乎可以运行了，但遗憾的是，它存在一个致命的缺陷。尤其是我们没有考虑到 ACK 或 NAK 分组受损的可能性! （在继续研究之前，你应该考虑怎样解决该问题遗憾的是，我们细小的疏忽并非像它看起来那么无关紧要。至少，我们需要在 ACK/NAK 分组中添加检验和比特以检测这样的差错。

更难的问题是协议应该怎样纠正 ACK 或 NAK 分组中的差错。这里的难点在于，如果一个 ACK 或 NAK 分组受损，发送方无法知道接收方是否正确接收了上一块发送的数据。

考虑我们处理受损 ACK 和 NAK 时的 3 种可能情况/解决办法:

• 情况1：考虑在口述报文情况下人可能的做法。如果说话者不理解来自接收方回答的 “0K” 或 “请重复一遍”，说话者将可能问 “你说什么?”（因此，在我们的协议中引入了一种新型发送方到接收方的分组）。接收方则将复述其回答。
  但是如果说话者的 “你说什么?” 产生了差错，情况又会怎样呢？接收者不明白那句混淆的话是口述内容的一部分还是一个要求重复上次回答的请求，很可能回一句“你说什么？”。于是，该回答可能含糊不清了。显然，我们走上了一条困 难重重之路。
• 情况2：增加足够的检验和比特，使发送方不仅可以检测差错，还可恢复差错。对于会产生差错但不丢失分组的信道，这就可以直接解决问题。
• 情况3：当发送方收到含糊不清的 ACK 或 NAK 分组时，只需重传当前数据分组即可。然而，这种方法在发送方到接收方的信道中引入了冗余分组 (dupli­cate packet)。冗余分组的根本困难在于接收方不知道它上次所发送的 ACK 或 NAK 是否被发送方正确地收到。因此它无法事先知道接收到的分组是新的还是一次
  重传!

3. 给发送分组添加编号: rdt2.1

解决这个新问题的一个简单方法（几乎所有现有的数据传输协议中，包括 TCP 都采用了这种方法）是在数据分组中添加一新字段，让发送方对其数据分组编号，即将发送数据分组的序号（sequence number）放在该字段。

于是，接收方只需要检查序号即可确定收到的分组是否一次重传。对于停等协议这种简单情况，1 比特序号就足够了，因为它可让接收方知道发送方是否正在重传前一个发送分组（接收到的分组序号与最三近收到的分组序号相同），或是一个新分组（序号变化了，用模 2 运算 “前向” 移动）。

因为目前我们假定信道不丢分组，ACK 和 NAK 分组本身不需要指明它们要确认的分组序号。发送方知道所接收到的 ACK 和 NAK 分组（无论是否是含糊不清的）是为响应其最近发送的数据分组而生成的。

下图给出了对 rdt2.1 的 FSM 描述，这是 rdt2.0 的修订版。rdt2.1 的发送方和接收方 FSM 的状态数都是以前的两倍。这是因为协议状态此时必须反映出目前（由发送方）正发送的分组或（在接收方）希望接收的分组的序号是 0 还是 1。值得注意的是，发送或期望接收 0 号分组的状态中的动作与发送或期望接收 1 号分组的状态中的动作是相似的；唯一的不同是序号处理的方法不同。

• 发送方
  协议 rdt2.1 使用了从接收方到发送方的肯定确认和否定确认。当接收到失序的分组时，接收方对所接收的分组发送一个肯定确认。如果收到受损的分组，则接收方将发送一个否定确认。如果不发送 NAK，而是对上次正确接收的分组发送一个 ACK，我们也能实现与 NAK —样的效果。发送方接收到对同一个分组的两个 ACK （即接收冗余ACK (duplicate ACK））后，就知道接收方没有正确接收到跟在被确认两次的分组后面的分组。
  
• 接收方
  

4. 无 NAK 的可靠数据传输协议: rdt2.2

rdt2.1 和 rdt2.2 之间的细微变化在于，接收方此时必须包括由一个 ACK 报文所确认的分组序号 (这可以通过在接收方 FSM 中，在 make_pkt() 中包括参数 ACK 0或 ACK 1来实现)，发送方此时必须检查接收到的 ACK 报文中被确认的分组序号 (这可通过在发送方 FSM 中，在 isACK() 中包括参数 0 或 1 来实现)。

• 发送方

• 接收方

5. 经具有比特出错的丢包信道的可靠数据传输: rdt3.0

rdt2.0, 2.1, 2.2 都是假定数据传输过程中只出现了比特出错，现在不管要针对比特出错的问题，还要针对出现丢包的情况下的解决办法。在 rdt2.2 中已经研发的技术，如使用检验和、序号、ACK 分组和重传等，使我们能给出后一个问题的答案。

有很多可能的方法用于解决丢包问题。这里，我们让发送方负责检测和恢复丢包工作。假定发送方传输一个数据分组，该分组或者接收方对该分组的 ACK 发生了丢失。在这两种情况下，发送方都收不到应当到来的接收方的响应。如果发送方愿意等待足够长的时间以便确定分组已丢失，则它只需重传该数据分组即可。你应该相信该协议确实有效。

但是发送方需要等待多久才能确定已丢失了某些东西呢？很明显发送方至少需要等待这样长的时间：即发送方与接收方之间的一个往返时延（可能会包括在中间路由器的缓冲时延）加上接收方处理一个分组所需的时间。

在很多网络中，最坏情况下的最大时延是很难估算的，确定的因素非常少。此外，理想的协议应尽可能快地从丢包中恢复出来；等待一个最坏情况的时延可能意味着要等待一段较长的时间，直到启动差错恢复为止。因此实践中采取的方法是发送方明智地选择一个时间值，以判定可能发生了丢包（尽管不能确保）。如果在这个时间内没有收到 ACK，则重传该分组。

注意到如果一个分组经历了一个特别大的时延，发送方可能会重传该分组，即使该数据分组及其 ACK 都没有丢失。这就在发送方到接收方的信道中引入了冗余数据分组（duplicate data packet）的可能性。幸运的是，rdt2.2 协议已经有足够的功能（即序号）来处理冗余分组情况。

从发送方的观点来看，重传是一种万能灵药。发送方不知道是一个数据分组丢失，还是一个ACK 丢失，或者只是该分组或 ACK 过度延时。在所有这些情况下，动作是同样的：重传。为了实现基于时间的重传机制，需要一个倒计数定时器（countdown timer），在一个给定的时间量过期后，可中断发送方。因此，发送方需要能做到：

1. 每次发送一个分组（包括第一次分组和重传分组）时，便启动一个定时器；
2. 响应定时器中断（采取适当的动作）；
3. 终止定时器。

下图给出了 rdt3.0 的发送方和接收方 FSM，这是一个在可能出错和丢包的信道上可靠传输数据的协议。

• 发送方
  

下图显示了在没有丢包和延迟分组情况下协议运作的情况，以及它是如何处理数据分组丢失的。

在上图中，时间从图的顶部朝底部移动；注意到一个分组的接收时间必定迟于一个分组的发送时间，这是因为发送时延与传播时延之故。在上图 b~ d 中，发送方括号部分表明了定时器的设置时刻以及随后的超时。

本章后面的习题探讨了该协议几个更细微的方面。因为分组序号在0和1之间交替，因此 rdt3.0 有时被称为比特交替协议（alternating- bit protocol) 。

现在我们归纳一下数据传输协议的要点。在检验和、序号、定时器、肯定和否定确认分组这些技术中，每种机制都在协议的运行中起到了必不可少的作用。至此，我们得到了一个可靠数据传输协议！