详解ARQ协议

自动重传请求（Automatic Repeat-reQuest，ARQ）是 OSI 模型中 数据链路层 和 传输层 的错误纠正协议之一。它通过使用 确认 ， 超时 ，校验和 这三个机制，在不可靠服务的基础上实现可靠的信息传输，且是一种面向连接的协议。

ARQ 协议到底属于数据链路层的协议还是传输层的协议?

ARQ 是一种可以在不可靠的数据通道上可靠地传输数据的方案，所以其实链路层和传输层都用了 ARQ ，并不专属某一层。例如，数据包到达数据链路层的网卡和交换机后会进行 FCS 校验，如果错误则直接丢弃；又如在 TCP（传输层）中，数据包的 TCP 报头有 seq 序列号，用于检测失序和丢失。

ARQ 包含三个协议：停止 - 等待协议（SW），回退N帧协议（GBN），选择重传协议（SR） 。下面对各个协议进行详细分析。

停止 - 等待协议（SW）

• 发送方和接收方都只有大小为 1 的滑动窗口 。每当发送方发送一个分组时，就会开启一个计时器，一旦超时，就重发分组，这意味着，当收到接收方发来的 ACK 前，发送方都必须将已发送的分组留在窗口中而不可删除。

• ARQ 协议通过 序号（seq） 和 确认号（ACK） 来判断失序和重复分组。由于信道中只可能同时存在一个分组或 ACK ，所以 seq 只需要 1 位，即 0 和 1 。ACK 号表明的是自己 预期收到的序号 （比如发送方发送了 seq = 1 的分组，接收方收到后，应发送 ACK = 0 的报文，表明自己下一次想要收到 seq = 0 的报文。

  在停止 - 等待协议 中，确认号总是以模 2 运算的方式声明预期收到的下一个分组。

• 为了发现破坏分组，我们需要在分组中加入一种被称之为 校验和 的检测数据，当发送方收到分组后，会利用校验和进行检测，如果校验和不正确，则说明包发生错误，将其丢弃。

  关于校验和，请移步博主另一篇文章：差错检测与纠正技术

• 对于发送方 ：

  • 若收到进程传来的数据，发送方创建分组 ，保留分组的副本，并将其发送，同时开启计时器。
  • 若收到无错（校验和正确）ACK 且与其值等于待发送分组序号，则进入第一步。
  • 若收到被破坏的 ACK 或 无关 ACK ，则直接丢弃。
  • 若发生超时，则重发分组，并重开计时。

  对于接收方 ：

  • 若预期无错分组 Seq = R 到达，则分组被传递到进程，然后窗口滑动，ACK = （R + 1）% 2 被发送。

  • 若失序无错分组 Seq != R到达，则分组被丢弃，且发送 ACK = R 。

  • 若有错分组到达，直接将其丢弃。注意，不发送 ACK！

    

• 效率分析： 如果我们的信道带宽较大，那么此方式将非常低效，信道中永远只有一个分组，利用率极低。

  带宽时延积： 传播时延 × 带宽
  注意，传播时延 ≠ 传输时延

  假设在 停止 - 等待 系统中，线路带宽为 1Mbps，1 bit 发送需要 20 毫秒完成往返。求其带宽时延积和信道利用率。

  带宽时延积 = $(1 × 10^6) × (20 × 10^{-3}) = 20000$ ，即信道容量可达 20000 位，而系统只发送了 1000 位，所以信道利用率为 5%。

  如果系统在往返时间内发送 15 个分组（15000位），则信道利用率达 75%（信道利用率不是越高越好），由此我们引出 回退N帧协议 。

回退N帧协议（GBN）

在网络或其他领域中，在之前的任务结束前，经常会开始另外一个新任务。这称之为 流水线（pipeline） 。流水线往往可以提高传输效率。

• 发送方收到 ACK 前可以同时连续发送多个分组且窗口最大为 $2^{m}-1$ （原因见下文），但接收方只能缓冲一个分组（窗口大小为 1） 。

  窗口本身是一种抽象 ，发送窗口有三个变量，分别为：$S_f$ （第一个未完成分组）$Sn$ （下一个待发送分组）$S{size}$ （窗口大小），接收窗口仅$R_n$

  

