Abstract:

Fat-tree is one of the most important topologies of interconnection networks. Several routing algorithms have been proposed for fat-tree topology. Among them, the OSRM routing algorithm is proved to be an optimal routing algorithm. However, all these algorithms ignore the ease of diagnosis of linkfault. Therefore, based on OSRM, a novel routing algorithm, named BT-OSRM, is proposed. In the BT-OSRM algorithm, the less-equal-great relationship between any pairs of processing nodes is defined, and hence the routing path is chosen from the OSRM routing path and its back-track routing path based on the defined relationship. Further, the BT-OSRM2 and BT-OSRM3 algorithms are described in detail for the commonly used two stages and three stages fattree topologies respectively. Theoretical analysis shows that the BTOSRM algorithm not only is as deadlockfree, loadbalanced and optimal as the OSRM algorithm, but also can guarantee the back-track feature for routing between any two endnodes, thus facilitating the diagnosis of linkfault in interconnection networks.

Key words: fat-tree;back-track;routing algorithm;deadlock freedom;load balance;oblivious performance ratio