File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Joint online coflow routing and scheduling in data center networks

TitleJoint online coflow routing and scheduling in data center networks
Authors
KeywordsCoflow
datacenter networks
online algorithm
Issue Date2019
PublisherInstitute of Electrical and Electronics Engineers. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=90
Citation
IEEE/ACM Transactions on Networking, 2019, v. 27 n. 5, p. 1771-1786 How to Cite?
AbstractA 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).
Persistent Identifierhttp://hdl.handle.net/10722/294270
ISSN
2023 Impact Factor: 3.0
2023 SCImago Journal Rankings: 2.034
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorTan, H-
dc.contributor.authorJIANG, SHC-
dc.contributor.authorLI, Y-
dc.contributor.authorLi, XY-
dc.contributor.authorZhang, C-
dc.contributor.authorHAN, Z-
dc.contributor.authorLau, FCM-
dc.date.accessioned2020-11-23T08:28:57Z-
dc.date.available2020-11-23T08:28:57Z-
dc.date.issued2019-
dc.identifier.citationIEEE/ACM Transactions on Networking, 2019, v. 27 n. 5, p. 1771-1786-
dc.identifier.issn1063-6692-
dc.identifier.urihttp://hdl.handle.net/10722/294270-
dc.description.abstractA 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).-
dc.languageeng-
dc.publisherInstitute of Electrical and Electronics Engineers. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=90-
dc.relation.ispartofIEEE/ACM Transactions on Networking-
dc.rightsIEEE/ACM Transactions on Networking. Copyright © Institute of Electrical and Electronics Engineers.-
dc.rights©20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.-
dc.subjectCoflow-
dc.subjectdatacenter networks-
dc.subjectonline algorithm-
dc.titleJoint online coflow routing and scheduling in data center networks-
dc.typeArticle-
dc.identifier.emailLau, FCM: fcmlau@cs.hku.hk-
dc.identifier.authorityLau, FCM=rp00221-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/TNET.2019.2930721-
dc.identifier.scopuseid_2-s2.0-85074905112-
dc.identifier.hkuros319188-
dc.identifier.volume27-
dc.identifier.issue5-
dc.identifier.spage1771-
dc.identifier.epage1786-
dc.identifier.isiWOS:000502059800001-
dc.publisher.placeUnited States-
dc.identifier.issnl1063-6692-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats