Random Regular Graph and Generalized De Bruijn Graph with k -Shortest Path Routing

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2018-01, Vol.29 (1), p.144-155
Main Authors: Faizian, Peyman, Mollah, Md Atiqul, Yuan, Xin, Alzaid, Zaid, Pakin, Scott, Lang, Michael
Format: Article
Language:English
Subjects:
<named-content xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" content-type="math" xlink:type="simple"> <inline-formula> <tex-math notation="LaTeX"> k </tex-math> <inline-graphic xlink:href="faizian-ieq7-2741492.gif" xlink:type="simple"/> </inline-formula> </named-content>-shortest path routing
Bandwidth
Computer simulation
Data centers
Driving conditions
generalized De Bruijn graph
Graphs
Load balancing
Load management
Load modeling
Network
Network topology
Production planning
random regular graph
Route planning
Routing
Servers
Shortest-path problems
Switches
Topology
Traffic
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2017.2741492