CSR: Small: Scalable, heterogeneity-aware load balancing

分布式系统提供了几个非常大的在线服务。负载平衡器通过在后端节点之间分发传入请求，在此类系统中发挥着至关重要的作用。然而，考虑到云计算的兴起和在线服务的日益普及，负载平衡器今天面临着影响性能的重大挑战。其中的关键是需要在异构节点之间快速分发数百万个请求，同时适应不断变化的系统条件。未能及时处理请求可能会因客户放弃而导致收入损失。这项研究提出了新颖的、可扩展的算法，使云部署的高吞吐量负载平衡器成为可能。通过利用排队理论中的概念，本研究将研究具有可证明的性能保证的动态、接近最优的负载分配策略。提出的算法将被设计为易于在现有的开源负载平衡器中采用，包括Apache， HAProxy和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.