In the Search of Optimal Tree Networks: Hardness and Heuristics Article Swipe
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1145/3712256.3726425
Traffic in datacenters may follow some pattern: some pairs of servers communicate more frequently than others. Demand-oblivious networks may perform poorly for such workloads, and demand-aware networks optimized for traffic should be used instead. Unfortunately, not all shapes of networks are feasible in real hardware. Practical limitations are usually provided in the form of a topology. For example, a network may be required to be a binary tree, a bounded-degree graph or a Fat tree. In this work, we consider a topology of a binary tree, one of the most fundamental network topologies. We show that already finding an optimal demand-aware binary tree network is NP-hard. Then, we explore how various optimization techniques, including simple local searches, as well as deterministic mutation and crossover operators, cope with generating efficient tree networks on real-life and synthetic workloads.
Related Topics To Compare & Contrast
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1145/3712256.3726425
- OA Status
- hybrid
- Cited By
- 1
- References
- 40
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4412106652