A ROUTING AND BROADCASTING SCHEME ON FAULTY STAR GRAPHS

In this correspondence, we present a routing algorithm that uses the d epth first search approach combined with a backtracking technique to r oute messages on the star graph in the presence of faulty links. The a lgorithm is distributed and requires no global knowledge of faults. Th e only knowledge required at a node is the state of its incident links . The routed message carries information about the followed path and t he visited nodes. The algorithm routes messages along the optimal, i.e ., the shortest path if no faults are encountered or if the faults am such that an optimal path still exists. In the absence of an optimal p ath, the algorithm always finds a path between two nodes within a boun ded number of hops if the two nodes are connected. Otherwise, it retur ns the message to the originating node. We provide a performance analy sis for the case where an optimal path does not exist. We prove that f or a maximum of n - 2 faults on a graph with N=n! nodes, at most 2i 2 steps am added to the path, where i is O(square-root n). Finally, we use the routing algorithm to present an efficient broadcast algorithm on the star graph in the presence of faults.