论文标题
零等待负载平衡算法的大型系统不敏感性
Large-System Insensitivity of Zero-Waiting Load Balancing Algorithms
论文作者
论文摘要
本文研究了一类负载平衡算法的敏感性（或不敏感），这些算法在下半钟惠特政权中获得渐近零等待，称为LB-Zero。零等待负载平衡算法的大多数现有结果都认为服务时间分布是指数的。本文确定了LB-Zero的{\ em大型系统不敏感}，其服务时间遵循具有有限数量阶段的考克斯分布。该结果表明，LB-Zero在大量的服务时间分布中实现渐近零等待，这在我们的模拟中得到了证实。为了证明这一结果，本文开发了一种新技术，称为“迭代状态空间剥离”（或简称ISSP）。 ISSP首先确定队列状态上的上限和下限之间的迭代关系，然后证明该系统生活在迭代界限的固定点附近，概率很高。基于ISSP，通过在固定点附近应用Stein的方法进一步分析了系统的稳态分布。 ISSP，例如在重流量分析中的状态空间崩溃，是一种通用方法，可用于研究其他复杂的随机系统。
This paper studies the sensitivity (or insensitivity) of a class of load balancing algorithms that achieve asymptotic zero-waiting in the sub-Halfin-Whitt regime, named LB-zero. Most existing results on zero-waiting load balancing algorithms assume the service time distribution is exponential. This paper establishes the {\em large-system insensitivity} of LB-zero for jobs whose service time follows a Coxian distribution with a finite number of phases. This result suggests that LB-zero achieves asymptotic zero-waiting for a large class of service time distributions, which is confirmed in our simulations. To prove this result, this paper develops a new technique, called "Iterative State-Space Peeling" (or ISSP for short). ISSP first identifies an iterative relation between the upper and lower bounds on the queue states and then proves that the system lives near the fixed point of the iterative bounds with a high probability. Based on ISSP, the steady-state distribution of the system is further analyzed by applying Stein's method in the neighborhood of the fixed point. ISSP, like state-space collapse in heavy-traffic analysis, is a general approach that may be used to study other complex stochastic systems.
