On the Routing of the OTIS-Cube Network in Presence of Faults

Ahmad Awwad¹ and Jehad Al-Sadi²

¹Faculty of Computing and Information Technology, Arab Open University, Kuwait

²Faculty of Computing and Information Technology, Arab Open University, Jordan

Abstract: This paper proposes a new fault-tolerant routing algorithm for the well-known class of networks, OTIS-cube. In this new proposed algorithm, each node A starts by computing the first level unsafety set, S1A, composed of the set of unreachable direct neighbors. It then performs m-1 exchanges with its neighbors to determine the k-level unsafety sets SkA, for all 1 £ k £ m, where m is an adjustable parameter between 1 and 2n + 1. The k-level unsafety set at node A represents the set of all faulty nodes at Hamming distance k from A, which either faulty or unreachable from A due to faulty nodes or links. Equipped with these unsafety sets, we show how each node calculates numeric unsafety vectors and uses them to achieve efficient fault-tolerant routing.

Keywords: Interconnection networks, OTIS-cube, fault-tolerant routing algorithm, safety vectors.

Received July 30, 2003; accepted March 20, 2004