Asymptotic Optimality of the Speed-Aware Join-the-Shortest-Queue in the Halfin-Whitt Regime for Heterogeneous Systems

The join-the-shortest-queue (JSQ) load-balancing scheme is known to minimize the average response time of jobs in homogeneous systems with identical servers. However, for heterogeneous systems with servers having different processing speeds, finding an optimal load balancing scheme remains an open problem for finite system sizes. Recently, for systems with heterogeneous servers, a variant of JSQ scheme, called the speed-aware-join-the-shortest-queue (SA-JSQ) scheme, has been shown to achieve asymptotic optimality in the fluid-scaling regime where the number of servers n tends to infinity but the normalized the arrival rate of jobs remains constant. In this paper, we show that the SA-JSQ scheme is also asymptotically optimal for heterogeneous systems √ in the Halfin-Whitt traffic regime where the normalized arrival rate scales are 1 O(1= ^ffiffiffin). Our analysis begins by establishing that an appropriately scaled and centered version of the Markov process describing system dynamics weakly converges to a two-dimensional reflected Ornstein-Uhlenbeck (OU) process. We then show using Stein’s method that the stationary distribution of the underlying Markov process converges to that of the OU process as the system size increases by establishing the validity of interchange of limits. Finally, through coupling with a suitably constructed sys-tem, we show that SA-JSQ asymptotically minimizes the diffusion-scaled total number of jobs and the diffusion-scaled number of waiting jobs in the steady state in the Halfin-Whitt regime among all policies that dispatch jobs based on queue lengths and server speeds.