Flow Control

Stop and Wait

发送端发送一帧至接收端。在接收端成功接收这一帧之后，它会进行一个回复（ACK）。发送端会在收到 ACK 之前进行持续的等待。接收端可以通过不发送 ACK 的方式中断传输流。

由于发送的帧数很多，这一方式的效率不足。

Sliding Windows

允许多个帧一起传送以提高效率。发送方可在无需等待 ACK 的情况下一次发送至多 W 帧。

每一帧都有序号。ACK 包含了下一帧的序号，即 ACK n 或者 RR n 表示了接收方已经接收到了直到序号为 n - 1 的帧，并准备接收第 n 及以后的帧。

帧的序号为从 0 至 2k - 1 的数字，其中 k 为位数。例如当 k = 2 时，帧序号依次为 0，1，2，3，0，1 … 等等。

发送方

  • 保持一个尺寸为 W 的窗口
  • 窗口初始大小为 W
  • 窗口大小表示了无需等待 ACK 即可进行传送的最大帧数量
  • 当发送一帧时，窗口大小减去1
  • 当收到一个 ACK 时，窗口大小增加1
  • 已经发送但是没有被回复 ACK 的帧保留在缓冲中

接收方

  • 保持一个尺寸为 W 的窗口
  • 窗口初始大小为 W
  • 窗口大小表示无需发送 ACK 即可进行接收的最大帧数量
  • 当收到一帧时，窗口大小减去1
  • 当发送一个 ACK 时，窗口大小增加1
  • 已经收到但是没有回复 ACK 的帧保留在缓冲中

Reliable Transmission

Automatic Repeat Request

Stop and Wait ARQ

在 stop and wait 基础上，发送端使用 timeout 机制。如果接收端收到损坏帧或者丢失帧，那么它不会回复 ACK。发送端在一定时间内没有收到回复，则重新发送。

实现很简单，但是 link utilization 很低。

Link utilization (U) 定义为数据帧实际花费的传输时间和连接被占用的时间的比值。

Go Back N ARQ

建立在 sliding window 的基础上。最大窗口大小为 2k - 1。

如果出错，接收端将丢弃该帧以及之后的帧直到该帧被正确接收。发送端返回重新发送该错误帧及之后的帧。

比 stop and wait 具有更好的 link utilization。适用于错误不多的情况。

Selective Reject ARQ

建立在 sliding window 的基础上。最大窗口大小为 2k-1。

如果出错，该帧被拒绝且由发送端重新发送，但是之后的帧会被接收并置于缓冲中。在传递给高层前需要对帧进行安排使之有序。

重新发送的情况减少，具有更好的 link utilization。接收端需要足够大的缓冲。实现比较复杂。

Performance of ARQ

  • Frame transmission time Tf
  • Link propagation time Tp
  • Total time that the link is engaged for one frame transmission denoted by Ttotal
  • Transmission time of ACK frame is negligible
  • Frame error probability denoted by Pf
  • Errors in ACK frames can be ignored
  • Errors in retransmitted frames other than the frame initially in error can be ignored
  • a = link propagation time (Tp) / frame transmission time (Tf) = number of frames that can be held on a link

Stop and Wait ARQ

Pf = 0 (error-free case)

  • 每隔 Tf+2Tp 发送一帧，Ttotal = Tf + 2Tp
  • U = Tf / Ttotal = 1 / (1 + 2a)

Pf > 0 (error case)

  • 令 Nr 表示每一帧被传送的次数，则 Nr = 1/(1 - Pf)
  • U = Tf / (Nr × Ttotal) = (1 - Pf) / (1 + 2a)

Go Back N ARQ

Error-free case

  • U = 1, W >= 1 + 2a，在这个情况下每隔 Tf 就发送一帧
  • U = W / (1 + 2a), W < 1 + 2a

Error case

  • U = (1 - Pf) / (1 + 2aPf), W >= 1 + 2a
  • U = [W(1 - Pf)] / [(1 + 2a)(1 - Pf + WPf)], W < 1 + 2a

Selective Reject ARQ

Error-free case

  • 和 Go Back N ARQ 一样

Error case

  • U = (1 - Pf), W >= 1 + 2a
  • U = [W(1 - Pf)] / (1 + 2a), W < 1 + 2a