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

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.