持续创作，加速成长！这是我参与「日新方案 10 月更文应战」的第9天

流水线可靠数据传输协议

rdt3.0，在功能上现已是一个齐备的协议，但它的功能并不高，原因就在于它是一个停等协议，发送一个分组时单独占用一个信道，后一个分组有必要等前一个分组传完之后才能传，也便是说发送方一次只能发送一个数据，它的信道利用率是极低的，就像这样：

可靠数据传输——GBN协议和SR协议

咱们处理这个问题的一个办法便是不以停等的办法运转，答应发送方发送多个分组无需等待，即：

可靠数据传输——GBN协议和SR协议

发送方一次发送多个分组的办法称为流水线（pipeline）技能 ，关于流水线技能，咱们应该留意：

  • 添加序号规模，每个在传输中的分组有必要有仅有序号，可见之前的0和1现已不能满足流水线的需求。
  • 发送方和接纳方需求缓存多个分组。
  • 所需序号规模和对缓冲的要求取决于数据传输协议如何处理丢掉、损坏以及延时大的分组。

其间第三点是摘录的top-down原话，要很好的解说它，咱们有必要先引出滑动窗口的内容。

滑动窗口（Slide Window）协议

在了解什么是滑动窗口之前，咱们先回想一下之前的内容。rdt协议中，发送方一次发送一个分组，接纳方一次接纳一个分组。可是人们不满足rdt协议的功能，所以提出流水线技能，使发送方一次发送多个分组，所以发送方需求缓存多个分组，按照缓存区内分组的不同类型，咱们大约能够分为以下几种：①已发送且被承认的分组 ②已发送但未被承认的分组 ③待发送的分组

咱们把已发送但未承认的分组和待发送的分组的区域称为发送缓冲区，图中N即为缓冲区的巨细

把已发送但未承认的分组构成的空间称为发送窗口。能够发现，发送窗口是发送缓冲区的一部分。

  • 发送窗口的后沿等于发送缓冲区的后沿
  • 发送窗口的前沿不超过发送缓冲区的前沿
  • 之后评论的移动是指发送窗口在移动，发送窗口在0-N之间变化

可靠数据传输——GBN协议和SR协议

关于以上的内容在第一次写这篇文章时一直没想明白，就去科大底下提问了，郑教师也很好的回答了我的疑问：

可靠数据传输——GBN协议和SR协议

咱们知道，rdt一次只能发送一个分组，所以sw = 1（send window咱们简称为sw，接纳窗口简称为rw），而流水线技能中，一次能够发送多个分组 ，所以sw > 1。而事实上，不仅是sw能够>1，接纳窗口rw也能够>1，即一次接纳承认多个分组。下面用一张表格来表明其间的联系：

sw rw 协议
sw = 1 rw = 1 rdt协议
sw > 1 rw = 1 GBN协议
sw > 1 rw > 1 SR协议

至此，咱们再次回到那就摘录的话：所需序号规模和对缓冲的要求取决于数据传输协议如何处理丢掉、损坏以及延时大的分组。这句话的后半句是：处理流水线的差错恢复有两种根本的办法：回退N步（GBN）和挑选重传（SR）。下面咱们就分别来看一下这两个协议。

回退N步（GBN）协议

首先咱们来考虑，在正常情况下GBN协议中发送方和接纳方两窗口的互动。关于发送窗口，能够参考上面的图。

可靠数据传输——GBN协议和SR协议

可靠数据传输——GBN协议和SR协议

其间有以下几点需求留意：

  • 由于rw = 1，GBN协议一次只能确定接纳1个分组

    • 所以GBN协议只能次序接纳，只要当收到最低序号的分组（代表次序正确），才发送ACK给发送方

分割线—————————————————————————————————–

那么以上便是正常情况下GBN协议两窗口的互动，在开端评论反常情况前，咱们要先清楚，关于GBN，什么是反常情况？答案即为乱序以及丢掉。在上面提到，GBN只能次序接纳，所以先收到乱序的分组，咱们要有处理办法。而丢掉就更不用说了。下面给出反常情况下GBN协议两窗口的互动情况：

