ReNets: Statically-Optimal Demand-Aware Networks

This paper studies the design of self-adjusting datacenter networks whose physical topology dynamically adapts to the workload, in an online and demand-aware manner. We propose ReNet, a self-adjusting network which does not require any predictions about future demands and amortizes reconfigurations: it performs as good as a hypothetical static algorithm with perfect knowledge of the future demand. In particular, we show that for arbitrary sparse communication demands, ReNets achieve static optimality, a fundamental property of learning algorithms, and that route lengths in ReNets are proportional to existing lower bounds, which are known to relate to an entropy metric of the demand. ReNets provide additional desirable properties such as compact and local routing and flat addressing therefore ensuring scalability and further reducing the overhead of reconfiguration. To achieve these properties, ReNets combine multiple self-adjusting tree topologies which are optimized toward individual sources, called ego-trees in this paper.