Polarized routing: an efficient and versatile algorithm for large direct networks

Supercomputer and datacenter networks can comprise hundreds of thousands of severs. Focusing on direct networks, different topologies have been proposed to attain such a high scalability, from Flattened Butterfly and Dragonfly to the most disruptive approach represented by Jellyfish, which is based on a random interconnection pattern. The routing problem on such networks remains a challenge that can be tackled as a topology aware solution, or with an agnostic approach. The case of random networks is a very special one because of the lack of an acceptable routing algorithm for them since no a priori topological clues can be exploited. In this paper, we introduce the Polarized Routing Algorithm, an adaptive non-minimal hop-by-hop mechanism for direct networks that can be used in a number of topologies, including Jellyfish. Polarized routing was conceived following two design criteria: a source-destination symmetry in the routes to enable load-balancing and to avoid undoing previously taken hops. A thorough experimentation shows Polarized routing constitutes an efficient and versatile solution, attaining the highest performance both in benign scenarios under uniform traffic patterns and in adverse ones on the tested networks. Interestingly, this algorithm provides important performance gains of more than 30% in the Jellyfish topology, for different traffic patterns, when compared to the state of the art solutions.