Static load-balanced routing for slimmed fat-trees

• A new load balanced routing scheme, RRRRRR, for slimmed fat-trees.
• A combined routing scheme that integrates RRRRRR, D-mod-k, and S-mod-k.
• Performance study.

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 (RRRRRR), for 22- and 33-level extended generalized fat-trees (XGFTs), which represent many fat-tree variations including slimmed fat-trees. RRRRRR 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, RRRRRR 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 RRRRRR and D-mod-k by using RRRRRR 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 RRRRRR for dense patterns.