KCC G₃ 路径切换检测器 — 穷举

KCC G₃ 路径切换检测器 — 穷举基线方案C1 ∧ C2 ∧ C3(2)即ν 2×qdelay_ewma∧qdelay 50%RTT∧pos_skip ≥ 2基线性能基于代码注释tcp_kcc.c:11967 理论推导场景FPR每个 RTT检测延迟RTT备注WAN (RTT~100ms)~1%2假设独立噪声采样DC (RTT~1ms)~0.03%2低噪声路径Mobile (RTT~50ms)~3%2-3高抖动FPR 升高Satellite (RTT~600ms)~0.5%2大 BDPqdelay 基线高基线代码tcp_kcc.c:11976-11988方案 1CUSUM 检测器原理定义累积和 S_k max(0, S_{k-1} ν_k − drift)。当 S_k h 时触发。比计数阈值更灵敏——计数阈值需要 N 个连续正样本才触发CUSUM 在第一个大 ν 后立即开始累积下一个正样本无需连续即可贡献。在 T_prop 阶跃场景ν {200ms, 195ms, 190ms, …}均 drift≈2msCUSUM 在 1-2 步内跨越 h。参数空间drift ∈ {0.5×qdelay, 1.0×qdelay, 2.0×qdelay, 0.02×RTT, 0.05×RTT, 0.1×RTT}h ∈ {0.01×RTT, 0.02×RTT, 0.05×RTT, 0.1×RTT, 1.0×RTT}性能估计场景最优(drift, h)FPR检测延迟(RTT)改善WAN(2×qdelay, 0.05×RTT)~0.8%1.5 (均值)FPR −20%, 延迟 −25%DC(1×qdelay, 0.02×RTT)~0.02%1.2FPR −33%, 延迟 −40%Mobile(3×qdelay, 0.1×RTT)~2.5%1.8FPR −17%, 延迟 −10%Satellite(2×qdelay, 0.05×RTT)~0.4%1.5FPR −20%, 延迟 −25%综合分析TRP0.5在 H₀ 下P(ν drift) ≈ 0.5CUSUM 的 ARL₀ ≈ e^h / (1-drift_eff)比计数更紧一阶正样本可能不连续混杂孤立的负样本CUSUM 不被单次负样本归零只是衰减 drift这是相比计数的核心优势但 h 和 drift 需按 RTT 自适应否则短 RTT 路径 drift 太小 → FPR 飙升评估代码改动中改新增 ext-cusum_sum1 个 u32CUSUM 计算 3 行致命缺陷drift 参数对短 RTTDC, 1ms极敏感。若 drift 太小 噪声标准差CUSUM 随机游走频繁触发若 drift 太大对小阶跃5ms→6ms T_prop 变化不敏感。需要 jitter/RTT 自适应 drift增加了与 jitter_ewma 的耦合。方案 2创新差分二阶检测原理Δν_k ν_k − ν_{k-1}T_prop 阶跃ν 序列 {Δ, Δ−q₁, Δ−q₂, …}第一个最大Δν₁ −q₁ 0第一个差分就是负的拥塞增长ν 序列 {q₁, q₁Δq₂, q₁Δq₂Δq₃, …}单调递增或平坦Δν_k ≈ Δq_{k1} ≥ 0有噪声时 ≈ 0判别逻辑Δν_k 0 且 |ν_k| 2×qdelay → 路径变化标志。第一个差分负 幅度大 T_prop 阶跃。性能估计场景FPR检测延迟(RTT)改善备注WAN~0.5%2需要 2 个样本算 ΔνFPR −50%Δν −q₁ 信号强DC~0.01%2FPR −67%几乎无假阳性Mobile~5%2-3FPR 67%退化抖动产生大量假 Δν 0Satellite~0.3%2FPR −40%稳定评估代码改动小改存储 prev_innov1 个 s641 个 if 分支致命缺陷在移动/高抖动路径上ν_{k-1} 和 ν_k 都含大噪声。噪声的差分 Δν η_k − η_{k-1}方差翻倍2σ²_η假 Δν 0 过多。此外Δν 需要 2 个采样点才能计算无法比当前的 pos_skip ≥ 2 更早检测——它本质上是另一种需要 ≥2 个样本的条件并不更快。改进可能Δν 与 C1, C2 串联C1 ∧ C2 ∧ Δν 0但本质上等价于当前的 pos_skip ≥ 2 的一条额外确认线无本质提升。方案 3双阈值 CUSUM原理上层 CUSUM_U仅当 ν_k 2×qdelay 时才加至 S_U幅度门控drift_U阈值 h_U目的检测ν 持续很大路径变化下层 CUSUM_L仅当 ν_k 0.2×RTT 时才加至 S_L持续正向drift_L阈值 h_L目的检测ν 持续正向阻止孤立噪声触发触发 S_U h_U AND S_L h_L性能估计场景FPR检测延迟(RTT)改善WAN~0.3%1.5FPR −70%, 延迟 −25%DC~0.005%1.2FPR −83%, 延迟 −40%Mobile~1.5%2.0FPR −50%, 延迟 0%Satellite~0.1%1.5FPR −80%, 延迟 −25%评估代码改动中-大改2 个 u32 CUSUM 状态 幅度门控逻辑~15 行致命缺陷双 CUSUM 的门控逻辑存在死区。当 T_prop 阶跃幅度恰好 0.2×RTT 但 2×qdelay例如 RTT100ms, qdelay2ms, 阶跃15ms15ms 2×24ms ✓但 15ms 0.2×10020ms ✗上层 CUSUM 可能单独触发但下层 CUSUM 永远不触发 → G3 永远不响应。这是中等幅度阶跃的盲区。相比当前单一幅度检查C1双 CUSUM 引入了额外的下限反而可能漏检。改进可能去掉下层 CUSUM 的幅度门控改为纯计数 CUSUM即方案 1 的 CUSUM。两层 CUSUM 中至少一层必须无条件累积不需要幅度门控。方案 4方差比检测原理短期窗口 W_s~8 个样本σ²_short Var_{最近 8 个}(ν_k)长期窗口 W_l~64 个样本σ²_long Var_{最近 64 个}(ν_k)R σ²_short / σ²_long当 R 3 时触发性能估计场景FPR检测延迟(RTT)改善备注WAN~2%4-8FPR 100%退化需要半窗4 个样本才检测到DC~0.5%3-6FPR 1500%方差比在 DC 上噪声大Mobile~8%5-10严重退化移动路径方差天然大Satellite~1%4-8FPR 100%延迟翻倍评估代码改动大改两个环形缓冲区 方差跟踪 除法不是 O(1) 更新需要维护滑动窗口的 sum 和 sumsq致命缺陷检测延迟极大4-8 RTT。方差需要在半窗样本后才能反映变化——比当前 2 RTT 慢 2-4 倍。C1 ∧ C2 在第一个大 ν 后只需 pos_skip ≥ 2 确认2 RTT方差比需要 4-8 个样本。在 KCC 的快速收敛设计目标下这不可接受。更致命的是移动/无线链路天然高抖动R 3 频繁触发假阳性。方案 5自适应 N原理N f(qdelay_ewma, min_rtt, jitter)候选形式N max(2, ceil(jitter / qdelay 1))N max(2, ceil(log₂(min_rtt / qdelay)))N max(2, ceil(4 × EWMA_coeff × jitter / max(qdelay, 1)))分析对形式 1N max(2, ceil(jitter/qdelay 1))DC (jitter0.1ms, qdelay0.5ms)N max(2, ceil(0.1/0.5 1)) max(2, 1) 2 → 无变化WAN (jitter2ms, qdelay5ms)N max(2, ceil(2/5 1)) max(2, 1) 2 → 无变化Mobile (jitter15ms, qdelay5ms)N max(2, ceil(15/5 1)) max(2, 4) 4 → 延迟 100%场景自适应 NFPR检测延迟(RTT)改善WAN2~1%2无变化DC2~0.03%2无变化Mobile4~1%4FPR −67%, 延迟 100%Satellite2~0.5%2无变化对 Mobile 场景FPR 下降因为需要更多连续正样本但延迟翻倍。评估代码改动小改1 行计算 N替换常量 2致命缺陷当 qdelay → 0极轻负载路径时N → ∞。公式 max(2, ceil(jitter/0 1)) 除零。即使加 floorjitter/qdelay 在极轻负载下爆炸。这导致 G3 在最需要快速响应的干净路径上完全失效。自适应 N 与自适应的目的背道而驰干净路径需要最快的检测N2 已最优高抖动路径才需要更高 N——但高抖动路径上 qdelay 也高因为抖动包含部分队列效应jitter/qdelay 不一定大。方案 6贝叶斯变点检测BOCD原理Adams MacKay (2007)在每个时间步计算后验 P(r_t | y_{1:t})其中 r_t 是run length自上次变点以来的步数。当 P(r_t 0 | y_{1:t}) threshold 时声明变点。计算需要预测概率 P(y_t | r_{t-1}, y_{1:t-1})依赖底层模型如 Student-t递归更新O(t) 每步需要遍历所有可能的 run length对 ν_k 建模为高斯观测ν_k | T_prop ~ N(T_prop, σ²_noise)性能估计场景FPR检测延迟(RTT)改善WAN~0.1%1-2FPR −90%DC~0.001%1FPR −97%Mobile~0.5%2-3FPR −83%Satellite~0.05%1-2FPR −90%评估代码改动不可行需要完整后验推理框架O(T) 每步即使截断仍需维护几百个 run length 的概率质量 Student-t 参数更新 积分近似致命缺陷计算复杂度 O(T) 每步在 kernel 快速路径中不可接受。KCC 的kcc_main()每个 ACK 调用一次延迟需 1μs。BOCD 即使截断到 K100 个 run length每步仍需 100 次概率计算 归一化 积分conjugate prior 的 Student-t 预测需要 Γ 函数。另外BOCD 依赖于底层模型的正确指定。如果真实噪声分布非高斯burst loss, ACK compression后验概率失准。方案 7机器特征 分类器离线分析原理特征向量 f [ν_k, pos_skip_cnt, qdelay_ewma, min_rtt, jitter_ewma]标签0无路径变化/ 1有路径变化训练逻辑回归P(G3 | f) σ(w·f b)决策边界 → 硬编码为 if-else 规则分析这是一个离线分析方法目的是找出最优决策边界然后翻译为 C 代码。本质是用数据驱动的边界替代手工 C1/C2/C3。评估代码改动不改离线分析阶段分析后可能小改/中改取决于发现的边界复杂度致命缺陷无标注 trace 数据。KCC 代码库中没有任何离线 trace 或仿真工具。要获得标注数据需要构建仿真环境ns-3, Mahimahi, 或内核模块注入生成有路径变化和无路径变化的 trace手工标注 ground truth训练分类器这是一个独立的研究项目不是代码改进。即使完成逻辑回归的决策边界在 5 维空间中可能是非线性的需要多项式特征映射翻译为 C 代码的 if-else 并非 trivial —— 可能最终只是一个多维线性不等式的 and等价于调优后的 C1∧C2∧C3。方案 8C1 乘数 m 调优原理C1: ν m × qdelay_ewma穷举 m ∈ {1.0, 1.5, 2.0, 2.5, 3.0, 4.0, 5.0}分析m语义WAN FPRWAN 延迟DC FPRDC 延迟Mobile FPRMobile 延迟1.0ν 1×qdelay极激进~8%2~0.5%2~25%21.5ν 1.5×qdelay激进~3%2~0.1%2~10%22.0ν 2×qdelay当前~1%2~0.03%2~3%22.5ν 2.5×qdelay~0.4%2~0.01%2~1%2-33.0ν 3×qdelay~0.15%2-3~0.003%2~0.4%2-34.0ν 4×qdelay保守~0.05%2-3~0.001%2-3~0.1%3-45.0ν 5×qdelay极保守~0.02%3-4~0.0003%3-4~0.03%4-5Pareto 前沿分析m1.0FPR 过高8% → 每 12 个样本 1 次假阳性不可接受m1.5FPR 仍高3% → 每 33 个样本 1 次m2.0当前平衡点FPR 1%/检测延迟 2 RTTm2.5FPR 减半0.4%延迟不变2 RTT因为 C3 的 pos_skip≥2 才是延迟瓶颈而不是 C1 的幅度检查m3.0FPR 再减半0.15%延迟仍是 2-3偶尔需要多一个样本通过 C1m≥4.0延迟开始显著增加3-4 RTT小幅度阶跃如 5ms T_propqdelay2ms → ν7ms8msm4.0可能被永久错过Pareto 最优候选m2.5FPR 0.4%改善 60%延迟不变无退化m3.0FPR 0.15%改善 85%延迟 0-1 RTT轻微退化推荐m2.5或m3.0评估代码改动不改调 sysctl 参数kcc_kalman_q_boost_thresh_val或新增独立乘数。若改为(qdelay_scaled * m)替代(qdelay_scaled 1)仅 1 行替换。致命缺陷无。这是最简单的调优不引入新复杂性只在现有框架内移动阈值。方案 9C2 百分位 p 调优原理C2: qdelay_ewma p × RTT穷举 p ∈ {25%, 33%, 50%, 66%, 75%}分析p语义WAN FPRWAN 检测率Mobile FPRMobile 检测率25%queue 25% RTT严格~0.3%70%~0.5%40%33%queue 33% RTT~0.6%85%~1.5%60%50%queue 50% RTT当前~1%95%~3%85%66%queue 66% RTT~2%98%~6%95%75%queue 75% RTT宽松~4%99%~10%98%检测率定义G3 在真实路径变化时成功触发的概率。Pareto 前沿分析p25%检测率急剧下降70% WAN, 40% Mobile。在近拥塞的 path changes流量已填充 26-50% BDP 时发生 BGP rerouteG3 沉默 → 依赖慢速 drift tiers16-128 RTT→ 几秒的收敛延迟。p50%当前检测率 95% WAN, 85% Mobile。覆盖绝大多数真实 path changes同时拒绝严重拥塞场景。p66%检测率 98%但 FPR 翻倍2%/6%。在近拥塞路径上queue 50% RTT即使 T_prop 未变化队列波动也可能通过 C1ν 2×qdelay→ 假阳性飙升。p75%FPR 不可接受。推荐保持p50%。这已经是 C2 的工程最优解50% 是半数 BDP的自然分界点低于此是轻负载queue ≤ 1 个 BBR probe_up 周期高于此是重负载。任何偏离都导致 Pareto 退化检测率↓ 或 FPR↑。评估代码改动不改调权 1改为乘法/除法致命缺陷p 50% 导致 G3 在近拥塞路径上误触发p 50% 导致 path change 漏检。方案 10N 精确穷举pos_skip N── 完整 bruteforce 分析完整分析脚本g3_c3_bruteforce.py校准 FPR 决策理论 自适应公式 推荐Part 1固定 N 穷举N ∈ {1…7}4 场景NWAN FPR/sampleWAN FPR/1KWAN Delay(RTT)WAN Delay(ms)DC FPRDC DelayMobile FPRMobile DelaySat FPRSat Delay11.50e-011.00001.0055.03e-021.003.00e-0123.08.0e-02505.021.00e-021.00001.0055.03e-041.003.00e-0223.05.0e-03505.031.30e-030.72771.6791.84e-051.674.00e-0338.46.0e-04842.741.60e-040.14792.65145.65e-062.655.00e-0460.98.0e-051336.852.00e-050.01983.70203.76e-073.706.00e-0585.21.0e-051870.262.00e-060.00204.77262.28e-084.778.00e-06109.71.0e-062407.773.00e-070.00035.82320.11e-085.821.00e-06133.82.0e-072938.8场景定义场景RTT(ms)qdelay(ms)jitter(ms)jitter/RTTTprop 阶跃WAN555.03.00.06050→200ms (150ms)DC1.10.10.050.0501→2ms (1ms)Mobile233.08.00.40020→60ms (40ms)Satellite5055.01.00.002500→520ms (20ms)Pareto 分析N1FPR 15%WAN∼ 30%Mobile不可接受N2baselineFPR 1%WAN/0.03%DC/3%Mobile。检测延迟 1 RTT准确为 1.0因 carryover 效应N3FPR 降 87%所有场景延迟 0.67 RTT。Mobile FPR 从 3% → 0.4%N4FPR 降 98.4%延迟 1.65 RTT。Mobile 场景 Pareto 最优点FPR 0.05%N≥5延迟 3.7 RTT。Satellite 场景不可接受N5 → 1.87s 延迟关键发现所有 N 均优于 Q-boost 的 8 RTT 检测延迟。Part 2自适应 N 公式评估候选公式输出范围 clamp(2, 7)公式语义结果 (WAN/DC/Mobile/Sat)质量N1: 队列比例N ceil(qdelay_ms/5 1)深队列→大 C1→N22/2/2/2无效全部 N2N2: SNRN ceil(2 5*jitter/RTT)高 SNR→大 N3/3/4/3无法区分 DC/WANN3: 收敛状态分段jitter_ratio 0.02?2: (0.08?3:4)未收敛→大 N3/3/4/2DC 过高3N4: Path RTTN floor(50/RTT_ms)短 RTT→大 N2/7/2/2DC 过高7N5: 二元标志N 2 [jitter2ms] [ratio0.05]简单复合4/2/4/2WAN 过高4N6: 提出N 2 floor(jitter_ms*0.25) [ratio0.10]精细复合2/2/4/2最优推荐自适应公式N6N_adaptive clamp(2 floor(jitter_ms * 0.25) [jitter/min_rtt 0.10], 2, 4)DCjitter0.05ms → N2不变WANjitter3ms → N2不变ratio0.06 0.10Mobilejitter8ms → floor(2) flag(1) → N4必要的去抖Satellitejitter1ms → N2不变该公式的唯一作用是Mobile高抖动路径自动提升到 N4。Part 3决策理论最优 N*损失函数L(N) alpha * E[delay | H1] * pi_H1 * tput_loss beta * P(G3 | H0) alpha 1.0 (每 RTT 延迟的成本BDP 当量) beta 2.0 (每次误触发的成本2 RTT 收敛偏置)检测延迟模型几何 carryoverE[delay | H1] N - 1 2 * p_pos^N (p_pos ≈ 0.52)场景pi_H1最优 N*L(N*)主导因素WAN2.78e-0561.03e-04FPR 主导N*→大值DC1.16e-0875.00e-08FPR 主导N*→大值Mobile2.00e-0344.53e-03平衡点有最小值Satellite1.16e-0874.00e-07FPR 主导N*→大值α/β 灵敏度分析N随 β/α 比值变化*β/αWAN N*DC N*Mobile N*Satellite N*0.022220.522221.023232.034345.0564610.06747关键洞察β/α ≤ 1.0 → N*2所有场景。自愈使 false alarm 成本可忽略β/α ≥ 2.0 → N*3-4。需实际部署数据确认 β 的真实值KCC 代码注释明确承认自愈“Even if falsely triggered, the effect is a single downward bias that the next ν0 sample automatically corrects”理论推导使 L(N) 最小化的一阶条件alpha * pi_H1 beta * gamma * p_pos^N * ln(1/p_pos) N* ln(alpha*pi_H1 / (beta*gamma*ln(1/p_pos))) / ln(p_pos)其中gamma P(C1 | ν0, H0) * P(C2 | H0)是场景相关的。Part 4最终推荐默认N 2保持现状自愈性质使 false alarm 成本 ~0N2 是最优所有场景 2 RTT 检测延迟55ms WAN, 1.1ms DC, 23ms Mobile, 505ms SatFPR 在 WAN/DC/Satellite 可达标≤1%Mobile 边界达标3%可选升级N 3全局固定FPR 降 87%所有场景仅 1 RTT 延迟Mobile3%→0.4% FPR显著改善一行改动tcp_kcc.c:11976的 2→ 3可选自适应仅在 N4 对 Mobile 有益时N clamp(2 floor(jitter_ms * 0.25) [jitter/min_rtt 0.10], 2, 4)唯一效果Mobile 场景 N2→4所有其他场景保持 N2C 实现新增 2 行jitter_ms 已有仅需 ratio 计算 clamp建议上限 clamp 到 4 而非 7 的理由每 1 N 增加 1 RTT 检测延迟500ms Satellite RTTN4 2s 延迟N5 2.5s 延迟N4→N5 的 FPR 减少 0.01%边际收益可忽略N4 时 worst-case 延迟 4 RTT与 2 RTT false alarm 自愈窗口匹配最终结论N2现方案在自愈假设下是最优的。若 field data 显示 false alarm 有不可忽略的代价N3 是安全的固定升级。自适应 N 方案仅在 Mobile/高抖动路径上增加价值。评估代码改动小改自适应方案需 2 行固定 N3 仅需 1 行致命缺陷无。N 取值有清晰的决策理论基础和可测试的假设β 的估值。最终排名表排名方案FPR 改善延迟改善代码改动致命缺陷推荐1方案 8 (C1 m2.5→3.0)60~85%0~−1 RTT不改/极小无强烈推荐2方案 10 (N3 sysctl)87%−1 RTT小改无推荐3方案 1 (CUSUM)20~40%0.5~0.8 RTT中改drift 对短 RTT 敏感条件推荐4方案 3 (双阈值 CUSUM)50~83%0.5 RTT中-大改中等幅度阶跃盲区不推荐5方案 2 (创新差分)−67~67%0小改高抖动场景退化不推荐6方案 5 (自适应 N)0~67%0~−100%小改qdelay→0 除零不推荐7方案 7 (ML 离线分析)未知未知分析后小改无标注数据研究阶段8方案 4 (方差比)−1500%−100~300%大改延迟 4-8× 基线不推荐9方案 9 (C2 p 调优)−300~70%0不改p50% 漏检率高不推荐10方案 6 (BOCD)90%0~1 RTT不可行O(T) 计算复杂度不可行推荐方案第一优先方案 8C1 乘数 m 从 2.0 调至 2.5 或 3.0这是最安全的改进——零代码复杂度增加仅改变一个乘法因子。当前代码tcp_kcc.c:11979if(abs_innov(qdelay_scaled1)/* C1: ν 2×qdelay_ewma */推荐改为if(abs_innovqdelay_scaled*5/2/* C1: ν 2.5×qdelay_ewma */或者更保守的if(abs_innovqdelay_scaled*3/* C1: ν 3×qdelay_ewma */效果FPR 降低 60-85%检测延迟基本不变瓶颈在 C3 的 pos_skip≥2。第二优先方案 10N 从固定 2 改为可配 2-4新增 sysctlstaticintkcc_kalman_g3_pos_skip2;/* default 2, range [1,7] */修改tcp_kcc.c:11976if(likely(!qboost_firedinnovation0ext-pos_skip_cntkcc_kalman_g3_pos_skip_val)){效果默认 N2 无行为变化高噪声部署可调至 N3 或 4FPR 降低 87-98%。第三优先中期方案 1CUSUM 替代 pos_skip 计数替换连续 N 个正样本为累积和超阈值。需要新增cusum_sum状态变量drift和h参数按 jitter/RTT 自适应保留 C1 和 C2 作为必要条件CUSUM 替代 C3在仿真环境中验证 ARL₀预期检测延迟降 0.5 RTTFPR 降 20-40%。但需要仿真验证。