research-article

Public Access

Sunflow: Efficient Optical Circuit Scheduling for Coflows

Authors:

Xin Sunny Huang,

Xiaoye Steven Sun,

T.S. Eugene NgAuthors Info & Claims

CoNEXT '16: Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies

Pages 297 - 311

https://doi.org/10.1145/2999572.2999592

Published: 06 December 2016 Publication History

Abstract

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 achieve high application-level communication efficiency when servicing structured traffic flows (a.k.a. Coflows) from distributed data processing applications. This paper presents the first OCS scheduling algorithm called Sunflow that addresses this requirement.

Preemption decisions are the key to any OCS scheduling algorithm. Sunflow makes preemption decisions at two levels. First, at the intra-Coflow level, Sunflow does not allow subflows within a Coflow to preempt each other. We prove that the performance of this strategy is within a factor-of-two to the optimal. We further demonstrate that under realistic traffic, performance of Sunflow is on average within 1.03× to optimal. Second, at the inter-Coflow level, Sunflow provides a framework for flexible preemption policies to support diverse usage scenarios. In the specific case of the shortest-Coflow-first policy, we find that Coflows on average finish just as fast in a Sunflow-scheduled optical circuit switched network as in a comparable packet switched network employing the state-of-the-art Coflow scheduler.

References

[1]

Apache Hive. http://hive.apache.org.

[2]

Apache Tez. http://tez.apache.org.

[3]

Based on private communications with Glimmerglass Networks Inc., an optical switch manufacturer.

[4]

Coflow benchmark based on Facebook traces. https://github.com/coflow/coflow-benchmark.

[5]

Al-Fares, M., Loukissas, A., and Vahdat, A. A scalable, commodity data center network architecture. In ACM SIGCOMM (2008).

Digital Library

[6]

Allahverdi, A., Ng, C., Cheng, T. E., and Kovalyov, M. Y. A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187, 3 (2008), 985--1032.

[7]

Balas, E., and Landweer, P. R. Traffic assignment in communication satellites. Operations Research Letters 2, 4 (1983), 141--147.

Digital Library

[8]

Birkhoff, G. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev. Ser. A 5 (1946), 147--151.

[9]

Calient. S series optical circuit switch. http://www.calient.net.

[10]

Chowdhury, M., and Stoica, I. Coflow: A networking abstraction for cluster applications. In ACM Hotnets (2012).

Digital Library

[11]

Chowdhury, M., and Stoica, I. Efficient coflow scheduling without prior knowledge. In ACM SIGCOMM (2015).

Digital Library

[12]

Chowdhury, M., Zhong, Y., and Stoica, I. Efficient coflow scheduling with Varys. In ACM SIGCOMM (2014).

Digital Library

[13]

Dasylva, A., and Srikant, R. Optimal WDM schedules for optical star networks. IEEE Transactions on Networking (TON) 7, 3 (1999), 446--456.

Digital Library

[14]

Edmonds, J. Paths, trees, and flowers. Canadian Journal of Mathematics 17 (1965), 449--467.

[15]

Farrington, N., Porter, G., Fainman, Y., Papen, G., and Vahdat, A. Hunting mice with microsecond circuit switches. In ACM HotNets (2012).

Digital Library

[16]

Farrington, N., Porter, G., Radhakrishnan, S., Bazzaz, H. H., Subramanya, V., Fainman, Y., Papen, G., and Vahdat, A. Helios: A hybrid electrical/optical switch architecture for modular data centers. In ACM SIGCOMM (2010).

Digital Library

[17]

Glimmerglass. Intelligent optical system. http://www.glimmerglass.com.

[18]

Gonzalez, T., and Sahni, S. Open shop scheduling to minimize finish time. Journal of the ACM (JACM) 23, 4 (1976), 665--679.

Digital Library

[19]

Gopal, I. S., and Wong, C. K. Minimizing the number of switchings in an SS/TDMA system. IEEE Transactions on Communications 33, 6 (1985), 497--501.

[20]

Greenberg, A., Hamilton, J. R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D. A., Patel, P., and Sengupta, S. VL2: A scalable and flexible data center network. In ACM SIGCOMM (2009).

Digital Library

[21]

Inukai, T. An efficient SS/TDMA time slot assignment algorithm. IEEE Transactions on Communications 27, 10 (1979), 1449--1455.

[22]

Isard, M., Budiu, M., Yu, Y., Birrell, A., and Fetterly, D. Dryad: Distributed data-parallel programs from sequential building blocks. In ACM EuroSys (2007).

Digital Library

[23]

