论文标题
超越缩放：重量流量中的两次选择权均值模型的可计算误差范围
Beyond Scaling: Calculable Error Bounds of the Power-of-Two-Choices Mean-Field Model in Heavy-Traffic
论文作者
论文摘要
本文提供了一种在重量流量中得出平均场模型的可计算近似误差的配方，重点是众所周知的负载平衡算法 - 两种选择功率（PO2）。该食谱结合了Stein的基于几何尾部边界的线性化平均场模型和状态空间浓度（SSC）的方法。特别是，我们将状态空间分为两个区域，即平均场平衡附近的一个邻居及其补充。我们首先使用尾巴绑定来表明稳态概率在附近的外部很小。然后，我们使用线性化的平均场模型和Stein的方法来表征发电机差，该差异提供了近似误差的主要项。从主要项来看，我们能够获得渐近的紧密结合和非肌化上限，两者都是可计算的边界，而不是像文献中的大多数结果那样的订单缩放结果。最后，我们将理论界限与数值评估进行了比较，以显示我们结果的有效性。我们注意到，模拟结果表明，即使对于只有十个服务器的系统，两个界限也有效。
This paper provides a recipe for deriving calculable approximation errors of mean-field models in heavy-traffic with the focus on the well-known load balancing algorithm -- power-of-two-choices (Po2). The recipe combines Stein's method for linearized mean-field models and State Space Concentration (SSC) based on geometric tail bounds. In particular, we divide the state space into two regions, a neighborhood near the mean-field equilibrium and the complement of that. We first use a tail bound to show that the steady-state probability being outside the neighborhood is small. Then, we use a linearized mean-field model and Stein's method to characterize the generator difference, which provides the dominant term of the approximation error. From the dominant term, we are able to obtain an asymptotically-tight bound and a nonasymptotic upper bound, both are calculable bounds, not order-wise scaling results like most results in the literature. Finally, we compared the theoretical bounds with numerical evaluations to show the effectiveness of our results. We note that the simulation results show that both bounds are valid even for small size systems such as a system with only ten servers.
