Authors

David C. Kutner, Iain A. Stewart

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.

Keywords

Algorithms; Complexity; Reconfigurable topologies; Optical circuit switches; Software-defined networking

Citation

  • Journal: Theoretical Computer Science
  • Year: 2025
  • Volume: 1038
  • Issue:
  • Pages: 115154
  • Publisher: Elsevier BV
  • DOI: 10.1016/j.tcs.2025.115154

BibTeX

@article{Kutner_2025,
  title={{Reconfigurable routing in data center networks}},
  volume={1038},
  ISSN={0304-3975},
  DOI={10.1016/j.tcs.2025.115154},
  journal={Theoretical Computer Science},
  publisher={Elsevier BV},
  author={Kutner, David C. and Stewart, Iain A.},
  year={2025},
  pages={115154}
}

Download the bib file

References

  • Abbott, On the construction of snake in the box codes. Util. Math. (1991)
  • Abbott, H. L. & Katchalski, M. On the snake in the box problem. Journal of Combinatorial Theory, Series B vol. 45 13–24 (1988) – 10.1016/0095-8956(88)90051-2
  • Al-Fares, M., Loukissas, A. & Vahdat, A. A scalable, commodity data center network architecture. ACM SIGCOMM Computer Communication Review vol. 38 63–74 (2008) – 10.1145/1402946.1402967
  • Avin, C. & Schmid, S. Toward demand-aware networking. ACM SIGCOMM Computer Communication Review vol. 48 31–40 (2019) – 10.1145/3310165.3310170
  • Berman, Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. (2002)
  • Chaintoutis, C. et al. Free Space Intra-Datacenter Interconnects Based on 2D Optical Beam Steering Enabled by Photonic Integrated Circuits. Photonics vol. 5 21 (2018) – 10.3390/photonics5030021
  • Chen, T., Gao, X. & Chen, G. The features, hardware, and architectures of data center networks: A survey. Journal of Parallel and Distributed Computing vol. 96 45–74 (2016) – 10.1016/j.jpdc.2016.05.009
  • Clark, B. N., Colbourn, C. J. & Johnson, D. S. Unit disk graphs. Discrete Mathematics vol. 86 165–177 (1990) – 10.1016/0012-365x(90)90358-o
  • Clark, The bisection width of cubic graphs. Bull. Aust. Math. Soc. (1988)
  • Fenz, Efficient non-segregated routing for reconfigurable demand-aware networks. (2019)
  • Fenz, T., Foerster, K.-T., Schmid, S. & Villedieu, A. Efficient non-segregated routing for reconfigurable demand-aware networks. Computer Communications vol. 164 138–147 (2020) – 10.1016/j.comcom.2020.10.003
  • Foerster, Characterizing the algorithmic complexity of reconfigurable data center architectures. (2018)
  • Foerster, K.-T., Pacut, M. & Schmid, S. On the Complexity of Non-Segregated Routing in Reconfigurable Data Center Architectures. ACM SIGCOMM Computer Communication Review vol. 49 2–8 (2019) – 10.1145/3336937.3336939
  • Foerster, K.-T. & Schmid, S. Survey of Reconfigurable Data Center Networks. ACM SIGACT News vol. 50 62–79 (2019) – 10.1145/3351452.3351464
  • Gonzalez, T. F. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science vol. 38 293–306 (1985) – 10.1016/0304-3975(85)90224-5
  • Guo, C. et al. BCube. ACM SIGCOMM Computer Communication Review vol. 39 63–74 (2009) – 10.1145/1594977.1592577
  • Guo, DCell: a scalable and fault-tolerant network structure for data centers. (2008)
  • Gupta, S., Sa’ar, G. & Zehavi, M. Grid recognition: Classical and parameterized computational perspectives. Journal of Computer and System Sciences vol. 136 17–62 (2023) – 10.1016/j.jcss.2023.02.008
  • Hall, A survey of reconfigurable optical networks. Opt. Switching Netw. (2021)
  • Hamedazimi, Firefly: a reconfigurable wireless data center fabric using free-space optics. (2014)
  • OEIS Foundation Inc.,
  • Pak, I. & Radoičić, R. Hamiltonian paths in Cayley graphs. Discrete Mathematics vol. 309 5501–5508 (2009) – 10.1016/j.disc.2009.02.018
  • Singla, Jellyfish: networking data centers randomly. (2012)
  • Valadarsky, Xpander: towards optimal-performance datacenters. (2016)
  • Zhang, S., Xue, X., Tangdiongga, E. & Calabretta, N. Low-Latency Optical Wireless Data-Center Networks Using Nanoseconds Semiconductor-Based Wavelength Selectors and Arrayed Waveguide Grating Router. Photonics vol. 9 203 (2022) – 10.3390/photonics9030203