跳到主要内容

附录 A. 强包守恒边界

强包守恒边界是可为 PRR-CRB 建立的一个形式化属性. 它表明, 在恢复期间的所有条件和事件序列下, PRR-CRB 都严格限制传输的数据量, 使其等于或小于已交付到接收方的数据量.

A.1. 形式化定义​

设:

  • D(t) = 时刻 t 已交付到接收方的累计数据
  • S(t) = 恢复期间时刻 t 发送方已发送的累计数据
  • R = 恢复开始时 inflight 的初始值 (RecoverFS)

则 PRR-CRB 保证:

S(t) - S(0) ≤ D(t) - D(0)

对于恢复阶段期间的所有 t 都成立, 其中 S(0) 和 D(0) 是恢复开始时的值.

A.2. 直观理解​

强包守恒边界确保恢复期间:

  1. 不会发送超过已交付数据的突发数据: 发送方绝不会向网络发送超过已确认交付到接收方的数据量的新数据.

  2. 恒定队列长度属性: 如果瓶颈处存在常驻队列且没有交叉流量, 则恢复期间该队列会保持精确恒定的长度, 仅因包到达和离开时间差异而出现 ±1 个段的波动.

  3. 保留自时钟: 该边界以最强形式保留 Van Jacobson 的包守恒原则, 即每个已交付的包最多触发发送一个包.

A.3. 数学证明概要​

PRR-CRB 维持以下不变量:

prr_out ≤ prr_delivered

当 inflight ≤ ssthresh 时, PRR-CRB 计算:

SndCnt = MAX(prr_delivered - prr_out, DeliveredData)

这确保:

  1. 基础项 prr_delivered - prr_out 维持守恒边界
  2. DeliveredData 项确保向前推进
  3. 最后的 MIN(ssthresh - inflight, SndCnt) 限制防止超过目标窗口

A.4. 对网络行为的影响​

队列稳定性​

在强包守恒边界下:

  • 稳定的瓶颈队列: 如果某个流在瓶颈处有常驻队列, PRR-CRB 不会导致该队列在恢复期间增长
  • 不放大拥塞: 恢复不会使现有拥塞恶化
  • 可预测行为: 网络运营者可以推理最坏情况下的队列占用

折中​

虽然强包守恒边界提供了强保证:

优点:

  • 消除重传诱发的拥塞崩溃
  • 提供可预测且保守的行为
  • 在保持队列稳定的同时保证向前推进

缺点:

  • 在某些场景中可能过于保守 (见第 7 节和第 8 节示例)
  • 当实际丢失超过目标窗口降低量时, 可能导致更长的恢复时间
  • 恢复期间可能无法充分利用可用带宽

A.5. 与 PRR-SSRB 的关系​

PRR-SSRB 通过允许每个 ACK 多发送一个段 (当 SafeACK 为 true 时), 对强包守恒边界做了轻微放宽:

SndCnt = MAX(prr_delivered - prr_out, DeliveredData) + SMSS

这意味着 PRR-SSRB 对严格边界的临时违反最多为:

(number of ACKs) × SMSS

但是, 这种违反是有界且受控的:

  • 仅在 inflight < ssthresh 时发生
  • 仅在 SafeACK 表明恢复进展良好时发生
  • 通常以极小风险实现更快恢复

A.6. 历史背景​

强包守恒边界形式化并强化了 Van Jacobson 的原始包守恒原则 [Jacobson88]. 原始原则允许将 "推定丢失" 的包视为已经离开网络, 而强边界只计算实际交付到接收方的包.

这种更严格的解释确保:

  1. pipe 计算中的估计错误不会造成突发
  2. 即使发生重排序, 算法也保持保守
  3. 恢复行为会基于实际接收方反馈自我校正

A.7. 实践考虑​

实现说明​

实现者应注意:

  • 该边界适用于概念性算法; 实现优化必须保留该属性
  • 字节计数 (而不是段计数) 提供更好的粒度, 并能更好防御 ACK 分割攻击
  • 无论其他估计器 (pipe, cwnd 等) 的准确性如何, 该边界都成立

性能影响​

在实践中:

  • PRR-CRB 的严格边界对于严重丢失场景可能过于保守
  • 自适应 SafeACK 启发式方法 (切换到 PRR-SSRB) 提供更好的真实世界性能
  • 该边界的价值在于提供安全保证, 而不是在所有情况下都提供最优性能

A.8. 形式化不变量​

PRR-CRB 在整个恢复期间维持以下不变量:

不变量 1 (守恒):

prr_out ≤ prr_delivered

不变量 2 (目标收敛):

lim (prr_out) = ssthresh
t→end

(假设丢失很少且没有应用停顿)

不变量 3 (单调性):

prr_delivered(t₁) ≤ prr_delivered(t₂) for all t₁ < t₂
prr_out(t₁) ≤ prr_out(t₂) for all t₁ < t₂

这些不变量确保:

  • 向前推进 (单调性)
  • 守恒 (不变量 1)
  • 正确的最终状态 (不变量 2)

A.9. 结论​

强包守恒边界为 PRR-CRB 提供了严谨基础, 确保 TCP 恢复绝不放大现有拥塞. 虽然 PRR-SSRB 和 SafeACK 启发式方法为了获得更好性能而放宽了该边界, 但强边界仍是一个重要的理论基线, 可保证即使在最坏场景下也能安全运行.

最后于 更新