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.
翻译:本文研究在亚Halfin- Whitt 系统中实现零等待状态状态的一组负负平衡算法的灵敏度( 或不灵敏度), 该算法在亚Halfin- Whitt 系统中实现了零等待状态, 名为 LB- 零。 多数关于零等待状态负载平衡算法的现有结果假定服务时间分布是指数化的。 本文为服务时间随着Coxian分布的有限阶段, 确定 LB- 零的工作建立了 LB- 的超大系统不灵敏度 。 此结果显示, LB- 零 能够实现零等待大规模服务时间分布的无药性。 为了证明这一结果, 本文开发了一种新的技术, 称为“ 国家空间切换动力” ( 简称ISAP ) 。 SISP 首先确定了排队列状态的上下界之间的迭接关系, 然后证明系统在迭接点附近有高概率的迭接线点。 基于 ISSP, 系统的稳定零状态分布通过在我们的模拟中应用Stein's 方法进一步分析系统, 将斯坦的系统应用固定空间平地方法进一步分析。 。 使用其他的崩溃系统, 。