A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm doe s not know the faulty element in advance. We present an optimal fault-toler ant message routing algorithm for double-loop networks. We show that sendin g at most two messages with different routing strategies can ensure that on e of the messages will be sent through a shortest path that avoids the faul ty element. At each vertex, for any destination, the algorithm needs only c onstant time and space to determine the next vertex to which the message is to be sent. (C) 1999 Elsevier Science B.V. All rights reserved.