第 12 章：技术挑战：多路径调度的难题

QUIC 的流数据必须按偏移量顺序交付给应用层。
多路径调度可能导致：快路径的数据到了，但慢路径的前序数据还没到。

时间线示例：

  发送端：
    偏移 0-999:   → Path 0 (WiFi, RTT 20ms)
    偏移 1000-1999: → Path 1 (4G, RTT 100ms)
    偏移 2000-2999: → Path 0 (WiFi, RTT 20ms)
    偏移 3000-3999: → Path 1 (4G, RTT 100ms)

  接收端时间线：
    T=20ms:  收到偏移 0-999 ✓ → 可以交付给应用
    T=22ms:  收到偏移 2000-2999 ✓ → 不能交付！要等 1000-1999
    T=100ms: 收到偏移 1000-1999 ✓ → 现在可以交付 1000-2999
    T=102ms: 收到偏移 3000-3999 ✓ → 交付

  应用层感受的延迟：
    第一块：20ms（正常）
    第二块：100ms（等了 78ms！因为头部阻塞）
    第三块：100ms（和第二块一起到的）
    第四块：102ms

  如果只用 WiFi 单路径：
    第一块：20ms
    第二块：40ms
    第三块：60ms
    第四块：80ms
    → 总完成时间：80ms，且延迟平稳
    
  多路径：
    总完成时间：102ms（反而慢了！）
    延迟不平稳（跳跃式）

根因：RTT 差异 + 顺序交付要求

如果两条路径 RTT 相同（如都是 20ms）：
  → 数据基本同时到达，没有阻塞
  → 多路径效果好

如果两条路径 RTT 差异大（20ms vs 100ms）：
  → 快路径数据等慢路径 → 浪费快路径优势
  → 可能不如只用快路径

"差异越大，阻塞越严重"

更难的是：RTT 会变化！
  某一刻 WiFi 20ms / 4G 100ms
  下一刻 WiFi 150ms (突发拥塞) / 4G 80ms
  你的调度策略必须快速适应

思路 1：只走快路径（退化为 MinRtt）
  - 阻塞为零
  - 但浪费了慢路径的带宽
  - 极端情况：快路径突然变差，切换延迟大

思路 2：冗余发送（Redundant）
  - 所有路径发相同数据
  - 谁先到用谁
  - 阻塞为零！
  - 但带宽利用率 = 1/N（N 条路径）
  - 适合小数据量（控制消息），不适合大带宽

思路 3：基于 RTT 差的加权调度
  - 如果 Path0 RTT=20ms, Path1 RTT=100ms
  - 给 Path0 分配 100/(20+100)=83% 的数据
  - 给 Path1 分配 20/(20+100)=17% 的数据
  - 让两条路径的数据"差不多同时到达"
  
  实现：
  fn calculate_weight(path: &Path, all_paths: &[&Path]) -> f64 {
      let total_inverse_rtt: f64 = all_paths.iter()
          .map(|p| 1.0 / p.rtt().as_secs_f64())
          .sum();
      let my_inverse_rtt = 1.0 / path.rtt().as_secs_f64();
      my_inverse_rtt / total_inverse_rtt
  }
  
  问题：RTT 估计有噪声，权重可能不准确

思路 4：接收端乱序容忍（Receive Buffer）
  - 允许接收端缓冲一定量的乱序数据
  - 设定一个"乱序容忍窗口"
  - 在窗口内的乱序不算阻塞
  - 但 QUIC 标准要求流内有序交付，这需要应用层配合

思路 5：预测性调度
  - 预测每个包在各路径上的到达时间
  - 选择能让接收端"按序到达"的分配方案
  - 需要准确的 RTT 预测 + 发送队列状态估计
  
  伪代码：
  fn predict_arrival(path: &Path, send_time: Instant) -> Instant {
      send_time + path.smoothed_rtt() + path.rtt_variance() * 2
  }
  
  fn schedule(data_chunks: &[Chunk], paths: &[Path]) -> Vec<(Chunk, PathId)> {
      // 动态规划：找到让最大到达时间差最小的分配方案
      // 这是一个优化问题！
  }

