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