TCP可靠传输：ARQ协议（停止等待、超时重传、滑动窗口、回退N帧、选择重传）

一. ARQ简介

• ARQ协议，即自动重传请求（Automatic Repeat-reQuest），是OSI模型中的错误纠正协议之一。
• 它通过使用确认和重传这两个机制，在不可靠服务的基础上实现可靠的信息传输。
• 如果发送方在发送后一段时间之内没有收到确认帧，它通常会重新发送。
• 重传的请求是自动进行的，接收方不需要请求发送方重传某个出错的分组
• ARQ包括停止等待ARQ协议和 连续ARQ协议

二. 停止等待ARQ

（1）正常传输

1. “停止等待”就是每发送完一个分组就停止发送，等待对方的确认。在收到确认后再发送下一个分组。
2. 全双工通信的双方既是发送方也是接收方。
3. 为了讨论问题的方便，我们仅考虑 A 发送数据，而 B 接收数据并发送确认。因此 A 叫做发送方，而 B 叫做接收方
   

（2）传输出现差错

在接收方 B 会出现两种情况：

1. B 接收 M1 时检测出了差错，就丢弃 M1，其他什么也不做（不通知 A 收到有差错的分组）。
2. M1 在传输过程中丢失了，这时 B 当然什么都不知道，也什么都不做。

在这两种情况下，B 都不会发送任何信息。A都必须重发分组，直到B正确接收为止，这样才能实现可靠通信。

1. 超时重传

A怎么知道 B 是否正确收到了 M1 呢？

1. A 为每一个已发送的分组都设置了一个超时计时器。
2. A 只要在超时计时器到期之前收到了相应的确认，就撤销该超时计时器，继续发送下一个分组 M2 。

丢失确认

1. 若A在超时计时器规定时间内没有收到B的确认ACK，就重发该分组。无论是自己发送的分组出错、丢失了，或者 是 B 发送的确认丢失了。
2. 假定 B 又收到了重传的分组 M1。这时 B 应采取两个行动：
   • 丢弃这个重复的分组 M1，不向上层交付。
   • 向 A 发送确认。不能认为已经发送过确认就不再发送，因为 A 之所以重传 M1 就表示 A 没有收到对 M1 的确认

2. 编号

若分组正确到达B，但B回送的确认ACK丢失或延迟了，A未收到B的确认，会超时重发。B 可能会收到重复的 M1 。B如何知道收到了重复的分组，需要丢弃呢？

1. A为每一个发送的分组都进行编号。若B收到了编号相同的分组，则认为收到了重复分组，丢弃重复的分组，并回送确认（之所以会收到重复的分组就是因为发送端没有正常收到确认）。
2. B为发送的确认也进行编号，指示该确认是对哪一个分组的确认。

A根据确认及其编号，可以确定它是对哪一个分组的确认，避免重发发送。若为重复的确认，则将其丢弃。

迟到确认

传输过程中没有出现差错，但 B 对分组 M1 的确认迟到了。

1. A会超时重发M1， 则B 收到重复的 M1，同样要丢弃重复的 M1，并重传确认分组。

2. 稍后B迟到的确认和重发的确认都会到达A，A收到重复的确认，对重复的确认的处理很简单：收下后就丢弃。

（3）信道利用率

三. 连续ARQ

（1）流水线传输

为了提高传输效率，发送方可连续发送多个分组，不必每发完一个分组就停顿下来等待对方的确认。这样可使信道上一直有数据不间断地传送。

流水线传输通常要求
（1）必须增加序号范围，因为每个输送中的分组（不计算重传的）必须有一个唯一的序号，因为可能存在有多个在输送中未确认的报文。
（2）协议的发送方和接收方要能缓存多个分组。发送方至少要能缓存那些已发送但没有确认的分组，接收方可能要缓存那些已正确接收的分组。
（3）所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。
（4）解决流水线传输的差错有两种滑动窗口协议：回退N(Go-Back- N，GBN) 和选择重传(Selective Repeat，SR) 。

累积确认

即接收方不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认。

因此，接收方不必对中间某个确认包的丢失进行重传，因为累积确认的效果，一旦一个较大序号的ACK被接收到，则表示这个包之前的包都已经成功收到。

如果接受方收到了这个确认，则表示到这个分组为止之前的所有分组都已正确收到了。

但同时累积确认也有缺陷，例如发送方传送了5个包，但是第3个包丢失了，第4和第5个正常。这时根据累积确认，接收方只能传送前两个包的ACK（按序到达的最后一个）。在接收到第2个包ACK的发送方不知道后面3个包是否到达，就会将后3个包全部进行重传。即：Go-back-N。

优点：容易实现，即使部分确认丢失也不必重传。
缺点：不能向发送方反映出接收方已经正确收到的所有分组的信息。

注：TCP并不是每一个报文段都会回复ACK的，可能会对一个报文段发送一个ACK（M0、M2），也可能会对多个报文段发送1个ACK（M3+M4+M5）

（2）滑动窗口

滑动窗口协议（Sliding Window Protocol）以基于分组的数据传输协议为特征。因此该协议适用于对按顺序传送分组的可靠性要求较高的环境，例如在数据链路层（OSI模型）以及传输控制协议（TCP）中。

1. 提供TCP的可靠性（最基本的传输可靠性来源于“确认重传”机制），避免丢包
2. 提供TCP的流控特性，用于网络数据传输时的流量控制，以避免拥塞的发生。

