CIF: Small: Load Balancing for Cloud Networks: Data Locality Issues and Modern Algorithms

CIF：小型：云网络的负载平衡：数据局部性问题和现代算法

• 批准号: 2113027
• 负责人: Debankur Mukherjee
• 金额: $ 42.32万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2113027&HistoricalAwards=false
• 关键词: CIF; Small; Load; Balancing; Cloud

Distributing incoming tasks among the back-end servers or virtual machines in a balanced way is crucial for the seamless functioning of large-scale service systems, such as data centers and cloud networks. As the bulk of modern applications now tend to come with specialized service requirements, these systems are suffering from stringent task-server compatibility constraints arising due to data locality. In simple terms, it means that the resources to process a particular type of task are available to only a small sub-collection of servers and cannot be accessed by the entire network. This issue of task-server compatibility has made large-scale load balancing ever more challenging. State-of-the-art heuristics are predominantly based on "full-flexibility" models that ignore the compatibility aspect and assume that any task can be processed by any server. Naturally, algorithms implemented from these heuristics cause a major adverse impact on the user-perceived delay performance. The current practice to deal with this problem is to find ad-hoc solutions in specific cases. With the investigator's expertise in the area of stochastic modeling and performance analysis, the project is taking a thorough and structured approach to address this issue. On successful completion, the findings will contribute to designing modern load balancing algorithms.The theoretical research agenda of the project is divided into two thrusts: (1) to identify classes of optimal compatibility constraints for existing algorithms, and (2) to develop novel compatibility-aware distributed algorithms for arbitrary systems. The research community has discovered several breakthrough load balancing algorithms over the last few years. These algorithms have excellent performance guarantees in the full-flexibility setup. The goal of Thrust 1 is to identify classes of compatibility constraints that can still preserve such performance guarantees under such existing algorithms. Employing these findings, a service provider can design compatibility structures that enjoy the performance benefits of a fully flexible system, by carefully placing the resource files across the servers. When designing the compatibility structure is not an option, state-of-the-art algorithms exhibit poor performance. In such cases, Thrust 2 aims to develop novel distributed algorithms with provable performance guarantees, that take the compatibility structure into consideration during task assignment. This part of the project is having direct consequences for the practitioners in implementing new algorithmic heuristics for modern systems. On the methodological side, the investigation requires the development of a theoretical foundation for the analysis of structurally constrained systems driven by stochastic inputs. The project is advancing the area of mean-field analysis, which has been a primary tool in the performance analysis of randomized algorithms for large-scale systems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

在后端服务器或虚拟机之间以平衡的方式分配传入任务对于数据中心和云网络等大规模服务系统的无缝运行至关重要。由于大部分现代应用程序现在往往带有专门的服务要求，这些系统正遭受严格的任务服务器兼容性约束，由于数据的本地性。简单地说，这意味着处理特定类型任务的资源仅可用于服务器的一小部分子集合，而不能被整个网络访问。这个任务服务器兼容性问题使得大规模负载平衡变得更加具有挑战性。最先进的代理主要基于“完全灵活”的模型，该模型忽略了兼容性方面，并假设任何任务都可以由任何服务器处理。当然，从这些算法实现的算法会对用户感知的延迟性能产生重大的不利影响。目前处理这一问题的做法是在具体情况下找到临时解决办法。凭借研究人员在随机建模和性能分析领域的专业知识，该项目正在采取彻底且结构化的方法来解决这个问题。该项目的理论研究议程分为两个重点：（1）为现有算法确定最佳兼容性约束类别，（2）为任意系统开发新的兼容性感知分布式算法。在过去的几年里，研究界已经发现了几种突破性的负载平衡算法。这些算法在全柔性设置中具有优异的性能保证。目标1是确定类的兼容性约束，仍然可以保持这样的性能保证在现有的算法。利用这些发现，服务提供商可以设计兼容性结构，享受一个完全灵活的系统的性能优势，通过仔细放置跨服务器的资源文件。当设计兼容性结构不是一种选择时，最先进的算法表现出较差的性能。在这种情况下，推力2的目标是开发新的分布式算法与可证明的性能保证，考虑到在任务分配的兼容性结构。该项目的这一部分对实践者在现代系统中实现新的算法算法有直接的影响。在方法论方面，调查需要发展的理论基础，结构约束系统的随机输入驱动的分析。该项目正在推进平均场分析领域，该领域一直是大规模系统随机算法性能分析的主要工具。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Scalable Load Balancing in Networked Systems: A Survey of Recent Advances

网络系统中的可扩展负载平衡：最新进展调查

• DOI: 10.1137/20m1323746
• 发表时间: 2022
• 期刊: SIAM Review
• 影响因子: 10.2
• 作者: der Boor, Mark Van;Borst, Sem C.;Van Leeuwaarden, Johan S.;Mukherjee, Debankur
• 通讯作者: Mukherjee, Debankur

Smoothed Online Optimization with Unreliable Predictions

• DOI: 10.1145/3579442
• 发表时间: 2022-02
• 期刊: Proceedings of the ACM on Measurement and Analysis of Computing Systems
• 作者: Daan Rutten;Nicolas H. Christianson;Debankur Mukherjee;A. Wierman

A New Approach to Capacity Scaling Augmented with Unreliable Machine Learning Predictions

通过不可靠的机器学习预测增强容量扩展的新方法

• DOI: 10.1287/moor.2023.1364
• 发表时间: 2023
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: Rutten, Daan;Mukherjee, Debankur
• 通讯作者: Mukherjee, Debankur

Self-Learning Threshold-Based Load Balancing

基于自学习阈值的负载平衡

• DOI: 10.1287/ijoc.2021.1100
• 发表时间: 2022
• 期刊: INFORMS Journal on Computing
• 影响因子: 2.1
• 作者: Goldsztajn, Diego;Borst, Sem C.;van Leeuwaarden, Johan S.;Mukherjee, Debankur;Whiting, Philip A.
• 通讯作者: Whiting, Philip A.

Load Balancing Under Strict Compatibility Constraints

严格兼容性约束下的负载均衡

• DOI: 10.1287/moor.2022.1258
• 发表时间: 2022
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: Rutten, Daan;Mukherjee, Debankur
• 通讯作者: Mukherjee, Debankur