Toward Self-Adjusting $k$-Ary Search Tree Networks
Evgeniy Feder, Anton Paramonov, Pavel Mavrin, Iosif Salem, Stefan Schmid, Vitaly Aksenov · 2024
Datacenter networks are becoming increasingly flexible with the incorporation of new optical communication technologies, such as optical circuit switches, enabling self-adjusting topologies that can adapt to the traffic pattern in a demand-aware manner. In this paper, we take the first steps toward demand-aware and self-adjusting$k$-ary tree networks. These are more powerful generalizations of existing binary search tree networks (like SplayNet [14]), which have been at the core of self-adjusting network (SAN) designs.$k$-ary search tree networks are a natural generalization offering nodes of higher degrees, reduced route lengths, and local routing in spite of reconfigurations (due to maintaining the search property). Our main results are algorithms for static$k$-ary tree networks and two online heuristics for self-adjusting$k$-ary tree networks.