Communications networks (see figure) are used to transmit vital corporate and public-safety data, so network reliability is critical in today's society. As networks become ever more complex and interconnected, however, it becomes difficult to predict how the behavior of individual components can affect the overall network. Sandia's Center for System Reliability has developed new methods for reliability modeling that can be applied to both current and next-generation networks. These methods can determine which parts of the network are likely to cause the most network downtime and can support recommendations about the most cost-effective ways to improve reliability. These models can be applied during both network design and operations to
provide reliable initial network designs,
prioritize network monitoring and maintenance activities, and
optimize network improvements using quantitative cost-effectiveness measures.
U.S. telephone signaling network
Software has been developed to demonstrate the methods for a wide variety of prototypical hierarchical and "flat" network architectures.
This project determined that networks can be broadly classified as either hierarchical or non-hierarchical on the basis of their physical and logical architecture.
We found that the connectivity of hierarchical networks can be adequately modeled using fault-tree analysis, and we developed a "plug-and-play" fault tree analysis method to assist persons who are not risk analysts to analyze such networks. One can easily extend these connectivity models to consider the availability of network services and classes of network traffic.
Non-hierarchical networks cannot be adequately modeled using fault trees because of the combinatorial expansion that can occur as one considers all paths between nodes when modeling full connectivity (the "everybody can talk to everybody" problem). For this reason we developed a new and efficient method that searches for cut sets from such networks without the need to construct a fault tree model. The method is orders of magnitude faster than traditional search methods because it first searches for cut sets based only on link ("edge") failures and then infers the existence of (but does not construct) the combinations of link and node failures that can cause a lack of network connectivity. A link cut set that contains n links can generate up to 3-to-the-nth-power cut sets based on both link and node failures. Because our methods does not have to generate or perform Boolean reduction on these cut sets, it achieves dramatic computational savings over previous methods. The method has been the subject of a patent disclosure.
In practice, many large networks contain both hierarchical and non-hierarchical elements. These hybrid networks can be modeled by combining the results of the two methods we developed using simple mathematical rules. We applied these methods to a variety of typical network architecture to demonstrate the method.
Sandia's Capabilities
Network connectivity cut sets provide a basis for
risk-based monitoring of network health
opportunities for optimal scheduling of testing and maintenance activities
computation of the importance of particular components and suggestions for the most cost-effective improvements in them
modeling of particular classes of service on a single network based on a single global model
Future Work
These methods could also be used to model network-like architectures in non-communications industries:
highway traffic management (hybrid hierarchical and non-hierarchical)
electrical distribution systems
local distribution networks (hierarchical)
national electrical grid (non-hierarchical)
water and sewage systems (mainly hierarchical)
For further information, contact:
Allen L. Camp
Sandia National Laboratories, MS-0747
Albuquerque, NM 87185-0747
Phone: (505) 844-5960
e-mail: alcamp@sandia.gov
Submitted October 1996 Layout design by Wanda Mar.
Submitted October 1996