Static load-balanced routing for slimmed fat-trees

Slimmed fat-trees have recently been proposed and deployed to reduce costs in High Performance Computing (HPC) clusters. 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 incur significant load imbalance in many slimmed fat-trees. In this work, we propose a static load balanced routing scheme, called Round-Robin Routing (RRR$RRR$), for 2$2$- and 3$3$-level extended generalized fat-trees (XGFTs), which represent many fat-tree variations including slimmed fat-trees. RRR$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. Our evaluation results indicate that on many slimmed fat-trees, RRR$RRR$ is significantly better than D-mod-k for dense traffic patterns due to its better load-balancing property, but performs worse for sparse patterns. We develop a combined routing scheme that enjoys the strengths of both RRR$RRR$ and D-mod-k by using RRR$RRR$ in conjunction with D-mod-k. The combined routing is a robust load-balanced routing scheme for slimmed fat-trees: it performs similar to D-mod-k for sparse traffic patterns and to RRR$RRR$ for dense patterns.