流水线技术：解决停等协议对物理资源的浪费
流水线可靠数据传输协议
rdt3.0性能问题的核心在于它是一个停等协议。
在停等协议中，发送方发完数据之后，必须进入等待ACK/NAK状态等待来自接收方的反馈信息。在等待状态中，发送方无法发送新一批的数据。这就造成了效率低下的问题。
解决方法是：不使用停等方式，允许发送方发送多个分组而无需等待反馈信息。即使用流水线技术。
比如，允许发送方在收到等待确认之前可以发送三个分组，那么效率也将提升3倍。
流水线技术将给可靠数据传输协议带来一下影响：
- 必须增加序号范围。因为每次输送有多个分组，所以只有0，1两个序号不够用了。
- 发送方和接收方需缓存多个分组。
- 所需要的序号范围和对缓存的要求取决于协议如何处理丢失、损坏及延时过大的分组。
解决流水线的差错恢复有两种基本方法：
- 回退N步（Go-Back-N，GBN）
- 选择重传（Selective Repeat，SR）
接下来将展开讲述GBN和SR。
回退N步（GBN）
在GBN协议中，允许发送方发送多个分组而无需等待反馈消息。但是GBN也不是说发送方可以无节制的发送，我们限制在流水线中已发送但未被确认的分组数目不能超过N。这主要是出于流量控制的原因。
- [0, base-1]是已发送且被确认的分组的序号。
- [base, nextseqnum-1]是已发送但未被确认的分组的序号。
- [nextseqnum, base+N-1]是给那些即将发送的分组使用的序号。
- [base+N, +∞]是不可用的序号。
所以在极端情况下，[base, base+N-1]这N个序号可以都是已发送但未被确认的分组。这种情况下，发送方不能再发送新分组了，因为没有可用的序号分配给新分组，发送方只能等待，等待序号base的分组得到接收方的确认，这时候这个长度为N的窗口就会向前滑动，就会有一个新的可用序号分配给即将发送的新分组使用，这样发送方就又可以发送分组了。
随着协议运行，窗口在序号空间向前滑动，因此N被称为窗口长度，GBN协议也被称为滑动窗口协议。
下面两图给出了一个基于ACK、无NAK的GBN协议的发送方和接收方的扩展FSM。
GBN发送方必须响应三种事件：
- 上层的调用。当上层调用
rdt_send(data)时，发送方首先检查发送窗口是否已满（即是否有N个已发送但未被确认的分组）。如果没满，则产生一个分组并将其发送，并更新变量（nextseqnum加1，即又多了一个已发送但未被确认的分组）；如果满了，则拒绝上层的数据，隐式地告诉上层，发送窗口满了，你等等再发吧。 - 收到一个ACK。GBN采取累计确认方式，即如果收到ACK n，则表示序号为n的分组以及n之前的所有分组，均已正确接收。
- 超时事件。GBN的名字回退N步来源于出现丢失和时延过长分组时发送的行为。如果出现超时，发送方将重传所有已发送但未被确认的分组。
GBN的接收方也很简单。如果一个序号为n的分组被正确接收，且是按序的（也就是说上次将给上层的是序号为n-1的分组），那么接收方将反馈ACK n并把分组n中的数据交给上层。除此之外的所有其他情况，接收方直接丢弃该分组，并为最近按序接收的分组反馈一个ACK。
也就是说，假定期望收到分组n，但是收到了分组n+1，由于数据必须按序交付，所以接收方会把n+1丢掉，即便这有点浪费。
可能会有人有疑问，为什么不让接收方把n+1缓存起来，等n到了并把n交付给上层之后，直接从缓存里取出n+1交付给上层不好吗？这样不省去一次重传吗？
答案是不会的。因为前边说过了GBN的重传规则，这种情况下，发送方只能收到ACK n-1，收不到ACK n，那么超时事件会被触发，这时候发送方一定会重传分组n，所以接收方其实没必要去缓存收到的失序分组，因为并不能省去一次重传。
所以GBN协议接收方不需要缓存失序分组。
GBN发送方维护着窗口的上下边界以及nextseqnum在窗口的位置；GBN接收方仅需要维护下一个按序接收的分组的序号，也就是说接收方只要清楚自己下一次想要哪个分组就OK了。
下图展示了一个窗口长度为4的GBN协议的运行情况。
选择重传（SR）
尽管GBN协议使用流水线技术避免了停等协议对信道资源的浪费，但是GBN本身也存在一些性能问题。当窗口长度和带宽时延积都很大时，流水线中将充斥着很多分组，而按照GBN的重传规则，一个分组的差错就会引起大量分组的重传，许多分组其实根本没必要重传（比如上例中的分组3、4、5）。
带宽时延积：链路上的最大比特数，也称以比特为单位的链路长度。带宽时延积是传播时延和带宽的乘积。
基于对GBN无脑大量重传的不满，我们引出选择重传即SR协议。顾名思义，选择重传通过仅让发送方重传那些它怀疑出错了的分组，而避免大量的无必要重传。
下面来看一下SR如何实现这种选择性重传。
SR与GBN的不同之处：
- SR接收方不再采取累计确认，而是逐个确认。
- SR接收方会缓存收到的失序分组。
- SR接收方也需要维护一个接收窗口。
SR发送方响应三种事件：
- 上层的调用。当收到上层的数据时，SR发送方检查下一个可用于该分组的序号。如果序号在发送方窗口内，就把该分组打包发送；如果不在窗口内，那么说明发送窗口满着呢，跟GBN一样，告诉接收方，你先别发了。
- 超时。同样的，使用定时器防止丢失分组。
- 收到ACK。这里要分两种情况。如果这个ACK所确认的分组序号是
send_base，那说明这个分组按序到达且接收方可把它直接交付给接收方上层。这样，窗口就可以向前滑动，滑动到具有最小序号的未确认分组处；第二种情况，如果这个ACK确认的序号不是send_base，而是窗口内其他序号，那说明这个分组是个失序分组，接收方已经把它缓存起来了。这个时候窗口就不能向前滑动。
SR接收方的事件与动作如下：
上图的第2步比较重要，接收方重新确认已经收到过的那些序号小于当前窗口基序号的分组。
下图展示一个SR协议的运行情况：
SR的困境：发送方与接收方窗口间不同步
在有限的序号范围内，发送方和接收方窗口间缺乏同步会产生严重后果。我们假定序号范围为0~3，看一下：
在图a）中，发送方发送了前三个分组，然后开始等待ACK，这三个分组接收方都收到了，反馈了ACK，接收方窗口向前滑动，准备接受第4、5、6个分组了。不幸的是，ACK全部丢失，发送方等不到前三个分组的ACK，发送方窗口无法向前滑动，直到超时触发，发送方重传前三个分组。这时候接收方又收到了一个序号为0的分组。
这个序号为0的分组，是第一个分组的重传，而不是当前接收方窗口内的序号为0的第五个分组。
在图b)中，发送方发送了前三个分组，然后接收方收到了这三个分组并且反馈了ACK，接收方窗口向前滑动。发送方收到ACK 0后发送方窗口也向前滑动，发送第四个分组，不幸的是分组3丢失了，收到ACK 1后，发送方窗口又向前移动，发送第五个分组（序号为0）。这时候接收方又收到一个序号为0的分组。
这个序号为0的分组，是第五个分组的第一次传输，而不是第一个分组的重传。
以上两种情况，从接收方来看，是完全一样的。我们清楚二者不同，是因为我们在上帝视角。而接收方看不到发送方采取的动作。接收方只知道自己收到了的分组以及它自己发送的ACK。也就是说发送方和接收方之间有一个帘子。所以，接收方根本不知道这个新收到的序号为0的分组是新分组还是旧分组的重传。
所以，按照上例，窗口长度比序号空间小1时，SR协议无法工作。那么窗口要多小才合适呢？窗口长度必须小于或等于序号空间大小的一半。
总结
停等协议
rdt1.0：底层信道完全可靠。
rdt2.0：加入校验和进行差错检测，并采用ACK/NAK机制以及重传机制进行差错恢复，实现了经具有比特差错信道的可靠数据传输协议。
rdt2.1：加入序号机制解决冗余分组问题。
rdt2.2：只有ACK、无NAK。
rdt3.0：加入超时机制，实现经具有比特差错的丢包信道的可靠数据传输协议。
流水线
GBN：采用流水线技术解决了停等协议对信道利用不充分的问题。但是存在缺陷：累计确认无脑重传导致大量不必要重传的分组充斥在流水线中。
SR：通过让接收方也维护一个接收窗口，并且接收方缓存失序分组以及逐个确认的方式，使得发送方仅重传需要重传的分组。
字节跳动公司氛围 560人发布