A Routing and Broadcasting Scheme on Faulty Star Graphs

Authors

Nader Bagherzadeh, University of California, IrvineFollow
Nabil Nassif, University of Nevada, Las VegasFollow
Shahram Latifi, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

11-1993

Publication Title

IEEE Transactions on Computers (TC)

Volume

42

First page number:

1398

Last page number:

1402

Abstract

The authors present a routing algorithm that uses the depth first search approach combined with a backtracking technique to route messages on the star graph in the presence of faulty links. The algorithm is distributed and requires no global knowledge of faults. The only knowledge required at a node is the state of its incident links. The routed message carries information about the followed path and the visited nodes. The algorithm routes messages along the optimal, i.e., the shortest path if no faults are encountered or if the faults are such that an optimal path still exists. In the absence of an optimal path, the algorithm always finds a path between two nodes within a bounded number of hops if the two nodes are connected. Otherwise, it returns the message to the originating node. The authors provide a performance analysis for the case where an optimal path does not exist. They prove that for a maximum of n-2 faults on a graph with N=n! nodes, at most 2i+2 steps are added to the path, where i is O(√n). Finally, they use the routing algorithm to present an efficient broadcast algorithm on the star graph in the presence of faults.

Keywords

Broadcasting; Cayley graphs; Computer algorithms; Hypercube networks (Computer networks); Integrated circuits--Fault tolerance; Parallel computers; Routing (Computer network management)

Disciplines

Computer and Systems Architecture | Digital Circuits | Digital Communications and Networking | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

Repository Citation

Bagherzadeh, N., Nassif, N., Latifi, S. (1993). A Routing and Broadcasting Scheme on Faulty Star Graphs. IEEE Transactions on Computers (TC), 42 1398-1402.