526互联

【计算机网络-数据链路层】流量控制与可靠传输机制

发布时间 2023-04-14 10:51:33作者: Mount256

目录

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

1 停止-等待协议

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

1.1 无差错情况

image

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

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

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

image

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

1.3 有差错情况——ACK 丢失

image

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

1.4 有差错情况——ACK 迟到

image

  • 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 性能分析

image

信道利用率：

\[\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）。

【解】

image

\[\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*} \]

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}\)