Effective methodology for deadlock-free minimal routing

The InfiniBand Architecture (IBA) defines a switch-based network with point-to-point links whose topology is arbitrarily established by the customer. Often, the inter-connection pattern is irregular, which complicates routing and deadlock avoidance. Current routing algorithms for NOWs, either achieve a low network performance, such as the up*/down * routing scheme, or cannot be implemented on IBA networks. IBA switches provide support for sev-eral virtual lanes, but they are primarily intended for QoS. Hence, its use for other purposes, like deadlock avoidance or performance improvement, should be limited. In this paper, we propose a simple and effective method-ology for designing deadlock-free routing strategies that are able to route packets through minimal paths in InfiniBand networks. This methodology can meet the trade-off be-tween network performance and the number of resources dedicated to deadlock avoidance. Evaluation results show that the resulting routing strategies significantly outperform up*/down * routing. In particular, throughput improvement ranges, on average, from 1:33 for small networks to 4:05 for large networks. Also, it is shown that just two virtual lanes and three service levels are enough to achieve more than 80 % of the throughput improvement achieved by the best proposed routing strategy (the one that always provides minimal paths without limiting the number of resources).