An optimal message routing algorithm for double-loop networks

A weighted double-loop network can be modeled by a weighted directed graph G(n; h(1), h(2); w(1), w(2)) with vertex set Z(n) = {0, 1,...,n-1}, and edge set the union of E-1 = {(u, u + h(1)) \ u epsilon Z(n)} and E-2 = {(u, u + h(2)) \ u epsilon Z(n)}. Assume that the weight of each edge in E-1 is w(1), and the weight of each edge in E-2 is w(2). We present an optimal message routing algorithm for weighted double-loop networks. At each vertex, for any destination, the algorithm needs only constant time and spaces to determine the next vertex on the shortest path to which the message must be sent. We also present a message routing algorithm when a vertex fault or an edge fault is detected. (C) 1998 Elsevier Science B.V.