ISS 间歇更新稳定性证明 — 穷举收紧路径

ISS 间歇更新稳定性证明 — 穷举收紧路径

基线:

• γ_window = (1 − K_min)^(1/26) = 0.784^(1/26) ≈0.9905
• κ ≈ 26·max(K_ss·η_max, w_max) / |d_k| (保守界 ≈234.7)
• K_min = (p_floor+Q)/(p_floor+Q+R) = 110/510 ≈0.216
• 最坏窗口: 25 次连续拒绝 + 1 次强制接受 → 26 步窗口

关键参数速查:

1. Markov 链分析 — P_est 稳态分布

思路:
拒绝序列 {连续拒绝次数} 在 i.i.d. 假设下服从几何分布：P(reject streak > n) = P_rejⁿ。
在 p_accept = 0.3 时，P(reject streak ≥ 26) = 0.71²⁶ ≈ 1.8×10⁻⁴（极小概率）。
p_est 的随机游走服从：

• 拒绝轮次: p_{k+1} = p_k + Q (线性增长)
• 接受轮次: p_{k+1} = p_k·R/(p_k+R) + Q (收缩)

稳态分布:
p_est 的稳态分布不是固定点的退化分布，而是马尔可夫链的平稳分布 π§。
从平稳分布取 99% 分位数 p_est^(99%) 作为实际 K_min 的计算基础，
替代最坏情况 K_floor (p_est→10 极端罕见)。

结论:

• 更紧的 γ:在 p_accept=0.3 时，p_est 的 99% 分位数远高于 p_floor=10
  • 典型稳态 p_est ≈ 33 (收敛阈值处 K≈0.25)
  • 此时 K_eff ≈ 0.25，γ_per_step = 1 − 0.25 = 0.75
  • 对 26 步窗口: γ_window = 0.75^(1/26) ≈0.9890（小幅改善）
  • 若用实际 p_accept≥0.3 → 拒绝概率 P_rej≈0.7，平均拒绝步数 = 1/(1-P_rej) ≈ 3.3
  • 对平均窗口而非最坏窗口 → γ_avg = 0.75^(1/3.3) ≈0.912（显著改善）
• 需要的额外假设:拒绝过程 i.i.d.；存在平稳分布；稳态已达成
• 致命缺陷:边界值分析（最坏情况）被替换为分布分析（典型情况），这不修改 ISS 的最坏情况保证，只提供了"概率 ISS"的替代——这是语义变更而非收紧。实际的最坏情况路径依然存在（无限长时间内随着 t→∞ 必发生）。

2. 概率 ISS (p-ISS)

思路:
标准 ISS: ∀ω, ∀k, |d_k| ≤ β(|d_0|, k) + γ(‖ω‖)。放宽为：
P(|d_k| > β(|d_0|, k) + γ(δ)(‖ω‖)) ≤ δ
即以概率 ≥ 1−δ 成立，允许低概率违反。

计算:
在 i.i.d. 拒绝假设下，拒绝序列长度 L 服从几何分布。
P(L ≥ n) = P_rejⁿ。给定 δ = 10⁻⁶：

• n(δ) = ln(δ)/ln(P_rej) = ln(10⁻⁶)/ln(0.71) ≈ −13.82/(−0.342) ≈ 40.4
• 即 99.9999% 概率下拒绝序列 ≤ 40 步，而非 26 步
• 但用 99% 分位数（δ=0.01）: n=ln(0.01)/ln(0.71) ≈ 13.5 步
• 用 n=13 替代 26 → γ(0.01) = (1−0.216)^(1/13) =0.9808
• 用 n=6 (p=0.5 时): γ(0.01) = 0.784^(1/6) =0.9603

在各种 δ 下的结果:

| δ (置信度) | 窗口 n | γ(δ) | κ(δ) (≈n·K_ss·η_max/|d_k|) |
|-----------|--------|------|------|
| 10⁻² (99%) | 13 | 0.9808 | 117 |
| 10⁻⁴ (99.99%) | 27 | 0.9911 | 243 |
| 10⁻⁶ (99.9999%) | 40 | 0.9940 | 360 |
| 最坏情况 (确定性) | 25+1=26 | 0.9905 | 234.7 |

结论:

• 更紧的 γ:在 δ=0.01 时 γ≈0.98（vs 0.9905）；在 δ=10⁻³ 时 γ≈0.985
• 需要的额外假设:拒绝序列 i.i.d.；过程遍历性；拒绝概率 P_rej < 1
• 致命缺陷:(a)p-ISS 不是标准 ISS —— 控制理论中 ISS 是确定性界，转为概率界削弱了稳定性保证。对于拥塞控制，"99% 概率不会爆炸"意味着每个流每 100 个 RTT 约有一次可能队列溢出——不可接受。(b)实际拒绝过程非 i.i.d.（门控条件依赖状态 d_k，存在正自相关）。©长拒绝序列有系统性原因（持续队列），此时假设失效。

3. Q-boost + 漂移联合增益

思路:
当前分析将 Q-boost 和漂移当作"安全网"（只在 26 步窗口末端使用一次）。
能否将它们整合到主证明路径中？

Q-boost (K_eff ≈ 0.73):
触发条件: |ν_k| > q_boost_thresh (≈4ms) 且 p_est ≤ converged (500)。
发生频率: 仅在路径变化时触发。稳态不触发。

漂移修正 (K_eff ≈ 0.1，Tier 1/2):
触发条件: 连续 16/128 次正创新。
平均 K_eff drift = 0.0975（Tier 1）或 0.0488（Tier 2）每轮。

联合平均增益计算:
在每个 26 步窗口内，考虑三种操作模式的平均增益：

• 正常接受（p_accept ≈ 0.3）: K_eff = K_ss = 0.39
• 正常拒绝（p_reject ≈ 0.7）: K_eff = 0
• 强制接受（第 26 步）: K_eff = K_min = 0.216
• Q-boost: K_eff = 0.73（偶发，占比 ≈ 10⁻⁴）
• 漂移: K_eff = 0.1（P(触发) ≈ (1/2)¹⁶ = 1.5×10⁻⁵，Tier 1）

加权平均增益: K̄_eff = 0.3×0.39 + 0.7×0 + ~10⁻⁴×0.73 + ~10⁻⁵×0.1 ≈0.117

但这忽略了 Q-boost/漂移在最坏情况下的正贡献。用更精确的方法：
在 26 步窗口内，至少有一次强制接受和可能的 Q-boost/漂移修正。计算每步平均增益：

K̄_window = [K_accept × n_accept + 0 × n_reject + K_force]/26

取 p_accept = 0.3, n_accept ≈ 8, n_reject = 17, K_min = 0.216:
K̄_window = (8×0.39 + 17×0 + 0.216)/26 = 3.336/26 ≈0.128

若含 Q-boost（概率触发，有效增益 ≈平均每窗口贡献一次 0.73×1）:
K̄_window = (3.336 + 0.73×P(Q-boost|window))/26 ≈ 0.128 + 0.028(极低) ≈0.128

结论:

• 更紧的 γ:γ_eff_per_step = 1 − K̄_window = 0.872; γ_eff_26 = 0.872^(1/26) ≈0.9945（​​反而更松！）
  • 等等——这是算术平均的错误用法。实际增益来自每步收缩因子 (1−K_k) 的乘积：
  • Π(1−K_k) ≤ (1−K_min)^(n_rej+1) · (1−K_ss)^(n_accept) ≤ (1−0.216)²⁶
  • 即使有 8 步 K_ss=0.39，乘积下限依然由最坏步决定
  • 关键洞察:乘积下界由最远的拒绝序列决定。如果 Q-boost 打断拒绝序列，窗口有效长度从 26 缩减：
    • 如果 Q-boost 在 10 步后触发: 窗口 = 10+1 = 11
    • γ_window = 0.784^(1/11) =0.978
  • 如果漂移在 16 步后修正: γ_window = 0.784^(1/17) =0.985
• 需要的额外假设:Q-boost 或漂移准时触发打断长拒绝序列
• 致命缺陷:Q-boost/漂移的触发不是确定性的——它们依赖创新幅度阈值或极长的正创新序列（16/128 步）。在最坏情况路径（持续微小正偏置队列），Q-boost 可能永不触发，漂移仅在 128 步后触发（比 26 步更长！）。Q-boost + 漂移不能用来加强最坏情况界。

4. 切换 Lyapunov 函数

思路:
接受和拒绝模式使用不同的 Lyapunov 函数：

