Leveraging Endpoint Flexibility when Scheduling Coflows across Geo-distributed Datacenters
Authors: 
Wenxin Li, Xu Yuan, Keqiu Li, Heng Qi, Xiaobo ZhouAuthors Info & Claims
Pages 873 - 881
Abstract
Coflow scheduling is crucial to improve the communication performance of data-parallel jobs, especially when these jobs running in the inter-datacenter networks with limited and heterogeneous link bandwidth. However, prior solutions on coflow scheduling assume the endpoints of flows in a coflow to be fixed, making them insufficient to optimize the coflow completion time (CCT). In this paper, we focus on the problem of jointly considering endpoint placement and coflow scheduling to minimize the average CCT of coflows across geo-distributed datacenters. We first develop the mathematical model and formulate a mixed integer linear programming (MILP) problem to characterize the intertwined relationship between endpoint placement and coflow scheduling, and reveal their impact on the average CCT. Then, we present SmartCoflow, a coflow-aware optimization framework, to solve the MILP problem without any prior knowledge of coflow arrivals. In SmartCoflow, we first apply an approximate algorithm to obtain the endpoint placement and scheduling decisions for a single coflow. Based on the single-coflow solution, we then develop an efficient online algorithm to handle the dynamically arrived coflows. To validate the efficiency and practical feasibility of SmartCoflow, we implement it as a real-world coflow scheduler based on the Varys open-source framework. Through experimental results from both a small-scale testbed implementation and large-scale simulations, we demonstrate that SmartCoflow can achieve significant improvement on the average CCT, when compared to the state-of-the-art scheduling-only method.
References
[1]
Q. Pu, G. Ananthanarayanan, P. Bodik, S. Kandula, A. Akella, P. Bahl, and I. Stoica, “Low latency geo-distributed data analytics”, in Proc. of ACM SIGCOMM, 2015.
[2]
C.-C. Hung, L. Golubchik, and M. Yu, “Scheduling jobs across geo-distributed datacenters”, in Proc. of ACM SoCC, 2015.
[3]
R. Viswanathan, G. Ananthanarayanan, and A. Akella, “Clarinet: Wan-aware optimization for analytics queries”, in Proc. of USENIX OSDI, 2016.
[4]
M. Chowdhury and I. Stoica, “Coflow: A networking abstraction for cluster applications”, in Proc. of ACM Workshop on Hot Topics in Networks, 2012.
[5]
K. Hsieh, A. Harlap, N. Vijaykumar, D. Konomis, G. R. Ganger, P. B. Gibbons, and O. Mutlu, “Gaia: Geo-distributed machine learning approaching lan speeds”. in Proc. of NSDI, 2017.
[6]
Z. Hu, B. Li, and J. Luo, “Flutter: Scheduling tasks closer to data across geo-distributed datacenters”, in Proc. of IEEE INFOCOM, 2016.
[7]
M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica, “Managing data transfers in computer clusters with orchestra”, in Proc. of ACM SIGCOMM, Toronto, Canada, 2011.
[8]
Y. Zhao, K. Chen, W. Bai, C. Tian, Y. Geng, Y. Zhang, D. Li, and S. Wang, “Rapier: Integrating routing and scheduling for coflow-aware data center networks”, in Proc. of IEEE INFOCOM, HK, 2015.
[9]
M. Chowdhury, Y. Zhong, and I. Stoica, “Efficient coflow scheduling with varys”, in Proc. of ACM SIGCOMM, Chicago, IL, USA, 2014.
[10]
M. Chowdhury and I. Stoica, “Efficient coflow scheduling without prior knowledge”, in Proc. of ACM SIGCOMM, 2015.
[11]
H. Zhang, L. Chen, B. Yi, K. Chen, M. Chowdhury, and Y. Geng, “Coda: Toward automatically identifying and scheduling coflows in the dark”, in Proc. of ACM SIGCOMM, 2016.
[12]
Y. Li, S. H.-C. Jiang, H. Tan, C. Zhang, G. Chen, J. Zhou, and F. Lau, “Efficient online coflow routing and scheduling”, in Proc. of ACM MobiHoc, 2016.
[13]
“Varys: Efficient clairvoyant coflow scheduler”. [Online]. Available: https://github.com/cofiow/varys.
[14]
W. Wang, S. Ma, B. Li, and B. Li, “Coflex: Navigating the fairness-efficiency tradeoff for coflow scheduling”, in Proc. of IEEE INFOCOM, 2017.
[15]
M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica, “Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing”, in Proc. of USENIX NSDI, 2012.
[16]
S. Venkataraman, A. Panda, G. Ananthanarayanan, M. J. Franklin, and I. Stoica, “The power of choice in data-aware cluster scheduling”. in Proc. of USENIX OSDI, 2014.
[17]
J. K. Karlof, Integer programming: theory and practice. CRC Press, 2005.
[18]
E. D. Andersen and K. D. Andersen, “The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm”, in High performance optimization. Springer, 2000, pp. 197–232.
[19]
“Breeze: A numerical processing library for scala”. [Online]. Available: http://www.scalanlp.org.
[20]
“Flow-level simulator for coflow scheduling used in varys and aalo”. [Online]. Available: https://github.com/coflow/cofiowsim.
[21]
C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer, “Achieving high utilization with software-driven wan”, in Proc. of ACM SIGCOMM, 2013.
[22]
“Synthesized data from real-world traces of data-intensive applications for coflow benchmarking”. [Online]. Available: https://github.com/coflow/coflow-benchmark.
[23]
M. Chowdhury, S. Kandula, and I. Stoica, “Leveraging endpoint fiexi-bility in data-intensive clusters”, in Proc. of ACM SIGCOMM, 2013.
[24]
F. Ahmad, S. T. Chakradhar, A. Raghunathan, and T. Vijaykumar, “Shufflewatcher: Shuffie-aware scheduling in multi-tenant mapreduce clusters”, in Proc. of USENIX ATC, 2014.
[25]
V. Jalaparti, P. Bodik, I. Menache, S. Rao, K. Makarychev, and M. Caesar, “Network-aware scheduling for data-parallel jobs: Plan when you can”, in Proc. of ACM SIGCOMM, 2015.
[26]
L. Chen, S. Liu, B. Li, and B. Li, “Scheduling jobs across geo-distributed datacenters with max-min fairness”, in Proc. of IEEE INFOCOM, 2017.
[27]
L. Chen, W. Cui, B. Li, and B. Li, “Optimizing coflow completion times with utility max-min fairness”, in Proc. of IEEE INFOCOM, 2016.
Index Terms
- Leveraging Endpoint Flexibility when Scheduling Coflows across Geo-distributed Datacenters
Index terms have been assigned to the content through auto-classification.
Recommendations
Scheduling jobs across geo-distributed datacenters
SoCC '15: Proceedings of the Sixth ACM Symposium on Cloud ComputingWith growing data volumes generated and stored across geo-distributed datacenters, it is becoming increasingly inefficient to aggregate all data required for computation at a single datacenter. Instead, a recent trend is to distribute computation to ...
Scheduling dependent coflows to minimize the total weighted job completion time in datacenters
AbstractDatacenter networks are critical to cloud computing. The coflow abstraction is a major leap forward of application-aware network scheduling. In the context of multi-stage jobs, there are dependencies among coflows. As a result, there is a large ...
On Scheduling Coflows
AbstractApplications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Apr 2018
2776 pages
Copyright © 2018.
Publisher
IEEE Press
Publication History
Published: 16 April 2018
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024