Kesselman, A., and Kogan, K. Nonpreemptive scheduling of optical switches. IEEE Transactions on Communications 55, 6 (2007), 1212--1219.

[24]

Lin, H.-C., and Wang, C.-H. A hybrid multicast scheduling algorithm for single-hop WDM networks. In IEEE INFOCOM (2001).

[25]

Liu, H., Lu, F., Forencich, A., Kapoor, R., Tewari, M., Voelker, G. M., Papen, G., Snoeren, A. C., and Porter, G. Circuit switching under the radar with REACToR. In USENIX NSDI (2014).

Digital Library

[26]

Liu, H., Mukerjee, M. K., Li, C., Feltman, N., Papen, G., Savage, S., Seshan, S., Voelker, G. M., Andersen, D. G., Kaminsky, M., et al. Scheduling techniques for hybrid circuit/packet networks. In ACM CoNEXT (2015).

Digital Library

[27]

Luo, S., Yu, H., Zhao, Y., Wang, S., Yu, S., and Li, L. Towards practical and near-optimal coflow scheduling for data center networks.

[28]

McKeown, N. The iSLIP scheduling algorithm for input-queued switches. IEEE Transactions on Networking 7, 2 (1999), 188--201.

Digital Library

[29]

Polatis. Series 7000 software defined optical switch. http://www.polatis.com.

[30]

Porter, G., Strong, R., Farrington, N., Forencich, A., Chen-Sun, P., Rosing, T., Fainman, Y., Papen, G., and Vahdat, A. Integrating microsecond circuit switching into the data center. In ACM SIGCOMM (2013).

Digital Library

[31]

Qiu, Z., Stein, C., and Zhong, Y. Minimizing the total weighted completion time of coflows in datacenter networks. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2015).

Digital Library

[32]

Rouskas, G. N., and Sivaraman, V. Packet scheduling in broadcast WDM networks with arbitrary transceiver tuning latencies. IEEE Transactions on Networking (TON) 5, 3 (1997), 359--370.

Digital Library

[33]

Towles, B., and Dally, W. J. Guaranteed scheduling for switches with configuration overhead. IEEE Transactions on Networking 11, 5 (2003), 835--847.

Digital Library

[34]

Wang, C.-H., Javidi, T., and Porter, G. End-to-end scheduling for all-optical data centers. In IEEE INFOCOM (2015).

[35]

Wang, G., Andersen, D. G., Kaminsky, M., Papagiannaki, K., Ng, T. S. E., Kozuch, M., and Ryan, M. c-Through: Part-time optics in data centers. In ACM SIGCOMM (2010).

Digital Library

[36]

Wang, G., Ng, T. S. E., and Shaikh, A. Programming your network at run-time for big data applications. In ACM HotSDN (2012).

Digital Library

[37]

Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauley, M., Franklin, M. J., Shenker, S., and Stoica, I. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In USENIX NSDI (2012).

Digital Library

[38]

Zhang, H., Chen, L., Yi, B., Chen, K., Chowdhury, M., and Geng, Y. CODA: Toward automatically identifying and scheduling coflows in the dark. In ACM SIGCOMM (2016).

Digital Library

[39]

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

Cited By

Liu LXu XZhou PChen XErgu DYu HSun GGuizani M(2025)PSscheduler: A parameter synchronization scheduling algorithm for distributed machine learning in reconfigurable optical networksNeurocomputing10.1016/j.neucom.2024.128876616(128876)Online publication date: Feb-2025
https://doi.org/10.1016/j.neucom.2024.128876
Li ZLi DChen YChen KZhang Y(2024)Decentralized Scheduling for Data-Parallel Tasks in the CloudACM Transactions on Parallel Computing10.1145/365185811:2(1-23)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3651858
Chen C(2024)Efficient Approximation Algorithms for Scheduling Coflows With Precedence Constraints in Identical Parallel Networks to Minimize Weighted Completion TimeIEEE Transactions on Services Computing10.1109/TSC.2023.334448117:5(2349-2364)Online publication date: Sep-2024
https://doi.org/10.1109/TSC.2023.3344481
Show More Cited By

Index Terms

Sunflow: Efficient Optical Circuit Scheduling for Coflows
1. Networks
  1. Network algorithms
    1. Control path algorithms
      1. Network control algorithms
      2. Network resources allocation
  2. Network types
    1. Data center networks

Recommendations

Exploiting Inter-Flow Relationship for Coflow Placement in Datacenters
APNet '17: Proceedings of the First Asia-Pacific Workshop on Networking

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 ...
Forget the Deadline: Scheduling Interactive Applications in Data Centers
CLOUD '15: Proceedings of the 2015 IEEE 8th International Conference on Cloud Computing

