Optimizing k-path selection for randomized interconnection networks

Several new interconnect designs have been proposed in the recent past for high performance computing clusters and data centers that use random connections of endpoints. Despite their superior flexibility, scalability and cost-effectiveness over conventional fat-tree based designs, practical deployment of random topologies can be prohibitive as they are prone to throughput bottlenecks if used with conventional shortest-path routing schemes. Even with multi-path routing, bottleneck issues remain on random topologies due to practical limits of routing table size. In this work, we propose a novel heuristic-driven scheme to select k best paths from all available short paths with an objective to minimize routing path bottlenecks. Our proposed scheme relies on the topological information to choose paths for each possible communication node pairs and can be paired with congestion-aware adaptive routing schemes. It, however, does not require awareness of the global traffic pattern in real time and as such, results in a stable routing control plane even under dynamic traffic conditions. We perform comparative performance analysis of our path selection with k-shortest path selection scheme on random regular graph networks and under various traffic conditions. Our experiments show that multi-path routing schemes paired with our path selection achieve up to 42 percent faster communication than the same schemes paired with k-shortest path selection, when the value of k is limited due to capacity constraints on routing table memory.