research-article

Exploiting Inter-Flow Relationship for Coflow Placement in Datacenters

Authors:

Xin Sunny Huang,

T. S. Eugene NgAuthors Info & Claims

APNet '17: Proceedings of the First Asia-Pacific Workshop on Networking

Pages 113 - 119

https://doi.org/10.1145/3106989.3107004

Published: 03 August 2017 Publication History

Abstract

A crucial challenge for data-parallel clusters is achieving high application-level communication efficiency for structured traffic flows (a.k.a. Coflows) from distributed data processing applications. A range of recent works focus on designing network scheduling algorithms with predetermined Coflow placement, i.e. the endpoints of subflows within a Coflow are preset. However, the underlying Coflow placement problem and its decisive impact on scheduling efficiency have long been overlooked.

It is hard to find good placements for Coflows. At the intra-Coflow level, constituent flows are related and therefore their placement decisions are dependent. Thus, strategies extended from flow-by-flow placement is sub-optimal due to negligence of the inter-flow relationship in a Coflow. At the inter-Coflow level, placing a new Coflow may introduce contentions with existing Coflows, which changes communication efficiency. This paper is the first to study the Coflow placement problem with careful considerations of the inter-flow relationship in Coflows. We formulate the Coflow placement problem and propose a Coflow placement algorithm. Under realistic traffic in various settings, our algorithm reduces the average completion time for Coflows by up to 26%.

References

[1]

2014. Coflow Benchmark Based on Facebook Traces. (2014). https://github.com/coflow/coflow-benchmark.

[2]

2017. 2D-Placement simulator. (2017). https://github.com/sunnyxhuang/2D-Placement.

[3]

Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. 2008. A scalable, commodity data center network architecture. In SIGCOMM '08.

Digital Library

[4]

Mosharaf Chowdhury and Ion Stoica. 2012. Coflow: A networking abstraction for cluster applications. In HotNets '12.

Digital Library

[5]

Mosharaf Chowdhury and Ion Stoica. 2015. Efficient Coflow Scheduling without Prior Knowledge. In SIGCOMM '15.

Digital Library

[6]

Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. 2014. Efficient coflow scheduling with Varys. In SIGCOMM '14.

Digital Library

[7]

Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. 2014. Multi-resource packing for cluster schedulers. In SIGCOMM '14.

Digital Library

[8]

Robert Grandl, Mosharaf Chowdhury, Aditya Akella, and Ganesh Ananthanarayanan. 2016. Altruistic Scheduling in Multi-Resource Clusters. In OSDI '16.

Digital Library

[9]

Albert Greenberg, James R Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A Maltz, Parveen Patel, and Sudipta Sengupta. 2009. VL2: A scalable and flexible data center network. In SIGCOMM '09.

Digital Library

[10]

Xin Sunny Huang, Xiaoye Steven Sun, and T. S. Eugene Ng. 2016. Sunflow: Efficient Optical Circuit Scheduling for Coflows. In CoNEXT '16.

[11]

Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, and Andrew Goldberg. 2009. Quincy: fair scheduling for distributed computing clusters. In SOSP '09.

Digital Library

[12]

Virajith Jalaparti, Peter Bodik, Ishai Menache, Sriram Rao, Konstantin Makarychev, and Matthew Caesar. 2015. Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can. In SIGCOMM '15.

Digital Library

[13]

Shouxi Luo, Hongfang Yu, Yangming Zhao, Sheng Wang, Shui Yu, and Lemin Li. 2016. Towards Practical and Near-optimal Coflow Scheduling for Data Center Networks. In IEEE TPDS '16.

Digital Library

[14]

Ali Munir, Ting He, Ramya Raghavendra, Franck Le, and Alex X. Liu. 2016. Network Scheduling Aware Task Placement in Datacenters. In CoNEXT '16.

Digital Library

[15]

Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, and John Wilkes. 2015. Large-scale cluster management at Google with Borg. In EuroSys '15.

Digital Library

[16]

Hong Zhang, Li Chen, Bairen Yi, Kai Chen, Mosharaf Chowdhury, and Yanhui Geng. 2016. CODA: Toward Automatically Identifying and Scheduling Coflows in the Dark. In SIGCOMM '16.

Digital Library

Cited By

