具有原路返回特征的改进OSRM胖树路由算法研究

胖树是最重要的互连网络拓扑结构之一。针对胖树拓扑结构，已经提出了多种路由算法，其中OSRM被证明是一种最优化的路由算法，但是所有算法都忽略了网络链路故障的易诊断性。为此，提出一种对OSRM改进的新型路由算法BT-OSRM。该算法定义了节点间的大小关系并通过比较节点大小而从OSRM路由路径与其反向路径中选择路由路径。此外，还针对常用的2级和3级胖树结构，分别详细给出了BT-OSRM2和BT-OSRM3路由算法。理论分析表明，BT OSRM路由算法不但继承了OSRM路由算法无死锁、负载均衡和性能最优等优点，而且保证了任意两节点间的路由路径具有原路返回特性，从而提高了网络故障链路的易诊断性。

Study on the improved OSRM routing algorithm with back-track feature for fat-tree networks

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.