research-article

Composite-Path Switching

Authors:

Shay Vargaftik,

Katherine Barabash,

Yaniv Ben-Itzhak,

Isaac Keslassy,

Ariel OrdaAuthors Info & Claims

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

Pages 329 - 343

https://doi.org/10.1145/2999572.2999610

Published: 06 December 2016 Publication History

Abstract

Hybrid switching combines a high-bandwidth optical circuit switch in parallel with a low-bandwidth electronic packet switch. It presents an appealing solution for scaling datacenter architectures. Unfortunately, it does not fit many traffic patterns produced by typical datacenter applications, and in particular the skewed traffic patterns that involve highly intensive one-to-many and many-to-one communications.

In this paper, we introduce composite-path switching by allowing for composite circuit/packet paths between the two switches. We show how this enables the datacenter network to deal with skewed traffic patterns, and offer a practical scheduling algorithm that can directly extend any hybrid-switching scheduling algorithm. Through extensive evaluations using modern datacenter workloads, we show how our solution outperforms two recently proposed state-of-the-art scheduling techniques, both in completion time and in circuit utilization.

References

[1]

Shaileshh Bojja, Mohammad Alizadeh, and Pramod Viswanath. Costly circuits, submodular schedules and approximate Carathéodory theorems. ACM Sigmetrics, 2015.

Digital Library

[2]

He Liu, Matthew K Mukerjee, Conglong Li, et al. Scheduling techniques for hybrid circuit/packet networks. ACM CoNEXT, 2015.

Digital Library

[3]

Nathan Farrington et al. Helios: a hybrid electrical/optical switch architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 2011.

Digital Library

[4]

George Porter, Richard Strong, Nathan Farrington, et al. Integrating microsecond circuit switching into the data center. ACM SIGCOMM, 2013.

Digital Library

[5]

Guohui Wang, David G Andersen, Michael Kaminsky, et al. c-Through: Part-time optics in data centers. ACM SIGCOMM Computer Communication Review, 2011.

Digital Library

[6]

He Liu, Feng Lu, Alex Forencich, Rishi Kapoor, et al. Circuit switching under the radar with reactor. In ACM/USENIX NSDI, 2014.

Digital Library

[7]

Christoforos Kachris, Konstantinos Kanonakis, and Ioannis Tomkos. Optical interconnection networks in data centers: recent trends and future challenges. Communications Magazine, IEEE, 2013.

[8]

Nathan Farrington, George Porter, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Hunting mice with microsecond circuit switches. In Proc. ACM Workshop on Hot Topics in Networks, 2012.

Digital Library

[9]

Bin Wu and Kwan L Yeung. Nxg05--6: Minimum delay scheduling in scalable hybrid electronic/optical packet switches. In Global Telecommunications Conference, 2006. GLOBECOM'06. IEEE, pages 1--5. IEEE, 2006.

[10]

Shoaib Kamil, Ali Pinar, Daniel Gunter, et al. Reconfigurable hybrid interconnection for static and dynamic scientific applications. In Proceedings of the 4th international conference on Computing frontiers, 2007.

Digital Library

[11]

Howard Wang, Yiting Xia, Keren Bergman, TS Ng, Sambit Sahu, and Kunwadee Sripanidkulchai. Rethinking the physical layer of data center networks of the next decade: Using optics to enable efficient*-cast connectivity. ACM SIGCOMM Computer Communication Review, 2013.

Digital Library

[12]

Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. Efficient coflow scheduling with varys. In ACM SIGCOMM Computer Communication Review, 2014.

Digital Library

[13]

Yangming Zhao, Kai Chen, Wei Bai, et al. Rapier: Integrating routing and scheduling for coflow-aware data center networks. In Computer Communications (INFOCOM), 2015 IEEE Conference on, 2015.

[14]

Zhen Qiu, Cliff Stein, and Yuan Zhong. Minimizing the total weighted completion time of coflows in datacenter networks. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015.

Digital Library

[15]

Mosharaf Chowdhury and Ion Stoica. Coflow: A networking abstraction for cluster applications. In Proceedings of the 11th ACM Workshop on Hot Topics in Networks, 2012.

Digital Library

[16]

Michael Isard et al. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS Operating Systems Review, 2007.

Digital Library

[17]

Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, et al. Pregel: a system for large-scale graph processing. In ACM SIGMOD, 2010.

Digital Library

[18]

Dhruba Borthakur. The hadoop distributed file system: Architecture and design. Hadoop Project Website, 2007.

[19]

Mosharaf Chowdhury, Srikanth Kandula, and Ion Stoica. Leveraging endpoint flexibility in data-intensive clusters. In ACM SIGCOMM Computer Communication Review, 2013.

Digital Library

[20]

Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation, 2012.

Digital Library

[21]

Christo Wilson, Hitesh Ballani, Thomas Karagiannis, and Ant Rowtron. Better never than late: Meeting deadlines in datacenter networks. In ACM SIGCOMM Computer Communication Review, 2011.

Digital Library

[22]

Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 2008.

Digital Library

[23]

Mohammad Alizadeh, Albert Greenberg, David A Maltz, et al. Data center tcp (dctcp). In ACM SIGCOMM computer communication review, 2010.

Digital Library

[24]

Pawan Prakash, Advait Dixit, Y Charlie Hu, and Ramana Kompella. The tcp outcast problem: exposing unfairness in data center networks. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation, 2012.

Digital Library

[25]

Mosharaf Chowdhury, Matei Zaharia, Justin Ma, Michael I Jordan, and Ion Stoica. Managing data transfers in computer clusters with orchestra. ACM SIGCOMM Computer Communication Review, 2011.

Digital Library

[26]

Fahad R Dogar, Thomas Karagiannis, Hitesh Ballani, and Antony Rowstron. Decentralized task-aware scheduling for data center networks. In ACM SIGCOMM Computer Communication Review, 2014.

Digital Library

[27]

Nick McKeown, Martin Izzard, Adisak Mekkittikul, William Ellersick, and Mark Horowitz. Tiny tera: a packet switch core. Micro, IEEE, 1997.

Digital Library

[28]

Balaji Prabhakar and Nick McKeown. On the speedup required for combined input-and output-queued switching. Automatica, 1999.

Digital Library

[29]

Mellanox SN2410 Switch System. http://www.mellanox.com/related-docs/prod_eth_switches/PB_SN2410.pdf.

[30]

Arista 7280R Series Data Center Switch Router. https://www.arista.com/assets/data/pdf/Datasheets/7280R-DataSheet.pdf.

[31]

Cisco Nexus 93180YC-EX Switch. http://www.cisco.com/c/en/us/products/collateral/switches/nexus-93108tc-ex-switch/datasheet-c78--736651.html.

[32]

IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems. IEEE Std 1588--2008 (Revision of IEEE Std 1588--2002), pages 1--269, July 2008.

[33]

Jonathan Perry, Amy Ousterhout, Hari Balakrishnan, Devavrat Shah, and Hans Fugal. Fastpass: A centralized zero-queue datacenter network. In ACM SIGCOMM Computer Communication Review, volume 44, pages 307--318. ACM, 2014.

Digital Library

[34]

Pedro Moreira et al. White rabbit: Sub-nanosecond timing distribution over ethernet. In 2009 International Symposium on Precision Clock Synchronization for Measurement, Control and Communication, pages 1--5. IEEE, 2009.

[35]

Steven Blake, David Black, Mark Carlson, Elwyn Davies, Zheng Wang, and Walter Weiss. An architecture for differentiated services. 1998.

[36]

CCITT Recommendation. I. 371: Traffic control and congestion control in b-isdn. Geneva, Study Group, 13, 1992.

[37]

Cisco Tech Notes. Comparing traffic policing and traffic shaping for bandwidth limiting. Document ID, 19645:22--42.

[38]

ITUT SGI. Traffic control and congestion control in b-isdn. ITU-T Rec, 1.

[39]

John William Evans and Clarence Filsfils. Deploying IP and MPLS QoS for Multiservice Networks: Theory & Practice. Morgan Kaufmann, 2010.

[40]

Cisco DocWiki. Resource Reservation Protocol. http://docwiki.cisco.com/wiki/Resource_Reservation_Protocol .

[41]

Sergey Legtchenko, Nicholas Chen, Daniel Cletheroe, et al. Xfabric: a reconfigurable in-rack network for rack-scale computers. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), 2016.

Digital Library

[42]

Kai Chen et al. OSA: An Optical Switching Architecture for Data Center Networks With Unprecedented Flexibility. Networking, IEEE/ACM Transactions on, 2014.

Digital Library

[43]

Polatis 6000n Protection Services Switch Data Sheet. http://www.polatis.com/datasheets/products/Polatis_6000n_Protection_Services_Switch_Data_Sheet.pdf.

[44]

Theophilus Benson, Aditya Akella, and David A Maltz. Network traffic characteristics of data centers in the wild. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, 2010.

Digital Library

[45]

Yossi Azar and Iftah Gamzu. Efficient submodular function maximization under linear packing constraints. In Automata, Languages, and Programming. 2012.

Digital Library

[46]

High-Density 25/100 Gigabit Ethernet StrataXGS Tomahawk Ethernet Switch Series. https://www.broadcom.com/products/ethernet-communication-and-switching/switching/bcm56960-series.

