In recent years, the efficiency and even the feasibility of traditional load-balancing policies are challenged by the rapid growth of cloud infrastructure with increasing levels of server heterogeneity and increasing size of cloud services and applications. In such many software-load-balancers heterogeneous systems, traditional solutions, such as JSQ, incur an increasing communication overhead, whereas low-communication alternatives, such as JSQ(d) and the recently proposed JIQ scheme are either unstable or provide poor performance.

 We argue that a better low-communication load balancing scheme can be established by allowing each dispatcher to have a different view of the system and keep using JSQ, rather than greedily trying to avoid starvation on a per-decision basis. 
 accordingly, we introduce the Loosely-Shortest -Queue family of load balancing algorithms. Roughly speaking, in Loosely-shortest -Queue, each dispatcher keeps a different approximation of the server queue lengths and routes jobs to the shortest among them. Communication is used only to update the approximations and make sure that they are not too far from the real queue lengths in expectation. We formally establish the strong stability of any Loosely-Shortest -Queue policy and provide an easy-to-verify sufficient condition for verifying that a policy is Loosely-Shortest -Queue. We further demonstrate that the Loosely-Shortest -Queue approach allows constructing throughput optimal policies with an arbitrarily low communication budget.

 Finally, using extensive simulations that consider homogeneous, heterogeneous and highly skewed heterogeneous systems in scenarios with a single dispatcher as well as with multiple dispatchers, we show that the examined Loosely-Shortest -Queue example policies are always stable as dictated by theory. Moreover, it exhibits an appealing performance and significantly outperforms well-known low-communication policies, such as JSQ(d) and JIQ, while using a similar communication budget. Background. In recent years, due to the rapidly increasing size and heterogeneity of cloud services and applications BID3 BID7 BID12 BID19 , the design of load balancing algorithms for parallel server systems has become extremely challenging. The goal of these algorithms is to efficiently load-balance incoming jobs to a large number of servers, even though these servers display large heterogeneity because of two reasons: First, current large-scale systems increasingly contain, in addition to multiple generations of CPUs (central processing units) BID11 , various types of accelerated devices such as GPUs (graphics processing units), FPGAs (field-programmable gate arrays) and ASICs (application-specific integrated circuit), with significantly higher processing speeds. Second, VMs (virtual machines) and/or containers are commonly used to deploy different services that share resources on the same servers, potentially leading to significant and unpredictable heterogeneity.In a traditional server farm, a centralized load-balancer (dispatcher) can rely on a full-state-information policy with strong theoretical guarantees for heterogeneous servers, such as join-theshortest-queue (JSQ), which routes emerging jobs to the server with the shortest queue BID4 BID5 BID12 BID28 BID29 . This is because in such single-centralized-dispatcher scenarios, the dispatcher forms a single access point to the servers. Therefore, by merely receiving a notification from each server upon the completion of each job, it can track all queue lengths, because it knows the exact arrival and departure patterns of each queue (neglecting propagation times) BID14 . The communication overhead between the servers and the dispatcher is at most a single message per job, which is appealing and does not increase with the number of servers.However, in current clouds, which keep growing in size and thus have to rely on multiple dispatchers BID9 , implementing a policy like JSQ may involve a prohibitive implementation overhead as the number m of dispatchers increases BID14 . This is because each server needs to keep all m dispatchers updated as jobs arrive and complete, leading to up to O(m) communication messages per job. This large communication overhead makes scaling the number of dispatchers difficult, and forces cloud dispatchers to rely on heuristics that do not provide any service guarantees with heterogeneous servers. For instance, in L7 load-balancers, multi-dispatcher services are essentially decomposed into several fully-independent single-dispatcher services, where each dispatcher applies either round-robin or JSQ reduced to its own jobs only BID0 BID20 BID24 . Unfortunately, such an approach suffers from lack of predictable guarantees, lack of a global view of the system, and communication bursts with potential incast issues.Related work. Despite their increasing importance, scalable policies for heterogeneous systems with multiple dispatchers have received little attention in the literature. In fact, as we later discuss, the only suggested scalable policies that address the many-dispatcher scenario in an heterogeneous setting are based on join-the-idlequeue (JIQ), and none of them is stable BID31 .In the JSQ(d) (power-of-choice) policy, to make a routing decision, a dispatcher samples d ≥ 2 queues uniformly at random and chooses the shortest among them BID1 BID2 BID8 BID17 BID30 . JSQ(d ) is stable in systems with homogeneous servers. However , with heterogeneous servers, JSQ(d) leads to poor performance and even to instability, both with a single and multiple dispatchers BID6 .In the JSQ(d, m) (power-of-memory) policy, the dispatcher samples the m shortest queues from the previous decision in addition to d ≥ m ≥ 1 new queues chosen uniformly-at-random BID16 BID21 . The job is then routed to the shortest among these d + m queues. JSQ(d, m) has been shown to be stable in the case of a single dispatcher, even with heterogeneous servers. However , it offers poor performance, and has not been considered with multiple dispatchers. than W R. We complete the proof by using the fact that in W R, the routing decisions do not depend on the system state (unlike JSQ). Sufficient stability condition. It can be challenging to prove that a policy is Loosely-Shortest-Queue, i.e., that in expectation, the local dispatcher views are not too far from the real queue lengths. Therefore , we develop a simple sufficiency condition to prove that a policy belongs to the Loosely-Shortest-Queue family, and exemplify its use. Intuitively , the condition states that there is a non-zero probability that a server updates a dispatcher at each time-slot. Example Loosely-Shortest-Queue policies. Since Loosely-ShortestQueue is not restricted to work with either push (i.e., dispatchers sample the servers) or pull (i.e., servers update the dispatchers) based communication, we aim to achieve the same communication overhead as the lowest-overhead/best-known examples in each class. Accordingly, we show how two of the newest existing low communication policies are in fact Loosely-Shortest-Queue and how to construct new Loosely-Shortest-Queue policies with communication patterns similar to that of other low-communication policies such as the push-based JSQ(2) and the pull-based JIQ, but with significantly stronger theoretical guarantees and empirical performance. Extensive simulations. Using extensive simulations considering homogeneous, heterogeneous, and highly-skewed heterogeneous systems, in scenarios of a single as well as multiple dispatchers, we show how simple Loosely-Shortest-Queue policies are always stable in practice, present appealing performance, and significantly outperform other low-communication policies using an equivalent communication budget. In this paper, we introduced the Loosely-Shortest-Queue family of load balancing algorithms. We formally established that any Loosely-Shortest-Queue policy is strongly stable and further developed a simplified sufficient condition for establishing that a policy is Loosely-Shortest-Queue. We then demonstrated that the LooselyShortest-Queue approach allows to construct stable policies with arbitrary low communication budgets for system with multiple dispatchers and heterogeneous servers. Using extensive simulations that consider homogeneous, heterogeneous and highly skewed heterogeneous systems in small single-dispatcher and larger-scale multi-dispatcher scenarios, we illustrated how simple low-communication Loosely-Shortest-Queue known policies are stable and at the same time exhibit appealing performance. Our example policies significantly outperform wellknown low-communication policies such as JSQ(2) and JIQ, while obeying the same constraints on the communication overhead.Given the strength of the Loosely-Shortest-Queue approach in large-scale multi-dispatcher heterogeneous systems, we believe that it has the potential to open a new thread in the research of scalable load balancing policies. the best performance which is identical to the baseline, i.e., JSQ. This is because in a single dispatcher scenario Loosely-ShortestQueue-U pdate(1) is always aware of the exact queue length of all queues.Loosely-Shortest-Queue-U pdate(0.01) offers better performance than JIQ especially as the load increases. This is achieved with similar average communication overhead. It is notable that JIQ performs similarly to JSQ at low loads, but its performance quickly degrades as the load increases. This complies with the latest theoretical results indicating that JIQ is asymptotically worse than JSQ at high loads (i.e., JIQ is not heavy traffic delay optimal) BID31 .Finally , Loosely-Shortest-Queue-U pdate(2) is always better than its JSQ(2) counterpart using exactly the same communication overhead. Loosely-Shortest-Queue-U pdate(1) is slightly worse in this scenario but with a lesser communication overhead.
Scalable and low communication load balancing solution for heterogeneous-server multi-dispatcher systems with strong theoretical guarantees and promising empirical results. 