2025-11-16T04:34:12.484648

Chronicles of Jockeying in Queuing Systems

Kiggundu, Han, Krummacker et al.
Emerging trends in communication systems, such as network softwarization, functional disaggregation, and multi-access edge computing (MEC), are reshaping both the infrastructural landscape and the application ecosystem. These transformations introduce new challenges for packet transmission, task offloading, and resource allocation under stringent service-level requirements. A key factor in this context is queue impatience, where waiting entities alter their behavior in response to delay. While balking and reneging have been widely studied, this survey focuses on the less explored but operationally significant phenomenon of jockeying, i.e. the switching of jobs or users between queues. Although a substantial body of literature models jockeying behavior, the diversity of approaches raises questions about their practical applicability in dynamic, distributed environments such as 5G and Beyond. This chronicle reviews and classifies these studies with respect to their methodologies, modeling assumptions, and use cases, with particular emphasis on communication systems and MEC scenarios. We argue that forthcoming architectural transformations in next-generation networks will render many existing jockeying models inapplicable. By highlighting emerging paradigms such as MEC, network slicing, and network function virtualization, we identify open challenges, including state dissemination, migration cost, and stability, that undermine classical assumptions. We further outline design principles and research directions, emphasizing hybrid architectures and decentralized decision making as foundations for re-conceptualizing impatience in next-generation communication systems.
academic

Chronicles of Jockeying in Queuing Systems

基本信息

  • 论文ID: 2402.11061
  • 标题: Chronicles of Jockeying in Queuing Systems
  • 作者: Anthony Kiggundu, Bin Han, Dennis Krummacker, Hans D. Schotten
  • 分类: cs.NI (Networking and Internet Architecture)
  • 发表时间/会议: ACM Computing Surveys (预期2023年1月)
  • 论文链接: https://arxiv.org/abs/2402.11061

摘要

通信系统的新兴趋势，如网络软件化、功能分解和多接入边缘计算(MEC)，正在重塑基础设施景观和应用生态系统。这些变革为严格服务级别要求下的数据包传输、任务卸载和资源分配带来了新挑战。队列不耐烦是一个关键因素，等待实体会根据延迟改变其行为。虽然退避(balking)和放弃(reneging)已被广泛研究，但本综述聚焦于探索较少但操作上重要的现象——队列切换(jockeying)，即作业或用户在队列之间的切换。尽管大量文献对队列切换行为建模，但方法的多样性引发了它们在5G及未来动态分布式环境中实际适用性的质疑。本文回顾并分类了这些研究的方法论、建模假设和用例，特别强调通信系统和MEC场景。我们论证下一代网络的架构变革将使许多现有队列切换模型不再适用，并通过强调MEC、网络切片和网络功能虚拟化等新兴范式，识别出状态传播、迁移成本和稳定性等开放挑战。

研究背景与动机

问题定义

本研究要解决的核心问题是：在下一代通信网络(5G/6G)中，传统的队列切换(jockeying)模型如何适应新的架构变革，以及如何重新设计队列不耐烦行为的建模方法。

问题重要性

  1. 延迟敏感应用激增: 远程控制、工业自动化、自动驾驶、沉浸式XR服务等对延迟和可靠性要求极高
  2. 架构变革: 网络软件化、功能分解、MEC等带来的复杂性
  3. 资源优化需求: 在严格SLA约束下的实时资源分配和任务卸载

现有方法局限性

  1. 同质化假设: 大多数模型假设队列系统是同质的，忽略了现实中的异构性
  2. 完全可观测性: 假设所有队列状态信息都能及时准确获得
  3. 零迁移成本: 忽略了状态转移、重配置等实际开销
  4. 静态环境: 未考虑移动性、动态扩缩容、突发流量等动态因素

研究动机

随着5G/6G网络中网络切片、SDN/NFV、MEC等技术的广泛部署，传统队列理论的基本假设被打破，急需重新审视和设计适应新架构的队列切换模型。

核心贡献

  1. 全面分类综述: 首次系统性地回顾和分类了队列切换建模技术，提供了该领域迄今为止最全面的文献综述
  2. 差距分析: 定量评估了经典模型在现代5G/6G架构约束下的实用性局限
  3. 架构集成分析: 深入分析了MEC、SDN/NFV和网络切片如何重新定义队列切换建模，揭示了异构性、信令延迟和跨域信任约束的影响
  4. 设计原则和未来方向: 基于分类和差距分析，提出了适用于下一代分布式环境的鲁棒、通信感知的队列切换模型设计原则

方法详解

任务定义

本文是一篇综述性论文，主要任务是：

  • 输入: 现有队列切换文献、5G/6G架构特征、MEC部署约束
  • 输出: 系统性分类、适用性评估、设计原则、未来研究方向
  • 约束: 需考虑实际网络部署的技术和经济约束

分类框架

1. 随机建模方法

  • 马尔可夫决策过程(MDP): 适用于序列决策，但存在状态空间爆炸问题
  • 博弈论方法: 基于纳什均衡，但要求完全信息和理性参与者假设
  • 流体理论模型: 将离散事件平均化为连续流，适用于大规模系统分析

2. 解析建模方法

  • 矩阵几何方法: 为准生灭过程提供精确解，但要求结构化、平稳的马尔可夫系统

3. 行为建模方法

  • 信息价值模型: 将队列切换视为局部决策问题
  • 人工神经网络: 捕获高维非线性关系，但存在"黑盒"问题

切换触发机制

