A note on state-space decomposition methods for analyzing stochastic flow networks

Consider a flow network with single source s and single sink t with demand d>0. Assume that the nodes do not restrict flow transmission and the arcs have finite random discrete capacities. This paper has two objectives: (1) it corrects errors in well-known algorithms by Doulliez and Jamoulle (1972) for (a) computing the probability that the demand is satisfied (or network reliability), (b) the probability that an arc belongs to a minimum cut which limits the flow below d, and (c) the probability that a cut limits the flow below d; and (2) it discusses the applicability of these procedures. The Doulliez and Jamoulle algorithms are frequently referenced or used by researchers in the areas of power and communication systems and appear to be very effective for the computation of the network reliability when the demand is close to the largest possible maximum flow value. Extensive testing is required before the Doulliez and Jamoulle algorithms are disposed in favor of alternative approaches. Such testing should compare the performance of existing methods in a variety of networks including grid networks and dense networks of various sizes