  Datacenter networks are becoming increasingly flexible with the incorporation
of new networking technologies, such as optical circuit switches. These
technologies allow for programmable network topologies that can be reconfigured
to better serve network traffic, thus enabling a trade-off between the benefits
(i.e., shorter routes) and costs of reconfigurations (i.e., overhead).
Self-Adjusting Networks (SANs) aim at addressing this trade-off by exploiting
patterns in network traffic, both when it is revealed piecewise (online dynamic
topologies) or known in advance (offline static topologies). In this paper, we
take the first steps toward Self-Adjusting k-ary tree networks. These are more
powerful generalizations of existing binary search tree networks (like
SplayNets), which have been at the core of SAN designs. k-ary search tree
networks are a natural generalization offering nodes of higher degrees, reduced
route lengths for a fixed number of nodes, and local routing in spite of
reconfigurations. We first compute an offline (optimal) static network for
arbitrary traffic patterns in $O(n^3 \cdot k)$ time via dynamic programming,
and also improve the bound to $O(n^2 \cdot k)$ for the special case of
uniformly distributed traffic. Then, we present a centroid-based topology of
the network that can be used both in the offline static and the online setting.
In the offline uniform-workload case, we construct this quasi-optimal network
in linear time $O(n)$ and, finally, we present online self-adjusting k-ary
search tree versions of SplayNet. We evaluate experimentally our new structure
for $k=2$ (allowing for a comparison with existing SplayNets) on real and
synthetic network traces. Our results show that this approach works better than
SplayNet in most of the real network traces and in average to low locality
synthetic traces, and is only little inferior to SplayNet in all remaining
traces.
