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

Jun Arai, Yamin Li


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 d0+k where d0 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(2kF(B)) time if the number of faulty nodes on HDN is less than d0+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.


Interconnection network; fault-tolerant routing

Full Text:



  • There are currently no refbacks.