• 接受时 (i_k = 1): V_acc(d) = d², ΔV_acc ≤ −α_acc·V + σ_acc·‖η‖²
• 拒绝时 (i_k = 0): V_rej(d) = |d|, ΔV_rej = 0 (因为 |d_{k+1}| = |d_k|)

交替使用多 Lyapunov 函数，计算平均衰减率。

分析:
对于接受步: ΔV_acc ≤ −(2K−K²)·V_acc + K²·‖η‖²（标准 ISS-Lyapunov）
对于拒绝步: V_rej(d) = |d| 不增长，ΔV_rej = 0

在 26 步窗口内（25 拒绝 + 1 强制接受）:

• 接受步: V_acc((1−K)d) = (1−K)²·V_acc(d)
• 拒绝步: |d| 不变

多 Lyapunov 函数的平均衰减（加权平均）:
α̂ = (α_acc×n_acc + 0×n_rej) / (n_acc + n_rej)
在 26 步窗口: α̂ = α_acc/26 = 0.39/26 ≈ 0.015
γ_avg = 1 − α̂ =0.985

结论:

• 更紧的 γ:γ_avg ≈ 0.985（比 0.9905 稍紧）
• 需要的额外假设:多 Lyapunov 函数满足 Liberzon 切换系统理论的公共 Lyapunov 衰减条件；切换信号满足平均驻留时间约束
• 致命缺陷:(a)这只收紧 5% 的相对间距。(b)多 Lyapunov 分析仍需要证明 V 在每个模式切换时不增长（满足：d 在拒绝时不变化，在强制接受后最多收缩）。©最终界仍然是 |d_k| 对最大‖η‖ 的比例——收紧的是 transient 速率而非 asymptotic 增益 κ。γ 收紧但 κ 不变，整体 ISS 界基本不变。

5. 利用实际 p_accept ≫ 1/26

思路:
当前最坏情况分析假设每 26 步才有一次更新（p_accept → 1/26 ≈ 0.038）。
实际中 Lemma Q.2 保证 PROBE_BW 每周期有一条清空样本 → p_accept ≥ 1/8 ≈ 0.125（下界）
但在 DRAIN 和 CRUISE 阶段，实际 p_accept ≫ 0.125，因为：

• DRAIN: 队列单调递减 → 正创新逐渐被拒绝，但部分样本 ν_k < 0
• CRUISE: 队列近乎零 → p_accept ≈ 0.5（对称噪声下 50% 负创新）
• 总体 p_accept ≈ 0.3 是可实现的

重新计算:
使用 Lemma Q.2 的确定性保证：每 8 步周期至少 1 步干净样本。
对 ISS 分析，使用 p_accept_min = 1/8（有证明的确定性下界）替代 p_accept_worst = 1/26（随机变数的上界）。

max_consec_reject = 25 是一个 safety valve，而非正则操作点：

• 名义操作：拒绝序列中位数 = 1/P_rej = 1/0.7 ≈ 1.4 步
• 99% 分位数拒绝序列：ln(0.01)/ln(0.71) ≈ 13.5 步
• 强制接受仅作用于 >99% 分位数的尾部分布

有效操作 γ:

结论:

• 更紧的 γ:γ_effective(Q.2) = 0.784^(1/8) ≈0.9695（有证明的确定性下界）
• 需要的额外假设:Lemma Q.2 的完整证明（每 PROBE_BW 周期至少一个干净样本）。这依赖于 DRAIN 的单调性保证（已证明）和 cycle-length 封闭性（8 步）。注意这个假设已经被 KCC README 的 §Q.2 证明。
• 致命缺陷:(a)仅当 DRAIN 未被 drain-skip 跳过时成立。在 drain-skip 时，残存队列 bounded by clean_thresh (≤10% BDP) 但非零——清空样本的保证弱化为"门控后非队列样本"。(b)在最坏情况（持续高利用率，队列从不完全清空），Lemma Q.2 的 “q→0” 结论需要 ≥ 2.6× margin of DRAIN time vs queue-full drain time，在最坏情况下 BDP 满载时仍成立，但窗口为 8 而非 26 要求更强的物理假设。©未改变 κ 的界——κ 仍由 η_max 和 w_max 决定。

6. 自适应 γ(t) — Q/R 时变分析

思路:
K_ss = p_ss/(p_ss+R) 的非线性 Riccati 解依赖于 Q 和 R 的实际值：

