UDRF: Multi-resource Fairness for Complex Jobs with Placement Constraints
File(s)
Published version
Author(s)
Tahir
Yang
Koliousis
McCann
Type
Conference Paper
Abstract
In this paper, we study the problem of multi- resource fairness in systems running complex jobs that consist of multiple interconnected tasks. A job is considered finished when all its corresponding tasks have been executed in the system. Tasks can have different resource requirements. Because of special demands on particular hardware or software, tasks may have placement constraints limiting the type of machines they can run on. We develop User-Dependence Dominant Resource Fairness (UDRF), a generalized version of max-min fairness that combines graph theory and the notion of dominant re- source shares to ensure multi-resource fairness between complex workflows. UDRF satisfies several desirable properties including strategy proofness, which ensures that users do not benefit from misreporting their true resource demands. We propose an offline algorithm that computes optimal UDRF allocation. But optimality comes at a cost, especially for systems where schedulers need to make thousands of online scheduling decisions per second. Therefore, we develop a lightweight online algorithm that closely approximates UDRF. Besides that, we propose a simple mechanism to decentralize the UDRF scheduling process across multiple schedulers. Large-scale simulations driven by Google cluster-usage traces show that UDRF achieves better resource utilization and throughput compared to the current state-of-the-art in fair resource allocation.
Date Issued
2015-12-10
Date Acceptance
2015-07-02
Citation
2015 IEEE Global Communications Conference (GLOBECOM), 2015, pp.1-7
Publisher
IEEE
Start Page
1
End Page
7
Journal / Book Title
2015 IEEE Global Communications Conference (GLOBECOM)
Copyright Statement
© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Source
IEEE GLOBECOM 2015
Publication Status
Published
Start Date
2015-12-06
Finish Date
2015-12-10
Coverage Spatial
San Diego, CA