数据链路层 —— 流量控制

为什么需要流量控制 ？

流量控制（Flow control）是链路层中主要功能之一，主要目的是确保发送方不会溢出接收方的缓冲区。这是一种防止发送方发送太多数据给接收方，后者来不及处理的机制。

流量控制协议

乌托邦协议

乌托邦协议（Utopian simplex protocol）是最理想状态下的传输协议，此协议有以下假设：

• 单工信道（Simplex channel）
• 信道无错（Error-free），即不会发生帧错误
• 接收方有不受限制的缓存（Unlimitied buffers）

乌托邦协议是非常理想的协议，正如其名字一样，实际的链路层通信是完全不一样的，由于接收方缓存有限，且信道的差错无可避免，我们需要考虑流量控制和差错控制。

ARQ

自动重传请求（Automatic Repeat reQuest，简称 ARQ）是一种用于数据通信中的错误控制方法。当传输的数据帧在接收端被检测到有错误时，ARQ 协议会要求发送端重新发送该帧。这种机制确保了数据的完整性和正确性。ARQ 通常与前向纠错编码（FEC）相结合，后者允许在不重新发送数据的情况下纠正错误。

接下来要介绍的停等协议和滑动窗口协议，都属于 ARQ。

停等协议

停等协议（Stop-and-Wait protocol）引入了应答（ACK）的概念，每次发送方发出一个数据帧后，接收方接受数据帧，如果接受成功就会发送一个应答（ACK），只有发送方接收到 ACK 后才会发送下一个数据帧。如果发送方长时间没有收到 ACK，则其会认为接收方没有收到目标数据帧，就会重新发送该数据帧。

有些协议中可能会有否定应答（NAK），即接收方收到数据，通过纠错码（如 CRC）判断数据出错后会向发送方发送 NAK，发送方收到 NAK 后则会重新发送数据帧。

以上展示了停等协议的四种主要情况，在情况（d）中，发送方没有成功接收到接收方的 ACK，其认定数据帧传输失败，于是重新传输数据帧，造成了数据冗余（Duplication）。

为了解决 ACK Lost 的问题，我们引入了 SN（Sequence number）编号。

在停等协议中，帧和 ACK 的 SN 编号只需要 1 个 bit 即可，具体操作如下：

发送方按照奇偶次序依次发送 SN 编号为 0 和 1 的帧，接收方则在收到发送方的信号后返回对应的 ACK。

使用 SN 编号的停等协议就可以解决之前提到的全部问题了。

• 数据帧丢失（Frame gets lost）

  

• ACK 丢失（ACK Lost）

  

• ACK 延迟（ACK Delayed）

  

  注：ACK 也必须要有 SN 编号，如果只对数据帧编号，则上图的接收方在收到 Frame 0 的重传递后会发送一个一样的 ACK，若发送方发送了 Frame 1 且接收方没有收到，则发送会误判接收方成功收到了 Frame 0 和 Frame 1，实际上接收方只收到了 Frame 0。

计时器（Timer）：

一般而言，发送方会设置一个固定的 Timeout interval，一旦在发送目标帧 i 后如果没有在规定的时间内收到 ACK（i），则会重新发送数据帧 i，这个时间段不宜过短，如果太短，可能导致发送方发送过多不必要的数据帧；也不宜过长，不然会导致数据接收的响应慢。

停等协议的优缺点

优点：

1. 简单性（Easy to implement）：停等协议的结构简单，容易实现。对于需要简单可靠数据传输的应用，该协议可能是合适的。
2. 完整性（Integrity）：由于每次只发送一个数据帧并等待确认，所以在低误差率的通信环境中，可以确保数据的完整性。

缺点：

1. 低效率（Low efficiency）：在高带宽或大延迟的通信环境中，停等协议的效率可能会很低。因为大部分时间可能都花在了等待确认上，而不是数据传输。
2. 延迟（Dalay）：每次发送一个数据帧后都要等待确认，这增加了传输的总延迟。
3. 资源利用不足（Insufficient utilization of resources）：在有大量可用带宽的情况下，停等协议可能无法充分利用所有的带宽，导致带宽浪费。

