Reducing Reconfiguration Time in Hybrid Optical-Electrical Datacenter Networks
Pages 41 - 46
Abstract
We study how to reduce the reconfiguration time in hybrid optical-electrical Datacenter Networks (DCNs). With a layer of Optical Circuit Switches (OCSes), hybrid optical-electrical DCNs could reconfigure their logical topologies to better match the on-going traffic patterns, but the reconfiguration time could directly affect the benefits of reconfigurability. The reconfiguration time consists of the topology solver running time and the network convergence time after triggering reconfiguration. However, existing topology solvers either incur high algorithmic complexity or fail to minimize the reconfiguration overhead.
In this paper, we propose a novel algorithm that combines the ideas of bipartition and Minimum Cost Flow (MCF) to reduce the overall reconfiguration time. For the first time, we formulate the topology solving problem as an MCF problem with piecewise cost, which strikes a better balance between solver complexity and solution optimality. Our evaluation shows that our algorithm can significantly reduce the network convergence time while consuming less topology solver running time, making its overall performance superior to existing algorithms. Our code and test cases are available at a public repository [25].
References
[1]
Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. 2008. A scalable, commodity data center network architecture. ACM SIGCOMM computer communication review 38, 4 (2008), 63–74.
[2]
Kateřina Altmanová, Dušan Knop, and Martin Kouteckỳ. 2019. Evaluating and tuning n-fold integer programming. Journal of Experimental Algorithmics (JEA) 24 (2019), 1–22.
[3]
Chen Avin, Manya Ghobadi, Chen Griner, and Stefan Schmid. 2020. On the complexity of traffic traces and implications. Proceedings of the ACM on Measurement and Analysis of Computing Systems 4, 1 (2020), 1–29.
[4]
Theophilus Benson, Aditya Akella, and David A Maltz. 2010. Network traffic characteristics of data centers in the wild. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement. 267–280.
[5]
Jon Louis Bentley, Dorothea Haken, and James B Saxe. 1980. A general method for solving divide-and-conquer recurrences. ACM SIGACT News 12, 3 (1980), 36–44.
[6]
Yael Berstein and Shmuel Onn. 2009. The Graver complexity of integer programming. Annals of Combinatorics 13 (2009), 289–296.
[7]
Kai Chen, Ankit Singla, Atul Singh, Kishore Ramachandran, Lei Xu, Yueping Zhang, Xitao Wen, and Yan Chen. 2013. OSA: An optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACM Transactions on Networking 22, 2 (2013), 498–511.
[8]
Jesús A De Loera, Raymond Hemmecke, Shmuel Onn, and Robert Weismantel. 2008. N-fold integer programming. Discrete Optimization 5, 2 (2008), 231–241.
[9]
Jesús A De Loera and Shmuel Onn. 2006. All linear and integer programs are slim 3-way transportation programs. SIAM Journal on Optimization 17, 3 (2006), 806–821.
[10]
Klaus-Tycho Foerster and Stefan Schmid. 2019. Survey of reconfigurable data center networks: Enablers, algorithms, complexity. ACM SIGACT News 50, 2 (2019), 62–79.
[11]
Alan M Frieze. 1983. Complexity of a 3-dimensional assignment problem. European Journal of Operational Research 13, 2 (1983), 161–164.
[12]
Albert Greenberg, James R Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A Maltz, Parveen Patel, and Sudipta Sengupta. 2009. VL2: A scalable and flexible data center network. In Proceedings of the ACM SIGCOMM 2009 conference on Data communication. 51–62.
[13]
Gurobi Optimization, LLC. 2023. Gurobi Optimizer Reference Manual. https://www.gurobi.com
[14]
Robert W Irving and Mark R Jerrum. 1994. Three-dimensional statistical data security problems. SIAM J. Comput. 23, 1 (1994), 170–184.
[15]
Klaus Jansen, Alexandra Lassota, and Lars Rohwedder. 2020. Near-linear time algorithm for n-fold ILPs via color coding. SIAM Journal on Discrete Mathematics 34, 4 (2020), 2282–2299.
[16]
Zoltán Király and Péter Kovács. 2012. Efficient implementations of minimum-cost flow algorithms. arXiv preprint arXiv:1207.6381 (2012).
[17]
Weiqiang Li, Rui Wang, and Jianan Zhang. 2022. Configuring data center network wiring. US Patent 11,223,527.
[18]
Dimitrios Michail, Joris Kinable, Barak Naveh, and John V Sichi. 2020. JGraphT—A Java library for graph data structures and algorithms. ACM Transactions on Mathematical Software (TOMS) 46, 2 (2020), 1–29.
[19]
Michel Minoux. 1986. Solving integer minimum cost flows with separable convex cost objective polynomially. Netflow at Pisa (1986), 237–239.
[20]
Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Mukarram Tariq, Rui Wang, Jianan Zhang, Virginia Beauregard, Patrick Conner, Steve Gribble, 2022. Jupiter evolving: Transforming google’s datacenter network via optical circuit switches and software-defined networking. In Proceedings of the ACM SIGCOMM 2022 Conference. 66–85.
[21]
Arjun Singh, Joon Ong, Amit Agarwal, Glen Anderson, Ashby Armistead, Roy Bannon, Seb Boving, Gaurav Desai, Bob Felderman, Paulie Germano, 2015. Jupiter rising: A decade of clos topologies and centralized control in google’s datacenter network. ACM SIGCOMM computer communication review 45, 4 (2015), 183–197.
[22]
CALIENT Technologies. 2023. CALIENT Data Sheet. https://www.calient.net
[23]
Min Yee Teh, Shizhen Zhao, Peirui Cao, and Keren Bergman. 2022. Enabling Quasi-Static Reconfigurable Networks With Robust Topology Engineering. IEEE/ACM Transactions on Networking (2022).
[24]
Laurence A Wolsey. 2020. Integer programming. John Wiley & Sons.
[25]
Shuyuan Zhang and Shu Shan. 2023. Repository. https://github.com/apnet23-reducing/evaluation
[26]
Shizhen Zhao, Rui Wang, Junlan Zhou, Joon Ong, Jeffrey C Mogul, and Amin Vahdat. 2019. Minimal Rewiring: Efficient Live Expansion for Clos Data Center Networks. In NSDI. 221–234.
Index Terms
- Reducing Reconfiguration Time in Hybrid Optical-Electrical Datacenter Networks
Recommendations
Lightwave Fabrics: At-Scale Optical Circuit Switching for Datacenter and Machine Learning Systems
ACM SIGCOMM '23: Proceedings of the ACM SIGCOMM 2023 ConferenceWe describe our experience developing what we believe to be the world's first large-scale production deployments of lightwave fabrics used for both datacenter networking and machine-learning (ML) applications. Using optical circuit switches (OCSes) and ...
Dynamic resource allocation in hybrid optical-electrical datacenter networks
Joint problem of bandwidth allocation and VM-placement in optical-electrical DC.Challenges: (i) limited reachability due to the size of the optical switch in the datacenter netework, (ii) dynamic creation of optical paths lead to the creation of ...
On the Parallel Reconfiguration of Virtual Networks in Hybrid Optical/Electrical Datacenter Networks
GLOBECOM 2020 - 2020 IEEE Global Communications ConferenceRecently, hybrid optical/electrical datacenter networks (HOE-DCNs) have been considered as a promising DCN architecture, because they merge the merits of electrical packet switching (EPS) and optical circuit switching (OCS). This paper considers the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2023
229 pages
ISBN:9798400707827
DOI:10.1145/3600061
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 September 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
APNET 2023
Acceptance Rates
Overall Acceptance Rate 50 of 118 submissions, 42%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 200Total Downloads
- Downloads (Last 12 months)200
- Downloads (Last 6 weeks)22
Reflects downloads up to 26 Sep 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatGet Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in