Random Regular Graph and Generalized De Bruijn Graph with $k$ -Shortest Path Routing
| Autor: | Michael Lang, Xin Yuan, Zaid Alzaid, Peyman Faizian, Scott Pakin, Atiqul Mollah |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computer science
Distributed computing 02 engineering and technology Network topology 01 natural sciences De Bruijn graph Simplex graph symbols.namesake 0103 physical sciences Random regular graph 0202 electrical engineering electronic engineering information engineering 010302 applied physics Discrete mathematics Voltage graph Graph theory Load balancing (computing) Average path length 020202 computer hardware & architecture Computational Theory and Mathematics Hardware and Architecture Signal Processing Shortest path problem Path (graph theory) symbols Regular graph K shortest path routing MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems. 29:144-155 |
| ISSN: | 2161-9883 1045-9219 |
| DOI: | 10.1109/tpds.2017.2741492 |
| Popis: | The Random regular graph (RRG) has recently been proposed as an interconnect topology for future large scale data centers and HPC clusters. An 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 DRGs on diameter, average $k$ -shortest path length, and a load balancing property with $k$ -shortest path routing, and use these bounds to evaluate RRGs. The results indicate that an 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, a 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 use modeling and simulation to exploit the strengths and weaknesses of RRGs for different traffic conditions by comparing RRGs with GDBGs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|