Efficient coflow scheduling with Varys
Authors:
Open Access
- 17 August 2014
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 44 (4) , 443-454
Abstract
Communication in data-parallel applications often involves a collection of parallel flows. Traditional techniques to optimize flow-level metrics do not perform well in optimizing such collections, because the network is largely agnostic to application-level requirements. The recently proposed coflow abstraction bridges this gap and creates new opportunities for network scheduling. In this paper, we address inter-coflow scheduling for two different objectives: decreasing communication time of data-intensive jobs and guaranteeing predictable communication time. We introduce the concurrent open shop scheduling with coupled resources problem, analyze its complexity, and propose effective heuristics to optimize either objective. We present Varys, a system that enables data-intensive frameworks to use coflows and the proposed algorithms while maintaining high network utilization and guaranteeing starvation freedom. EC2 deployments and trace-driven simulations show that communication stages complete up to 3.16X faster on average and up to 2X more coflows meet their deadlines using Varys in comparison to per-flow mechanisms. Moreover, Varys outperforms non-preemptive coflow schedulers by more than 5X.Keywords
Funding Information
- Division of Computing and Communication Foundations (CCF-1139158)
- LBNL Award (7076018)
- Amazon Web Services Google SAP The Thomas and Stacey Siebel Foundation Apple Inc. Cisco Cloudera EMC Ericsson Facebook (Gift for the AMPLab)
- Defense Advanced Research Projects Agency (FA8750-12-2-0331)
This publication has 22 references indexed in Scilit:
- pFabric2013
- Coflow2012
- MicroTE2011
- Towards predictable datacenter networks2011
- Managing data transfers in computer clusters with orchestra2011
- Minimizing the sum of weighted completion times in a concurrent open shopOperations Research Letters, 2010
- SCOPEProceedings of the VLDB Endowment, 2008
- A note on the complexity of the concurrent open shop problemJournal of Scheduling, 2006
- Achieving 100% throughput in an input-queued switchIEEE Transactions on Communications, 1999
- A bridging model for parallel computationCommunications of the ACM, 1990