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

The hierarchical dual-net (HDN) is an interconnection network for building ultra-scale supercomputers. 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 HDN(B; k; S) is d(0) + k where d(0) 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 fault-free path on HDN. The first algorithm can always find a fault-free path in O (2(k) F (B)) time if the number of faulty nodes on HDN is less than d(0) + k, where F (B) is the time complexity of fault-tolerant routing in B. The second algorithm, more practical one, can find a fault-free path on HDN with arbitrary number of faulty nodes. The simulation result shows that the second algorithm can find fault-free paths at high probability.