IEEE/ACM Transactions on Networking · 2019 · 40 citations · 53 references
ComputingComputer EngineeringComputer ScienceComputer NetworksParallel AlgorithmsParallel ComputingNetwork Flow AlgorithmsParallel Computing SystemsResource SchedulingRoutingRouting AlgorithmsBandwidthCo-schedulingCompetitive RatioFlow SchedulingNetwork ResourcesParallel Flow AlgorithmsRandomized Approximation AlgorithmsRandomized Rounding
A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage computing task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the total weighted coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources, such as link bandwidth. To minimize the total weighted CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow. We then derive a competitive ratio bound of our problem and prove that the competitive ratio of OMCoflow is nearly tight. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently and avoids frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the total weighted CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER).
53
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
TensorFlow: A system for large-scale machine learning
Martı́n Abadi, Paul Barham, Jianmin Chen et al. · arXiv (Cornell University) · 2016 · 8.8K citations · Full text
TensorFlow: a system for large-scale machine learning
Martı́n Abadi, Paul Barham, Jianmin Chen et al. · Operating Systems Design and Implementation · 2016 · 6.4K citations
Spark: cluster computing with working sets
Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin et al. · 2010 · 4.2K citations