Search

Load balancing, which is responsible for dispatching jobs on parallel servers, is a key component in computer networks and distributed computing systems, with broad applications in Web service, cloud computing, distributed cashing system, and grid computing. To provide delay performance guarantees and to design effective load balancing schemes, it is imperative to develop analytical tools to evaluate the system performance under different load balancing schemes. To that end, one important line of research has focused on the heavy-traffic regime when the load ρ approaches one. In this dissertation, we have made the following contributions.• Algorithm design: This is aimed at designing low-complexity and flexible load balancing schemes with rigorous theoretical guarantees on performance optimal- ity. (i) To achieve the advantages of both push-based and pull-based schemes at the same time, we propose a new load balancing scheme that carries out the principles emanating from the theoretical foundations. (ii) To address the fact that existing policies are often too restrictive, we identify a class of load bal- ancing policies that enjoy a nice trade-off between flexibility and performance guarantee. (iii) To handle load balancing with multiple dispatchers in heteroge- neous systems, we propose the Local-Estimation-Driven (LED framework that enables us to achieve optimal performance.ii• Performance analysis: This is aimed at the mathematical analysis of load bal- ancing schemes with proper metrics to establish tight characterizations of per- formance and to reveal the limits of their applicability. (i) We establish the nec- essary and sufficient conditions for a general class of pull-based load balancing schemes to achieve optimal delay in heavy traffic, which resolves a generalized version of the conjecture by Kelly and Laws. (ii) Instead of only focusing on the heavy-traffic delay optimality in the first moment, we directly characterize the stationary distribution and the convergence rates in heavy traffic by a novel development of Stein’s method. (ii) We further go beyond metrics concerned with the sum queue lengths in the system by devising a refined performance evaluation metric, which allows us not only to successfully distinguish between good and poor load balancing schemes, but to guide the design of new schemes.