每条路径独立运行拥塞控制时，可能出现不公平：

场景：
  用户同时用 WiFi 和 4G
  WiFi 和邻居共享（100Mbps 总容量）
  4G 和其他用户共享

如果 TQUIC 的两条路径各自独立运行 CUBIC：
  WiFi 路径的 CUBIC：抢到 50Mbps（和邻居五五分）
  4G 路径的 CUBIC：抢到 30Mbps
  TQUIC 总带宽：80Mbps

但邻居只用了单路径 TCP：
  邻居的 TCP：50Mbps

问题：TQUIC 用户获得了 80Mbps，邻居只有 50Mbps
  → 不公平！TQUIC 在 WiFi 上抢了双份
  → 因为 TQUIC 同时在两个瓶颈链路上运行两个独立的 CC
  → 相当于一个人在两条队伍同时排队

Coupled Congestion Control (LIA / OLIA / BALIA)：

基本思想：
  多条路径的窗口增长要协调，保证：
  1. 总吞吐不低于最好的单路径
  2. 在共享瓶颈上不超过单路径 TCP 的份额
  3. 流量尽量往不拥塞的路径转移

LIA (Linked Increases Algorithm)：
  窗口增长公式：
  对每条路径 r，每收到一个 ACK：
    w_r += min(alpha/w_total, 1/w_r)
  
  其中 alpha = w_total * max_r(w_r/rtt_r^2) / (sum(w_r/rtt_r))^2
  
  直觉：
  - alpha 控制"总增长速度"
  - 当路径 r 的 RTT 最小时，它增长最快
  - 总增长速度等于单路径 TCP 在最好路径上的增长速度
  - → 保证公平性

OLIA (Opportunistic LIA)：
  改进：当某路径质量好时更积极使用，差时更保守
  → 更好的带宽利用率

BALIA (Balanced LIA)：
  再改进：在公平性和响应速度之间找平衡

RFC 6356 定义了这些算法的规范

TQUIC 当前状态：
  - 每路径独立 CC（可选 CUBIC/BBR/BBR3/COPA）
  - 没有实现 Coupled CC
  
为什么？
  1. Coupled CC 主要针对 CUBIC 设计，和 BBR 不兼容
  2. 腾讯的场景中 WiFi 和 4G 通常不共享瓶颈
     （WiFi 的瓶颈在无线链路，4G 的瓶颈在基站）
  3. 公平性在私有网络中不是首要问题

竞赛中的考虑：
  - 如果测试环境有共享瓶颈 → 需要考虑公平性
  - 如果测试环境无共享瓶颈 → 独立 CC 即可
  - 折中方案：基于 RTT 相似度检测共享瓶颈
    if path_a.rtt 和 path_b.rtt 高度相关 → 可能共享瓶颈 → 降低总窗口

调度器需要路径信息来做决策，但这些信息都有噪声：

1. RTT 估计
   - 只能测量"已发送包"的 RTT
   - 如果某路径很久没发包，RTT 信息过时
   - 突发拥塞可能让 RTT 突然变大 100 倍
   
2. 带宽估计
   - BBR 需要发送足够多数据才能探测带宽
   - 如果调度器不往某路径发数据，就测不到带宽
   - "不发 → 不知道带宽 → 不发" 恶性循环

3. 丢包率估计
   - 需要足够的样本量
   - 少量丢包可能是随机的，不代表路径变差
   - 多少丢包才算"显著"？统计学问题

4. 路径状态变化
   - WiFi 信号强度可能在 1 秒内剧烈变化
   - 4G 切基站时有短暂中断
   - 网络拥塞可能持续 10ms 也可能持续 10s

经典的"多臂老虎机"问题：

你有 N 台老虎机（N 条路径）：
  - 每台的中奖概率不同（路径质量不同）
  - 你不知道真实概率，只能通过拉来估计
  - 你想最大化总收益

纯利用（Exploit）：
  - 只用目前看起来最好的路径
  - 风险：如果估计不准，可能一直用次优路径
  - 风险：其他路径变好了你不知道

