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∈_n} and E_2 ={(u,u+h_2)|u∈Zn}. Assume That the weight of each edge in E_1 is w_1, and the weight of each edge in E_2 is w2. 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.