||Hierarchical Dual-Net における素な経路および耐故障経路探索アルゴリズム
Disjoint-Paths and Fault-Tolerant Routing on Hierarchical Dual-Nets
荒井, 純ARAI, Jun
102015-03-24 , 法政大学大学院情報科学研究科
The hierarchical dual-net (HDN) was introduced as a topology of interconnection networks for ultra-scale parallel computers. The HDN is constructed by a symmetricproduct graph (called base network), such as threedimensional torus and hypercube. A k-level hierarchical dual-net, HDN(B; k; S), is given by applying k-time dualconstructions on the base network B. S defines a set of super-node that adjust the scale of the network. The node degree of HDN(B; k; S) is d0 + k where d0 is the nodedegree 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 four efficientalgorithms for finding disjoint-paths and a fault-free path on HDN. Both of the first and second algorithms find disjoint-paths on the HDN. The first algorithm has a limitation which the number of cluster in each class must equal to or greater than d0+k, while the second algorithm eliminates this limitation. The rest of two algorithms find a faultfree path on the HDN. The third algorithm can always finda fault-free path in O(2kF(B)) time with the number of faulty nodes in the HDN is less than d0 + k, where F(B) is the time complexity of fault-tolerant routing in B. On the other hand, the fourth algorithm can find a fault-free path on HDN with arbitrary number of faulty nodes. We performed two types of simulations for evaluating performance of our proposed algorithms.