research-article

Open access

Scheduling techniques for hybrid circuit/packet networks

Authors:

Matthew K. Mukerjee,

Nicolas Feltman,

Srinivasan Seshan,

Geoffrey M. Voelker,

David G. Andersen,

Michael Kaminsky,

Alex C. SnoerenAuthors Info & Claims

CoNEXT '15: Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies

Article No.: 41, Pages 1 - 13

https://doi.org/10.1145/2716281.2836126

Published: 01 December 2015 Publication History

Abstract

A range of new datacenter switch designs combine wireless or optical circuit technologies with electrical packet switching to deliver higher performance at lower cost than traditional packet-switched networks. These "hybrid" networks schedule large traffic demands via a high-rate circuits and remaining traffic with a lower-rate, traditional packet-switches. Achieving high utilization requires an efficient scheduling algorithm that can compute proper circuit configurations and balance traffic across the switches. Recent proposals, however, provide no such algorithm and rely on an omniscient oracle to compute optimal switch configurations.

Finding the right balance of circuit and packet switch use is difficult: circuits must be reconfigured to serve different demands, incurring non-trivial switching delay, while the packet switch is bandwidth constrained. Adapting existing crossbar scheduling algorithms proves challenging with these constraints. In this paper, we formalize the hybrid switching problem, explore the design space of scheduling algorithms, and provide insight on using such algorithms in practice. We propose a heuristic-based algorithm, Solstice that provides a 2.9× increase in circuit utilization over traditional scheduling algorithms, while being within 14% of optimal, at scale.

References

[1]

M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan. Data Center TCP (DCTCP). In Proc. ACM SIGCOMM, Aug. 2010.

Digital Library

[2]

T. Benson, A. Akella, and D. A. Maltz. Network Traffic Characteristics of Data Centers in the Wild. In Proc. ACM IMC, Nov. 2010.

Digital Library

[3]

G. Birkhoff. Tres Observaciones Sobre el Algebra Lineal. Univ. Nac. Tucumán Rev. Ser. A, 1946.

[4]

K. Chen, A. Singla, A. Singh, K. Ramachandran, L. Xu, Y. Zhang, and X. Wen. OSA: An Optical Switching Architecture for Data Center Networks and Unprecedented Flexibility. In Proc. USENIX NSDI, Apr. 2012.

Digital Library

[5]

N. Farrington, G. Porter, Y. Fainman, G. Papen, and A. Vahdat. Hunting Mice with Microsecond Circuit Switches. In Proc. ACM HotNets-XI, Oct. 2012.

Digital Library

[6]

N. Farrington, G. Porter, S. Radhakrishnan, H. Bazzaz, V. Subramanya, Y. Fainman, G. Papen, and A. Vahdat. Helios: A Hybrid Electrical/Optical Switch Architecture for Modular Data Centers. In Proc. ACM SIGCOMM, Aug. 2010.

Digital Library

[7]

S. Fu, B. Wu, X. Jiang, A. Pattavina, L. Zhang, and S. Xu. Cost and Delay Tradeoff in Three-Stage Switch Architecture for Data Center Networks. In Proc. IEEE High Perf. Switching and Routing, July 2013.

[8]

P. Giaccone, B. Prabhakar, and D. Shah. Randomized Scheduling Algorithms for High-Aggregate Bandwidth Switches. IEEE J. Sel. Areas in Comms., May 2003.

Digital Library

[9]

A. Goel, M. Kapralov, and S. Khanna. Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs. In ACM STOC, June 2013.

Digital Library

[10]

I. S. Gopal and C. K. Wong. Minimizing the Number of Switchings in a SS/TDMA System. IEEE Trans. Comms., June 1985.

[11]

Gurobi. Gurobi Optimization. http://www.gurobi.com/.

[12]

J. Haglund and J. Remmel. Rook Theory for Perfect Matchings. Advances in Applied Math., Aug. 2001.

Digital Library

[13]

D. Halperin, S. Kandula, J. Padhye, P. Bahl, and D. Wetherall. Augmenting Data Center Networks with Multi-gigabit Wireless Links. In Proc. ACM SIGCOMM, Aug. 2011.

Digital Library

[14]

T. Inukai. An Efficient SS/TDMA Time Slot Assignment Algorithm. IEEE Trans. Comms., Oct. 1979.

[15]

S. Kandula, J. Padhye, and P. Bahl. Flyways To De-Congest Data Center Networks. In Proc. ACM HotNets-VIII, Oct. 2009.

[16]

S. Kandula, S. Sengupta, A. Greenberg, P. Patel, and R. Chaiken. The Nature of Data Center Traffic: Measurements & Analysis. In Proc. ACM IMC, Nov. 2009.

Digital Library

[17]

R. Kapoor, A. C. Snoeren, G. M. Voelker, and G. Porter. Bullet Trains: A Study of NIC Burst Behavior at Microsecond Timescales. In Proc. ACM CoNEXT, Dec. 2013.

Digital Library

[18]

X. Li and M. Hamdi. On Scheduling Optical Packet Switches with Reconfiguration Delay. IEEE JSAC, Sept. 2003.

Digital Library

[19]

H. Liu, F. Lu, A. Forencich, R. Kapoor, M. Tewari, G. M. Voelker, G. Papen, A. C. Snoeren, and G. Porter. Circuit Switching Under the Radar with REACToR. In Proc. USENIX NSDI, Apr. 2014.

Digital Library

[20]

N. McKeown. The iSLIP Scheduling Algorithm for Input-Queued Switches. IEEE Trans. Networking, Apr. 1999.

Digital Library

[21]

Q.-K. Pan and R. Ruiz. A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics to Minimize Flowtime. Comp. & Op. Research, Jan. 2013.

Digital Library

[22]

G. Porter, R. Strong, N. Farrington, A. Forencich, P.-C. Sun, T. Rosing, Y. Fainman, G. Papen, and A. Vahdat. Integrating Microsecond Circuit Switching into the Data Center. In Proc. ACM SIGCOMM, Aug. 2013.

Digital Library

[23]

A. Roy, H. Zeng, J. Bagga, G. Porter, and A. C. Snoeren. Inside the Social Network's (Datacenter) Network. In Proc. ACM SIGCOMM, Aug. 2015.

Digital Library

[24]

R. Sinkhorn and K. Paul. Concerning Nonnegative Matrices and Doubly Stochastic Matrices. Pacific J. Math., May 1967.

[25]

M. Tandon, P. Cummings, and M. LeVan. Flowshop Sequencing with Non-Permutation Schedules. Comp. & Chem. Eng., Aug. 1991.

[26]

B. Towles and W. J. Dally. Guaranteed Scheduling for Switches with Configuration Overhead. IEEE Trans. Networking, Oct. 2003.

Digital Library

[27]

G. Wang, D. G. Andersen, M. Kaminsky, M. Kozuch, T. S. E. Ng, K. Papagiannaki, M. Glick, and L. Mummert. Your Data Center Is a Router: The Case for Reconfigurable Optical Circuit Switched Paths. In Proc. ACM HotNets-VIII, Oct. 2009.

[28]

G. Wang, D. G. Andersen, M. Kaminsky, K. Papagiannaki, T. S. E. Ng, M. Kozuch, and M. Ryan. c-Through: Part-time Optics in Data Centers. In Proc. ACM SIGCOMM, Aug. 2010.

Digital Library

[29]

B. Wu and K. L. Yeung. Minimum Delay Scheduling in Scalable Hybrid Electronic/Optical Packet Switches. In IEEE GLOBECOM, Nov. 2006.

[30]

B. Wu, K. L. Yeung, and X. Wang. Improving Scheduling Efficiency for High-Speed Routers with Optical Switch Fabrics. In IEEE GLOBECOM, Nov. 2006.

[31]

X. Zhou, Z. Zhang, Y. Zhu, Y. Li, S. Kumar, A. Vahdat, B. Y. Zhao, and H. Zheng. Mirror Mirror on the Ceiling: Flexible Wireless Links for Data Centers. In Proc. ACM SIGCOMM, Aug. 2012.

