流量控制、可靠传输

主要由三种协议实现流量控制和可靠传输

• 停止-等待协议

• 后退 N 帧协议

• 选择重传协议

这三种协议都基于滑动窗口机制

滑动窗口机制

假设现有两个结点，分别为接收方和发送方

发送方发送的帧为：

A	B	C	D	E	F	G	H	I	J	K	L

蓝色部分的帧为发送窗口

接收方接收的帧为：

A	B	C	D	E	F	G	H	I	J	K	L

红色部分的帧为接收窗口

发送窗口（$W_T$）为发送方当前允许发送的帧，接收窗口（$W_R$）为接收方当前允许接收的帧，这两个值一般是固定的，两方不能发送和接收超粗窗口的数据

接收方可以通过某种方式控制窗口的滑动、从而实现流量控制

三种协议在以上四个方面的实现都有所不同、后续三种协议的学习都需要关注这四个方面

停止-等待协议（S-W）

• 滑动窗口机制

发送窗口： $W_T = 1$ ，接收窗口 $W_R = 1$

• 确认机制

确认帧：ACK_i ，若接收方收到 i 号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i

• 重传机制

超时重传：若发送方超时未收到 ACK_i ，则重传 i 号帧

• 帧编号

要求：$W_T + W_R \leq 2^n$

正常情况

停止等待协议会将每个数据帧以 0 1 0 1 0 1 序列编号，发送方发送数据帧 DATA_0 时，接收方需要返回确认帧 ACK_0 ，发送方发送数据帧 DATA_1 时，接收方需要返回确认帧 ACK_1 ，以此类推

数据帧、和确认帧通常由首部、尾部^[1]和数据部分组成，通常数据帧比确认帧更长

帧	A	B	C	D	E	F	G	H	I	J	K	L
帧编号	0	1	0	1	0	1	0	1	0	1	0	1

1. 发送方发送数据帧 DATA_0 并启动计时器

2. 接收方接收到 DATA_0 并且确认数据完整无误后，将数据传输给网络层，并且将接收窗口后移一位，向发送方发送确认帧 ACK_0 并期待接收 DATA_1 帧

3. 发送方接收到确认帧 ACK_0 ，校验后将发送窗口后移一位并发送 DATA_1 ，以此类推……

异常情况

• 数据帧丢失

在正常情况下，由于某种原因，可能是网络噪声或者其他原因导致帧丢失

前提条件：发送方会在发送数据的同时设置一个计时器

1. 假设某次数据传输过程中发送方发送 DATA_0 丢失，接收方没有顺利接收到这个帧

2. 发送方在超过计时器设置的阈值后未收到 ACK_0 ，会重传 DATA_0 同时也会重置计时器

3. 如果此次发送没有出现意外，接收方将会在确认无误后发送 ACK_0 然后进入正常情况的传输过程

• 确认帧丢失

在正常情况的传输过程中，接收方在接收到 DATA_0 后确认无误然后发送 ACK_0 并将接收窗口后移一位

1. 此时由于各种原因导致发送方无法接收到确认帧，此时在计时器达到阈值时就会触发重传

2. 由于此时接收方期待接收 DATA_1 ，所以再次接收的 DATA_0 被判定为重复帧并且丢弃并再次向发送方发送 ACK_0

3. 如果发送方顺利接收 ACK_0 那么接下来就继续正常的数据传输

后退 N 帧协议（GBN）

• 滑动窗口机制

发送窗口： $W_T > 1$ ，接收窗口 $W_R = 1$

• 确认机制

确认帧：ACK_i ，若接收方收到 i 号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i，同时，接收方可“累计确认”，即连续接收到多个数据帧时，可仅返回最后一帧的ACK ，即 ACK_i 表示接收方已收到 i 号帧及其之前的所有帧

• 重传机制

超时重传：若发送方超时未收到 ACK_i ，则重传 i 号帧，以及之后的所有帧

• 帧编号

至少需要 n bit 来给帧“编号”

要求：$W_T + W_R \leq 2^n$

正常情况

帧	A	B	C	D	E	F	G	H	I	J	K	L
帧编号	0	1	2	3	0	1	2	3	0	1	2	3
发送方	A	B	C	D	E	F	G	H	I	J	K	L
接收方	A	B	C	D	E	F	G	H	I	J	K	L

假设发送窗口为 3 而接收窗口为 1 ，则至少需要 2 bit 来给帧进行编号，别为 0、1、2、3

