2021/12/05 by Hailiang Zhao, Zhao, Hailiang, Shuiguang Deng +7
Computer Science · #Age of Information Optimization #Cloud Computing and Resource Management #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2112.02456
openalex publication_date 2021/12/05 · openalex created_date 2023/02/13 · openalex updated_date 2026/07/28
Multi-server jobs are imperative in modern computing clusters. A multi-server job has multiple task components and each of the task components is responsible for processing a specific size of workloads. Efficient online workload dispatching is crucial but challenging to co-located heterogeneous multi-server jobs. The dispatching policy should decide (i) where to launch each task component instance of the arrived jobs and (ii) the size of workloads that each task component processes. Existing policies are explicit and effective when facing service locality and resource contention in both offline and online settings. However, when adding the deadline-aware constraint, the theoretical superiority of these policies could not be guaranteed. To fill the theoretical gap, in this paper, we design an α-competitive online workload dispatching policy for deadline-aware multi-server jobs based on the spatio-temporal resource mesh model. We formulate the problem as a social welfare maximization program and solve it online with several well designed pseudo functions. The social welfare is formulated as the sum of the utilities of jobs and the utility of the computing cluster. The proposed policy is rigorously proved to be α-competitive for some α≥ 2. We also validate the theoretical superiority of it with simulations and the results show that it distinctly outperforms two handcrafted baseline policies on the social welfare.