A fault-tolerant routing algorithm in HyperX topology based on unsafety vectors

摘要

HyperX is a promising high-radix topology proposed by a group of researchers in HP laboratories. The topology offers numerous advantages of high-radix routers, among which are very low diameter and low average distance. Increasing degree of routers and growth of network size intensifies failure probability of routers. Thereby, the essence of a routing algorithm with fault-tolerance capability is inevitable. In this paper, for the first time, a fault-tolerant routing algorithm for HyperX topology is suggested. The proposed algorithm is based on the concept of unsafety vectors by which the unsafety degree of each node is calculated depending on its faulty neighbors. For each step of the routing, the node with the lowest number of faulty neighbors is selected. The neighbors are located along the path of message from source to destination. Furthermore, we analytically have induced some properties of the proposed algorithm. Yet, an applied example for step by step illustration of the functionality of the algorithm is given showing its efficient performance even in the presence of catastrophic failures. The performance of proposed routing algorithm is evaluated by the simulation results of various workloads signifying the accuracy and integrity of the suggested algorithm.