停等协议的坏处

由于停等协议必须等待 ACK 到来以后才能发送下一个分组，造成其效率低下，下面通过一个简单的例子来看一下它的效率到底有多低。

rdt3.0 是一个功能正确的协议，但并非人人都对它的性能满意，特别是在今天的高速网络中更是如此。rdt3.0 性能问题的核心在于它是一个停等协议（必须的等到上一个分组的 ACK 能够正确地被接收到，才发送下一个分组）。

假设现在有两个电脑相互通信，通信的分组大小为 1000 字节，往返的传播时延 RTT 大约为 30 毫秒。假定彼此通过一条发送速率 R 为 1Gbps 的信道相连，则将一个分组从电脑发送 1Gbps 链路需要的时间为：

由上面知道 1 个分组的大小为 1000Byte=8000bit，则从电脑往链路发送一个分组需要的传输时间为

下图显示了对于该停等协议，如果发送方在 t=0 时刻开始发送分组，则在 后，最后 1 比特数据进入了发送端信道。该分组经过 15ms 的时间到达接收端，该分组的最后 1 比特在时刻 时到达接收方。

了简化起见，假设 ACK 分组很小（以便我们可以忽略传输时间），接收方一旦收到一个数据分组的最后 1 比特后立即发送 ACK，ACK 在时刻 时在发送方出现。

此时，发送方可以发送下一个报文。因此，在30. 008ms 内，发送方的发送只用了 0.008ms。如果我们定义发送方（或信道）的利用率（utilization）为：发送方实际忙于将发送比特送进信道的那部分时间与发送时间之比，上图中的分析表明了停等协议有着常低的发送方利用率 Usender:

在发送方将第一个分组送出去之后就等着它的确认消息 ACK 到来，而这个过程是相当耗时间的，所以造成了利用率不够高（类似于程序中的单线程，只要一步卡住了，接下来的部分就不能继续了）。

由停等协议到流水线协议

这种特殊的性能问题的一个简单解决方法是：不以停等方式运行，允许发送方发送多个分组而无须等待确认，如在下图所示的那样。

下图显示了如果发送方可以在等待确认之前发送 3 个报文，其利用率也基本上提高 3 倍。因为许多从发送方向接收方输送的分组可以被看成是填充到一条流水线中，故这种技术被称为流水线（pipelining）。流水线技术对可靠数据传输协议可带来如下影响

• 必须增加序号范围，因为每个输送中的分组（不计算重传的）必须有一个唯一的序号，而且也许有多个在输送中的未确认报文。
• 协议的发送方和接收方两端也许不得不缓存多个分组。发送方最低限度应当能缓冲那些已发送但没有确认的分组。如下面讨论的那样，接收方或许也需要缓那
  些已正确接收的分组。
• 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。解决流水线的差错恢复有两种基本方法是：回退N步（Go-Back-N,
  GBN) 和选择重传 (Selective Repeat, SR)。

基于流水线机制的可靠数据传输协议

回退N步(GBN)协议

在回退 N 步（GBN）协议中，允许发送方发送多个分组（当有多个分组可用时）而不需等待确认，但它也受限于在流水线中未确认的分组数不能超过某个最大允许数 N。在本节中我们较为详细地描述 GBN。

关于 GBN 协议，作者提供了一个 Java 小程序帮助理解，点击链接前往动手操作：Go-Back Protocol (pearsoncmg.com)

下图显示了发送方看到的 GBN 协议的序号范围。如果我们将基序号（base）定义为最早未确认分组的序号，将下一个序号（nextseqnum）定义为最小的未使用序号（即下一个待发分组的序号），则可将序号范围分割成4段。

• 在 [0, base-1] 段内的序号对应于已经发送并被确认的分组。
• [base, nextseqnum-1] 段内对应已经发送但未被确认的分组。
• [nextseqnum, base+N-1] 段内的序号能用于那些要被立即发送的分组，如果有数据来自上层的话。
• 大于或等于 base + N 的序号是不能使用的，直到当前流水线中未被确认的分组（特别是序号为 base 的分组）已得到确认为止。

