A HoL-blocking aware mechanism for selecting the upward path in fat-tree topologies

The final publication is available at Springer via http://link.springer.com/article/10.1007%2Fs11227-014-1303-xLarge cluster-based machines require efficient high-performance interconnection networks. Routing is a key design issue of interconnection networks. Adaptive routing usually outperforms deterministic routing at the expense of introducing out-of-order packet delivery. Many of the commodity interconnects for clusters are based on fat-trees. The adaptive routing algorithm commonly used in fat-trees is composed of a fully adaptive upward subpath, followed by a deterministic downward subpath. As the latter is determined by the former, choosing the most adequate upward path for each packet is critical in fat-trees to achieve a good performance. In this paper, we present a mechanism for selecting the upward path in fat-trees, which enables optimum use of the available network resources to achieve a high network throughput. The proposed path selection is destination based, which allows reducing the head-of-line blocking effect. Indeed, the proposed mechanism can be used either as a selection function (the provided path is used as the preferred one), or as a deterministic routing algorithm (the path is the only possible one). The results show that the resulting selection function outperforms any other known one. Moreover, the proposed deterministic routing algorithm can achieve a similar, or even higher, level of performance than adaptive routing, while providing in-order packet delivery and a simpler switch implementation.This work was supported by the Spanish Ministerio de Ciencia e Innovacion (MICINN) and jointly financed with Plan E funds, under Grant TIN2009-14475-C04 as well as by Consolider-Ingenio 2010 under Grant CSD2006-00046.Gómez Requena, C.; Gilabert Villamon, F.; Gómez Requena, ME.; López Rodríguez, PJ.; Duato Marín, JF. (2015). A HoL-blocking aware mechanism for selecting the upward path in fat-tree topologies. Journal of Supercomputing. 71(7):2339-2364. doi:10.1007/s11227-014-1303-xS2339236471