紀要論文

Hierarchical Dual-Net における素な経路および耐故障経路探索アルゴリズム

Disjoint-Paths and Fault-Tolerant Routing on Hierarchical Dual-Nets

jpn

18810667

https://doi.org/10.15002/00011675

法政大学大学院情報科学研究科

10

1

6

2015-03-24

Version of Record

The hierarchical dual-net (HDN) was introduced as a topology of interconnection networks for ultra-scale parallel computers. The HDN is constructed by a symmetric product 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 dual constructions 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 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 four efficient algorithms 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 find a 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.

Article

AA12222297