An optimal fault-tolerant routing algorithm for double-loop networks

A weighted double-loop network can be modeled by a directed graph G(n: h(1), h(2); w(1), w(2)) with vertex set Z(n) = {0, 1,..., n - 1) and edge set E = E-1 boolean OR E-2 where E-1 = {(u, u + h(1))\ u is an element of Z(n)}, E-2 = {(u, u + h(2)) \| u is an element of 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) In this paper, we present an optimal routing algorithm on double-loop networks under the case where there is at most one faulty element. Our algorithm is based on the fact that the shortest path from a vertex to any other vertex in a double-loop network is in the L-shape region.