More Web Proxy on the site http://driver.im/

research-article

Optimizing Reconfigurable Optical Datacenters: The Power of Randomization

Authors:

Marcin Bienkowski,

David Fuchssteiner,

Stefan SchmidAuthors Info & Claims

SC '23: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 83, Pages 1 - 11

https://doi.org/10.1145/3581784.3607057

Published: 11 November 2023 Publication History

Abstract

Reconfigurable optical topologies are a promising new technology to improve datacenter network performance and cope with the explosive growth of traffic. In particular, these networks allow to directly and adaptively connect racks between which there is currently much traffic, hence making an optimal use of the bandwidth capacity by avoiding multi-hop forwarding.

This paper studies the dynamic optimization of such reconfigurable topologies, by adapting the network to the traffic in an online manner. The underlying algorithmic problem can be described as an online maximum weight b-matching problem, a generalization of maximum weight matching where each node has at most b ≥ 1 incident matching edges.

We make the case for a randomized approach for matching optimization. Our main contribution is a O(log b)-competitive algorithm and we show that it is asymptotically optimal. This algorithm is hence exponentially better than the best possible deterministic online algorithm.

We complement our theoretical results with extensive trace-driven simulations, based on real-world datacenter workloads.

Supplemental Material

MP4 File - SC23 paper presentation recording for "Optimizing Reconfigurable Optical Datacenters: The Power of Randomization"

SC23 paper presentation recording for "Optimizing Reconfigurable Optical Datacenters: The Power of Randomization", by Marcin Bienkowski, David Fuchssteiner and Stefan Schmid

Download
174.35 MB

References

[1]

Dimitris Achlioptas, Marek Chrobak, and John Noga. 2000. Competitive analysis of randomized paging algorithms. Theoretical Computer Science, 234, 1--2, 203--218.

Digital Library

[2]

Vamsi Addanki, Chen Avin, and Stefan Schmid. 2023. Mars: near-optimal throughput with shallow buffers in reconfigurable datacenter networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7, 1, 1--43.

Digital Library

[3]

Richard P Anstee. 1987. A polynomial algorithm for b-matchings: an alternative approach. Information Processing Letters, 24, 3, 153--157.

Digital Library

[4]

Chen Avin, Manya Ghobadi, Chen Griner, and Stefan Schmid. 2020. On the complexity of traffic traces and implications. In Proc. ACM SIGMETRICS.

Digital Library

[5]

Chen Avin, Kaushik Mondal, and Stefan Schmid. 2017. Demand-aware network designs of bounded degree. In Proc. International Symposium on Distributed Computing (DISC).

[6]

Chen Avin and Stefan Schmid. 2021. Renets: statically-optimal demand-aware networks. In Proc. SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS).

[7]

Hitesh Ballani et al. 2020. Sirius: a flat datacenter network with nanosecond optical switching. In Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication, 782--797.

[8]

Nikhil Bansal, Niv Buchbinder, and Joseph Naor. 2012. A primal-dual randomized algorithm for weighted paging. J. ACM, 59, 4, 19:1--19:24.

Digital Library

[9]

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. ACM, 267--280.

Digital Library

[10]

Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski, and Stefan Schmid. 2020. Online dynamic b-matching with applications to reconfigurable datacenter networks. In Proc. 38th International Symposium on Computer Performance, Modeling, Measurements and Evaluation (PERFORMANCE).

[11]

Davide Bilò, Luciano Gualà, and Guido Proietti. 2012. Improved approximability and non-approximability results for graph diameter decreasing problems. Theoretical Computer Science, 417, 12--22.

Digital Library

[12]

Benjamin Birnbaum and Claire Mathieu. 2008. On-line bipartite matching made simple. SIGACT News, 39, 1, 80--87.

Digital Library

[13]

Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press.

Digital Library

[14]

Niv Buchbinder, Kamal Jain, and Joseph Naor. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proc. 15th European Symp. on Algorithms (ESA), 253--264.

[15]