• 滑动窗口协议在发送方和接收方之间各自维持一个滑动窗口，发送方是发送窗口，接收方是接收窗口（两个窗口大小不一定相同）
• 使用滑动窗口协议控制发送方和接收方所能发送和接收的分组的数量和编号
• 它允许发送方发送多个分组而不需等待确认，TCP的滑动窗口是以字节为单位的
• 每收到一个确认，发送方就把发送窗口向前滑动。

发送窗口中有四个概念：

1. 已发送并收到确认的数据（不在发送窗口和发送缓冲区之内）
2. 已发送但未收到确认的数据（位于发送窗口之内）
3. 允许发送但尚未发送的数据（位于发送窗口之内）
4. 发送窗口之外的缓冲区内暂时不允许发送的数据

接收窗口中也有四个概念：

1. 已发送确认并交付主机的数据（不在接收窗口和接收缓冲区之内）
2. 未按序收到的数据（位于接收窗口之内）
3. 允许的数据（位于接收窗口之内）
4. 不允许接收的数据（位于发送窗口之内）
   
   
   当A 的发送窗口内的序号都已用完，但还没有再收到确认时，必须停止发送

为了解决流水线传输的差错，TCP协议提供两种滑动窗口：回退N(Go-Back- N，GBN) 和选择重传(Selective Repeat，SR) 来解决这个问题

1. 回退N帧

如果发送方发送了前 5 个分组，而中间的第 3 个分组丢失了。这时接收方只能对前两个分组发出确认。

发送方无法知道后面三个分组的下落，而只好把后面的三个分组都再重传一次。

这就叫做 Go-back-N（回退 N），表示需要再退回来重传已发送过的 N 个分组。

可见当通信线路质量不好时，连续 ARQ 协议会带来负面的影响。

如果下面的网络层协议丢失了很多分组,那么返回N协议的效率就会很低。

因为每当一个分组损坏,发送方就需要重传所有待确认的分组,虽然其中有些分组实际上已经完整地被接收了

2. 选择重传

选择重传协议只重传真正出错或者丢失的帧，那怎么实现呢？

1. 发送方维持着一个窗口，包含可发送或已发送但未被确认的序号。

2. 接收方维持着一个窗口，包含可接收的序号，每个序号还保留一个缓冲区。与每个缓冲区项相关联的还有一个标志位，用来指明缓冲区是满的还是空的。
   

3. 每到达一个帧，接收方通过检查它的序号，看是否落在窗口内。如果确实落在窗口内且之前没有接收过，则接收该分组然后保存在缓冲区并返回一个确认。等前面这些帧都到达后一起交付给上层

4. 发送端每个发送缓冲都设有一个超时一个超时计时器，一个超时事件发生后相应缓冲区的帧就会被重发

但是非顺序接收也引发了一些特殊问题。

假设我们用3bit的序号（0~ 7），那么发送方允许发送8个帧，然后开始等待确认。刚开始时，发送方和接收方的窗口如图所示

现在发送方发出0~ 7号帧，接收方的窗口接收任何序号落在0~7之间的帧。

这8个帧全部到达后，接收方发送确认（发送方还未收到），并且向前移动它的窗口，允许下一次接收0、1、2、3、4、5，6，7号帧

这时会存在两个场景

情景一：
发送方收到了全部确认，发送窗口前移，然后继续发送后面的数据（0号帧）

这时接收方会收到一个0号帧

情景二：
假如第一次发出的所有确认都丢失了，所以接收方在超时之后便会重传0号帧（其他帧也会重传，只不过0号帧先被发送、先超时、先重传）

因为接收方已经接收了0~7号帧，并已发送了确认(虽然接收方未收到)，所以窗口会向前移动，允许下一次接收0、1、2、3、4、5，6，7号帧。

此时接收方也能收到一个0号帧

两种情况下接收方都能收到0号帧，一个是重传的一个是新发送的，接收方没法区分这两个0号帧。

这个问题通常通过设置窗口大小来解决

1. 让接收窗口大小等于发送窗口大小（大了会溢出，小了没意义）
2. 发送窗口=接收窗口=2^(n-1) ，n表示用多少bit来表示允许发送的帧序号，上文发送了8个帧（2 ^3 ），也就是3bit，所以窗口大小应该小于等于2 ^(3-1)=4，即序列号的一半

---

四. 停止等待ARQ和连续ARQ比较

注意： 在发送完一个分组后，必须暂时保留已发送的分组的副本，以备重发。

• 分组和确认分组都必须进行编号。
• 超时计时器的重传时间应当比数据在分组传输的平均往返时间更长一些。

---

五. ARQ到底运行在那一层？

这里引用知乎的一个答复

1. ARQ是一种可以在不可靠的数据通道上可靠地传输数据的方案，所以其实链路层和传输层都用了ARQ，并不专属某一层。
2. 并不是一条连接只要有一层用了ARQ，它的上层的通信就是可靠的。因为ARQ只保证使用它的点到点是可靠的，比如数据链路层只保证你和你的路由器通信可靠，你的路由器到小区的路由器通信也可靠， 但是路由器本身会故障，会拥塞丢包，也就是点本身会产生问题。
3. 所以需要在传输层或者应用层再加一层ARQ保障整条数据通道的可靠性。比如你自己写程序要在应用层通信，但传输层不用tcp想用udp，也可以在你程序里用ARQ协来实现可靠性。