Efficient Coflow Scheduling with Varys

Communication in data-parallel applications often involves a col-lection 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 require-ments. The recently proposed coflow abstraction bridges this gap and creates new opportunities for network scheduling. In this pa-per, we address inter-coflow scheduling for two different objec-tives: 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 opti-mize either objective. We present Varys, a system that enables data-intensive frameworks to use coflows and the proposed algo-rithms while maintaining high network utilization and guarantee-ing starvation freedom. EC2 deployments and trace-driven simula-tions show that communication stages complete up to 3:16 faster on average and up to 2 more coflows meet their deadlines us-ing Varys in comparison to per-flow mechanisms. Moreover, Varys outperforms non-preemptive coflow schedulers by more than 5