基于阈值的切换

队列长度或等待时间阈值：当队列长度差异超过预设阈值时触发切换

if |Q₁ - Q₂| > threshold:
    switch_to_shorter_queue()

基于成本和期望延迟

在异构系统中，结合队列长度阈值和期望等待时间：

switch_condition = (expected_waiting_time < current_position_time) 
                  AND (migration_cost < benefit)

技术创新点

  1. 混合架构设计: 分离状态传播和决策控制
    • 集中式传播：确保系统范围的队列状态可见性
    • 分布式决策：在延迟约束下进行本地自主决策
  2. 信息价值方法: 仅当期望效用增益超过通信成本时才触发高保真更新
  3. 稳定性保障: 通过迟滞阈值、冷却定时器、显式迁移成本考虑防止振荡

实验设置

文献分析方法

  • 系统性检索: 涵盖队列理论、通信网络、边缘计算等相关领域
  • 分类标准: 按建模方法、队列类型、切换阈值、性能指标进行分类
  • 适用性评估: 基于5G/6G架构特征评估现有模型的局限性

评价维度

  1. 建模假设的现实性: 同质性、信息可得性、迁移成本等
  2. 可扩展性: 状态空间复杂度、计算可行性
  3. 鲁棒性: 对不完整信息、动态环境的适应能力

实验结果

主要发现

1. 经典假设失效

  • 同质性假设: 网络切片引入的多厂商、多性能配置使简单队列长度比较不足
  • 零迁移成本: 有状态迁移产生与状态大小和网络路径特征成比例的传输时间
  • 完全信息: 及时认证的切片描述符传播消耗控制平面资源

2. 稳定性和安全风险

  • 乒乓效应: 低队列长度阈值可能引发振荡行为
  • 安全威胁: 未认证状态报告可被恶意利用

3. 性能改进潜力

数值研究表明，自适应工作负载重分布可将平均逗留时间减少20-30%，加速延迟敏感MEC应用的任务完成。

模型局限性分析

随机模型局限

  • 部分、延迟或审查的遥测产生有偏高方差估计
  • 动态系统(移动性、自动扩缩容)导致快速概念漂移
  • 切片异构性使池化模型失效

纳什均衡模型局限

  • 假设明确的效用函数和参与者的充分知识
  • 在实际中参与者是有界理性的，运行学习启发式
  • 跨管理域的可执行性问题

流体模型局限

  • 平均化离散事件可能掩盖尾部事件和离散触发器
  • 假设平滑、缓慢变化的输入，但网络功能扩缩容产生突变

相关工作

队列理论基础

从Haight (1958)的开创性工作开始，队列切换研究经历了从简单M/M/2系统到复杂异构环境的演进。

现代网络应用

  • 边缘计算: Han等人在MEC环境中的不耐烦队列研究
  • 网络切片: 5G网络中基于切片的资源分配和SLA管理
  • SDN/NFV: 软件定义网络中的动态负载均衡

与本文关系

本文整合了传统队列理论和现代网络架构，提供了跨学科的综合视角。

结论与讨论

主要结论

  1. 经典模型不足: 传统队列切换模型在5G/6G环境下面临根本性挑战
  2. 混合架构必要性: 需要分离状态传播和决策控制的混合设计
  3. 信息价值导向: 基于效用的信息更新策略比定期广播更高效
  4. 稳定性关键: 必须显式考虑迁移成本和防振荡机制

局限性

  1. 理论与实践差距: 大多数分析基于理论模型，缺乏大规模实际部署验证
  2. 安全考虑不足: 对恶意行为和攻击的防护机制需要更深入研究
  3. 跨域协调: 多厂商环境下的策略协调和信任机制仍需完善

未来方向

  1. 实证验证: 在MEC测试平台进行受控实验
  2. 大规模仿真: 基于真实流量轨迹的性能量化
  3. 理论界限: 最小更新频率的理论界限分析
  4. 安全机制: 抗恶意报告的鲁棒遥测认证

深度评价

优点

  1. 全面性: 首次系统性综述队列切换领域，涵盖从经典理论到现代应用
  2. 前瞻性: 准确识别了5G/6G架构变革对传统模型的挑战
  3. 实用性: 提出的混合架构和设计原则具有实际部署价值
  4. 跨学科性: 成功连接了队列理论、通信网络和边缘计算领域

不足

  1. 实验验证缺乏: 作为综述论文，缺少原创实验验证
  2. 量化分析有限: 对性能改进的量化分析主要引用其他研究
  3. 实现细节不足: 提出的设计原则需要更具体的实现指导

影响力

  1. 学术价值: 为队列切换研究提供了重要的理论基础和发展方向
  2. 实用价值: 对5G/6G网络设计和MEC部署具有指导意义
  3. 启发性: 为跨学科研究提供了良好范例

适用场景

  1. 网络切片环境: 多租户、异构服务要求的场景
  2. 边缘计算: 延迟敏感应用的任务卸载和资源分配
  3. 实时系统: 工业自动化、自动驾驶等关键应用

参考文献

论文引用了172篇参考文献，涵盖了队列理论经典文献、现代网络架构研究和边缘计算应用，为读者提供了全面的文献基础。

总体评价: 这是一篇高质量的综述论文，系统性地分析了队列切换在现代网络环境中面临的挑战，并提出了有价值的解决方向。论文的主要贡献在于识别了传统模型的局限性并提出了适应新架构的设计原则，对该领域的理论发展和实际应用都具有重要意义。