Jivitej S. Chadha, Naveen Garg, Amit Kumar, and V. N. Muralidhara. 2009. A competitive algorithm for minimizing weighted flow time on unrelated-machines with speed augmentation. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 679--684.

Digital Library

[16]

K. Chen, A. Singla, A. Singh, K. Ramachandran, L. Xu, Y. Zhang, X. Wen, and Y. Chen. 2014. Osa: an optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACM Transactions on Networking, 22, 2, (Apr. 2014), 498--511.

Digital Library

[17]

Kai Chen, Ankit Singla, Atul Singh, Kishore Ramachandran, Lei Xu, Yueping Zhang, Xitao Wen, and Yan Chen. 2014. OSA: an optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACM Transactions on Networking, 22, 2, 498--511.

Digital Library

[18]

Li Chen, Kai Chen, Zhonghua Zhu, Minlan Yu, George Porter, Chunming Qiao, and Shan Zhong. 2017. Enabling wide-spread communications on optical fabric with megaswitch. In Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation (NSDI'17). USENIX Association, Boston, MA, USA, 577--593. isbn: 9781931971379.

Digital Library

[19]

Shang-Tse Chuang, Ashish Goel, Nick McKeown, and Balaji Prabhakar. 1999. Matching output queueing with a combined input/output-queued switch. IEEE Journal on Selected Areas in Communications, 17, 6, 1030--1039.

Digital Library

[20]

Daniel D. Sleator and Robert E. Tarjan. 1985. Amortized efficiency of list update and paging rules. Communications of the ACM, 28, 2, 202--208.

Digital Library

[21]

Erik D Demaine and Morteza Zadimoghaddam. 2010. Minimizing the diameter of a network using shortcut edges. In Proc. Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 420--431.

Digital Library

[22]

Nikhil R. Devanur and Kamal Jain. 2012. Online matching with concave returns. In Proc. 44th ACM Symp. on Theory of Computing (STOC), 137--144.

[23]

Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. 2013. Randomized primal-dual analysis of RANKING for online bipartite matching. In Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (SODA), 101--107.

Digital Library

[24]

M. Dinitz and B. Moseley. 2020. Scheduling for weighted flow and completion times in reconfigurable networks. In IEEE Conference on Computer Communications (INFOCOM), 1043--1052.

[25]

Fred Douglis, Seth Robertson, Eric Van den Berg, Josephine Micallef, Marc Pucci, Alex Aiken, Maarten Hattink, Mingoo Seok, and Keren Bergman. 2021. Fleet---fast lanes for expedited execution at 10 terabits: program overview. IEEE Internet Computing.

[26]

Leah Epstein, Csanád Imreh, Asaf Levin, and Judit Nagy-György. 2011. On variants of file caching. In Proc. 38th Int. Colloq. on Automata, Languages and Programming (ICALP). Luca Aceto, Monika Henzinger, and Jiri Sgall, (Eds.) Springer, 195--206.

[27]

Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. 2008. A scalable, commodity data center network architecture. In ACM SIGCOMM Computer Communication Review number 4. Vol. 38. ACM, 63--74.

[28]

Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. 2011. Helios: a hybrid electrical/optical switch architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 41, 4, 339--350.

Digital Library

[29]

Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. 1991. Competitive paging algorithms. Journal of Algorithms, 12, 4, 685--699.

Digital Library

[30]

Klaus-Tycho Foerster, Monia Ghobadi, and Stefan Schmid. 2018. Characterizing the algorithmic complexity of reconfigurable data center architectures. In Proc. ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS).

Digital Library

[31]

Klaus-Tycho Foerster, Thibault Marette, Stefan Neumann, Claudia Plant, Ylli Sadikaj, Stefan Schmid, and Yllka Velaj. 2023. Analyzing the communication clusters in datacenters. In Proceedings of the ACM Web Conference (WWW), 3022--3032.

Digital Library

[32]

Zvi Galil. 1986. Efficient algorithms for finding maximum matching in graphs. ACM Comput. Surv., 18, 1, (Mar. 1986), 23--38.

