在随机网络中,队列峰值随时间呈对数增长,突破几何阈值后显著放缓。
Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds

- 通过自归一化机制,将容量几何影响从对数系数中剥离。
- 超过几何阈值后,队列峰值在高概率和期望下仅对数增长。
- 适用于带状态空间坍缩的输入排队交换机,可实现紧致对数界。
我们研究广义交换机中的有限时域队列峰值,这是一种标准的随机网络模型,多个队列共享受限服务资源。到达过程可相关、非平稳且依赖系统历史;唯一负载条件是均匀内部松弛,即条件均值到达向量始终位于容量区域的固定收缩内。我们发现,该松弛重塑了漂移最小化调度策略(如MaxWeight)的有限时间峰值规律。无松弛时尖锐的平方根包络仅在与几何相关的阈值前成立;超过该阈值后,运行最大值在高概率和期望下仅随时间对数增长。其机制是自归一化:在当前队列方向上,投影波动尺度被稳定漂移尺度归一化。这消除了容量几何对对数系数的影响,而几何仍决定阈值。匹配的下界表明,对数项和几何阈值均不可避免。当存在有限时间状态空间坍缩时,可通过局部瓶颈几何进一步收紧阈值。对于广义输入排队交换机,我们获得了对数系数紧致的有限时间峰值界。模拟验证了两阶段包络、局部几何修正及方差敏感改进的理论预测。
原文摘要 · Abstract (English)
We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent, nonstationary, and responsive to the system history; the only load condition is uniform interior slack, meaning the conditional mean arrival vector stays in a fixed contraction of the capacity region. We show that this slack reshapes the finite-time peak law for drift-minimizing scheduling policies such as MaxWeight. The square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold, the running maximum grows only logarithmically with the horizon, both with high probability and in expectation. The mechanism is self-normalization: in the current queue direction, the projected fluctuation scale is normalized by the stabilizing drift scale. This removes capacity geometry from the logarithmic coefficient, while geometry remains in the threshold. Matching lower bounds show that both the logarithmic term and a geometric threshold are unavoidable. When finite-time state-space collapse is available, the threshold can be sharpened using local bottleneck geometry. For generalized input-queued switches, we obtain finite-time peak bounds with tight logarithmic coefficients. Simulations illustrate the two-phase envelope, local geometric refinements, and variance-sensitive improvements predicted by the theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。