Name
Abstract | ||
|---|---|---|
Random regular graph (RRG) has recently been proposed as an interconnect topology for future large scale data centers and HPC clusters. While various studies have been performed, this topology is still not well understood. RRG is a special case of directed regular graph (DRG) where each link is unidirectional and all nodes have the same number of incoming and outgoing links. In this work, we establish bounds for DRG on diameter, average k-shortest path length, and a load balancing property with k-shortest path routing, and use these bounds to evaluate RRG. The results indicate that RRG with k-shortest path routing is not ideal in terms of diameter and load balancing. We further consider the Generalized De Bruijn Graph (GDBG), a deterministic DRG, and prove that for most network configurations, GDBG is near optimal in terms of diameter, average k-shortest path length, and load balancing with a k-shortest path routing scheme. Finally, we explore the strengths and weaknesses of RRG for different traffic conditions by comparing RRG with GDBG. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/IPDPS.2016.44 | 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Keywords | DocType | Volume |
network,topology,random regular graph,generalized De Bruijn graph,k-shortest path routing | Journal | 29 |
Issue | ISSN | ISBN |
1 | 1530-2075 | 978-1-5090-2141-3 |
Citations | PageRank | References |
2 | 0.40 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peyman Faizian | 1 | 4 | 0.79 |
| Md Atiqul Mollah | 2 | 5 | 2.17 |
| Xin Yuan | 3 | 1089 | 92.27 |
| Scott Pakin | 4 | 1098 | 134.55 |
| Michael Lang 0003 | 5 | 34 | 5.13 |