[33]

Monia Ghobadi et al. 2016. Projector: agile reconfigurable data center interconnect. In Proceedings of the 2016 ACM SIGCOMM Conference. ACM, 216--229.

[34]

Andrew Gozzard, Max Ward, and Amitava Datta. 2018. Converting a network into a small-world network: fast algorithms for minimizing average path length through link addition. Information Sciences, 422, 282--289.

Digital Library

[35]

Chen Griner, Johannes Zerwas, Andreas Blenk, Manya Ghobadi, Stefan Schmid, and Chen Avin. 2022. Cerberus: the power of choices in datacenter topology design (a throughput perspective). In Proc. ACM SIGMETRICS.

Digital Library

[36]

Chuanxiong Guo, Guohan Lu, Dan Li, Haitao Wu, Xuan Zhang, Yunfeng Shi, Chen Tian, Yongguang Zhang, and Songwu Lu. 2009. Bcube: a high performance, server-centric network architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 39, 4, 63--74.

Digital Library

[37]

Matthew Nance Hall, Klaus-Tycho Foerster, Stefan Schmid, and Ramakrishnan Durairajan. 2021. A survey of reconfigurable optical networks. In Optical Switching and Networking (OSN), Elsevier.

[38]

Navid Hamedazimi, Zafar Qazi, Himanshu Gupta, Vyas Sekar, Samir R Das, Jon P Longtin, Himanshu Shah, and Ashish Tanwer. 2014. Firefly: a reconfigurable wireless data center fabric using free-space optics. In ACM SIGCOMM Computer Communication Review number 4. Vol. 44. ACM, 319--330.

[39]

Michelle Hampson. 2021. Reconfigurable optical networks will move super-computerdata 100x faster. In IEEE Spectrum.

[40]

Kathrin Hanauer, Monika Henzinger, Lara Ost, and Stefan Schmid. 2023. Dynamic demand-aware link scheduling for reconfigurable datacenters. In IEEE INFOCOM.

[41]

Kathrin Hanauer, Monika Henzinger, Stefan Schmid, and Jonathan Trummer. 2022. Fast and heavy disjoint weighted matchings for demand-aware datacenter topologies. In Proc. IEEE Conference on Computer Communications (INFOCOM).

Digital Library

[42]

Bala Kalyanasundaram and Kirk Pruhs. 2000. Speed is as powerful as clairvoyance. J. ACM, 47, 4, 617--643.

Digital Library

[43]

Bala Kalyanasundaram and Kirk R Pruhs. 2000. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233, 1--2, 319--325.

Digital Library

[44]

Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An optimal algorithm for on-line bipartite matching. In Proc. 22nd ACM Symp. on Theory of Computing (STOC), 352--358.

[45]

Simon Kassing, Asaf Valadarsky, Gal Shahaf, Michael Schapira, and Ankit Singla. 2017. Beyond fat-trees without antennae, mirrors, and disco-balls. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication. ACM, 281--294.

Digital Library

[46]

Wolfgang Kellerer, Patrick Kalmbach, Andreas Blenk, Arsany Basta, Martin Reisslein, and Stefan Schmid. 2019. Adaptable and data-driven softwarized networks: review, opportunities, and challenges. Proceedings of the IEEE, 107, 4, 711--731.

[47]

Janardhan Kulkarni, Stefan Schmid, and Pawel Schmidt. 2021. Scheduling opportunistic links in two-tiered reconfigurable datacenters. In 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).

Digital Library

[48]

Yuliang Li et al. 2019. Hpcc: high precision congestion control. In Proceedings of the ACM Special Interest Group on Data Communication, 44--58.

[49]

Vincent Liu, Daniel Halperin, Arvind Krishnamurthy, and Thomas E. Anderson. 2013. F10: A fault-tolerant engineered network. In NSDI, 399--412.

[50]