如上图所提示的那样，那些已被发送但还未被确认的分组的许可序号范围可以被看成是一个在序号范围内长度为 N 的窗口。随着协议的运行，该窗口在序号空间向前滑动。因此，N 常被称为窗口长度（window size）， GBN 协议也常被称为滑动窗口协议 （sliding-window protocol）。

你也许想知道，我们为什么先要限制这些被发送的、未被确认的分组的数目为 N 呢？为什么不允许这些分组为无限制的数目呢？大概的原因有两个：

1. 流量控制是对发送方施加限制的原因之一
2. TCP拥塞控制是另一个原因。

在实践中，一个分组的序号承载在分组首部的一个固定长度的字段中。如果分组序号字段的比特数是 ，则该序号范围是 [0, 2k-1]。在一个有限的序号范围内，所有涉及序号的运算必须使用模 2k 运算。（即序号空间可被看作是一个长度为 2k 的环，其中序号 2k-1 紧接着序号 0）。前面讲过，rdt3.0 的分组序号最大为 1，所以序号范围是 [0, 1]。 TCP 有一个 32 比特的序号字段，其中的 TCP 序号是按字节流中的字节进行计数的，而不是按分组计数。

下图给出了一个基于 ACK、无 NAK 的 GBN 协议的发送方和接收方这两端的扩展 FSM 描述。我们称该 FSM 描述为扩展 FSM，是因为我们已经增加了变量（类似
于编程语言中的变量）base 和 nextseqnum，还增加了对这些变量的操作以及与这些变量有关的条件动作。注意到该扩展的 FSM 规约现在变得有点像编程语言规约。

• 发送方
  
• 接收方
  

GBN 发送方必须响应三种类型的事件：

• 上层的调用。当上层调用 rdt_send() 时，发送方首先检查发送窗口是否已满，即是否有 N 个已发送但未被确认的分组。如果窗口未满，则产生一个分组并将其发送，并相应地更新变量。如果窗口已满，发送方只需将数据返回给上层，隐式地指示上层该窗口已满。然后上层可能会过一会儿再试。在实际实现中，发送方更可能缓存（并不立刻发送）这些数据，或者使用同步机制（如一个信号量或标志）允许上层在仅当窗口不满时才调用 rdt_send()。
• 收到一个 ACK。在 GBN 协议中，对序号为几的分组的确认采取累积确认（cumu­lative acknowledgment）的方式，表明接收方已正确接收到序号为 n 的以前且包括 n 在内的所有分组。稍后讨论 GBN 接收方时，我们将再次研究这个主题。
• 超时事件。协议的名字 “回退N步” 来源于出现丢失和时延过长分组时发送方的行为。就像在停等协议中那样，定时器将再次用于恢复数据或确认分组的丢失。如果出现超时，发送方重传所有已发送但还未被确认过的分组。下图中的发送方仅使用一个定时器，它可被当作是最早的已发送但未被确认的分组所使用的定
  时器。如果收到一个 ACK，但仍有已发送但未被确认的分组，则定时器被重新启动。如果没有已发送但未被确认的分组，停止该定时器。

在 GBN 中，接收方的动作也很简单。如果一个序号为 n 的分组被正确接收到，并且按序（即上次交付给上层的数据是序号为 n-1 的分组），则接收方为分组发送一个 ACK，并将该分组中的数据部分交付到上层。在所有其他情况下，接收方丢弃该分组，并为最近按序接收的分组重新发送 ACK。注意到因为一次交付给上层一个分组，如果分组 k 已接收并交付，则所有序号比 k 小的分组也已经交付。因此，使用累积确认是 GBN —个自然的选择。

