Reliability Modeling and Assessment of the Star-graph networks

Document Type


Publication Date


Publication Title

IEEE Transactions on Reliability



First page number:


Last page number:



The reliability of the Star Graph architecture is discussed. The robustness of the Star Graph network under node failures, link failures, and combined node and link failures is shown. The degradation of the Star Graph into Substar Graphs is used as the measure of system effectiveness in the face of failures. Models are provided for each of the failure and re-mapping modes evaluated herein, and the resilience of the Star Graph to failures is emphasized. This paper defines failure of a Star Graph as being when no fault-free (n - 1)-substars remain operational and the intermediate states are defined by the number of (n - 1)-substars that remain operational. A powerful tool (re-mapping) is introduced in which the number of operational (n 1)-substars can be maintained for longer periods, thus improving the overall MTTF (mean time to failure). For comparison the results of a similar reliability analysis of the hypercube is shown. The comparisons are considered conservative due to the failure model used herein for the star graph. One might apply re-mapping to hypercubes; while it would improve the overall MTTF of hypercubes, the hypercubes would still have an appreciably poorer performance than star graphs.


Computer algorithms; Computer networks; Graph theory; Hypercube networks (Computer networks); Markov processes; Routing protocols (Computer network protocols)


Controls and Control Theory | Electrical and Computer Engineering | Electronic Devices and Semiconductor Manufacturing | Systems and Communications




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.

UNLV article access

Search your library