Yunpeng James Liu, Peter Xiang Gao, Bernard Wong, and Srinivasan Keshav. 2014. Quartz: a new design element for low-latency dcns. SIGCOMM Comput. Commun. Rev., 44, 4, (Aug. 2014), 283--294.

Digital Library

[51]

Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In Proc. 43rd ACM Symp. on Theory of Computing (STOC), 597--606.

Digital Library

[52]

Lyle A. McGeoch and Daniel D. Sleator. 1991. A strongly competitive randomized paging algorithm. Algorithmica, 6, 6, 816--825.

Digital Library

[53]

Nick McKeown. 1999. The islip scheduling algorithm for input-queued switches. IEEE/ACM transactions on networking, 7, 2, 188--201.

[54]

Aranyak Mehta. 2013. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8, 4, 265--368.

Digital Library

[55]

Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. 2007. Adwords and generalized online matching. Journal of the ACM, 54, 5.

Digital Library

[56]

William M Mellette, Rajdeep Das, Yibo Guo, Rob McGuinness, Alex C Snoeren, and George Porter. 2020. Expanding across time to deliver bandwidth efficiency and low latency. In 17th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 20), 1--18.

[57]

William M Mellette, Rob McGuinness, Arjun Roy, Alex Forencich, George Papen, Alex C Snoeren, and George Porter. 2017. Rotornet: a scalable, low-complexity, optical datacenter network. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication. ACM, 267--280.

Digital Library

[58]

Adam Meyerson and Brian Tagiku. 2009. Minimizing average shortest path distances via shortcut edge addition. In Proc. Int. Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 272--285.

Digital Library

[59]

Pooria Namyar, Sucha Supittayapornpong, Mingyang Zhang, Minlan Yu, and Ramesh Govindan. 2021. A throughput-centric view of the performance of datacenter topologies. In To appear in Proceedings of the ACM SIGCOMM 2021 conference.

[60]

Joseph Naor and David Wajc. 2015. Near-optimum online ad allocation for targeted advertising. In Proc. 16th ACM Conf. on Economics and Computation (EC), 131--148.

Digital Library

[61]

Manos Papagelis, Francesco Bonchi, and Aristides Gionis. 2011. Suggesting ghost edges for a smaller world. In Proc. 20th ACM International Conference on Information and Knowledge Management (CIKM), 2305--2308.

Digital Library

[62]

Nikos Parotsidis, Evaggelia Pitoura, and Panayiotis Tsaparas. 2015. Selecting shortcuts for a smaller world. In Proc. SIAM International Conference on Data Mining, 28--36.

[63]

