A method of designing fault-tolerant networks of computers and other electronic circuits has been conceived with a view toward minimizing costs by utilizing commercial off-the-shelf (COTS) products and standards for all system and component interfaces. The method involves, more specifically, utilization of selected features of the 1394 bus architecture and of the stack tree-topology (see Figure 1), which is a special case of the general tree topology and which complies with the 1394 standard. Of particular significance in the method is a specific type of stack tree denoted as Complete Stack Tree (CST) of n stem nodes.

Figure 1. Stack Trees are constructed from three-port nodes. A leaf node is one that is connected to one other node denoted a stem node. Each stem node is connected to at most three other nodes, of which no more than two are stem nodes. A complete stack tree (CST) is one in which each stem node is connected to at least one leaf node.

Taken by itself, the stack-tree topology is not fault tolerant: failure of any link partitions a stack tree into two segments, while failure of a stem node can partition the tree into two or three segments, depending on the specific design. Moreover, the 1394 standard does not permit loops, which would be formed if, for example, one were to connect the leaf nodes of a CST with spare links. However, the 1394 standard provides a "port disable" feature, which can be utilized to make any spare links "invisible" to the rest of the network. In the initial configuration of the network, the ports connected to the spare links are disabled, thereby disabling the spare links and preventing the formation of loops. In the event of failure of one or more nodes or a link of the initial network configuration, messages can be rerouted around the failed parts by enabling the appropriate ports to activate the appropriate spare links.

Figure 2. The CSTR Topology Is More Fault-Tolerant than is the corresponding CSTS topology. These curves were calculated for the example of a CST of n = 16 and an assumed fault-detection-and-reconfiguration coverage of 0.9999.

The upper part of Figure 2 schematically depicts a complete stack tree without spare links [denoted a "simplex complete stack tree" (CSTS)] and a complete stack tree with a spare link constructed to obtain a configuration called "CSTR" (where "R" refers to the fact that the resulting network topology is ringlike). The lower part of Figure 2 presents an example of calculated bus network reliabilities as functions of the node failure rate to demonstrate that a significant increase in reliability is expected to be achievable by the present method.

This work was done by Leon Alkali, Savio Chau, and Ann Tai of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp  under the Electronic Components and Systems category.

In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to

Technology Reporting Office
Mail Stop 122-116
4800 Oak Grove Drive
Pasadena, CA 91109
(818) 354-2240

Refer to NPO-20817, volume and number of this NASA Tech Briefs issue, and the page number.

This Brief includes a Technical Support Package (TSP).
Networks Based on Stack-Tree Topology and a 1394 Bus

(reference NPO-20817) is currently available for download from the TSP library.

Don't have an account? Sign up here.

NASA Tech Briefs Magazine

This article first appeared in the June, 2000 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.