We analyse Join-the-Shortest-Queue in a contemporary scaling regime known asthe Non-Degenerate Slowdown regime. Join-the-Shortest-Queue (JSQ) is aclassical load balancing policy for queueing systems with multiple parallelservers. Parallel server queueing systems are regularly analysed anddimensioned by diffusion approximations achieved in the Halfin-Whitt scalingregime. However, when jobs must be dispatched to a server upon arrival, weadvocate the Non-Degenerate Slowdown regime (NDS) to compare differentload-balancing rules. In this paper we identify novel diffusion approximation and timescaleseparation that provides insights into the performance of JSQ. We calculate theprice of irrevocably dispatching jobs to servers and prove this to within 15%(in the NDS regime) of the rules that may manoeuvre jobs between servers. Wealso compare ours results for the JSQ policy with the NDS approximations ofmany modern load balancing policies such as Idle-Queue-First andPower-of-$d$-choices policies which act as low information proxies for the JSQpolicy. Our analysis leads us to construct new rules that have identicalperformance to JSQ but require less communication overhead thanpower-of-2-choices.
展开▼
