Coflow Deadline Scheduling via Network-Aware Optimization
Authors:
- 1 October 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 829-833
Abstract
Several cloud or data-parallel applications involve coflow scheduling, which controls a set of flows under the same semantic meaning with a common goal. Due to such common goal, optimizing each flow using the standard flow scheduling approaches does not necessarily lead to good coflow performance. Therefore, numerous methods and systems are proposed to focus on coflow scheduling problem. However, the current coflow scheduling designs are based on simple heuristics or observations. The absence of the optimum makes it hard to adjudge their absolute effectiveness. In this work, we derive the optimal solution to the coflow deadline satisfaction problem (CDS), which maximizes the number of satisfied coflow deadlines, from a mixed integer linear program formulation. We further show that CDS is not only NP-hard to solve but also intractable to approximate with a fixed approximation ratio (unless P=NP). As such, the use of heuristics is justified. We then develop optimization-based methods to approach the problem offline and online. The proposed methods are simulated and compared against the optimum, along with some state-of-the-art designs, and the results suggest that our methods are much closer to the optimum than the existing ones, especially when we have more room to schedule.Keywords
This publication has 18 references indexed in Scilit:
- Rapier: Integrating routing and scheduling for coflow-aware data center networks2015
- Decentralized task-aware scheduling for data center networksACM SIGCOMM Computer Communication Review, 2014
- Efficient coflow scheduling with VarysACM SIGCOMM Computer Communication Review, 2014
- Deadline-aware datacenter tcp (D2TCP)ACM SIGCOMM Computer Communication Review, 2012
- Managing data transfers in computer clusters with orchestraACM SIGCOMM Computer Communication Review, 2011
- Better never than lateACM SIGCOMM Computer Communication Review, 2011
- HiveProceedings of the VLDB Endowment, 2009
- MapReduceCommunications of the ACM, 2008
- DryadACM SIGOPS Operating Systems Review, 2007
- Why flow-completion time is the right metric for congestion controlACM SIGCOMM Computer Communication Review, 2006