EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4228. Affinity Aware Scheduling in Distributed Computing via Vector Bin Packing

Invited abstract in session WB-26: Combinatorial Optimization in Scheduling, stream Combinatorial Optimization.

Wednesday, 10:30-12:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Natalia Shakhlevich
School of Computing, University of Leeds
2. Thomas Erlebach
University of Durham
3. Clément Mommessin
IMT Atlantique Nantes
4. Renyu Yang
Beihang University
5. Xiaoyang Sun
University of Leeds
6. Satish Kumar
School of Built Environment, Engineering, and Computing, Leeds Beckett University
7. Junqing Xiao
Alibaba Group
8. Jie Xu
University of Leeds

Abstract

The problem of allocating long-running applications (LRAs) to cloud resources can be modelled as vector bin packing (VBP) with additional compatibility constraints. In that problem, cloud compute nodes correspond to bins and LRAs to items. The multidimensional nature of the problem is associated with characteristics of bins and items, such as CPU cores, RAM, GPUs, etc. Planning resource allocation can be performed before LRA deployment and it is aimed at minimizing the number of nodes to which LRAs are allocated. In our study, we model affinity restrictions on LRA deployment. They are defined for pairs of LRAs which replicas can be jointly co-located to the same node, but with some limits, or for pairs of incompatible LRAs, which cannot be co-located. In our work, we explore a broad range of VBP heuristics capable of producing high quality solutions to the affinity-aware version of the problem and find a solution within acceptable time. The findings are supported by extensive computational experiments performed on the Alibaba Tianchi dataset.

Keywords

Status: accepted

Back to the list of papers