Brendon Go, Evan Liu
Original Paper: Singla, Ankit, Philip Brighten Godfrey, and Alexandra Kolla. “High Throughput Data Center Topology Design.” NSDI. Vol. 14. 2014.
The goal of network topology design is to create a data center topology that can achieve high throughput with low cost. Before Singla et. al’s High Throughput Data Center Topology Design, prior work explored many different designs but none claimed any notion of optimality. Moreover, prevailing research focused on homogenous network topologies where all switches have the same port count and line-speeds are constant. Singla et al’s paper makes contributions on heterogeneous network topologies but we focus on their work on homogenous topologies.
This paper’s first main contribution is supplying a non-trivial upper bound on for throughput and average shortest path length in any homogeneous network topology. They then show that, surprisingly, random graph topologies can achieve throughputs within only a few percent of this upper bound. Figure 1a and 2a show the ratio of predicted throughput to the theoretical upper bound (calculated using flow analysis) of random regular graphs (RRG) as degree varies. It shows that the predicted throughput and pathlength of a random regular graph is optimal, at least for all-to-all traffic. Figures 1b and 2b show that the observed average server path length (ASLP) closely tracks the theoretical lower bound.
The paper’s second main contribution is that they observe a somewhat surprising result: throughput is empirically unaffected under a wide range of cross-cluster connectivity. One might expect that greater cross-cluster connectivity would yield greater throughput, since there are more available links to send flow across clusters. However, the authors observe that throughput is relatively stable across a wide range of cross-cluster connectivity, only dropping when cross-cluster connectivity tends toward 0. The authors formalize this observation, providing upper-bounds on throughput, which do not change much under cross-cluster connectivity, and further show that these bounds are relatively tight empirically.