1. 开始发送数据时，发送方按顺序连续发送 DATA_0 、 DATA_1 、 DATA_2 三个数据帧

2. 接收方按顺序接收到 DATA_0 、 DATA_1 、 DATA_2 ，每次滑动窗口向后移动一位

3. 接收到 DATA_2（即数据帧组最后一个数据帧）后，向发送方发送 ACK_2 表示已连续无误收到三个数据帧并且将窗口后移一位

4. 发送方收到 ACK_2 后窗口向后移动三位，随后继续发送数据并循环这个过程

异常情况

• 数据帧丢失

假设发送方继续发送 DATA_3 、 DATA_0 、 DATA_1 ，接收方正常接收 DATA_3 接收窗口向后移动一位，即期待接收 DATA_0

1. 但是由于各种原因没有正常接收 DATA_0 ，DATA_1 被正常接收，此时由于接收帧并没有落在接收窗口内，因此接收方将丢弃该帧，并向发送方发送最后一个正确接收的数据帧的 ACK ，在本例中为 ACK_3

2. 此时发送方接收到 ACK_3 后，发送窗口将会向后移动一位，即确认接收方接收到的最后一个正确帧为这次发送的 3 个数据帧的第一个，移动发送窗口后由于此前并没有传输 ACK_0

3. 所以发送方的 DATA_0 计时器超时，此时将会重新开始发送 DATA_0 、 DATA_1 、 DATA_2 重传的同时这三个帧的计时器也重新开始计时

4. 接收方依次接收完 DATA_0 、 DATA_1 、 DATA_2 后向发送方发送 ACK_2

5. 然后发送方将发送窗口后移至 DATA_3 、 DATA_0 、 DATA_1 随后继续下一次发送操作

• 确认帧丢失

假设此时发送方发送 DATA_0 、 DATA_1 、 DATA_2 三个数据帧，均被正确接收

1. 此时接收方向发送方返回 ACK_2 并将接收窗口后移，但是由于各种原因导致 ACK_2 未被发送方正确接收

2. 发送方 DATA_0 的计时器会超时，接下来会重传这些数据帧给接收方

3. 但是由于这些数据不在接收窗口内，此时接收方会再次发送最后一个正确接收的 ACK 本例中即 ACK_2 并且会将重复接收到的数据帧丢弃即第二次收到的相同数据帧

4. 如果此时发送方正确接收 ACK_2 那么会将窗口滑动至 DATA_2 的下一位以及后 $W_T - 1$ 的位置，然后继续传输数据

特定情况探讨

帧	A	B	C	D	E	F	G	H	I	J	K	L
帧编号	0	1	2	3	0	1	2	3	0	1	2	3
发送方	A	B	C	D	E	F	G	H	I	J	K	L
接收方	A	B	C	D	E	F	G	H	I	J	K	L

• 如果不满足 $W_T + W_R \leq 2^n$ 条件

假设 $W_T = 4, W_R = 1$ 的情况，数据编号为 0、1、2、3 循环

假设接收方正确接收了一组数据 DATA_0、 DATA_1 、 DATA_2 、 DATA_3 并且将接收窗口移至 DATA_0 ，并发送 ACK_3

1. 此时由于各种原因导致 ACK_3 未能被发送方正确接收

2. 由于 DATA_0 计时器超时，发送方会再次发送此前的 DATA_0、 DATA_1 、 DATA_2 、 DATA_3

3. 但是由于此时的接收窗口位于 DATA_0 所以接收方会再次接收相同的一组数据 DATA_0、 DATA_1 、 DATA_2 、 DATA_3 ，并发送 ACK_3 ，此时接收方的数据以及造成了帧重复的现象，从而导致数据损坏。

缺点

如果接收方接收速度很慢、或在信道误码率很高的情况下，可能导致发送方的发送进度经常需要“后退”，传输效率低下

选择重传协议（SR）

• 滑动窗口机制

发送窗口： $W_T > 1$ ，接收窗口 $W_R > 1$，且 $W_T \geq W_R$ （发送窗口必须大于等于接收窗口）

• 确认机制

确认帧：ACK_i ，若接收方收到 i 号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i ， SR协议不支持“累计确认”，每个数据帧都必须单独确认即单独发送 ACK ，即 ACK_i 表示接收方已收到 i 号帧；对于接收方接收到的 i 号帧，检测出该帧有“差错”，则需要丢弃该帧，并向发送方返回否认帧 NAK_i