[47]

Dan Alistarh, Hitesh Ballani, Paolo Costa, Adam Funnell, Joshua Benjamin, Philip Watts, and Benn Thomsen. A high-radix, low-latency optical switch for data centers. In ACM SIGCOMM Computer Communication Review, 2015.

Digital Library

[48]

SDN-Enabled All-Optical Circuit Switching: An Answer to Data Center Bandwidth Challenges. https://www.sdxcentral.com/wp-content/uploads/2015/02/Polatis-SDN-Enabled-All-Optical-Circuit-Switching.pdf.

[49]

Mike Mesnier, Gregory R Ganger, and Erik Riedel. Object-based storage. IEEE Communications Magazine, 2003.

Digital Library

[50]

Kevin J Barker, Alan Benner, Ray Hoare, et al. On the feasibility of optical circuit switching for high performance computing systems. In Proceedings of the 2005 ACM/IEEE conference on Supercomputing. IEEE Computer Society, 2005.

Digital Library

[51]

George Porter, Richard Strong, Nathan Farrington, Alex Forencich, et al. Integrating microsecond circuit switching into the data center. In Proc. ACM SIGCOMM., 2013.

Digital Library

[52]

Navid Hamedazimi, Zafar Qazi, Himanshu Gupta, et al. Firefly: a reconfigurable wireless data center fabric using free-space optics. ACM SIGCOMM Computer Communication Review, 2015.

Digital Library

[53]

Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, et al. Projector: Agile reconfigurable data center interconnect. In ACM SIGCOMM, 2016.

Digital Library

Cited By

Zerwas JGyörgyi CBlenk ASchmid SAvin C(2023)Duo: A High-Throughput Reconfigurable Datacenter Network Using Local Routing and ControlProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35794497:1(1-25)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3579449
Zhang TRen FBao JShu RCheng W(2021)Minimizing Coflow Completion Time in Optical Circuit Switched NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.302514532:2(457-469)Online publication date: 1-Feb-2021
https://doi.org/10.1109/TPDS.2020.3025145
Tseng SBait BLui J(2018)Hybrid Circuit/Packet Network Scheduling with Multiple Composite PathsIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8485837(882-890)Online publication date: Apr-2018
https://doi.org/10.1109/INFOCOM.2018.8485837
Show More Cited By

Index Terms

Composite-Path Switching
1. Networks

Recommendations

Scheduling techniques for hybrid circuit/packet networks
CoNEXT '15: Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies

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 ...
Distributed resource scheduling in not-aligned optical cell switching

Most all-optical switching paradigms assume that different wavelengths are switched independently, which limits scalability. In optical cell switching (OCS), time is divided into time slots of fixed size by time-division multiplexing, and the ...
Path switching: reduced-state flow handling in SDN using path information
CoNEXT '15: Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies

The advent of virtualization, containerization and the Internet of Things (IoT) is leading to an explosive growth in the number of endpoints. Ideally with Software Defined Networking (SDN), one would like to customize packet handling for each of these ...

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

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

Israel Ministry of Science and Technology
Technion Fund for Security Research
European Community's Seventh Framework Programme (FP7/2001-2013) - COSIGN Project
Gordon Fund for Systems Engineering
Hasso Plattner Institute Research School

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

5
Total Citations
View Citations
308
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zerwas JGyörgyi CBlenk ASchmid SAvin C(2023)Duo: A High-Throughput Reconfigurable Datacenter Network Using Local Routing and ControlProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35794497:1(1-25)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3579449
Zhang TRen FBao JShu RCheng W(2021)Minimizing Coflow Completion Time in Optical Circuit Switched NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.302514532:2(457-469)Online publication date: 1-Feb-2021
https://doi.org/10.1109/TPDS.2020.3025145
Tseng SBait BLui J(2018)Hybrid Circuit/Packet Network Scheduling with Multiple Composite PathsIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8485837(882-890)Online publication date: Apr-2018
https://doi.org/10.1109/INFOCOM.2018.8485837
Sun XNg T(2017)When creek meets river: Exploiting high-bandwidth circuit switch in scheduling multicast data2017 IEEE 25th International Conference on Network Protocols (ICNP)10.1109/ICNP.2017.8117591(1-6)Online publication date: Oct-2017
https://doi.org/10.1109/ICNP.2017.8117591
Sun WKoo JByeon SPark WLim SBan DChoi S(2017)BlueCoDE: Bluetooth coordination in dense environment for better coexistence2017 IEEE 25th International Conference on Network Protocols (ICNP)10.1109/ICNP.2017.8117534(1-10)Online publication date: Oct-2017
https://doi.org/10.1109/ICNP.2017.8117534

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents