Graph analysis shows that these topologies, when compared to non-random topologies of the same degree, lead to drastically reduced diameter and average shortest path length. The best results are obtained when adding random links to a ring topology, meaning that good random shortcut topologies can easily be generated for arbitrary numbers of switches. Flit-level discrete event simulation shows that random shortcut topologies achieve throughput comparable to and latency lower than that of existing non-random topologies such as hypercubes and tori. Random topologies give rise to several practical challenges, including routing scalability and larger physical cable lengths, which will be discussed.
“Random Network Topologies”, by Henri Casanova, Associate Professor of Information and Computer Sciences, University of Hawaii. Thursday, August 30, 2012. 4:30pm. POST 127