• Q 自适应: Q_eff = max(q_min_factor×Q_nominal, min(Q_nominal, Q_max_auto))，在路径变化时 Q-boost 提升至 ~2500
• R 自适应: R_eff = R_nominal + R_boost，其中 R_boost 依赖于 jitter_ewma
• 稳态 K_ss 随噪声环境动态变化

时变 γ(t) 的推导:

平均 γ (在 PROBE_BW 周期内):
8 步周期内各相位的 K_k 不同：

• PROBE (1 RTT): 队列增长 → 门控关闭 → γ₃=0（不接受）
• DRAIN (1-4 RTTs): 队列排出 → 门控逐步打开 → K_k 从 0 到 K_ss
• CRUISE (6 RTTs): 正常操作 → γ_per_step = 1−K_ss = 0.61
• 周期平均: γ̄_per_step = [1×1 + (1_4)×0.7 + 6×0.61] / 8 ≈ (1+2.1+3.66)/8 ≈ 0.845

关键发现:
平均每步 γ ≈ 0.845 << 0.9905（最坏窗口界）。这比最坏情况界紧 ~22 倍（在对数空间中）。

结论:

• 更紧的 γ:γ̄_adaptive ≈0.845（平均每 RTT），约 300 倍快于 0.9905 隐含的衰减率
  • 注：按 26 步窗口折算: 0.845^(1/26) ≈0.9935—— 对窗口界收紧不大
  • 真正的收紧在 per-step 衰减: (1−0.845)²⁶ → 但 step 间的 26 步分离性问题在于拒绝序列
• 需要的额外假设:系统大部分时间在 CRUISE 模式（6/8 周期占比）；Q-boost 在路径变化时生效
• 致命缺陷:(a)时变 γ(t) 不能替代最坏情况界——如果系统恰好处于长期噪声状态（p_accept 低），实际 γ(t) 可能高于平均。(b)长期平均 γ 的推导依赖遍历性，不构成最坏情况证明。©如果噪声持续高水平，R 升高 → K_ss 降低 → γ 增加，自适应可能朝更差方向演化（一个自适应系统可能趋向更低 K_ss 的稳态，即最坏情况恰在稳态）。

7. 比较 KCC ISS 与标准 KF ISS — 方向门的最优性下界

思路:
标准 KF (所有样本更新): γ_KF = 1 − K_ss ≈ 0.61，per-step 衰减很快。
KCC (间歇更新): γ_window ≈ 0.9905，per-step 衰减约为标准 KF 的 1/16。
证明在"队列无偏"约束下，任何门控方案都不可能使 γ < 某个下界。

分析:
设方向门在 p_clean 比例的样本上打开。最坏情况是持续队列时的接受样本数。
任何门控方案必须满足：

• 对于 T_queue > 0 的样本不执行更新（定向性约束）
• 在 p_clean 比例的干净样本上执行更新

如果在 K_clean 个干净样本上 K_eff = K_ss，在 (1 − p_clean) 比例上 K_eff = 0：
per-step 衰减率 = p_clean·K_ss (asymptotic)
γ_gated ≥ (1 − p_clean·K_ss)

下界推导:
给定物理约束 p_clean ∈ (0, 0.5] (在一般互联网路径上 <50% 概率遭遇非空队列)：
γ_lower_bound = (1 − p_clean·K_ss) = 1 − p_clean·0.39 = ≥ 1 − 0.5×0.39 =0.805

如果每 26 步才一次更新（最坏操作）：
γ_lower_bound_26 = (1 − 0.39)^(1/26) 的极端情况

但对于一般间歇更新方案，使用 average-case 分析：
令 p_accept = p_clean·1/2（干净样本中 50% 为负创新）
γ_theoretical = (1 − p_clean·K_ss/2)
取 p_clean ∈ [0.1, 0.5]: γ ∈ [0.981, 0.903]

对 KCC 的重新诠释:
γ_window = 0.9905 不是"弱点"，而是在给定的"方向门 + 无偏性约束 + 最坏情况队列"下的近似最优。
相比无条件门控（所有样本都更新 → 偏置 T_prop 估计 → 不安全），KCC 接受了更慢的收敛速率以换取无偏性。

结论:

• 更紧的 γ (重新定义):不是在绝对值上更紧，而是在约束条件下的最优性证明。在"队列无法影响 T_prop 估计"的约束下，任何门控方案的 γ 下界约为 0.95-0.99
• 需要的额外假设:形式化"方向门最优性"的证明框架；队列-干净样本率的全局下界
• 致命缺陷:(a)这是一个"重新定义"（从弱点→最优可达），而非数值收紧。控制理论界仍会看 γ = 0.9905 并问"为何这么差"。(b)证明最优性需要建立所有可能门控方案的博弈论下界——范围广且不平凡。©如果加入"智能门控"（不只 ν≤0 而是更多条件），γ 确实可以更低，但这冒着丢失无偏性约束的风险。

8. 经验验证 — Trace 数据分析

思路:
使用 KCC 的 trace 数据计算实际经验衰减率 γ_empirical。

方法:
从实际运行的 KCC trace 中收集 {|d_k|} 序列（d_k = x̂_k − T_prop）。在连续的 26 步窗口内拟合:
|d_{k+26}| ≤ γ_emp·|d_k| + κ_emp

理论预期值:

在最坏情况 trace 中，如果 γ_emp 出现在哪个区间，表明实际界比理论界紧多少。

需要的数据:

• x_est(Kalman T_prop 估计)
• min_rtt_us(真实 T_prop 的替代测量)
• consec_reject_cnt(每一步的拒绝状态)
• p_est(估计误差协方差)
  这些数据可通过 KCC 的内核 tracepoint 获得。

结论:

• 更紧的 γ:经验 γ 预期在0.75-0.95范围，远低于 0.9905
• 需要的额外假设:可获取足够的真实网络 trace 数据；d_k 的 ground truth 可从 min_rtt 或外部测量获得
• 致命缺陷:(a)经验验证不能替代数学证明——它只能显示"在实际 trace 中没有出现 0.9905"，不能证明"永远不可能出现"。(b)需要大量多样性 trace（卫星、数据中心、WiFi、固定光纤）来建立统计置信度。©如果实际发现 γ→0.99+ 的 trace，会削弱而非加强 ISS 论点。

最终排名表

最终推荐：2 条最佳收紧路径

路径 A（确定性，主要证明路径）: 基于 Lemma Q.2 的 p_accept 下界

现状: γ_window = (1 − K_min)^(1/26) ≈ 0.9905 (p_accept ≈ 0.038) 收紧: γ_window = (1 − K_min)^(1/8) ≈ 0.9695 (p_accept ≈ 0.125)

证明骨架:

1. Lemma Q.2 证明每 PROBE_BW 周期至少有一个干净样本 (p_accept ≥ 1/8 确定性)
2. 最坏情况不是 26 步拒绝窗口，而是 8 步（因为每周期必有一个接受）
3. 在 8 步窗口内: |d_{k+8}| ≤ (1−K_min)·|d_k| + 8·max(K_ss·η_max, w_max)
4. γ = 0.784^(1/8) = 0.9695 (从 0.9905 降低约 2.1%)
5. κ ≈ 8·max(K_ss·η_max, w_max) / |d_k| (从 234.7 降低约 70% — 主要改善！)

需要证明/修改:

• Lemma Q.2 的证明必须包含 drain-skip 场景
• 需要确定在 drain-skip 操作下，残存队列是否 invalid 干净样本的性质
• p_accept 下界从 1/8 收紧到 2/8 = 1/4，如果 DRAIN+CRUISE 都产生干净样本

路径 B（工程层面，概率性）: 操作 p_accept + Markov 稳态分析

现状: 使用最坏 p_est=10 计算 K_min=0.216 改进: 使用稳态 99% 分位 p_est ≈ 33 计算 K_eff=0.25，窗口 8（路径 A）

合并效果:

• γ_merged = (1 − 0.25)^(1/8) = 0.75^(1/8) ≈0.9647(vs 0.9905)
• κ_merged ≈ 8·0.25·η_max / |d_k| ≈ 原 κ 的 0.25/0.216 × 8/26 ≈0.31×(减小 ~69%)
• 收敛速度 (1−γ): 0.0353 (每步) vs 0.0095 →3.7× 加速

限定条件 (路径 B):

• 对最坏情况路径，仍退化到路径 A 的 0.9695
• 稳态假设要求系统不在初始瞬态（第一个 8 窗口内）
• 如果长期队列使 p_est 退化，界回到路径 A

关键数值总结