loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Sixth Pacific Rim International Symposium on Dependable Computing (PRDC'99)
Fault-Tolerant Routing Algorithms Based on Optimal Path Matrices
Hong Kong, China
December 16-December 17
ISBN: 0-7695-0371-3
Feng Gao, Chinese Academy of Sciences
Zhongcheng Li, Chinese Academy of Sciences
This paper presents a new concept Optimal Path Matrices for fault-tolerant routing on hypercube multicomputers. Optimal Path Matrices (OPMs) stored on each node of a hypercube keep faulty information and indicate whether there is an optimal path from the node to a destination. Two fault-tolerant routing algorithms based on Optimal Path Matrices are proposed to maintain the matrices and route messages from sources to destinations. One is a routing algorithm based on OPMs, which are filled with pre-collected information through information exchange between neighbors. It can easily establish a path for a message. And the length of the path is no greater than the hamming distance between the source and the destination of the message plus two. The other is a modified depth-first search algorithm, which adopts a dynamically learning strategy to fill OPMs during normal message transmission and can find almost all optimal paths. The memory overhead is n2 words on each node of an n-dimensional hypercube.
Index Terms:
optimal path matrices, fault-tolerant routing, hypercube multicomputers, dynamical learning, information pre-collecting
Citation:
Feng Gao, Zhongcheng Li, "Fault-Tolerant Routing Algorithms Based on Optimal Path Matrices," prdc, pp.227, Sixth Pacific Rim International Symposium on Dependable Computing (PRDC'99), 1999
Usage of this product signifies your acceptance of the Terms of Use.