Characterizing the algorithmic complexity of reconfigurable data center architectures

TLDR

Emerging data center architectures are becoming reconfigurable, yet the algorithmic complexity of these hybrid topologies—combining reconfigurable optical or wireless components with static electrical switches—remains poorly understood, especially as current proposals enforce exclusive routing by labeling flows as mice or elephant. The study aims to show that this artificial segregation in routing policy yields non‑optimal paths and to propose algorithms that route packets seamlessly across the entire network. We present the first algorithmic analysis of reconfigurable network architectures, offering optimality and hardness proofs that relate to both topology and routing policy. Our results demonstrate that classical matching algorithms are optimal only when the topology contains a single reconfigurable switch and routing is segregated; otherwise, seamless routing across hybrid networks is NP‑hard, even for just two flows with multiple reconfigurable switches.

Abstract

Emerging data center architectures are becoming reconfigurable. While prior work has shown the practical benefits of reconfigurable topologies, the underlying algorithmic complexity is not yet well understood. In particular, most reconfigurable topologies are hybrid, where parts of the network are reconfigurable (consisting of optical or wireless devices) while other parts are static (consisting of electrical switches). Current proposals enforce a routing policy that routes flows on either part "exclusively" by labeling flows as mice or elephant. We show that such artificial segregation in routing policy results in non-optimal paths and argue for algorithms that route packets across the network seamlessly. In doing so, we present the first algorithmic study of reconfigurable network architectures and provide optimality and hardness proofs in terms of topology and routing policy. Our results show that classical matching algorithms, as used in prior work, are optimal only when the topology consists of one reconfigurable switch, and the routing policy is enforced to be segregated. In other words, if there is an option of routing flows seamlessly along reconfigurable and non-reconfigurable parts of the network, matching algorithms are not optimal. In fact, when the hybrid network is seen from a joint perspective, optimal routing is an NP-hard problem. We further show that optimally routing even two flows in a network with multiple reconfigurable switches is an NP-hard problem as well.