自动重传请求（Automatic Repeat reQuest，ARQ）通过接收方请求发送方重传出错的数据帧来恢复出错的的帧。

1 停止-等待协议

为讨论问题方便，设发送方为 A，接收方为 B。

1.1 无差错情况

• A 发送数据帧 DATA0，发完就暂停发送，启动超时计时器，等待 B 的确认。
• B 收到数据帧 DATA0，就向 A 发送确认帧 ACK0。
• A 在超时计时器到期之前，收到数据帧 DATA0 的确认，就再发送数据帧 DATA1，然后再发送数据帧 DATA0，如此反复。

【注】对于停止-等待协议，由于每发送一个数据分组就停止等待，只要保证每发送一个新的数据分组，其序号与上次发送的数据分组的序号不同就可以了，因此用一个比特来编号就够了，序号有 0 和 1。对确认帧也是同样的道理。

1.2 有差错情况——数据帧出错或丢失

• A 发送数据帧 DATA1，发完就暂停发送，启动超时计时器，等待 B 的确认。
• B 收到数据帧 DATA1，检测到出现了差错，就丢弃数据帧 DATA1；或数据帧 DATA1 在传输过程中丢失了。此时 B 不会发送任何信息。
• A 的超时计时器到期后，仍未收到确认帧 ACK1，就认为刚才的数据帧丢失了。
• A 进行超时重传，重新发送数据帧 DATA1，发完就暂停发送，启动超时计时器，等待 B 的确认。

1.3 有差错情况——ACK 丢失

• A 发送数据帧 DATA1，发完就暂停发送，启动超时计时器，等待 B 的确认。
• B 收到数据帧 DATA1，发送确认帧 ACK1，但在传输途中丢失。
• A 的超时计时器到期后，仍未收到确认帧 ACK1，就认为刚才的数据帧丢失了。
• A 进行超时重传，重新发送数据帧 DATA1，发完就暂停发送，启动超时计时器，等待 B 的确认。
• B 收到数据帧 DATA1，重新发送确认帧 ACK1，并丢弃重复的数据帧 DATA1。

1.4 有差错情况——ACK 迟到

• A 发送数据帧 DATA0，发完就暂停发送，启动超时计时器，等待 B 的确认。
• B 收到数据帧 DATA0，发送确认帧 ACK0，但在传输途中遭遇阻塞，未及时传输到 A。
• A 的超时计时器到期后，仍未收到确认帧 ACK0，就认为刚才的数据帧丢失了。
• A 进行超时重传，重新发送数据帧 DATA0，发完就暂停发送，启动超时计时器，等待 B 的确认。
• B 收到数据帧 DATA0，重新发送确认帧 ACK0，并丢弃重复的数据帧 DATA0。
• A 在超时计时器到期之前，收到这一轮的确认帧 ACK0，就再发送数据帧 DATA1。
• 这时 A 才收到先前的确认帧 ACK0，A 将该重复的确认帧 ACK0丢弃。

1.5 性能分析

信道利用率：

U=TDT+RTT+TA\\begin{equation} U=\\frac{T_D}{T+RTT+T_A} \\end{equation} U=T+RTT+TA​TD​​​​

因为确认分组长度远小于数据分组长度：TA<<TDT_A<<T_DTA​<<TD​，所以又可以化简为：

U=TDT+RTT\\begin{equation} U=\\frac{T_D}{T+RTT} \\end{equation} U=T+RTTTD​​​​

【注】设时间$T$内发送$L$比特数据，数据传输率为$C$，则：

信道利用率=LCT信道利用率=\\frac{\\frac{L}{C}}{T} 信道利用率=TCL​​

$$信道吞吐率=信道利用率\times 发送方的发送速率$$

1.6 相关例题

【例 1】主机甲采用停-等协议向主机乙发送数据，数据传输速率是 3kbps，单向传播延时是 200ms，忽略确认帧的传输延时。当信道利用率等于 40% 时，数据帧的长度为（D）。

A. 240 比特

B. 400 比特

C. 480 比特

D. 800 比特

【解】设数据帧长度为$xb$，代入数据得：

信道利用率=数据帧的发送时延数据帧的发送时延+单向传播时延×240%=xb3kb/sxb3kb/s+200ms×2\\begin{align*} 信道利用率 &= \\frac{数据帧的发送时延}{数据帧的发送时延+单向传播时延 \\times 2} \\\\ 40\\% &= \\frac{\\frac{x b}{3kb/s}}{\\frac{x b}{3kb/s} + 200ms \\times 2} \\end{align*} 信道利用率40%​=数据帧的发送时延+单向传播时延×2数据帧的发送时延​=3kb/sxb​+200ms×23kb/sxb​​​

解得$x=800b$

2 后退 N 帧协议（GBN）

发送窗口：发送方需要维护一个发送窗口WTW_TWT​，在未收到接收方确认分组的情况下，发送方可将序号落入WTW_TWT​内的所有数据分组连续发送出去。采用 n 个比特给分组编序号，则WTW_TWT​的取值范围是1<WT≤2n−11<W_T≤2^n-11<WT​≤2n−1。

【注】若WT>2n−1W_T>2^n-1WT​>2n−1，则接收方无法分辨新旧数据分组。

接收窗口：接收方需要维护一个接收窗口WRW_RWR​，只有正确到达接收方（无误码）且序号落入WRW_RWR​内的数据分组才被接收方接收。WRW_RWR​的取值只能是 1。

