CSR: Small: Scalable, heterogeneity-aware load balancing

一些极大的在线服务由分布式系统提供。负载均衡器通过在后端节点之间分发传入请求，在这类系统中扮演着至关重要的角色。然而，考虑到云计算的兴起和在线服务的日益普及，负载均衡器今天面临着影响性能的重大挑战。其中的关键是需要在不同的节点之间快速分发数百万个请求，同时适应不断变化的系统条件。未能及时为客户提供服务可能会因客户遗弃而导致收入损失。这项研究提出了新颖、可扩展的算法，可实现云部署的高吞吐量负载均衡器。通过利用排队论中的概念，本研究将研究具有可证明的性能保证的动态、接近最优的负载分配策略。建议的算法将被设计为易于在现有的开源负载均衡器中采用，包括ApacheHAProxy和nginx。最近的网络功能虚拟化趋势使软件网络功能重新成为人们关注的焦点。该项目将探索适用于现代计算环境的新型软件负载均衡器，包括专用集群和共享云环境。考虑到对高吞吐量负载均衡决策的需求，本研究侧重于简单而强大的随机化负载均衡器设计。提出的研究的核心思想是基于推断的工作负载和基础设施的变化来动态调整路由概率。将利用排队理论模型来了解路由对性能的影响，并将使用机器学习技术来检测系统变化。建议的负载均衡器将在Web和依赖数据的环境中进行评估，包括MapReduce实现。整合的理论-系统研究方法将提供独特的跨学科教育和合作机会，包括(交叉列出的)课程开发、学生培训和与行业合作伙伴的技术转让。

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.