Factoring and reductions for networks with imperfect vertices

Factoring and reductions are effective methods for computing the K-terminal reliability of undirected networks, but they have been applied mostly to networks with perfect vertices. However, in real problems, vertices may fail as well as edges. Imperfect vertices can be factored like edges, but the complexity then increases exponentially with their number. A technique has been developed to account for the failure of vertices with small additional cost, using a modified method of factoring and reductions. This technique is very easy to integrate into a factoring algorithm. It consists of factoring not on a single element (e.g., a single edge) but on a set of elements (e.g., an edge and its endpoints). The problem is that random variables associated with the elements of the network are no longer independent. This can be handled by choosing factoring edges that have at least one perfect endpoint. This technique leaves the factoring algorithm practically unchanged. The only difference is that some supplementary probability values are kept for the imperfect vertices of the original and the induced graphs. For algorithms using simple reductions, it has negligible computational cost     

Partial factoring: an efficient algorithm for approximatingtwo-terminal reliability on complete graphs

An efficient network reliability approximation algorithm for two-terminal undirected complete graphs is presented. The method recursively applies a factoring theorem of network reliability in conjunction with series-parallel reliability-preserving reductions. After each pivot, one of the resulting subproblems is further factored, while the other is approximated. The final approximate solution is given in terms of an upper and a lower bound. In the worse case, the algorithm requires O(|V|² log |V|) time and O(|V²|) space. For 128-node complete graphs, the method requires less than 16 s on an IBM AT personal computer. The algorithm's mean error bound is both theoretically and empirically analyzed. The mean difference between the upper and lower bounds is guaranteed to be less than 10^-14 for component reliabilities uniformly distributed between 0.99 and 1.00. Empirically, this difference is always less than 10^-17     

Finding parity in a simple broadcast network

A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(ln N)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication     

Factoring Algorithms for Computing K-Terminal Network Reliability

Let GK denote a graph G whose edges can fail and with a set K ? V specified. Edge failures are independent and have known probabilities. The K-terminal reliability of GK, R(GK), is the probability that all vertices in K are connected by working edges. A factoring algorithm for computing network reliability recursively applies the formula R(GK) = piR(GK * ei) + qiR(GK - ei) where GK * ei is GK, with edge ei contracted, GK - ei is GK with ei deleted and pi ? 1 - qi is the reliability of edge ei. Various reliability-preserving reductions can be performed after each factoring operation in order to reduce computation. A unified framework is provided for complexity analysis and for determining optimal factoring strategies. Recent results are reviewed and extended within this framework.     

Reliability of directed networks using the factoring theorem

The authors present a framework in which the factoring theorem can be used in conjunction with other network reductions and simplifications to determine the reliability of source-to-sink communication in a directed network. On published test networks, the proposed microcomputer implementation of this framework solves the two-terminal reliability problem substantially faster than existing implementations of other current algorithms     

A linear-time algorithm to compute the reliability of planarcube-free networks

A planar graph G=(V,E) is a cube-free graph (CF graph) if it has no subgraph homomorphic to the cube. The cube is the graph whose vertices and edges are the vertices and edges of the three dimensional geometric cube. The all-terminal reliability of a graph G whose edges can fail (with known probabilities) is the probability that G is connected. The problem of computing the all-terminal reliability of a general graph is NP-hard. An O(| V|) time algorithm for computing the all-terminal reliability of CF graphs is presented     

