Load-Optimization in Reconfigurable Networks
- 5 March 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 48 (3), 39-44
- https://doi.org/10.1145/3453953.3453962
Abstract
Emerging reconfigurable data centers introduce the unprecedented flexibility in how the physical layer can be programmed to adapt to current traffic demands. These reconfigurable topologies are commonly hybrid, consisting of static and reconfigurable links, enabled by e.g. an Optical Circuit Switch (OCS) connected to top-of-rack switches in Clos networks. Even though prior work has showcased the practical benefits of hybrid networks, several crucial performance aspects are not well understood. In this paper, we study the algorithmic problem of how to jointly optimize topology and routing in reconfigurable data centers with a known traffic matrix, in order to optimize a most fundamental metric, maximum link load. We chart the corresponding algorithmic landscape by investigating both un-/splittable flows and (non-)segregated routing policies. We moreover prove that the problem is not submodular for all these routing policies, even in multi-layer trees, where a topological complexity classification of the problem reveals that already trees of depth two are intractable. However, networks that can be abstracted by a single packet switch (e.g., nonblocking Fat-Tree topologies) can be optimized efficiently, and we present optimal polynomialtime algorithms accordingly. We complement our theoretical results with trace-driven simulation studies, where our algorithms can significantly improve the network load in comparison to the state of the art.Keywords
This publication has 29 references indexed in Scilit:
- ProjecToRPublished by Association for Computing Machinery (ACM) ,2016
- Optimizing Bulk Transfers with Software-Defined Optical WANPublished by Association for Computing Machinery (ACM) ,2016
- Scheduling techniques for hybrid circuit/packet networksPublished by Association for Computing Machinery (ACM) ,2015
- Inside the Social Network's (Datacenter) NetworkPublished by Association for Computing Machinery (ACM) ,2015
- Scalable, optimal flow routing in datacenters via local link balancingPublished by Association for Computing Machinery (ACM) ,2013
- pFabricPublished by Association for Computing Machinery (ACM) ,2013
- Augmenting data center networks with multi-gigabit wireless linksPublished by Association for Computing Machinery (ACM) ,2011
- Improving datacenter performance and robustness with multipath TCPACM SIGCOMM Computer Communication Review, 2011
- On Nonblocking Folded-Clos Networks in Computer Communication EnvironmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- A Study of Non-Blocking Switching NetworksBell System Technical Journal, 1953