目录
自动重传请求(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 性能分析
信道利用率:
\[\begin{equation} U=\frac{T_D}{T+RTT+T_A} \end{equation} \]因为确认分组长度远小于数据分组长度:\(T_A<<T_D\),所以又可以化简为:
\[\begin{equation} U=\frac{T_D}{T+RTT} \end{equation} \]【注】设时间\(T\)内发送\(L\)比特数据,数据传输率为\(C\),则:
\[信道利用率=\frac{\frac{L}{C}}{T} \]\[信道吞吐率=信道利用率 \times 发送方的发送速率 \]
1.6 相关例题
【例 1】主机甲采用停-等协议向主机乙发送数据,数据传输速率是 3kbps,单向传播延时是 200ms,忽略确认帧的传输延时。当信道利用率等于 40% 时,数据帧的长度为(D)。
A. 240 比特
B. 400 比特
C. 480 比特
D. 800 比特
【解】设数据帧长度为\(x b\),代入数据得:
\[\begin{align*} 信道利用率 &= \frac{数据帧的发送时延}{数据帧的发送时延+单向传播时延 \times 2} \\ 40\% &= \frac{\frac{x b}{3kb/s}}{\frac{x b}{3kb/s} + 200ms \times 2} \end{align*} \]解得\(x=800b\)
2 后退 N 帧协议(GBN)
发送窗口:发送方需要维护一个发送窗口\(W_T\),在未收到接收方确认分组的情况下,发送方可将序号落入\(W_T\)内的所有数据分组连续发送出去。采用 n 个比特给分组编序号,则\(W_T\)的取值范围是\(1<W_T≤2^n-1\)。
【注】若\(W_T>2^n-1\),则接收方无法分辨新旧数据分组。
接收窗口:接收方需要维护一个接收窗口\(W_R\),只有正确到达接收方(无误码)且序号落入\(W_R\)内的数据分组才被接收方接收。\(W_R\)的取值只能是 1。
为讨论问题方便,设发送方为 A,接收方为 B,假设采用 3 个比特给分组编序号,则\(W_T\)的取值范围是 2~7,这里取\(W_T=5\)。
2.1 无差错情况
- 初始时:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | |||||||||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 |
- 发送方 A 发送\(W_T\)内的序号 0:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | √ | ||||||||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 |
- 接收方 B 收到序号 0,检查发现序号 0 是\(W_R\)内,于是接收,并返回 ACK0,\(W_R\)向前移动一个序号。发送方 A 收到 ACK0 后,\(W_T\)向前移动一个序号:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | √ | ||||||||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 | √ |
- 接下来发送方 A 发送序号 1,跟之前一样的过程。当 A 发完前 5 个数据后的情况如下:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | √ | √ | √ | √ | √ | ||||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 | √ | √ | √ | √ | √ |
- 当然,接收方不必对收到的每一个数据分组都发送一个确认分组,而是可以在收到几个序号连续的数据分组后,对按序到达的最后一个数据分组发送确认分组,这叫累积确认。ACKn 表明序号为 n 及之前的所有数据分组都已正确接收(如 ACK4 表示序号 0~4 已正确接收):
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | √ | √ | √ | √ | √ | ||||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 | √ |
2.2 超时重传、回退 N 帧
- 初始时:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | |||||||||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 |
- 发送方 A 发完\(W_T\)的 5 个数据,序号 0 和序号 1 没有问题,接收方 B 依次返回了 ACK0 和 ACK1,\(W_T\)和\(W_R\)向前移动到相应位置。但序号 2 出现了误码,被接收方 B 丢弃,同时重复发送 ACK1(接收方必须按序接收数据分组);之后 B 收到正确的序号 3 和 4,但因为没有落入\(W_R\),所以都被丢弃,且 B 重复发送了两次 ACK1:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | √ | √ | √ | √ | √ | ||||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 | √ | √ |
- 发送方 A 针对序号 2 的重传计时器已经超时,但仍未等来 B 发来的 ACK2,因此 A 重发\(W_T\)的 5 个数据(注意与初始时所发数据不同了)。这次接收方 B 收到了正确的数据,并依次返回 ACK:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | √ | ||||||
发送方 A 已发送 | √ | √ | √ | √ | √ | √ | √ | ||||
接收方 B 的 \(W_R\) | √ | ||||||||||
接收方 B 已确认 | √ | √ | √ | √ | √ | √ | √ |
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)。
【解】
3 选择重传协议(SR)
为了使发送方仅重传出现差错的数据分组,接收方不再采用累积确认,而需要对每一个正确接收的数据分组进行逐一确认。用\(n(n>1)\)个比特给分组编号:
\[\left\{ \begin{aligned} %\nonumber 1<W_R≤W_T\\ W_T+W_R≤2^{n}\\ \end{aligned} \right. \]因此有:\(1<W_R≤2^{n-1}\)
当\(W_R\)取最大值\(2^{n-1}\)时,\(W_R\)也取最大值\(2^{n-1}\)
【注】为何如此取值?
- \(1<W_R≤W_T\):\(W_R\)超过\(W_T\)没有意义。
- \(W_T+W_R≤2^{n}\):确保接收窗口向前滑动后,落入接收窗口内的新序号与之前的旧序号没有重叠,避免无法分辨新旧数据分组。
现假设采用 3 个比特给分组编序号,则序号范围是\([0,2^3-1]\),发送窗口取最大值\(W_T=2^{3-1}=2^2\),接收窗口取最大值\(W_R=2^{3-1}=2^2\)。
3.1 有差错情况
- 初始时:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | |||||||
发送方 A 已发送 | |||||||||||
接收方 B 的 \(W_R\) | √ | √ | √ | √ | |||||||
接收方 B 已确认 |
- 发送方 A 发送\(W_T\)内的序号 0~3:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | |||||||
发送方 A 已发送 | √ | √ | √ | √ | |||||||
接收方 B 的 \(W_R\) | √ | √ | √ | √ | |||||||
接收方 B 已确认 |
- 接收方 B 只收到序号 0 和序号 2,序号 1 丢失,序号 3 误码被 B 丢弃。于是 B 发送 ACK0 和 ACK2:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | |||||||
发送方 A 已发送 | √ | √ | √ | √ | |||||||
接收方 B 的 \(W_R\) | √ | √ | √ | √ | |||||||
接收方 B 已确认 | √ | √ |
- 发送方 A 针对序号 1 和序号 3 的重传计时器已经超时,所以重新发送序号 1 和序号 3。接收方 B 正确接收后发送 ACK1 和 ACK3:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | |||||||
发送方 A 已发送 | √ | √ | √ | √ | |||||||
接收方 B 的 \(W_R\) | √ | √ | √ | √ | |||||||
接收方 B 已确认 | √ | √ | √ | √ |
- 发送方 A 收到 ACK 后,双方的滑动窗口向前移动,继续下一轮传输:
数据序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|
发送方 A 的 \(W_T\) | √ | √ | √ | √ | |||||||
发送方 A 已发送 | √ | √ | √ | √ | |||||||
接收方 B 的 \(W_R\) | √ | √ | √ | √ | |||||||
接收方 B 已确认 | √ | √ | √ | √ |
3.2 相关例题
【例 1】数据链路层采用选择重传协议(SR)传输数据,发送方已发送了 0~3 号数据帧,现已收到 1 号帧的确认,而 0、2 号帧依次超时,则此时需要重传的帧数是(B)。
A. 1
B. 2
C. 3
D. 4
4 总结
协议 | 发送窗口\(W_T\) | 接收窗口\(W_R\) |
---|---|---|
停止-等待协议 | \(1\) | \(1\) |
后退 N 帧协议 | \(1<W_T≤2^n-1\) | \(1\) |
选择重传协议 | \(1<W_R≤W_T, W_T+W_R≤2^{n}\) | \(1<W_R≤2^{n-1}\) |