On the average delay for routing subject to independent deflections

Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p . At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is roughly, at least H(p)/(1-h(q), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable in the case where the packet always begins at a fixed node. Also considered is the maximum, over all pairs of nodes in a graph, of the mean transit time from one node to the other. The work is motivated by the search for graphs that work well in conjunction with deflection routing in communication networks     

Hypermedia and network reliability

A simple algorithm utilizing the factoring theorem and other elementary network reductions is available to determine network reliability in a number of different forms. This paper describes a computer-based implementation of such an algorithm housed in a hypermedia environment. The environment can provide for both the formulation and the solution of reliability problems. In our treatment the user draws the network interactively on the computer screen and clicks an on-screen button to perform the reliability analysis. This provides an alternative to manual calculations that become tedious or impossible with networks which are neither series-parallel nor extremely small.     

Reliability evaluation of a limited-flow network in terms ofminimal cutsets

Many systems can be regarded as flow networks whose arcs have discrete and multi-valued random capacities. The probability of the maximum flow at each various level and the reliability of such a flow network can be calculated in terms of K-lattices which are generated from each subset of the family of all MCs (minimal cutsets). However the size of such a family 2^m-1 (m=number of MCs) grows exponentially with m. Such a flow network can be considered as a multistate system with multistate components so that its reliability can be evaluated in terms of upper boundary points of each level d (named d-MCs here). This work presents an algorithm to generate all d-MCs from each MC for each system capacity level d. The new algorithm is analyzed and compared with the algorithm given by J. Xue (1985). Examples show how all d-MCs are generated; the reliability of one example is computed     

Reliability of networks of three-state devices

A three-state device is a device that can exhibit two different types of failure mode, an “open” failure and a “shorted” failure. This paper treats networks whose arcs may experience these two failure modes in addition to the normal “success” state. The network is undirected and has two designated nodes as source and sink. Such a network is itself subject to each of the two failure modes, and the reliability problem considered is computation of the probability of each of the three states of the network. Our observation is that such problems are easily reduced to the usual two-state network reliability problem for which common techniques such as the factoring theorem are readily applicable.     

Evaluation of system reliability with common-cause failures, by apseudo-environments model

An efficient method for calculating system reliability with CCFs (common-cause failures) is presented by applying the factoring (total probability) theorem when the system and its associated class of CCFs are both arbitrary. Existing methods apply this theorem recursively until no CCF remains to be considered, and so can be time-consuming in computation. The method applies such a theorem only once and can be carried out in two steps: (1) determine each state in terms of the occurrence (or not) of every CCF in the associated class, to regard it as a pseudo-environment and to calculate its probability or weight; (2) determine each resulting subsystem of the system under the environment, calculate its reliability as in the no CCF case and take the weighted sum of such reliabilities, viz, the system reliability. This method is in terms of a Markov process and requires only the occurrence rate of each CCF to obtain the probability of each environment and only the failure rate of each component to obtain the system reliability under each environment; hence, it is practical, efficient, and useful     

Calculation of the binomial survivor function [reliabilityapplications]

A method is presented for calculating the binomial SF (cumulative binomial distribution), binfc(k;p,n), especially for a large n, beyond the range of existing tables, where conventional computer programs fail because of underflow and overflow, and Gaussian or Poisson approximations yield insufficient accuracy for the purpose at hand. This method is used to calculate and sum the individual binomial terms while using multiplication factors to avoid underflow; the factors are then divided out of the partial sum whenever it has the potential to overflow. A computer program uses this technique to calculate the binomial SF for arbitrary inputs of k, p, and n. Two other algorithms are presented to determine the value of p needed to yield a specified SF for given values of k and n and calculate the value where p=SF for a given k and n. Reliability applications of each algorithm/program are given, e.g. the value of p needed to achieve a stated k-out-of-n :G system reliability and the value of p for which k -out-of-n:G system reliability equals p     

Consecutive-2-of-n:F systems with node and link failures

It has always been assumed that nodes can fail but not links, although most examples given for the consecutive-k-out-of-n :F system show no reason for such an assumption. The system described not only allows links to fail, but allows both nodes and links to fail, with distinct probabilities. For the k=2 case, the authors set up recursive equations for system reliability, and give a closed-form solution. It is proved that for n large, the reliability is decreasing in n (with one exceptional case) and higher reliability should be provided to the nodes, and then to the longer links rather than to shorter links     

Packet error probabilities in frequency-hopped spread-spectrumpacket radio networks-memoryless frequency-hopping patterns considered

The packet error probability induced in a frequency-hopped spread-spectrum packet radio network is computed. The frequency spectrum is divided into q frequency bins. Each packet is exactly one codeword from an (M, L) Reed-Solomon code [M=number of codeword symbols (bytes); L=number of information symbols (bytes)]. Every user in the network sends each of the M bytes of his packet at a frequency chosen among the q frequencies with equal probability and independently of the frequencies chosen for other bytes (i.e., memoryless frequency-hopping patterns). Statistically independent frequency-hopping patterns correspond to different users in the network. Provided that K users have simultaneously transmitted their packets on the channel and a receiver has locked on to one of these K packets, the probability that this packet is not decoded correctly is evaluated. It is also shown that although memoryless frequency-hopping patterns are utilized, the byte errors at the receiver are not statistically independent; instead they exhibit a Markovian structure     

A coherent model for reliability of multiprocessor networks

Graph G has perfectly reliable nodes and edges that are subject to stochastic failure. The network reliability R is the probability that the surviving edges induce a spanning connected subgraph of G. Analysis problems concern determining efficient algorithms to calculate R, which is known to be NP-hard for general graphs. Synthesis problems concern determining graphs that are, according to some definition, the most reliable in the class of all graphs having a given number of edges and nodes. In applications where the edges are perfectly reliable and the nodes are subject to failure, another measure (residual node connectedness reliability) is defined as the probability that the surviving nodes induce a connected subgraph of G. Referring to such a subset as an operating state, the measure is not coherent because a superset of an operating state need not be an operating state. This paper proposes a new definition of network reliability that handles the case of node failures; it is coherent. We determine many of its properties, and present several analysis and synthesis results     

State-dependent routing on symmetric loss networks with trunkreservations. I

The aggregated-least-busy-alternative (ALBA), a distributed, state-dependent, dynamic routing strategy for circuit-switched loss networks is discussed. The networks considered are symmetric and fully connected. The offered calls form Poisson streams, and routes have at most two links. In ALBA(K), the states of each link are lumped into K (K⩾2) aggregates, and the route of each call is determined by local information on the aggregate states of the links of the alternate routes at the time of the call's arrival. The last aggregate is always the set of states reserved for direct traffic. A fixed-point model for ALBA(K) for general K is presented. The particular case of ALBA in which there is no aggregation is least busy alternative (LBA); ALBA(2) represents the other extreme of aggregation. Simulation and analytic results for LBA are compared. An asymptotic scaling based on the fixed-point models is also discussed. It is shown that there is a dichotomy in network behavior: if the offered traffic is below a threshold, then the network loss probability decreases exponentially with increasing network size, and above the threshold, performance is poor     

Reliability polynomial for a ring network

A mathematical model is developed for the reliability of a system made up of m unreliable nodes arranged in a ring. The model can be used to calculate the reliability of single-ring networks in which the network recovery mechanism depends on bypassing failed stations, but link signal power margins are inadequate to overcome losses due to more than n bypass switches in series. Computational complexity is 0(n²m+nm²/2) in time, and 0(m²/2) in memory requirements     

A computer approach for reliability evaluation of telecommunicationnetworks with heterogeneous link-capacities

The authors present a computer approach to obtaining a survivability index called capacity related reliability (CRR) in large telecommunication networks where links have different capacities. The method is a two-step approach. The first step deals with composite path enumeration (CPE). A k-composite path is defined as the union of the set of edges in any k simple paths and relates link capacity and network connectivity. The CPE approach is an improvement over the algorithms proposed by the authors earlier (1991). In step two, k-composite paths information is manipulated to generate the CRR. The authors use CAREL (computer aided reliability evaluator) to solve this step. The technique is automated using C on the Encore Multimax System. The results on CRR for three networks with various values of minimum message capacity are presented. An exhaustive technique is used to verify these results. An informal proof of the CPE approach is also included     

Automated tracking of ice floes: a stochastic approach

A method for tracking ice floes in sequential satellite imagery is presented. The approach, based on probability distributions, directly incorporates the spatial information about feature locations into the estimation procedure. Given an image taken at time t₀, a probability model is used to determine how features in the image will appear at time t₁, and the probability distribution is used to identify features common to both images. The use of a probability model provides a means to measure the goodness of fit of the resulting matches. The features used are the outlines of sea ice floes observed in SAR (synthetic aperture radar) images, although the method can be applied to any set of features. The floe outlines are found using an erosion-propagation algorithm which combines erosion from mathematical morphology with local propagation of information about floe edges