3.4 流量控制与可靠传输机制

流量控制与可靠传输机制：停止-等待协议、后退N帧协议、选择重传协议。

3.4 流量控制与可靠传输机制

3.4.1 流量控制、可靠传输与滑动窗口机制

1. 流量控制

• 目标：协调发送方与接收方的数据传输速率，避免接收方缓冲区溢出。
• 作用范围：
  • 数据链路层：相邻节点间
  • 传输层：端到端

2. 可靠传输

• 目标：确保接收端准确无误地接收发送端所发送的数据。

• 核心机制：

  • 确认（ACK）：接收方告知发送方哪些内容被正确接收。有时将确认捎带在回复帧中（捎带确认）。
  • 超时重传：发送方发送数据帧后启动计时器，超时未收到确认则重传。

• 自动重传请求（ARQ）：通过请求重传出错帧来应对信道差错，主要包括：

  • 停止-等待ARQ：每发一帧等待确认，仅当确认到达后才发新帧。
  • 后退N帧ARQ（GBN）：发送窗口内可连续发送多帧，若某帧出错，则重传该帧及之后所有帧。
  • 选择性重传ARQ（SR）：仅重传出错帧，正确接收的帧暂存。

注意：数据链路层中流量控制与可靠传输机制交织在一起。有线链路出错概率低，通常不要求数据链路层提供可靠传输；无线链路出错概率高，通常要求可靠传输。可靠传输不局限于数据链路层，各层均可选择实现。

3. 滑动窗口机制

• 发送窗口：发送方维护，窗口内的数据帧可连续发送而不必等待确认。
• 接收窗口：接收方维护，窗口内的数据帧可按序接收和确认。
• 窗口滑动：收到确认后，窗口向前滑动，允许发送/接收下一批帧。
• 特性：
  • 接收窗口向前滑动后，发送窗口才可能向前滑动（基于收到的确认）。
  • 三种协议的窗口大小：
    • 停止-等待：发送窗口 = 1，接收窗口 = 1
    • 后退N帧：发送窗口 > 1，接收窗口 = 1
    • 选择重传：发送窗口 > 1，接收窗口 > 1
  • 接收窗口为1时可保证帧的有序接收。
  • 数据链路层滑动窗口协议中，窗口大小在传输过程中固定。

3.4.2 停止-等待协议

• 原理：发送方每发送一个数据帧，必须等待接收方的确认（ACK）后才能发送下一帧。
• 流程：
  1. 发送方发送数据帧，启动超时计时器。
  2. 接收方收到后发送ACK。
  3. 发送方收到ACK，发送下一帧。
  4. 若超时未收到ACK，重传该帧。
• 细节：
  • 使用1比特编号（0/1），ACK0/ACK1。
  • 发送方保留副本，收到确认后清除；接收方也保留缓冲区。
  • 超时时间应大于平均RTT。
• 信道利用率：
  [
  \text{信道利用率} = \frac{\text{数据传输时间}}{\text{发送周期}}
  ]
  其中发送周期 = 数据传输时间 + 2×传播时延 + 确认帧传输时间（忽略时通常简化为 ( T_{\text{data}} + 2\tau )）。
• 优点：实现简单，确保可靠传输。
• 缺点：信道利用率低，适合低速传输。

例题（2018年36题）
主机甲采用停-等协议向乙发送数据，速率3kbps，单向传播时延200ms，忽略确认帧传输时延。当信道利用率=40%时，数据帧长度？

• 解：设帧长 (L) bit，发送时间 (t = L / 3000) s，RTT=0.4 s。
  利用率 (= t / (t + 0.4) = 0.4 ) → ( t = 0.4t + 0.16 ) → (0.6t = 0.16) → (t = 0.2667) s → (L = 800) bit。选D。

3.4.3 后退N帧协议（GBN）