Digital Library

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
Chen SHe KWang RSeshan SSteenkiste PVanbever LZhang I(2024)Precise data center traffic engineering with constrained hardware resourcesProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691862(669-690)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.5555/3691825.3691862
Mellette WForencich AAthapathu RSnoeren APapen GPorter GSekar VYu MSeneviratne AVeitch D(2024)Realizing RotorNet: Toward Practical Microsecond Scale Optical NetworkingProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672273(392-414)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672273
Show More Cited By

Index Terms

Scheduling techniques for hybrid circuit/packet networks
1. Networks

Recommendations

A control theoretical approach to congestion control in packet networks

In this paper, we introduce a control theoretical analysis of the closed-loop congestion control problem in packet networks. The control theoretical approach is used in a proportional rate controller, where packets are admitted into the network in ...
Efficient Hybrid Packet Classification in Traffic Control System Using Network Processors
ICACC '09: Proceedings of the 2009 International Conference on Advanced Computer Control

The fast increasing Internet applications need accurate, high performance and scalable packet classification in traffic control systems. Although there are several designs of packet classification implemented on heterogeneous hardware platforms, ...
Analysis of a clock-recovery technique for circuit emulation services over packet networks

One important requirement of circuit emulation services (CES) over packet networks is clock synchronization and timing distribution among the nodes. CES depends on reliable and high-quality timing for operations. In the time division multiplexing (TDM) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '15: Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies

December 2015

483 pages

ISBN:9781450334129

DOI:10.1145/2716281

General Chairs:
Felipe Huici
NEC Europe Ltd
,
Giuseppe Bianchi
University of Rome Tor Vergata

Copyright © 2015 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2015

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CoNEXT '15

Sponsor:

SIGCOMM

CoNEXT '15: Conference on emerging Networking Experiments and Technologies

December 1 - 4, 2015

Heidelberg, Germany

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
1,069
Total Downloads

Downloads (Last 12 months)286
Downloads (Last 6 weeks)46

Reflects downloads up to 13 Feb 2025

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
Chen SHe KWang RSeshan SSteenkiste PVanbever LZhang I(2024)Precise data center traffic engineering with constrained hardware resourcesProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691862(669-690)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.5555/3691825.3691862
Mellette WForencich AAthapathu RSnoeren APapen GPorter GSekar VYu MSeneviratne AVeitch D(2024)Realizing RotorNet: Toward Practical Microsecond Scale Optical NetworkingProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672273(392-414)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672273
Aykurt KZerwas JBlenk AKellerer W(2024)When TCP Meets Reconfigurations: A Comprehensive Measurement StudyIEEE Transactions on Network and Service Management10.1109/TNSM.2023.332750821:2(1372-1386)Online publication date: Apr-2024
https://doi.org/10.1109/TNSM.2023.3327508
Qiu YZhao GXu HHuang HQiao C(2024)PARING: Joint Task Placement and Routing for Distributed Training With In-Network AggregationIEEE/ACM Transactions on Networking10.1109/TNET.2024.341485332:5(4317-4332)Online publication date: Oct-2024
https://doi.org/10.1109/TNET.2024.3414853
Zhang HAn CZhou ALi CLiu XPei JZhu YLiu LMa H(2024)Reviving Peer-to-Peer Networking for Scalable Crowdsourced Live Video StreamingIEEE/ACM Transactions on Networking10.1109/TNET.2024.338039532:4(3205-3220)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3380395
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
Li SGu HYu XHuang HWang SChang Z(2024)COCSN: A Multi-Tiered Cascaded Optical Circuit Switching Network for Data CenterIEEE Transactions on Cloud Computing10.1109/TCC.2024.348827512:4(1463-1475)Online publication date: Oct-2024
https://doi.org/10.1109/TCC.2024.3488275
Valls VPromponas PTassiulas L(2024)A Brief Introduction to Quantum Network ControlIEEE Communications Magazine10.1109/MCOM.008.230085562:10(48-53)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/MCOM.008.2300855
Zhang SShao JChen BSun WHu W(2024)Interruptible Scheduling of Partially Re-Configurable Optical Switching in Data Center NetworksJournal of Lightwave Technology10.1109/JLT.2023.334104242:7(2212-2224)Online publication date: 1-Apr-2024
https://doi.org/10.1109/JLT.2023.3341042
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

Figures

Tables

Media

View Table of Conten