Optimal routing to parallel servers in heavy traffic

Abstract

We study a system with heterogeneous parallel servers, each with an infinite waiting room. Upon arrival, a job is routed to the queue of one of the servers, possibly depending on the dynamic state information such as the real-time queue lengths, the arrival, and service history of jobs. The objective is to find the routing policy that best uses the available state information to minimize the expected stationary queue length. In this paper, we establish the diffusion limit for the round-robin policy (respectively, arrival-chasing policy, service-chasing policy), and show that with properly chosen parameters, it achieves the optimal performance asymptotically within the class of admissible policies that require no state information (respectively, require arrival history, service history). Like the jointhe-shortest-queue and the balanced routing policies that use real-time queue length information, the optimal service-chasing policy is also asymptotically optimal over all admissible policies. Further analysis of the diffusion limits yields a number of insights into the performance of these routing policies and reveals the value of various state information. We numerically demonstrate the effectiveness of the estimators derived from the diffusion limits for the policies being studied and obtain interesting observations. We also address the problem of interchange of limits under the aforementioned policies, which justifies the stationary performance of the diffusion limit as a valid approximation to that of the original system under respective policies. Methodologically, this study contributes to the application of the BIGSTEP method for constructing control policy to optimize stationary performance and the recipe for justifying the interchange of limits in the heavy traffic analysis of stochastic processing networks.