Zero-Delay Load Balancing Algorithms in Large-Scale Data Centers

This poster presents results on a class of load balancing algorithms for large-scale cloud computing systems. We established steady-state perfor-mance of load balancing algorithms in the heavy traffic regime such that the load of system is approaches to one. This is a typical scenario under demand-response. We established a sufficient condition under which the probability that an incoming job is routed to an idle server is one asymp-totically. The class of load balancing algorithms that satisfy the condition includes join-the-shortest-queue (JSQ), idle-one-first (I1F), join-the-idle-queue (JIQ), and power-of-d-choices (Pod) with d = Na log N. The proof of the main result is based on the framework of Stein's method. A key contribution is to use a simple generator approximation based on state space collapse.