• 重传机制

  • 超时重传：若发送方超时未收到 ACK_i ，则重传 i 号帧

  • 请求重传：若接收方接收到 NAK_i ，则重传 i 号帧

• 帧编号

$W_T + W_R \leq 2^n$

SR协议的窗口大小限制条件

根据协议，窗口大小需要满足以下条件：

1. 若用 n bit 给帧编号， $W_T + W_R \leq 2^n$

2. $W_T \geq W_R$

假设使用 3 bit 给帧进行编号，则编号由 0 ~ 7 ，而接收窗口和发送窗口的大小组合可以有多种，但在实际应用中一般会让接收窗口和发送窗口的大小相等，即 $W_T = W_R$

帧	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
帧编号	0	1	2	3	4	5	6	7	0	1	2	3	4	5	6

正常情况

假设 $W_T = 4, W_R = 4$ ，使用 3 bit 给帧进行编号

1. 发送方依次向接收方发送 DATA_0 ，DATA_1 、 DATA_2 、 DATA_3 并启动计时器

2. 接收方依次接收 DATA_0 、 DATA_1 、 DATA_2 、 DATA_3 并向发送方依次返回 ACK_0 ，ACK_1 、 ACK_2 、 ACK_3 ，并向后移动接收窗口

3. 发送方依次接收到 ACK_0 、 ACK_1 、 ACK_2 、 ACK_3 ，并且确认无误后，移动发送窗口，并进入新一轮的数据发送流程

异常情况

• 数据帧丢失

假设发送方继续发送 DATA_4 、 DATA_5 、 DATA_6 、 DATA_7 由于各种原因，接收方未能接收 DATA_5

1. 此时接收方已接收 DATA_4 、DATA_6 、DATA_7 并依次返回 ACK_4 、 ACK_6 、 ACK_7 ，由于 DATA_4 即数据帧组的前一个帧已顺利接收，因此接收窗口向后移动一位

2. 发送方由于只收到 ACK_4 、 ACK_6 、 ACK_7 接收到的 ACK 只有前一位连续，因此发送窗口向后移动一位，此时 DATA_0 进入发送窗口，发送方发送 DATA_0 并设置计时器， DATA_5 的计时器由于超时被触发，开始重传 DATA_5 并重置计时器

3. 接收方顺利接收到 DATA_5 和 DATA_0 ，此时返回 ACK_5 和 ACK_0 ，由于此时接收到的数据帧组全部正确完整连续，接收窗口向后移动 4 位，DATA_1 、 DATA_2 、 DATA_3 、 DATA_4 进入接收窗口

4. 发送方接收到 ACK_5 和 ACK_0 后，发送窗口内的数据帧也全部连续确认发送完毕，发送窗口向右移动 4 位，DATA_1 、 DATA_2 、 DATA_3 、 DATA_4 进入发送窗口

• 数据帧因检测出差错而被接收方丢弃

假设发送方继续发送 DATA_4 、 DATA_5 、 DATA_6 、 DATA_7 由于各种原因，DATA_5 内部出现“差错”，而被接收方拒收丢弃

1. 此时接收方已接收 DATA_4 、DATA_6 、DATA_7 并依次返回 ACK_4 、 NAK_5 、 ACK_6 、 ACK_7 ，由于 DATA_4 即数据帧组的前一个帧已顺利接收，因此接收窗口向后移动一位

2. 发送方由于收到 ACK_4 、 NAK_5 、 ACK_6 、 ACK_7 接收到的 ACK 只有前一位连续，因此发送窗口向后移动一位，此时 DATA_0 进入发送窗口，发送方发送 DATA_0 并设置计时器， 由于收到 NAK_5 ，因此发送方会在计时器超时之前重传 DATA_5 并重置计时器

3. 接收方顺利接收到 DATA_5 和 DATA_0 ，此时返回 ACK_5 和 ACK_0 ，由于此时接收到的数据帧组全部正确完整连续，接收窗口向后移动 4 位，DATA_1 、 DATA_2 、 DATA_3 、 DATA_4 进入接收窗口

4. 发送方接收到 ACK_5 和 ACK_0 后，发送窗口内的数据帧也全部连续确认发送完毕，发送窗口向右移动 4 位，DATA_1 、 DATA_2 、 DATA_3 、 DATA_4 进入发送窗口

