2017/12/22 by Mark van der Boor, Sem Borst, van der Boor, Mark +5
Business, Management and Accounting · Computer Science · Engineering · #Advanced Queuing Theory Analysis #Advanced Wireless Network Optimization #Age of Information Optimization #FOS: Computer and information sciences #FOS: Mathematics #Performance (cs.PF) #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1712.08555
openalex publication_date 2017/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an overview of scalable load balancing algorithms which provide\nfavorable delay performance in large-scale systems, and yet only require\nminimal implementation overhead. Aimed at a broad audience, the paper starts\nwith an introduction to the basic load balancing scenario, consisting of a\nsingle dispatcher where tasks arrive that must immediately be forwarded to one\nof N single-server queues.\n A popular class of load balancing algorithms are so-called power-of-d or\nJSQ(d) policies, where an incoming task is assigned to a server with the\nshortest queue among d servers selected uniformly at random. This class\nincludes the Join-the-Shortest-Queue (JSQ) policy as a special case (d = N),\nwhich has strong stochastic optimality properties and yields a mean waiting\ntime that vanishes as N grows large for any fixed subcritical load. However,\na nominal implementation of the JSQ policy involves a prohibitive communication\nburden in large-scale deployments. In contrast, a random assignment policy (d\n= 1) does not entail any communication overhead, but the mean waiting time\nremains constant as N grows large for any fixed positive load.\n In order to examine the fundamental trade-off between performance and\nimplementation overhead, we consider an asymptotic regime where d(N) depends\non N. We investigate what growth rate of d(N) is required to match the\nperformance of the JSQ policy on fluid and diffusion scale. The results\ndemonstrate that the asymptotics for the JSQ(d(N)) policy are insensitive to\nthe exact growth rate of d(N), as long as the latter is sufficiently fast,\nimplying that the optimality of the JSQ policy can asymptotically be preserved\nwhile dramatically reducing the communication overhead. We additionally show\nhow the communication overhead can be reduced yet further by the so-called\nJoin-the-Idle-Queue scheme, leveraging memory at the dispatcher.\n