Dynamic and Distributed Multipath Routing Policy for High-Speed Cluster Networks

The increasing demand of parallel applications in cluster computing requires the use of interconnection networks to provide low and bounded communication delays. However, message congestion appears when communication load between nodes is not fairly distributed over the network. Congestion spreading increases latency and reduces network throughput causing important performance degradation. In this paper we present dynamic routing balancing with multipath distribution (DRB-MD), a new method developed to control network congestion based on a uniform balancing of communication load. DRB-MD distributes the traffic load according to a gradual and load-controlled path expansion. It monitors message latency in network switches, makes decisions about how many alternative paths should be used, and finally decides which path (or paths) to use between each source-destination pair. Experiments with permutation patterns and hotspot traffic were conducted to evaluate DRB-MD performance under conditions commonly created by parallel scientific applications.