• 原理：发送方在窗口内可连续发送多帧，若某帧出错，则重传该帧及之后所有帧（后退N）。
• 窗口约束：发送窗口 (1 < W_T \leq 2^n - 1)，接收窗口 (W_R = 1)（n为帧编号位数）。
• 流程：
  • 发送方连续发送窗口内帧，每帧设超时计时器。
  • 接收方按序接收，发送累积确认（ACK序号表示该序号之前的所有帧都已正确接收）。
  • 若接收帧序号不是期望的，则丢弃并重发上一个ACK。
  • 超时后，发送方重传从第一个未确认帧开始的所有帧。
• 优点：提高信道利用率，接收方简单。
• 缺点：出错时重传量大，若误码率高，可能不如停-等协议。

例题（2009年35题）
已发0~7号帧，计时器超时，收到0、2、3号帧的确认，需要重发的帧数？

• 累积确认：收到3号确认表示03都已正确。未确认的是47，需重发4个帧。选C。

3.4.4 选择重传协议（SR）

• 原理：发送方可连续发送窗口内帧，接收方仅请求重传出错帧，正确接收的帧暂存。
• 窗口约束：发送窗口 (W_T > 1)，接收窗口 (W_R > 1)，且 (W_T + W_R \leq 2^n)，通常 (W_T = W_R = 2^{n-1})。
• 流程：
  • 发送方发送窗口内帧，每帧设超时计时器。
  • 接收方按序接收，对正确接收的帧发送ACK（单独确认，非累积）。若收到的帧序号在接收窗口内但未按序，则暂存并发送ACK；若序号在窗口外则丢弃。
  • 若某帧出错，接收方发送NAK请求重传该帧。
  • 超时后，发送方仅重传未确认的帧。
• 优点：减少重传开销，适合高误码率信道。
• 缺点：接收方需较大缓冲区，窗口大小受限于序号空间。

例题（2015年35题）
主机甲通过128kbps卫星链路，单向传播时延250ms，帧长1000字节，不考虑确认帧开销。要使链路利用率≥80%，帧序号比特数至少？

• 解：发送一帧时间 (t = 1000×8 / 128000 = 0.0625) s，RTT=0.5 s。发送周期至少为 (t + RTT = 0.5625) s。若窗口大小为 (W)，则连续发送 (W) 帧的总时间为 (W×t)，要求 (W×t / (W×t + RTT) \geq 0.8)。代入得 (W×0.0625 / (W×0.0625+0.5) \geq 0.8) → (W×0.0625 \geq 0.8W×0.0625 + 0.4) → (0.0125W \geq 0.4) → (W \geq 32)。需要 (W \leq 2^{n-1})，故 (2^{n-1} \geq 32) → (n-1 \geq 5) → (n \geq 6)，取整数n=6？但选项是3,4,7,8。实际上考虑最大窗口 (2^{n-1})，至少32，则 (2^{n-1} \geq 32) → (n \geq 6)，但选项无6，可能是算错？正确应为 (W \leq 2^{n-1}) 且 (W \geq 32)，故 (2^{n-1} \geq 32) → (n \geq 6)，但选项只有3,4,7,8，可能因链路是卫星，RTT大，实际需要n=8？复习：通常SR窗口最大为 (2^{n-1})，若W=32，则n-1=5 → n=6。但答案可能是B.4？再算：利用率为 (W×t / (W×t + RTT) = W×0.0625 / (W×0.0625+0.5) \geq 0.8) 解得 (W \geq 32)。由于 (W \leq 2^{n-1})，所以 (2^{n-1} \geq 32) → (n-1 \geq 5) → (n \geq 6)，最少需要6位。选项无6，若n=4，最大窗口8<32；n=7，最大窗口64≥32，可行，但n=6就够了，但选项给7可能对应。然而真题答案选B.4？我怀疑原题数据不同。实际上2015年35题原题是128kbps，帧长1000B，传播时延250ms，选项是3,4,7,8，正确答案是4？让我再核对：若n=4，最大窗口8，利用率=8×0.0625/(8×0.0625+0.5)=0.5/1=0.5，不足0.8；n=7，最大窗口64，利用率=64×0.0625/(64×0.0625+0.5)=4/4.5≈0.89>0.8，满足。但题目问“至少”，应选n=7。但可能原题窗口公式为 (W_T \leq 2^n-1)，但SR常用 (W_T \leq 2^{n-1})。这里不纠结，按标准公式计算即可。

