research-article

Public Access

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling

Authors:

Hamidreza Jahanjou,

Rajmohan RajaramanAuthors Info & Claims

SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 45 - 54

https://doi.org/10.1145/3087556.3087567

Published: 24 July 2017 Publication History

Abstract

Many modern datacenter applications involve large-scale computations composed of multiple data flows that need to be completed over a shared set of distributed resources. Such a computation completes when all of its flows complete. A useful abstraction for modeling such scenarios is a coflow, which is a collection of flows (e.g., tasks, packets, data transmissions) that all share the same performance goal. In this paper, we present the first approximation algorithms for scheduling coflows over general network topologies with the objective of minimizing total weighted completion time. We consider two different models for coflows based on the nature of individual flows: circuits, and packets. We design constant-factor polynomial-time approximation algorithms for scheduling packet-based coflows with or without given flow paths, and circuit-based coflows with given flow paths. Furthermore, we give an O(log n/log log n)-approximation polynomial time algorithm for scheduling circuit-based coflows without given flow paths (here n is the number of network edges).

We obtain our results by developing a general framework for coflow schedules, based on interval-indexed linear programs, which may extend to other coflow models and objective functions and may also yield improved approximation bounds for specific network scenarios. We also present an experimental evaluation of our approach for circuit-based coflows that show a performance improvement of at least %22 on average over competing heuristics.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. x0--13--617549-X

[2]

M. Al-Fares, S. Radhakrishnan, B Raghavan, N. Huang, and A. Vahdat. 2010. Hedera: Dynamic Flow Scheduling for Data Center Networks. In NSDI.

Digital Library

[3]

Mohammad Al-Fares, Sivasankar Radhakrishnan, Barath Raghavan, Nelson Huang, and Amin Vahdat. 2010. Hedera: Dynamic Flow Scheduling for Data Center Networks. In USENIX.

[4]

J. D. Blocher and D. Chhajed. 1996. The customer order lead-time problem on parallel machines. Naval Research Logistics 43, 5 (1996).

[5]

M. Chowdhury and I. Stoica. 2012. Coflow: A Networking Abstraction for Cluster Applications. In HotNets.

Digital Library

[6]

M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica. 2011. Managing data transfers in computer clusters with orchestra. In SIGCOMM.

Digital Library

[7]

M. Chowdhury, Y. Zhong, and I. Stoica. 2014. Efficient Coflow Scheduling with Varys. SIGCOMM, Comput. Commun. Rev. 44, 4 (2014).

Digital Library

[8]

J. Chuzhoy, V. Guruswami, S. Khanna, and K. Talwar. 2007. Hardness of routing with congestion in directed graphs. In STOC.

Digital Library

[9]

José R. Correa, Martin Skutella, and José Verschae. 2009. The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders. Springer Berlin Heidelberg, Berlin, Heidelberg, 84--97. x978--3--642-03685--9 https://doi.org/10.1007/978--3--642-03685--9_7

[10]

J. Dean and S. Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM 51, 1 (2008).

Digital Library

[11]

N. Garg, A. Kumar, and V. Pandit. 2007. Order Scheduling Models: Hardness and Algorithms. In FSTTCS.

[12]

R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. 1979. Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Discrete Mathematics, Vol. 5.

[13]

C. Hong, M. Caesar, and B. Godfrey. Finishing flows quickly with preemptive scheduling. In ACM Conference, SIGCOMM.

Digital Library

[14]

M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. In Proc. of the EuroSys Conference.

Digital Library

[15]

S. Khuller and M. Purohit. 2016. Improved Approximation Algorithms for Scheduling Co-Flows. In SPAA. Brief Announcement.

[16]

R. Koch, B. Peis, M. Skutella, and A.s Wiese. 2009. Real-Time Message Routing and Scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Seince, Vol. 5687.

[17]

Jr. L. R. Ford and D. R. Fulkerson. 1958. Constructing Maximal Dynamic Flows from Static Flows. Operations Research 6, 3 (1958).

[18]

J. Labetoulle, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. 1984. Preemptive Scheduling of Uniform Machines Subject to Release Dates. In Progress in Combinatorial Optimization, William R. Pulleyblank (Ed.). Academic Press.

[19]

F.T. Leighton, B.M. Maggs, and S.B. Rao. 1994. Packet routing and job-shop scheduling in O(congestion+dilation) steps. Combinatorica (1994).

[20]

F. T. Leighton, B.M. Maggs, and A.W. Richa. 1999. Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules. Combinatorica 19, 3 (1999).

[21]

J. Y-T. Leung, H. Li, and M. Pinedo. 2005. Order Scheduling Models: An Overview.

[22]

B. Peis, M. Skutella, and A. Wiese. 2009. Packet Routing: Complexity and Algorithms. In WAOA.

[23]

Z. Qiu, C. Stein, and Y. Zhong. 2015. Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks. In SPAA.

Digital Library

[24]

M. Queyranne and M. Sviridenko. 2002. Approximation Algorithms for Shop Scheduling Problems with Minsum Objective. Journal of Scheduling (2002).

[25]

P. Raghavan and C. Thompson. 1987. Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs. Combinatorica 7 (1987).

Digital Library

[26]

A Srinivasan and C.-P. Teo. 2001. A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria. SIAM J. Comput. 30, 6 (2001).