为讨论问题方便，设发送方为 A，接收方为 B，假设采用 3 个比特给分组编序号，则WTW_TWT​的取值范围是 2~7，这里取WT=5W_T=5WT​=5。

2.1 无差错情况

• 初始时：

• 发送方 A 发送WTW_TWT​内的序号 0：

• 接收方 B 收到序号 0，检查发现序号 0 是WRW_RWR​内，于是接收，并返回 ACK0，WRW_RWR​向前移动一个序号。发送方 A 收到 ACK0 后，WTW_TWT​向前移动一个序号：

• 接下来发送方 A 发送序号 1，跟之前一样的过程。当 A 发完前 5 个数据后的情况如下：

• 当然，接收方不必对收到的每一个数据分组都发送一个确认分组，而是可以在收到几个序号连续的数据分组后，对按序到达的最后一个数据分组发送确认分组，这叫累积确认。ACKn 表明序号为 n 及之前的所有数据分组都已正确接收（如 ACK4 表示序号 0~4 已正确接收）：

2.2 超时重传、回退 N 帧

• 初始时：

• 发送方 A 发完WTW_TWT​的 5 个数据，序号 0 和序号 1 没有问题，接收方 B 依次返回了 ACK0 和 ACK1，WTW_TWT​和WRW_RWR​向前移动到相应位置。但序号 2 出现了误码，被接收方 B 丢弃，同时重复发送 ACK1（接收方必须按序接收数据分组）；之后 B 收到正确的序号 3 和 4，但因为没有落入WRW_RWR​，所以都被丢弃，且 B 重复发送了两次 ACK1：

• 发送方 A 针对序号 2 的重传计时器已经超时，但仍未等来 B 发来的 ACK2，因此 A 重发WTW_TWT​的 5 个数据（注意与初始时所发数据不同了）。这次接收方 B 收到了正确的数据，并依次返回 ACK：

2.3 相关例题

【例 1】数据链路层使用后退 N 帧（GBN）协议，发送方已经发送了编号 0~7 的帧。当计时器超时时，若发送方只收到了 0、2、3 号帧的确认，则发送方需要重发的帧数是（C）。

A. 2

B. 3

C. 4

D. 5

【例 2】主机甲与主机乙之间使用后退 N 帧（GBN）协议传输数据，甲的发送窗口尺寸为 1000，数据帧长为 1000 字节，信道带宽为 100Mbps，乙每收到一个数据帧就立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间的单向传播延迟是 50ms，则甲可以达到的最大平均数据传输速率约为（C）。

【解】

最大平均数据传输速率=可发送的数据量数据帧的发送时延+单向传播时延×2=1000×8×10001000100×106+50×10−6×2=80Mbps\\begin{align*} 最大平均数据传输速率 &= \\frac{可发送的数据量}{数据帧的发送时延+单向传播时延 \\times 2} \\\\ &= \\frac{1000 \\times 8 \\times 1000}{\\frac{1000}{100 \\times 10^{6}} + 50 \\times 10^{-6} \\times 2} \\\\ &= 80Mbps \\end{align*} 最大平均数据传输速率​=数据帧的发送时延+单向传播时延×2可发送的数据量​=100×1061000​+50×10−6×21000×8×1000​=80Mbps​

3 选择重传协议（SR）

为了使发送方仅重传出现差错的数据分组，接收方不再采用累积确认，而需要对每一个正确接收的数据分组进行逐一确认。用$n(n>1)$个比特给分组编号：

{1<WR≤WTWT+WR≤2n\\left\\{ \\begin{aligned} %\\nonumber 1<W_R≤W_T\\\\ W_T+W_R≤2^{n}\\\\ \\end{aligned} \\right. {1<WR​≤WT​WT​+WR​≤2n​

因此有：1<WR≤2n−11<W_R≤2^{n-1}1<WR​≤2n−1

当WRW_RWR​取最大值2n−12^{n-1}2n−1时，WRW_RWR​也取最大值2n−12^{n-1}2n−1

【注】为何如此取值？

• 1<WR≤WT1<W_R≤W_T1<WR​≤WT​：WRW_RWR​超过WTW_TWT​没有意义。
• WT+WR≤2nW_T+W_R≤2^{n}WT​+WR​≤2n：确保接收窗口向前滑动后，落入接收窗口内的新序号与之前的旧序号没有重叠，避免无法分辨新旧数据分组。

现假设采用 3 个比特给分组编序号，则序号范围是[0,23−1][0,2^3-1][0,23−1]，发送窗口取最大值WT=23−1=22W_T=2^{3-1}=2^2WT​=23−1=22，接收窗口取最大值WR=23−1=22W_R=2^{3-1}=2^2WR​=23−1=22。

3.1 有差错情况

• 初始时：

• 发送方 A 发送WTW_TWT​内的序号 0~3：

• 接收方 B 只收到序号 0 和序号 2，序号 1 丢失，序号 3 误码被 B 丢弃。于是 B 发送 ACK0 和 ACK2：

• 发送方 A 针对序号 1 和序号 3 的重传计时器已经超时，所以重新发送序号 1 和序号 3。接收方 B 正确接收后发送 ACK1 和 ACK3：

• 发送方 A 收到 ACK 后，双方的滑动窗口向前移动，继续下一轮传输：

3.2 相关例题

【例 1】数据链路层采用选择重传协议（SR）传输数据，发送方已发送了 0~3 号数据帧，现已收到 1 号帧的确认，而 0、2 号帧依次超时，则此时需要重传的帧数是（B）。

A. 1

B. 2

C. 3

D. 4

4 总结