滑动窗口协议

捎带应答

捎带应答（Piggybacking）指的是在全双工（Full-duplex）信道传输中，接收方在收到数据帧后先将 ACK 暂存起来，然后将其捎带在数据帧处发送出去，这样能一定程度上节约信道的使用。

什么是滑动窗口协议 ？

更确切来说，这里提到的滑动窗口（Sliding window），主要由两部分组成：

• 发送窗口（Sending window）

  发送方维护一个窗口，只有处于该窗口的数据帧可以被发送。

  

• 接收窗口（Receiving window）

  接收方维护一个窗口，只能处于该窗口的数据帧可以被接收。

  

滑动窗口协议允许发送方在收到 ACK 之前发送多个数据帧。

在滑动窗口协议中，若发送窗口大小为 \(W_T\) ，接收窗口大小为 \(W_R\) ，SN 模数为 \(m\)（通常 \(m = 2 ^ n\)），则必须满足 \(W_T + W_R \leq m\)

，至于原因，我们会在下文中介绍。

累积 ACK

累计 ACK（Cumulative ACK），即一种记录累积效果的 ACK，若发送方收到 ACK（i），则说明 Frame（0 ~ i）都被成功接收。

Go-Back-N

在 Go-Back-N 协议中，如果某个帧接收失败，则接收方会拒绝所有在此之后发送过来的数据帧直到错误帧被成功接收。因此若发送方发送的数据帧未被成功接收，则其必须回退重发该帧。

一般而言，GBN 协议中接收窗口的尺寸为 1，因此某一时刻只能接收特定帧。

• 数据帧损坏：

  1. 接收方检测到 Frame（i）出错
  2. 接收方丢弃 Frame（i）与所有后续帧
  3. 超时之后，发送方重发 Frame（i）与后续帧

  

• ACK 丢失：

  1. 接收方成功收到 Frame（i）并发送了 ACK（i），但是发送方没有成功收到 ACK
  2. 但由于这里的 ACK 记录累积效果，所以如果在 Frame（i）重传之前收到了 ACK（i + n），那么 Frame（i）就不需要再重传
  3. 如果超时，重传 Frame（i）与后续帧

  

根据上文提及的 \(W_T + W_R \leq m\)，我们不难得出在 GBN 协议中有 \(W_T + 1 \leq m\) ，即 \(W_T < m\) ，如果 \(W_T \geq m\) 会发生什么事情呢？

如上图所示，接收窗口的大小等于 SN 模数（4），若前 4 帧的 ACK 均未被成功接收，则发送方会因为超时重新发送 Frame（0），此刻接收方的接收窗口恰好与发送窗口有重叠部分 0，此时接收方会错误地接收冗余的 Frame（0）并认为这是新的一帧。

因此 \(W_T + W_R \leq m\) 其实就是为了保证：

当发送方发送完发送窗口内所有帧，在未收到 ACK 之前，接收方正确接收到所有发送来的帧，接收窗口向前推移，此时，必须保证发送窗口与接收窗口在序号上不能重叠。

选择重传协议

选择重传协议（Selective Repeat ARQ），与 GBN 协议相比，选择重传协议更加高效，其减少了重传的次数，同时也更加复杂。

与 GBN 协议不同的是，选择重传协议的接收窗口尺寸通常更大，这意味着接收方可以接受失序的帧。当接收到失序的帧时，它不会丢弃这些帧，而是将它们缓存起来，并为每个正确接收的帧发送确认。

上图中接收方在收到 Frame（4）和 Frame（5）后依然发送 ACK（1）是因为目前连续接收成功的帧只有 0 ~ 1，在收到 Frame（2）后才会发送 ACK（5）。

假设 SN 模数为 \(2 ^ n\) ，则在选择重传协议中发送窗口和接收窗口尺寸的选择有以下要求：

• \(W_T + W_R \leq 2 ^ n\)
• \(W_T \geq W_R\)

一般而言，我们会选择 \(W_T = W_R = 2 ^ {n - 1}\)