CSR: Small: Scalable, heterogeneity-aware load balancing

Suny At Stony Brook, Stony Brook NY

Investigators

Abstract

Several extremely large online services are provided by distributed systems. Load balancers play a vital role in such systems by distributing incoming requests among the back-end nodes. However, given the rise in cloud computing and the increasing popularity of online services, load balancers today face significant challenges that impact performance. Key among them is the need to quickly distribute millions of requests among heterogeneous nodes while adapting to changing system conditions. Failure to serve requests in a timely manner can lead to loss of revenue due to customer abandonment. This research proposes novel, scalable algorithms that enable high-throughput load balancers for cloud deployments. By leveraging concepts from queueing theory, this research will investigate dynamic, near-optimal load distribution policies with provable performance guarantees. The proposed algorithms will be designed for easy adoption in existing open-source load balancers, including Apache, HAProxy, and nginx. Recent network function virtualization trends have put the spotlight back on software network functions. This project will explore novel software load balancers for modern computing environments, including dedicated clusters and shared cloud environments. Given the need for high-throughput load balancing decisions, this research focuses on simple yet powerful randomized load balancer designs. The key idea of the proposed research is to dynamically adapt the routing probability based on inferred changes in the workload and infrastructure. Queueing theoretic models will be leveraged to understand the impact of routing on performance, and machine learning techniques will be employed for detecting system changes. The proposed load balancers will be evaluated in Web and data-dependent environments, including MapReduce implementations. The integrated theory-systems research approach will provide unique interdisciplinary educational and collaborative opportunities, including (cross-listed) course development, student training, and technology transfer with industrial partners.