書誌事項
- タイトル別名
-
- Disjoint-Paths and Fault-Tolerant Routing on Hierarchical Dual-Nets
この論文をさがす
抄録
type:Article
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.
収録刊行物
-
- 法政大学大学院紀要. 情報科学研究科編
-
法政大学大学院紀要. 情報科学研究科編 10 1-6, 2015-03-24
法政大学大学院情報科学研究科
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390572174784194176
-
- NII論文ID
- 120005622158
-
- NII書誌ID
- AA12222297
-
- ISSN
- 18810667
-
- Web Site
- http://hdl.handle.net/10114/10990
-
- 本文言語コード
- ja
-
- データソース種別
-
- JaLC
- IRDB
- CiNii Articles