Towards Practical and Near-Optimal Coflow Scheduling for Data Center Networks

Luo, S; Yu, H; Zhao, Y; Wang, S; Yu, S; Li, L

Towards Practical and Near-Optimal Coflow Scheduling for Data Center Networks

Luo, S Yu, H Zhao, Y Wang, S Yu, S

Li, L

Permalink

Publisher:: IEEE COMPUTER SOC
Publication Type:: Journal Article
Citation:: IEEE Transactions on Parallel and Distributed Systems, 2016, 27, (11), pp. 3366-3380
Issue Date:: 2016-11-01

Closed Access

	Filename	Description	Size
	Towards_Practical_and_Near-Optimal_Coflow_Scheduling_for_Data_Center_Networks.pdf	Published version	1.47 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Luo, S
dc.contributor.author	Yu, H
dc.contributor.author	Zhao, Y
dc.contributor.author	Wang, S
dc.contributor.author	Yu, S https://orcid.org/0000-0003-4485-6743
dc.contributor.author	Li, L
dc.date.accessioned	2022-07-31T01:17:45Z
dc.date.available	2022-07-31T01:17:45Z
dc.date.issued	2016-11-01
dc.identifier.citation	IEEE Transactions on Parallel and Distributed Systems, 2016, 27, (11), pp. 3366-3380
dc.identifier.issn	1045-9219
dc.identifier.issn	1558-2183
dc.identifier.uri	http://hdl.handle.net/10453/159410
dc.description.abstract	In current data centers, an application (e.g., MapReduce, Dryad, search platform, etc.) usually generates a group of parallel flows to complete a job. These flows compose a coflow and only completing them all is meaningful to the application. Accordingly, minimizing the average Coflow Completion Time (CCT) becomes a critical objective of flow scheduling. However, achieving this goal in today's Data Center Networks (DCNs) is quite challenging, not only because the schedule problem is theoretically NP-hard, but also because it is tough to perform practical flow scheduling in large-scale DCNs. In this paper, we find that minimizing the average CCT of a set of coflows is equivalent to the well-known problem of minimizing the sum of completion times in a concurrent open shop. As there are abundant existing solutions for concurrent open shop, we open up a variety of techniques for coflow scheduling. Inspired by the best known result, we derive a 2-approximation algorithm for coflow scheduling, and further develop a decentralized coflow scheduling system, D-CAS, which avoids the system problems associated with current centralized proposals while addressing the performance challenges of decentralized suggestions. Trace-driven simulations indicate that D-CAS achieves a performance close to Varys, the state-of-the-art centralized method, and outperforms Baraat, the only existing decentralized method, significantly.
dc.language	English
dc.publisher	IEEE COMPUTER SOC
dc.relation.ispartof	IEEE Transactions on Parallel and Distributed Systems
dc.relation.isbasedon	10.1109/TPDS.2016.2525767
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0803 Computer Software, 0805 Distributed Computing, 1005 Communications Technologies
dc.subject.classification	Distributed Computing
dc.title	Towards Practical and Near-Optimal Coflow Scheduling for Data Center Networks
dc.type	Journal Article
utslib.citation.volume	27
utslib.for	0803 Computer Software
utslib.for	0805 Distributed Computing
utslib.for	1005 Communications Technologies
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2022-07-31T01:17:43Z
pubs.issue	11
pubs.publication-status	Published
pubs.volume	27
utslib.citation.issue	11

Abstract:

In current data centers, an application (e.g., MapReduce, Dryad, search platform, etc.) usually generates a group of parallel flows to complete a job. These flows compose a coflow and only completing them all is meaningful to the application. Accordingly, minimizing the average Coflow Completion Time (CCT) becomes a critical objective of flow scheduling. However, achieving this goal in today's Data Center Networks (DCNs) is quite challenging, not only because the schedule problem is theoretically NP-hard, but also because it is tough to perform practical flow scheduling in large-scale DCNs. In this paper, we find that minimizing the average CCT of a set of coflows is equivalent to the well-known problem of minimizing the sum of completion times in a concurrent open shop. As there are abundant existing solutions for concurrent open shop, we open up a variety of techniques for coflow scheduling. Inspired by the best known result, we derive a 2-approximation algorithm for coflow scheduling, and further develop a decentralized coflow scheduling system, D-CAS, which avoids the system problems associated with current centralized proposals while addressing the performance challenges of decentralized suggestions. Trace-driven simulations indicate that D-CAS achieves a performance close to Varys, the state-of-the-art centralized method, and outperforms Baraat, the only existing decentralized method, significantly.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/159410