流量控制

ARQ 协议

ARQ 协议是一类 可靠数据传输协议，用于在 不可靠的信道（比如可能出错或丢包的网络链路）上实现 可靠通信。

ARQ 协议的 核心思想 是：

• 发送方在发送数据后，必须等待接收方的确认（ACK）。
• 如果在规定时间内没有收到确认，就认为数据丢失或出错，需要重传。

ARQ 协议主要包括三种形式：停等（Stop‑and‑Wait）、回退 N 帧（Go‑Back‑N）以及 选择性重传（Selective Repeat）。其中，回退 N 帧和选择性重传统称为 连续 ARQ 协议。

停等协议

停等（Stop‑and‑Wait）是一种最基本的 自动重传请求（ARQ）协议。其核心思想是：发送方在发送完每一个数据帧后立即停止发送，并 等待 接收方的 确认（ACK）。只有在收到确认后，发送方才会继续发送下一个帧。由于任意时刻网络中只会有一个帧在传输，所以该协议也被称为“停等”。

停等协议的 工作过程 如下：

1. 发送数据
   • 发送方将一个数据帧发送给接收方。
   • 同时启动 计时器，用于监控该帧的确认是否在规定时间内到达。
2. 等待确认
   • 在计时器超时之前，发送方保持在“等待”状态。
   • 此期间若收到 确认帧（ACK），则说明该帧已成功到达并被正确接收。
3. 确认的接收
   • 接收方收到数据帧后，首先检验其完整性（如校验和、序号等）。
   • 若数据帧无误，接收方立即发送 确认帧（ACK）回给发送方；若检测到错误，则不发送 ACK，导致发送方超时后重传。
4. 计时器到期
   • 若计时器在收到确认之前到期，发送方认为该帧或其确认已丢失。
   • 发送方随后 重新发送 同一数据帧，并重新启动计时器，重复上述过程直至收到有效的确认。

通过上述四个步骤，停等协议实现了可靠的点对点数据传输，尽管其效率受限于 “每次只能发送一个帧” 的特性。

回退 N 帧

在 回退 N 帧（GBN，Go‑Back‑N）协议中，发送方可以在未收到确认的情况下连续发送多个帧，只要发送的帧数不超过发送窗口的大小。当窗口已满时，发送方必须等待确认才能继续发送。

回退 N 帧的 核心要点 如下：

1. 窗口大小
   • 若帧序号使用 $n$ 位二进制，则序号空间大小为 $2^{n}$。
   • 为保证不产生歧义，GBN 的发送窗口大小 $W$ 必须满足 $W \le 2^{n}-1$，因此 最大窗口大小 为 $2^{n}-1$。
   • 接收窗口的大小固定为 1，即接收方只能一次接受并确认期望的序号。
2. 发送过程
   • 只要发送窗口未满，发送方就可以把窗口内的帧依次发送出去。
   • 对于 最早发送且尚未被确认的帧（即窗口中的第一个未确认帧），发送方启动 单一的超时计时器。
   • 其余已发送但尚未确认的帧不再单独维护计时器，而是共享这一个计时器。
3. 接收过程
   • 接收方维护一个 期望序号（expected sequence number）。
   • 当收到的帧序号等于期望序号时，接收方接受该帧并发送 累计确认 ACK（确认该帧及其之前的所有帧）。随后期望序号加 1。
   • 若收到的帧序号不是期望序号（说明前面的某帧丢失），接收方直接 丢弃该帧，并 重新发送最近一次正确接收的帧的 ACK。由于接收窗口为 1，后续已到达但序号不连续的帧都会被丢弃。
4. 超时与重传
   • 当 超时计时器 触发时，发送方认为窗口中最早的未确认帧已丢失。按照 GBN 的工作原理，发送方会 从该帧开始，把窗口内的所有帧全部 重新发送。
   • 这样做的原因是：即使后面的帧已经到达接收方，由于接收窗口仅能接受连续的序号，这些帧会在接收方被丢弃，只有最早丢失的帧被重新发送后，后续帧才能被顺利接收。
5. 滑动窗口
   • 当发送方收到某帧的 累计 ACK 时，意味着该帧以及它之前的所有帧都已被接收方确认。发送方随后 将窗口向前滑动，释放已确认的帧位置，从而可以继续发送新的帧。

通过 GBN、SR 交互演示 可以直观地了解 Go‑Back‑N 与 Selective Repeat 的工作流程，加深对上述概念的理解。

选择性重传

选择性重传（SR，Selective Repeat）是一种 自动重传请求（ARQ）协议，专门用于克服回退 N 帧（Go‑Back‑N）在高误码率环境下的效率低下。与 Go‑Back‑N 不同，SR 只 重传 那些真正丢失或出错的帧，而不必重新发送随后所有的帧，从而在误码率较高的链路上表现得更为高效。

