Erlang-C模型有限时间行为的研究:混合时间、平均队列长度与尾界
Finite-Time Behavior of Erlang-C Model: Mixing Time, Mean Queue Length and Tail Bounds
摘要 Abstract
数据中心和网约车服务等实际系统在文献中常被建模为排队系统。由于其分析上的可处理性,这些系统主要在稳态下进行研究。然而,几乎所有现实生活中的应用并不处于稳态运行,因此在将理论排队结果转化为实际应用时存在明显的差异。为此,我们针对Erlang-C系统(也称为$M/M/n$队列)提供了有限时间收敛的结果,为理解更一般的排队系统的瞬态行为奠定了基础。我们得到了有限数量服务器下有限时间队列长度分布与稳态分布之间的卡方距离的一个界。然后利用这些界研究了多服务器强拥塞渐近区域的行为。Erlang-C模型在所谓的Halfin-Whitt区域表现出相变。我们证明了我们的混合速率在Super-Halfin-Whitt区域匹配极限行为,并在Sub-Halfin-Whitt区域以一个常数因子匹配。为了证明这样的结果,我们采用了李雅普诺夫-庞加莱方法,在有限集合外部首先精心设计了一个李雅普诺夫函数以获得负漂移;在有限集合内部,则根据不同属性采用不同的策略,通过局部庞加莱不等式控制混合行为。我们方法论贡献的关键方面在于在这两个区域中获得了紧致保证,当它们结合在一起时为我们提供了紧致的混合时间界限。我们认为这种方法对研究可逆可数状态马尔可夫链的混合行为具有独立的兴趣价值。
Service systems like data centers and ride-hailing are popularly modeled as queueing systems in the literature. Such systems are primarily studied in the steady state due to their analytical tractability. However, almost all applications in real life do not operate in a steady state, so there is a clear discrepancy in translating theoretical queueing results to practical applications. To this end, we provide a finite-time convergence for Erlang-C systems (also known as $M/M/n$ queues), providing a stepping stone towards understanding the transient behavior of more general queueing systems. We obtain a bound on the Chi-square distance between the finite time queue length distribution and the stationary distribution for a finite number of servers. We then use these bounds to study the behavior in the many-server heavy-traffic asymptotic regimes. The Erlang-C model exhibits a phase transition at the so-called Halfin-Whitt regime. We show that our mixing rate matches the limiting behavior in the Super-Halfin-Whitt regime, and matches up to a constant factor in the Sub-Halfin-Whitt regime. To prove such a result, we employ the Lyapunov-Poincar\'e approach, where we first carefully design a Lyapunov function to obtain a negative drift outside a finite set. Within the finite set, we develop different strategies depending on the properties of the finite set to get a handle on the mixing behavior via a local Poincar\'e inequality. A key aspect of our methodological contribution is in obtaining tight guarantees in these two regions, which when combined give us tight mixing time bounds. We believe that this approach is of independent interest for studying mixing in reversible countable-state Markov chains more generally.