Many interactive applications running in data centers such as web search, social networks, online gaming, and financial services are delay-sensitive, and often have a deadline. These deadlines vary across users and applications, which makes the job ...
A RWA performance comparison for hybrid optical networks combining circuit and multi-wavelength packet switching
ONDM'09: Proceedings of the 13th international conference on Optical Network Design and Modeling

This paper compares several routing and wavelength assignment algorithms for a hybrid optical network architecture combining optical circuit switching (OCS) and multi-wavelength optical packet switching (MW-OPS). In this network, due to the fact that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '16: Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies

December 2016

524 pages

ISBN:9781450342926

DOI:10.1145/2999572

General Chairs:
Athina Markopoulou
University of California, Irvine, USA
,
Michalis Faloutsos
University of California, Riverside, USA
,
Program Chairs:
Vyas Sekar
Carnegie Mellon University, USA
,
Dejan Kostic
KTH Royal Institute of Technology, Sweden

Copyright © 2016 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].

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 December 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

CoNEXT '16

Sponsor:

SIGCOMM

CoNEXT '16: The 12th International Conference on emerging Networking EXperiments and Technologies

December 12 - 15, 2016

California, Irvine, USA

Acceptance Rates

CoNEXT '16 Paper Acceptance Rate 30 of 160 submissions, 19%;

Overall Acceptance Rate 198 of 789 submissions, 25%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
450
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)10

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu LXu XZhou PChen XErgu DYu HSun GGuizani M(2025)PSscheduler: A parameter synchronization scheduling algorithm for distributed machine learning in reconfigurable optical networksNeurocomputing10.1016/j.neucom.2024.128876616(128876)Online publication date: Feb-2025
https://doi.org/10.1016/j.neucom.2024.128876
Li ZLi DChen YChen KZhang Y(2024)Decentralized Scheduling for Data-Parallel Tasks in the CloudACM Transactions on Parallel Computing10.1145/365185811:2(1-23)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3651858
Chen C(2024)Efficient Approximation Algorithms for Scheduling Coflows With Precedence Constraints in Identical Parallel Networks to Minimize Weighted Completion TimeIEEE Transactions on Services Computing10.1109/TSC.2023.334448117:5(2349-2364)Online publication date: Sep-2024
https://doi.org/10.1109/TSC.2023.3344481
Wang XShen HTian H(2024)Scheduling Coflows in Hybrid Optical-Circuit and Electrical-Packet Switches With Performance GuaranteeIEEE/ACM Transactions on Networking10.1109/TNET.2024.335424532:3(2299-2314)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2024.3354245
Chen C(2024)Efficient Approximation Algorithms for Scheduling Coflows With Total Weighted Completion Time in Identical Parallel NetworksIEEE Transactions on Cloud Computing10.1109/TCC.2023.334072912:1(116-129)Online publication date: Jan-2024
https://doi.org/10.1109/TCC.2023.3340729
Liu LZhou PSun GChen XWu TYu HGuizani M(2024)Topologies in distributed machine learning: Comprehensive survey, recommendations and future directionsNeurocomputing10.1016/j.neucom.2023.127009567(127009)Online publication date: Jan-2024
https://doi.org/10.1016/j.neucom.2023.127009
Zhang FLiu JWu YChen QChai YWang Z(2024)Towards real-time non-preemptive multicast scheduling in reconfigurable data center networksPeer-to-Peer Networking and Applications10.1007/s12083-024-01804-w17:6(4070-4083)Online publication date: 12-Sep-2024
https://doi.org/10.1007/s12083-024-01804-w
Liu LGao CWang PHuang HLi JXu HZhang W(2023)Bottleneck-Aware Non-Clairvoyant Coflow Scheduling With FaiIEEE Transactions on Cloud Computing10.1109/TCC.2021.312836011:1(1011-1025)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3128360
Jiang RZhang TYi C(2023)Effective Coflow Scheduling in Hybrid Circuit and Packet Switching Networks2023 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC58397.2023.10217994(1156-1161)Online publication date: 9-Jul-2023
https://doi.org/10.1109/ISCC58397.2023.10217994
Ren HShen HWang X(2023)Dynamic Priority Coflow Scheduling in Optical Circuit Switched NetworksParallel and Distributed Computing, Applications and Technologies10.1007/978-981-99-8211-0_20(215-226)Online publication date: 29-Nov-2023
https://doi.org/10.1007/978-981-99-8211-0_20
Show More Cited By

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