纯探索（Explore）：
  - 均匀往所有路径发数据
  - 好处：总能获得最新信息
  - 坏处：在差路径上浪费了很多数据

最优策略：在两者间平衡
  
  epsilon-greedy 策略：
    以 (1-epsilon) 概率用最好的路径
    以 epsilon 概率随机探索其他路径
    epsilon 随时间衰减（越来越确定后减少探索）

  UCB (Upper Confidence Bound) 策略：
    对每条路径计算"乐观估计"：
      score = 估计质量 + 探索奖励
      探索奖励 = sqrt(2 * ln(总次数) / 该路径使用次数)
    选 score 最高的路径
    
    效果：
    - 长时间没用的路径，探索奖励高 → 会被选中探索
    - 质量估计高的路径 → 大部分时候被选中
    - 自动平衡探索和利用！

  Thompson Sampling 策略：
    对每条路径维护质量的概率分布
    每次决策时从分布中采样
    选采样值最高的路径
    
    直觉：
    - 不确定性大的路径 → 采样值波动大 → 有时会被选中（探索）
    - 确定性高且质量好的路径 → 采样值稳定高 → 经常被选中（利用）

多路径导致接收端包乱序。但 QUIC 的丢包检测依赖包号顺序。

问题：
  发送端在两条路径上发送包 1-10：
    Path 0: 包 1, 3, 5, 7, 9  (RTT 20ms)
    Path 1: 包 2, 4, 6, 8, 10 (RTT 100ms)
  
  接收端在 T=20ms 收到: 1, 3, 5, 7, 9
  接收端发送 ACK: "收到了 1, 3, 5, 7, 9"
  
  发送端收到 ACK：
    "包 2, 4, 6, 8, 10 没被 ACK..."
    "包 9 已经 ACK 了，但 2, 4, 6, 8 还没..."
    "差距 > 3 → 判定为丢包！"
    → 触发不必要的重传！
    
  但实际上包 2, 4, 6, 8, 10 只是在慢路径上还在路上...
  T=100ms 时它们就到了。

这就是"虚假重传"(Spurious Retransmission)：
  - 浪费带宽（重传了没丢的包）
  - 干扰拥塞控制（错误地认为发生了丢包）
  - 降低了慢路径的拥塞窗口

方案 1：Per-path 包号空间
  
  每条路径用独立的包号序列：
    Path 0: 包号 P0-1, P0-2, P0-3, ...
    Path 1: 包号 P1-1, P1-2, P1-3, ...
  
  丢包检测也是每路径独立：
    Path 0 的 ACK 只判断 Path 0 的包是否丢
    Path 1 的 ACK 只判断 Path 1 的包是否丢
  
  → 不会因为跨路径乱序触发虚假重传！
  → 这是 Multipath QUIC draft 的设计

  TQUIC 的实现：
    每条路径有独立的 Recovery 状态
    包号空间按路径分离
    ACK 帧携带路径标识

方案 2：增大丢包检测阈值
  
  标准 QUIC：包号差 > 3 判定丢包
  多路径：可以把阈值设为 max(3, max_RTT_difference / min_RTT * expected_burst)
  
  → 容忍更大的乱序范围
  → 代价：真正丢包时检测更慢

方案 3：基于时间的丢包检测
  
  不看包号差，看时间差：
    if (now - packet_sent_time) > max(smoothed_rtt * 1.25, smoothed_rtt + 具体路径rtt变动)
        → 判定为丢包
  
  → 不受跨路径乱序影响
  → QUIC 本身也支持时间阈值丢包检测

移动端场景中路径状态频繁变化：

典型时间线：
  T=0s:    WiFi 强信号，4G 待机
  T=30s:   用户走出 WiFi 覆盖区
  T=31s:   WiFi 信号变弱，丢包率上升
  T=32s:   WiFi 断开
  T=33s:   4G 激活（从待机到活跃有 1-2s 延迟）
  T=35s:   4G 开始传输
  
  在 T=31-35s 这段时间：
  - WiFi 路径质量快速恶化
  - 4G 路径还没准备好
  - 存在 3-4s 的"空窗期"

挑战：
  1. 如何快速检测路径质量恶化？
  2. 如何在新路径还没验证时做决策？
  3. 如何在路径恢复时快速利用？

策略 1：心跳探测
  - 每隔 T 秒在每条路径上发送 PATH_CHALLENGE
  - 收到 PATH_RESPONSE → 路径存活
  - 超时未收到 → 路径可能故障
  
  trade-off：
  - T 太大：检测慢，故障响应延迟
  - T 太小：浪费带宽（特别是蜂窝网络有数据计费）

策略 2：被动检测
  - 如果某路径连续 N 个包没有收到 ACK → 怀疑路径故障
  - 如果 RTT 突然增大 K 倍 → 怀疑路径质量恶化
  - 不额外发探测包，利用正常流量判断
  
  问题：如果调度器不往某路径发数据，就无法被动检测

策略 3：自适应探测频率
  - 路径稳定时：低频探测（每 30s）
  - 路径不稳定时：高频探测（每 1s）
  - 检测到变化后：立即探测确认
  
  实现：
  fn next_probe_interval(path: &Path) -> Duration {
      match path.stability() {
          Stability::Stable => Duration::from_secs(30),
          Stability::Unstable => Duration::from_secs(1),
          Stability::Unknown => Duration::from_secs(5),
      }
  }

多路径接收端需要缓冲乱序数据，等待慢路径的数据到达。

问题：缓冲区多大合适？

缓冲区太小：
  快路径数据到了但缓冲区满 → 丢弃 → 重传 → 浪费
  
缓冲区太大：
  内存消耗过多
  延迟增加（数据在缓冲区等待排序的时间）
  
最优缓冲区大小和什么有关？
  - RTT 差异：差异越大，需要缓冲越多
  - 带宽：带宽越高，单位时间产生的乱序数据越多
  - 路径数量：路径越多，乱序越严重

公式（近似）：
  optimal_buffer = sum_of_all_paths(bandwidth_i * (max_RTT - RTT_i))
  
  例：
    Path 0: 100Mbps, RTT 20ms
    Path 1: 50Mbps, RTT 100ms
    max_RTT = 100ms
    
    Path 0 需要的缓冲 = 100Mbps * (100-20)ms = 100 * 80 / 8 = 1000 KB
    Path 1 需要的缓冲 = 50Mbps * (100-100)ms = 0
    总缓冲 = 1000 KB ≈ 1 MB
    
  这对移动设备可能是显著的内存开销！

策略 1：动态缓冲区
  - 根据实时 RTT 差异调整缓冲区大小
  - RTT 差异小 → 缩小缓冲区
  - RTT 差异突然变大 → 扩大缓冲区

策略 2：调度端缓解
  - 从根源减少乱序：调度器尽量让数据按序到达
  - 前面讨论的"基于 RTT 差的加权调度"
  - 缓冲区压力和调度策略是相互关联的

策略 3：流级别的路径亲和
  - 同一个流的数据尽量走同一条路径
  - 不同流可以走不同路径
  - → 流内有序，流间并行
  
  优点：零乱序（流内）
  缺点：不能在流级别利用多路径带宽聚合
  适合：多流并发的场景（如 HTTP/3 多个请求并行）

WiFi vs 蜂窝的能耗差异：

WiFi：
  - 发送/接收：~100mW
  - 空闲（已连接）：~10mW
  - 关闭：~0mW

蜂窝（4G/5G）：
  - 发送/接收：~1000mW（WiFi 的 10 倍！）
  - DRX 周期（省电模式）：~50mW
  - 从省电到激活：~500ms 延迟 + 能耗尖峰

含义：
  1. 如果数据量不大，可能不值得激活 4G
     → 激活 4G 的能耗 > 数据走 4G 节省的时间
  
  2. 4G 在后台保持连接也有基础能耗
     → 如果多路径总是保持 4G 活跃 → 电池消耗加快
  
  3. 需要"能量感知"的调度策略
     → 电量低时只用 WiFi
     → 电量充足时才启用多路径

另一个约束：蜂窝数据计费
  - WiFi 通常免费
  - 4G/5G 有月度流量限制
  - 调度器应该优先用 WiFi，4G 只在必要时使用
  
  策略：
  fn should_use_cellular(
      battery: f32,       // 0.0 - 1.0
      data_remaining: u64, // bytes of cellular quota
      urgency: f32,        // 0.0 - 1.0 (数据紧急程度)
  ) -> bool {
      battery > 0.3 && data_remaining > 10_000_000 && urgency > 0.7
  }

攻击场景 1：路径注入攻击
  
  攻击者伪造一条新路径（假装是另一个 IP）
  → 如果 TQUIC 不验证就使用 → 数据被劫持
  
  防御：PATH_CHALLENGE / PATH_RESPONSE 验证
  → 新路径必须通过验证才能使用
  → TQUIC 已实现

攻击场景 2：路径降级攻击
  
  攻击者在某条路径上故意制造丢包或延迟
  → 调度器把所有流量切到另一条路径
  → 另一条路径是攻击者控制的
  
  防御：
  - 不要完全放弃看起来"差"的路径
  - 保持最低限度的探测
  - 多路径本身就是冗余，不应完全依赖单路径

攻击场景 3：连接 ID 关联攻击
  
  多路径场景：同一连接在多条路径上有不同的 Connection ID
  → 如果能关联这些 CID → 可以追踪用户跨网络的移动
  
  防御：
  - 每条路径使用独立的 CID
  - CID 之间没有数学关联
  - 定期轮换 CID

输入信息：
  1. 每条路径的 RTT（smoothed + 最新 + 最小）
  2. 每条路径的估计带宽
  3. 每条路径的丢包率（短期 + 长期）
  4. 每条路径的拥塞窗口剩余空间
  5. 要发送数据的属性（大小、紧急程度、是否可乱序）
  6. 接收端缓冲区压力（通过反馈获知）
  7. 设备约束（电量、流量配额）

决策输出：
  - 选择哪条路径发送当前数据
  - 发送多少数据
  - 是否需要冗余发送

设计原则：
  1. 快速响应：路径质量变化后 < 1 RTT 内调整
  2. 稳定性：不能因为噪声频繁切换路径
  3. 探索：保持对所有路径质量的了解
  4. 公平性：不过度占用共享瓶颈的带宽
  5. 高效：调度决策本身不能成为瓶颈（< 1μs）

评价指标：
  - 总吞吐量（越高越好）
  - 完成时间（越短越好）
  - 延迟分布（P50, P95, P99）
  - 乱序程度（越低越好）
  - 虚假重传率（越低越好）
  - 公平性指数（越接近 1 越好）

2023-2025 年多路径调度的研究热点：

1. 基于强化学习的调度 (RL-based Scheduling)
   论文：[Peekaboo: Learning-based Multipath Scheduling]
   方法：Deep RL (PPO/SAC) 学习调度策略
   挑战：训练环境 vs 真实网络的 gap
   
2. 跨层优化 (Cross-layer Optimization)
   论文：[XLINK: QoE-Driven Multi-Path QUIC Transport]
   方法：结合应用层 QoE 指标（如视频卡顿率）做调度
   挑战：需要应用层信息穿透到传输层

3. 联合调度 + 拥塞控制
   论文：[MPCC: Online Learning Multipath Congestion Control]
   方法：把调度和 CC 统一为一个优化问题
   挑战：状态空间太大，难以收敛

4. 可解释调度 (Explainable Scheduling)
   方向：让调度决策可以被人类理解和调试
   方法：基于规则 + 参数可调（而不是黑箱神经网络）
   好处：部署信心更高

5. 多路径 QUIC 标准化进展
   IETF Draft: draft-ietf-quic-multipath
   状态：Active work item in QUIC WG
   关键争论：
   - 一个包号空间 vs 每路径独立包号空间
   - 哪些信号应该标准化 vs 留给实现