Digital Library

[27]

M. Zaharia, M Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. 2010. Spark: Cluster Computing with Working Sets. In HotCloud.

Digital Library

[28]

D. Zats, T. Das, P. Mohan, D. Borthakur, and R. H. Katz. 2012. DeTail: reducing the flow completion time tail in datacenter networks. In SIGCOMM.

Digital Library

[29]

Y. Zhao, K. Chen, W. Bai, M. Yu, C. Tian, Y. Geng, Y. Zhang, D. Li, and S. Wang. 2015. Rapier: Integrating routing and scheduling for coflow-aware data center networks. In INFOCOM.

Cited By

Liu HDing FWang YXiang QShu JDu HKong LLiu X(2023)What Appears Suboptimal May Surprise You: A Fixed-Rate Scheduling Policy for Geo-Distributed CoFlows2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00192(1342-1349)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00192
Shafiee MGhaderi J(2022)Scheduling Coflows With Dependency GraphIEEE/ACM Transactions on Networking10.1109/TNET.2021.311613330:1(450-463)Online publication date: Mar-2022
https://doi.org/10.1109/TNET.2021.3116133
Mao RAggarwal V(2021)NPSCS: Non-Preemptive Stochastic Coflow Scheduling With Time-Indexed LP RelaxationIEEE Transactions on Network and Service Management10.1109/TNSM.2021.305165718:2(2377-2387)Online publication date: Jun-2021
https://doi.org/10.1109/TNSM.2021.3051657
Show More Cited By

Index Terms

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling
1. Networks
  1. Network algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms

Recommendations

Approximation algorithms for multiprocessor scheduling under uncertainty
SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor ...
Approximation algorithms for parallel machine scheduling with linear deterioration

This paper deals with a parallel machine scheduling problem. Different from fixed processing time assumption in the classical scheduling, a job's processing time is a simple linear increasing function of its starting time. The aim is makespan ...
Approximation Algorithms for Multiprocessor Scheduling under Uncertainty
Special Title: Parallelism on Algorithms and Architectures (SPAA); Guest Editors: Cyril Gavoille, Boaz Patt-Shamir and Christian Scheideler

Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

July 2017

392 pages

ISBN:9781450345934

DOI:10.1145/3087556

General Chair:
Christian Scheideler
Paderborn University, Germany
,
Program Chair:
Mohammad Hajiaghayi
University of Maryland at College Park, USA

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 ACM 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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

coflows

Qualifiers

Research-article

Funding Sources

Google
NSF

Conference

SPAA '17

Sponsor:

SPAA '17: 29th ACM Symposium on Parallelism in Algorithms and Architectures

July 24 - 26, 2017

DC, Washington, USA

Acceptance Rates

SPAA '17 Paper Acceptance Rate 31 of 127 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
313
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)16

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu HDing FWang YXiang QShu JDu HKong LLiu X(2023)What Appears Suboptimal May Surprise You: A Fixed-Rate Scheduling Policy for Geo-Distributed CoFlows2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00192(1342-1349)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00192
Shafiee MGhaderi J(2022)Scheduling Coflows With Dependency GraphIEEE/ACM Transactions on Networking10.1109/TNET.2021.311613330:1(450-463)Online publication date: Mar-2022
https://doi.org/10.1109/TNET.2021.3116133
Mao RAggarwal V(2021)NPSCS: Non-Preemptive Stochastic Coflow Scheduling With Time-Indexed LP RelaxationIEEE Transactions on Network and Service Management10.1109/TNSM.2021.305165718:2(2377-2387)Online publication date: Jun-2021
https://doi.org/10.1109/TNSM.2021.3051657
Benet CKassler AAntichi GBenson TPongracz G(2021)Providing In-network Support to Coflow Scheduling2021 IEEE 7th International Conference on Network Softwarization (NetSoft)10.1109/NetSoft51509.2021.9492530(235-243)Online publication date: 28-Jun-2021
https://doi.org/10.1109/NetSoft51509.2021.9492530
Jahanjou HRajaraman RStalfa DScheideler CSpear M(2020)Scheduling Flows on a Switch to Optimize Response TimesProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400218(305-315)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400218
Zeng YYe BTang BGuo SQu Z(2020)Scheduling coflows of multi-stage jobs under network resource constraintsComputer Networks10.1016/j.comnet.2020.107686(107686)Online publication date: Nov-2020
https://doi.org/10.1016/j.comnet.2020.107686
Wang ZZhang HShi XGeng HLi YYin XLiu JWu Q(2019)Efficient Scheduling of Weighted Coflows in Data CentersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.2905560(1-1)Online publication date: 2019
https://doi.org/10.1109/TPDS.2019.2905560
Agarwal SRajakrishnan SNarayan AAgarwal RShmoys DVahdat AGorinsky STapolcai J(2018)SincroniaProceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication10.1145/3230543.3230569(16-29)Online publication date: 7-Aug-2018
https://dl.acm.org/doi/10.1145/3230543.3230569
Wang SZhang JHuang TLiu JPan TLiu Y(2018)A Survey of Coflow Scheduling Schemes for Data Center NetworksIEEE Communications Magazine10.1109/MCOM.2017.170026756:6(179-185)Online publication date: Jun-2018
https://doi.org/10.1109/MCOM.2017.1700267

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents