Distributed Self-Adjusting Tree Networks
Bruna Soares Peres, Otavio A. de O. Souza, Olga Goussevskaia, Chen Avin, Stefan Schmid · 2019
We consider the problem of designing dynamic network topologies that self-adjust to the (possibly changing) traffic pattern they serve. Such demand-aware networks currently receive much attention, especially in the context of datacenters, due to emerging technologies supporting the fast reconfiguration of the physical topology. We present the first fully distributed, provably efficient self-adjusting network. Our network called DiSptayNet relies on algorithms that perform decentralized and concurrent topological adjustments to account for changes in the demand. We present a rigorous formal analysis of the correctness and performance of DiSptayNet, which can be seen as an interesting generalization of analyses known from sequential self-adjusting datastructures. We also report on results from extensive trace-driven simulations.