Heavy-traffic Delay Optimality in Pull-based Load Balancing Systems
- 21 December 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 2 (3), 1-33
- https://doi.org/10.1145/3287323
Abstract
In this paper, we consider a load balancing system under a general pull-based policy. In particular, each arrival is randomly dispatched to one of the servers with queue length below a threshold; if none exists, this arrival is randomly dispatched to one of the entire set of servers. We are interested in the fundamental relationship between the threshold and the delay performance of the system in heavy traffic. To this end, we first establish the following necessary condition to guarantee heavy-traffic delay optimality: the threshold will grow to infinity as the exogenous arrival rate approaches the boundary of the capacity region (i.e., the load intensity approaches one) but the growth rate should be slower than a polynomial function of the mean number of tasks in the system. As a special case of this result, we directly show that the delay performance of the popular pull-based policy Join-Idle-Queue (JIQ) lies strictly between that of any heavy-traffic delay optimal policy and that of random routing. We further show that a sufficient condition for heavy-traffic delay optimality is that the threshold grows logarithmically with the mean number of tasks in the system. This result directly resolves a generalized version of the conjecture by Kelly and Laws.Keywords
Funding Information
- Office of Naval Research (N00014-17-1-2417)
- National Science Foundation (CNS-1719371,1717060,1518829)
This publication has 25 references indexed in Scilit:
- Asymptotically tight steady-state queue length bounds implied by drift conditionsQueueing Systems, 2012
- Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web servicesPerformance Evaluation, 2011
- State Space Collapse in Many-Server Diffusion Limits of Parallel Server SystemsMathematics of Operations Research, 2011
- Queue-and-Idleness-Ratio Controls in Many-Server Service SystemsMathematics of Operations Research, 2009
- Stationary Distribution Convergence for Generalized Jackson Networks in Heavy TrafficMathematics of Operations Research, 2009
- Validity of heavy traffic steady-state approximations in generalized Jackson networksThe Annals of Applied Probability, 2006
- Dynamic Routing in Large-Scale Service Systems with Heterogeneous ServersQueueing Systems, 2005
- Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policiesThe Annals of Applied Probability, 1998
- Heavy traffic limit theorems for a queueing system in which customers join the shortest lineAdvances in Applied Probability, 1989
- A Basic Dynamic Routing Problem and DiffusionIEEE Transactions on Communications, 1978