Fault-Tolerant Routing Based on Safety Path Vectors in Hypercube System.pdfVIP

Vol.15, No.5 ?2004 Journal of Software 软 件 学 报 1000-9825/2004/15(05)0783 超立方体系统中基于安全通路向量的容错路由 ? 王 雷, 林亚平+, 陈治平, 文 学 (湖南大学 计算机与通信学院,湖南 长沙 410082) Fault-Tolerant Routing Based on Safety Path Vectors in Hypercube System WANG Lei, LIN Ya-Ping+, CHEN Zhi-Ping, WEN Xue (College of Computer and Communication, Hu’nan University, Changsha 410082, China) + Corresponding author: Phn: +86-731-8821932, E-mail: yplin@, Received 2002-11-17; Accepted 2003-07-07 Wang L, Lin YP, Chen ZP, Wen X. Fault-Tolerant routing based on safety path vectors in hypercube system. Journal of Software, 2004,15(5):783~790. /1000-9825/15/783.htm Abstract: Hypercube multicomputers system has good performances in parallel and distributed computation. With the increasing size of a multicomputers network system, the fault possibility of computers and their links increases. As a result, it becomes very important to seek for better fault-tolerant routing strategies for realizing more effective fault-tolerant routing when lots of faults occur in the multicomputers system. Many significant researches have been done on the fault-tolerant routing design for the hypercube multicomputers system. An innovative fault-tolerant routing algorithm is proposed, in which each node uses a safety path vector (SPV) to record the optimal paths to the other nodes. The safety path vector is an approximate measure of the number and distribution of the faults in the neighborhood and can be setup or updated through the n?1 rounds of information exchanges among neighboring nodes by consuming only n bits storage space. Compared with previous fault-tolerant routing algorithms such as the safety vectors (SVs), extended safety vectors (ESVs), optimal path matrices (OPMs) and extended optimal path matrices (EOPMs), SPVs have stronger ability in tracing optimal paths with equal or less storage cost. Analysis and simulation are given to show the merit of the SPVs. Key words: fault-tolerant routing; sa