An NPV-based optimal fault-tolerant routing algorithm for generalized hypercube

被引：1
作者：
Tian, Shao-Huai [1 ]
Lu, Ying-Ping [2 ]
Zhang, Da-Fang [1 ]
机构：
[1] Software School, Hunan University
[2] Department of Computer Science and Engineering, University of Minnesota, Minneapolis
来源：
| 1818年 / Chinese Academy of Sciences, P.O. Box 8718, Beijing, 100080, China卷 / 18期
关键词：
Fault-tolerant routing; Generalized hypercube; Node path vector; Relay node technique;
D O I：
10.1360/jos181818
中图分类号：
学科分类号：
摘要：
Optimal fault-tolerant routing is imperative for large hypercube systems in the existence of large number of faulty links or nodes. This paper first defines hypercube network with a large number of faulty nodes and/or links to be generalized hypercube and illustrates that many non-hypercube systems can be transformed to Generalized Hypercube systems. It then proposes node path vector (NPV) to capture the complete optimal and sub-optimal routing information for a generalized hypercube system. To reduce the computation iterations in solving NPV, it also introduces the concept of relay node technique. Based on NPV and relay node technique, this paper further proposes optimal fault-tolerant routing scheme (OFTRS) to derive shortest path for any communication pair in a generalized hypercube system. With an example of large number of faulty nodes or faulty links, it is illustrated that the previous algorithm could omit up to 60% routing paths, while this approach achieves all optimal and sub-optimal routing paths. Compared to previous work, OFTRS has a significant improvement in obtaining routing information for optimal and sub-optimal, i.e. no matter how many faulty nodes or links exist, it is guaranteed to route through the optimal or sub-optimal path as long as a path between the source-destination pair exists. In addition, the proposed scheme is distributed and relying only on non-faulty neighboring nodes since it only requires the information of non-faulty neighbor nodes in computing NPV, thus it has high applicability, especially when some non-hypercube systems can be transformed into Generalized Hypercube systems.
引用
收藏
页码：1818 / 1830
页数：12
相关论文
共 19 条
  • [1] Lee T.C., Hayes J.P., A fault-tolerant communication scheme for hypercube computers, IEEE Trans. on Computers, 41, 10, pp. 1242-1256, (1992)
  • [2] Chiu G.M., Wu S.P., A fault-tolerant routing strategy in hypercube multicomputers, IEEE Trans. on Computers, 45, 2, pp. 143-155, (1996)
  • [3] Chen M.S., Shin K.G., Depth-First approach for fault-tolerant routing in hypercube multicomputers, IEEE Trans. on Parallel and Distributed Systems, 1, 2, pp. 152-159, (1990)
  • [4] Jong K., Shin K.G., Deadlock-Free fault-tolerant routing in injured hypercubes, IEEE Trans. on Computers, 42, 9, pp. 1078-1088, (1993)
  • [5] Chen M.S., Shin K.G., Adaptive fault-tolerant routing in hypercubes multicomputers, IEEE Trans. on Computers, 39, 12, pp. 1406-1416, (1990)
  • [6] Wu J., Reliable unicasting in faulty hypercubes using safety levels, IEEE on Computers, 46, 2, pp. 241-247, (1997)
  • [7] Wu J., Adaptive fault-tolerant routing in cube-based multicomputers using safety vectors, IEEE Trans. on Parallel and Distributed Systems, 9, 4, pp. 321-334, (1998)
  • [8] Gao F., Li Z.C., Min Y.H., Wu J., A fault-tolerant routing strategy based on extended safety vectors in hypercube multicomputers, Chinese Journal of Computers, 23, 3, pp. 248-254, (2000)
  • [9] Gao F., Li Z.C., Fault-Tolerant routing in hypercube multicomputers using optimal path matrices, Chinese Journal of Computers, 23, 3, pp. 242-247, (2000)
  • [10] Al-Sadi J., Day K., Ould-Khaoua M., A new fault-tolerant routing for k-ary n-cubes, Microprocessors and Microsystems, 25, 5, pp. 239-246, (2001)
12