NAK 重传可以节约时间，不需要等待发送方计时器超时即可完成重传操作

• 确认帧丢失

1. 发送方依次向接收方发送 DATA_0 ，DATA_1 、 DATA_2 、 DATA_3 ，接收方也正确接收了这 4 帧数据并向发送方发送 ACK_0 ， ACK_1 、 ACK_2 、 ACK_3 ，然后向后移动 4 位接收窗口

2. 假设此时由于各种原因导致发送方未能接收到 ACK_1 、 ACK_3 ，此时由于发送方仅接收到前一位连续的 ACK 因此发送窗口只能先向后移动 1 位，此时 DATA_4 落入发送窗口，发送方发送 DATA_4 并设置计时器， DATA_1 、 DATA_3 超时触发重传

3. 接收方接收到 DATA_4 、 DATA_1 、 DATA_3 由于 DATA_1 、 DATA_3 不在接收窗口内，会被丢弃，而 DATA_4 在接收窗口内于是被接收，并且返回 ACK_4 、 ACK_1 、 ACK_3

4. 3 个 ACK 被正确接收，发送窗口向右移动 4 位，之后继续进行下一轮数据传输流程

特定情况讨论

本例规定使用 3 bit 编号帧

• 不满足 $W_T + W_R \leq 2^n$ 的情况

假设 $W_T = 5, W_R = 4$

1. 发送方同时发送 DATA_0 、 DATA_1 、 DATA_2 、 DATA_3 、 DATA_4 ，接收方依次正确接收了数据并移动接收窗口直到移动 5 位，并依次发送 ACK 此时接收窗口为 DATA_5 、 DATA_6 、 DATA_7 、 DATA_0

2. 在极其特殊的情况下， ACK 全部接收失败，发送方的计时器会陆续超时并重发数据，此时由于发送窗口没有移动，仍然处于 DATA_0 、 DATA_1 、 DATA_2 、 DATA_3 、 DATA_4 这 5 个帧上，因此会重传这些帧，但是接收窗口已经含有 DATA_0（这里的 DATA_0 已经是下一序列的数据了） ，此时重传的数据会被接收方误接收，造成数据错误

三种协议的信道利用率分析

S-W 协议

假设：

• 信道的数据传输速率为 1kbps

• 数据帧长度为 4kb

• 确认帧长度为 1kb

• 信道单向传播时延为 7s

S-W传输信道图示

根据图示结合信道利用率公式

$$\text{信道利用率} = \frac{\text{数据传输时间}}{\text{数据发送时间}}$$

所以可得：

$$\text{发送信道利用率} = \frac{4}{4 + 2 \times 7 + 1} \approx 21 \%$$

设数据帧传输时延为 $T_D$ ，2 倍单向传播时延为 $RTT$ ，确认帧传输时延为 $T_A$ 由此可得理想情况下发送信道利用率 $U$ 为

$$U = \frac{T_D}{T_D + RTT + T_A}$$

在特定情况下可以将确认帧传输时延看成非常短的时间，因此可以将 $T_A$ 看成 0 ，从而得到：

$$U = \frac{T_D}{T_D + RTT}$$

补充：

$$\text{数据帧传输时延} = \frac{\text{数据帧长度}}{\text{信道数据传输速率}}$$

GBN 协议、SR 协议

假设：

• 发送窗口大小为 4

• 信道数据传输速率为 1kbps

• 数据帧长度为 4kb

• 确认帧长度为 1kb

• 信道单向传播时延为 7s

GBN传输信道图示

同样依据上面的公式可以计算：

$$\text{信道利用率} = \frac{4 \times 4}{4 + 2 \times 7 + 1} \approx 84 \%$$

可以总结为：

$$U = \frac{NT_D}{T_D + RTT + T_A}$$

其中 $N$ 为发送窗口的大小

需要特别注意的是，当发送窗口大于某个值时，信道可能会出现拥挤的情况（即某次发送下一帧数据时，前面的某个数据帧还未发送完成占用信道），但是确认帧已经接收，此时的信道利用率即 $U = 1$

术语补充：

• 术语上滑动窗口协议指的是GBN协议和SR协议

• ARQ（Automatic Repeat Request）自动重传请求协议，包含以上三种协议

• 连续 ARQ 协议指的是 GBN 协议和 SR 协议

---

1. 帧首部和尾部存有帧的控制信息，例如：帧定界信息、帧序号、校验码和、帧类型等 ↩︎