Paper Info
Title
RRR: A Load Balanced Routing Scheme for Slimmed Fat-Trees
Abstract
Fat-trees are widely adopted in HPC systems. While existing static routing schemes such as destination-mod-k (D-mod-k) routing are load-balanced and effective for full bisection bandwidth fat-trees, they are not load-balanced for many slimmed fat-trees, which have recently been suggested to reduce costs in HPC systems. In this work, we propose a load balanced routing scheme, called Round-Robin Routing (RRR), for 2- and 3-level extended generalized fat-trees (XGFTs), which represent many fat-tree variations including slimmed fat-trees. RRR achieves near perfect load-balancing for any such XGFT in that links at the same level of a tree carry traffic from almost the same number of source-destination pairs. Simulation results show that on many slimmed fat-trees, RRR is significantly better than D-mod-K for majority of traffic patterns.
Year
DOI
Venue
2013
10.1109/IPDPSW.2013.223
IPDPS Workshops
Keywords
Field
DocType
source-destination pairs,scheduling,network routing,perfect load-balancing,static routing,traffic patterns,static routing scheme,trees (mathematics),load balanced routing scheme,xgft,traffic pattern,3-level extended generalized fat-trees,interconnect,resource allocation,fat-tree variation,2-extended generalized fat-trees,hpc system,source-destination pair,slimmed fat-trees,simulation result,fat-tree,round-robin routing,full bisection bandwidth fat-trees,rrr,fat tree,downlink,switches,bandwidth,uplink,routing
Equal-cost multi-path routing,Multipath routing,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Parallel computing,Computer network,Destination-Sequenced Distance Vector routing,Routing table,Routing Information Protocol
Conference
ISBN
Citations 
PageRank 
978-0-7695-4979-8
1
0.36
References 
Authors
10
4
Name
Order
Citations
PageRank
Xin Yuan1108992.27
Santosh K. Mahapatra2736.04
Michael Lang326619.91
Scott Pakin41098134.55