习题

1. 在停止-等待协议中，接收方收到重复帧时，正确的处理方式是（A. 丢弃该帧, 并向发送方发送确认帧）

2. 假设数据帧长度为1000字节，数据传输速率为1Mbps，信号传播时延为20ms，确认帧长度忽略不计，采用停止-等待协议，信道利用率约为（B. 20%？）

   • 发送时间=1000×8/1e6=0.008s，RTT=0.04s，周期=0.048s，利用率=0.008/0.048≈16.7%，接近A.17%

3. 在后退N帧协议（GBN）中，当一个数据包出现错误时，发送方会如何处理（B. 重传所有未确认的数据包）

4. 假设GBN协议的发送窗口大小为5，当发送方发送了0-4号帧后，收到对1号帧的确认，此时发送方还可以发送的帧数是（C. 3）

   • 已确认1号，窗口滑到2，新窗口为2~6，已发送2,3,4，还可发5,6,7? 窗口大小5，故最多发5个未确认，已发2,3,4三个未确认，还可发2个？但选项有1,2,3,4。具体：窗口大小为5，收到对1的确认，则窗口下界变为2，窗口包含2,3,4,5,6。已发2,3,4，还可发5,6两个。所以选B.2。但有的教材认为GBN窗口大小固定，发送方收到ACK后可以继续发送，但此时已发帧中还有未确认的2,3,4，窗口内允许连续发送的帧数不超过窗口大小减去已发未确认数，故还可发2帧。因此答案为2，但原题选项是1,2,3,4，选B。

5. 在SR协议中，若发送方的定时器超时，它会（B. 重发超时的那一帧）

6. 在SR协议中，发送方已经发送了编号为0-4的帧，仅收到对2号帧的确认时，发送窗口的范围是（D. 3-6）

   • 收到2号确认，表示2已正确，但0,1,3,4未确认（因SR单独确认）。发送窗口下界移动到3，窗口大小不变（假设大小=4），则窗口为3~6。

7. 谢希仁教材5-16：在停止等待协议中如果不使用编号是否可行？为什么？

   • 不可行。若不使用编号，接收方无法区分重复帧和正常帧，可能导致协议出错。

8. 谢希仁教材5-18：画图略。描述：发送方发M0，超时重传M0，后来收到旧M0的确认，接着发M1并收到确认，再发新M0时丢失，旧M0到达接收方，接收方误认为是新M0并确认，导致协议失败。

9. 谢希仁教材5-21：

   • (1) 发送窗口大小=3，序号015，接收方期望序号5，表明接收方已收到04，发送窗口可能包含哪些序号？可能的情况：发送方可能已发5,6,7（窗口下界5），也可能只发了5,6（窗口57），也可能只发了5（窗口57），也可能还未发5（但窗口下界5表示已发5？实际上，窗口下界是5表示04已确认，57是发送窗口，但5可能已发未确认，也可能未发。所以组合可以是{5},{5,6},{5,6,7}。但题目说“可能出现的序号组合”，即发送方已经发送但未确认的帧的序号集合。因为接收方期望5，说明0~4已确认，所以发送窗口下界为5，窗口内是5,6,7。发送方已发送的帧只能是5,6,7的子集，所以组合有：{5},{6},{7},{5,6},{5,7},{6,7},{5,6,7}，但实际GBN中窗口内帧一般是连续发送的，所以可能只有{5},{5,6},{5,6,7}三种（因为发送方通常从窗口下界开始连续发送）。题目可能要求列出所有可能。
   • (2) 接收方已发送的确认分组可能有哪些？确认分组用来确认序号04（因为期望5，表明04已确认，但确认分组可能还滞留在网络中）。确认分组可能是ACK0, ACK1, …, ACK4，以及可能ACK? 另外，由于可能未收到某些帧的确认，所以网络中可能有对04的确认，也可能有重复确认（如多个ACK3）。但题目只问“可能有哪些”，即可能存在的确认分组序号范围是04。

笔记结束