Performance Analysis and Optimization of Stochastic Monotone Networks Using Permutational Methods

In this paper we show how the permutation Monte Carlo method, orig-inally developed for reliability networks, can be extended to stochastic monotone networks subject to edge failures, and in particular for estima-tion of the probability that the sample performance is above some fixed level. By a stochastic monotone network we understand a network whose performance function is monotone with respect to the edges failure proba-bility vector. In addition to the networks monotonicity property we require existing of an algorithm (oracle) capable of finding in polynomial time its performance value under perfect edges. We consider two models; one where the edges fail with the same probability and another where they fail with different ones. For each model we design a different algorithm for esti-mating the desired probability; in the former case it is based on the well known D-spectrum method and in the latter one- on the permutational Monte Carlo. We also discuss the convergence properties of our estimator