Wang XXu SZhao Y(2024)SARS: Towards minimizing average Coflow Completion Time in MapReduce systemsComputer Networks10.1016/j.comnet.2024.110429247(110429)Online publication date: Jun-2024
https://doi.org/10.1016/j.comnet.2024.110429
Oubaydallah YIbrahimi KAzouzi R(2023)Recent Advances in Data Intensive Applications: Survey2023 10th International Conference on Wireless Networks and Mobile Communications (WINCOM)10.1109/WINCOM59760.2023.10322920(1-6)Online publication date: 26-Oct-2023
https://doi.org/10.1109/WINCOM59760.2023.10322920
Wang LWang XTornatore MKim KMukherjee B(2022)Coflow scheduling and placement for packet-switched optical datacenter networksPhotonic Network Communications10.1007/s11107-021-00958-443:2(156-164)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11107-021-00958-4
Show More Cited By

Index Terms

Exploiting Inter-Flow Relationship for Coflow Placement in Datacenters
1. Networks
  1. Network algorithms
    1. Control path algorithms
      1. Network resources allocation
  2. Network types
    1. Data center networks

Recommendations

Network Scheduling Aware Task Placement in Datacenters
CoNEXT '16: Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies

To improve the performance of data-intensive applications, existing datacenter schedulers optimize either the placement of tasks or the scheduling of network flows. The task scheduler strives to place tasks close to their input data (i.e., maximize data ...
Sunflow: Efficient Optical Circuit Scheduling for Coflows
CoNEXT '16: Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies

Optical Circuit Switches (OCS) are increasingly used in cluster networks due to their data rate, energy and longevity advantages over electrical packet switches. Concurrently, an emerging crucial requirement for modern data-parallel clusters is to ...
Semi-Distributed Coflow Scheduling in Datacenters
With the advent of big data applications, coflow scheduling has become a cornerstone for the engineering of traffic in datacenters. Minimizing the average weighted Coflow Completion Times (CCT) is a crucial step to minimize the execution time of jobs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

APNet '17: Proceedings of the First Asia-Pacific Workshop on Networking

August 2017

127 pages

ISBN:9781450352444

DOI:10.1145/3106989

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 August 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

APNet'17

APNet'17: First Asia-Pacific Workshop on Networking

August 3 - 4, 2017

Hong Kong, China

Acceptance Rates

Overall Acceptance Rate 50 of 118 submissions, 42%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
97
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang XXu SZhao Y(2024)SARS: Towards minimizing average Coflow Completion Time in MapReduce systemsComputer Networks10.1016/j.comnet.2024.110429247(110429)Online publication date: Jun-2024
https://doi.org/10.1016/j.comnet.2024.110429
Oubaydallah YIbrahimi KAzouzi R(2023)Recent Advances in Data Intensive Applications: Survey2023 10th International Conference on Wireless Networks and Mobile Communications (WINCOM)10.1109/WINCOM59760.2023.10322920(1-6)Online publication date: 26-Oct-2023
https://doi.org/10.1109/WINCOM59760.2023.10322920
Wang LWang XTornatore MKim KMukherjee B(2022)Coflow scheduling and placement for packet-switched optical datacenter networksPhotonic Network Communications10.1007/s11107-021-00958-443:2(156-164)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11107-021-00958-4
Zhao YTian CFan JGuan TZhang XQiao C(2021)Joint Reducer Placement and Coflow Bandwidth Scheduling for Computing ClustersIEEE/ACM Transactions on Networking10.1109/TNET.2020.303706429:1(438-451)Online publication date: 16-Feb-2021
https://dl.acm.org/doi/10.1109/TNET.2020.3037064
Wu Z(2021)Joint Coflow Optimization for Data Center NetworksIEEE Access10.1109/ACCESS.2021.31020679(108402-108410)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3102067
Zhao YTian CFan JGuan TQiao C(2018)RPC: Joint Online Reducer Placement and Coflow Bandwidth Scheduling for Clusters2018 IEEE 26th International Conference on Network Protocols (ICNP)10.1109/ICNP.2018.00028(187-197)Online publication date: Sep-2018
https://doi.org/10.1109/ICNP.2018.00028
Tang WWang SLi DHuang TDou WYu S(2018)A Deadline-Aware Coflow Scheduling Approach for Big Data Applications2018 IEEE International Conference on Communications (ICC)10.1109/ICC.2018.8422563(1-6)Online publication date: May-2018
https://doi.org/10.1109/ICC.2018.8422563

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents