Networks bases on stack-tree topology and a 1394 bus

NASA Tech Briefs, Jun 2000 by Alkali, Leon, Tai, Ann

COTS circuits can be configured to achieve high degrees of fault tolerance.

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) prod ucts 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.

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 net work, 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.

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 net work topology is ringlike). The lower part of Figure 2 presents an example of calcu lated 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 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 JPL Mail Stop 122-116 4800 Oak Grove Drive Pasadena, CA 91109 (818) 354-2240

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

NASA's Jet Propulsion Laboratory, Pasadena, California