Fault-Tolerant Routing Algorithms for Hierarchical Dual-Nets with Limited and Arbitrary Number of Faulty Nodes

Abstract

The hierarchical dual-net (HDN) is an interconnection network for building ultra-scale parallel systems. The HDN is constructed based on a symmetric product graph (called base network), such as three-dimensional torus and n-dimensional hypercubes. A k-level hierarchical dual-net, HDN(B,k,S), is obtained by applying k-time dual constructions on the base network B. S defines a super-node set that adjusts the scale of the system. The node degree of an HDN(B,k,S) is d₀+k where d₀ is the node degree of B. The HDN is node and edge symmetric and can contain huge number of nodes with small node degree and short diameter. In this paper, we propose two efficient algorithms for finding a fault-free path on HDN. The first algorithm can always find a fault-free path in O(2^kF(B)) time if the number of faulty nodes on HDN is less than d₀+k, where F(B) is the time complexity of fault-tolerant routing in the base network. The second algorithm, more practical one, can find a fault-free path on HDN with arbitrary number of faulty nodes. The simulation results show that the second algorithm can find a fault-free path at high probability.