Reconfigurable routing in data center networks

Stewart, Iain; Kutner, David

Abstract

A hybrid network is a static (electronic) network that is augmented with optical switches. The Reconfigurable Routing Problem (RRP) in hybrid networks is the problem of finding settings for the optical switches augmenting a static network so as to achieve optimal delivery of some given workload. The problem has previously been studied in various scenarios with both tractability and NP-hardness results obtained. However, the data center and interconnection networks to which the problem is most relevant are almost always such that the static network is highly structured (and often node-symmetric) whereas all previous results assume that the static network can be arbitrary (which makes existing computational hardness results less technologically relevant and also easier to obtain). In this paper, and for the first time, we prove various intractability results for RRP where the underlying static network is highly structured, for example consisting of a hypercube, and also extend some existing tractability results.

Citation

Stewart, I., & Kutner, D. (2025). Reconfigurable routing in data center networks. Theoretical Computer Science, 1038, Article 115154. https://doi.org/10.1016/j.tcs.2025.115154

• Journal Article Type: Article
• Acceptance Date: Feb 26, 2025
• Online Publication Date: Mar 12, 2025
• Publication Date: May 22, 2025
• Deposit Date: Mar 4, 2025
• Publicly Available Date: Mar 13, 2025
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 1038
• Article Number: 115154
• DOI: https://doi.org/10.1016/j.tcs.2025.115154
• Public URL: https://durham-repository.worktribe.com/output/3672164