Reconfigurable routing in data center networks

Kutner, David C.; Stewart, Iain A.

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

Kutner, D. C., & Stewart, I. A. (2024, September). Reconfigurable routing in data center networks. Presented at 20th International Symposium on Algorithmics of Wireless Networks, ALGOWIN 2024, Egham, UK

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th International Symposium on Algorithmics of Wireless Networks, ALGOWIN 2024
• Start Date: Sep 5, 2024
• End Date: Sep 6, 2024
• Acceptance Date: Aug 1, 2024
• Online Publication Date: Dec 27, 2024
• Publication Date: 2025-01
• Deposit Date: Sep 11, 2024
• Publicly Available Date: Jan 21, 2025
• Print ISSN: 0302-9743
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 15026
• Pages: 117-130
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Algorithmics of Wireless Networks
• ISBN: 9783031745799
• DOI: https://doi.org/10.1007/978-3-031-74580-5_9
• Public URL: https://durham-repository.worktribe.com/output/2860604