选择性重传的 核心要点 如下：

1. 窗口大小
   • 在 SR 中，发送窗口和接收窗口的大小保持一致。
   • 若帧序号采用 $n$ 位二进制表示，则窗口的最大取值为 $2^{n-1}$（即序号空间的半数），以避免发送方和接收方窗口的重叠产生歧义。
2. 发送过程
   • 发送方在其发送窗口范围内连续发帧。
   • 每发送一帧，就为该帧启动一个 计时器；计时器独立于其他帧，超时后仅针对该帧进行重传。
3. 接收过程
   • 接收方接受所有落在接收窗口中的帧，即使这些帧顺序错乱。
   • 对于每一正确收到的帧，接收方立即发送 确认（ACK）。
   • 乱序到达的帧会被 缓存，待窗口前面的缺失帧补齐后，按正确顺序交付给上层。
4. 超时与重传
   • 当某帧的计时器到期，发送方只 重传 该帧，而不是窗口内的全部帧。这一点是 SR 与 GBN 的根本区别，也是 SR 在高误码率下保持高吞吐量的关键。
5. 滑动窗口机制
   • 发送方：收到帧的确认后，窗口左边界向前移动，释放已确认的帧槽位，随后可以发送新的帧。
   • 接收方：当缓存的帧已能够连续组成一个完整序列并交付给上层后，接收窗口也向前滑动，腾出空间接收后续帧。
6. 冲突确认的处理
   • 由于网络延迟，发送方可能在重传帧后才收到该帧的早期确认。
   • 为避免误判，SR 协议必须具备 识别并丢弃重复确认（duplicate ACK）的机制，只对最新、有效的确认作出响应。

协议对比

说明

• 表格中的“窗口大小”指的是发送方或接收方在任意时刻能够同时处理的帧数。
• GBN 与 SR 均属于 滑动窗口协议，但它们在窗口大小的取值范围以及错误恢复策略上有本质差异。
• 停等协议是最简单的可靠传输方式，适用于 高可靠、低时延 的链路；而 GBN 与 SR 则在 带宽受限或时延较大的环境 中表现更佳。

窗口大小限制

$$\text{发送窗口大小} + \text{接受窗口大小} \le 2^n$$

滑动窗口协议是计算机网络中用于控制传输层数据流的一种机制。在这种协议下，发送窗口和接收窗口的大小有一个重要的限制，即 它们的和不能超过序列号空间的大小。序列号空间是由能够用于标识帧的序列号的总数确定的，这通常是由序列号的位数决定的。

对于一个使用了 $n$ 位序列号的协议，序列号的范围是从 $0$ 到 $2^n-1$ 。因此，整个序列号空间的大小是 $2^n$ ，这意味着理论上最多可以有 $2^n$ 个不同的帧在传输中被唯一区分。

这个限制的主要原因是防止所谓的“序列号回绕”（Sequence Number Wraparound）。如果发送窗口和接收窗口的大小之和大于序列号空间的大小，那么就可能发生一个新的帧使用了一个老的、已经被使用的序列号，但是该帧可能还在网络中传输或者被延迟。接收方将无法区分这是一个新的帧还是重复的帧（出现了歧义）。

信道利用率

在 ARQ 协议中，信道利用率（也叫做链路利用率）是指信道用于传输有效数据的效率，通常定义为 成功传输数据的时间占总传输时间的比例。它反映了协议在给定信道条件下的性能，是评估 ARQ 协议效率的重要指标。

信道利用率 $U$ 可以表示为

$$U = \frac{T_{data}}{T_{total}}$$

其中：

• $T_{data}$：成功传输有效数据的时间。
• $T_{total}$：总时间，包含数据传输、确认、重传以及等待。

计算方法

对于 ARQ 协议，假设信号传播时间为 $T_p$，一个数据帧的传输时间为 $T_d$，一个确认帧的传输时间为 $T_a$，发送窗口的最大值为 $N$，信号往返时间 $RTT = 2 \cdot T_p$。

在此情况下，信道利用率 $U$ = 发送数据的时间 / 从发送第一个帧的时间到收到第一个确认帧的时间：

$$U = \frac{N \cdot T_d}{RTT + T_d + T_a}$$

停等协议

对于停等协议，信道利用率为

$$U = \frac{T_d}{RTT + T_d + T_a}$$

连续 ARQ 协议

对于使用了滑动窗口的协议（比如回退 N 帧和选择性重传），一次性可以传输 $N$ 个数据帧，信道利用率为

$$U = \frac{N \cdot T_d}{RTT + T_d + T_a}$$

注意有些时候确认帧比较小，在这种情况下确认帧传输时间 $T_a$ 可以忽略。

此外，$U \le 1$，所以当 $N \cdot T_d > RTT + T_d + T_a$ 时，信道利用率 $U = 1$。