This paper analyzes a sampling method proposed by Fishman (1986) for computing the 2-terminal and global reliability of a network. It describes the sampling algorithm, and computation experiments on networks corresponding to a real situation as well as examples from the literature. A communication network is modeled by an undirected graph as a function of the set of vertices (the network nodes) and the set of edges (the links connecting pairs of vertices). Each edge is in 1 of 2 states (operational and failed). Failures are assumed to be statistically independent. A network is connected if the set of edges that are operational, forms a spanning connected subgraph (a subgraph containing at least 1 operational path between any 2 vertices). The problems of computing: (1) the 2-terminal network reliability (probability that between 2 given vertices there exists at least 1 operational path); and (2) the global network reliability (probability that the network is connected), are treated. This paper provides: (i) a detailed, clear exposition of the Fishman method, (ii) a complete description of the corresponding algorithm, (iii) its extension for computing global reliability (problem 2), and (iv) computational experiments on networks both new and in the literature. A Monte Carlo approach for these problems is fully justified by looking at their computational complexity. The exact computation of the network reliability (either 2-terminal or global) is a /spl npar/P-complete problem. If one looks for efficient algorithms, one must settle for approximations obtained by a heuristic procedure.

A parametric model is proposed for the cell arrival traffic on the input lines of a switch. The cell stream alternates between active and silent periods, and general distributions are allowed for the lengths of these periods. The traffic is represented by a discrete Markov chain model obtained through a simple moment matching procedure. The cell arrivals at in input port of the switch are typically non-Poisson and exhibit periodicities. The simulation experiments illustrate that each parameter included in the model has a significant impact on the performance of the switch (as measured by cell-loss probabilities, average cell delay, and steady-state queue length distribution).>

A computer system consisting of several identical CPUs and several identical I/O units Is described The system works under light load conditions in a multlprogrammmg mode Programs belong either to an incoming queue, which may be empty, or to an inner loop if they are allowed access to the resources of the system The maximum number of programs in the inner loop is finite Under Markovlan assumptions it is shown that the steady-state probablhty distribution is of matrixgeometric form.The stablhty condition is exphcltly given For stable systems It Is shown how the stationary probability distribution, the virtual waiting time in the incoming queue, and other features of interest may be computed

Consider a finite waiting room shared by several servers. Such a system may approximate, for instance, a packet switch in a communications network. It is assumed that interarrival and service times have exponential distributions, and that a customer is lost if he cannot enter the waiting room. Different policies for sharing the finite waiting room are compared-the measure of performance being the probability that a customer is lost.