Weighted Scheduling of Time-Sensitive Coflows
- 3 April 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Cloud Computing
- Vol. 12 (2) , 644-658
Abstract
Datacenter networks commonly facilitate the transmission of data in distributed computing frameworks through coflows, which are collections of parallel flows associated with a common task. Most of the existing research has concentrated on scheduling coflows to minimize the time required for their completion, i.e., to optimize the average dispatch rate of coflows in the network fabric. Nevertheless, modern applications often produce coflows that are specifically intended for online services and mission-crucial computational tasks, necessitating adherence to specific deadlines for their completion. In this paper, we introduce $\mathtt {WDCoflow}$ , a new algorithm to maximize the weighted number of coflows that complete before their deadline. By combining a dynamic programming algorithm along with parallel inequalities, our heuristic solution performs at once coflow admission control and coflow prioritization, imposing a $\sigma$ -order on the set of coflows. With extensive simulation, we demonstrate the effectiveness of our algorithm in improving up to $3\times$ more coflows that meet their deadline in comparison the best SoA solution, namely $\mathtt {CS\rm{-}MHA}$ . Furthermore, when weights are used to differentiate coflow classes, $\mathtt {WDCoflow}$ is able to improve the admission per class up to $4\times$ , while increasing the average weighted coflow admission rate.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- ELITE: Near-Optimal Heuristics for Coflow Scheduling2022
- On Scheduling CoflowsAlgorithmica, 2020
- Coflow Scheduling with Performance Guarantees for Data Center Applications2020
- Coflow Deadline Scheduling via Network-Aware Optimization2018
- Decentralized deadline-aware coflow scheduling for datacenter networks2016
- Chronos: Meeting coflow deadlines in data center networks2016
- Optimizing coflow completion times with utility max-min fairness2016
- Minimizing the sum of weighted completion times in a concurrent open shopOperations Research Letters, 2010
- Customer order scheduling to minimize the number of late jobsEuropean Journal of Operational Research, 2007
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979