Small-World Datacenters

Datacenters Inspired by Small-World Networks

Small-world datacenters project proposes an unorthodox way to wire up a datacenter; namely, eschew all hierarchical switches and connect nodes at random on top of a regular grid connections according to a small-world-inspired distribution. Specifically, nodes are connected at the small scale in a regular pattern, such as a ring, torus or cube, such that every node can route efficiently to nodes in its immediate vicinity, and amended by the addition of random links to nodes throughout the datacenter.


Papers

People

1. Characteristics

Small-world datacenters achieve higher bisection bandwidth than a typical hierarchical datacenters. Even a simple greedy geographical algorithm can efficiently route packets to far away locations. Coupled with geographical address assignment, the resulting network can provide content routing in addition to traditional routing, and thus efficiently implement datacenter applications such as a key-value store.

2. Construction and Scaling

Each server in small-world datacenters directly connects to multiple others and wiring process requires more work than connecting a hierarchical datacenter. Wiring regular grid links can be easy and using wiring techniques for supercomputers, we can limit the maximum wire length to be short. A reusable rack structure using patch panels can reduce the wiring overhead for random links by enabling coarse grain management of wires. Precutting the wires according to the known random probability can speed up the wiring process.

Adding new nodes require 1) wiring regular grid links and 2) wiring random links. Wiring regular links can be straightforward disconnecting the existing links, adding new nodes in-between disconnected links and connecting new nodes in a way that preserves the grid pattern. Random links' destination set D, are determined using Kleinberg's random probability for connecting small-world networks. One of random links in each server in D is disconnected from a server in S, where S is the set of servers at the other side of the random links from D. New nodes' random links are connected to D's disconnected random links. Disconnected random links in S are connected within S.

Regular links or grids are torus-based structures and arbitrary number of nodes can be added. For example, if a small-world datacenter has 16 nodes and is based on a 4 by 4 2-d torus, less than 4 nodes can be added. If 2 nodes are added, the datacenter will be based on 5 by 5 2-d torus with 2 nodes missing on a side. This does not change the network characteristics of small-world datacenters.

3. Performance

Small-world datacenters can achieve higher bandwidth and fault tolerance compared to both conventional hierarchical datacenters, and the recently proposed CamCube topology. Depending on the network traffic and the support of hardware accelerations for packet switching, small-world datacenters can achieve up to 16 times higher bandwidth than a conventional datacenter. Small-world datacenters maintain over 90% of connectivity among live server nodes even until 90% of racks fail.

4. Comparison with Other Datacenter Network Topologies

- CamCube [Abu-Libdeh, Costa, Rowstron, O'Shea, and Donnelly'2010]

CamCube is based on a 3-d torus and provides a content-routing API that provides a deterministic address to node mapping. Small-world datacenters supports all features supported by CamCube, including the ability to perform content routing. Such routing is more efficient in small-world networks because our random links provide the ability to quickly traverse large spans.

- Scafida [Gyarmati, and Trinh'2010]

Scafida is a datacenter network inspired by scale-free network, built solely from random links. In contrast, small-world datacenters pursue a mix of regular and random connections. For this reason, small-world datacenters can provide more effective content routing and easier implementation of regular packet routing.

- Jellyfish [Singla, Hong, Popa, and Godfrey'2012]

Jellyfish addresses the scalablity problem in datacenters by connecting top-of-rack switches in a totally random manner. Small-world datacenters utilize random connections at server level granularity and the existence of regular links makes regular packet routing easier than that in Jellyfish. From a fault tolerance viewpoint, small-world datacenters are more robust since they do not have top-of-rack switches as single points of failure.

Acknowledgements

This material is based upon work supported by National Science Foundation under Grant No. 0546568. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.