在 GBN 协议中，接收方丢弃所有失序分组。尽管丢弃一个正确接收（但失序）的分组有点愚蠢和浪费，但这样做是有理由的。前面讲过，接收方必须按序将数据交付给上层。假定现在期望接收分组 n 而分组 n+1 却到了。因为数据必须按序交付，接收方可能缓存（保存）分组 n+1。然后，在它收到并交付分组 n 后，再将该分组交付到上层。然而，如果分组 n 丢失，则该分组及分组 n+1最终将在发送方根据 GBN 重传规则而被重传。因此，接收方只需丢弃分组 n+1 即可，不需要缓存任何失序分组。因此，虽然发送方必须维护窗口的上下边界及 **nextseqnum** 在该窗口中的位置，但是接收方需要维护的唯一信息就是下一个按序接收的分组的序号。当然，丢弃一个正确接收的分组的缺点是随后对该分组的重传也许会丢失或出错，因此甚至需要更多的重传。

下图给岀了窗口长度为 4 个分组的 GBN 协议的运行情况

因为该窗口长度的限制，发送方发送分组 0~3，然后在继续发送之前，必须等待直到一个或多个分组被确认。当接收到每一个连续的 ACK （例如 ACK0 和 ACK1）时，该窗口便向前滑动，发送方便可以发送新的分组（分别是分组 4 和分组 5）。在接收方，分组 2 丢失，因此分组 3、4 和 5 被发现是失序分组并被丢弃。

选择重传(SR)协议

GBN 协议潜在地允许发送方用多个分组 “填充流水线”，因此避免了停等协议中所提到的信道利用率问题。然而，GBN 本身也有一些情况存在着性能问题。尤其是当窗口长度和带宽时延积都很大时，在流水线中会有很多分组更是如此。单个分组的差错就能够引起 GBN 重传大量分组，许多分组根本没有必要重传。随着信道差错率的增加，流水线可能会被这些不必要重传的分组所充斥。

顾名思义，选择重传（SR）协议通过让发送方仅重传那些它怀疑在接收方出错（即丢失或受损）的分组而避免了不必要的重传。这种个别的、按需的重传要求接收方逐个地确认正确接收的分组。再次用窗口长度 N 来限制流水线中未完成、未被确认的分组数。

然而，与 GBN 不同的是，发送方已经收到了对窗口中某些分组的 ACK。下图显示了 SR 发送方看到的序号空间。

下面详细描述了 SR 发送方所采取的动作。

SR 发送方的事件与动作
1. 从上层收到数据。当从上层接收到数据后，SR 发送方检查下一个可用于该分组的序号。如果序号位于发送方的窗口内，则将数据打包并发送；否则就像在 GBN 中一样，要么将数据缓存，要么将其返回给上层以便以后传输。
2. 超时。定时器再次被用来防止丢失分组。然而，现在每个分组必须拥有其自己的逻辑定时器，因为超时发生后只能发送一个分组。可以使用单个硬件定时器模拟多个逻辑定时器的操作。
3. 收到 ACK。如果收到 ACK,倘若该分组序号在窗口内，则 SR 发送方将那个被确认的分组标记为已接收。如果该分组的序号等于 send_base,则窗口基序号向前移动到具有最小序号的未确认分组处。如果窗口移动了并且有序号落在窗口内的未发送分组，则发送这些分组

SR 接收方将确认一个正确接收的分组而不管其是否按序。失序的分组将被缓存直到所有丢失分组（即序号更小的分组）皆被收到为止，这时才可以将一批分组按序交付给上层。下面详细列出了 SR 接收方所采用的各种动作。

SR 接收方的事件与动作
1. 序号在［rcv_base, rcv_base +N-1] 内的分组被正确接收口在此情况下，收到的分组落在接收方的窗口内，一个选择ACK被回送给发送方。如果该分组以前没收到过，则缓存该分组。如果该分组的序号等于接收窗口的基序号。则该分组以及以前缓存的序号连续的（起始于 rcv_base 的）分组交付给上层。然后，接收窗口按向前移动分组的编号向上交付这些分组。
2.序号在［rcv_base-N, rcv_base-1] 内的分组被正确收到。在此情况下，必须产生一个 ACK,即使该分组是接收方以前已确认过的分组。
3.其他情况。忽略该分组。