George Porter, Richard Strong, Nathan Farrington, Alex Forencich, Pang Chen-Sun, Tajana Rosing, Yeshaiahu Fainman, George Papen, and Amin Vahdat. 2013. Integrating microsecond circuit switching into the data center. In Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM (SIGCOMM '13). Association for Computing Machinery, Hong Kong, China, 447--458. isbn: 9781450320566.

Digital Library

[64]

Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex C Snoeren. 2015. Inside the social network's (datacenter) network. In ACM SIGCOMM Computer Communication Review. Vol. 45, 123--137.

Digital Library

[65]

Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. 2016. Splaynet: towards locally self-adjusting networks. IEEE/ACM Transactions on Networking (ToN), 24, 3, 1421--1433.

Digital Library

[66]

Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and combinatorics. Springer.

[67]

Roy Schwartz, Mohit Singh, and Sina Yazdanbod. 2019. Online and offline greedy algorithms for routing with switching costs. arXiv preprint arXiv:1905.02800.

[68]

Arjun Singh et al. 2015. Jupiter rising: A decade of clos topologies and centralized control in google's datacenter network. Computer Communication Review, 45, 5, 183--197.

Digital Library

[69]

Ankit Singla, Chi-Yao Hong, Lucian Popa, and Philip Brighten Godfrey. 2012. Jellyfish: networking data centers randomly. In NSDI, 225--238.

[70]

Ankit Singla, Atul Singh, Kishore Ramachandran, Lei Xu, and Yueping Zhang. 2010. Proteus: a topology malleable data center network. In Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. ACM, 8.

Digital Library

[71]

Min Yee Teh, Zhenguo Wu, and Keren Bergman. 2020. Flexspander: augmenting expander networks in high-performance systems with optical bandwidth steering. IEEE/OSA Journal of Optical Communications and Networking, 12, 4, B44--B54.

[72]

Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, and Pramod Viswanath. 2018. Costly circuits, submodular schedules and approximate carathéodory theorems. Queueing Systems, 88, 3--4, 311--347.

[73]

Guohui Wang, David G Andersen, Michael Kaminsky, Konstantina Papagiannaki, TS Ng, Michael Kozuch, and Michael Ryan. 2011. C-through: part-time optics in data centers. ACM SIGCOMM Computer Communication Review, 41, 4, 327--338.

[74]

Haitao Wu, Guohan Lu, Dan Li, Chuanxiong Guo, and Yongguang Zhang. 2009. Mdcube: a high performance network structure for modular data center interconnection. In Proceedings of the 5th international conference on Emerging networking experiments and technologies. ACM, 25--36.

Digital Library

[75]

Neal E. Young. 1991. On-line caching as cache size varies. In Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 28--30 January 1991, San Francisco, California, USA. Alok Aggarwal, (Ed.), 241--250.

Digital Library

[76]

Neal E. Young. 1994. The k-server dual and loose competitiveness for paging. Algorithmica, 11, 6, 525--541.

Digital Library

[77]

Johannes Zerwas, Csaba Györgyi, Andreas Blenk, Stefan Schmid, and Chen Avin. 2023. Duo: a high-throughput reconfigurable datacenter network using local routing and control. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7, 1, 1--25.

Digital Library

[78]

Xia Zhou, Zengbin Zhang, Yibo Zhu, Yubo Li, Saipriya Kumar, Amin Vahdat, Ben Y Zhao, and Haitao Zheng. 2012. Mirror mirror on the ceiling: flexible wireless links for data centers. ACM SIGCOMM Computer Communication Review, 42, 4, 443--454.

Digital Library

Cited By

Figiel AMelnyk DNichterlein APourdamghani ASchmid SAgrawal KPetrank E(2024)Brief Announcement: Minimizing the Weighted Average Shortest Path Length in Demand-Aware Networks via Matching AugmentationProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3660264(447-449)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3660264

Index Terms

Optimizing Reconfigurable Optical Datacenters: The Power of Randomization
1. Networks
  1. Network algorithms
  2. Network architectures

Recommendations

Partially effective randomization in simulations between arbitrary and common PRAMs

It is known that Θ(log n/log log n) steps are needed to simulate one step of ARBITRARY CRCW PRAMs by COMMON CRCW PRAMs, but it was open whether there is a faster simulation when randomization is allowed. This paper gives both positive and negative ...
Randomization in particle swarm optimization for global search ability

This paper introduces a novel particle swarm optimization (PSO) with random position to improve the global search ability of particle swarm optimization with linearly decreasing inertia weight (IWPSO). Standard particle swarm optimization and most of ...
The impact of randomization in smoothing networks

We revisit randomized smoothing networks (Herlihy and Tirthapura in J Parallel Distrib Comput 66(5):626---632, 2006), which are made up of balancers and wires. We assume that balancers are oriented independently and uniformly at random. Tokens arrive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '23: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

November 2023

1428 pages

ISBN:9798400701092

DOI:10.1145/3581784

Chair:
Dorian Arnold,
Program Chair:
Rosa M Badia,
Program Co-chair:
Kathryn Mohror

Copyright © 2023 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 November 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SC '23

Sponsor:

SIGHPC

SC '23: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 17, 2023

CO, Denver, USA

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
158
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Figiel AMelnyk DNichterlein APourdamghani ASchmid SAgrawal KPetrank E(2024)Brief Announcement: Minimizing the Weighted Average Shortest Path Length in Demand-Aware Networks via Matching AugmentationProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3660264(447-449)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3660264

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