技术摘要：动态负载下计算连续体中的队列感知任务卸载

问题陈述

计算连续体将本地设备、边缘节点和云系统集成到一个统一的架构中。其中的一个核心挑战是任务卸载：即决定是将传入的任务在本地执行、在边缘执行，还是在云端执行。这种决策必须在动态且共享的条件下在线做出，而在这些条件下，系统行为难以预测。

关键难点包括：

• 队列效应： 当利用率接近容量时，等待时间成为延迟的主要组成部分。
• 服务变异性： 服务时间通常呈现重尾分布（例如 Pareto 分布），标准的指数模型（M/M/c）无法捕捉这些特性，从而导致对延迟的严重低估。
• 动态负载： 流量通常具有突发性和时变性，使得稳态分析模型无法满足瞬时决策的需求。
• 现有方法的局限性：
  • 分析模型： 假设条件是平稳的且参数固定，无法对瞬时拥塞做出反应。
  • 队列状态观测（如 JSQ）： 反应迅速但存在噪声，对短期波动敏感，且忽略了服务时间的变异性。
  • 基于学习的方法（如 DRL）： 需要大量的训练，存在样本复杂度高的问题，且缺乏形式化的性能保证或可解释性。

方法论

本文提出了一种队列感知卸载方法，该方法通过使用混合延迟估计器来进行逐个任务的决策。其核心创新在于将分析队列模型与实时队列观测进行自适应融合。

1. 系统模型

• 层级： 系统由本地（$L$）、边缘（$E$）和云（$C$）三个层级组成。
• 到达： 建模为具有时变速率的泊松过程。每层到达率（$\lambda_i$）通过滑动窗口进行在线估计，以避免不对称流量分布带来的偏差。
• 服务时间： 使用 Pareto 分布（形状参数 $\alpha > 2$）进行建模，以体现重尾变异性。
• 延迟组成： 总延迟 $T_i$ 是等待时间（$W_i$）、服务时间（$1/\mu_i$）和通信延迟（$D_i$）之和。

2. 混合延迟估计器

该方法通过结合两种互补的来源来估计等待时间（$W_i$）：

• 分析组件（$W^{model}_i$）： 使用 Allen–Cunneen 公式 来近似 G/G/c 队列的等待时间。该公式通过利用源自 Pareto 分布的平方变异系数（$C^2_s$）对标准的 M/M/c Erlang-C 公式进行修正，从而纠正了标准模型。这提供了一个稳定且具有前瞻性的拥塞估计。
• 队列状态组件（$W^{queue}_i$）： 一个基于当前等待任务数（$q_i$）相对于活跃服务器数（$n_i$）的反应式估计。它能捕捉瞬时拥塞，但存在噪声。

3. 自适应融合机制

该方法并非使用固定的混合参数，而是采用了一种基于负载的融合权重 $\beta_i(t)$：
$$\beta_i(t) = \min\left(1, \frac{q_i(t)}{c_i}\right)$$
最终估计值为：
$$W_i(t) = (1 - \beta_i(t)) \cdot W^{model}_i(t) + \beta_i(t) \cdot W^{queue}_i(t)$$

• 逻辑： 当某层为空（$q_i=0$）时，估计完全依赖于分析模型。随着队列积压相对于容量（$c_i$）增长，权重会线性向反应式队列观测转移。一旦积压超过容量，估计将完全依赖于观测到的状态。
• 利用率惩罚： 如果利用率 $\rho_i(t)$ 超过阈值（0.9），则应用乘法惩罚，以抑制向接近饱和的层级进行路由。

4. 决策规则

任务被分配到使估计总延迟最小化的层级：
$$i^*(t) = \arg \min_{i \in T} \left[ \hat{W}_i(t) + \frac{1}{\mu_i} + D_i(t) \right]$$
其中包含一个 $\epsilon$-greedy 探索步骤（$\epsilon=0.05$），以防止速率估计器在被选择次数过少的层级中发生崩溃。

核心贡献

1. 队列感知延迟估计： 一种通过 G/G/c 近似（通过 Allen–Cunneen）针对重尾服务时间对分析队列等待时间进行修正，并将其与实时队列观测相结合的公式化方法。
2. 逐层到达率估计： 一种滑动窗口估计器，用于分别追踪各层的到达率，从而避免了使用单一全局速率代理所带来的偏差。
   云。
3. 自适应预测-反应混合路由： 一种融合机制，其权重是当前队列积压的确定性函数，无需固定混合超参数或离线调优。
4. 双重验证： 使用离散事件模拟器和基于 HTTP 的仿真测试平台（具有真实的异步请求分发、队列竞争和墙钟时间测量）进行评估。
5. 估计准确性分析： 证明了该混合估计器在所有负载水平下，其预测误差均低于仅基于模型或仅基于队列的组件。

实验结果

该方法在增加的负载、突发到达以及变化的边缘容量下进行了评估，并与静态基准（边缘优先、随机）、动态基准（JSQ、JSQ-S）以及 Oracle 策略进行了对比。

• 延迟降低： 在所有负载水平下，该方法相比于静态（边缘优先）和分析不足（仅模型）的基准，显著降低了平均延迟。
• 尾部延迟与公平性： 虽然贪婪队列长度启发式算法（JSQ）在平均延迟方面表现良好，但所提方法在处理大型重尾任务时展现出更优越的尾部延迟（P95）。它防止了纯 JSQ 路由中常见的对大型任务的系统性饥饿现象。
• 预测误差： 混合估计器在所有负载下均保持了最低的平均绝对相对误差（MAPE），避免了仅模型估计在高负载下的退化，以及仅队列估计在低负载下的不稳定。
• 适应性： 在突发场景中，该策略能够快速适应，通过在边缘拥塞增加时将任务重新分配到云端，比静态策略更快地稳定延迟。
• 开销： 决策过程的计算开销处于微秒级（模拟中平均约为 7.4 µs），证实了其适用于资源受限的边缘节点。
• 验证： 基于 HTTP 的仿真证实了模拟器的动态特性在真实请求处理下得以重现，差异归因于系统的网络延迟校准偏移，而非策略失效。

意义与主张

论文声称，所提方法通过同时满足以下三个属性，填补了现有文献在实际连续体卸载方面的空白：

1. 在线逐任务决策，无需训练。
2. 通过 G/G/c 近似显式建模非指数服务时间的变异性。
3. 轻量级、无需训练的操作，具备逐层拥塞感知能力。

作者强调，该方法不需要离线校准或固定超参数，因为融合权重是直接由系统状态导出的。结果表明，将分析稳定性与反应式观测相结合，比仅依赖其中之一能产生更鲁棒的决策，特别是在具有重尾服务时间和动态负载的环境中。

承认的局限性：

• 仿真使用的是合成 Pareto 服务时间，而非生产环境追踪数据。
• 假设任务是独立的且无状态的（无数据局部性或依赖关系）。
• 该方法假设服务速率和队列长度是可观测的，这在分布式设置中可能需要专门的监测手段。
• 能量消耗目前不在优化目标之内。
• 该方法相对于 JSQ 的优势集中在尾部延迟和公平性，而非测试配置中的聚合平均延迟。