一、前言

  前两天看完了《计算机网络——自顶向下方法》这本书的运输层部分，看完后发现TCP协议太过复杂，所以想写一下TCP的系列博客来加深印象，而这是其中的第三篇。这一篇博客就来谈一谈流水线传输的实现原理，以及TCP是如何实现流水线传输的。


二、正文

 2.1 什么是流水线传输以及为什么需要它

  在谈流水线传输之前，我们先来说一说不用流水线传输是什么情况。假设客户端和服务器建立了一条TCP连接，同时客户端需要向服务器发送一个大文件，此时若TCP没有实现流水线传输，则客户端将如何向服务器发送数据呢？由于网络对数据报长度的限制，TCP会将文件分割成很多的数据段，然后从前往后逐一发送，先发送第一个TCP数据段，当接收到服务器的确认报文后，再发送第二段，以此类推。这样有什么问题？我们发现，客户端在等待数据段在网络中传输，并接收到ACK报文的这段时间，完全是没有工作的，这是一种极大的资源浪费。假设一个数据段的大小是10KB，而客户端将数据送入网络的速率是10M/s，而数据的往返时间（RTT）是1s，由于每次只能传输一个数据段，所以在1s内，只传输了10KB的数据，尽管理论传输速率达到了10M/s，却由于这种逐个传输的机制，导致大部分都没有利用上。而且正是因为这种机制，导致要完整的传输完一份数据的时间大大增加。

  正是为了解决上面所述的问题，才有了流水线传输。流水线传输的原理很简单：连续发送多个数据段，而不需要先等待之前发送的数据段被确认。第一段说的情况中，最大的浪费就是等待ACK到达的这段时间，客户端什么事情都干不了，而流水线就是为了解决这个问题。同样是一份文件，被分成了多个数据段，假设客户端连续发送3个数据段，被服务器确认接收后，再发送3个，以此类推。因为合理利用了等待的时间，这样相比于之前，速度将提升3倍。这就是流水线传输，而每次发送多少个数据段，将由具体的实现决定以及网络拥塞情况动态决定。


 2.2 流水线传输将要面临的问题

  流水线传输和逐个传输有很大的区别，而其中一个非常关键的区别就是：数据段可能不会按顺序到达。在使用逐个传输的机制时，我们完全不需要考虑这个问题，因为每次都只发送一个数据段，等这个发送成功时，再发送下一个，所以数据段一定是按顺序到达的。但是流水线不同，流水线机制中，发送发一次将会发送多个数据，而由于网络的不确定性，这多个数据可能不是通过一条路径到达目的地，所以完全有可能出现靠后的数据段先到达目的地的可能。

  为了接收方在接收到多个数据段后，能够将它们重新按照顺序组合起来，TCP为每一个数据段都进行了编号（TCP报文结构中有一个32位的序号字段），通过这个序号，接收方就可以知道当前收到的数据段是属于完整数据的哪一部分了。假设报文段是按照0，1，2，3，4，5……逐一编号的，虽然具体情况并非如此，但是为了方便我们讨论流水线传输，我们暂且这么认为。接下来我们就来讨论流水线传输的两种理论实现方式——回退N步和选择重传。


 2.2 回退N步（GBN）

  回退N步协议简称为GBN，是流水线传输的一种理论实现方式。在GBN中，将维护一个大小为N的窗口来限制数据的发送，这个窗口其实就是一个区间，而序号落在这个区间内的报文段，都可以不需要等待之前的报文段被确认而直接发送。

  在GBN中，我们可以将所有的报文段序号划分为四个区间：

  1. 已经发送并接收到ACK报文的报文段；
  2. 已经发送但是还没有接收到ACK报文的报文段；
  3. 允许被发送，但是还没有发送的报文段；
  4. 还不能发送的报文段；

  这里我们定义几个变量，方便我们解释后面的内容。假设我们将当前第一个被发送，但是还没有接收到ACK的报文段的序号定义为base，而下一个需要被发送的报文段的序号被定义为nextseqnum，则对于上面的四部分，每一部分都对应一个区间。第一部分的序号将落在[0, base - 1]中，第二部分的序号将落在[base, nextseqnum - 1]，第三部分将落在[nextseqnum, base + N - 1]（N是窗口的长度），最后大于base+N的就是第四部分。而第二和第三部分共同组成了长度为N的窗口。如下图所示：

  在上图中的情况下，发送方还允许发送6个报文段，即属于第三部分的报文段。而为什么需要设置窗口，而不是无限制发送呢？当然是为了不让网络太过拥挤，造成数据发送缓慢甚至丢失的情况。下面我们根据发送方处理各种事件的方式，来进一步了解GBN：

  • 事件一：上层调用接口，向网络中传输数据。此时，发送方将检查窗口中是否有剩余的空间，即窗口中是否包含序号属于第三个区间的报文段。若窗口有空闲，则将数据发出，同时让nextseqnum + 1。若此时窗口中的所有数据段都是已经发送但还没有接收到ACK的数据段，则发送方可以将数据返回给上层，隐式地告诉上层窗口已满，而上层可能会过一段时间再试；或者也可以将上层传递的数据放入缓存，等窗口有空闲区间之后再将数据发送；或者使用同步机制，仅当窗口有空闲时，才允许上层调用发送数据的接口。在实际实现中一般使用第二种。
  • 事件二：接收到一个ACK报文。在GBN中，使用的是累计确认机制（累计确认指的是当接收到n号报文段的ACK报文，表示0 - n号报文段都已经被成功接收），所以当收到一个ACK报文时，窗口将向前移动，直到base的值等于这个ACK报文所确认的下一个报文的序号为止。而此时，又将有更大的序号进入到窗口中，窗口中将产生空闲区间。
  • 事件三：发生超时事件。在GBN中，只有一个计时器，而它记录的是序号为base的报文是否超时，当这个报文段被发出后，超过了指定时间还没有收到ACK报文（表明大概率已经丢失），则发送方将重传所有已经发送但还没有接收到ACK报文的报文段，也就是上面图片中的第二部分。这就是回退N步这个名字的由来。当此事件发生，计时器将被重新启动。

  这里在补充一下发送方的计时器，当接收到一个ACK后，若还存在已经发送但是没有收到ACK的报文段，计时器将重新启动；若不存在，则停止，并等到有数据发出后再启动。说完了发送方，我们再来说说接收方对于各种事件是如何处理的：假设接收方已经成功接收到了报文段0到n-1，此时收到报文n，这是一条按顺序到达的报文，所以接收方直接将数据段交付给上层；但是若收到的不是n，而是n+1，甚至更大，则接收方会将它丢弃，并向发送方回送n-1的ACK报文，表示它目前成功接收到的最大的报文段是n-1（被丢弃的不算成功接收），而发送方在超时后，将重传n，n+1……这就是GBN累计确认的实现原理，接收方每次确认的都是当前已经接收，并且按序到达的最大值。所以对于接收方来说，只需要维护一个变量，即当前期望获得的报文段的序号expectedSeqNum，在上面的例子中expectedSeqNum == n。

  这里就有一个问题，为什么接收方接收到乱序的报文后，不可以先将它缓存下来，等序号更小的报文段到达后，再一同传递给上层？那是因为没有太大的必要性。就拿上面的例子来说，假设报文n丢失，发送方将重传n，n+1，n+2等所有已经发送但还没有接收到ACK的报文，所以接收方就没有必要再缓存之前乱序到达的报文段了。而对于乱序到达的报文，有不小的几率是前面的报文已经丢失。尤其是乱序到达的越多，之前的那些报文丢失的几率越大。


 2.3 选择重传（SR）

  GBN最大的一个缺陷就是，在发生传输超时事件时，可能出现很大程度的无用功。比如说发送方同时发送出了10个报文段，但是第一个报文段丢失，结果将导致这10个报文段都要重传，就算后面9个报文段成功到达，也会被接收方丢弃。而选择重传机制解决了这个问题，因为它将有选择地重传报文段。

  SR与GBN类似，它也维护一个大小为N的窗口，只有序号落在窗口中的报文段才允许被发送。但是和GBN不同，SR的窗口中报文段不会被按顺序确认，后发出的报文也可以被先确认。和上面类似，我们假设窗口的第一个报文段的序号，也就是最先被发出但还没收到ACK的报文段的序号为sned_base，而下一个允许发送的报文段的序号为nextseqnum。和GBN不同，SR的接收方不管报文段是否按顺序到达，都会接收并发送相应的ACK报文，所以对于发送方的窗口，将充斥着三类报文段：

  1. 已经发出，但是还没接收到ACK的报文段；
  2. 已经发出，并成功接收到ACK的报文段；
  3. 可以发送，但是还没有发送的报文段；

  所以SR发送端的报文段的分布如下所示：

  和GBN一样，我们根据SR发送方要处理的事件，来更进一步的了解它：

  • 事件一：上层调用数据传输接口，请求发送数据。此时，发送端将检查窗口中是否还有空闲空间，即窗口中是否还存在可用，但是还没有使用的序号。若存在，则使用nextseqnum指向的序号封装报文段并发送。同时nextseqnum指针向前移动，直到没有空间或者数据发送完毕为止；若不存在空闲序号，则发送方可以将数据返回给上层，隐式地告知上层当前发送接口不可用，可以稍后再试，或者也可以将数据缓存，当窗口有空闲时再发送，或者使用同步机制。
  • 事件二：接收到某个报文段的ACK报文。由于在SR中，接收方发送的ACK报文就是对接收到的报文进行确认，不论是否有序，也就是非累计确认，所以当发送方接收到ACK报文时，将有三种情况。（1）接收到一条已经被确认的报文段的重复ACK（一般是由超时引起），则忽略它；（2）收到一条序号不是send_base的报文段的ACK，则标记这个序号的报文已经被确认；（3）收到序号为send_base的报文的ACK报文，此时send_base指针向前移动，直到移动到第一个已经发送但是还没有被确认的报文序号为止。比如上图，接收到了send_base和send_base+1的ACK报文，则此时send_base将更新为send_base+4。
  • 事件三：报文超时。由于在SR中，报文可以无序到达，所以在理论实现中，需要为每一个已经发送的报文段都绑定一个计时器，来记录此报文是否超时。若某个已经发送的报文段的计时器超时，发送方将重传对应的报文，注意，和GBN不同，SR只重传超时的那条报文。

  说完了发送方，再来说一说接收方。在SR机制中，发送方若接收到一个乱序报文段，不会将其丢失，而是放入到接收缓存中，然后等待序号更小的报文段都到达后，再取出交付给上层。所以对于接收方来说，报文序号分为四类：

  1. 期待接收到的报文段，即下一条想要的报文段；
  2. 已经接收，但不是按顺序到达报文段；
  3. 可以接收的报文段；
  4. 暂时还不能接收的报文段；

  而接收方也是通过维护一个大小为N的窗口来管理这些报文段。同时，在接收方维护了一个变量rcv_base，表示窗口的第一个报文段的序号，其实也就是下一条期待接收的报文。至于为什么接收方也需要维护一个窗口限制接收，是因为接收缓存的大小有限，假设期待接收到的报文一直没有到达，到达的一直都是乱序的报文，此时接收方要将它们放入接收缓存，但是由于接收缓存大小有限，所以不能无限制地接收，只能通过窗口来限制可以接收的范围。下面就是接收窗口的模型图：

  对于接收方来说，若接收到一条报文，将会分为四种情况进行处理：

  1. 接收到的报文段的序号为rcv_base。此时rcv_base将向前移动，直到到达第一个没有被接收的序号为止，这样意味着窗口在向前移动，并腾出了新的空闲区间；
  2. 接收到的报文序号在窗口中，但不是rcv_base。此时，若这个报文之前已经接收过，则直接发送此报文对应的ACK报文，但是不接收；若没有接收过，则将此报文放入接收缓存中，再发送ACK报文；
  3. 接收到的报文序号小于rcv_base，则表示这条报文已经被接收过，直接发送一个ACK报文，但是不接收此报文段；
  4. 除上述外，其他报文段都忽略；

  这里再讨论一下为什么接收方会接收到已经接收过的报文段。原因就是ACK报文超时到达接收方，或者ACK报文丢失，所以导致了发送方对报文段进行重传。而此时，为了让发送方知道自己已经成功接收，接收方需要再次发送此报文段的ACK报文，而不是忽略它。


 2.4 TCP的流水线传输

  上面两种流水线传输机制是两种理论模型，而实际的TCP流水线传输，是对这两种模型的结合和改进，抽取了各自好的部分，弥补对方不足的部分。在TCP的流水线传输机制中，和GBN一样使用的是累计确认，同时只使用一个计时器，用来记录窗口中的第一个报文段是否超时，同时只重传丢失的分组；对于接收方，接收到不按照顺序到达的报文段，不会丢弃，而是放入接收缓存。下面我就来说一说TCP的流水线传输是如何实现的。

  对于发送方，TCP的流水线传输与GBN有着高度的相似性。同样一个大小为N的窗口，同样一个base和一个nextseqnum变量，同样的序号划分，也就是如下图所示的模型：

  同样的累计确认，同样的序号划分，同样的单一计时器，所以发送端的实现几乎一致，除了最重大的一个地方。GBN最大的缺陷就是当超时事件发生时，会进行大量不必要的重传，而TCP的流水线传输避免了这个问题。这里的计时器记录的是序号为base的数据段是否超时，若发生超时事件时，发送方只会重传序号为base的报文段，而不会重传后续的这些已经发送但还没有接收到ACK的报文段。而且除此之外，这里还使用到了一个叫快速重传的机制，提高效率。除了重传，TCP流水线传输的发送方基本上与GBN相同。

  下面再来说一说接收方。在TCP传输的接收方，也会维护一个和SR类似的接收窗口，来限制数据的接收。也就是和SR一样的模型图：

  但是实际的接收方式，相对于SR来说，有了很大的改变。在接收方，若接收到一条报文，将产生以下几种情况：

  1. 接收到按序到达的报文，也就是序号为rcv_base的报文，则rcv_base向前移动，也就是窗口向前移动，直到移动到第一个没有接收到的序号为止，同时对新的rcv_base的前一条报文进行确认。比如上面这张图，接收到rcv_base后，窗口将移动到rcv_base+4，而确认报文将是对rcv_base+3的确认，表示已经接收到rcv_base+3及其之前全部报文；
  2. 接收到的报文序号不是rcv_base，但是依旧落在窗口内，则发送确认报文，但是是对rcv_base - 1这个报文的确认，表示现在接收方已经接收到的按序的报文中，最大值是rcv_base - 1，下一条需要的是rcv_base。同时，再判断这条报文是否已经有缓存，若没有，则加入到接收缓存中；

  由于TCP的流水线传输使用的是累计确认，所以没有必要每接收到一条报文，都进行一次确认，而是有选择地进行确认，这样可以减少传输ACK报文的数量，节省网络资源。而在TCP规范中，对于何时传输ACK，给出了几条建议：

  1. 接收到序号为rcv_base的报文段时，若这之前的报文都已经确认过了，则延迟ACK报文的发送，等待另一个报文段的到达（最多等待500毫秒），若在等待的过程中，另一条按顺序的报文段到达，则直接发送那条报文的确认，同时确认了两条报文；若这段时间内无有序报文到达，则发送当前报文的确认；
  2. 接收到序号为rcv_base的报文段时，若在这之前还有没被确认的报文，比如说前一条报文在等待当前报文的到达（情况一），则立即发送一个ACK，确认这两条报文；
  3. 接收到一个序号比rcv_base大的报文段，表示出现了乱序，此时立即发送一个ACK报文，告知发送方下一条需要的是rcv_base；
  4. 若接收到的报文段序号是rcv_base，同时之前已经接收了一些乱序的报文段，则立即发送ACK报文；

  上面四种建议中，1-2条是为了更少地发送ACK报文，而3-4条则是快速重传机制的依据（尤其是第三条）。这种实现，也有另外一种叫法，叫做选择确认。


 2.5 窗口大小的限制

  在流水线传输中，需要注意一个问题，那就是窗口不能太大，否则将会出现问题。序号不是无限大的，比如在实际实现中，序号是一个32位的int整数，所以当序号超过最大值时，将对最大值取模，重新获取一个较小的值作为序号。也就是说，序号范围实际可以看成一个环，而在这个环中，有两个窗口，一个是接收窗口，而一个是发送窗口。看下面一种情况，假设序号只有0，1，2，3这四个，窗口大小N == 3：

  • 初始时刻，发送方的窗口是0，1，2，而接收方的窗口也是0，1，2；

  • 发送方发送报文0，1，2，到达接收方后，接收方的发送确认报文，同时窗口移动，变为3，0，1；

  • 确认报文没有按时到达发送方，于是发送方重传报文段0；

  • 接收方接收到后，检查自己的窗口，发现序号0在窗口中，而且并未接收，于是将此报文当作一个新的报文段接收；

  上面发生了什么？由于窗口太大，出现了序号重叠的现象，也就是在这个序号环中，接收窗口的头，触碰到了发送窗口的尾。为了避免这个问题，窗口长度必须小于等于总区间长度的一半。因为发送窗口的头和接收窗口的尾一定是重合的，而为了让发送窗口的尾不碰到接收窗口的头，必须使它们两个的长度之和小于等于总区间长度。


三、总结

  长篇大论快给我写吐了，就不多说了。总之，希望这篇博客对看到的人有所帮助，若是发现错误的部分，也希望能够提出来。


四、参考

  • 《计算机网络——自顶向下方法（原书第七版）》