• 序号是模 $2^m$ 的 ，其中 m 为序号字段的位大小，如 TCP 的 Seq 段为 16 ，范围为 $0$ ~ $2^{32}-1$ 。

• 在本协议中，确认号 ACK 是累积的 。例如，接收方发送 ACK = 4 ，则说明 Seq = 4 之前的分组 都已收到，这对于 ACK 报文的丢失尤其有用（见后文图示）。

• 仅有一个计时器 。因为第一个未完成分组的计时器总是最先停止，且计时器超时直接重发所有分组，所以只需要一个。

• 对于发送方 ：

  • 当发送窗口内第一个分组时开始计时，一旦超时，全发所有未完成（已发送但未收到 ACK）分组 。

    如：$S_f = 4$ ，$S_n = 7$ ，且计时器（发送分组 4 时开始计时）超时，则重发分组 4，5，6。

  • 如果无错且相关 $ACK = S_f+m$ （显然 $S_f<S_f+m<=S_n$ ）到达，则 $S_f=S_f+m$ 。并且，若所有未完成分组都被确认，则计时器停止并进行下一轮发送；若不是所有未完成分组都被确认（即 $ACK ≠ S_n$ ），则计时器重新开始 。

  • 若被破坏或无关的 ACK 报文到达，直接丢弃。注意，不会重发。

  • 若发生超时，直接重发所有未完成分组，并重新计时。

  对于接收方 ：

  • 若对应无错分组到达，报文被解开并传入进程，随后窗口滑动，接着发送 ACK。
  • 若无错但无关分组到达，将其丢弃，且发送 ACK = $R_n$ 的 ACK 报文 （表明自己需要的是 Seq = $R_n$ 的分组）。
  • 若被破坏分组到达，则直接丢弃。注意，不发送 ACK 。

为什么发送窗口最大为 $2^{m}-1$ ？

新接收窗口可能将历史延迟报文当作新报文接收，如下：

累积确认如何起作用 ：

可见，ACK = 3 到达后，同时完成了对 Seq = 1，2 的确认。

总览图：

选择重传（SR）协议

显然，GBN 协议在网络拥塞时，效率会很低，因为只要一个包丢失或错误或乱序，都会导致重发所有未完成分组，从而进一步加剧网络拥塞，形成恶循环。为了解决此问题，选择性重传协议应运而生。

• 发送窗口相对于 GBN 更小，为 $2^{m-1}$ ， 且发送窗口和接收窗口大小一致。

• 接收窗口允许储存失序分组 ，直到成为连续分组。

• 与 GBN 不同，SR 的确认号不是累积的 ，仅定义为本次收到的报文，对其他分组没有反馈。

• 理论上需要需要为每一个未完成分组分配单独计时器，但这样会给系统造成很大开销，所以只使用一个计时器。原因同 GBN 。

  《计算机网络第七版》中表示 SR 协议中，每个分组都会分配单独计时器，这样可以做到超时只重发指定的未完成报文。可以用单个硬件定时器来模拟多个逻辑定时器的操作。GBN 仍只使用一个计时器。

• 对发送方：

  • 若收到进程数据，则创建分组，然后发送分组并保留副本，同时开启计时器（如果未开启）。
  • 若无错且相关 ACK 到达，则将对应分组标记为已确认；若 ACK = $S_f$ ，那么窗口向右滑动，直到 $S_f$ 指向第一个未完成分组；此时若还存在未完成分组，则重启计时器，否则停止计时。
  • 若出错或无关 ACK 到达，则丢弃。
  • 若超时，则发送所有未完成分组。

  对接收方：

  • 若 Seq 在接收方窗口内的无错分组到达，则储存分组，且发送 ACK = Seq ；此外，若 Seq = $R_n$ ，则分组以及之前连续到达的分组被传递到应用层，并滑动窗口。
  • 若 Seq 不在接收窗口内的无错分组到达，则丢弃，且发送 ACK = $R_n$ 。
  • 若出错分组到达，直接丢弃。

为什么窗口最大为 $2^{m-1}$？

总览图：