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.
- Small-World Datacenters
Ji-Yong Shin, Bernard Wong, and Emin Gün Sirer
In Proceedings of 2nd ACM Symposium on Cloud Computing, Cascais, Portugal, Oct 2011
Full Paper [ACM],
Slides [ pptx
| pdf ]
Poster [ pdf ]
Small-world datacenters achieve higher bisection bandwidth than a typical
Even a simple greedy geographical algorithm can
efficiently route packets to far away locations.
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.
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 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 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 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.
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.