注意到上述 SR 接收方动作中的第 2 步很重要，接收方重新确认（而不是忽略）已收到过的那些序号小于当前窗口基序号的分组。你应该理解这种重新确认确实是需要的。

下图给出了一个例子以说明出现丢包时 SR 的操作。值得注意的是，在下图中接收方初始时缓存了分组3、4、5，并在最终收到分组 2 时.才将它们一并交付给上层。

当我们面对有限序号范围的现实时，发送方和接收方窗口间缺乏同步会产生严重的后果。考虑下面例子中可能发生的情况，该例有包括4个分组序号0、1、2、3的有限序号范围且窗口长度为 3。

假定发送了分组 0 至 2，并在接收方被正确接收且确认了。此时, 接收方窗口落在第4、5、6个分组上，其序号分别为3、0、1。现在考虑两种情况。

在第一种情况下，如下图所示，对前 3 个分组的 ACK 丢失，因此发送方重传这些分组。因此，接收方下一步要接收序号为 0 的分组，即第一个发送分组的副本。

在第二种情况下，如下图所示，对前 3 个分组的 ACK 都被正确交付。因此发送方向前移动窗口并发送第4、5、6个分组，其序号分别为3、0、10序号为 3 的分组丢失， 但序号为 0 的分组到达（一个包含新数据的分组）。

现在考虑一下上述两种情况中接收方的观点，在发送方和接收方之间有一个假想的帘子，因为接收方不能 “看见” 发送方采取的动作。接收方所能观察到的是它从信道中收到的以及它向信道中发出报文序列。就其所关注的而言，上述两种情况是等同的。

没有办法区分是第 1 个分组的重传还是第 5 个分组的初次传输。显然，窗口长度比序号空间小 1 时协议无法工作。但窗口必须多小呢？本章后面的一道习题请你说明为何对于 SR 协议而言，窗口长度必须小于或等于序号空间大小的一半。

进入 Java 小程序，手动查看 SR 协议的细节：https://media.pearsoncmg.com/ph/esm/ecs_kurose_compnetwork_8/cw/content/interactiveanimations/selective-repeat-protocol/index.html

总结：可靠数据传输协议

至此我们结束了对可靠数据传输协议的讨论。我们已涵盖许多基础知识，并介绍了多种机制，这些机制可一起提供可靠数据传输。下表总结这些机制。既然我们已经学习了所有这些运行中的机制，并能看到 “全景”，我们建议你再复习一遍本节内容，看看这些机制是怎样逐步被添加进来，以涵盖复杂性渐增的（现实的）连接发送方与接收方的各种信道模型的，或者如何改善协议性能的。

可靠数据传输机制及其用途的总结

我们通过考虑在底层信道模型中的一个遗留假设来结束对可靠数据传输协议的讨论。 前面讲过，我们曾假定分组在发送方与接收方之间的信道中不能被重新排序。这在发送方与接收方由单段物理线路相连的情况下，通常是一个合理的假设。

然而，当连接两端的 “信道” 是一个网络时，分组重新排序是可能会发生的。分组重新排序的一个表现就是，一个具有序号或确认号 x 的分组的旧副本可能会出现，即使发送方或接收方的窗口中都没有包含 x。对于分组重新排序，信道可被看成基本上是在缓存分组，并在将来任意时刻自然地释放岀这些分组。

由于序号可以被重新使用，那么必须小心，以免出现这样的冗余分组。实际应用中采用的方法是，确保一个序号不被重新使用，直到发送方 “确信” 任何先前发送的序号为咒的分组都不再在网络中为止。通过假定一个分组在网络中的 “存活” 时间不会超过某个固定最大时间量来做到这一点。在高速网络的TCP扩展中，最长的分组寿命被假定为大约 3 分钟。