
Hierarchical DualNet における素な経路および耐故障経路探索アルゴリズムHierarchical DualNet における素な経路および耐故障経路探索アルゴリズムAA12222297 DisjointPaths and FaultTolerant Routing on Hierarchical DualNets 
"/荒井, 純/"荒井, 純 ,
"/ARAI, Jun/"ARAI, Jun
1020150324 , 法政大学大学院情報科学研究科
ISSN:18810667
NCID:AA12222297
Description
The hierarchical dualnet (HDN) was introduced as a topology of interconnection networks for ultrascale parallel computers. The HDN is constructed by a symmetricproduct graph (called base network), such as threedimensional torus and hypercube. A klevel hierarchical dualnet, HDN(B; k; S), is given by applying ktime dualconstructions on the base network B. S defines a set of supernode 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 nodedegree and short diameter. In this paper, we propose four efficientalgorithms for finding disjointpaths and a faultfree path on HDN. Both of the first and second algorithms find disjointpaths 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 faultfree 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 faulttolerant routing in B. On the other hand, the fourth algorithm can find a faultfree path on HDN with arbitrary number of faulty nodes. We performed two types of simulations for evaluating performance of our proposed algorithms.
FullText
http://repo.lib.hosei.ac.jp/bitstream/10114/10990/1/13t0001.pdf