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

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

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.