Measuring and Understanding Throughput of Network Topologies

In settings varying from transport networks to communica-tion networks, a fundamental goal of network design has been to achieve high throughput. While myriad network designs have been proposed, particularly in the data center and HPC networking communities, a consistent and accurate method of predicting a design’s throughput performance and comparing it to past proposals is conspicuously absent. In this work, we develop a framework to benchmark the throughput of network topologies and apply this method-ology to reveal insights about network structure. First, we show that despite being commonly used, cut-based metrics such as bisection bandwidth are the wrong metrics: they yield incorrect conclusions about the throughput performance of networks. We therefore measure flow-based throughput directly and show how to evaluate topologies with nearly-worst-case traffic matrices. Next, we use these metrics to an-alyze the throughput performance of a variety of networks. We evaluate networks used in data centers and high perfor-mance computing, and find that random graphs outperform the carefully-structured networks. We also evaluate several real-world complex networks and observe that throughput varies widely, and is not captured by other graph metrics such as betweenness or clustering coefficient. Finally, we study whether proposed models of complex networks are able to capture the throughput of real networks. We have made our evaluation framework freely available to facilitate future work on rigorously designing and evalu-ating networks, and reproducing results. 1