This paper studies the design of self-adjusting networks whose topology dynamically adapts to the workload, in an online and demand-aware manner. This problem is motivated by emerging optical technologies which allow to reconfigure the datacenter topology at runtime. Our main contribution is ReNet, a self-adjusting network which maintains a balance between the benefits and costs of reconfigurations. In particular, we show that ReNets are statically optimal for arbitrary sparse communication demands, i.e., perform at least as good as any fixed demand-aware network designed with a perfect knowledge of the future demand. Furthermore, ReNets provide compact and local routing, by leveraging ideas from self-adjusting datastructures.
@cite_61: Emerging communication technologies allow to reconfigure the physical network topology at runtime, enabling demand-aware networks (DANs): networks whose topology is optimized toward the workload they serve. However, today, only little is known about the fundamental algorithmic problems underlying the design of such demand-aware networks. This paper presents the first bounded-degree, demand-aware network, ct-DAN, which minimizes both congestion and route lengths. The designed network is provably (asymptotically) optimal in each dimension individually: we show that there do not exist any bounded-degree networks providing shorter routes (independently of the load), nor do there exist networks providing lower loads (independently of the route lengths). The main building block of the designed ct-DAN networks are ego-trees: communication sources arrange their communication partners in an optimal tree, individually. While the union of these ego-trees forms the basic structure of cl-DANs, further techniques are presented to ensure bounded degrees (for scalability).
@cite_43: This paper initiates the study of locally self-adjusting networks: networks whose topology adapts dynamically and in a decentralized manner, to the communication pattern @math . Our vision can be seen as a distributed generalization of the self-adjusting datastructures introduced by Sleator and Tarjan, 1985: In contrast to their splay trees which dynamically optimize the lookup costs from a single node (namely the tree root), we seek to minimize the routing cost between arbitrary communication pairs in the network. As a first step, we study distributed binary search trees (BSTs), which are attractive for their support of greedy routing. We introduce a simple model which captures the fundamental tradeoff between the benefits and costs of self-adjusting networks. We present the SplayNet algorithm and formally analyze its performance, and prove its optimality in specific case studies. We also introduce lower bound techniques based on interval cuts and edge expansion, to study the limitations of any demand-optimized network. Finally, we extend our study to multi-tree networks, and highlight an intriguing difference between classic and distributed splay trees.
@cite_16: 
@cite_1: Traditionally, networks such as datacenter interconnects are designed to optimize worst-case performance under arbitrary traffic patterns. Such network designs can however be far from optimal when considering the actual workloads and traffic patterns which they serve. This insight led to the development of demand-aware datacenter interconnects which can be reconfigured depending on the workload. Motivated by these trends, this paper initiates the algorithmic study of demand-aware networks, and in particular the design of bounded-degree networks. The inputs to the network design problem are a discrete communication request distribution, ( D ), defined over communicating pairs from the node set V, and a bound, ( ), on the maximum degree. In turn, our objective is to design an (undirected) demand-aware network (N=(V,E) ) of bounded-degree ( ), which provides short routing paths between frequently communicating nodes distributed across (N ). In particular, the designed network should minimize the expected path length on (N ) (with respect to ( D )), which is a basic measure of the efficiency of the network. We derive a general lower bound based on the entropy of the communication pattern ( D ), and present asymptotically optimal demand-aware network design algorithms for important distribution families, such as sparse distributions and distributions of locally bounded doubling dimensions.
In terms of formal guarantees, an upper bound on what can be achieved in terms of statically optimized demand-aware networks is due to @cite_1 , who build upon initial insights in @cite_43 @cite_16 . We in this paper leverage the degree reduction technique of @cite_1 , however, to derive a very different result. The fixed demand-aware network designs by @cite_1 have recently also been extended to optimize for load, in addition to route lengths @cite_61 .