City Research Online

Abstract

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 [22]), 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 two online heuristics for self-adjusting k-ary tree networks. Empirical results show that our heuristics work better than SplayNet in most of the real network traces and for average to low locality synthetic traces, and are only a little inferior to SplayNet in all remaining traces. We build our online algorithms by first solving the offline case. First, we compute an offline (optimal) static demand-aware network for arbitrary traffic patterns in O(n3 · k) time via dynamic programming, where n is the number of network nodes (e.g., datacenter racks), and also improve the bound for the special case of uniformly distributed traffic. Then, we present a centroid-based approach to demand-aware network designs that we use both in the offline static and online settings. In the offline uniform-workload case, we construct this centroid network in linear time O(n).

Publication Type:	Conference or Workshop Item (Paper)
Additional Information:	© Evgeniy Feder, Anton Paramonov, Pavel Mavrin, Iosif Salem, Vitaly Aksenov, and Stefan Schmid; licensed under Creative Commons License CC-BY 4.0
Publisher Keywords:	self-adjusting networks, networks, splay-tree, k-ary tree
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology School of Science & Technology > Computer Science
SWORD Depositor:	Symplectic Administrator

Export

Downloads