可靠数据传输——GBN协议和SR协议

  • 收到乱序分组时，由于没有落入接纳窗口的规模内，接纳方只能丢掉。

  • 重复发老分组的ACK给发送方后，发送方发后沿不移动，所以从上层新来的分组不能进入发送缓冲区。

  • GBN只要一个计时器，这点是和rdt不同的，定时器的作业机制为

    • 假如收到一个ACK，此刻还有已发送但未承认的分组，则定时器重新启动。
    • 假如收到一个ACK后，没有已发送但未承认的分组了，则停止该计时器。

  • 当触发超时重传后，发送方将重传所有已发送但未被承认的分组，这便是所谓的回退N步。

这样的作业机制保证了该定时器能够作为最早发送但未被承认的分组的定时器

关于GBN反常情况咱们这儿举一个栗子：

发送方发送0,1,2,3,4,5给接纳方，咱们假定分组2会丢掉，由于接纳方只能次序接纳，所以流程为：

  • 收到0，回复ACK0，后沿向右移动
  • 收到1，回复ACK1，后沿向右移动
  • 未收到2,2在中途丢掉
  • 收到3，由于2没到来，所以接纳方只能丢掉3并持续回复ACK1，此刻发送发收到ACK且仍有已发送但未确定的分组（2），所以定时器启动。此刻后沿不动
  • 收到4，回复ACK1
  • 收到5，回复ACK1
  • 某一时间，定时器timeout，发送方重新发送2,3,4,5

可靠数据传输——GBN协议和SR协议

最终咱们再来通过GBN协议中发送方和接纳方的FSM来整理一下GBN协议

发送方

可靠数据传输——GBN协议和SR协议

  • 发送窗口初始值为0（nextseqnum – base）

  • 收到上层rdt_send()调用后，判别是否在可发送规模内

    • 在可发送规模内：发送，并启动定时器，前沿向右滑动
    • 在可发送规模外：没法发送（发送缓冲区用完）

  • timeout超时：重新启动定时器，重传所有已发送但未承认的分组

  • 收到承认：后沿向右滑动

挑选重传（SR）协议

SR协议和GBN协议相同，都使用了流水线技能，使sw>1，SR和GBN的不同点在于，SR协议的RW>1，即SR协议能够接纳确定多个分组。和发送窗口相同，SR协议也有接纳窗口。

在正常情况下，SR协议的两窗口互动和GBN协议的相同，在之前咱们也提到过，这两种的不同点在于处理反常情况的办法不同。由于SR的rw>1，能够承认接纳多个分组，也便是说，假如收到乱序分组，不用抛弃，能够把它缓存起来。下面给出反常情况下SR协议两窗口互动：

可靠数据传输——GBN协议和SR协议

除了接纳窗口和GBN不同之外，SR协议为每个发送的分组都设置了一个定时器，不同于GBN协议只要一个定时器。这样在触发超时重传时，只需发送超时的那个分组即可。

这儿拿GBN协议中举的栗子持续看一下：

发送方发送0,1,2,3,4,5给接纳方，咱们假定分组2会丢掉，流程为：

  • 收到分组0，发送ACK0，后沿滑动
  • 收到分组1，发送ACK1，后沿滑动
  • 分组2在发送过程中丢掉
  • 收到分组3，发现是乱序，缓存起来，发送ACK3，后沿不滑动
  • 收到分组4，发现是乱序，缓存起来，发送ACK4
  • 收到分组5，，发现是乱序，缓存起来，发送ACK5
  • 直到某个时间，分组2的定时器timeout，重传分组2

可靠数据传输——GBN协议和SR协议

对比GBN和SR

GBN SR
长处 简略，所需资源小（接纳方一个缓存单元） 犯错时，只需重传1个，代价小
缺陷 一旦犯错，回退N步代价大 复杂，所需 资源多（接纳方多个缓存单元）

不难发现，GBN 和 SR 的长处和缺陷是相互对应的，所以咱们能够构想出它们的适用场景

  • 犯错率低时，合适GBN
  • 链路容量大（延迟大，带广大）时，合适SR，由于一旦犯错GBN代价很大。